Nim - This repository contains the Nim compiler, Nim's stdlib, tools, and documentation. (mirror)

diff options

Diffstat (limited to 'lib/pure/times.nim')

0 files changed, 0 insertions, 0 deletions

d='n268' href='#n268'>268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323

# # # Nim's Runtime Library # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # ## This module implements some common generic algorithms. type SortOrder* = enum ## sort order Descending, Ascending {.deprecated: [TSortOrder: SortOrder].} 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 ## *less than*, ``== 0`` for *equal*, ``> 0`` for *greater than*. var y = order.ord - 1 result = (x xor y) - y proc reverse*[T](a: var openArray[T], first, last: Natural) = ## reverses the array ``a[first..last]``. var x = first var y = last while x < y: swap(a[x], a[y]) dec(y) inc(x) proc reverse*[T](a: var openArray[T]) = ## reverses the array `a`. reverse(a, 0, a.high) proc reversed*[T](a: openArray[T], first, last: Natural): seq[T] = ## returns the reverse of the array `a[first..last]`. result = newSeq[T](last - first + 1) var x = first.int var y = last.int while x <= last: result[x] = a[y] dec(y) inc(x) proc reversed*[T](a: openArray[T]): seq[T] = ## returns the reverse of the array `a`. reversed(a, 0, a.high) proc binarySearch*[T](a: openArray[T], key: T): int = ## binary search for `key` in `a`. Returns -1 if not found. var b = len(a) while result < b: var mid = (result + b) div 2 if a[mid] < key: result = mid + 1 else: b = mid if result >= len(a) or a[result] != key: result = -1 proc smartBinarySearch*[T](a: openArray[T], key: T): int = ## ``a.len`` must be a power of 2 for this to work. var step = a.len div 2 while step > 0: if a[result or step] <= key: result = result or step step = step shr 1 if a[result] != key: result = -1 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 ## 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. ## ## `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] ## arr.insert(4, arr.lowerBound(4)) ## `after running the above arr is `[1,2,3,4,5,6,7,8,9]` result = a.low var pos = result var count, step: int count = a.high - a.low + 1 while count != 0: pos = result step = count div 2 pos += step if cmp(a[pos], key) < 0: pos.inc result = pos count -= step + 1 else: 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, cmp: proc (x, y: T): int {.closure.}, order: SortOrder) = template `<-` (a, b: expr) = when false: a = b elif onlySafeCode: shallowCopy(a, b) else: copyMem(addr(a), addr(b), sizeof(T)) # optimization: If max(left) <= min(right) there is nothing to do! # 1 2 3 4 ## 5 6 7 8 # -> O(n) for sorted arrays. # On random data this safes up to 40% of merge calls if cmp(a[m], a[m+1]) * order <= 0: return var j = lo # copy a[j..m] into b: assert j <= m when onlySafeCode: var bb = 0 while j <= m: b[bb] <- a[j] inc(bb) inc(j) else: copyMem(addr(b[0]), addr(a[j]), sizeof(T)*(m-j+1)) j = m+1 var i = 0 var k = lo # copy proper element back: while k < j and j <= hi: if cmp(b[i], a[j]) * order <= 0: a[k] <- b[i] inc(i) else: a[k] <- a[j] inc(j) inc(k) # copy rest of b: when onlySafeCode: while k < j: a[k] <- b[i] inc(k) inc(i) else: if k < j: copyMem(addr(a[k]), addr(b[i]), sizeof(T)*(j-k)) 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 ## 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 ## 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: ## ## .. code-block:: nim ## ## sort(myIntArray, system.cmp[int]) ## ## # do not use cmp[string] here as we want to use the specialized ## # overload: ## sort(myStrArray, system.cmp) ## ## You can inline adhoc comparison procs with the `do notation ## <manual.html#do-notation>`_. Example: ## ## .. code-block:: nim ## ## people.sort do (x, y: Person) -> int: ## result = cmp(x.surname, y.surname) ## if result == 0: ## result = cmp(x.name, y.name) var n = a.len var b: seq[T] newSeq(b, n div 2) var s = 1 while s < n: var m = n-1-s while m >= 0: merge(a, b, max(m-s+1, 0), m, m+s, cmp, order) 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] = ## 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 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 ## expression. Example: ## ## .. code-block:: nim ## ## 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 people.sortedByIt((it.age, it.name)) ## var result {.gensym.} = sorted(seq1, proc(x, y: type(seq1[0])): int = var it {.inject.} = x let a = op it = y let b = op result = cmp(a, b)) result proc product*[T](x: openArray[seq[T]]): seq[seq[T]] = ## produces the Cartesian product of the array. Warning: complexity ## may explode. result = @[] if x.len == 0: return if x.len == 1: result = @x return var indexes = newSeq[int](x.len) initial = newSeq[int](x.len) index = 0 # replace with newSeq as soon as #853 is fixed var next: seq[T] = @[] next.setLen(x.len) for i in 0..(x.len-1): if len(x[i]) == 0: return initial[i] = len(x[i])-1 indexes = initial while true: while indexes[index] == -1: indexes[index] = initial[index] index += 1 if index == x.len: return indexes[index] -= 1 for ni, i in indexes: next[ni] = x[ni][i] var res: seq[T] shallowCopy(res, next) result.add(res) index = 0 indexes[index] -= 1 proc nextPermutation*[T](x: var openarray[T]): bool {.discardable.} = ## Calculates the next lexicographic permutation, directly modifying ``x``. ## The result is whether a permutation happened, otherwise we have reached ## the last-ordered permutation. ## ## .. code-block:: nim ## ## var v = @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ## v.nextPermutation() ## echo v if x.len < 2: return false var i = x.high while i > 0 and x[i-1] >= x[i]: dec i if i == 0: return false var j = x.high while j >= i and x[j] <= x[i-1]: dec j swap x[j], x[i-1] x.reverse(i, x.high) result = true proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} = ## Calculates the previous lexicographic permutation, directly modifying ## ``x``. The result is whether a permutation happened, otherwise we have ## reached the first-ordered permutation. ## ## .. code-block:: nim ## ## var v = @[0, 1, 2, 3, 4, 5, 6, 7, 9, 8] ## v.prevPermutation() ## echo v if x.len < 2: return false var i = x.high while i > 0 and x[i-1] <= x[i]: dec i if i == 0: return false x.reverse(i, x.high) var j = x.high while j >= i and x[j-1] < x[i-1]: dec j swap x[i-1], x[j] result = true


context:
space:
mode: