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."
5 is@(InsertionSequence traits) insertionPoint
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."
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.
28 is@(InsertionSequence traits) gapSize
30 is gapEnd - is gapStart
33 is@(InsertionSequence traits) isFull
38 is@(InsertionSequence traits) growTo: capacity
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)].
47 is gapEnd := is gapEnd + shift.
51 is@(InsertionSequence traits) grow
53 is growTo: is growSize
56 is@(InsertionSequence traits) at: n
59 ifTrue: [is contents at: n]
60 ifFalse: [is contents at: n + is gapSize]
63 is@(InsertionSequence traits) at: n put: obj
66 ifTrue: [is contents at: n put: obj]
67 ifFalse: [is contents at: n + is gapSize put: obj]
70 is@(InsertionSequence traits) insert: obj
72 is isFull ifTrue: [is grow].
73 is contents at: is gapStart put: obj.
74 is gapStart := is gapStart + 1.
78 is@(InsertionSequence traits) insertAll: c
80 is gapSize > (cs ::= c size)
82 growSize := cs - is gapSize.
84 ifFalse: [c doWithIndex:
86 is contents at: index + is gapStart put: each].
87 is gapStart := is gapStart + cs].
91 is@(InsertionSequence traits) add: obj after: index
93 is insertionPoint := index.
97 is@(InsertionSequence traits) do: block
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)].
104 is@(InsertionSequence traits) reverseDo: block
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)].
111 is@(InsertionSequence traits) doWithIndex: block
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].