src/lib/queue.slate

   1 define: #Queue &parents: {ArrayBacked}
   2 "A Queue is an ExtensibleSequence designed to use its underlying Array in a
   3 wrap-around manner, maintaining a (moving) gap for efficient extension to
   4 either end of the Queue."
   5 &slots: {#firstIndex -> 0.
   6 "The lower inclusive bound of the used section of the Array."
   7 #lastIndex -> 0
   8 "The upper exclusive bound of the used section of the Array (the address of
   9 the first non-Queue element); if this is less than the firstIndex, then the
  10 contents themselves surround a gap."
  11 }.
  12
  13 q@(Queue traits) clear
  14 [
  15   resend.
  16   q firstIndex := 0.
  17   q lastIndex := 0.
  18   q
  19 ].
  20
  21 q@(Queue traits) new &capacity: n
  22 "The Queue always maintains atleast one unusable sentinel element so that
  23 all n requested elements may fit without lastIndex = firstIndex (the empty
  24 condition) occurring."
  25 [n ifNotNil: [n += 1]. resend clear].
  26
  27 s@(Sequence traits) as: es@(Queue traits)
  28 "Likewise, we have to protect the buggy coding of whoever wrote this class."
  29 [
  30   es new `>> [contents := s arrayType newSize: s length + 1.
  31               addAll: s. ]
  32 ].
  33
  34
  35 q@(Queue traits) isFull
  36 "The Queue is full if the indices span the whole array or are adjacent."
  37 [
  38   q firstIndex = 0
  39    /\ [q contents size - 1 = q lastIndex]
  40    \/ [q lastIndex + 1 = q firstIndex]
  41 ].
  42
  43 q@(Queue traits) isEmpty
  44 "The Queue is empty if the indices are equal."
  45 [
  46   q lastIndex = q firstIndex
  47 ].
  48
  49 q@(Queue traits) isSplit
  50 "Whether the contents are split into two pieces or contiguous."
  51 [
  52   q lastIndex < q firstIndex
  53 ].
  54
  55 q@(Queue traits) gapSize
  56 "How many elements can be added to fill the Queue Array."
  57 [
  58   q isSplit
  59     ifTrue: [q firstIndex - q lastIndex - 1]
  60     ifFalse: [q contents size - q lastIndex + q firstIndex - 1]
  61 ].
  62
  63 q@(Queue traits) capacity
  64 [
  65   q contents size - 1
  66 ].
  67
  68 q@(Queue traits) size
  69 [
  70   q isSplit
  71     ifTrue: [q contents size - q firstIndex + q lastIndex]
  72     ifFalse: [q lastIndex - q firstIndex]
  73 ].
  74
  75 q@(Queue traits) growTo: n
  76 "Provide a new Array of the appropriate capacity and transfer the contents
  77 and adjust the indices to match, then replace the old one."
  78 [| newContents |
  79   n <= (q gapSize + q size) ifTrue: [error: 'The contents will not fit.'].
  80   newContents := q contents new &capacity: n + 1.
  81   q isSplit
  82     ifTrue:
  83       [| offset |
  84        offset := newContents size - q contents size.
  85        newContents replaceFrom: 0 to: q lastIndex with: q contents.
  86        newContents replaceFrom: q firstIndex + offset below: newContents size with: q contents &startingAt: q firstIndex.
  87        q firstIndex := q firstIndex + offset]
  88     ifFalse:
  89       [newContents replaceFrom: q firstIndex to: q lastIndex with: q contents &startingAt: q firstIndex].
  90   q contents := newContents.
  91   q
  92 ].
  93
  94 q@(Queue traits) at: n
  95 "The firstIndex is treated as the 0 address. Wrap-around is handled."
  96 [| index |
  97   (index := q firstIndex + n) >= q contents size
  98     ifTrue: [index -= q contents size].
  99   q contents at: index
 100 ].
 101
 102 q@(Queue traits) at: n put: obj
 103 "The firstIndex is treated as the 0 address. Wrap-around is handled."
 104 [| index |
 105   (index := q firstIndex + n) >= q contents size
 106     ifTrue: [index -= q contents size].
 107   q contents at: index put: obj
 108 ].
 109
 110 q@(Queue traits) do: block
 111 [
 112   q isSplit
 113     ifTrue: [q contents from: q firstIndex to: q contents size - 1 do: block.
 114              q contents from: 0 to: q lastIndex do: block]
 115     ifFalse: [q contents from: q firstIndex to: q lastIndex do: block]
 116 ].
 117
 118 q@(Queue traits) addLast: obj
 119 [
 120   q isFull ifTrue: [q grow].
 121   q contents at: q lastIndex put: obj.
 122   q lastIndex: q lastIndex + 1 \\ q contents size.
 123   obj
 124 ].
 125
 126 q@(Queue traits) addFirst: obj
 127 [
 128   q isFull ifTrue: [q grow].
 129   q contents
 130     at: (q firstIndex := q firstIndex - 1 \\ q contents size)
 131     put: obj.
 132   obj
 133 ].
 134
 135 q@(Queue traits) addAllLast: seq
 136 [| newLastIndex |
 137   "Make room for the sequence as necessary."
 138   seq size > q gapSize ifTrue: [q growBy: seq size].
 139   "The new lastIndex after all the elements are added."
 140   newLastIndex := q lastIndex + seq size \\ q contents size.
 141   "Whether adding the elements to the end will push the lastIndex past the
 142    underlying Array's end."
 143   newLastIndex < q lastIndex
 144     ifTrue:
 145       [| split |
 146        "The number of elements that will fit before wrap-around."
 147        split := q contents size - q lastIndex.
 148        q contents replaceFrom: q lastIndex below: q contents size with: seq.
 149        q contents replaceFrom: 0 below: seq size - split with: seq &startingAt: split]
 150     ifFalse: [q contents replaceFrom: q lastIndex below: newLastIndex with: seq].
 151   "Finally, update the lastIndex."
 152   q lastIndex := newLastIndex.
 153   seq
 154 ].
 155
 156 q@(Queue traits) addAllFirst: seq
 157 [| newFirstIndex |
 158   "Make room for the sequence as necessary."
 159   seq size > q gapSize ifTrue: [q growTo: q contents size + seq size].
 160   "The new firstIndex after all the elements are added."
 161   newFirstIndex := q firstIndex - seq size \\ q contents size.
 162   "Whether adding the elements to the end will push the firstIndex past the
 163    underlying Array's start."
 164   newFirstIndex > q firstIndex
 165     ifTrue:
 166       [| split |
 167        "The number of elements that will need to be added at the end of the Array."
 168        split := seq size - q firstIndex.
 169        q contents replaceFrom: 0 below: q firstIndex with: seq &startingAt: split.
 170        q contents replaceFrom: newFirstIndex below: q contents size with: seq]
 171     ifFalse: [q contents replaceFrom: newFirstIndex below: q firstIndex with: seq].
 172   "Finally, update the firstIndex."
 173   q firstIndex := newFirstIndex.
 174   seq
 175 ].
 176
 177 q@(Queue traits) removeLast
 178 [| result |
 179   q lastIndex := q lastIndex - 1 \\ q contents size.
 180   result := q contents at: q lastIndex.
 181   q contents at: q lastIndex put: Nil.
 182   result
 183 ].
 184
 185 q@(Queue traits) removeFirst
 186 [| oldIndex result |
 187   q firstIndex := (oldIndex := q firstIndex) + 1 \\ q contents size.
 188   result := q contents at: oldIndex.
 189   q contents at: oldIndex put: Nil.
 190   result
 191 ].
 192
 193 q@(Queue traits) removeLast: n
 194 [| removed newLastIndex |
 195   removed := q contents new &capacity: n.
 196   newLastIndex := q lastIndex - n \\ q contents size.
 197   "Whether removing the N elements will push the lastIndex past the underlying
 198    Array's start."
 199   newLastIndex > q lastIndex
 200     ifTrue: [| split |
 201              split := n - q lastIndex.
 202              removed replaceFrom: split below: n with: q contents.
 203              removed replaceFrom: 0 below: split with: q contents &startingAt: q contents size - split.
 204              "Clear the contents Array at the removed locations."
 205              0 below: n - split do: [| :i | q contents at: i put: Nil].
 206              newLastIndex below: q contents size do: [| :i | q contents at: i put: Nil]]
 207     ifFalse: [removed replaceFrom: 0 below: removed size with: q contents &startingAt: q lastIndex.
 208               newLastIndex below: q lastIndex do: [| :index | q contents at: index put: Nil]].
 209   "Finally, update the firstIndex."
 210   q forgetLast: n.
 211   removed
 212 ].
 213
 214 q@(Queue traits) removeFirst: n
 215 [| removed newFirstIndex |
 216   removed := q contents new &capacity: n.
 217   newFirstIndex := q firstIndex + n \\ q contents size.
 218   "Whether removing the first N elements will push the firstIndex past the
 219   underlying Array's end."
 220   newFirstIndex < q firstIndex
 221     ifTrue: [| split |
 222              split := q contents size - q firstIndex.
 223              removed replaceFrom: split below: n with: q contents &startingAt: q firstIndex.
 224              removed replaceFrom: 0 below: split with: q contents.
 225              q firstIndex below: q contents size do:
 226                [| :i | q contents at: i put: Nil].
 227              0 below: newFirstIndex do: [| :i | q contents at: i put: Nil]]
 228     ifFalse: [removed replaceFrom: 0 below: n with: q contents &startingAt: q firstIndex.
 229               q firstIndex below: q firstIndex + n do:
 230                 [| :i | q contents at: i put: Nil]].
 231   "Finally, update the firstIndex."
 232   q forgetFirst: n.
 233   removed
 234 ].
 235
 236 q@(Queue traits) forgetFirst: n
 237 [
 238   q firstIndex := q firstIndex + n \\ q contents size.
 239 ].
 240
 241 q@(Queue traits) forgetLast: n
 242 [
 243   q lastIndex := q lastIndex - n \\ q contents size.
 244 ].
 245
 246
 247 q@(Queue traits) remove [q removeFirst].
 248 q@(Queue traits) remove: n [q removeFirst: n].
 249
 250 "Stack-compatible protocol: " (
 251 q@(Queue traits) push: obj [q add: obj].
 252 q@(Queue traits) pop [q remove].
 253 q@(Queue traits) pushAll: c [q addAll: c].
 254 q@(Queue traits) pop: n [q remove: n].
 255 ).