<commit_before>#
#
#            Nim's Runtime Library
#        (c) Copyright 2012 <NAME>
#
#    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 fill*[T](a: var openArray[T], first, last: Natural, value: T) =
  ## fills the array ``a[first..last]`` with `value`.
  var x = first
  while x <= last:
    a[x] = value
    inc(x)

proc fill*[T](a: var openArray[T], value: T) =
  ## fills the array `a` with `value`.
  fill(a, 0, a.high, value)

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 count = a.high - a.low + 1
  var step, pos: int
  while count != 0:
    step = count div 2
    pos = result + step
    if cmp(a[pos], key) < 0:
      result = pos + 1
      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 isSorted*[T](a: openarray[T],
                 cmp: proc(x, y: T): int {.closure.},
                 order = SortOrder.Ascending): bool =
  result = true
  for i in 0..<len(a)-1:
    if cmp(a[i],a[i+1]) * order > 0:
      return false

proc product*[T](x: openArray[seq[T]]): seq[seq[T]] =
  ## produces the Cartesian product of the array. Warning: complexity
  ## may explode.
  result = newSeq[seq[T]]()
  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<commit_msg>Added documentation<commit_after>#
#
#            Nim's Runtime Library
#        (c) Copyright 2012 <NAME>
#
#    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 fill*[T](a: var openArray[T], first, last: Natural, value: T) =
  ## fills the array ``a[first..last]`` with `value`.
  var x = first
  while x <= last:
    a[x] = value
    inc(x)

proc fill*[T](a: var openArray[T], value: T) =
  ## fills the array `a` with `value`.
  fill(a, 0, a.high, value)

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 count = a.high - a.low + 1
  var step, pos: int
  while count != 0:
    step = count div 2
    pos = result + step
    if cmp(a[pos], key) < 0:
      result = pos + 1
      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 isSorted*[T](a: openarray[T],
                 cmp: proc(x, y: T): int {.closure.},
                 order = SortOrder.Ascending): bool =
  ## Checks to see whether `a` is already sorted in `order`
  ## using `cmp` for the comparison. Parameters identical
  ## to `sort`
  result = true
  for i in 0..<len(a)-1:
    if cmp(a[i],a[i+1]) * order > 0:
      return false

proc product*[T](x: openArray[seq[T]]): seq[seq[T]] =
  ## produces the Cartesian product of the array. Warning: complexity
  ## may explode.
  result = newSeq[seq[T]]()
  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
{'fraction_non_alphanumeric': 0.16765076627081538, 'fraction_numerical': 0.014064884230080276, 'mean_word_length': 2.569500355197727, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3269845', 'n_tokens_mistral': 5848, 'n_tokens_neox': 5657, 'n_words': 1913}