src/lib/sequence-insertable.slate

   1 collections define: #InsertionSequence &parents: {ExtensibleArray} &slots: {#gapStart -> 0. #gapEnd -> 0}.
   2 "This collection type is optimized for insertions into the sequence in the
   3 middle or at the ends. A gap is maintained for growth space."
   4
   5 is@(InsertionSequence traits) insertionPoint
   6 [
   7   is gapStart
   8 ].
   9
  10 is@(InsertionSequence traits) insertionPoint: n
  11 "This handles movement of the insertion point, and automatically shuffles
  12 around the contents to handle it, so should only be used when necessary.
  13 If the gap is empty, don't do anything but shift around the start and end."
  14 [
  15   is isFull ifTrue: [
  16     ^ (is gapStart := is gapEnd := n)].
  17   (numToMove ::= is gapStart - n) positive
  18     ifTrue: ["Shift the elements to the right, moving the gap to the left."
  19       n below: is gapEnd do: [| :index |
  20         is contents at: index + numToMove put: (is contents at: index)]]
  21     ifFalse: ["Shift the elements to the left, moving the gap to the right."
  22       is gapEnd + numToMove below: is gapEnd do: [| :index |
  23         is contents at: is gapEnd + index put: (is contents at: index)]].
  24   is gapEnd := is gapEnd - numToMove.
  25   is gapStart := n
  26 ].
  27
  28 is@(InsertionSequence traits) gapSize
  29 [
  30   is gapEnd - is gapStart
  31 ].
  32
  33 is@(InsertionSequence traits) isFull
  34 [
  35   is gapSize isZero
  36 ].
  37
  38 is@(InsertionSequence traits) growTo: capacity
  39 [
  40   newC ::= is contents new &capacity: capacity.
  41   shift ::= capacity - is contents size.
  42   0 below: is gapStart do:
  43     [| :index | newC at: index put: (is contents at: index)].
  44   is gapEnd below: is contents size do:
  45     [| :index | newC at: index + shift put: (is contents at: index)].
  46   is contents := newC.
  47   is gapEnd := is gapEnd + shift.
  48   is
  49 ].
  50
  51 is@(InsertionSequence traits) grow
  52 [
  53   is growTo: is growSize
  54 ].
  55
  56 is@(InsertionSequence traits) at: n
  57 [
  58   n < is gapStart
  59     ifTrue: [is contents at: n]
  60     ifFalse: [is contents at: n + is gapSize]
  61 ].
  62
  63 is@(InsertionSequence traits) at: n put: obj
  64 [
  65   n < is gapStart
  66     ifTrue: [is contents at: n put: obj]
  67     ifFalse: [is contents at: n + is gapSize put: obj]
  68 ].
  69
  70 is@(InsertionSequence traits) insert: obj
  71 [
  72   is isFull ifTrue: [is grow].
  73   is contents at: is gapStart put: obj.
  74   is gapStart := is gapStart + 1.
  75   obj
  76 ].
  77
  78 is@(InsertionSequence traits) insertAll: c
  79 [
  80   is gapSize > (cs ::= c size)
  81     ifTrue: [| growSize |
  82              growSize := cs - is gapSize.
  83          ]
  84     ifFalse: [c doWithIndex:
  85                 [| :each :index |
  86                  is contents at: index + is gapStart put: each].
  87               is gapStart := is gapStart + cs].
  88   c
  89 ].
  90
  91 is@(InsertionSequence traits) add: obj after: index
  92 [
  93   is insertionPoint := index.
  94   is insert: obj
  95 ].
  96
  97 is@(InsertionSequence traits) do: block
  98 [
  99   0 below: is gapStart do: [| :index | block applyWith: (contents at: index)].
 100   is gapEnd below: is size do: [| :index | block applyWith: (contents at: index)].
 101   is
 102 ].
 103
 104 is@(InsertionSequence traits) reverseDo: block
 105 [
 106   is size above: is gapEnd do: [| :index | block applyWith: (contents at: index)].
 107   is gapStart - 1 downTo: 0 do: [| :index | block applyWith: (contents at: index)].
 108   is
 109 ].
 110
 111 is@(InsertionSequence traits) doWithIndex: block
 112 [
 113   0 below: is gapStart do: [| :index |
 114     block applyWith: (contents at: index) with: index].
 115   is gapEnd below: is size do: [| :index |
 116     block applyWith: (contents at: index) with: index].
 117   is
 118 ].