diff options
Diffstat (limited to 'lib/pure/algorithm.nim')
| -rw-r--r-- | lib/pure/algorithm.nim | 51 |
1 files changed, 33 insertions, 18 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 20976e788..08d224dfd 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -11,15 +11,15 @@ type SortOrder* = enum ## sort order - Descending, Ascending + Descending, Ascending {.deprecated: [TSortOrder: SortOrder].} -proc `*`*(x: int, order: SortOrder): int {.inline.} = +proc `*`*(x: int, order: SortOrder): int {.inline.} = ## flips `x` if ``order == Descending``; ## if ``order == Ascending`` then `x` is returned. - ## `x` is supposed to be the result of a comparator, ie ``< 0`` for + ## `x` is supposed to be the result of a comparator, ie ``< 0`` for ## *less than*, ``== 0`` for *equal*, ``> 0`` for *greater than*. var y = order.ord - 1 result = (x xor y) - y @@ -73,14 +73,15 @@ const onlySafeCode = true proc lowerBound*[T](a: openArray[T], key: T, cmp: proc(x,y: T): int {.closure.}): int = - ## same as binarySearch except that if key is not in `a` then this + ## same as binarySearch except that if key is not in `a` then this ## returns the location where `key` would be if it were. In other - ## words if you have a sorted sequence and you call insert(thing, elm, lowerBound(thing, elm)) - ## the sequence will still be sorted + ## words if you have a sorted sequence and you call + ## insert(thing, elm, lowerBound(thing, elm)) + ## the sequence will still be sorted. + ## + ## `cmp` is the comparator function to use, the expected return values are + ## the same as that of system.cmp. ## - ## `cmp` is the comparator function to use, the expected return values are the same as - ## that of system.cmp - ## ## example:: ## ## var arr = @[1,2,3,5,6,7,8,9] @@ -102,9 +103,9 @@ proc lowerBound*[T](a: openArray[T], key: T, cmp: proc(x,y: T): int {.closure.}) count = step proc lowerBound*[T](a: openArray[T], key: T): int = lowerBound(a, key, cmp[T]) -proc merge[T](a, b: var openArray[T], lo, m, hi: int, +proc merge[T](a, b: var openArray[T], lo, m, hi: int, cmp: proc (x, y: T): int {.closure.}, order: SortOrder) = - template `<-` (a, b: expr) = + template `<-` (a, b: expr) = when false: a = b elif onlySafeCode: @@ -151,10 +152,10 @@ proc merge[T](a, b: var openArray[T], lo, m, hi: int, proc sort*[T](a: var openArray[T], cmp: proc (x, y: T): int {.closure.}, order = SortOrder.Ascending) = - ## Default Nim sort. The sorting is guaranteed to be stable and + ## Default Nim sort. The sorting is guaranteed to be stable and ## the worst case is guaranteed to be O(n log n). ## The current implementation uses an iterative - ## mergesort to achieve this. It uses a temporary sequence of + ## mergesort to achieve this. It uses a temporary sequence of ## length ``a.len div 2``. Currently Nim does not support a ## sensible default argument for ``cmp``, so you have to provide one ## of your own. However, the ``system.cmp`` procs can be used: @@ -187,14 +188,15 @@ proc sort*[T](a: var openArray[T], dec(m, s*2) s = s*2 -proc sorted*[T](a: openArray[T], cmp: proc(x, y: T): int {.closure.}, order = SortOrder.Ascending): seq[T] = +proc sorted*[T](a: openArray[T], cmp: proc(x, y: T): int {.closure.}, + order = SortOrder.Ascending): seq[T] = ## returns `a` sorted by `cmp` in the specified `order`. result = newSeq[T](a.len) for i in 0 .. a.high: result[i] = a[i] sort(result, cmp, order) -template sortByIt*(seq1, op: expr): expr = +template sortedByIt*(seq1, op: expr): expr = ## Convenience template around the ``sorted`` proc to reduce typing. ## ## The template injects the ``it`` variable which you can use directly in an @@ -202,10 +204,23 @@ template sortByIt*(seq1, op: expr): expr = ## ## .. code-block:: nim ## - ## var users: seq[tuple[id: int, name: string]] = - ## @[(0, "Smith"), (1, "Pratt"), (2, "Sparrow")] + ## type Person = tuple[name: string, age: int] + ## var + ## p1: Person = (name: "p1", age: 60) + ## p2: Person = (name: "p2", age: 20) + ## p3: Person = (name: "p3", age: 30) + ## p4: Person = (name: "p4", age: 30) + ## + ## people = @[p1,p2,p4,p3] + ## + ## echo people.sortedByIt(it.name) + ## + ## Because the underlying ``cmp()`` is defined for tuples you can do + ## a nested sort like in the following example: + ## + ## .. code-block:: nim ## - ## echo users.sortByIt(it.name) + ## echo people.sortedByIt((it.age, it.name)) ## var result {.gensym.} = sorted(seq1, proc(x, y: type(seq1[0])): int = var it {.inject.} = x |