# # # Nim's Runtime Library # (c) Copyright 2015 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # ## The `tables` module implements variants of an efficient `hash table`:idx: ## (also often named `dictionary`:idx: in other programming languages) that is ## a mapping from keys to values. ## ## There are several different types of hash tables available: ## * `Table<#Table>`_ is the usual hash table, ## * `OrderedTable<#OrderedTable>`_ is like `Table` but remembers insertion order, ## * `CountTable<#CountTable>`_ is a mapping from a key to its number of occurrences ## ## For consistency with every other data type in Nim these have **value** ## semantics, this means that `=` performs a copy of the hash table. ## ## For `ref semantics`_ ## use their `Ref` variants: `TableRef<#TableRef>`_, ## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. ## ## To give an example, when `a` is a `Table`, then `var b = a` gives `b` ## as a new independent table. `b` is initialised with the contents of `a`. ## Changing `b` does not affect `a` and vice versa: runnableExamples: var a = {1: "one", 2: "two"}.toTable # creates a Table b = a assert a == b b[3] = "three" assert 3 notin a assert 3 in b assert a != b ## On the other hand, when `a` is a `TableRef` instead, then changes to `b` ## also affect `a`. Both `a` and `b` **ref** the same data structure: runnableExamples: var a = {1: "one", 2: "two"}.newTable # creates a TableRef b = a assert a == b b[3] = "three" assert 3 in a assert 3 in b assert a == b ## ## ---- ## ## # Basic usage ## ## Table runnableExamples: from std/sequtils import zip let names = ["John", "Paul", "George", "Ringo"] years = [1940, 1942, 1943, 1940] var beatles = initTable[string, int]() for pairs in zip(names, years): let (name, birthYear) = pairs beatles[name] = birthYear assert beatles == {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940}.toTable var beatlesByYear = initTable[int, seq[string]]() for pairs in zip(years, names): let (birthYear, name) = pairs if not beatlesByYear.hasKey(birthYear): # if a key doesn't exist, we create one with an empty sequence # before we can add elements to it beatlesByYear[birthYear] = @[] beatlesByYear[birthYear].add(name) assert beatlesByYear == {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]}.toTable ## ## OrderedTable ## `OrderedTable<#OrderedTable>`_ is used when it is important to preserve ## the insertion order of keys. runnableExamples: let a = [('z', 1), ('y', 2), ('x', 3)] ot = a.toOrderedTable # ordered tables assert $ot == """{'z': 1, 'y': 2, 'x': 3}""" ## ## CountTable ## `CountTable<#CountTable>`_ is useful for counting number of items of some ## container (e.g. string, sequence or array), as it is a mapping where the ## items are the keys, and their number of occurrences are the values. ## For that purpose `toCountTable proc<#toCountTable,openArray[A]>`_ ## comes handy: runnableExamples: let myString = "abracadabra" let letterFrequencies = toCountTable(myString) assert $letterFrequencies == "{'a': 5, 'd': 1, 'b': 2, 'r': 2, 'c': 1}" ## The same could have been achieved by manually iterating over a container ## and increasing each key's value with `inc proc ## <#inc,CountTable[A],A,int>`_: runnableExamples: let myString = "abracadabra" var letterFrequencies = initCountTable[char]() for c in myString: letterFrequencies.inc(c) assert $letterFrequencies == "{'d': 1, 'r': 2, 'c': 1, 'a': 5, 'b': 2}" ## ## ---- ## ## ## Hashing ## ## If you are using simple standard types like `int` or `string` for the ## keys of the table you won't have any problems, but as soon as you try to use ## a more complex object as a key you will be greeted by a strange compiler ## error: ## ## .. code:: ## ## Error: type mismatch: got (Person) ## but expected one of: ## hashes.hash(x: openArray[A]): Hash ## hashes.hash(x: int): Hash ## hashes.hash(x: float): Hash ## … ## ## What is happening here is that the types used for table keys require to have ## a `hash()` proc which will convert them to a `Hash `_ ## value, and the compiler is listing all the hash functions it knows. ## Additionally there has to be a `==` operator that provides the same ## semantics as its corresponding `hash` proc. ## ## After you add `hash` and `==` for your custom type everything will work. ## Currently, however, `hash` for objects is not defined, whereas ## `system.==` for objects does exist and performs a "deep" comparison (every ## field is compared) which is usually what you want. So in the following ## example implementing only `hash` suffices: runnableExamples: import std/hashes type Person = object firstName, lastName: string proc hash(x: Person): Hash = ## Piggyback on the already available string hash proc. ## ## Without this proc nothing works! result = x.firstName.hash !& x.lastName.hash result = !$result var salaries = initTable[Person, int]() p1, p2: Person p1.firstName = "Jon" p1.lastName = "Ross" salaries[p1] = 30_000 p2.firstName = "소진" p2.lastName = "박" salaries[p2] = 45_000 ## ## ---- ## ## # See also ## ## * `json module`_ for table-like structure which allows ## heterogeneous members ## * `strtabs module`_ for efficient hash tables ## mapping from strings to strings ## * `hashes module`_ for helper functions for hashing import std/private/since import hashes, math, algorithm when not defined(nimHasEffectsOf): {.pragma: effectsOf.} type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] KeyValuePairSeq[A, B] = seq[KeyValuePair[A, B]] Table*[A, B] = object ## Generic hash table, consisting of a key-value pair. ## ## `data` and `counter` are internal implementation details which ## can't be accessed. ## ## For creating an empty Table, use `initTable proc<#initTable>`_. data: KeyValuePairSeq[A, B] counter: int TableRef*[A, B] = ref Table[A, B] ## Ref version of `Table<#Table>`_. ## ## For creating a new empty TableRef, use `newTable proc ## <#newTable>`_. const defaultInitialSize* = 32 # ------------------------------ helpers --------------------------------- # Do NOT move these to tableimpl.nim, because sharedtables uses that # file and has its own implementation. template maxHash(t): untyped = high(t.data) template dataLen(t): untyped = len(t.data) include tableimpl proc raiseKeyError[T](key: T) {.noinline, noreturn.} = when compiles($key): raise newException(KeyError, "key not found: " & $key) else: raise newException(KeyError, "key not found") template get(t, key): untyped = ## retrieves the value at `t[key]`. The value can be modified. ## If `key` is not in `t`, the `KeyError` exception is raised. mixin rawGet var hc: Hash var index = rawGet(t, key, hc) if index >= 0: result = t.data[index].val else: raiseKeyError(key) proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] newSeq(n, len(t.data) * growthFactor) swap(t.data, n) for i in countup(0, high(n)): let eh = n[i].hcode if isFilled(eh): var j: Hash = eh and maxHash(t) while isFilled(t.data[j].hcode): j = nextTry(j, maxHash(t)) when defined(js): rawInsert(t, t.data, n[i].key, n[i].val, eh, j) else: rawInsert(t, t.data, move n[i].key, move n[i].val, eh, j) # ------------------------------------------------------------------- # ------------------------------ Table ------------------------------ # ------------------------------------------------------------------- proc initTable*[A, B](initialSize = defaultInitialSize): Table[A, B] = ## Creates a new hash table that is empty. ## ## Starting from Nim v0.20, tables are initialized by default and it is ## not necessary to call this function explicitly. ## ## See also: ## * `toTable proc<#toTable,openArray[]>`_ ## * `newTable proc<#newTable>`_ for creating a `TableRef` runnableExamples: let a = initTable[int, string]() b = initTable[char, seq[int]]() initImpl(result, initialSize) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,Table[A,B],A,B>`_ ## * `del proc<#del,Table[A,B],A>`_ for removing a key from the table runnableExamples: var a = initTable[char, int]() a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.toTable putImpl(enlarge) proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = ## Creates a new hash table that contains the given `pairs`. ## ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `initTable proc<#initTable>`_ ## * `newTable proc<#newTable,openArray[]>`_ for a `TableRef` version runnableExamples: let a = [('a', 5), ('b', 9)] let b = toTable(a) assert b == {'a': 5, 'b': 9}.toTable result = initTable[A, B](pairs.len) for key, val in items(pairs): result[key] = val proc `[]`*[A, B](t: Table[A, B], key: A): B = ## Retrieves the value at `t[key]`. ## ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,Table[A,B],A>`_ whether ## the key exists. ## ## See also: ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,Table[A,B],A>`_ for checking if a key is in ## the table runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] get(t, key) proc `[]`*[A, B](t: var Table[A, B], key: A): var B = ## Retrieves the value at `t[key]`. The value can be modified. ## ## If `key` is not in `t`, the `KeyError` exception is raised. ## ## See also: ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,Table[A,B],A>`_ for checking if a key is in ## the table get(t, key) proc hasKey*[A, B](t: Table[A, B], key: A): bool = ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,Table[A,B],A>`_ for use with the `in` operator ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false var hc: Hash result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: Table[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,Table[A,B],A>`_ for use with ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert 'b' in a == true doAssert a.contains('z') == false return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,Table[A,B],A>`_ ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.toTable if a.hasKeyOrPut('a', 50): a['a'] = 99 if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.toTable hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,Table[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,Table[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = ## Retrieves the value at `t[key]` if `key` is in `t`. ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,Table[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,Table[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## ## Note that while the value returned is of type `var B`, ## it is easy to accidentally create a copy of the value at `t[key]`. ## Remember that seqs and strings are value types, and therefore ## cannot be copied into a separate variable for modification. ## See the example below. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,Table[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.toTable doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.toTable # An example of accidentally creating a copy var t = initTable[int, seq[int]]() # In this example, we expect t[10] to be modified, # but it is not. var copiedSeq = t.mgetOrPut(10, @[10]) copiedSeq.add(20) doAssert t[10] == @[10] # Correct t.mgetOrPut(25, @[25]).add(35) doAssert t[25] == @[25, 35] mgetOrPutImpl(enlarge) proc len*[A, B](t: Table[A, B]): int = ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert len(a) == 2 result = t.counter proc add*[A, B](t: var Table[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## ## Use `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. addImpl(enlarge) template tabMakeEmpty(i) = t.data[i].hcode = 0 template tabCellEmpty(i) = isEmpty(t.data[i].hcode) template tabCellHash(i) = t.data[i].hcode proc del*[A, B](t: var Table[A, B], key: A) = ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), ## this may need to be called multiple times. ## ## See also: ## * `pop proc<#pop,Table[A,B],A,B>`_ ## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.toTable a.del('a') doAssert a == {'b': 9, 'c': 13}.toTable a.del('z') doAssert a == {'b': 9, 'c': 13}.toTable delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = ## Deletes the `key` from the table. ## Returns `true`, if the `key` existed, and sets `val` to the ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), ## this may need to be called multiple times. ## ## See also: ## * `del proc<#del,Table[A,B],A>`_ ## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.toTable i: int doAssert a.pop('b', i) == true doAssert a == {'a': 5, 'c': 13}.toTable doAssert i == 9 i = 0 doAssert a.pop('z', i) == false doAssert a == {'a': 5, 'c': 13}.toTable doAssert i == 0 var hc: Hash var index = rawGet(t, key, hc) result = index >= 0 if result: val = move(t.data[index].val) delImplIdx(t, index, tabMakeEmpty, tabCellEmpty, tabCellHash) proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool {.inline.} = ## Alias for: ## * `pop proc<#pop,Table[A,B],A,B>`_ pop(t, key, val) proc clear*[A, B](t: var Table[A, B]) = ## Resets the table so that it is empty. ## ## See also: ## * `del proc<#del,Table[A,B],A>`_ ## * `pop proc<#pop,Table[A,B],A,B>`_ runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.toTable doAssert len(a) == 3 clear(a) doAssert len(a) == 0 clearImpl() proc `$`*[A, B](t: Table[A, B]): string = ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: Table[A, B]): bool = ## The `==` operator for hash tables. Returns `true` if the content of both ## tables contains the same key-value pairs. Insert order does not matter. runnableExamples: let a = {'a': 5, 'b': 9, 'c': 13}.toTable b = {'b': 9, 'c': 13, 'a': 5}.toTable doAssert a == b equalsImpl(s, t) proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] result = initTable[C, B]() for item in collection: result[index(item)] = item template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = ## Retrieves the value at `t[key]`. ## ## `value` can be modified in the scope of the `withValue` call. runnableExamples: type User = object name: string uid: int var t = initTable[int, User]() let u = User(name: "Hello", uid: 99) t[1] = u t.withValue(1, value): # block is executed only if `key` in `t` value.name = "Nim" value.uid = 1314 t.withValue(2, value): value.name = "No" value.uid = 521 assert t[1].name == "Nim" assert t[1].uid == 1314 mixin rawGet var hc: Hash var index = rawGet(t, key, hc) let hasKey = index >= 0 if hasKey: var value {.inject.} = addr(t.data[index].val) body template withValue*[A, B](t: var Table[A, B], key: A, value, body1, body2: untyped) = ## Retrieves the value at `t[key]`. ## ## `value` can be modified in the scope of the `withValue` call. runnableExamples: type User = object name: string uid: int var t = initTable[int, User]() let u = User(name: "Hello", uid: 99) t[1] = u t.withValue(1, value): # block is executed only if `key` in `t` value.name = "Nim" value.uid = 1314 t.withValue(521, value): doAssert false do: # block is executed when `key` not in `t` t[1314] = User(name: "exist", uid: 521) assert t[1].name == "Nim" assert t[1].uid == 1314 assert t[1314].name == "exist" assert t[1314].uid == 521 mixin rawGet var hc: Hash var index = rawGet(t, key, hc) let hasKey = index >= 0 if hasKey: var value {.inject.} = addr(t.data[index].val) body1 else: body2 iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,Table[A,B]>`_ ## * `keys iterator<#keys.i,Table[A,B]>`_ ## * `values iterator<#values.i,Table[A,B]>`_ ## ## **Examples:** ## ## .. code-block:: ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] ## }.toTable ## ## for k, v in a.pairs: ## echo "key: ", k ## echo "value: ", v ## ## # key: e ## # value: [2, 4, 6, 8] ## # key: o ## # value: [1, 5, 7, 9] let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ ## * `mvalues iterator<#mvalues.i,Table[A,B]>`_ runnableExamples: var a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toTable for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.toTable let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator keys*[A, B](t: Table[A, B]): lent A = ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ ## * `values iterator<#values.i,Table[A,B]>`_ runnableExamples: var a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toTable for k in a.keys: a[k].add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A, B](t: Table[A, B]): lent B = ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ ## * `keys iterator<#keys.i,Table[A,B]>`_ ## * `mvalues iterator<#mvalues.i,Table[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toTable for v in a.values: doAssert v.len == 4 let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: var Table[A, B]): var B = ## Iterates over any value in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,Table[A,B]>`_ ## * `values iterator<#values.i,Table[A,B]>`_ runnableExamples: var a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toTable for v in a.mvalues: v.add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator allValues*[A, B](t: Table[A, B]; key: A): B {.deprecated: "Deprecated since v1.4; tables with duplicated keys are deprecated".} = ## Iterates over any value in the table `t` that belongs to the given `key`. ## ## Used if you have a table with duplicate keys (as a result of using ## `add proc<#add,Table[A,B],A,sinkB>`_). ## runnableExamples: import std/[sequtils, algorithm] var a = {'a': 3, 'b': 5}.toTable for i in 1..3: a.add('z', 10*i) doAssert toSeq(a.pairs).sorted == @[('a', 3), ('b', 5), ('z', 10), ('z', 20), ('z', 30)] doAssert sorted(toSeq(a.allValues('z'))) == @[10, 20, 30] var h: Hash = genHash(key) and high(t.data) let L = len(t) while isFilled(t.data[h].hcode): if t.data[h].key == key: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") h = nextTry(h, high(t.data)) # ------------------------------------------------------------------- # ---------------------------- TableRef ----------------------------- # ------------------------------------------------------------------- proc newTable*[A, B](initialSize = defaultInitialSize): TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## See also: ## * `newTable proc<#newTable,openArray[]>`_ for creating a `TableRef` ## from a collection of `(key, value)` pairs ## * `initTable proc<#initTable>`_ for creating a `Table` runnableExamples: let a = newTable[int, string]() b = newTable[char, seq[int]]() new(result) {.noSideEffect.}: result[] = initTable[A, B](initialSize) proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = ## Creates a new ref hash table that contains the given `pairs`. ## ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `newTable proc<#newTable>`_ ## * `toTable proc<#toTable,openArray[]>`_ for a `Table` version runnableExamples: let a = [('a', 5), ('b', 9)] let b = newTable(a) assert b == {'a': 5, 'b': 9}.newTable new(result) {.noSideEffect.}: result[] = toTable[A, B](pairs) proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] result = newTable[C, B]() {.noSideEffect.}: for item in collection: result[index(item)] = item proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = ## Retrieves the value at `t[key]`. ## ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,TableRef[A,B],A>`_ whether ## the key exists. ## ## See also: ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]=,TableRef[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ for checking if a key is in ## the table runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] result = t[][key] proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: sink B) = ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,TableRef[A,B],A,B>`_ ## * `del proc<#del,TableRef[A,B],A>`_ for removing a key from the table runnableExamples: var a = newTable[char, int]() a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.newTable t[][key] = val proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,TableRef[A,B],A>`_ for use with the `in` ## operator ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false result = t[].hasKey(key) proc contains*[A, B](t: TableRef[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,TableRef[A,B],A>`_ for use with ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert 'b' in a == true doAssert a.contains('z') == false return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: TableRef[A, B], key: A, val: B): bool = ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.newTable if a.hasKeyOrPut('a', 50): a['a'] = 99 if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.newTable t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,TableRef[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 getOrDefault(t[], key) proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = ## Retrieves the value at `t[key]` if `key` is in `t`. ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,TableRef[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## Note that while the value returned is of type `var B`, ## it is easy to accidentally create an copy of the value at `t[key]`. ## Remember that seqs and strings are value types, and therefore ## cannot be copied into a separate variable for modification. ## See the example below. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.newTable doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.newTable # An example of accidentally creating a copy var t = newTable[int, seq[int]]() # In this example, we expect t[10] to be modified, # but it is not. var copiedSeq = t.mgetOrPut(10, @[10]) copiedSeq.add(20) doAssert t[10] == @[10] # Correct t.mgetOrPut(25, @[25]).add(35) doAssert t[25] == @[25, 35] t[].mgetOrPut(key, val) proc len*[A, B](t: TableRef[A, B]): int = ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert len(a) == 2 result = t.counter proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## ## Use `[]= proc<#[]=,TableRef[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. t[].add(key, val) proc del*[A, B](t: TableRef[A, B], key: A) = ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), ## this may need to be called multiple times. ## ## See also: ## * `pop proc<#pop,TableRef[A,B],A,B>`_ ## * `clear proc<#clear,TableRef[A,B]>`_ to empty the whole table runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.newTable a.del('a') doAssert a == {'b': 9, 'c': 13}.newTable a.del('z') doAssert a == {'b': 9, 'c': 13}.newTable t[].del(key) proc pop*[A, B](t: TableRef[A, B], key: A, val: var B): bool = ## Deletes the `key` from the table. ## Returns `true`, if the `key` existed, and sets `val` to the ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), ## this may need to be called multiple times. ## ## See also: ## * `del proc<#del,TableRef[A,B],A>`_ ## * `clear proc<#clear,TableRef[A,B]>`_ to empty the whole table runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.newTable i: int doAssert a.pop('b', i) == true doAssert a == {'a': 5, 'c': 13}.newTable doAssert i == 9 i = 0 doAssert a.pop('z', i) == false doAssert a == {'a': 5, 'c': 13}.newTable doAssert i == 0 result = t[].pop(key, val) proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool {.inline.} = ## Alias for: ## * `pop proc<#pop,TableRef[A,B],A,B>`_ pop(t, key, val) proc clear*[A, B](t: TableRef[A, B]) = ## Resets the table so that it is empty. ## ## See also: ## * `del proc<#del,Table[A,B],A>`_ ## * `pop proc<#pop,Table[A,B],A,B>`_ runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.newTable doAssert len(a) == 3 clear(a) doAssert len(a) == 0 clearImpl() proc `$`*[A, B](t: TableRef[A, B]): string = ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: TableRef[A, B]): bool = ## The `==` operator for hash tables. Returns `true` if either both tables ## are `nil`, or neither is `nil` and the content of both tables contains the ## same key-value pairs. Insert order does not matter. runnableExamples: let a = {'a': 5, 'b': 9, 'c': 13}.newTable b = {'b': 9, 'c': 13, 'a': 5}.newTable doAssert a == b if isNil(s): result = isNil(t) elif isNil(t): result = false else: equalsImpl(s[], t[]) iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ ## * `keys iterator<#keys.i,TableRef[A,B]>`_ ## * `values iterator<#values.i,TableRef[A,B]>`_ ## ## **Examples:** ## ## .. code-block:: ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] ## }.newTable ## ## for k, v in a.pairs: ## echo "key: ", k ## echo "value: ", v ## ## # key: e ## # value: [2, 4, 6, 8] ## # key: o ## # value: [1, 5, 7, 9] let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = ## Iterates over any `(key, value)` pair in the table `t`. The values ## can be modified. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ ## * `mvalues iterator<#mvalues.i,TableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newTable for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.newTable let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator keys*[A, B](t: TableRef[A, B]): lent A = ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ ## * `values iterator<#values.i,TableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newTable for k in a.keys: a[k].add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A, B](t: TableRef[A, B]): lent B = ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ ## * `keys iterator<#keys.i,TableRef[A,B]>`_ ## * `mvalues iterator<#mvalues.i,TableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newTable for v in a.values: doAssert v.len == 4 let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: TableRef[A, B]): var B = ## Iterates over any value in the table `t`. The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ ## * `values iterator<#values.i,TableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newTable for v in a.mvalues: v.add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") # --------------------------------------------------------------------------- # ------------------------------ OrderedTable ------------------------------- # --------------------------------------------------------------------------- type OrderedKeyValuePair[A, B] = tuple[ hcode: Hash, next: int, key: A, val: B] OrderedKeyValuePairSeq[A, B] = seq[OrderedKeyValuePair[A, B]] OrderedTable*[A, B] = object ## Hash table that remembers insertion order. ## ## For creating an empty OrderedTable, use `initOrderedTable proc ## <#initOrderedTable>`_. data: OrderedKeyValuePairSeq[A, B] counter, first, last: int OrderedTableRef*[A, B] = ref OrderedTable[A, B] ## Ref version of ## `OrderedTable<#OrderedTable>`_. ## ## For creating a new empty OrderedTableRef, use `newOrderedTable proc ## <#newOrderedTable>`_. # ------------------------------ helpers --------------------------------- proc rawGetKnownHC[A, B](t: OrderedTable[A, B], key: A, hc: Hash): int = rawGetKnownHCImpl() proc rawGetDeep[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int {.inline.} = rawGetDeepImpl() proc rawGet[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int = rawGetImpl() proc rawInsert[A, B](t: var OrderedTable[A, B], data: var OrderedKeyValuePairSeq[A, B], key: A, val: sink B, hc: Hash, h: Hash) = rawInsertImpl() data[h].next = -1 if t.first < 0: t.first = h if t.last >= 0: data[t.last].next = h t.last = h proc enlarge[A, B](t: var OrderedTable[A, B]) = var n: OrderedKeyValuePairSeq[A, B] newSeq(n, len(t.data) * growthFactor) var h = t.first t.first = -1 t.last = -1 swap(t.data, n) while h >= 0: var nxt = n[h].next let eh = n[h].hcode if isFilled(eh): var j: Hash = eh and maxHash(t) while isFilled(t.data[j].hcode): j = nextTry(j, maxHash(t)) rawInsert(t, t.data, move n[h].key, move n[h].val, n[h].hcode, j) h = nxt template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} = if t.counter > 0: var h = t.first while h >= 0: var nxt = t.data[h].next if isFilled(t.data[h].hcode): yieldStmt h = nxt # ---------------------------------------------------------------------- proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, B] = ## Creates a new ordered hash table that is empty. ## ## Starting from Nim v0.20, tables are initialized by default and it is ## not necessary to call this function explicitly. ## ## See also: ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ ## * `newOrderedTable proc<#newOrderedTable>`_ for creating an ## `OrderedTableRef` runnableExamples: let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() initImpl(result, initialSize) proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,OrderedTable[A,B],A,B>`_ ## * `del proc<#del,OrderedTable[A,B],A>`_ for removing a key from the table runnableExamples: var a = initOrderedTable[char, int]() a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.toOrderedTable putImpl(enlarge) proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = ## Creates a new ordered hash table that contains the given `pairs`. ## ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `initOrderedTable proc<#initOrderedTable>`_ ## * `newOrderedTable proc<#newOrderedTable,openArray[]>`_ for an ## `OrderedTableRef` version runnableExamples: let a = [('a', 5), ('b', 9)] let b = toOrderedTable(a) assert b == {'a': 5, 'b': 9}.toOrderedTable result = initOrderedTable[A, B](pairs.len) for key, val in items(pairs): result[key] = val proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = ## Retrieves the value at `t[key]`. ## ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ whether ## the key exists. ## ## See also: ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]=,OrderedTable[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for checking if a ## key is in the table runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] get(t, key) proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B = ## Retrieves the value at `t[key]`. The value can be modified. ## ## If `key` is not in `t`, the `KeyError` exception is raised. ## ## See also: ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]=,OrderedTable[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for checking if a ## key is in the table get(t, key) proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,OrderedTable[A,B],A>`_ for use with the `in` ## operator ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false var hc: Hash result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for use with ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert 'b' in a == true doAssert a.contains('z') == false return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.toOrderedTable if a.hasKeyOrPut('a', 50): a['a'] = 99 if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.toOrderedTable hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,OrderedTable[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = ## Retrieves the value at `t[key]` if `key` is in `t`. ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,OrderedTable[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.toOrderedTable mgetOrPutImpl(enlarge) proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert len(a) == 2 result = t.counter proc add*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## ## Use `[]= proc<#[]=,OrderedTable[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. addImpl(enlarge) proc del*[A, B](t: var OrderedTable[A, B], key: A) = ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## O(n) complexity. ## ## See also: ## * `pop proc<#pop,OrderedTable[A,B],A,B>`_ ## * `clear proc<#clear,OrderedTable[A,B]>`_ to empty the whole table runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable a.del('a') doAssert a == {'b': 9, 'c': 13}.toOrderedTable a.del('z') doAssert a == {'b': 9, 'c': 13}.toOrderedTable if t.counter == 0: return var n: OrderedKeyValuePairSeq[A, B] newSeq(n, len(t.data)) var h = t.first t.first = -1 t.last = -1 swap(t.data, n) let hc = genHash(key) while h >= 0: var nxt = n[h].next if isFilled(n[h].hcode): if n[h].hcode == hc and n[h].key == key: dec t.counter else: var j = -1 - rawGetKnownHC(t, n[h].key, n[h].hcode) rawInsert(t, t.data, move n[h].key, move n[h].val, n[h].hcode, j) h = nxt proc pop*[A, B](t: var OrderedTable[A, B], key: A, val: var B): bool {.since: (1, 1).} = ## Deletes the `key` from the table. ## Returns `true`, if the `key` existed, and sets `val` to the ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## O(n) complexity. ## ## See also: ## * `del proc<#del,OrderedTable[A,B],A>`_ ## * `clear proc<#clear,OrderedTable[A,B]>`_ to empty the whole table runnableExamples: var a = {'c': 5, 'b': 9, 'a': 13}.toOrderedTable i: int doAssert a.pop('b', i) == true doAssert a == {'c': 5, 'a': 13}.toOrderedTable doAssert i == 9 i = 0 doAssert a.pop('z', i) == false doAssert a == {'c': 5, 'a': 13}.toOrderedTable doAssert i == 0 var hc: Hash var index = rawGet(t, key, hc) result = index >= 0 if result: val = move(t.data[index].val) del(t, key) proc clear*[A, B](t: var OrderedTable[A, B]) = ## Resets the table so that it is empty. ## ## See also: ## * `del proc<#del,OrderedTable[A,B],A>`_ ## * `pop proc<#pop,OrderedTable[A,B],A,B>`_ runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable doAssert len(a) == 3 clear(a) doAssert len(a) == 0 clearImpl() t.first = -1 t.last = -1 proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, order = SortOrder.Ascending) {.effectsOf: cmp.} = ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list ## that kept the insertion order, so insertion order is lost after this ## call but key lookup and insertions remain possible after `sort` (in ## contrast to the `sort proc<#sort,CountTable[A]>`_ for count tables). runnableExamples: import std/[algorithm] var a = initOrderedTable[char, int]() for i, c in "cab": a[c] = 10*i doAssert a == {'c': 0, 'a': 10, 'b': 20}.toOrderedTable a.sort(system.cmp) doAssert a == {'a': 10, 'b': 20, 'c': 0}.toOrderedTable a.sort(system.cmp, order = SortOrder.Descending) doAssert a == {'c': 0, 'b': 20, 'a': 10}.toOrderedTable var list = t.first var p, q, e, tail, oldhead: int nmerges, psize, qsize, i: int if t.counter == 0: return var insize = 1 while true: p = list; oldhead = list list = -1; tail = -1; nmerges = 0 while p >= 0: inc(nmerges) q = p psize = 0 i = 0 while i < insize: inc(psize) q = t.data[q].next if q < 0: break inc(i) qsize = insize while psize > 0 or (qsize > 0 and q >= 0): if psize == 0: e = q; q = t.data[q].next; dec(qsize) elif qsize == 0 or q < 0: e = p; p = t.data[p].next; dec(psize) elif cmp((t.data[p].key, t.data[p].val), (t.data[q].key, t.data[q].val)) * order <= 0: e = p; p = t.data[p].next; dec(psize) else: e = q; q = t.data[q].next; dec(qsize) if tail >= 0: t.data[tail].next = e else: list = e tail = e p = q t.data[tail].next = -1 if nmerges <= 1: break insize = insize * 2 t.first = list t.last = tail proc `$`*[A, B](t: OrderedTable[A, B]): string = ## The `$` operator for ordered hash tables. Used internally when calling ## `echo` on a table. dollarImpl() proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = ## The `==` operator for ordered hash tables. Returns `true` if both the ## content and the order are equal. runnableExamples: let a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable b = {'b': 9, 'c': 13, 'a': 5}.toOrderedTable doAssert a != b if s.counter != t.counter: return false if s.counter == 0 and t.counter == 0: return true var ht = t.first var hs = s.first while ht >= 0 and hs >= 0: var nxtt = t.data[ht].next var nxts = s.data[hs].next if isFilled(t.data[ht].hcode) and isFilled(s.data[hs].hcode): if (s.data[hs].key != t.data[ht].key) or (s.data[hs].val != t.data[ht].val): return false ht = nxtt hs = nxts return true iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. ## ## See also: ## * `mpairs iterator<#mpairs.i,OrderedTable[A,B]>`_ ## * `keys iterator<#keys.i,OrderedTable[A,B]>`_ ## * `values iterator<#values.i,OrderedTable[A,B]>`_ ## ## **Examples:** ## ## .. code-block:: ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] ## }.toOrderedTable ## ## for k, v in a.pairs: ## echo "key: ", k ## echo "value: ", v ## ## # key: o ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] let L = len(t) forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`) in insertion order. The values can be modified. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ ## * `mvalues iterator<#mvalues.i,OrderedTable[A,B]>`_ runnableExamples: var a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toOrderedTable for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'o': @[1, 5, 7, 9, 11], 'e': @[2, 4, 6, 8, 12]}.toOrderedTable let L = len(t) forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator keys*[A, B](t: OrderedTable[A, B]): lent A = ## Iterates over any key in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ ## * `values iterator<#values.i,OrderedTable[A,B]>`_ runnableExamples: var a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toOrderedTable for k in a.keys: a[k].add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.toOrderedTable let L = len(t) forAllOrderedPairs: yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A, B](t: OrderedTable[A, B]): lent B = ## Iterates over any value in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ ## * `keys iterator<#keys.i,OrderedTable[A,B]>`_ ## * `mvalues iterator<#mvalues.i,OrderedTable[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toOrderedTable for v in a.values: doAssert v.len == 4 let L = len(t) forAllOrderedPairs: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = ## Iterates over any value in the table `t` (must be ## declared as `var`) in insertion order. The values ## can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,OrderedTable[A,B]>`_ ## * `values iterator<#values.i,OrderedTable[A,B]>`_ runnableExamples: var a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.toOrderedTable for v in a.mvalues: v.add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.toOrderedTable let L = len(t) forAllOrderedPairs: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") # --------------------------------------------------------------------------- # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- proc newOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## See also: ## * `newOrderedTable proc<#newOrderedTable,openArray[]>`_ for creating ## an `OrderedTableRef` from a collection of `(key, value)` pairs ## * `initOrderedTable proc<#initOrderedTable>`_ for creating an ## `OrderedTable` runnableExamples: let a = newOrderedTable[int, string]() b = newOrderedTable[char, seq[int]]() new(result) {.noSideEffect.}: result[] = initOrderedTable[A, B](initialSize) proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that contains the given `pairs`. ## ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `newOrderedTable proc<#newOrderedTable>`_ ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ for an ## `OrderedTable` version runnableExamples: let a = [('a', 5), ('b', 9)] let b = newOrderedTable(a) assert b == {'a': 5, 'b': 9}.newOrderedTable result = newOrderedTable[A, B](pairs.len) {.noSideEffect.}: for key, val in items(pairs): result[key] = val proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = ## Retrieves the value at `t[key]`. ## ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ whether ## the key exists. ## ## See also: ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]=,OrderedTableRef[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ for checking if ## a key is in the table runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] result = t[][key] proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) = ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,OrderedTableRef[A,B],A,B>`_ ## * `del proc<#del,OrderedTableRef[A,B],A>`_ for removing a key from the table runnableExamples: var a = newOrderedTable[char, int]() a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.newOrderedTable t[][key] = val proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,OrderedTableRef[A,B],A>`_ for use with the `in` ## operator ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false result = t[].hasKey(key) proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ for use with ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert 'b' in a == true doAssert a.contains('z') == false return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): bool = ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.newOrderedTable if a.hasKeyOrPut('a', 50): a['a'] = 99 if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.newOrderedTable result = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,OrderedTableRef[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 getOrDefault(t[], key) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = ## Retrieves the value at `t[key]` if `key` is in `t`. ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ ## * `mgetOrPut proc<#mgetOrPut,OrderedTableRef[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return ## a custom value if the key doesn't exist runnableExamples: var a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.newOrderedTable result = t[].mgetOrPut(key, val) proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert len(a) == 2 result = t.counter proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## ## Use `[]= proc<#[]=,OrderedTableRef[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. t[].add(key, val) proc del*[A, B](t: OrderedTableRef[A, B], key: A) = ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## See also: ## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable a.del('a') doAssert a == {'b': 9, 'c': 13}.newOrderedTable a.del('z') doAssert a == {'b': 9, 'c': 13}.newOrderedTable t[].del(key) proc pop*[A, B](t: OrderedTableRef[A, B], key: A, val: var B): bool {.since: (1, 1).} = ## Deletes the `key` from the table. ## Returns `true`, if the `key` existed, and sets `val` to the ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: ## * `del proc<#del,OrderedTableRef[A,B],A>`_ ## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table runnableExamples: var a = {'c': 5, 'b': 9, 'a': 13}.newOrderedTable i: int doAssert a.pop('b', i) == true doAssert a == {'c': 5, 'a': 13}.newOrderedTable doAssert i == 9 i = 0 doAssert a.pop('z', i) == false doAssert a == {'c': 5, 'a': 13}.newOrderedTable doAssert i == 0 pop(t[], key, val) proc clear*[A, B](t: OrderedTableRef[A, B]) = ## Resets the table so that it is empty. ## ## See also: ## * `del proc<#del,OrderedTableRef[A,B],A>`_ runnableExamples: var a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable doAssert len(a) == 3 clear(a) doAssert len(a) == 0 clear(t[]) proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, order = SortOrder.Ascending) {.effectsOf: cmp.} = ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list ## that kept the insertion order, so insertion order is lost after this ## call but key lookup and insertions remain possible after `sort` (in ## contrast to the `sort proc<#sort,CountTableRef[A]>`_ for count tables). runnableExamples: import std/[algorithm] var a = newOrderedTable[char, int]() for i, c in "cab": a[c] = 10*i doAssert a == {'c': 0, 'a': 10, 'b': 20}.newOrderedTable a.sort(system.cmp) doAssert a == {'a': 10, 'b': 20, 'c': 0}.newOrderedTable a.sort(system.cmp, order = SortOrder.Descending) doAssert a == {'c': 0, 'b': 20, 'a': 10}.newOrderedTable t[].sort(cmp, order = order) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = ## The `==` operator for ordered hash tables. Returns true if either both ## tables are `nil`, or neither is `nil` and the content and the order of ## both are equal. runnableExamples: let a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable b = {'b': 9, 'c': 13, 'a': 5}.newOrderedTable doAssert a != b if isNil(s): result = isNil(t) elif isNil(t): result = false else: result = s[] == t[] iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. ## ## See also: ## * `mpairs iterator<#mpairs.i,OrderedTableRef[A,B]>`_ ## * `keys iterator<#keys.i,OrderedTableRef[A,B]>`_ ## * `values iterator<#values.i,OrderedTableRef[A,B]>`_ ## ## **Examples:** ## ## .. code-block:: ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] ## }.newOrderedTable ## ## for k, v in a.pairs: ## echo "key: ", k ## echo "value: ", v ## ## # key: o ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] let L = len(t) forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. The values can be modified. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ ## * `mvalues iterator<#mvalues.i,OrderedTableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newOrderedTable for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'o': @[1, 5, 7, 9, 11], 'e': @[2, 4, 6, 8, 12]}.newOrderedTable let L = len(t) forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator keys*[A, B](t: OrderedTableRef[A, B]): lent A = ## Iterates over any key in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ ## * `values iterator<#values.i,OrderedTableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newOrderedTable for k in a.keys: a[k].add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.newOrderedTable let L = len(t) forAllOrderedPairs: yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A, B](t: OrderedTableRef[A, B]): lent B = ## Iterates over any value in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ ## * `keys iterator<#keys.i,OrderedTableRef[A,B]>`_ ## * `mvalues iterator<#mvalues.i,OrderedTableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newOrderedTable for v in a.values: doAssert v.len == 4 let L = len(t) forAllOrderedPairs: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = ## Iterates over any value in the table `t` in insertion order. The values ## can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,OrderedTableRef[A,B]>`_ ## * `values iterator<#values.i,OrderedTableRef[A,B]>`_ runnableExamples: let a = { 'o': @[1, 5, 7, 9], 'e': @[2, 4, 6, 8] }.newOrderedTable for v in a.mvalues: v.add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.newOrderedTable let L = len(t) forAllOrderedPairs: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") # ------------------------------------------------------------------------- # ------------------------------ CountTable ------------------------------- # ------------------------------------------------------------------------- type CountTable*[A] = object ## Hash table that counts the number of each key. ## ## For creating an empty CountTable, use `initCountTable proc ## <#initCountTable>`_. data: seq[tuple[key: A, val: int]] counter: int isSorted: bool CountTableRef*[A] = ref CountTable[A] ## Ref version of ## `CountTable<#CountTable>`_. ## ## For creating a new empty CountTableRef, use `newCountTable proc ## <#newCountTable>`_. # ------------------------------ helpers --------------------------------- proc ctRawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], key: A, val: int) = var h: Hash = hash(key) and high(data) while data[h].val != 0: h = nextTry(h, high(data)) data[h].key = key data[h].val = val proc enlarge[A](t: var CountTable[A]) = var n: seq[tuple[key: A, val: int]] newSeq(n, len(t.data) * growthFactor) for i in countup(0, high(t.data)): if t.data[i].val != 0: ctRawInsert(t, n, move t.data[i].key, move t.data[i].val) swap(t.data, n) proc rawGet[A](t: CountTable[A], key: A): int = if t.data.len == 0: return -1 var h: Hash = hash(key) and high(t.data) # start with real hash value while t.data[h].val != 0: if t.data[h].key == key: return h h = nextTry(h, high(t.data)) result = -1 - h # < 0 => MISSING; insert idx = -1 - result template ctget(t, key, default: untyped): untyped = var index = rawGet(t, key) result = if index >= 0: t.data[index].val else: default proc inc*[A](t: var CountTable[A], key: A, val = 1) # ---------------------------------------------------------------------- proc initCountTable*[A](initialSize = defaultInitialSize): CountTable[A] = ## Creates a new count table that is empty. ## ## Starting from Nim v0.20, tables are initialized by default and it is ## not necessary to call this function explicitly. ## ## See also: ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable>`_ for creating a ## `CountTableRef` initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = ## Creates a new count table with every member of a container `keys` ## having a count of how many times it occurs in that container. result = initCountTable[A](keys.len) for key in items(keys): result.inc(key) proc `[]`*[A](t: CountTable[A], key: A): int = ## Retrieves the value at `t[key]` if `key` is in `t`. ## Otherwise `0` is returned. ## ## See also: ## * `getOrDefault<#getOrDefault,CountTable[A],A,int>`_ to return ## a custom value if the key doesn't exist ## * `[]= proc<#[]%3D,CountTable[A],A,int>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,CountTable[A],A>`_ for checking if a key ## is in the table assert(not t.isSorted, "CountTable must not be used after sorting") ctget(t, key, 0) template cntMakeEmpty(i) = t.data[i].val = 0 template cntCellEmpty(i) = t.data[i].val == 0 template cntCellHash(i) = hash(t.data[i].key) proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key ## * `inc proc<#inc,CountTable[A],A,int>`_ for incrementing a ## value of a key assert(not t.isSorted, "CountTable must not be used after sorting") assert val >= 0 if val == 0: delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) else: let h = rawGet(t, key) if h >= 0: t.data[h].val = val else: insertImpl() proc inc*[A](t: var CountTable[A], key: A, val = 1) = ## Increments `t[key]` by `val` (default: 1). runnableExamples: var a = toCountTable("aab") a.inc('a') a.inc('b', 10) doAssert a == toCountTable("aaabbbbbbbbbbb") assert(not t.isSorted, "CountTable must not be used after sorting") var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) if t.data[index].val == 0: delImplIdx(t, index, cntMakeEmpty, cntCellEmpty, cntCellHash) else: if val != 0: insertImpl() proc len*[A](t: CountTable[A]): int = ## Returns the number of keys in `t`. result = t.counter proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) ## ## See also: ## * `largest proc<#largest,CountTable[A]>`_ assert t.len > 0, "counttable is empty" var minIdx = -1 for h in 0 .. high(t.data): if t.data[h].val > 0 and (minIdx == -1 or t.data[minIdx].val > t.data[h].val): minIdx = h result.key = t.data[minIdx].key result.val = t.data[minIdx].val proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) ## ## See also: ## * `smallest proc<#smallest,CountTable[A]>`_ assert t.len > 0, "counttable is empty" var maxIdx = 0 for h in 1 .. high(t.data): if t.data[maxIdx].val < t.data[h].val: maxIdx = h result.key = t.data[maxIdx].key result.val = t.data[maxIdx].val proc hasKey*[A](t: CountTable[A], key: A): bool = ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,CountTable[A],A>`_ for use with the `in` ## operator ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,CountTable[A],A,int>`_ to return ## a custom value if the key doesn't exist assert(not t.isSorted, "CountTable must not be used after sorting") result = rawGet(t, key) >= 0 proc contains*[A](t: CountTable[A], key: A): bool = ## Alias of `hasKey proc<#hasKey,CountTable[A],A>`_ for use with ## the `in` operator. return hasKey[A](t, key) proc getOrDefault*[A](t: CountTable[A], key: A; default: int = 0): int = ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## integer value of `default` is returned. ## ## See also: ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,CountTable[A],A>`_ for checking if a key ## is in the table ctget(t, key, default) proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = ## Deletes `key` from table `t`. Does nothing if the key does not exist. ## ## See also: ## * `pop proc<#pop,CountTable[A],A,int>`_ ## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table runnableExamples: var a = toCountTable("aabbbccccc") a.del('b') assert a == toCountTable("aaccccc") a.del('b') assert a == toCountTable("aaccccc") a.del('c') assert a == toCountTable("aa") delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} = ## Deletes the `key` from the table. ## Returns `true`, if the `key` existed, and sets `val` to the ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: ## * `del proc<#del,CountTable[A],A>`_ ## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table runnableExamples: var a = toCountTable("aabbbccccc") var i = 0 assert a.pop('b', i) assert i == 3 i = 99 assert not a.pop('b', i) assert i == 99 var index = rawGet(t, key) result = index >= 0 if result: val = move(t.data[index].val) delImplIdx(t, index, cntMakeEmpty, cntCellEmpty, cntCellHash) proc clear*[A](t: var CountTable[A]) = ## Resets the table so that it is empty. ## ## See also: ## * `del proc<#del,CountTable[A],A>`_ ## * `pop proc<#pop,CountTable[A],A,int>`_ clearImpl() t.isSorted = false func ctCmp[T](a, b: tuple[key: T, val: int]): int = result = system.cmp(a.val, b.val) proc sort*[A](t: var CountTable[A], order = SortOrder.Descending) = ## Sorts the count table so that, by default, the entry with the ## highest counter comes first. ## ## .. warning:: This is destructive! Once sorted, you must not modify `t` afterwards! ## ## You can use the iterators `pairs<#pairs.i,CountTable[A]>`_, ## `keys<#keys.i,CountTable[A]>`_, and `values<#values.i,CountTable[A]>`_ ## to iterate over `t` in the sorted order. runnableExamples: import std/[algorithm, sequtils] var a = toCountTable("abracadabra") doAssert a == "aaaaabbrrcd".toCountTable a.sort() doAssert toSeq(a.values) == @[5, 2, 2, 1, 1] a.sort(SortOrder.Ascending) doAssert toSeq(a.values) == @[1, 1, 2, 2, 5] t.data.sort(cmp = ctCmp, order = order) t.isSorted = true proc merge*[A](s: var CountTable[A], t: CountTable[A]) = ## Merges the second table into the first one (must be declared as `var`). runnableExamples: var a = toCountTable("aaabbc") let b = toCountTable("bcc") a.merge(b) doAssert a == toCountTable("aaabbbccc") assert(not s.isSorted, "CountTable must not be used after sorting") for key, value in t: s.inc(key, value) when (NimMajor, NimMinor) <= (1, 0): proc merge*[A](s, t: CountTable[A]): CountTable[A] = ## Merges the two tables into a new one. runnableExamples: let a = toCountTable("aaabbc") b = toCountTable("bcc") doAssert merge(a, b) == toCountTable("aaabbbccc") result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) for table in @[s, t]: for key, value in table: result.inc(key, value) proc `$`*[A](t: CountTable[A]): string = ## The `$` operator for count tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A](s, t: CountTable[A]): bool = ## The `==` operator for count tables. Returns `true` if both tables ## contain the same keys with the same count. Insert order does not matter. equalsImpl(s, t) iterator pairs*[A](t: CountTable[A]): (A, int) = ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ ## * `keys iterator<#keys.i,CountTable[A]>`_ ## * `values iterator<#values.i,CountTable[A]>`_ ## ## **Examples:** ## ## .. code-block:: ## let a = toCountTable("abracadabra") ## ## for k, v in pairs(a): ## echo "key: ", k ## echo "value: ", v ## ## # key: a ## # value: 5 ## # key: b ## # value: 2 ## # key: c ## # value: 1 ## # key: d ## # value: 1 ## # key: r ## # value: 2 let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A](t: var CountTable[A]): (A, var int) = ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ ## * `mvalues iterator<#mvalues.i,CountTable[A]>`_ runnableExamples: var a = toCountTable("abracadabra") for k, v in mpairs(a): v = 2 doAssert a == toCountTable("aabbccddrr") let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator keys*[A](t: CountTable[A]): lent A = ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ ## * `values iterator<#values.i,CountTable[A]>`_ runnableExamples: var a = toCountTable("abracadabra") for k in keys(a): a[k] = 2 doAssert a == toCountTable("aabbccddrr") let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A](t: CountTable[A]): int = ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ ## * `keys iterator<#keys.i,CountTable[A]>`_ ## * `mvalues iterator<#mvalues.i,CountTable[A]>`_ runnableExamples: let a = toCountTable("abracadabra") for v in values(a): assert v < 10 let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A](t: var CountTable[A]): var int = ## Iterates over any value in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ ## * `values iterator<#values.i,CountTable[A]>`_ runnableExamples: var a = toCountTable("abracadabra") for v in mvalues(a): v = 2 doAssert a == toCountTable("aabbccddrr") let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") # --------------------------------------------------------------------------- # ---------------------------- CountTableRef -------------------------------- # --------------------------------------------------------------------------- proc inc*[A](t: CountTableRef[A], key: A, val = 1) proc newCountTable*[A](initialSize = defaultInitialSize): CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## See also: ## * `newCountTable proc<#newCountTable,openArray[A]>`_ for creating ## a `CountTableRef` from a collection ## * `initCountTable proc<#initCountTable>`_ for creating a ## `CountTable` new(result) {.noSideEffect.}: result[] = initCountTable[A](initialSize) proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = ## Creates a new ref count table with every member of a container `keys` ## having a count of how many times it occurs in that container. result = newCountTable[A](keys.len) {.noSideEffect.}: for key in items(keys): result.inc(key) proc `[]`*[A](t: CountTableRef[A], key: A): int = ## Retrieves the value at `t[key]` if `key` is in `t`. ## Otherwise `0` is returned. ## ## See also: ## * `getOrDefault<#getOrDefault,CountTableRef[A],A,int>`_ to return ## a custom value if the key doesn't exist ## * `inc proc<#inc,CountTableRef[A],A,int>`_ to inc even if missing ## * `[]= proc<#[]%3D,CountTableRef[A],A,int>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,CountTableRef[A],A>`_ for checking if a key ## is in the table result = t[][key] proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key ## * `inc proc<#inc,CountTableRef[A],A,int>`_ for incrementing a ## value of a key assert val > 0 {.noSideEffect.}: t[][key] = val proc inc*[A](t: CountTableRef[A], key: A, val = 1) = ## Increments `t[key]` by `val` (default: 1). runnableExamples: var a = newCountTable("aab") a.inc('a') a.inc('b', 10) doAssert a == newCountTable("aaabbbbbbbbbbb") {.noSideEffect.}: t[].inc(key, val) proc smallest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) ## ## See also: ## * `largest proc<#largest,CountTableRef[A]>`_ t[].smallest proc largest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) ## ## See also: ## * `smallest proc<#smallest,CountTable[A]>`_ t[].largest proc hasKey*[A](t: CountTableRef[A], key: A): bool = ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,CountTableRef[A],A>`_ for use with the `in` ## operator ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key ## * `getOrDefault proc<#getOrDefault,CountTableRef[A],A,int>`_ to return ## a custom value if the key doesn't exist result = t[].hasKey(key) proc contains*[A](t: CountTableRef[A], key: A): bool = ## Alias of `hasKey proc<#hasKey,CountTableRef[A],A>`_ for use with ## the `in` operator. return hasKey[A](t, key) proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## integer value of `default` is returned. ## ## See also: ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key ## * `hasKey proc<#hasKey,CountTableRef[A],A>`_ for checking if a key ## is in the table result = t[].getOrDefault(key, default) proc len*[A](t: CountTableRef[A]): int = ## Returns the number of keys in `t`. result = t.counter proc del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} = ## Deletes `key` from table `t`. Does nothing if the key does not exist. ## ## See also: ## * `pop proc<#pop,CountTableRef[A],A,int>`_ ## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table del(t[], key) proc pop*[A](t: CountTableRef[A], key: A, val: var int): bool {.since: (1, 1).} = ## Deletes the `key` from the table. ## Returns `true`, if the `key` existed, and sets `val` to the ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: ## * `del proc<#del,CountTableRef[A],A>`_ ## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table pop(t[], key, val) proc clear*[A](t: CountTableRef[A]) = ## Resets the table so that it is empty. ## ## See also: ## * `del proc<#del,CountTableRef[A],A>`_ ## * `pop proc<#pop,CountTableRef[A],A,int>`_ clear(t[]) proc sort*[A](t: CountTableRef[A], order = SortOrder.Descending) = ## Sorts the count table so that, by default, the entry with the ## highest counter comes first. ## ## **This is destructive! You must not modify `t` afterwards!** ## ## You can use the iterators `pairs<#pairs.i,CountTableRef[A]>`_, ## `keys<#keys.i,CountTableRef[A]>`_, and `values<#values.i,CountTableRef[A]>`_ ## to iterate over `t` in the sorted order. t[].sort(order = order) proc merge*[A](s, t: CountTableRef[A]) = ## Merges the second table into the first one. runnableExamples: let a = newCountTable("aaabbc") b = newCountTable("bcc") a.merge(b) doAssert a == newCountTable("aaabbbccc") s[].merge(t[]) proc `$`*[A](t: CountTableRef[A]): string = ## The `$` operator for count tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A](s, t: CountTableRef[A]): bool = ## The `==` operator for count tables. Returns `true` if either both tables ## are `nil`, or neither is `nil` and both contain the same keys with the same ## count. Insert order does not matter. if isNil(s): result = isNil(t) elif isNil(t): result = false else: result = s[] == t[] iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ ## * `keys iterator<#keys.i,CountTableRef[A]>`_ ## * `values iterator<#values.i,CountTableRef[A]>`_ ## ## **Examples:** ## ## .. code-block:: ## let a = newCountTable("abracadabra") ## ## for k, v in pairs(a): ## echo "key: ", k ## echo "value: ", v ## ## # key: a ## # value: 5 ## # key: b ## # value: 2 ## # key: c ## # value: 1 ## # key: d ## # value: 1 ## # key: r ## # value: 2 let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = ## Iterates over any `(key, value)` pair in the table `t`. The values can ## be modified. ## ## See also: ## * `pairs iterator<#pairs.i,CountTableRef[A]>`_ ## * `mvalues iterator<#mvalues.i,CountTableRef[A]>`_ runnableExamples: let a = newCountTable("abracadabra") for k, v in mpairs(a): v = 2 doAssert a == newCountTable("aabbccddrr") let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "table modified while iterating over it") iterator keys*[A](t: CountTableRef[A]): A = ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ ## * `values iterator<#values.i,CountTable[A]>`_ runnableExamples: let a = newCountTable("abracadabra") for k in keys(a): a[k] = 2 doAssert a == newCountTable("aabbccddrr") let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A](t: CountTableRef[A]): int = ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTableRef[A]>`_ ## * `keys iterator<#keys.i,CountTableRef[A]>`_ ## * `mvalues iterator<#mvalues.i,CountTableRef[A]>`_ runnableExamples: let a = newCountTable("abracadabra") for v in values(a): assert v < 10 let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A](t: CountTableRef[A]): var int = ## Iterates over any value in the table `t`. The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ ## * `values iterator<#values.i,CountTableRef[A]>`_ runnableExamples: var a = newCountTable("abracadabra") for v in mvalues(a): v = 2 doAssert a == newCountTable("aabbccddrr") let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it")