collections addPrototype: #InsertionSequence derivedFrom: {ExtensibleArray}.
"This collection type is optimized for insertions into the sequence in the
middle or at the ends. A gap is maintained for growth space."
InsertionSequence addSlot: #gapStart valued: 0.
InsertionSequence addSlot: #gapEnd valued: 0.
InsertionSequence addSlot: #contents valued: {}.

is@(InsertionSequence traits) insertionPoint
[
  is gapStart
].

is@(InsertionSequence traits) insertionPoint: n
"This handles movement of the insertion point, and automatically shuffles
around the contents to handle it, so should only be used when necessary.
If the gap is empty, don't do anything but shift around the start and end."
[| numToMove |
  is gapSize = 0 ifTrue: [
    ^ (is gapStart: (is gapEnd: n))].
  numToMove: is gapStart - n.
  numToMove positive
    ifTrue: ["Shift the elements to the right, moving the gap to the left."
      n below: is gapEnd do: [| :index |
        is contents at: index + numToMove put: (is contents at: index)]]
    ifFalse: ["Shift the elements to the left, moving the gap to the right."
      is gapEnd + numToMove below: is gapEnd do: [| :index |
        is contents at: is gapEnd + index put: (is contents at: index)]].
  is gapEnd: is gapEnd - numToMove.
  is gapStart: n
].

is@(InsertionSequence traits) gapSize
[
  is gapEnd - is gapStart
].

is@(InsertionSequence traits) isFull
[
  is gapSize = 0
].

is@(InsertionSequence traits) growTo: capacity
[| newC shift |
  newC: (is contents newSize: capacity).
  shift: capacity - is contents size.
  0 below: is gapStart do:
    [| :index | newC at: index put: (is contents at: index)].
  is gapEnd below: is contents size do:
    [| :index | newC at: index + shift put: (is contents at: index)].
  is contents: newC.
  is gapEnd: is gapEnd + shift.
  is
].

is@(InsertionSequence traits) grow
[
  is growTo: is growSize
].

is@(InsertionSequence traits) at: n
[
  n < is gapStart
    ifTrue: [is contents at: n]
    ifFalse: [is contents at: n + is gapSize]
].

is@(InsertionSequence traits) at: n put: obj
[
  n < is gapStart
    ifTrue: [is contents at: n put: obj]
    ifFalse: [is contents at: n + is gapSize put: obj]
].

is@(InsertionSequence traits) insert: obj
[
  is isFull ifTrue: [is grow].
  is contents at: is gapStart put: obj.
  is gapStart: is gapStart + 1.
  obj
].

is@(InsertionSequence traits) insertAll: c
[| cs |
  cs: c size.
  is gapSize > cs
    ifTrue: [| growSize |
      growSize: cs - is gapSize.
      ]
    ifFalse: [c doWithIndex: [| :each :index |
      is contents at: index + is gapStart put: each].
      is gapStart: is gapStart + cs].
  c
].

is@(InsertionSequence traits) add: obj after: index
[
  is insertionPoint: index.
  is insert: obj
].

is@(InsertionSequence traits) do: block
[
  0 below: is gapStart do: [| :index | block applyWith: (contents at: index)].
  is gapEnd below: is size do: [| :index | block applyWith: (contents at: index)].
  is
].

is@(InsertionSequence traits) reverseDo: block
[
  is size above: is gapEnd do: [| :index | block applyWith: (contents at: index)].
  is gapStart - 1 downTo: 0 do: [| :index | block applyWith: (contents at: index)].
  is
].

is@(InsertionSequence traits) doWithIndex: block
[
  0 below: is gapStart do: [| :index |
    block applyWith: (contents at: index) with: index].
  is gapEnd below: is size do: [| :index |
    block applyWith: (contents at: index) with: index].
  is
].