"A [[MutableSet]] implemented as a hash set stored in an [[Array]] of singly linked lists. Each element is assigned an index of the array according to its hash code. The hash code of an element is defined by [[Object.hash]]. The [[stability]] of a `HashSet` controls its iteration order: - A [[linked]] set has a stable and meaningful order of iteration. The elements of the set form a linked list, where new elements are added to the end of the linked list. Iteration of the set follows this linked list, from least recently added elements to most recently added elements. - An [[unlinked]] set has an unstable iteration order that may change when the set is modified. The order itself is not meaningful to a client. The stability is `linked` by default. The management of the backing array is controlled by the given [[hashtable]]." by ("Stéphane Épardaud", "Gavin King") shared serializable class HashSet<Element> satisfies MutableSet<Element> given Element satisfies Object { "Determines whether this is a linked hash set with a stable iteration order." Stability stability; "Performance-related settings for the backing array." Hashtable hashtable; "Array of linked lists where we store the elements. Each element is stored in a linked list from this array at the index of the hash code of the element, modulo the array size." variable Array<CachingCell<Element>?> store; "The initial elements of the set." {Element*} elements; "Number of elements in this set." variable Integer length; "Head of the traversal linked list if in `linked` mode. Storage is done in [[store]], but traversal is done using an alternative linked list maintained to have a stable iteration order. Note that the cells used are the same as in the [[store]], except for storage we use [[CachingCell.rest]] for traversal, while for the stable iteration we use the [[LinkedCell.next]]/[[LinkedCell.previous]] attributes of the same cell." variable LinkedCell<Element>? head = null; "Tip of the traversal linked list if in `linked` mode." variable LinkedCell<Element>? tip = null; Boolean accurateInitialCapacity; "Create a new `HashSet` with the given initial elements." shared new ( "Determines whether this is a linked hash set with a stable iteration order, defaulting to [[linked]] (stable)." Stability stability = linked, "Performance-related settings for the backing array." Hashtable hashtable = Hashtable(), "The initial elements of the set, defaulting to no initial elements." {Element*} elements = {}) { this.stability = stability; this.hashtable = hashtable; this.elements = elements; length = 0; // For Collections, we can efficiently obtain an // accurate initial capacity. For a generic iterable, // just use the given initialCapacity. accurateInitialCapacity = elements is Collection<Anything>; value initialCapacity = accurateInitialCapacity then hashtable.initialCapacityForSize(elements.size) else hashtable.initialCapacityForUnknownSize(); store = cachingElementStore<Element>(initialCapacity); } "Create a new `HashSet` with the same initial elements as the given [[hashSet]]." shared new copy( "The `HashSet` to copy." HashSet<Element> hashSet, "Determines whether this is a linked hash set with a stable iteration order, defaulting to the stability of the copied `HashSet`." Stability stability = hashSet.stability, "Performance-related settings for the backing array." Hashtable hashtable = Hashtable()) { this.stability = stability; this.hashtable = hashtable; accurateInitialCapacity = true; store = cachingElementStore<Element>(hashSet.store.size); if (stability == unlinked) { elements = {}; length = hashSet.length; variable Integer index = 0; // walk every bucket while (index < hashSet.store.size) { if (exists bucket = hashSet.store[index]) { store[index] = bucket.clone(); } index++; } } else { //TODO!!!! length = 0; elements = hashSet; } } // Write function hashCode(Object key) => let (h = key.hash) h.xor(h.rightLogicalShift(16)); Integer storeIndex(Integer elemHash, Array<CachingCell<Element>?> store) => elemHash.and(store.size - 1); //=> (elem.hash % store.size).magnitude; CachingCell<Element> createCell(Element elem, Integer elemHash, CachingCell<Element>? rest) { if (stability == linked) { value cell = LinkedCell(elem, elemHash, rest, tip); if (exists last = tip) { last.next = cell; } tip = cell; if (!head exists) { head = cell; } return cell; } else { return CachingCell(elem, elemHash, rest); } } void deleteCell(CachingCell<Element> cell) { if (stability == linked) { assert (is LinkedCell<Element> cell); if (exists last = cell.previous) { last.next = cell.next; } else { head = cell.next; } if (exists next = cell.next) { next.previous = cell.previous; } else { tip = cell.previous; } } } Boolean addToStore(Array<CachingCell<Element>?> store, Element element) { value elementHash = hashCode(element); Integer index = storeIndex(elementHash, store); value headBucket = store[index]; variable value bucket = headBucket; while (exists cell = bucket) { if (cell.keyHash == elementHash && cell.element == element) { // modify an existing entry cell.element = element; return false; } bucket = cell.rest; } // add a new entry store[index] = createCell(element, elementHash, headBucket); return true; } void checkRehash() { if (hashtable.rehash(length, store.size)) { // must rehash value newStore = cachingElementStore<Element> (hashtable.capacity(length)); variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { bucket = cell.rest; Integer newIndex = storeIndex(cell.keyHash, newStore); value newBucket = newStore[newIndex]; cell.rest = newBucket; newStore[newIndex] = cell; } index++; } store = newStore; } } // Add initial values for (val in elements) { if (addToStore(store, val)) { length++; } } // After collecting all the initial // values, rebuild the hashtable if // necessary if (!accurateInitialCapacity) { checkRehash(); } // End of initialiser section shared actual Boolean add(Element element) { if (addToStore(store, element)) { length++; checkRehash(); return true; } return false; } shared actual Boolean addAll({Element*} elements) { variable Boolean ret = false; for (elem in elements) { if (addToStore(store, elem)) { length++; ret = true; } } if (ret) { checkRehash(); } return ret; } shared actual Boolean remove(Element element) { value elementHash = hashCode(element); Integer index = storeIndex(elementHash, store); if (exists head = store[index], head.element == element) { store[index] = head.rest; deleteCell(head); length--; return true; } variable value bucket = store[index]; while (exists cell = bucket) { value rest = cell.rest; if (exists rest, rest.keyHash == elementHash, rest.element == element) { cell.rest = rest.rest; deleteCell(rest); length--; return true; } else { bucket = rest; } } return false; } shared actual void clear() { variable Integer index = 0; // walk every bucket while (index < store.size) { store[index++] = null; } length = 0; head = null; tip = null; } // Read size => length; iterator() => stability == linked then LinkedCellIterator(head) else CachingStoreIterator(store); shared actual Integer count (Boolean selecting(Element element)) { variable Integer count = 0; variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { if (selecting(cell.element)) { count++; } bucket = cell.rest; } index++; } return count; } shared actual void each(void step(Element element)) { store.each((bucket) { variable value iter = bucket; while (exists cell = iter) { step(cell.element); iter = cell.rest; } }); } shared actual Integer hash { variable value index = 0; variable value hash = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { hash += cell.element.hash; bucket = cell.rest; } index++; } return hash; } shared actual Boolean equals(Object that) { if (is HashSet<Anything> that, this===that) { return true; } else if (is Set<> that, that.size==length) { variable value index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { if (!cell.element in that) { return false; } bucket = cell.rest; } index++; } return true; } else { return false; } } shared actual HashSet<Element> clone() => copy(this); shared actual Boolean contains(Object element) { if (empty) { return false; } else { value elementHash = hashCode(element); Integer index = storeIndex(elementHash, store); variable value bucket = store[index]; while (exists cell = bucket) { if (cell.keyHash == elementHash && cell.element == element) { return true; } bucket = cell.rest; } return false; } } shared actual HashSet<Element> complement<Other> (Set<Other> set) given Other satisfies Object { value ret = HashSet<Element>(); for (elem in this) { if (!(elem in set)) { ret.add(elem); } } return ret; } shared actual HashSet<Element|Other> exclusiveUnion<Other> (Set<Other> set) given Other satisfies Object { value ret = HashSet<Element|Other>(); for (elem in this) { if (!(elem in set)) { ret.add(elem); } } for (elem in set) { if (!(elem in this)) { ret.add(elem); } } return ret; } shared actual HashSet<Element&Other> intersection<Other> (Set<Other> set) given Other satisfies Object { value ret = HashSet<Element&Other>(); for (elem in this) { if (elem in set, is Other elem) { ret.add(elem); } } return ret; } shared actual HashSet<Element|Other> union<Other> (Set<Other> set) given Other satisfies Object { value ret = HashSet<Element|Other>(); ret.addAll(this); ret.addAll(set); return ret; } shared actual Element? first => if (stability == linked) then head?.element else store.coalesced.first?.element; shared actual Element? last { if (stability == linked) { return tip?.element; } else { variable value bucket = store.reversed.coalesced.first; while (exists cell = bucket?.rest) { bucket = cell; } return bucket?.element; } } }