Coverage report: /home/ellis/.stash/quicklisp/dists/quicklisp/software/alexandria-20241012-git/alexandria-1/sequences.lisp

KindCoveredAll%
expression0832 0.0
branch0134 0.0
Key
Not instrumented
Conditionalized out
Executed
Not executed
 
Both branches taken
One branch taken
Neither branch taken
1
 (in-package :alexandria)
2
 
3
 ;; Make these inlinable by declaiming them INLINE here and some of them
4
 ;; NOTINLINE at the end of the file. Exclude functions that have a compiler
5
 ;; macro, because NOTINLINE is required to prevent compiler-macro expansion.
6
 (declaim (inline copy-sequence sequence-of-length-p))
7
 
8
 (defun sequence-of-length-p (sequence length)
9
   "Return true if SEQUENCE is a sequence of length LENGTH. Signals an error if
10
 SEQUENCE is not a sequence. Returns FALSE for circular lists."
11
   (declare (type array-index length)
12
            #-lispworks (inline length)
13
            (optimize speed))
14
   (etypecase sequence
15
     (null
16
      (zerop length))
17
     (cons
18
      (let ((n (1- length)))
19
        (unless (minusp n)
20
          (let ((tail (nthcdr n sequence)))
21
            (and tail
22
                 (null (cdr tail)))))))
23
     (vector
24
      (= length (length sequence)))
25
     (sequence
26
      (= length (length sequence)))))
27
 
28
 (defun rotate-tail-to-head (sequence n)
29
   (declare (type (integer 1) n))
30
   (if (listp sequence)
31
       (let ((m (mod n (proper-list-length sequence))))
32
         (if (null (cdr sequence))
33
             sequence
34
             (let* ((tail (last sequence (+ m 1)))
35
                    (last (cdr tail)))
36
               (setf (cdr tail) nil)
37
               (nconc last sequence))))
38
       (let* ((len (length sequence))
39
              (m (mod n len))
40
              (tail (subseq sequence (- len m))))
41
         (replace sequence sequence :start1 m :start2 0)
42
         (replace sequence tail)
43
         sequence)))
44
 
45
 (defun rotate-head-to-tail (sequence n)
46
   (declare (type (integer 1) n))
47
   (if (listp sequence)
48
       (let ((m (mod (1- n) (proper-list-length sequence))))
49
         (if (null (cdr sequence))
50
             sequence
51
             (let* ((headtail (nthcdr m sequence))
52
                    (tail (cdr headtail)))
53
               (setf (cdr headtail) nil)
54
               (nconc tail sequence))))
55
       (let* ((len (length sequence))
56
              (m (mod n len))
57
              (head (subseq sequence 0 m)))
58
         (replace sequence sequence :start1 0 :start2 m)
59
         (replace sequence head :start1 (- len m))
60
         sequence)))
61
 
62
 (defun rotate (sequence &optional (n 1))
63
   "Returns a sequence of the same type as SEQUENCE, with the elements of
64
 SEQUENCE rotated by N: N elements are moved from the end of the sequence to
65
 the front if N is positive, and -N elements moved from the front to the end if
66
 N is negative. SEQUENCE must be a proper sequence. N must be an integer,
67
 defaulting to 1.
68
 
69
 If absolute value of N is greater then the length of the sequence, the results
70
 are identical to calling ROTATE with
71
 
72
   (* (signum n) (mod n (length sequence))).
73
 
74
 Note: the original sequence may be destructively altered, and result sequence may
75
 share structure with it."
76
   (if (plusp n)
77
       (rotate-tail-to-head sequence n)
78
       (if (minusp n)
79
           (rotate-head-to-tail sequence (- n))
80
           sequence)))
81
 
