src/lib/ringbuffer.slate

   1 define: #RingBuffer &parents: {Queue}.
   2 "A RingBuffer is an ExtensibleSequence like a Queue in that it uses a gap
   3 to optimize for adding elements at one end and removing them from another.
   4 Unlike a Queue, it does not grow when its underlying Array is used up.
   5 Instead, it starts overwriting elements at the other end.
   6 It can be grown on request, however."
   7
   8 r@(RingBuffer traits) addLast: obj
   9 [
  10   r contents at: r lastIndex := obj.
  11   r isFull ifTrue: [r firstIndex := r firstIndex + 1 \\ r contents size].
  12   r lastIndex := r lastIndex + 1 \\ r contents size.
  13   obj
  14 ].
  15
  16 r@(RingBuffer traits) addFirst: obj
  17 [
  18   r isFull ifTrue: [r lastIndex := r lastIndex - 1 \\ r contents size].
  19   r firstIndex := r firstIndex - 1 \\ r contents size.
  20   r contents at: r firstIndex := obj.
  21   obj
  22 ].
  23
  24 r@(RingBuffer traits) addAllLast: seq
  25 [| newLastIndex |
  26   seq size > r capacity ifTrue:
  27     [seq := seq sliceFrom: seq size - r capacity].
  28   "The new lastIndex after all the elements are added."
  29   newLastIndex := r lastIndex + seq size \\ r contents size.
  30   "Update the firstIndex if adding the elements will fill up the contents."
  31   seq size > r gapSize ifTrue:
  32     [r firstIndex := r firstIndex + (seq size - r gapSize) \\ r contents size].
  33   "Whether adding the elements to the end will push the lastIndex past the
  34    underlying Array's end."
  35   newLastIndex < r lastIndex
  36     ifTrue:
  37       [| split |
  38        "The number of elements that will fit before wrap-around."
  39        split := r contents size - r lastIndex.
  40        r contents replaceFrom: r lastIndex below: r contents size with: seq.
  41        r contents replaceFrom: 0 below: seq size - split with: seq &startingAt: split]
  42     ifFalse: [r contents replaceFrom: r lastIndex below: newLastIndex with: seq].
  43   "Finally, update the lastIndex."
  44   r lastIndex := newLastIndex.
  45   seq
  46 ].
  47
  48 r@(RingBuffer traits) addAllFirst: seq
  49 [| newFirstIndex |
  50   seq size > r capacity ifTrue:
  51     [seq := seq sliceFrom: seq size - r capacity].
  52   "The new firstIndex after all the elements are added."
  53   newFirstIndex := r firstIndex - seq size \\ r contents size.
  54   "Update the lastIndex if adding the elements will fill up the contents."
  55   seq size > r gapSize ifTrue:
  56     [r lastIndex := r lastIndex - (seq size - r gapSize) \\ r contents size].
  57   "Whether adding the elements to the end will push the firstIndex past the
  58    underlying Array's start."
  59   newFirstIndex > r firstIndex
  60     ifTrue:
  61       [| split |
  62        "The number of elements that will need to be added at the end of the Array."
  63        split := seq size - r firstIndex.
  64        r contents replaceFrom: 0 below: r firstIndex with: seq &startingAt: split.
  65        r contents replaceFrom: newFirstIndex below: r contents size with: seq]
  66     ifFalse: [r contents replaceFrom: newFirstIndex below: r firstIndex with: seq].
  67   "Finally, update the firstIndex."
  68   r firstIndex := newFirstIndex.
  69   seq
  70 ].