"An identity map implemented as a hash map stored in an [[Array]] of singly linked lists of [[Entry]]s. The hash code of a key is defined by [[identityHash]]. Note that an `IdentityMap` is not a [[Map]], since it does not obey the semantics of a `Map`. In particular, it may contain multiple keys which are equal, as determined by the `==` operator." by ("Gavin King") shared serializable class IdentityMap<Key, Item> (hashtable=Hashtable(), entries = {}) satisfies {<Key->Item>*} & Collection<Key->Item> & Correspondence<Key,Item> given Key satisfies Identifiable { "The initial entries in the map." {<Key->Item>*} entries; "Performance-related settings for the backing array." Hashtable hashtable; variable value store = entryStore<Key,Item> (hashtable.initialCapacity); variable Integer length = 0; // Write Integer storeIndex(Identifiable key, Array<Cell<Key->Item>?> store) => (identityHash(key) % store.size).magnitude; Boolean addToStore(Array<Cell<Key->Item>?> store, Key->Item entry) { Integer index = storeIndex(entry.key, store); value headBucket = store[index]; variable value bucket = headBucket; while (exists cell = bucket) { if (cell.element.key === entry.key) { // modify an existing entry cell.element = entry; return false; } bucket = cell.rest; } // add a new entry store[index] = Cell(entry, headBucket); return true; } void checkRehash() { if (hashtable.rehash(length, store.size)) { // must rehash value newStore = entryStore<Key,Item> (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.element.key, newStore); value newBucket = newStore[newIndex]; cell.rest = newBucket; newStore[newIndex] = cell; } index++; } store = newStore; } } // Add initial values for (entry in entries) { if (addToStore(store, entry)) { length++; } } checkRehash(); // End of initialiser section shared Item? put(Key key, Item item) { Integer index = storeIndex(key, store); value entry = key->item; value headBucket = store[index]; variable value bucket = headBucket; while (exists cell = bucket) { if (cell.element.key === key) { Item oldItem = cell.element.item; // modify an existing entry cell.element = entry; return oldItem; } bucket = cell.rest; } // add a new entry store[index] = Cell(entry, headBucket); length++; checkRehash(); return null; } "Adds a collection of key/value mappings to this map, may be used to change existing mappings" shared void putAll({<Key->Item>*} entries) { for (entry in entries) { if (addToStore(store, entry)) { length++; } } checkRehash(); } shared Boolean replaceEntry(Key key, Item&Object item, Item newItem) { Integer index = storeIndex(key, store); variable value bucket = store[index]; while (exists cell = bucket) { if (cell.element.key === key) { if (exists oldItem = cell.element.item, oldItem==item) { // modify an existing entry cell.element = key->newItem; return true; } else { return false; } } bucket = cell.rest; } return false; } "Removes a key/value mapping if it exists" shared Item? remove(Key key) { Integer index = storeIndex(key, store); if (exists head = store[index], head.element.key === key) { store[index] = head.rest; length--; return head.element.item; } variable value bucket = store[index]; while (exists cell = bucket) { value rest = cell.rest; if (exists rest, rest.element.key === key) { cell.rest = rest.rest; length--; return rest.element.item; } else { bucket = rest; } } return null; } "Remove the entries associated with the given keys, if any, from this map" shared void removeAll({Key*} keys) { for (key in keys) { remove(key); } } shared Boolean removeEntry(Key key, Item&Object item) { Integer index = storeIndex(key, store); while (exists head = store[index], head.element.key === key) { if (exists it = head.element.item, it==item) { store[index] = head.rest; length--; return true; } else { return false; } } variable value bucket = store[index]; while (exists cell = bucket) { value rest = cell.rest; if (exists rest, rest.element.key === key) { if (exists it = rest.element.item, it==item) { cell.rest = rest.rest; length--; return true; } else { return false; } } else { bucket = rest; } } return false; } "Removes every key/value mapping" shared void clear() { variable Integer index = 0; // walk every bucket while (index < store.size) { store[index++] = null; } length = 0; } // Read size => length; shared actual Item? get(Key key) { if (empty) { return null; } Integer index = storeIndex(key, store); variable value bucket = store[index]; while (exists cell = bucket) { if (cell.element.key === key) { return cell.element.item; } bucket = cell.rest; } return null; } /*shared Collection<Item> values { value ret = LinkedList<Item>(); variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index); while (exists cell = bucket) { ret.add(cell.element.item); bucket = cell.rest; } index++; } return ret; } shared actual IdentitySet<Key> keys { value ret = IdentitySet<Key>(); variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index); while (exists cell = bucket) { ret.add(cell.element.key); bucket = cell.rest; } index++; } return ret; } shared actual Map<Item,Set<Key>> inverse { value ret = HashMap<Item,MutableSet<Key>>(); variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index); while (exists cell = bucket) { if (exists keys = ret[cell.car.item]) { keys.add(cell.car.key); }else{ value k = HashSet<Key>(); ret.put(cell.car.item, k); k.add(cell.car.key); } bucket = cell.cdr; } index++; } return ret; }*/ iterator() => StoreIterator(store); shared actual Integer count(Boolean selecting(Key->Item element)) { variable Integer index = 0; variable Integer count = 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(Key->Item element)) { store.each((bucket) { variable value iter = bucket; while (exists cell = iter) { step(cell.element); iter = cell.rest; } }); } shared actual Integer hash { variable Integer index = 0; variable Integer hash = 17; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { hash = (hash * 31 + identityHash(cell.element.key))*31; if (exists item = cell.element.item) { hash += item.hash; } bucket = cell.rest; } index++; } return hash; } shared actual Boolean equals(Object that) { if (is IdentityMap<Object,Object> that) { if (this===that) { return true; } if (size == that.size) { variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { value thatItem = that.get(cell.element.key); if (exists thisItem = cell.element.item) { if (exists thatItem) { if (thatItem != thisItem) { return false; } } else { return false; } } else if (thatItem exists) { return false; } bucket = cell.rest; } index++; } return true; } } return false; } shared actual IdentityMap<Key,Item> clone() { value clone = IdentityMap<Key,Item>(); clone.length = length; clone.store = entryStore<Key,Item>(store.size); variable Integer index = 0; // walk every bucket while (index < store.size) { if (exists bucket = store[index]) { clone.store[index] = bucket.clone(); } index++; } return clone; } shared actual Boolean defines(Key key) { variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { if (cell.element.key === key) { return true; } bucket = cell.rest; } index++; } return false; } shared actual Boolean contains(Object element) { variable Integer index = 0; // walk every bucket while (index < store.size) { variable value bucket = store[index]; while (exists cell = bucket) { if (exists it = cell.element.item, it == element) { return true; } bucket = cell.rest; } index++; } return false; } }