diff options
Diffstat (limited to 'lib/pure/collections/tables.nim')
| -rw-r--r-- | lib/pure/collections/tables.nim | 246 |
1 files changed, 172 insertions, 74 deletions
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index f77642349..d414caeed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -136,12 +136,11 @@ runnableExamples: ## a more complex object as a key you will be greeted by a strange compiler ## error: ## -## 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 -## … +## 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 <hashes.html#Hash>`_ @@ -189,7 +188,6 @@ runnableExamples: ## ## * `json module<json.html>`_ for table-like structure which allows ## heterogeneous members -## * `sharedtables module<sharedtables.html>`_ for shared hash table support ## * `strtabs module<strtabs.html>`_ for efficient hash tables ## mapping from strings to strings ## * `hashes module<hashes.html>`_ for helper functions for hashing @@ -198,6 +196,10 @@ runnableExamples: import std/private/since import std/[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]] @@ -215,8 +217,6 @@ type ## For creating a new empty TableRef, use `newTable proc ## <#newTable>`_. -const - defaultInitialSize* = 32 # ------------------------------ helpers --------------------------------- @@ -227,6 +227,12 @@ 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. @@ -235,10 +241,7 @@ template get(t, key): untyped = var index = rawGet(t, key, hc) if index >= 0: result = t.data[index].val else: - when compiles($key): - raise newException(KeyError, "key not found: " & $key) - else: - raise newException(KeyError, "key not found") + raiseKeyError(key) proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] @@ -275,6 +278,7 @@ proc initTable*[A, B](initialSize = defaultInitialSize): Table[A, B] = let a = initTable[int, string]() b = initTable[char, seq[int]]() + result = default(Table[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = @@ -309,7 +313,7 @@ proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = 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 = +proc `[]`*[A, B](t: Table[A, B], key: A): lent B = ## Retrieves the value at `t[key]`. ## ## If `key` is not in `t`, the `KeyError` exception is raised. @@ -321,7 +325,7 @@ proc `[]`*[A, B](t: Table[A, B], key: A): B = ## 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,B>`_ for inserting a new + ## * `[]= 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 @@ -342,7 +346,7 @@ proc `[]`*[A, B](t: var Table[A, B], key: A): var B = ## 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,B>`_ for inserting a new + ## * `[]= 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 @@ -412,7 +416,7 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 - + result = default(B) getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = @@ -430,7 +434,7 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 - + result = default(B) getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = @@ -439,7 +443,7 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = ## ## ## 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]`. + ## 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. @@ -471,6 +475,18 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) +proc mgetOrPut*[A, B](t: var Table[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.newTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.newTable + + mgetOrPutImpl(enlarge) + proc len*[A, B](t: Table[A, B]): int = ## Returns the number of keys in `t`. runnableExamples: @@ -485,7 +501,7 @@ proc add*[A, B](t: var Table[A, B], key: A, val: sink B) {.deprecated: ## ## **This can introduce duplicate keys into the table!** ## - ## Use `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## Use `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. addImpl(enlarge) @@ -496,6 +512,9 @@ 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 @@ -514,6 +533,9 @@ proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = ## 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 @@ -594,17 +616,17 @@ template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = let u = User(name: "Hello", uid: 99) t[1] = u - t.withValue(1, value) do: + t.withValue(1, value): # block is executed only if `key` in `t` value.name = "Nim" value.uid = 1314 - t.withValue(2, value) do: + t.withValue(2, value): value.name = "No" value.uid = 521 - doAssert t[1].name == "Nim" - doAssert t[1].uid == 1314 + assert t[1].name == "Nim" + assert t[1].uid == 1314 mixin rawGet var hc: Hash @@ -629,16 +651,22 @@ template withValue*[A, B](t: var Table[A, B], key: A, let u = User(name: "Hello", uid: 99) t[1] = u - t.withValue(1, value) do: + t.withValue(1, value): # block is executed only if `key` in `t` value.name = "Nim" value.uid = 1314 - # do: - # # block is executed when `key` not in `t` - # raise newException(KeyError, "Key not found") - doAssert t[1].name == "Nim" - doAssert t[1].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) @@ -660,7 +688,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -674,6 +702,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## # 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): @@ -702,7 +731,7 @@ iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = 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]): A = +iterator keys*[A, B](t: Table[A, B]): lent A = ## Iterates over any key in the table `t`. ## ## See also: @@ -723,7 +752,7 @@ iterator keys*[A, B](t: Table[A, B]): A = 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]): B = +iterator values*[A, B](t: Table[A, B]): lent B = ## Iterates over any value in the table `t`. ## ## See also: @@ -795,7 +824,7 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B {.deprecated: # ------------------------------------------------------------------- -proc newTable*[A, B](initialSize = defaultInitialSize): <//>TableRef[A, B] = +proc newTable*[A, B](initialSize = defaultInitialSize): TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## See also: @@ -808,9 +837,10 @@ proc newTable*[A, B](initialSize = defaultInitialSize): <//>TableRef[A, B] = b = newTable[char, seq[int]]() new(result) - result[] = initTable[A, B](initialSize) + {.noSideEffect.}: + result[] = initTable[A, B](initialSize) -proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = +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. @@ -824,14 +854,16 @@ proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = assert b == {'a': 5, 'b': 9}.newTable new(result) - result[] = toTable[A, B](pairs) + {.noSideEffect.}: + result[] = toTable[A, B](pairs) -proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): <//>TableRef[C, B] = +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]() - for item in collection: - result[index(item)] = item + {.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]`. @@ -901,7 +933,7 @@ proc contains*[A, B](t: TableRef[A, B], key: A): bool = return hasKey[A, B](t, key) -proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = +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: @@ -994,6 +1026,18 @@ proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = doAssert t[25] == @[25, 35] t[].mgetOrPut(key, val) +proc mgetOrPut*[A, B](t: TableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.newTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.newTable + + t[].mgetOrPut(key) + proc len*[A, B](t: TableRef[A, B]): int = ## Returns the number of keys in `t`. runnableExamples: @@ -1015,7 +1059,8 @@ proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: proc del*[A, B](t: TableRef[A, B], key: A) = ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## - ## **If duplicate keys were added, this may need to be called multiple times.** + ## .. 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>`_ @@ -1035,7 +1080,8 @@ proc pop*[A, B](t: TableRef[A, B], key: A, val: var B): bool = ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## - ## **If duplicate keys were added, this may need to be called multiple times.** + ## .. 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>`_ @@ -1104,7 +1150,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -1118,6 +1164,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## # 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): @@ -1146,7 +1193,7 @@ iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = 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]): A = +iterator keys*[A, B](t: TableRef[A, B]): lent A = ## Iterates over any key in the table `t`. ## ## See also: @@ -1167,7 +1214,7 @@ iterator keys*[A, B](t: TableRef[A, B]): A = 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]): B = +iterator values*[A, B](t: TableRef[A, B]): lent B = ## Iterates over any value in the table `t`. ## ## See also: @@ -1300,6 +1347,7 @@ proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() + result = default(OrderedTable[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = @@ -1335,7 +1383,7 @@ proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = 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 = +proc `[]`*[A, B](t: OrderedTable[A, B], key: A): lent B = ## Retrieves the value at `t[key]`. ## ## If `key` is not in `t`, the `KeyError` exception is raised. @@ -1391,7 +1439,7 @@ proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false - var hc: Hash + var hc: Hash = default(Hash) result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = @@ -1440,7 +1488,7 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 - + result = default(B) getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = @@ -1458,7 +1506,7 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 - + result = default(B) getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = @@ -1481,6 +1529,18 @@ proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) +proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.toOrderedTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.toOrderedTable + + mgetOrPutImpl(enlarge) + proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = ## Returns the number of keys in `t`. runnableExamples: @@ -1579,7 +1639,7 @@ proc clear*[A, B](t: var OrderedTable[A, B]) = t.last = -1 proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, - order = SortOrder.Ascending) = + order = SortOrder.Ascending) {.effectsOf: cmp.} = ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list @@ -1680,7 +1740,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -1694,6 +1754,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] + ## ``` let L = len(t) forAllOrderedPairs: @@ -1722,7 +1783,7 @@ iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = 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]): A = +iterator keys*[A, B](t: OrderedTable[A, B]): lent A = ## Iterates over any key in the table `t` in insertion order. ## ## See also: @@ -1743,7 +1804,7 @@ iterator keys*[A, B](t: OrderedTable[A, B]): A = 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]): B = +iterator values*[A, B](t: OrderedTable[A, B]): lent B = ## Iterates over any value in the table `t` in insertion order. ## ## See also: @@ -1790,7 +1851,7 @@ iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- -proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## See also: @@ -1803,9 +1864,10 @@ proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableR a = newOrderedTable[int, string]() b = newOrderedTable[char, seq[int]]() new(result) - result[] = initOrderedTable[A, B](initialSize) + {.noSideEffect.}: + result[] = initOrderedTable[A, B](initialSize) -proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] = +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. @@ -1820,7 +1882,8 @@ proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] assert b == {'a': 5, 'b': 9}.newOrderedTable result = newOrderedTable[A, B](pairs.len) - for key, val in items(pairs): result[key] = val + {.noSideEffect.}: + for key, val in items(pairs): result[key] = val proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = @@ -1890,7 +1953,7 @@ proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = return hasKey[A, B](t, key) -proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = +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: @@ -1967,6 +2030,18 @@ proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = result = t[].mgetOrPut(key, val) +proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.toOrderedTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.toOrderedTable + + t[].mgetOrPut(key) + proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = ## Returns the number of keys in `t`. runnableExamples: @@ -2036,7 +2111,7 @@ proc clear*[A, B](t: OrderedTableRef[A, B]) = clear(t[]) proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, - order = SortOrder.Ascending) = + order = SortOrder.Ascending) {.effectsOf: cmp.} = ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list @@ -2088,7 +2163,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -2102,6 +2177,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] + ## ``` let L = len(t) forAllOrderedPairs: @@ -2130,7 +2206,7 @@ iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = 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]): A = +iterator keys*[A, B](t: OrderedTableRef[A, B]): lent A = ## Iterates over any key in the table `t` in insertion order. ## ## See also: @@ -2151,7 +2227,7 @@ iterator keys*[A, B](t: OrderedTableRef[A, B]): A = 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]): B = +iterator values*[A, B](t: OrderedTableRef[A, B]): lent B = ## Iterates over any value in the table `t` in insertion order. ## ## See also: @@ -2262,6 +2338,7 @@ proc initCountTable*[A](initialSize = defaultInitialSize): CountTable[A] = ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable>`_ for creating a ## `CountTableRef` + result = default(CountTable[A]) initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = @@ -2371,7 +2448,7 @@ proc contains*[A](t: CountTable[A], key: A): bool = 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 + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## integer value of `default` is returned. ## ## See also: @@ -2501,7 +2578,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = toCountTable("abracadabra") ## ## for k, v in pairs(a): @@ -2518,6 +2595,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = ## # value: 1 ## # key: r ## # value: 2 + ## ``` let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: @@ -2543,7 +2621,7 @@ iterator mpairs*[A](t: var CountTable[A]): (A, var int) = 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]): A = +iterator keys*[A](t: CountTable[A]): lent A = ## Iterates over any key in the table `t`. ## ## See also: @@ -2610,7 +2688,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = proc inc*[A](t: CountTableRef[A], key: A, val = 1) -proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] = +proc newCountTable*[A](initialSize = defaultInitialSize): CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## See also: @@ -2619,13 +2697,15 @@ proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] = ## * `initCountTable proc<#initCountTable>`_ for creating a ## `CountTable` new(result) - result[] = initCountTable[A](initialSize) + {.noSideEffect.}: + result[] = initCountTable[A](initialSize) -proc newCountTable*[A](keys: openArray[A]): <//>CountTableRef[A] = +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) - for key in items(keys): result.inc(key) + {.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`. @@ -2649,7 +2729,8 @@ proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = ## * `inc proc<#inc,CountTableRef[A],A,int>`_ for incrementing a ## value of a key assert val > 0 - t[][key] = val + {.noSideEffect.}: + t[][key] = val proc inc*[A](t: CountTableRef[A], key: A, val = 1) = ## Increments `t[key]` by `val` (default: 1). @@ -2658,7 +2739,8 @@ proc inc*[A](t: CountTableRef[A], key: A, val = 1) = a.inc('a') a.inc('b', 10) doAssert a == newCountTable("aaabbbbbbbbbbb") - t[].inc(key, val) + {.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) @@ -2691,7 +2773,7 @@ proc contains*[A](t: CountTableRef[A], key: A): bool = 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 + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## integer value of `default` is returned. ## ## See also: @@ -2777,7 +2859,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = newCountTable("abracadabra") ## ## for k, v in pairs(a): @@ -2794,6 +2876,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## # value: 1 ## # key: r ## # value: 2 + ## ``` let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: @@ -2872,3 +2955,18 @@ iterator mvalues*[A](t: CountTableRef[A]): var int = 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") + +proc hash*[K,V](s: Table[K,V]): Hash = + for p in pairs(s): + result = result xor hash(p) + result = !$result + +proc hash*[K,V](s: OrderedTable[K,V]): Hash = + for p in pairs(s): + result = result !& hash(p) + result = !$result + +proc hash*[V](s: CountTable[V]): Hash = + for p in pairs(s): + result = result xor hash(p) + result = !$result |