1# 2# 3# Nim's Runtime Library 4# (c) Copyright 2012 Andreas Rumpf 5# 6# See the file "copying.txt", included in this 7# distribution, for details about the copyright. 8# 9 10## The `sets` module implements an efficient `hash set`:idx: and 11## ordered hash set. 12## 13## Hash sets are different from the `built in set type 14## <manual.html#types-set-type>`_. Sets allow you to store any value that can be 15## `hashed <hashes.html>`_ and they don't contain duplicate entries. 16## 17## Common usages of sets: 18## * removing duplicates from a container by converting it with `toHashSet proc 19## <#toHashSet,openArray[A]>`_ (see also `sequtils.deduplicate func 20## <sequtils.html#deduplicate,openArray[T],bool>`_) 21## * membership testing 22## * mathematical operations on two sets, such as 23## `union <#union,HashSet[A],HashSet[A]>`_, 24## `intersection <#intersection,HashSet[A],HashSet[A]>`_, 25## `difference <#difference,HashSet[A],HashSet[A]>`_, and 26## `symmetric difference <#symmetricDifference,HashSet[A],HashSet[A]>`_ 27## 28## .. code-block:: 29## echo toHashSet([9, 5, 1]) # {9, 1, 5} 30## echo toOrderedSet([9, 5, 1]) # {9, 5, 1} 31## 32## let 33## s1 = toHashSet([9, 5, 1]) 34## s2 = toHashSet([3, 5, 7]) 35## 36## echo s1 + s2 # {9, 1, 3, 5, 7} 37## echo s1 - s2 # {1, 9} 38## echo s1 * s2 # {5} 39## echo s1 -+- s2 # {9, 1, 3, 7} 40## 41## 42## Note: The data types declared here have *value semantics*: This means 43## that `=` performs a copy of the set. 44## 45## **See also:** 46## * `intsets module <intsets.html>`_ for efficient int sets 47## * `tables module <tables.html>`_ for hash tables 48 49 50import 51 hashes, math 52 53{.pragma: myShallow.} 54# For "integer-like A" that are too big for intsets/bit-vectors to be practical, 55# it would be best to shrink hcode to the same size as the integer. Larger 56# codes should never be needed, and this can pack more entries per cache-line. 57# Losing hcode entirely is also possible - if some element value is forbidden. 58type 59 KeyValuePair[A] = tuple[hcode: Hash, key: A] 60 KeyValuePairSeq[A] = seq[KeyValuePair[A]] 61 HashSet*[A] {.myShallow.} = object ## \ 62 ## A generic hash set. 63 ## 64 ## Use `init proc <#init,HashSet[A]>`_ or `initHashSet proc <#initHashSet,int>`_ 65 ## before calling other procs on it. 66 data: KeyValuePairSeq[A] 67 counter: int 68 69type 70 OrderedKeyValuePair[A] = tuple[ 71 hcode: Hash, next: int, key: A] 72 OrderedKeyValuePairSeq[A] = seq[OrderedKeyValuePair[A]] 73 OrderedSet*[A] {.myShallow.} = object ## \ 74 ## A generic hash set that remembers insertion order. 75 ## 76 ## Use `init proc <#init,OrderedSet[A]>`_ or `initOrderedSet proc 77 ## <#initOrderedSet>`_ before calling other procs on it. 78 data: OrderedKeyValuePairSeq[A] 79 counter, first, last: int 80 SomeSet*[A] = HashSet[A] | OrderedSet[A] 81 ## Type union representing `HashSet` or `OrderedSet`. 82 83const 84 defaultInitialSize* = 64 85 86include setimpl 87 88# --------------------------------------------------------------------- 89# ------------------------------ HashSet ------------------------------ 90# --------------------------------------------------------------------- 91 92 93proc init*[A](s: var HashSet[A], initialSize = defaultInitialSize) = 94 ## Initializes a hash set. 95 ## 96 ## Starting from Nim v0.20, sets are initialized by default and it is 97 ## not necessary to call this function explicitly. 98 ## 99 ## You can call this proc on a previously initialized hash set, which will 100 ## discard all its values. This might be more convenient than iterating over 101 ## existing values and calling `excl() <#excl,HashSet[A],A>`_ on them. 102 ## 103 ## See also: 104 ## * `initHashSet proc <#initHashSet>`_ 105 ## * `toHashSet proc <#toHashSet,openArray[A]>`_ 106 runnableExamples: 107 var a: HashSet[int] 108 init(a) 109 110 initImpl(s, initialSize) 111 112proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = 113 ## Wrapper around `init proc <#init,HashSet[A]>`_ for initialization of 114 ## hash sets. 115 ## 116 ## Returns an empty hash set you can assign directly in `var` blocks in a 117 ## single line. 118 ## 119 ## Starting from Nim v0.20, sets are initialized by default and it is 120 ## not necessary to call this function explicitly. 121 ## 122 ## See also: 123 ## * `toHashSet proc <#toHashSet,openArray[A]>`_ 124 runnableExamples: 125 var a = initHashSet[int]() 126 a.incl(3) 127 assert len(a) == 1 128 129 result.init(initialSize) 130 131proc `[]`*[A](s: var HashSet[A], key: A): var A = 132 ## Returns the element that is actually stored in `s` which has the same 133 ## value as `key` or raises the `KeyError` exception. 134 ## 135 ## This is useful when one overloaded `hash` and `==` but still needs 136 ## reference semantics for sharing. 137 var hc: Hash 138 var index = rawGet(s, key, hc) 139 if index >= 0: result = s.data[index].key 140 else: 141 when compiles($key): 142 raise newException(KeyError, "key not found: " & $key) 143 else: 144 raise newException(KeyError, "key not found") 145 146proc contains*[A](s: HashSet[A], key: A): bool = 147 ## Returns true if `key` is in `s`. 148 ## 149 ## This allows the usage of `in` operator. 150 ## 151 ## See also: 152 ## * `incl proc <#incl,HashSet[A],A>`_ 153 ## * `containsOrIncl proc <#containsOrIncl,HashSet[A],A>`_ 154 runnableExamples: 155 var values = initHashSet[int]() 156 assert(not values.contains(2)) 157 assert 2 notin values 158 159 values.incl(2) 160 assert values.contains(2) 161 assert 2 in values 162 163 var hc: Hash 164 var index = rawGet(s, key, hc) 165 result = index >= 0 166 167proc len*[A](s: HashSet[A]): int = 168 ## Returns the number of elements in `s`. 169 ## 170 ## Due to an implementation detail you can call this proc on variables which 171 ## have not been initialized yet. The proc will return zero as the length 172 ## then. 173 runnableExamples: 174 var a: HashSet[string] 175 assert len(a) == 0 176 let s = toHashSet([3, 5, 7]) 177 assert len(s) == 3 178 179 result = s.counter 180 181proc card*[A](s: HashSet[A]): int = 182 ## Alias for `len() <#len,HashSet[A]>`_. 183 ## 184 ## Card stands for the `cardinality 185 ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set. 186 result = s.counter 187 188proc incl*[A](s: var HashSet[A], key: A) = 189 ## Includes an element `key` in `s`. 190 ## 191 ## This doesn't do anything if `key` is already in `s`. 192 ## 193 ## See also: 194 ## * `excl proc <#excl,HashSet[A],A>`_ for excluding an element 195 ## * `incl proc <#incl,HashSet[A],HashSet[A]>`_ for including other set 196 ## * `containsOrIncl proc <#containsOrIncl,HashSet[A],A>`_ 197 runnableExamples: 198 var values = initHashSet[int]() 199 values.incl(2) 200 values.incl(2) 201 assert values.len == 1 202 203 inclImpl() 204 205proc incl*[A](s: var HashSet[A], other: HashSet[A]) = 206 ## Includes all elements from `other` set into `s` (must be declared as `var`). 207 ## 208 ## This is the in-place version of `s + other <#+,HashSet[A],HashSet[A]>`_. 209 ## 210 ## See also: 211 ## * `excl proc <#excl,HashSet[A],HashSet[A]>`_ for excluding other set 212 ## * `incl proc <#incl,HashSet[A],A>`_ for including an element 213 ## * `containsOrIncl proc <#containsOrIncl,HashSet[A],A>`_ 214 runnableExamples: 215 var 216 values = toHashSet([1, 2, 3]) 217 others = toHashSet([3, 4, 5]) 218 values.incl(others) 219 assert values.len == 5 220 221 for item in other: incl(s, item) 222 223proc toHashSet*[A](keys: openArray[A]): HashSet[A] = 224 ## Creates a new hash set that contains the members of the given 225 ## collection (seq, array, or string) `keys`. 226 ## 227 ## Duplicates are removed. 228 ## 229 ## See also: 230 ## * `initHashSet proc <#initHashSet>`_ 231 runnableExamples: 232 let 233 a = toHashSet([5, 3, 2]) 234 b = toHashSet("abracadabra") 235 assert len(a) == 3 236 ## a == {2, 3, 5} 237 assert len(b) == 5 238 ## b == {'a', 'b', 'c', 'd', 'r'} 239 240 result = initHashSet[A](keys.len) 241 for key in items(keys): result.incl(key) 242 243iterator items*[A](s: HashSet[A]): A = 244 ## Iterates over elements of the set `s`. 245 ## 246 ## If you need a sequence with the elements you can use `sequtils.toSeq 247 ## template <sequtils.html#toSeq.t,untyped>`_. 248 ## 249 ## .. code-block:: 250 ## type 251 ## pair = tuple[a, b: int] 252 ## var 253 ## a, b = initHashSet[pair]() 254 ## a.incl((2, 3)) 255 ## a.incl((3, 2)) 256 ## a.incl((2, 3)) 257 ## for x, y in a.items: 258 ## b.incl((x - 2, y + 1)) 259 ## assert a.len == 2 260 ## echo b 261 ## # --> {(a: 1, b: 3), (a: 0, b: 4)} 262 let length = s.len 263 for h in 0 .. high(s.data): 264 if isFilled(s.data[h].hcode): 265 yield s.data[h].key 266 assert(len(s) == length, "the length of the HashSet changed while iterating over it") 267 268proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = 269 ## Includes `key` in the set `s` and tells if `key` was already in `s`. 270 ## 271 ## The difference with regards to the `incl proc <#incl,HashSet[A],A>`_ is 272 ## that this proc returns `true` if `s` already contained `key`. The 273 ## proc will return `false` if `key` was added as a new value to `s` during 274 ## this call. 275 ## 276 ## See also: 277 ## * `incl proc <#incl,HashSet[A],A>`_ for including an element 278 ## * `incl proc <#incl,HashSet[A],HashSet[A]>`_ for including other set 279 ## * `missingOrExcl proc <#missingOrExcl,HashSet[A],A>`_ 280 runnableExamples: 281 var values = initHashSet[int]() 282 assert values.containsOrIncl(2) == false 283 assert values.containsOrIncl(2) == true 284 assert values.containsOrIncl(3) == false 285 286 containsOrInclImpl() 287 288proc excl*[A](s: var HashSet[A], key: A) = 289 ## Excludes `key` from the set `s`. 290 ## 291 ## This doesn't do anything if `key` is not found in `s`. 292 ## 293 ## See also: 294 ## * `incl proc <#incl,HashSet[A],A>`_ for including an element 295 ## * `excl proc <#excl,HashSet[A],HashSet[A]>`_ for excluding other set 296 ## * `missingOrExcl proc <#missingOrExcl,HashSet[A],A>`_ 297 runnableExamples: 298 var s = toHashSet([2, 3, 6, 7]) 299 s.excl(2) 300 s.excl(2) 301 assert s.len == 3 302 303 discard exclImpl(s, key) 304 305proc excl*[A](s: var HashSet[A], other: HashSet[A]) = 306 ## Excludes all elements of `other` set from `s`. 307 ## 308 ## This is the in-place version of `s - other <#-,HashSet[A],HashSet[A]>`_. 309 ## 310 ## See also: 311 ## * `incl proc <#incl,HashSet[A],HashSet[A]>`_ for including other set 312 ## * `excl proc <#excl,HashSet[A],A>`_ for excluding an element 313 ## * `missingOrExcl proc <#missingOrExcl,HashSet[A],A>`_ 314 runnableExamples: 315 var 316 numbers = toHashSet([1, 2, 3, 4, 5]) 317 even = toHashSet([2, 4, 6, 8]) 318 numbers.excl(even) 319 assert len(numbers) == 3 320 ## numbers == {1, 3, 5} 321 322 for item in other: discard exclImpl(s, item) 323 324proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = 325 ## Excludes `key` in the set `s` and tells if `key` was already missing from `s`. 326 ## 327 ## The difference with regards to the `excl proc <#excl,HashSet[A],A>`_ is 328 ## that this proc returns `true` if `key` was missing from `s`. 329 ## The proc will return `false` if `key` was in `s` and it was removed 330 ## during this call. 331 ## 332 ## See also: 333 ## * `excl proc <#excl,HashSet[A],A>`_ for excluding an element 334 ## * `excl proc <#excl,HashSet[A],HashSet[A]>`_ for excluding other set 335 ## * `containsOrIncl proc <#containsOrIncl,HashSet[A],A>`_ 336 runnableExamples: 337 var s = toHashSet([2, 3, 6, 7]) 338 assert s.missingOrExcl(4) == true 339 assert s.missingOrExcl(6) == false 340 assert s.missingOrExcl(6) == true 341 342 exclImpl(s, key) 343 344proc pop*[A](s: var HashSet[A]): A = 345 ## Removes and returns an arbitrary element from the set `s`. 346 ## 347 ## Raises KeyError if the set `s` is empty. 348 ## 349 ## See also: 350 ## * `clear proc <#clear,HashSet[A]>`_ 351 runnableExamples: 352 var s = toHashSet([2, 1]) 353 assert [s.pop, s.pop] in [[1, 2], [2,1]] # order unspecified 354 doAssertRaises(KeyError, echo s.pop) 355 356 for h in 0 .. high(s.data): 357 if isFilled(s.data[h].hcode): 358 result = s.data[h].key 359 excl(s, result) 360 return result 361 raise newException(KeyError, "set is empty") 362 363proc clear*[A](s: var HashSet[A]) = 364 ## Clears the HashSet back to an empty state, without shrinking 365 ## any of the existing storage. 366 ## 367 ## `O(n)` operation, where `n` is the size of the hash bucket. 368 ## 369 ## See also: 370 ## * `pop proc <#pop,HashSet[A]>`_ 371 runnableExamples: 372 var s = toHashSet([3, 5, 7]) 373 clear(s) 374 assert len(s) == 0 375 376 s.counter = 0 377 for i in 0 ..< s.data.len: 378 s.data[i].hcode = 0 379 s.data[i].key = default(typeof(s.data[i].key)) 380 381 382proc union*[A](s1, s2: HashSet[A]): HashSet[A] = 383 ## Returns the union of the sets `s1` and `s2`. 384 ## 385 ## The same as `s1 + s2 <#+,HashSet[A],HashSet[A]>`_. 386 ## 387 ## The union of two sets is represented mathematically as *A ∪ B* and is the 388 ## set of all objects that are members of `s1`, `s2` or both. 389 ## 390 ## See also: 391 ## * `intersection proc <#intersection,HashSet[A],HashSet[A]>`_ 392 ## * `difference proc <#difference,HashSet[A],HashSet[A]>`_ 393 ## * `symmetricDifference proc <#symmetricDifference,HashSet[A],HashSet[A]>`_ 394 runnableExamples: 395 let 396 a = toHashSet(["a", "b"]) 397 b = toHashSet(["b", "c"]) 398 c = union(a, b) 399 assert c == toHashSet(["a", "b", "c"]) 400 401 result = s1 402 incl(result, s2) 403 404proc intersection*[A](s1, s2: HashSet[A]): HashSet[A] = 405 ## Returns the intersection of the sets `s1` and `s2`. 406 ## 407 ## The same as `s1 * s2 <#*,HashSet[A],HashSet[A]>`_. 408 ## 409 ## The intersection of two sets is represented mathematically as *A ∩ B* and 410 ## is the set of all objects that are members of `s1` and `s2` at the same 411 ## time. 412 ## 413 ## See also: 414 ## * `union proc <#union,HashSet[A],HashSet[A]>`_ 415 ## * `difference proc <#difference,HashSet[A],HashSet[A]>`_ 416 ## * `symmetricDifference proc <#symmetricDifference,HashSet[A],HashSet[A]>`_ 417 runnableExamples: 418 let 419 a = toHashSet(["a", "b"]) 420 b = toHashSet(["b", "c"]) 421 c = intersection(a, b) 422 assert c == toHashSet(["b"]) 423 424 result = initHashSet[A](max(min(s1.data.len, s2.data.len), 2)) 425 426 # iterate over the elements of the smaller set 427 if s1.data.len < s2.data.len: 428 for item in s1: 429 if item in s2: incl(result, item) 430 else: 431 for item in s2: 432 if item in s1: incl(result, item) 433 434 435proc difference*[A](s1, s2: HashSet[A]): HashSet[A] = 436 ## Returns the difference of the sets `s1` and `s2`. 437 ## 438 ## The same as `s1 - s2 <#-,HashSet[A],HashSet[A]>`_. 439 ## 440 ## The difference of two sets is represented mathematically as *A ∖ B* and is 441 ## the set of all objects that are members of `s1` and not members of `s2`. 442 ## 443 ## See also: 444 ## * `union proc <#union,HashSet[A],HashSet[A]>`_ 445 ## * `intersection proc <#intersection,HashSet[A],HashSet[A]>`_ 446 ## * `symmetricDifference proc <#symmetricDifference,HashSet[A],HashSet[A]>`_ 447 runnableExamples: 448 let 449 a = toHashSet(["a", "b"]) 450 b = toHashSet(["b", "c"]) 451 c = difference(a, b) 452 assert c == toHashSet(["a"]) 453 454 result = initHashSet[A]() 455 for item in s1: 456 if not contains(s2, item): 457 incl(result, item) 458 459proc symmetricDifference*[A](s1, s2: HashSet[A]): HashSet[A] = 460 ## Returns the symmetric difference of the sets `s1` and `s2`. 461 ## 462 ## The same as `s1 -+- s2 <#-+-,HashSet[A],HashSet[A]>`_. 463 ## 464 ## The symmetric difference of two sets is represented mathematically as *A △ 465 ## B* or *A ⊖ B* and is the set of all objects that are members of `s1` or 466 ## `s2` but not both at the same time. 467 ## 468 ## See also: 469 ## * `union proc <#union,HashSet[A],HashSet[A]>`_ 470 ## * `intersection proc <#intersection,HashSet[A],HashSet[A]>`_ 471 ## * `difference proc <#difference,HashSet[A],HashSet[A]>`_ 472 runnableExamples: 473 let 474 a = toHashSet(["a", "b"]) 475 b = toHashSet(["b", "c"]) 476 c = symmetricDifference(a, b) 477 assert c == toHashSet(["a", "c"]) 478 479 result = s1 480 for item in s2: 481 if containsOrIncl(result, item): excl(result, item) 482 483proc `+`*[A](s1, s2: HashSet[A]): HashSet[A] {.inline.} = 484 ## Alias for `union(s1, s2) <#union,HashSet[A],HashSet[A]>`_. 485 result = union(s1, s2) 486 487proc `*`*[A](s1, s2: HashSet[A]): HashSet[A] {.inline.} = 488 ## Alias for `intersection(s1, s2) <#intersection,HashSet[A],HashSet[A]>`_. 489 result = intersection(s1, s2) 490 491proc `-`*[A](s1, s2: HashSet[A]): HashSet[A] {.inline.} = 492 ## Alias for `difference(s1, s2) <#difference,HashSet[A],HashSet[A]>`_. 493 result = difference(s1, s2) 494 495proc `-+-`*[A](s1, s2: HashSet[A]): HashSet[A] {.inline.} = 496 ## Alias for `symmetricDifference(s1, s2) 497 ## <#symmetricDifference,HashSet[A],HashSet[A]>`_. 498 result = symmetricDifference(s1, s2) 499 500proc disjoint*[A](s1, s2: HashSet[A]): bool = 501 ## Returns `true` if the sets `s1` and `s2` have no items in common. 502 runnableExamples: 503 let 504 a = toHashSet(["a", "b"]) 505 b = toHashSet(["b", "c"]) 506 assert disjoint(a, b) == false 507 assert disjoint(a, b - a) == true 508 509 for item in s1: 510 if item in s2: return false 511 return true 512 513proc `<`*[A](s, t: HashSet[A]): bool = 514 ## Returns true if `s` is a strict or proper subset of `t`. 515 ## 516 ## A strict or proper subset `s` has all of its members in `t` but `t` has 517 ## more elements than `s`. 518 runnableExamples: 519 let 520 a = toHashSet(["a", "b"]) 521 b = toHashSet(["b", "c"]) 522 c = intersection(a, b) 523 assert c < a and c < b 524 assert(not (a < a)) 525 526 s.counter != t.counter and s <= t 527 528proc `<=`*[A](s, t: HashSet[A]): bool = 529 ## Returns true if `s` is a subset of `t`. 530 ## 531 ## A subset `s` has all of its members in `t` and `t` doesn't necessarily 532 ## have more members than `s`. That is, `s` can be equal to `t`. 533 runnableExamples: 534 let 535 a = toHashSet(["a", "b"]) 536 b = toHashSet(["b", "c"]) 537 c = intersection(a, b) 538 assert c <= a and c <= b 539 assert a <= a 540 541 result = false 542 if s.counter > t.counter: return 543 result = true 544 for item in items(s): 545 if not(t.contains(item)): 546 result = false 547 return 548 549proc `==`*[A](s, t: HashSet[A]): bool = 550 ## Returns true if both `s` and `t` have the same members and set size. 551 runnableExamples: 552 var 553 a = toHashSet([1, 2]) 554 b = toHashSet([2, 1]) 555 assert a == b 556 557 s.counter == t.counter and s <= t 558 559proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] = 560 ## Returns a new set after applying `op` proc on each of the elements of 561 ##`data` set. 562 ## 563 ## You can use this proc to transform the elements from a set. 564 runnableExamples: 565 let 566 a = toHashSet([1, 2, 3]) 567 b = a.map(proc (x: int): string = $x) 568 assert b == toHashSet(["1", "2", "3"]) 569 570 result = initHashSet[B]() 571 for item in items(data): result.incl(op(item)) 572 573proc hash*[A](s: HashSet[A]): Hash = 574 ## Hashing of HashSet. 575 for h in 0 .. high(s.data): 576 result = result xor s.data[h].hcode 577 result = !$result 578 579proc `$`*[A](s: HashSet[A]): string = 580 ## Converts the set `s` to a string, mostly for logging and printing purposes. 581 ## 582 ## Don't use this proc for serialization, the representation may change at 583 ## any moment and values are not escaped. 584 ## 585 ## **Examples:** 586 ## 587 ## .. code-block:: 588 ## echo toHashSet([2, 4, 5]) 589 ## # --> {2, 4, 5} 590 ## echo toHashSet(["no", "esc'aping", "is \" provided"]) 591 ## # --> {no, esc'aping, is " provided} 592 dollarImpl() 593 594 595proc initSet*[A](initialSize = defaultInitialSize): HashSet[A] {.deprecated: 596 "Deprecated since v0.20, use 'initHashSet'".} = initHashSet[A](initialSize) 597 598proc toSet*[A](keys: openArray[A]): HashSet[A] {.deprecated: 599 "Deprecated since v0.20, use 'toHashSet'".} = toHashSet[A](keys) 600 601proc isValid*[A](s: HashSet[A]): bool {.deprecated: 602 "Deprecated since v0.20; sets are initialized by default".} = 603 ## Returns `true` if the set has been initialized (with `initHashSet proc 604 ## <#initHashSet>`_ or `init proc <#init,HashSet[A]>`_). 605 ## 606 runnableExamples: 607 proc savePreferences(options: HashSet[string]) = 608 assert options.isValid, "Pass an initialized set!" 609 # Do stuff here, may crash in release builds! 610 result = s.data.len > 0 611 612 613 614# --------------------------------------------------------------------- 615# --------------------------- OrderedSet ------------------------------ 616# --------------------------------------------------------------------- 617 618template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} = 619 if s.data.len > 0: 620 var h = s.first 621 var idx = 0 622 while h >= 0: 623 var nxt = s.data[h].next 624 if isFilled(s.data[h].hcode): 625 yieldStmt 626 inc(idx) 627 h = nxt 628 629 630proc init*[A](s: var OrderedSet[A], initialSize = defaultInitialSize) = 631 ## Initializes an ordered hash set. 632 ## 633 ## Starting from Nim v0.20, sets are initialized by default and it is 634 ## not necessary to call this function explicitly. 635 ## 636 ## You can call this proc on a previously initialized hash set, which will 637 ## discard all its values. This might be more convenient than iterating over 638 ## existing values and calling `excl() <#excl,HashSet[A],A>`_ on them. 639 ## 640 ## See also: 641 ## * `initOrderedSet proc <#initOrderedSet>`_ 642 ## * `toOrderedSet proc <#toOrderedSet,openArray[A]>`_ 643 runnableExamples: 644 var a: OrderedSet[int] 645 init(a) 646 647 initImpl(s, initialSize) 648 649proc initOrderedSet*[A](initialSize = defaultInitialSize): OrderedSet[A] = 650 ## Wrapper around `init proc <#init,OrderedSet[A]>`_ for initialization of 651 ## ordered hash sets. 652 ## 653 ## Returns an empty ordered hash set you can assign directly in `var` blocks 654 ## in a single line. 655 ## 656 ## Starting from Nim v0.20, sets are initialized by default and it is 657 ## not necessary to call this function explicitly. 658 ## 659 ## See also: 660 ## * `toOrderedSet proc <#toOrderedSet,openArray[A]>`_ 661 runnableExamples: 662 var a = initOrderedSet[int]() 663 a.incl(3) 664 assert len(a) == 1 665 666 result.init(initialSize) 667 668proc toOrderedSet*[A](keys: openArray[A]): OrderedSet[A] = 669 ## Creates a new hash set that contains the members of the given 670 ## collection (seq, array, or string) `keys`. 671 ## 672 ## Duplicates are removed. 673 ## 674 ## See also: 675 ## * `initOrderedSet proc <#initOrderedSet>`_ 676 runnableExamples: 677 let 678 a = toOrderedSet([5, 3, 2]) 679 b = toOrderedSet("abracadabra") 680 assert len(a) == 3 681 ## a == {5, 3, 2} # different than in HashSet 682 assert len(b) == 5 683 ## b == {'a', 'b', 'r', 'c', 'd'} # different than in HashSet 684 685 result = initOrderedSet[A](keys.len) 686 for key in items(keys): result.incl(key) 687 688proc contains*[A](s: OrderedSet[A], key: A): bool = 689 ## Returns true if `key` is in `s`. 690 ## 691 ## This allows the usage of `in` operator. 692 ## 693 ## See also: 694 ## * `incl proc <#incl,OrderedSet[A],A>`_ 695 ## * `containsOrIncl proc <#containsOrIncl,OrderedSet[A],A>`_ 696 runnableExamples: 697 var values = initOrderedSet[int]() 698 assert(not values.contains(2)) 699 assert 2 notin values 700 701 values.incl(2) 702 assert values.contains(2) 703 assert 2 in values 704 705 var hc: Hash 706 var index = rawGet(s, key, hc) 707 result = index >= 0 708 709proc incl*[A](s: var OrderedSet[A], key: A) = 710 ## Includes an element `key` in `s`. 711 ## 712 ## This doesn't do anything if `key` is already in `s`. 713 ## 714 ## See also: 715 ## * `excl proc <#excl,OrderedSet[A],A>`_ for excluding an element 716 ## * `incl proc <#incl,HashSet[A],OrderedSet[A]>`_ for including other set 717 ## * `containsOrIncl proc <#containsOrIncl,OrderedSet[A],A>`_ 718 runnableExamples: 719 var values = initOrderedSet[int]() 720 values.incl(2) 721 values.incl(2) 722 assert values.len == 1 723 724 inclImpl() 725 726proc incl*[A](s: var HashSet[A], other: OrderedSet[A]) = 727 ## Includes all elements from the OrderedSet `other` into 728 ## HashSet `s` (must be declared as `var`). 729 ## 730 ## See also: 731 ## * `incl proc <#incl,OrderedSet[A],A>`_ for including an element 732 ## * `containsOrIncl proc <#containsOrIncl,OrderedSet[A],A>`_ 733 runnableExamples: 734 var 735 values = toHashSet([1, 2, 3]) 736 others = toOrderedSet([3, 4, 5]) 737 values.incl(others) 738 assert values.len == 5 739 740 for item in items(other): incl(s, item) 741 742proc containsOrIncl*[A](s: var OrderedSet[A], key: A): bool = 743 ## Includes `key` in the set `s` and tells if `key` was already in `s`. 744 ## 745 ## The difference with regards to the `incl proc <#incl,OrderedSet[A],A>`_ is 746 ## that this proc returns `true` if `s` already contained `key`. The 747 ## proc will return false if `key` was added as a new value to `s` during 748 ## this call. 749 ## 750 ## See also: 751 ## * `incl proc <#incl,OrderedSet[A],A>`_ for including an element 752 ## * `missingOrExcl proc <#missingOrExcl,OrderedSet[A],A>`_ 753 runnableExamples: 754 var values = initOrderedSet[int]() 755 assert values.containsOrIncl(2) == false 756 assert values.containsOrIncl(2) == true 757 assert values.containsOrIncl(3) == false 758 759 containsOrInclImpl() 760 761proc excl*[A](s: var OrderedSet[A], key: A) = 762 ## Excludes `key` from the set `s`. Efficiency: `O(n)`. 763 ## 764 ## This doesn't do anything if `key` is not found in `s`. 765 ## 766 ## See also: 767 ## * `incl proc <#incl,OrderedSet[A],A>`_ for including an element 768 ## * `missingOrExcl proc <#missingOrExcl,OrderedSet[A],A>`_ 769 runnableExamples: 770 var s = toOrderedSet([2, 3, 6, 7]) 771 s.excl(2) 772 s.excl(2) 773 assert s.len == 3 774 775 discard exclImpl(s, key) 776 777proc missingOrExcl*[A](s: var OrderedSet[A], key: A): bool = 778 ## Excludes `key` in the set `s` and tells if `key` was already missing from `s`. 779 ## Efficiency: O(n). 780 ## 781 ## The difference with regards to the `excl proc <#excl,OrderedSet[A],A>`_ is 782 ## that this proc returns `true` if `key` was missing from `s`. 783 ## The proc will return `false` if `key` was in `s` and it was removed 784 ## during this call. 785 ## 786 ## See also: 787 ## * `excl proc <#excl,OrderedSet[A],A>`_ 788 ## * `containsOrIncl proc <#containsOrIncl,OrderedSet[A],A>`_ 789 runnableExamples: 790 var s = toOrderedSet([2, 3, 6, 7]) 791 assert s.missingOrExcl(4) == true 792 assert s.missingOrExcl(6) == false 793 assert s.missingOrExcl(6) == true 794 795 exclImpl(s, key) 796 797proc clear*[A](s: var OrderedSet[A]) = 798 ## Clears the OrderedSet back to an empty state, without shrinking 799 ## any of the existing storage. 800 ## 801 ## `O(n)` operation where `n` is the size of the hash bucket. 802 runnableExamples: 803 var s = toOrderedSet([3, 5, 7]) 804 clear(s) 805 assert len(s) == 0 806 807 s.counter = 0 808 s.first = -1 809 s.last = -1 810 for i in 0 ..< s.data.len: 811 s.data[i].hcode = 0 812 s.data[i].next = 0 813 s.data[i].key = default(typeof(s.data[i].key)) 814 815proc len*[A](s: OrderedSet[A]): int {.inline.} = 816 ## Returns the number of elements in `s`. 817 ## 818 ## Due to an implementation detail you can call this proc on variables which 819 ## have not been initialized yet. The proc will return zero as the length 820 ## then. 821 runnableExamples: 822 var a: OrderedSet[string] 823 assert len(a) == 0 824 let s = toHashSet([3, 5, 7]) 825 assert len(s) == 3 826 827 result = s.counter 828 829proc card*[A](s: OrderedSet[A]): int {.inline.} = 830 ## Alias for `len() <#len,OrderedSet[A]>`_. 831 ## 832 ## Card stands for the `cardinality 833 ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set. 834 result = s.counter 835 836proc `==`*[A](s, t: OrderedSet[A]): bool = 837 ## Equality for ordered sets. 838 runnableExamples: 839 let 840 a = toOrderedSet([1, 2]) 841 b = toOrderedSet([2, 1]) 842 assert(not (a == b)) 843 844 if s.counter != t.counter: return false 845 var h = s.first 846 var g = t.first 847 var compared = 0 848 while h >= 0 and g >= 0: 849 var nxh = s.data[h].next 850 var nxg = t.data[g].next 851 if isFilled(s.data[h].hcode) and isFilled(t.data[g].hcode): 852 if s.data[h].key == t.data[g].key: 853 inc compared 854 else: 855 return false 856 h = nxh 857 g = nxg 858 result = compared == s.counter 859 860proc hash*[A](s: OrderedSet[A]): Hash = 861 ## Hashing of OrderedSet. 862 forAllOrderedPairs: 863 result = result !& s.data[h].hcode 864 result = !$result 865 866proc `$`*[A](s: OrderedSet[A]): string = 867 ## Converts the ordered hash set `s` to a string, mostly for logging and 868 ## printing purposes. 869 ## 870 ## Don't use this proc for serialization, the representation may change at 871 ## any moment and values are not escaped. 872 ## 873 ## **Examples:** 874 ## 875 ## .. code-block:: 876 ## echo toOrderedSet([2, 4, 5]) 877 ## # --> {2, 4, 5} 878 ## echo toOrderedSet(["no", "esc'aping", "is \" provided"]) 879 ## # --> {no, esc'aping, is " provided} 880 dollarImpl() 881 882 883 884iterator items*[A](s: OrderedSet[A]): A = 885 ## Iterates over keys in the ordered set `s` in insertion order. 886 ## 887 ## If you need a sequence with the elements you can use `sequtils.toSeq 888 ## template <sequtils.html#toSeq.t,untyped>`_. 889 ## 890 ## .. code-block:: 891 ## var a = initOrderedSet[int]() 892 ## for value in [9, 2, 1, 5, 1, 8, 4, 2]: 893 ## a.incl(value) 894 ## for value in a.items: 895 ## echo "Got ", value 896 ## # --> Got 9 897 ## # --> Got 2 898 ## # --> Got 1 899 ## # --> Got 5 900 ## # --> Got 8 901 ## # --> Got 4 902 let length = s.len 903 forAllOrderedPairs: 904 yield s.data[h].key 905 assert(len(s) == length, "the length of the OrderedSet changed while iterating over it") 906 907iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = 908 ## Iterates through (position, value) tuples of OrderedSet `s`. 909 runnableExamples: 910 let a = toOrderedSet("abracadabra") 911 var p = newSeq[(int, char)]() 912 for x in pairs(a): 913 p.add(x) 914 assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')] 915 916 let length = s.len 917 forAllOrderedPairs: 918 yield (idx, s.data[h].key) 919 assert(len(s) == length, "the length of the OrderedSet changed while iterating over it") 920