OrderedMap
OrderedMap: OrderedMap, ~OrderedMap, size, empty, contains, operator[], insert, remove, find, findNode, lowerKey, lowerNode, higherKey, higherNode, first, firstNode, last, lastNode, iterator
OrderedMapIterator: OrderedMapIterator, hasValue, value, increment
struct OrderedMap<Key, Value>
An ordered key-value container that supports fast insertion, deletion and lookup
OrderedMap
OrderedMap()Initializes an empty map.
~OrderedMap
~OrderedMap()Frees all nodes.
size
int size()Returns the size of the Map
empty
bool empty()Returns true if the Map is empty, otherwise false
contains
bool contains(Key& key)Checks if the given element is in the Map. Returns true if it is, otherwise false
operator[]
Value&? operator[](Key& key)Returns the value of the given key, if it exists in the Map. Otherwise, returns null.
insert
bool insert(Key key, Value value)Inserts a key-value pair into the Map.
remove
void remove(Key& key)Removes a key and it's associated value from the Map
find
MapEntry<Key, Value>&? find(Key& key)Returns the key-value pair corresponding to key, or null
if it doesn't exist in the Map
findNode
AVLnode<Key, Value>*? findNode(Key& key)Returns the node corresponding to key, or null if it
doesn't exist in the Map
lowerKey
Key&? lowerKey(Key& key)Returns the key immediately smaller than the one given, or null, if
key is the smallest in the Map.
lowerNode
AVLnode<Key, Value>*? lowerNode(AVLnode<Key, Value>* node)Returns the node that contains the key immediately smaller than the
key of the given node, or null, if the key of node is the
smallest value.
higherKey
Key&? higherKey(Key& key)Returns the key immediately higher than the one given, or null, if
key is the largest in the Map.
higherNode
AVLnode<Key, Value>*? higherNode(AVLnode<Key, Value>* node)Returns the node that contains the key immediately larger than the
key of the given node, or null, if the key of node is the
largest value.
first
Key&? first()Returns the smallest element in the Map, or null if the Map is empty.
firstNode
AVLnode<Key, Value>*? firstNode()Returns the node with the smallest key in the Map, or null if the Map is empty.
last
Key&? last()Returns the largest element in the Map, or null if the map is empty.
lastNode
AVLnode<Key, Value>*? lastNode()Returns the node with the largest key in the Map, or null if the Map is empty.
iterator
OrderedMapIterator<Key, Value> iterator()Iterate over the map, in order
struct AVLnode<Key, Value>
One node in the AVL tree
AVLnode
AVLnode(Key key, AVLnode<Key, Value>*? parent, Value value)Initializes a node holding the given key and value.
deallocate
void deallocate()Frees the subtree rooted at this node.
struct OrderedMapIterator<Key, Value>: Copyable, Iterator<MapEntry<Key, Value>&>
Iterates over the entries of an ordered map, in order.
OrderedMapIterator
OrderedMapIterator(OrderedMap<Key, Value>& map)Initializes an iterator over the given map.
hasValue
bool hasValue()Returns true if there are more entries.
value
MapEntry<Key, Value>& value()Returns the current entry.
increment
void increment()Advances to the next entry.