82
 (defun shuffle (sequence &key (start 0) end)
83
   "Returns a random permutation of SEQUENCE bounded by START and END.
84
 Original sequence may be destructively modified.
85
 Signals an error if SEQUENCE is not a proper sequence."
86
   (declare (type fixnum start)
87
            (type (or fixnum null) end))
88
   (etypecase sequence
89
     (list
90
      (let* ((end (or end (proper-list-length sequence)))
91
             (n (- end start))
92
             (sublist (nthcdr start sequence))
93
             (small-enough-threshold 100))
94
        ;; It's fine to use a pure list shuffle if the number of items
95
        ;; to shuffle is small enough, but otherwise it's more
96
        ;; time-efficient to create an intermediate vector to work on.
97
        ;; I picked the threshold based on rudimentary benchmarks on my
98
        ;; machine, where both branches take about the same time.
99
        (if (< n small-enough-threshold)
100
            (do ((tail sublist (cdr tail)))
101
                ((zerop n))
102
              (rotatef (car tail) (car (nthcdr (random n) tail)))
103
              (decf n))
104
            (let ((intermediate-vector (replace (make-array n) sublist)))
105
              (replace sublist (shuffle intermediate-vector))))))
106
     (vector
107
      (let ((end (or end (length sequence))))
108
        (loop for i from start below end
109
              do (rotatef (aref sequence i)
110
                          (aref sequence (+ i (random (- end i))))))))
111
     (sequence
112
      (let ((end (or end (length sequence))))
113
        (loop for i from (- end 1) downto start
114
              do (rotatef (elt sequence i)
115
                          (elt sequence (+ i (random (- end i)))))))))
116
   sequence)
117
 
118
 (defun random-elt (sequence &key (start 0) end)
119
   "Returns a random element from SEQUENCE bounded by START and END. Signals an
120
 error if the SEQUENCE is not a proper non-empty sequence, or if END and START
121
 are not proper bounding index designators for SEQUENCE."
122
   (declare (sequence sequence) (fixnum start) (type (or fixnum null) end))
123
   (let* ((size (if (listp sequence)
124
                    (proper-list-length sequence)
125
                    (length sequence)))
126
          (end2 (or end size)))
127
     (cond ((zerop size)
128
            (error 'type-error
129
                   :datum sequence
130
                   :expected-type `(and sequence (not (satisfies emptyp)))))
131
           ((not (and (<= 0 start) (< start end2) (<= end2 size)))
132
            (error 'simple-type-error
133
                   :datum (cons start end)
134
                   :expected-type `(cons (integer 0 (,end2))
135
                                         (or null (integer (,start) ,size)))
136
                   :format-control "~@<~S and ~S are not valid bounding index designators for ~
137
                                    a sequence of length ~S.~:@>"
138
                   :format-arguments (list start end size)))
139
           (t
140
            (let ((index (+ start (random (- end2 start)))))
141
              (elt sequence index))))))
142
 
143
 (declaim (inline remove/swapped-arguments))
