application/octet-stream
•
3.22 KB
•
106 lines
; Nujel - Copyright (C) 2020-2021 - Benjamin Vincent Schulenburg
; This project uses the MIT license, a copy should be included under /LICENSE
;; Some functions dealing with arrays
[defun array/+= [a i v]
"Add V to the value in A at position I and store the result in A returning A"
[array/set! a i [+ v [array/ref a i]]]]
[defun array/++ [a i]
"Increment position I in A and return A"
[array/+= a i 1]]
[defun array/fill! [a v i]
"Fills array a with value v"
[def len [array/length a]]
[for [i 0 len]
[array/set! a i v]]
a]
[defun array/append [a b]
"Append array A to array B"
[when-not [and [array? a] [array? b]] [throw [list :type-error "array/append expects two arrays as its arguments" #nil [current-lambda]]]]
[def ret [array/allocate [+ [array/length a] [array/length b]]]]
[for [i 0 [array/length a]]
[array/set! ret i [a i]]]
[for [i [array/length a] [array/length ret]]
[array/set! ret i [b [- i [array/length a]]]]]
ret]
[defun array/dup [a]
"Duplicate Array A"
[array/append a #[]]]
[defun array/reduce [arr fun α]
"Reduce an array, [reduce] should be preferred"
[def len [array/length arr]]
[for [i 0 len]
[set! α [fun α [arr i]]]]
α]
[defun array/map [arr fun]
"Map an array, [map] should be preferred"
[def len [array/length arr]]
[for [i 0 len]
[array/set! arr i [fun [arr i]]]]
arr]
[defun array/filter [arr pred]
"Filter an array, [filter] should be preferred"
[def ri 0]
[def len [array/length arr]]
[def ret [array/allocate len]]
[for [ai 0 len]
[when [pred [arr ai]]
[array/set! ret ri [arr ai]]
[++ ri]]]
[array/length! ret ri]]
[defun array/push [arr . val]
"Append all arguments following ARR to ARR"
[for-in [v val]
[array/length! arr [+ 1 [array/length arr]]]
[array/set! arr [- [array/length arr] 1] v]]
arr]
[defun array/swap [arr i j]
[def tmp [arr i]]
[array/set! arr i [arr j]]
[array/set! arr j tmp]]
[defun array/heapify [arr n at]
"bubble up the element from index AT to until the max-heap property is satisfied"
[def top at]
[def looping #t]
[while looping
[def l [+ [<< at 1] 1]]
[def r [+ [<< at 1] 2]]
[when [and [< l n] [> [arr l] [arr top]]]
[set! top l]]
[when [and [< r n] [> [arr r] [arr top]]]
[set! top r]]
[if [== top at]
[set! looping #f]
[do [array/swap arr at top]
[set! at top]]]]
arr]
[defun array/make-heap [arr]
[def l [array/length arr]]
[def l2 [/ l 2]]
[while [>= l2 0]
[array/heapify arr l l2]
[-- l2]]
arr]
[defun array/heap-sort [arr]
[array/make-heap arr]
[def l [array/length arr]]
[while [> l 0]
[-- l]
[array/swap arr 0 l]
[array/heapify arr l 0]]
arr]
[def array/sort array/heap-sort]
