diff options
| author | David Thompson <dthompson2@worcester.edu> | 2020-09-29 11:53:12 -0400 |
|---|---|---|
| committer | David Thompson <dthompson2@worcester.edu> | 2020-09-29 11:53:12 -0400 |
| commit | 04964c4ffcfdab5393aaadc7bcf6d5e8c0ce25e0 (patch) | |
| tree | 35a86ca7946a9bd39f3f51fec1c2b337bc2b0d05 | |
| parent | 3bb57f3982c8f73c5a5a44d2b3ac03e8d7913bf8 (diff) | |
array-list: Add array-list-delete! procedure.
| -rw-r--r-- | chickadee/array-list.scm | 24 |
1 files changed, 24 insertions, 0 deletions
diff --git a/chickadee/array-list.scm b/chickadee/array-list.scm index 5e2174c..6be6da1 100644 --- a/chickadee/array-list.scm +++ b/chickadee/array-list.scm @@ -29,6 +29,7 @@ array-list-set! array-list-push! array-list-pop! + array-list-delete! array-list-clear! array-list-for-each array-list-fold)) @@ -99,6 +100,29 @@ (set-array-list-size! array-list index) item)) +(define* (array-list-delete! array-list item #:key (equal? equal?) fast?) + (let* ((v (array-list-vector array-list)) + (n (array-list-size array-list))) + (let loop ((i 0)) + (when (< i n) + (if (equal? item (vector-ref v i)) + (if fast? + ;; Fast: Swap the last element with the element to be + ;; deleted. Constant time but does not preserve + ;; order. + (let ((last (- n 1))) + (vector-set! v i (vector-ref v last)) + (vector-set! v last #f)) + ;; Slow: Shift all elements to the left. Linear time + ;; but preserves order. + (let shift ((j (+ i 1))) + (if (= j n) + (vector-set! v j #f) + (begin + (vector-set! v (- j 1) (vector-ref v j)) + (shift (+ j 1)))))) + (loop (+ i 1))))))) + (define (array-list-clear! array-list) (let ((size (array-list-size array-list)) (vec (array-list-vector array-list))) |