zpvector.zp

(define (vector:head v) "gets vector head"
  (v 0))

(define (vector:map f v) "map f over vector v"
  (let loop ((i 0)
             (len (vector:length v))
             (new (vector)))
    (if (> len i)
      (loop (add1 i) len (+= new (f (v i))))
      new)))

(define (vector:mapcat f v) "maps f over and concats a vector v"
  (apply ++ (vector:map f v)))

(define (vector:reduce f acc . v) "reduces with f over vector v; using accumulator acc"
  (if (null? v)
    (vector:reduce f (vector:head acc) (vector:tail acc))
    (let ((v (car v)))
      (let loop ((i 0)
                 (len (vector:length v))
                 (acc acc))
        (if (> len i)
          (loop (add1 i) len (f acc (v i)))
          acc)))))

(define (vector:filter f v) "filters with f over vector v"
  (let loop ((i 0)
             (len (vector:length v))
             (new {}))
    (if (> len i)
      (if (f (v i))
        (loop (add1 i) len (++ new (v i)))
        (loop (add1 i) len new))
      new)))

(define (vector:drop-while f v) "drops elements from v as long as f matches"
  (if (f (vector:head v))
    (vector:drop-while f (vector:tail v))
    (vector:tail v)))

(define (vector:take-while f v) "takes elements from v as long as f matches"
  (define (internal f v acc)
    (if (f (vector:head v))
      (internal f (vector:tail v) (++ acc (vector:head v)))
      acc))
  (internal f v []))

(define (vector->byte-vector v) "converts vector into bytevector"
  (vector:reduce (lambda (acc x) (++ acc (->bytes x))) b{} v))

(define (vector:tail v) "gets vector tail"
  (vector:subvector v 1 (sub1 (vector:length v))))

