"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;
}
}
}