| 1 |
;;; |
| 2 |
;;; data.ideque - immutable double-ended queue |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2015-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
;; This implements banker's deque |
| 35 |
;; as described in Chris Okasaki's Purely Functional Data Structures. |
| 36 |
;; It provides amortized O(1) operation. |
| 37 |
;; The API is adapted to SRFI-134 |
| 38 |
|
| 39 |
(define-module data.ideque |
| 40 |
(use gauche.record) |
| 41 |
(use gauche.generator) |
| 42 |
(use gauche.lazy) |
| 43 |
(use util.match) |
| 44 |
(use scheme.list) |
| 45 |
(export <ideque> |
| 46 |
make-ideque ideque ideque? ideque-empty? ideque= |
| 47 |
ideque-unfold ideque-unfold-right ideque-tabulate |
| 48 |
list->ideque ideque->list ideque-reverse |
| 49 |
generator->ideque ideque->generator |
| 50 |
ideque-ref |
| 51 |
ideque-front ideque-add-front ideque-remove-front |
| 52 |
ideque-back ideque-add-back ideque-remove-back |
| 53 |
ideque-take ideque-take-right ideque-drop ideque-drop-right |
| 54 |
ideque-split-at |
| 55 |
ideque-length ideque-append ideque-count ideque-zip |
| 56 |
ideque-map ideque-for-each ideque-for-each-right |
| 57 |
ideque-fold ideque-fold-right |
| 58 |
ideque-filter-map ideque-append-map |
| 59 |
ideque-filter ideque-remove ideque-partition |
| 60 |
ideque-find ideque-find-right |
| 61 |
ideque-take-while ideque-take-while-right |
| 62 |
ideque-drop-while ideque-drop-while-right |
| 63 |
ideque-span ideque-break |
| 64 |
ideque-any ideque-every)) |
| 65 |
(select-module data.ideque) |
| 66 |
|
| 67 |
(define-record-type <ideque> %make-dq ideque? |
| 68 |
(lenf dq-lenf) ; length of front chain |
| 69 |
(f dq-f) ; front chain |
| 70 |
(lenr dq-lenr) ; length of rear chain |
| 71 |
(r dq-r)) ; rear chain |
| 72 |
|
| 73 |
;; We use a singleton for empty deque |
| 74 |
(define-constant *empty* (%make-dq 0 '() 0 '())) |
| 75 |
|
| 76 |
;; |
| 77 |
;; Constructors |
| 78 |
;; |
| 79 |
|
| 80 |
;; API |
| 81 |
(define (make-ideque n :optional (init #f)) |
| 82 |
(let* ([lenf (quotient n 2)] |
| 83 |
[lenr (- n lenf)]) |
| 84 |
(%make-dq lenf (make-list lenf init) |
| 85 |
lenr (make-list lenr init)))) |
| 86 |
|
| 87 |
;; API [SRFI-134] |
| 88 |
(define (ideque . args) (list->ideque args)) |
| 89 |
|
| 90 |
;; API [SRFI-134] |
| 91 |
(define (ideque-unfold p f g seed) |
| 92 |
(list->ideque (unfold p f g seed))) |
| 93 |
|
| 94 |
;; API [SRFI-134] |
| 95 |
(define (ideque-unfold-right p f g seed) |
| 96 |
(list->ideque (unfold-right p f g seed))) |
| 97 |
;; alternatively: |
| 98 |
;; (ideque-reverse (list->ideque (unfold p f g seed))) |
| 99 |
|
| 100 |
;; API [SRFI-134] |
| 101 |
(define (ideque-tabulate size init) |
| 102 |
(let ([lenf (quotient size 2)] |
| 103 |
[lenr (quotient (+ size 1) 2)]) |
| 104 |
(%make-dq lenf (list-tabulate lenf init) |
| 105 |
lenr (unfold (cut = <> lenr) |
| 106 |
(^n (init (- size n 1))) |
| 107 |
(cut + <> 1) |
| 108 |
0)))) |
| 109 |
|
| 110 |
(define-constant C 3) |
| 111 |
|
| 112 |
(define (check lenf f lenr r) |
| 113 |
(cond [(> lenf (+ (* lenr C) 1)) |
| 114 |
(let* ([i (quotient (+ lenf lenr) 2)] |
| 115 |
[j (- (+ lenf lenr) i)] |
| 116 |
[f. (take f i)] |
| 117 |
[r. (lappend r (reverse (drop f i)))]) |
| 118 |
(%make-dq i f. j r.))] |
| 119 |
[(> lenr (+ (* lenf C) 1)) |
| 120 |
(let* ([j (quotient (+ lenf lenr) 2)] |
| 121 |
[i (- (+ lenf lenr) j)] |
| 122 |
[r. (take r j)] |
| 123 |
[f. (lappend f (reverse (drop r j)))]) |
| 124 |
(%make-dq i f. j r.))] |
| 125 |
[else (%make-dq lenf f lenr r)])) |
| 126 |
|
| 127 |
;; |
| 128 |
;; Basic operations |
| 129 |
;; |
| 130 |
|
| 131 |
;; API [SRFI-134] |
| 132 |
(define (ideque-empty? dq) |
| 133 |
(and (zero? (dq-lenf dq)) |
| 134 |
(zero? (dq-lenr dq)))) |
| 135 |
|
| 136 |
;; API [SRFI-134] |
| 137 |
(define (ideque-add-front dq x) |
| 138 |
(check (+ (dq-lenf dq) 1) (cons x (dq-f dq)) (dq-lenr dq) (dq-r dq))) |
| 139 |
|
| 140 |
;; API [SRFI-134] |
| 141 |
(define (ideque-front dq) |
| 142 |
(if (zero? (dq-lenf dq)) |
| 143 |
(if (zero? (dq-lenr dq)) |
| 144 |
(error "Empty deque:" dq) |
| 145 |
(car (dq-r dq))) |
| 146 |
(car (dq-f dq)))) |
| 147 |
|
| 148 |
;; API [SRFI-134] |
| 149 |
(define (ideque-remove-front dq) |
| 150 |
(if (zero? (dq-lenf dq)) |
| 151 |
(if (zero? (dq-lenr dq)) |
| 152 |
(error "Empty deque:" dq) |
| 153 |
*empty*) |
| 154 |
(check (- (dq-lenf dq) 1) (cdr (dq-f dq)) (dq-lenr dq) (dq-r dq)))) |
| 155 |
|
| 156 |
;; API [SRFI-134] |
| 157 |
(define (ideque-add-back dq x) |
| 158 |
(check (dq-lenf dq) (dq-f dq) (+ (dq-lenr dq) 1) (cons x (dq-r dq)))) |
| 159 |
|
| 160 |
;; API [SRFI-134] |
| 161 |
(define (ideque-back dq) |
| 162 |
(if (zero? (dq-lenr dq)) |
| 163 |
(if (zero? (dq-lenf dq)) |
| 164 |
(error "Empty deque:" dq) |
| 165 |
(car (dq-f dq))) |
| 166 |
(car (dq-r dq)))) |
| 167 |
|
| 168 |
;; API [SRFI-134] |
| 169 |
(define (ideque-remove-back dq) |
| 170 |
(if (zero? (dq-lenr dq)) |
| 171 |
(if (zero? (dq-lenf dq)) |
| 172 |
(error "Empty deque:" dq) |
| 173 |
*empty*) |
| 174 |
(check (dq-lenf dq) (dq-f dq) (- (dq-lenr dq) 1) (cdr (dq-r dq))))) |
| 175 |
|
| 176 |
;; API [SRFI-134] |
| 177 |
(define (ideque-reverse dq) |
| 178 |
(if (ideque-empty? dq) |
| 179 |
*empty* |
| 180 |
(%make-dq (dq-lenr dq) (dq-r dq) (dq-lenf dq) (dq-f dq)))) |
| 181 |
|
| 182 |
;; |
| 183 |
;; Other operations |
| 184 |
;; |
| 185 |
|
| 186 |
;; API [SRFI-134] |
| 187 |
(define ideque= |
| 188 |
(case-lambda |
| 189 |
[(elt=) #t] |
| 190 |
[(elt= ideque) (assume-type ideque <ideque>) #t] |
| 191 |
[(elt= dq1 dq2) |
| 192 |
;; we optimize two-arg case |
| 193 |
(assume-type dq1 <ideque>) |
| 194 |
(assume-type dq2 <ideque>) |
| 195 |
(or (eq? dq1 dq2) |
| 196 |
(let ([len1 (+ (dq-lenf dq1) (dq-lenr dq1))] |
| 197 |
[len2 (+ (dq-lenf dq2) (dq-lenr dq2))]) |
| 198 |
(and (= len1 len2) |
| 199 |
(receive (x t1 t2) (list-prefix= elt= (dq-f dq1) (dq-f dq2)) |
| 200 |
(and x |
| 201 |
(receive (y r1 r2) (list-prefix= elt= (dq-r dq1) (dq-r dq2)) |
| 202 |
(and y |
| 203 |
(if (null? t1) |
| 204 |
(list= elt= t2 (reverse r1)) |
| 205 |
(list= elt= t1 (reverse r2))))))))))] |
| 206 |
[(elt= . dqs) |
| 207 |
(apply list= elt= (map ideque->list dqs))])) |
| 208 |
|
| 209 |
;; Compare two lists up to whichever shorter one. |
| 210 |
;; Returns the compare result and the tails of uncompared lists. |
| 211 |
(define (list-prefix= elt= a b) |
| 212 |
(let loop ([a a] [b b]) |
| 213 |
(cond [(or (null? a) (null? b)) (values #t a b)] |
| 214 |
[(elt= (car a) (car b)) (loop (cdr a) (cdr b))] |
| 215 |
[else (values #f a b)]))) |
| 216 |
|
| 217 |
;; API [SRFI-134] |
| 218 |
(define (ideque-ref dq n) |
| 219 |
(let1 len (+ (dq-lenf dq) (dq-lenr dq)) |
| 220 |
(cond [(or (< n 0) (>= n len)) (error "Index out of range:" n)] |
| 221 |
[(< n (dq-lenf dq)) (list-ref (dq-f dq) n)] |
| 222 |
[else (list-ref (dq-r dq) (- len n 1))]))) |
| 223 |
|
| 224 |
(define (%ideque-take dq n) ; n is within the range |
| 225 |
(match-let1 ($ <ideque> lenf f lenr r) dq |
| 226 |
(if (<= n lenf) |
| 227 |
(check n (take f n) 0 '()) |
| 228 |
(let1 lenr. (- n lenf) |
| 229 |
(check lenf f lenr. (take-right r lenr.)))))) |
| 230 |
|
| 231 |
(define (%ideque-drop dq n) ; n is within the range |
| 232 |
(match-let1 ($ <ideque> lenf f lenr r) dq |
| 233 |
(if (<= n lenf) |
| 234 |
(check (- lenf n) (drop f n) lenr r) |
| 235 |
(let1 lenr. (- lenr (- n lenf)) |
| 236 |
(check 0 '() lenr. (take r lenr.)))))) |
| 237 |
|
| 238 |
(define (%check-length dq n) |
| 239 |
(unless (<= 0 n (ideque-length dq)) |
| 240 |
(error "argument is out of range:" n))) |
| 241 |
|
| 242 |
;; API [SRFI-134] |
| 243 |
(define (ideque-take dq n) |
| 244 |
(%check-length dq n) |
| 245 |
(%ideque-take dq n)) |
| 246 |
|
| 247 |
;; API [SRFI-134] |
| 248 |
(define (ideque-take-right dq n) |
| 249 |
(%check-length dq n) |
| 250 |
(%ideque-drop dq (- (ideque-length dq) n))) |
| 251 |
|
| 252 |
;; API [SRFI-134] |
| 253 |
(define (ideque-drop dq n) |
| 254 |
(%check-length dq n) |
| 255 |
(%ideque-drop dq n)) |
| 256 |
|
| 257 |
;; API [SRFI-134] |
| 258 |
(define (ideque-drop-right dq n) |
| 259 |
(%check-length dq n) |
| 260 |
(%ideque-take dq (- (ideque-length dq) n))) |
| 261 |
|
| 262 |
;; API [SRFI-134] |
| 263 |
(define (ideque-split-at dq n) |
| 264 |
(%check-length dq n) |
| 265 |
(values (%ideque-take dq n) |
| 266 |
(%ideque-drop dq n))) |
| 267 |
|
| 268 |
;; API [SRFI-134] |
| 269 |
(define (ideque-length dq) (+ (dq-lenf dq) (dq-lenr dq))) |
| 270 |
|
| 271 |
;; API [SRFI-134] |
| 272 |
(define (ideque-append . dqs) |
| 273 |
;; We could save some list copying by carefully split dqs into front and |
| 274 |
;; read group and append separately, but for now we don't bother... |
| 275 |
(list->ideque (concatenate (map ideque->list dqs)))) |
| 276 |
|
| 277 |
;; API [SRFI-134] |
| 278 |
(define ideque-count |
| 279 |
(case-lambda |
| 280 |
[(pred dq) (+ (count pred (dq-f dq)) (count pred (dq-r dq)))] |
| 281 |
[(pred . dqs) (apply count pred (map ideque->list dqs))])) |
| 282 |
|
| 283 |
;; API [SRFI-134] |
| 284 |
(define (ideque-zip dq . dqs) |
| 285 |
(apply ideque-map list dq dqs)) |
| 286 |
|
| 287 |
;; API [SRFI-134] |
| 288 |
(define ideque-map |
| 289 |
(case-lambda |
| 290 |
[(proc dq) (%make-dq (dq-lenf dq) (map proc (dq-f dq)) |
| 291 |
(dq-lenr dq) (map proc (dq-r dq)))] |
| 292 |
[(proc . dqs) (list->ideque (apply map proc (map ideque->list dqs)))])) |
| 293 |
|
| 294 |
;; API [SRFI-134] |
| 295 |
(define ideque-filter-map |
| 296 |
(case-lambda |
| 297 |
[(proc dq) (let ([f (filter-map proc (dq-f dq))] |
| 298 |
[r (filter-map proc (dq-r dq))]) |
| 299 |
(check (length f) f (length r) r))] |
| 300 |
[(proc . dqs) |
| 301 |
(list->ideque (apply filter-map proc (map ideque->list dqs)))])) |
| 302 |
|
| 303 |
;; API [SRFI-134] |
| 304 |
(define ideque-for-each |
| 305 |
(case-lambda |
| 306 |
[(proc dq) (for-each proc (dq-f dq)) (for-each proc (reverse (dq-r dq)))] |
| 307 |
[(proc . dqs) (apply for-each proc (map ideque->list dqs))])) |
| 308 |
|
| 309 |
;; API [SRFI-134] |
| 310 |
(define ideque-for-each-right |
| 311 |
(case-lambda |
| 312 |
[(proc dq) (for-each proc (dq-r dq)) (for-each proc (reverse (dq-f dq)))] |
| 313 |
[(proc . dqs) |
| 314 |
(apply for-each proc (map (lambda (dq) |
| 315 |
(ideque->list (ideque-reverse dq))) |
| 316 |
dqs))])) |
| 317 |
|
| 318 |
;; API [SRFI-134] |
| 319 |
(define ideque-fold |
| 320 |
(case-lambda |
| 321 |
[(proc knil dq) (fold proc (fold proc knil (dq-f dq)) (reverse (dq-r dq)))] |
| 322 |
[(proc knil . dqs) (apply fold proc knil (map ideque->list dqs))])) |
| 323 |
|
| 324 |
;; API [SRFI-134] |
| 325 |
(define ideque-fold-right |
| 326 |
(case-lambda |
| 327 |
[(proc knil dq) |
| 328 |
(fold-right proc (fold-right proc knil (reverse (dq-r dq))) (dq-f dq))] |
| 329 |
[(proc knil . dqs) |
| 330 |
(apply fold-right proc knil (map ideque->list dqs))])) |
| 331 |
|
| 332 |
;; API [SRFI-134] |
| 333 |
(define (ideque-append-map proc . dqs) |
| 334 |
;; can be cleverer, but for now... |
| 335 |
(list->ideque (apply append-map proc (map ideque->list dqs)))) |
| 336 |
|
| 337 |
(define (%ideque-filter-remove op pred dq) |
| 338 |
(let ([f (op pred (dq-f dq))] |
| 339 |
[r (op pred (dq-r dq))]) |
| 340 |
(check (length f) f (length r) r))) |
| 341 |
|
| 342 |
;; API [SRFI-134] |
| 343 |
(define (ideque-filter pred dq) (%ideque-filter-remove filter pred dq)) |
| 344 |
(define (ideque-remove pred dq) (%ideque-filter-remove remove pred dq)) |
| 345 |
|
| 346 |
;; API [SRFI-134] |
| 347 |
(define (ideque-partition pred dq) |
| 348 |
(receive (f1 f2) (partition pred (dq-f dq)) |
| 349 |
(receive (r1 r2) (partition pred (dq-r dq)) |
| 350 |
(values (check (length f1) f1 (length r1) r1) |
| 351 |
(check (length f2) f2 (length r2) r2))))) |
| 352 |
|
| 353 |
(define *not-found* (cons #f #f)) ; unique value |
| 354 |
|
| 355 |
(define (%search pred seq1 seq2 failure) |
| 356 |
;; we could write seek as CPS, but we employ *not-found* instead to avoid |
| 357 |
;; closure allocation |
| 358 |
(define (seek pred s) |
| 359 |
(cond [(null? s) *not-found*] |
| 360 |
[(pred (car s)) (car s)] |
| 361 |
[else (seek pred (cdr s))])) |
| 362 |
(let1 r (seek pred seq1) |
| 363 |
(if (not (eq? r *not-found*)) |
| 364 |
r |
| 365 |
(let1 r (seek pred (reverse seq2)) |
| 366 |
(if (not (eq? r *not-found*)) |
| 367 |
r |
| 368 |
(failure)))))) |
| 369 |
|
| 370 |
;; API [SRFI-134] |
| 371 |
(define (ideque-find pred dq :optional (failure (^[] #f))) |
| 372 |
(%search pred (dq-f dq) (dq-r dq) failure)) |
| 373 |
|
| 374 |
;; API [SRFI-134] |
| 375 |
(define (ideque-find-right pred dq :optional (failure (^[] #f))) |
| 376 |
(%search pred (dq-r dq) (dq-f dq) failure)) |
| 377 |
|
| 378 |
;; API [SRFI-134] |
| 379 |
(define (ideque-take-while pred dq) |
| 380 |
(receive (hd tl) (span pred (dq-f dq)) |
| 381 |
(if (null? tl) |
| 382 |
(receive (hd. tl.) (span pred (reverse (dq-r dq))) |
| 383 |
(check (dq-lenf dq) (dq-f dq) (length hd.) (reverse hd.))) |
| 384 |
(check (length hd) hd 0 '())))) |
| 385 |
|
| 386 |
;; API [SRFI-134] |
| 387 |
(define (ideque-take-while-right pred dq) |
| 388 |
(ideque-reverse (ideque-take-while pred (ideque-reverse dq)))) |
| 389 |
|
| 390 |
;; API [SRFI-134] |
| 391 |
(define (ideque-drop-while pred dq) |
| 392 |
(receive (hd tl) (span pred (dq-f dq)) |
| 393 |
(if (null? tl) |
| 394 |
(receive (hd. tl.) (span pred (reverse (dq-r dq))) |
| 395 |
(check (length tl.) tl. 0 '())) |
| 396 |
(check (length tl) tl (dq-lenr dq) (dq-r dq))))) |
| 397 |
|
| 398 |
;; API [SRFI-134] |
| 399 |
(define (ideque-drop-while-right pred dq) |
| 400 |
(ideque-reverse (ideque-drop-while pred (ideque-reverse dq)))) |
| 401 |
|
| 402 |
(define (%idq-span-break op pred dq) |
| 403 |
(receive (head tail) (op pred (dq-f dq)) |
| 404 |
(if (null? tail) |
| 405 |
(receive (head. tail.) (op pred (reverse (dq-r dq))) |
| 406 |
(values (check (length head) head (length head.) (reverse head.)) |
| 407 |
(check (length tail.) tail. 0 '()))) |
| 408 |
(values (check (length head) head 0 '()) |
| 409 |
(check (length tail) tail (dq-lenr dq) (dq-r dq)))))) |
| 410 |
|
| 411 |
;; API [SRFI-134] |
| 412 |
(define (ideque-span pred dq) (%idq-span-break span pred dq)) |
| 413 |
(define (ideque-break pred dq) (%idq-span-break break pred dq)) |
| 414 |
|
| 415 |
;; API [SRFI-134] |
| 416 |
(define ideque-any |
| 417 |
(case-lambda |
| 418 |
[(pred dq) (if (null? (dq-r dq)) |
| 419 |
(any pred (dq-f dq)) |
| 420 |
(or (any pred (dq-f dq)) (any pred (reverse (dq-r dq)))))] |
| 421 |
[(pred . dqs) (apply any pred (map ideque->list dqs))])) |
| 422 |
|
| 423 |
;; API [SRFI-134] |
| 424 |
(define ideque-every |
| 425 |
(case-lambda |
| 426 |
[(pred dq) (if (null? (dq-r dq)) |
| 427 |
(every pred (dq-f dq)) |
| 428 |
(and (every pred (dq-f dq)) (every pred (reverse (dq-r dq)))))] |
| 429 |
[(pred . dqs) (apply every pred (map ideque->list dqs))])) |
| 430 |
|
| 431 |
;; API [SRFI-134] |
| 432 |
(define (ideque->list dq) (append (dq-f dq) (reverse (dq-r dq)))) |
| 433 |
|
| 434 |
;; API [SRFI-134] |
| 435 |
(define (list->ideque lis) (check (length lis) lis 0 '())) |
| 436 |
|
| 437 |
;; API [SRFI-134] |
| 438 |
(define (ideque->generator dq) |
| 439 |
(^[] (if (ideque-empty? dq) |
| 440 |
(eof-object) |
| 441 |
(rlet1 v (ideque-front dq) |
| 442 |
(set! dq (ideque-remove-front dq)))))) |
| 443 |
|
| 444 |
;; API [SRFI-134] |
| 445 |
(define (generator->ideque gen) |
| 446 |
(list->ideque (generator->list gen))) |