~jojo/Carth

ref: 55fb4f948f1f3797078b584dc60b4f7dd68b37ed Carth/std/array.carth -rw-r--r-- 2.5 KiB
55fb4f94JoJo Check `cast` in Infer instead of Gen 5 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
(import iter)
(import mem)

(define (array/length (Array _ n)) n)

(define: (array/iter (Array ptr len))
    (forall (a) (Fun (Array a) (Iter a)))
  (map (<o deref (<o (ptr/+ ptr) cast))
       (xrange 0 (cast len))))

(define: (array/collect xs) (forall (a) (Fun (Iter a) (Array a)))
  (let ((n (count xs))
        (ptr (: (transmute (id@"GC_malloc" (* (sizeof a) (cast n)))) (Box a))))
    (foldl (fun (v [i x]) (array/insert i x v))
           (Array ptr (cast n))
           (enumerate xs))))

(define: (array/insert i x (Array ptr n))
    (forall (a) (Fun Nat a (Array a) (Array a)))
  (if (>= i n)
      (panic "array/insert after end of array")
    (seq (store x (ptr/+ ptr i))
         (Array ptr n))))

(define (array/lookup i (Array ptr n))
  (if (< i n)
      (Some (deref (ptr/+ ptr i)))
    None))

(define array/lookup! (<oo unwrap! array/lookup))

;;? Returns index of the first occurence of the element in the array, if it *is* an element
(define: (array/find eq? x xs)
    (forall (a) (Fun (Fun a a Bool) a (Array a) (Maybe Nat)))
  (array/find-by (= x) xs))

;;? Returns the index of the first element that satisfies the predicate
(define (array/find-by p xs)
  (let1 i (count (take-while (<o not p) (array/iter xs)))
    (if (< i (array/length xs))
        (Some i)
      None)))

;;? Positive m: skip from beginning, take from end. Negative m: skip from end, take from
;;? beginning.
(define: (array/skip m (Array ptr n))
    (forall (a) (Fun Int (Array a) (Array a)))
  (if (< m 0)
      (let1 m (min n (cast (neg m)))
        (Array ptr (- n m)))
    (let1 m (min n (cast m))
      (Array (ptr/+ ptr m) (- n m)))))

;;? Positive m: take from beginning, skip from end. Negative m: take from end, skip from
;;? beginning.
(define: (array/take m (Array ptr n))
    (forall (a) (Fun Int (Array a) (Array a)))
  (if (< m 0)
      (let1 m (min n (cast (neg m)))
        (Array (ptr/+ ptr (- n m)) m))
    (Array ptr (min n (cast m)))))

;;? Binary search
;;?
;;? If there are multiple matches, the index of any of them may be returned.
(define: (array/search cmp x ys)
    (forall (a) (Fun (Fun a a Cmp) a (Array a) (Maybe Nat)))
  (define (go start end)
    (if (= start end)
        None
      (let ((i (+ start (/ (- end start) (cast 2))))
            (y (array/lookup! i ys)))
        (match (cmp x y)
          (case Eq (Some i))
          (case Lt (go start i))
          (case Gt (go (inc i) end))))))
  (go (cast 0) (array/length ys)))

(define (array/split i (Array ptr n))
  (if (< i n)
      (Some [(Array ptr i) (Array (ptr/+ ptr i) (- n i))])
    None))