144
 (defun remove/swapped-arguments (sequence item &rest keyword-arguments)
145
   (apply #'remove item sequence keyword-arguments))
146
 
147
 (define-modify-macro removef (item &rest keyword-arguments)
148
   remove/swapped-arguments
149
   "Modify-macro for REMOVE. Sets place designated by the first argument to
150
 the result of calling REMOVE with ITEM, place, and the KEYWORD-ARGUMENTS.")
151
 
152
 (declaim (inline delete/swapped-arguments))
153
 (defun delete/swapped-arguments (sequence item &rest keyword-arguments)
154
   (apply #'delete item sequence keyword-arguments))
155
 
156
 (define-modify-macro deletef (item &rest keyword-arguments)
157
   delete/swapped-arguments
158
   "Modify-macro for DELETE. Sets place designated by the first argument to
159
 the result of calling DELETE with ITEM, place, and the KEYWORD-ARGUMENTS.")
160
 
161
 (deftype proper-sequence ()
162
   "Type designator for proper sequences, that is proper lists and sequences
163
 that are not lists."
164
   `(or proper-list
165
        (and (not list) sequence)))
166
 
167
 (eval-when (:compile-toplevel :load-toplevel :execute)
168
   (when (and (find-package '#:sequence)
169
              (find-symbol (string '#:emptyp) '#:sequence))
170
     (pushnew 'sequence-emptyp *features*)))
171
 
172
 #-alexandria::sequence-emptyp
173
 (defun emptyp (sequence)
174
   "Returns true if SEQUENCE is an empty sequence. Signals an error if SEQUENCE
175
 is not a sequence."
176
   (etypecase sequence
177
     (list (null sequence))
178
     (sequence (zerop (length sequence)))))
179
 
180
 #+alexandria::sequence-emptyp
181
 (declaim (ftype (function (sequence) (values boolean &optional)) emptyp))
182
 #+alexandria::sequence-emptyp
183
 (setf (symbol-function 'emptyp) (symbol-function 'sequence:emptyp))
184
 #+alexandria::sequence-emptyp
185
 (define-compiler-macro emptyp (sequence)
186
   `(sequence:emptyp ,sequence))
187
 
188
 (defun length= (&rest sequences)
189
   "Takes any number of sequences or integers in any order. Returns true iff
190
 the length of all the sequences and the integers are equal. Hint: there's a
191
 compiler macro that expands into more efficient code if the first argument
192
 is a literal integer."
193
   (declare (dynamic-extent sequences)
194
            (inline sequence-of-length-p)
195
            (optimize speed))
196
   (unless (cdr sequences)
197
     (error "You must call LENGTH= with at least two arguments"))
198
   ;; There's room for optimization here: multiple list arguments could be
199
   ;; traversed in parallel.
200
   (let* ((first (pop sequences))
201
          (current (if (integerp first)
202
                       first
203
                       (length first))))
204
     (declare (type array-index current))
205
     (dolist (el sequences)
206
       (if (integerp el)
207
           (unless (= el current)
208
             (return-from length= nil))
209
           (unless (sequence-of-length-p el current)
210
             (return-from length= nil)))))
211
   t)
212
 
213
 (define-compiler-macro length= (&whole form length &rest sequences)
214
   (cond
215
     ((zerop (length sequences))
216
      form)
217
     (t
218
      (let ((optimizedp (integerp length)))
219
        (with-unique-names (tmp current)
220
          (declare (ignorable current))
221
          `(locally
222
               (declare (inline sequence-of-length-p))
223
             (let ((,tmp)
224
                   ,@(unless optimizedp
225
                      `((,current ,length))))
226
               ,@(unless optimizedp
227
                   `((unless (integerp ,current)
228
                       (setf ,current (length ,current)))))
229
               (and
230
                ,@(loop
231
                     :for sequence :in sequences
232
                     :collect `(progn
233
                                 (setf ,tmp ,sequence)
234
                                 (if (integerp ,tmp)
235
                                     (= ,tmp ,(if optimizedp
236
                                                  length
237
                                                  current))
238
                                     (sequence-of-length-p ,tmp ,(if optimizedp
239
                                                                     length
240
                                                                     current)))))))))))))
241
 
242
 (defun copy-sequence (type sequence)
243
   "Returns a fresh sequence of TYPE, which has the same elements as
244
 SEQUENCE."
245
   (if (typep sequence type)
246
       (copy-seq sequence)
247
       (coerce sequence type)))
248
 
249
 (defun first-elt (sequence)
250
   "Returns the first element of SEQUENCE. Signals a type-error if SEQUENCE is
251
 not a sequence, or is an empty sequence."
252
   ;; Can't just directly use ELT, as it is not guaranteed to signal the
253
   ;; type-error.
254
   (cond  ((consp sequence)
255
           (car sequence))
256
          ((and (typep sequence 'sequence) (not (emptyp sequence)))
257
           (elt sequence 0))
258
          (t
259
           (error 'type-error
260
                  :datum sequence
261
                  :expected-type '(and sequence (not (satisfies emptyp)))))))
262
 
263
 (defun (setf first-elt) (object sequence)
264
   "Sets the first element of SEQUENCE. Signals a type-error if SEQUENCE is
265
 not a sequence, is an empty sequence, or if OBJECT cannot be stored in SEQUENCE."
266
   ;; Can't just directly use ELT, as it is not guaranteed to signal the
267
   ;; type-error.
268
   (cond ((consp sequence)
269
          (setf (car sequence) object))
270
         ((and (typep sequence 'sequence) (not (emptyp sequence)))
271
          (setf (elt sequence 0) object))
272
         (t
273
          (error 'type-error
274
                 :datum sequence
275
                 :expected-type '(and sequence (not (satisfies emptyp)))))))
276
 
277
 (defun last-elt (sequence)
278
   "Returns the last element of SEQUENCE. Signals a type-error if SEQUENCE is
279
 not a proper sequence, or is an empty sequence."
280
   ;; Can't just directly use ELT, as it is not guaranteed to signal the
281
   ;; type-error.
282
   (let ((len 0))
283
     (cond ((consp sequence)
284
            (lastcar sequence))
285
           ((and (typep sequence '(and sequence (not list))) (plusp (setf len (length sequence))))
286
            (elt sequence (1- len)))
287
           (t
288
            (error 'type-error
289
                   :datum sequence
290
                   :expected-type '(and proper-sequence (not (satisfies emptyp))))))))
291
 
292
 (defun (setf last-elt) (object sequence)
293
   "Sets the last element of SEQUENCE. Signals a type-error if SEQUENCE is not a proper
294
 sequence, is an empty sequence, or if OBJECT cannot be stored in SEQUENCE."
295
   (let ((len 0))
296
     (cond ((consp sequence)
297
            (setf (lastcar sequence) object))
298
           ((and (typep sequence '(and sequence (not list))) (plusp (setf len (length sequence))))
299
            (setf (elt sequence (1- len)) object))
300
           (t
301
            (error 'type-error
302
                   :datum sequence
303
                   :expected-type '(and proper-sequence (not (satisfies emptyp))))))))
304
 
305
 (defun starts-with-subseq (prefix sequence &rest args
306
                            &key
307
                            (return-suffix nil return-suffix-supplied-p)
308
                            &allow-other-keys)
309
   "Test whether the first elements of SEQUENCE are the same (as per TEST) as the elements of PREFIX.
310
 
311
 If RETURN-SUFFIX is T the function returns, as a second value, a
312
 sub-sequence or displaced array pointing to the sequence after PREFIX."
313
   (declare (dynamic-extent args))
314
   (let ((sequence-length (length sequence))
315
         (prefix-length (length prefix)))
316
     (when (< sequence-length prefix-length)
317
       (return-from starts-with-subseq (values nil nil)))
318
     (flet ((make-suffix (start)
319
              (when return-suffix
320
                (cond
321
                  ((not (arrayp sequence))
322
                   (if start
323
                       (subseq sequence start)
324
                       (subseq sequence 0 0)))
325
                  ((not start)
326
                   (make-array 0
327
                               :element-type (array-element-type sequence)
328
                               :adjustable nil))
329
                  (t
330
                   (make-array (- sequence-length start)
331
                               :element-type (array-element-type sequence)
332
                               :displaced-to sequence
333
                               :displaced-index-offset start
334
                               :adjustable nil))))))
335
       (let ((mismatch (apply #'mismatch prefix sequence
336
                              (if return-suffix-supplied-p
337
                                  (remove-from-plist args :return-suffix)
338
                                  args))))
339
         (cond
340
           ((not mismatch)
341
            (values t (make-suffix nil)))
342
           ((= mismatch prefix-length)
343
            (values t (make-suffix mismatch)))
344
           (t
345
            (values nil nil)))))))
346
 
347
 (defun ends-with-subseq (suffix sequence &key (test #'eql))
348
   "Test whether SEQUENCE ends with SUFFIX. In other words: return true if
349
 the last (length SUFFIX) elements of SEQUENCE are equal to SUFFIX."
350
   (let ((sequence-length (length sequence))
351
         (suffix-length (length suffix)))
352
     (when (< sequence-length suffix-length)
353
       ;; if SEQUENCE is shorter than SUFFIX, then SEQUENCE can't end with SUFFIX.
354
       (return-from ends-with-subseq nil))
355
     (loop for sequence-index from (- sequence-length suffix-length) below sequence-length
356
           for suffix-index from 0 below suffix-length
357
           when (not (funcall test (elt sequence sequence-index) (elt suffix suffix-index)))
358
           do (return-from ends-with-subseq nil)
359
           finally (return t))))
360
 
361
 (defun starts-with (object sequence &key (test #'eql) (key #'identity))
362
   "Returns true if SEQUENCE is a sequence whose first element is EQL to OBJECT.
363
 Returns NIL if the SEQUENCE is not a sequence or is an empty sequence."
364
   (let ((first-elt (typecase sequence
365
                      (cons (car sequence))
366
                      (sequence
367
                       (if (emptyp sequence)
368
                           (return-from starts-with nil)
369
                           (elt sequence 0)))
370
                      (t
371
                       (return-from starts-with nil)))))
372
     (funcall test (funcall key first-elt) object)))
373
 
374
 (defun ends-with (object sequence &key (test #'eql) (key #'identity))
375
   "Returns true if SEQUENCE is a sequence whose last element is EQL to OBJECT.
376
 Returns NIL if the SEQUENCE is not a sequence or is an empty sequence. Signals
377
 an error if SEQUENCE is an improper list."
378
   (let ((last-elt (typecase sequence
379
                     (cons
380
                      (lastcar sequence)) ; signals for improper lists
381
                     (sequence
382
                      ;; Can't use last-elt, as that signals an error
383
                      ;; for empty sequences
384
                      (let ((len (length sequence)))
385
                        (if (plusp len)
386
                            (elt sequence (1- len))
387
                            (return-from ends-with nil))))
388
                     (t
389
                      (return-from ends-with nil)))))
390
     (funcall test (funcall key last-elt) object)))
391
 
392
 (defun map-combinations (function sequence &key (start 0) end length (copy t))
393
   "Calls FUNCTION with each combination of LENGTH constructable from the
394
 elements of the subsequence of SEQUENCE delimited by START and END. START
395
 defaults to 0, END to length of SEQUENCE, and LENGTH to the length of the
396
 delimited subsequence. (So unless LENGTH is specified there is only a single
397
 combination, which has the same elements as the delimited subsequence.) If
398
 COPY is true (the default) each combination is freshly allocated. If COPY is
399
 false all combinations are EQ to each other, in which case consequences are
400
 unspecified if a combination is modified by FUNCTION."
401
   (let* ((end (or end (length sequence)))
402
          (size (- end start))
403
          (length (or length size))
404
          (combination (subseq sequence 0 length))
405
          (function (ensure-function function)))
406
     (if (= length size)
407
         (funcall function combination)
408
         (flet ((call ()
409
                  (funcall function (if copy
410
                                        (copy-seq combination)
411
                                        combination))))
412
           (etypecase sequence
413
             ;; When dealing with lists we prefer walking back and
414
             ;; forth instead of using indexes.
415
             (list
416
              (labels ((combine-list (c-tail o-tail)
417
                         (if (not c-tail)
418
                             (call)
419
                             (do ((tail o-tail (cdr tail)))
420
                                 ((not tail))
421
                               (setf (car c-tail) (car tail))
422
                               (combine-list (cdr c-tail) (cdr tail))))))
423
                (combine-list combination (nthcdr start sequence))))
424
             (vector
425
              (labels ((combine (count start)
426
                         (if (zerop count)
427
                             (call)
428
                             (loop for i from start below end
429
                                   do (let ((j (- count 1)))
430
                                        (setf (aref combination j) (aref sequence i))
431
                                        (combine j (+ i 1)))))))
432
                (combine length start)))
433
             (sequence
434
              (labels ((combine (count start)
435
                         (if (zerop count)
436
                             (call)
437
                             (loop for i from start below end
438
                                   do (let ((j (- count 1)))
439
                                        (setf (elt combination j) (elt sequence i))
440
                                        (combine j (+ i 1)))))))
441
                (combine length start)))))))
442
   sequence)
443
 
444
 (defun map-permutations (function sequence &key (start 0) end length (copy t))
445
   "Calls function with each permutation of LENGTH constructable
446
 from the subsequence of SEQUENCE delimited by START and END. START
447
 defaults to 0, END to length of the sequence, and LENGTH to the
448
 length of the delimited subsequence."
449
   (let* ((end (or end (length sequence)))
450
          (size (- end start))
451
          (length (or length size)))
452
     (labels ((permute (seq n)
453
                (let ((n-1 (- n 1)))
454
                  (if (zerop n-1)
455
                      (funcall function (if copy
456
                                            (copy-seq seq)
457
                                            seq))
458
                      (loop for i from 0 upto n-1
459
                            do (permute seq n-1)
460
                            (if (evenp n-1)
461
                                (rotatef (elt seq 0) (elt seq n-1))
462
                                (rotatef (elt seq i) (elt seq n-1)))))))
463
              (permute-sequence (seq)
464
                (permute seq length)))
465
       (if (= length size)
466
           ;; Things are simple if we need to just permute the
467
           ;; full START-END range.
468
           (permute-sequence (subseq sequence start end))
469
           ;; Otherwise we need to generate all the combinations
470
           ;; of LENGTH in the START-END range, and then permute
471
           ;; a copy of the result: can't permute the combination
472
           ;; directly, as they share structure with each other.
473
           (let ((permutation (subseq sequence 0 length)))
474
             (flet ((permute-combination (combination)
475
                      (permute-sequence (replace permutation combination))))
476
               (declare (dynamic-extent #'permute-combination))
477
               (map-combinations #'permute-combination sequence
478
                                 :start start
479
                                 :end end
480
                                 :length length
481
                                 :copy nil)))))))
482
 
483
 (defun map-derangements (function sequence &key (start 0) end (copy t))
484
   "Calls FUNCTION with each derangement of the subsequence of SEQUENCE denoted
485
 by the bounding index designators START and END. Derangement is a permutation
486
 of the sequence where no element remains in place. SEQUENCE is not modified,
487
 but individual derangements are EQ to each other. Consequences are unspecified
488
 if calling FUNCTION modifies either the derangement or SEQUENCE."
489
   (let* ((end (or end (length sequence)))
490
          (size (- end start))
491
          ;; We don't really care about the elements here.
492
          (derangement (subseq sequence 0 size))
493
          ;; Bitvector that has 1 for elements that have been deranged.
494
          (mask (make-array size :element-type 'bit :initial-element 0)))
495
     (declare (dynamic-extent mask))
496
     ;; ad hoc algorith
497
     (labels ((derange (place n)
498
                ;; Perform one recursive step in deranging the
499
                ;; sequence: PLACE is index of the original sequence
500
                ;; to derange to another index, and N is the number of
501
                ;; indexes not yet deranged.
502
                (if (zerop n)
503
                    (funcall function (if copy
504
                                          (copy-seq derangement)
505
                                          derangement))
506
                    ;; Itarate over the indexes I of the subsequence to
507
                    ;; derange: if I != PLACE and I has not yet been
508
                    ;; deranged by an earlier call put the element from
509
                    ;; PLACE to I, mark I as deranged, and recurse,
510
                    ;; finally removing the mark.
511
                    (loop for i from 0 below size
512
                          do
513
                          (unless (or (= place (+ i start)) (not (zerop (bit mask i))))
514
                            (setf (elt derangement i) (elt sequence place)
515
                                  (bit mask i) 1)
516
                            (derange (1+ place) (1- n))
517
                            (setf (bit mask i) 0))))))
518
       (derange start size)
519
       sequence)))
520
 
521
 (declaim (notinline sequence-of-length-p))
522
 
523
 (defun extremum (sequence predicate &key key (start 0) end)
524
   "Returns the element of SEQUENCE that would appear first if the subsequence
525
 bounded by START and END was sorted using PREDICATE and KEY.
526
 
527
 EXTREMUM determines the relationship between two elements of SEQUENCE by using
528
 the PREDICATE function. PREDICATE should return true if and only if the first
529
 argument is strictly less than the second one (in some appropriate sense). Two
530
 arguments X and Y are considered to be equal if (FUNCALL PREDICATE X Y)
531
 and (FUNCALL PREDICATE Y X) are both false.
532
 
533
 The arguments to the PREDICATE function are computed from elements of SEQUENCE
534
 using the KEY function, if supplied. If KEY is not supplied or is NIL, the
535
 sequence element itself is used.
536
 
537
 If SEQUENCE is empty, NIL is returned."
538
   (let* ((pred-fun (ensure-function predicate))
539
          (key-fun (unless (or (not key) (eq key 'identity) (eq key #'identity))
540
                     (ensure-function key)))
541
          (real-end (or end (length sequence))))
542
     (cond ((> real-end start)
543
            (if key-fun
544
                (flet ((reduce-keys (a b)
545
                         (if (funcall pred-fun
546
                                      (funcall key-fun a)
547
                                      (funcall key-fun b))
548
                             a
549
                             b)))
550
                  (declare (dynamic-extent #'reduce-keys))
551
                  (reduce #'reduce-keys sequence :start start :end real-end))
552
                (flet ((reduce-elts (a b)
553
                         (if (funcall pred-fun a b)
554
                             a
555
                             b)))
556
                  (declare (dynamic-extent #'reduce-elts))
557
                  (reduce #'reduce-elts sequence :start start :end real-end))))
558
           ((= real-end start)
559
            nil)
560
           (t
561
            (error "Invalid bounding indexes for sequence of length ~S: ~S ~S, ~S ~S"
562
                   (length sequence)
563
                   :start start
564
                   :end end)))))