(define (vector:empty? v) "is vector empty?"
  (eq? v #()))

(define (vector:matches? pred? v) "check whether there is an element in v that matches the predicate pred?"
  (cond
    ((vector:empty? v) #f)
    ((pred? (vector:head v)) #t)
    (else (vector:matches? pred? (vector:tail v)))))

(define (vector:binary-search v el) "performs binary search on a vector (must be sorted)"
  (define (internal v el low high)
    (if (< high low)
      (- (add1 low))
      (let* ((mid (/ (+ low high) 2))
             (midv (v mid)))
        (cond
          ((< midv el) (internal v el (add1 mid) high))
          ((> midv el) (internal v el low (sub1 high)))
          (else mid)))))
  (internal v el 0 (sub1 (length v))))

(define (vector:index v el) "get index of el in l; otherwise get -1"
  (define (internal v el c)
    (cond 
      ((vector:empty? v) -1)
      ((eq? (vector:head v) el) c)
      (else (internal (vector:tail v) el (add1 c)))))
  (internal v el 0))

(define (vector:after v el) "returns subvector of v after first occurrence of element el"
  (vector:subvector v (+ (vector:index v el) 1) (sub1 (vector:length v))))

(define (vector:count v el) "returns number of occurences of el in v"
  (define (internal v el c)
    (cond
      ((vector:empty? v) c)
      ((eq? (vector:head v) el) (internal (vector:tail v) el (+ c 1)))
      (else (internal (vector:tail v) el c))))
  (internal v el 0))

(define (vector:min v) "minimum in vector"
  (define (internal v m)
    (cond 
      ((vector:empty? v) m)
      ((< (vector:head v) m) (internal (vector:tail v) (vector:head v)))
      (else (internal (vector:tail v) m))))
  (internal (vector:tail v) (vector:head v)))

(define (vector:max v) "maximum in vector"
  (define (internal v m)
    (cond 
      ((vector:empty? v) m)
      ((> (vector:head v) m) (internal (vector:tail v) (vector:head v)))
      (else (internal (vector:tail v) m))))
  (internal (vector:tail v) (vector:head v)))

(define (vector:last v) "get last element of v"
  (if (vector:empty? v)
    (nil)
    (vector:ref v (- (vector:length v) 1))))

(define (vector:in? v el) "returns boolean signifying whether element is in vector"
  (<= 0 (vector:index v el)))

(define (vector:indexed-tail v k) "get tail of a list starting at index"
    (if (zero? k)
      v
      (vector:indexed-tail (vector:tail v) (- k 1))))

(define vector:drop (flip vector:indexed-tail))

(define (vector:swap v i j) "swap elements in v at positions i and j"
  (let ((temp (vector:ref v i)))
    (vector:set! v i (vector:ref v j))
    (vector:set! v j temp)))

(define (vector:shuffle v) "shuffle v's order"
  (do ((n (length v) (- n 1))) ((zero? n) v)
    (let* ((r (randint n)) (t (vector:ref v r)))
      (vector:set! v r (vector:ref v (- n 1)))
      (vector:set! v (- n 1) t))))

(define (byte-vector:last b) "get last element from byte-vector b"
  (byte-vector:ref x (- (byte-vector:length x) 1)))

(define (byte-vector:map f b) "map f over bytevector b"
  (let loop ((i 0)
             (len (byte-vector:length b))
             (new (byte-vector)))
    (if (> len i)
      (loop (add1 i) len (+= new (f (byte-vector:ref b i))))
      new)))

(define (byte-vector:reduce f acc . b) "map f over bytevector b using accumulator acc"
  (if (null? b)
    (byte-vector:reduce f (byte-vector:head acc) (byte-vector:tail acc))
    (let ((b (car b)))
      (let loop ((i 0)
                 (len (byte-vector:length b))
                 (acc acc))
        (if (> len i)
          (loop (add1 i) len (f acc (byte-vector:ref b i)))
          acc)))))

(define (byte-vector:filter f b) "filters with f over bytevector b"
  (let loop ((i 0)
             (len (byte-vector:length b))
             (new b{}))
    (if (> len i)
      (if (f (b i))
        (loop (add1 i) len (++ new (b i)))
        (loop (add1 i) len new))
      new)))

(define (byte-vector->list b) "converts bytevector into list"
  (byte-vector:reduce (lambda (acc x) (++ acc x)) [] b))

(define (byte-vector->vector b) "converts bytevector into vector"
  (byte-vector:reduce (lambda (acc x) (++ acc x)) {} b))

(define (byte-vector:head b) "gets first element of bytevector"
  (byte-vector:ref b 0))

(define (byte-vector:tail b) "gets rest of bytevector"
  (byte-vector:subvector b 1 (length b)))

(define (byte-vector:empty? b) "is bytevector empty?"
  (eq? (byte-vector:length b) 0))

(define (byte-vector:mapcat f b) "maps f over and concats a byte-vector b"
  (apply ++ (byte-vector:map f b)))

(define (byte-vector:binary-search b el) "performs binary search on a byte-vector (must be sorted)"
  (define (internal b el low high)
    (if (< high low)
      (- (add1 low))
      (let* ((mid (/ (+ low high) 2))
             (midv (b mid)))
        (cond
          ((< midv el) (internal b el (add1 mid) high))
          ((> midv el) (internal b el low (sub1 high)))
          (else mid)))))
  (internal b el 0 (sub1 (length b))))

(define (byte-vector:index b el) "get index of el in l; otherwise get -1"
  (define (internal b el c)
    (cond 
      ((byte-vector:empty? b) -1)
      ((eq? (byte-vector:head b) el) c)
      (else (internal (byte-vector:tail b) el (add1 c)))))
  (internal b el 0))

(define (byte-vector:in? b el) "returns boolean signifying whether element is in byte-vector"
  (<= 0 (byte-vector:index b el)))

(define-syntax vector:update!
  (syntax-rules ()
    ((_ v i f) (vector:set! v i (f (v i))))))

(define (vector:set v i x) "sets vector non-destructively"
  (vector:set! v i x))

(define (vector:update v i f) "update vector non-destructively"
  (vector:update! v i f))

(define-syntax byte-vector:update!
  (syntax-rules ()
    ((_ v i f) (byte-vector:set! v i (f (v i))))))

(define (integer->byte-vector n)
  (cond
   ((= n 0) b{0})
   ((negative? n) (error "can't convert a negative integer to bytevector" n))
   (else
    (let lp ((n n) (res '()))
      (if (= n 0)
          (let* ((len (length res))
                 (bv (make-byte-vector len 0)))
            (do ((i 0 (+ i 1))
                 (ls res (cdr ls)))
                ((= i len) bv)
              (byte-vector:set! bv i (make-small (car ls)))))
          (lp (quotient n 256) (cons (remainder n 256) res)))))))

(define (byte-vector->integer bv)
  (let ((len (length bv)))
    (let lp ((i 0) (n 0))
      (if (>= i len)
          n
          (lp (add1 i)
              (+ (arithmetic-shift n 8)
                 (byte-vector:ref bv i)))))))