| 1 |
;;; |
| 2 |
;;; data.range - Range objects |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2021-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 |
;; Superset of SRFI-196 |
| 35 |
|
| 36 |
(define-module data.range |
| 37 |
(use gauche.sequence) |
| 38 |
(use scheme.list) |
| 39 |
(use scheme.division) |
| 40 |
(use srfi.42) |
| 41 |
(export |
| 42 |
;; we expose only the root classes (not the subclasses; they're |
| 43 |
;; internal details) |
| 44 |
<range-meta> <range> |
| 45 |
|
| 46 |
;; Constructors |
| 47 |
range numeric-range iota-range vector-range string-range |
| 48 |
uvector-range bitvector/bool-range bitvector/int-range |
| 49 |
range-append range-reverse |
| 50 |
|
| 51 |
;; Predicates |
| 52 |
range? range=? |
| 53 |
|
| 54 |
;; Accessors |
| 55 |
range-length range-ref range-first range-last |
| 56 |
|
| 57 |
;; Iteration |
| 58 |
range-split-at subrange range-segment |
| 59 |
range-take range-take-right |
| 60 |
range-drop range-drop-right |
| 61 |
range-count range-any |
| 62 |
range-every range-map range-map->list range-map->vector |
| 63 |
range-for-each range-filter-map range-filter-map->list |
| 64 |
range-filter range-filter->list range-remove range-remove->list |
| 65 |
range-fold range-fold-right |
| 66 |
|
| 67 |
;; Searching |
| 68 |
range-index range-index-right |
| 69 |
range-take-while range-take-while-right |
| 70 |
range-drop-while range-drop-while-right |
| 71 |
|
| 72 |
;; Conversion |
| 73 |
range->list range->vector range->string |
| 74 |
vector->range range->generator)) |
| 75 |
(select-module data.range) |
| 76 |
|
| 77 |
;; The classes <range> and <flat-range> are private. Users must use |
| 78 |
;; SRFI-196 API. |
| 79 |
|
| 80 |
;; In Gauche, a range is a sequence whose element may be computed from |
| 81 |
;; the index. |
| 82 |
(define-class <range-meta> (<class>) ()) |
| 83 |
|
| 84 |
(define-class <range> (<sequence>) |
| 85 |
((length :init-keyword :length) |
| 86 |
(indexer :init-keyword :indexer)) ; obj, integer -> element |
| 87 |
:metaclass <range-meta>) |
| 88 |
|
| 89 |
(define-method write-object ((r <range>) port) |
| 90 |
(format port "#<range (~d)>" (~ r'length))) |
| 91 |
|
| 92 |
;; special case, where indexer is simply a indexed reference from a sequence |
| 93 |
;; raw-indexer, storage and offset must be given at initialization; indexer |
| 94 |
;; is computed based on the initialized value. Changing them later will have |
| 95 |
;; no effect. |
| 96 |
(define-class <flat-range> (<range>) |
| 97 |
((raw-indexer :init-keyword :raw-indexer :init-value ref) |
| 98 |
(storage :init-keyword :storage) |
| 99 |
(offset :init-keyword :offset :init-value 0))) |
| 100 |
|
| 101 |
(define-method initialize ((r <flat-range>) initargs) |
| 102 |
(next-method) |
| 103 |
(let ([raw-indexer (~ r'raw-indexer)] |
| 104 |
[offset (~ r'offset)] |
| 105 |
[storage (~ r'storage)] |
| 106 |
[length (~ r'length)]) |
| 107 |
(set! (~ r'indexer) |
| 108 |
(^[o i] |
| 109 |
(assume (and (exact-integer? i) |
| 110 |
(<=:< 0 i length)) |
| 111 |
"Index out of range:" i) |
| 112 |
(raw-indexer storage (+ offset i)))))) |
| 113 |
|
| 114 |
;; appended ranges. |
| 115 |
;; ranges slot contains #((offset . subrange) ...) |
| 116 |
(define (%appended-range-index range i) |
| 117 |
(assume (exact-integer? i) "Range index must be an exact integer:" i) |
| 118 |
(assume (<=:< 0 i (~ range'length)) "Range index out of range:" i) |
| 119 |
(let* ([vec (~ range'ranges)] |
| 120 |
[len (vector-length vec)]) |
| 121 |
(define (call-indexer p i) |
| 122 |
((~ (cdr p)'indexer) (cdr p) (- i (car p)))) |
| 123 |
(let loop ([lo 0] [hi len] [k (ash len -1)]) |
| 124 |
(let1 p (vector-ref vec k) |
| 125 |
(cond [(= k lo) (call-indexer p i)] |
| 126 |
[(> (car p) i) (loop lo k (+ lo (ash (- k lo) -1)))] |
| 127 |
[else (loop k hi (+ k (ash (- hi k) -1)))]))))) |
| 128 |
|
| 129 |
(define-class <appended-range> (<range>) |
| 130 |
((indexer :init-value %appended-range-index) |
| 131 |
(ranges :init-keyword :ranges))) |
| 132 |
|
| 133 |
;; take a section of a range. |
| 134 |
;; Use subrange to construct this type of instance. The constructor |
| 135 |
;; tries to "flatten" nested subranges. |
| 136 |
;; If the reverse? flag is true, the indexing is reversed. |
| 137 |
(define (%subrange-index range i) |
| 138 |
((~ range'range'indexer) (~ range'range) (+ i (~ range'offset)))) |
| 139 |
(define (%subrange-index-reverse range i) |
| 140 |
((~ range'range'indexer) (~ range'range) |
| 141 |
(+ (- (~ range'length) i 1) (~ range'offset)))) |
| 142 |
|
| 143 |
(define-class <subrange> (<range>) |
| 144 |
((indexer :init-value %subrange-index :init-keyword :indexer) |
| 145 |
(range :init-keyword :range) |
| 146 |
(offset :init-keyword :offset))) |
| 147 |
|
| 148 |
(define (%subrange-reversed? subrange) |
| 149 |
(eq? (~ subrange'indexer) %subrange-index-reverse)) |
| 150 |
|
| 151 |
;;; |
| 152 |
;;; Constructors |
| 153 |
;;; |
| 154 |
|
| 155 |
(define (range length indexer) |
| 156 |
(assume (and (exact-integer? length) (>= length 0)) |
| 157 |
"Range length must be exact nonnnegative integer:" length) |
| 158 |
(make <range> :length length :indexer (^[_ i] (indexer i)))) |
| 159 |
|
| 160 |
(define (numeric-range start end :optional (step 1)) |
| 161 |
(make <range> |
| 162 |
:length (max 0 (ceiling->exact (/ (- end start) step))) |
| 163 |
:indexer (^[_ i] (+ start (* i step))))) |
| 164 |
|
| 165 |
(define (iota-range length :optional (start 0) (step 1)) |
| 166 |
(make <range> |
| 167 |
:length length |
| 168 |
:indexer (^[_ i] (+ start (* i step))))) |
| 169 |
|
| 170 |
;; optional arguments are Gauche-specific |
| 171 |
(define (vector-range vec :optional (start 0) (end (vector-length vec))) |
| 172 |
(assume-type vec <vector>) |
| 173 |
(assume (<= 0 start end (vector-length vec)) |
| 174 |
"Start or end index is inconsistent:" start end) |
| 175 |
(make <flat-range> |
| 176 |
:length (- end start) |
| 177 |
:raw-indexer vector-ref |
| 178 |
:storage vec |
| 179 |
:offset start)) |
| 180 |
|
| 181 |
;; optional arguments are Gauche-specific |
| 182 |
(define (string-range str :optional (start 0) (end (string-length str))) |
| 183 |
(assume-type str <string>) |
| 184 |
(assume (<= 0 start end (string-length str)) |
| 185 |
"Start or end index is inconsistent:" start end) |
| 186 |
(make <flat-range> |
| 187 |
:length (- end start) |
| 188 |
:indexer string-ref |
| 189 |
:storage (string-build-index! str) |
| 190 |
:offset start)) |
| 191 |
|
| 192 |
;; Gauche extension |
| 193 |
(define (uvector-range uvec :optional (start 0) (end (uvector-length uvec))) |
| 194 |
(assume-type uvec <uvector>) |
| 195 |
(assume (<= 0 start end (uvector-length uvec)) |
| 196 |
"Start or end index is inconsistent:" start end) |
| 197 |
(make <flat-range> |
| 198 |
:length (- end start) |
| 199 |
:raw-indexer uvector-ref |
| 200 |
:storage uvec |
| 201 |
:offset start)) |
| 202 |
|
| 203 |
;; Gauche extension |
| 204 |
(define (bitvector/bool-range bvec |
| 205 |
:optional (start 0) (end (bitvector-length bvec))) |
| 206 |
(assume-type bvec <bitvector>) |
| 207 |
(assume (<= 0 start end (bitvector-length bvec)) |
| 208 |
"Start or end index is inconsistent:" start end) |
| 209 |
(make <flat-range> |
| 210 |
:length (- end start) |
| 211 |
:raw-indexer bitvector-ref/bool |
| 212 |
:storage bvec |
| 213 |
:offset start)) |
| 214 |
|
| 215 |
;; Gauche extension |
| 216 |
(define (bitvector/int-range bvec |
| 217 |
:optional (start 0) (end (bitvector-length bvec))) |
| 218 |
(assume-type bvec <bitvector>) |
| 219 |
(assume (<= 0 start end (bitvector-length bvec)) |
| 220 |
"Start or end index is inconsistent:" start end) |
| 221 |
(make <flat-range> |
| 222 |
:length (- end start) |
| 223 |
:raw-indexer bitvector-ref/int |
| 224 |
:storage bvec |
| 225 |
:offset start)) |
| 226 |
|
| 227 |
(define (range-append . ranges) |
| 228 |
(receive (off&ranges total) |
| 229 |
(map-accum (^[range total] |
| 230 |
(values (cons total range) |
| 231 |
(+ total (range-length range)))) |
| 232 |
0 ranges) |
| 233 |
(make <appended-range> |
| 234 |
:length total |
| 235 |
:ranges (list->vector off&ranges)))) |
| 236 |
|
| 237 |
(define (range-reverse rg :optional (start 0) (end (range-length rg))) |
| 238 |
(assume-type rg <range>) |
| 239 |
(assume (<= 0 start end (range-length rg)) |
| 240 |
"Start or end index is inconsistent:" start end) |
| 241 |
(if (is-a? rg <subrange>) |
| 242 |
(if (%subrange-reversed? rg) |
| 243 |
(make <subrange> |
| 244 |
:length (- end start) |
| 245 |
:range (~ rg'range) |
| 246 |
:offset (+ start (~ rg'offset))) |
| 247 |
(make <subrange> |
| 248 |
:indexer %subrange-index-reverse |
| 249 |
:length (- end start) |
| 250 |
:range (~ rg'range) |
| 251 |
:offset (+ start (~ rg'offset)))) |
| 252 |
(make <subrange> |
| 253 |
:indexer %subrange-index-reverse |
| 254 |
:range rg |
| 255 |
:length (- end start) |
| 256 |
:offset start))) |
| 257 |
|
| 258 |
;;; |
| 259 |
;;; Predicates |
| 260 |
;;; |
| 261 |
|
| 262 |
(define (range? x) (is-a? x <range>)) |
| 263 |
|
| 264 |
(define (range=? elt= . ranges) |
| 265 |
(or (null? ranges) |
| 266 |
(and (assume (range? (car ranges)) "Range required, but got:" (car ranges)) |
| 267 |
(null? (cdr ranges))) |
| 268 |
(let1 len (range-length (car ranges)) |
| 269 |
(every?-ec (: r (cdr ranges)) |
| 270 |
(and (= len (range-length r)) |
| 271 |
(every?-ec (: i len) |
| 272 |
(elt= (range-ref (car ranges) i) |
| 273 |
(range-ref r i)))))))) |
| 274 |
|
| 275 |
;;; |
| 276 |
;;; Accessors |
| 277 |
;;; |
| 278 |
|
| 279 |
(define (range-length range) |
| 280 |
(assume (range? range) "Range required, but got:" range) |
| 281 |
(~ range'length)) |
| 282 |
|
| 283 |
;; The optional fallback is Gauche extension |
| 284 |
(define (range-ref range n :optional fallback) |
| 285 |
(assume (range? range)) |
| 286 |
(cond [(<=:< 0 n (range-length range)) ((~ range'indexer) range n)] |
| 287 |
[(undefined? fallback) (error "Index out of range:" n)] |
| 288 |
[else fallback])) |
| 289 |
|
| 290 |
(define (range-first range :optional fallback) |
| 291 |
(if (zero? (range-length range)) |
| 292 |
(if (undefined? fallback) |
| 293 |
(error "range is empty:" range) |
| 294 |
fallback) |
| 295 |
(range-ref range 0))) |
| 296 |
(define (range-last range :optional fallback) |
| 297 |
(let1 len (range-length range) |
| 298 |
(if (zero? len) |
| 299 |
(if (undefined? fallback) |
| 300 |
(error "range is empty:" range) |
| 301 |
fallback) |
| 302 |
(range-ref range (- len 1))))) |
| 303 |
|
| 304 |
;;; |
| 305 |
;;; Iteration |
| 306 |
;;; |
| 307 |
|
| 308 |
(define (range-split-at range index) |
| 309 |
(assume-type range <range>) |
| 310 |
(assume (<= 0 index (range-length range))) |
| 311 |
(values (subrange range 0 index) |
| 312 |
(subrange range index (range-length range)))) |
| 313 |
|
| 314 |
(define (subrange range start end) |
| 315 |
(assume-type range <range>) |
| 316 |
(assume (<= start end (range-length range)) |
| 317 |
"Subrange start/end index out of original range:" |
| 318 |
range start end) |
| 319 |
(if (is-a? range <subrange>) |
| 320 |
;; We flatten the range |
| 321 |
(make <subrange> |
| 322 |
:length (- end start) |
| 323 |
:range (~ range'range) ; use inner range |
| 324 |
:offset (+ (~ range'offset) start)) |
| 325 |
(make <subrange> |
| 326 |
:length (- end start) |
| 327 |
:range range |
| 328 |
:offset start))) |
| 329 |
|
| 330 |
(define (range-segment range length) |
| 331 |
(let* ([total-length (range-length range)] |
| 332 |
[n (ceiling-quotient total-length length)]) |
| 333 |
(map (^i (subrange range |
| 334 |
(* i length) |
| 335 |
(min (* (+ i 1) length) total-length))) |
| 336 |
(liota n)))) |
| 337 |
|
| 338 |
(define (range-take range index) |
| 339 |
(subrange range 0 index)) |
| 340 |
(define (range-take-right range index) |
| 341 |
(subrange range (- (range-length range) index) (range-length range))) |
| 342 |
|
| 343 |
(define (range-drop range index) |
| 344 |
(subrange range index (range-length range))) |
| 345 |
(define (range-drop-right range index) |
| 346 |
(subrange range 0 (- (range-length range) index))) |
| 347 |
|
| 348 |
(define (range-count pred range1 . ranges) |
| 349 |
(if (null? ranges) |
| 350 |
(range-fold (^[cnt val] (if (pred val) (+ cnt 1) cnt)) 0 range1) |
| 351 |
(apply range-fold (^[cnt . vals] (if (apply pred vals) (+ cnt 1) cnt)) |
| 352 |
0 range1 ranges))) |
| 353 |
|
| 354 |
(define (range-any pred range1 . ranges) |
| 355 |
(if (null? ranges) |
| 356 |
(let1 g (range->generator range1) |
| 357 |
(let loop ([v (g)]) |
| 358 |
(cond [(eof-object? v) #f] |
| 359 |
[(pred v)] |
| 360 |
[else (loop (g))]))) |
| 361 |
(let1 gs (cons (range->generator range1) |
| 362 |
(map range->generator ranges)) |
| 363 |
(let loop ([vs (map (^g (g)) gs)]) |
| 364 |
(cond [(any eof-object? vs) #f] |
| 365 |
[(apply pred vs)] |
| 366 |
[else (loop (map (^g (g)) gs))]))))) |
| 367 |
|
| 368 |
(define (range-every pred range1 . ranges) |
| 369 |
(if (null? ranges) |
| 370 |
(let1 g (range->generator range1) |
| 371 |
(let loop ([v (g)] [last #t]) |
| 372 |
(cond [(eof-object? v) last] |
| 373 |
[(pred v) => (cut loop (g) <>)] |
| 374 |
[else #f]))) |
| 375 |
(let1 gs (cons (range->generator range1) |
| 376 |
(map range->generator ranges)) |
| 377 |
(let loop ([vs (map (^g (g)) gs)] [last #t]) |
| 378 |
(cond [(any eof-object? vs) last] |
| 379 |
[(apply pred vs) => (cut loop (map (^g (g)) gs) <>)] |
| 380 |
[else #f]))))) |
| 381 |
|
| 382 |
(define (range-map proc range1 . ranges) |
| 383 |
(vector-range (apply range-map->vector proc range1 ranges))) |
| 384 |
|
| 385 |
(define (range-map->list proc range1 . ranges) |
| 386 |
(if (null? ranges) |
| 387 |
(range-fold-right (^[r v] (cons (proc v) r)) '() range1) |
| 388 |
(apply range-fold-right (^[r . vs] (cons (apply proc vs) r)) '() |
| 389 |
range1 ranges))) |
| 390 |
(define (range-map->vector proc range1 . ranges) |
| 391 |
(if (null? ranges) |
| 392 |
(rlet1 vec (make-vector (range-length range1)) |
| 393 |
(do-ec (: k (range-length range1)) |
| 394 |
(vector-set! vec k (proc (range-ref range1 k))))) |
| 395 |
(let* ([ranges (cons range1 ranges)] |
| 396 |
[vec (make-vector (apply min (map range-length ranges)))]) |
| 397 |
(do-ec (: k (vector-length vec)) |
| 398 |
(vector-set! vec k (apply proc (map (cut range-ref <> k) ranges)))) |
| 399 |
vec))) |
| 400 |
|
| 401 |
(define (range-for-each proc range1 . ranges) |
| 402 |
(if (null? ranges) |
| 403 |
(range-fold (^[_ v] (proc v)) #f range1) |
| 404 |
(apply range-fold (^[_ . vs] (apply proc vs)) #f range1 ranges))) |
| 405 |
|
| 406 |
(define (range-filter-map proc range1 . ranges) |
| 407 |
($ vector-range $ list->vector |
| 408 |
$ apply range-filter-map->list proc range1 ranges)) |
| 409 |
|
| 410 |
(define (range-filter-map->list proc range1 . ranges) |
| 411 |
(if (null? ranges) |
| 412 |
(range-fold-right (^[r e] (if-let1 v (proc e) |
| 413 |
(cons v r) |
| 414 |
r)) |
| 415 |
'() range1) |
| 416 |
(apply range-fold-right |
| 417 |
(^[r . es] (if-let1 v (apply proc es) |
| 418 |
(cons v r) |
| 419 |
r)) |
| 420 |
'() range1 ranges))) |
| 421 |
|
| 422 |
(define (range-filter pred range) |
| 423 |
($ vector-range $ list->vector $ range-filter->list pred range)) |
| 424 |
(define (range-filter->list pred range) |
| 425 |
(range-fold-right (^[r e] (if (pred e) (cons e r) r)) '() range)) |
| 426 |
|
| 427 |
(define (range-remove pred range) |
| 428 |
($ vector-range $ list->vector $ range-remove->list pred range)) |
| 429 |
(define (range-remove->list pred range) |
| 430 |
(range-fold-right (^[r e] (if (pred e) r (cons e r))) '() range)) |
| 431 |
|
| 432 |
;; kons is invoked with the same order of vector-fold (state first) |
| 433 |
(define (range-fold kons knil range1 . ranges) |
| 434 |
(if (null? ranges) |
| 435 |
(fold (^[i seed] (kons seed (range-ref range1 i))) |
| 436 |
knil |
| 437 |
(liota (range-length range1))) |
| 438 |
(let1 len (fold (^[r m] (min m (range-length r))) |
| 439 |
(range-length range1) |
| 440 |
ranges) |
| 441 |
(fold (^[i seed] (apply kons seed |
| 442 |
(range-ref range1 i) |
| 443 |
(map (^r (range-ref r i)) ranges))) |
| 444 |
knil |
| 445 |
(liota len))))) |
| 446 |
|
| 447 |
(define (range-fold-right kons knil range1 . ranges) |
| 448 |
(if (null? ranges) |
| 449 |
(fold (^[i seed] (kons seed (range-ref range1 i))) |
| 450 |
knil |
| 451 |
(liota (range-length range1) (- (range-length range1) 1) -1)) |
| 452 |
(let1 len (fold (^[r m] (min m (range-length r))) |
| 453 |
(range-length range1) |
| 454 |
ranges) |
| 455 |
(fold (^[i seed] (apply kons seed |
| 456 |
(range-ref range1 i) |
| 457 |
(map (^r (range-ref r i)) ranges))) |
| 458 |
knil |
| 459 |
(liota len (- len 1) -1))))) |
| 460 |
|
| 461 |
;;; |
| 462 |
;;; Searching |
| 463 |
;;; |
| 464 |
|
| 465 |
(define (range-index pred range1 . ranges) |
| 466 |
(if (null? ranges) |
| 467 |
(let1 len (range-length range1) |
| 468 |
(let loop ([i 0]) |
| 469 |
(cond [(= i len) #f] |
| 470 |
[(pred (range-ref range1 i)) i] |
| 471 |
[else (loop (+ i 1))]))) |
| 472 |
(let1 len (apply min (range-length range1) (map range-length ranges)) |
| 473 |
(let loop ([i 0]) |
| 474 |
(cond [(= i len) #f] |
| 475 |
[(apply pred (range-ref range1 i) |
| 476 |
(map (cut range-ref <> i) ranges)) i] |
| 477 |
[else (loop (+ i 1))]))))) |
| 478 |
|
| 479 |
(define (range-index-right pred range1 . ranges) |
| 480 |
(if (null? ranges) |
| 481 |
(let1 len (range-length range1) |
| 482 |
(let loop ([i (- len 1)]) |
| 483 |
(cond [(= i 0) #f] |
| 484 |
[(pred (range-ref range1 i)) i] |
| 485 |
[else (loop (- i 1))]))) |
| 486 |
(let1 len (apply min (range-length range1) (map range-length ranges)) |
| 487 |
(let loop ([i (- len 1)]) |
| 488 |
(cond [(= i 0) #f] |
| 489 |
[(apply pred (range-ref range1 i) |
| 490 |
(map (cut range-ref <> i) ranges)) i] |
| 491 |
[else (loop (- i 1))]))))) |
| 492 |
|
| 493 |
(define (range-take-while pred r) |
| 494 |
(let1 len (range-length r) |
| 495 |
(let loop ([i 0]) |
| 496 |
(if (= i len) |
| 497 |
r |
| 498 |
(let1 e (range-ref r i) |
| 499 |
(if (pred e) |
| 500 |
(loop (+ i 1)) |
| 501 |
(subrange r 0 i))))))) |
| 502 |
|
| 503 |
(define (range-take-while-right pred r) |
| 504 |
(let1 len (range-length r) |
| 505 |
(let loop ([i (- len 1)]) |
| 506 |
(if (= i 0) |
| 507 |
r |
| 508 |
(let1 e (range-ref r i) |
| 509 |
(if (pred e) |
| 510 |
(loop (- i 1)) |
| 511 |
(subrange r (+ i 1) len))))))) |
| 512 |
|
| 513 |
(define (range-drop-while pred r) |
| 514 |
(let1 len (range-length r) |
| 515 |
(let loop ([i 0]) |
| 516 |
(if (= i len) |
| 517 |
(range 0 (constantly #f)) |
| 518 |
(let1 e (range-ref r i) |
| 519 |
(if (pred e) |
| 520 |
(loop (+ i 1)) |
| 521 |
(subrange r i len))))))) |
| 522 |
|
| 523 |
(define (range-drop-while-right pred r) |
| 524 |
(let1 len (range-length r) |
| 525 |
(let loop ([i (- len 1)]) |
| 526 |
(if (= i 0) |
| 527 |
(range 0 (constantly #f)) |
| 528 |
(let1 e (range-ref r i) |
| 529 |
(if (pred e) |
| 530 |
(loop (- i 1)) |
| 531 |
(subrange r 0 (+ i 1)))))))) |
| 532 |
|
| 533 |
;;; |
| 534 |
;;; Conversion |
| 535 |
;;; |
| 536 |
|
| 537 |
(define (range->list range) |
| 538 |
(assume-type range <range>) |
| 539 |
(list-ec (: i (range-length range)) |
| 540 |
(range-ref range i))) |
| 541 |
|
| 542 |
(define (range->vector range) |
| 543 |
(assume-type range <range>) |
| 544 |
;; We might be able to return the internal storage directly if range is |
| 545 |
;; <flat-range> on a vector, since "it is an error" to mutate the return |
| 546 |
;; value; but there would be no check if the caller conforms it. Until |
| 547 |
;; we see the case that such optimization is effective, we just build |
| 548 |
;; a new vector. |
| 549 |
(vector-ec (: i (range-length range)) |
| 550 |
(range-ref range i))) |
| 551 |
|
| 552 |
(define (range->string range) |
| 553 |
(assume-type range <range>) |
| 554 |
(if (and (is-a? range <flat-range>) |
| 555 |
(string? (~ range'storage))) |
| 556 |
(substring (~ range'storage) |
| 557 |
(~ range'offset) |
| 558 |
(+ (~ range'offset) (~ range'length))) |
| 559 |
(string-ec (: i (range-length range)) |
| 560 |
(range-ref range i)))) |
| 561 |
|
| 562 |
;; optional arguments are Gauche-specific |
| 563 |
(define (vector->range vec :optional (start 0) (end (vector-length vec))) |
| 564 |
(vector-range (vector-copy vec start end))) |
| 565 |
|
| 566 |
;; optional arguments are Gauche-specific |
| 567 |
(define (range->generator range :optional (start 0) (end (range-length range))) |
| 568 |
(define i start) |
| 569 |
(^[] (if (>= i end) |
| 570 |
(eof-object) |
| 571 |
(begin0 (range-ref range i) (inc! i))))) |
| 572 |
|
| 573 |
;;; |
| 574 |
;;; Sequence protocol |
| 575 |
;;; |
| 576 |
|
| 577 |
(define-method referencer ((r <range>)) (~ r'indexer)) |
| 578 |
|
| 579 |
(define-method call-with-iterator ((r <range>) proc |
| 580 |
:key (start 0) |
| 581 |
(end (range-length r)) |
| 582 |
:allow-other-keys) |
| 583 |
(let ([i start]) |
| 584 |
(proc (^[] (>= i end)) |
| 585 |
(^[] (begin0 (range-ref r i) (inc! i)))))) |
| 586 |
|
| 587 |
(define-method call-with-reverse-iterator ((r <range>) proc |
| 588 |
:key (start 0) |
| 589 |
(end (range-length r)) |
| 590 |
:allow-other-keys) |
| 591 |
(let ([i (- end 1)]) |
| 592 |
(proc (^[] (< i start) |
| 593 |
(^[] (begin0 (range-ref r i) (dec! i))))))) |
| 594 |
|
| 595 |
(define-method call-with-builder ((c <range-meta>) proc :key (size #f)) |
| 596 |
(if (integer? size) |
| 597 |
(let ([buf (make-vector size #f)] |
| 598 |
[i 0]) |
| 599 |
(proc (^v (vector-set! buf i v) (inc! i)) |
| 600 |
(^[] (vector-range buf)))) |
| 601 |
(let ([vs '()]) |
| 602 |
(proc (^v (push! vs v)) |
| 603 |
(^[] (vector-range (reverse-list->vector vs))))))) |
| 604 |
|
| 605 |
(define-method size-of ((r <range>)) (range-length r)) |
| 606 |
|
| 607 |
;; some shortcuts |
| 608 |
(define-method subseq ((r <range>) s e) (subrange r s e)) |
| 609 |
(define-method subseq ((r <range>) s) (subrange r s (range-length r))) |
| 610 |
(define-method coerce-to ((r <range-meta>) (v <vector>)) (vector-range v)) |
| 611 |
(define-method coerce-to ((r <range-meta>) (v <string>)) (string-range v)) |