Carp/core/StaticArray.carp

(doc StaticArray "is a data type for static, immutable arrays. They are
stack-allocated. For a more flexible, heap-allocated version, you might want to look at the [`Array`](./Array.html) module.")
(defmodule StaticArray

  (doc map! "Maps a function over the static array `xs`, mutating it in place. The difference to Array.endo-map (which does the same thing internally) is that this function takes a ref (since you can never have static arrays as values) and that it returns ().")
  (defn map! [xs f]
    (for [i 0 (StaticArray.length xs)]
      (StaticArray.aset! xs i (~f (StaticArray.unsafe-nth xs i)))))

  (doc reverse! "Reverse array in place.")
  (defn reverse! [a]
    (let-do [i 0
             j (Int.dec (length a))]
      (while (Int.< i j)
        (let-do [tmp @(unsafe-nth a i)]
          (aset! a i @(unsafe-nth a j))
          (set! i (Int.inc i))
          (aset! a j tmp)
          (set! j (Int.dec j))))))

  (defndynamic foreach-internal [var xs expr]
    (let [xsym (gensym-with 'xs)
          len (gensym-with 'len)
          i (gensym-with 'i)]
      `(let [%xsym %xs
             %len (StaticArray.length %xsym)]
         (for [%i 0 %len]
           (let [%var (StaticArray.unsafe-nth %xsym %i)]
             %expr)))))

  (defmacro foreach [binding expr]
    (StaticArray.foreach-internal (car binding) (cadr binding) expr))

  (defn reduce [f x xs]
    (let [total x]
      (do
        (for [i 0 (StaticArray.length xs)]
          (set! total (~f total (StaticArray.unsafe-nth xs i))))
        total)))

    (doc scan! "Scans and replaces the array in-place, using a binary function.

For example, give `(def numbers [1 1 1])`, a `scan!` using `Int.+` will mutate `numbers` to be `[1 2 3]`.")
  (defn scan! [f xs]
    (let [n (StaticArray.length xs)]
      (for [i 1 n]
        (StaticArray.aset! xs i (~f @(unsafe-nth xs (dec i)) @(unsafe-nth xs i))))))

  (doc = "compares two static arrays.")
  (defn = [a b]
    (if (/= (StaticArray.length a) (StaticArray.length b))
      false
      (let-do [eq true]
        (for [i 0 (StaticArray.length a)]
          (when (/= (StaticArray.unsafe-nth a i) (StaticArray.unsafe-nth b i))
            (do
              (set! eq false)
              (break))))
        eq)))
  (implements = StaticArray.=)

  (doc empty? "checks whether the array `a` is empty.")
  (defn empty? [a]
    (= (StaticArray.length a) 0))
  (implements empty? StaticArray.empty?)

  (doc any? "checks whether any of the elements in `a` match the function `f`.")
  (defn any? [f a]
    (let-do [res false]
      (for [i 0 (length a)]
        (when (~f (unsafe-nth a i))
          (do
            (set! res true)
            (break))))
      res))

  (doc all? "checks whether all of the elements in `a` match the function `f`.")
  (defn all? [f a]
    (let-do [res true]
      (for [i 0 (length a)]
        (when (not (~f (unsafe-nth a i)))
          (do
            (set! res false)
            (break))))
      res))

  (doc find "finds an element in `a` that matches the function `f` and wraps it in a `Just`.

If it doesn’t find an element, `Nothing` will be returned.")
  (defn find [f a]
    (let-do [res (Maybe.Nothing)]
      (for [i 0 (length a)]
        (when (~f (unsafe-nth a i))
          (do
            (set! res (Maybe.Just @(unsafe-nth a i)))
            (break))))
      res))

  (doc find-index "finds the index of the first element in `a` that matches the function `f` and wraps it in a `Just`.

If it doesn’t find an index, `Nothing` will be returned.")
  (defn find-index [f a]
    (let-do [ret (Maybe.Nothing)]
      (for [i 0 (length a)]
        (when (~f (unsafe-nth a i))
          (do
            (set! ret (Maybe.Just i))
            (break))))
      ret))

  (doc unsafe-first "takes the first element of an array.

Generates a runtime error if the array is empty.")
  (defn unsafe-first [a]
    @(unsafe-nth a 0))

  (doc first "takes the first element of an array and returns a `Just`.

Returns `Nothing` if the array is empty.")
  (defn first [a]
    (if (empty? a)
      (Maybe.Nothing)
      (Maybe.Just @(unsafe-nth a 0))))

  (doc unsafe-last "takes the last element of an array.

Generates a runtime error if the array is empty.")
  (defn unsafe-last [a]
    @(unsafe-nth a (Int.dec (length a))))


  (doc last "takes the last element of an array and returns a `Just`.

Returns `Nothing` if the array is empty.")
  (defn last [a]
    (if (empty? a)
      (Maybe.Nothing)
      (Maybe.Just @(unsafe-nth a (Int.dec (length a))))))

  (doc maximum "gets the maximum in an array (elements must support `<`) and wraps it in a `Just`.

If the array is empty, it returns `Nothing`.")
  (defn maximum [xs]
    (if (empty? xs)
      (Maybe.Nothing)
      (let-do [result (unsafe-nth xs 0)
               n (length xs)]
        (for [i 1 n]
          (let [x (unsafe-nth xs i)]
            (when (< result x)
              (set! result x))))
        (Maybe.Just @result))))

  (doc minimum "gets the minimum in an array (elements must support `>`) and wraps it in a `Just`.

If the array is empty, returns `Nothing`")
  (defn minimum [xs]
    (if (empty? xs)
      (Maybe.Nothing)
      (let-do [result (unsafe-nth xs 0)
               n (length xs)]
        (for [i 1 n]
          (let [x (unsafe-nth xs i)]
            (when (> result x)
              (set! result x))))
        (Maybe.Just @result))))

  (doc sum "sums an array (elements must support `+` and `zero`).")
  (defn sum [xs]
    (reduce &(fn [x y] (+ x @y)) (zero) xs))

  (doc index-of "gets the index of element `e` in an array and wraps it on a `Just`.

  If the element is not found, returns `Nothing`")
  (defn index-of [a e]
    (let-do [idx (Maybe.Nothing)]
      (for [i 0 (length a)]
        (when (= (unsafe-nth a i) e)
          (do
            (set! idx (Maybe.Just i))
            (break))))
      idx))

  (doc element-count "counts the occurrences of element `e` in an array.")
  (defn element-count [a e]
    (let-do [c 0]
      (for [i 0 (length a)]
        (when (= e (unsafe-nth a i)) (set! c (Int.inc c))))
      c))

  (doc predicate-count "counts the number of elements satisfying the predicate function `pred` in an array.")
  (defn predicate-count [a pred]
    (let-do [c 0]
      (for [i 0 (length a)]
        (when (~pred (unsafe-nth a i))
          (set! c (Int.inc c))))
      c))

    (doc unsafe-nth-value "returns the value at index `i` of a static array `a` (just like [unsafe-nth](#unsafe-nth)) but does not take its reference, and does *not* copy the value. Should only be used for optimizations and when you know what you're doing, circumvents the borrow checker!")
  (deftemplate unsafe-nth-value (Fn [(Ref (StaticArray a)) Int] a)
    "$a $NAME(Array *a, int i)"
    "$DECL { return (($a*)a->data)[i]; }")

  (doc aupdate! "transmutes (i.e. updates) the element at index `i` of an array `a` using the function `f` in place.")
  (defn aupdate! [a i f]
    (aset-uninitialized! a i (~f (unsafe-nth-value a i))))

  (doc swap! "swaps the indices `i` and `j` of an array `a` in place.")
  (defn swap! [a i j]
    (let-do [x @(unsafe-nth a i)
             y @(unsafe-nth a j)]
      (aset! a i y)
      (aset! a j x)))

  (doc nth "gets a reference to the `n`th element from an array `arr` wrapped on a `Maybe`.

  If the `index` is out of bounds, return `Maybe.Nothing`")
  (defn nth [xs index]
   (if (and (>= index 0) (< index (length xs)))
     (Maybe.Just @(unsafe-nth xs index)) ; the copy will go away with lifetimes
     (Maybe.Nothing)))

  (doc contains? "checks wether an element exists in the array.")
  (defn contains? [arr el]
    (let-do [result false]
      (for [i 0 (length arr)]
        (when (= el (unsafe-nth arr i))
          (do
            (set! result true)
            (break))))
      result))

  (doc unsafe-raw "returns an array a as a raw pointer—useful for interacting with C.")
  (deftemplate unsafe-raw (Fn [(Ref (StaticArray t))] (Ptr t))
    "$t* $NAME(Array *a)"
    "$DECL { return a->data; }"))