collections addSlot: #InsertionSequence valued: ExtensibleSequence derive.
InsertionSequence addSlot: #gapStart valued: 0.
InsertionSequence addSlot: #gapEnd valued: 0.
InsertionSequence addSlot: #contents valued: ExtensibleSequence newEmpty.

"This collection type is optimized for insertions into the sequence in the
middle or at the ends. A gap is maintained for growth space."

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) 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 gapSize = 0
    ifTrue: []
    ifFalse: [is contents at: gapStart put: obj.
      is gapStart: isgapStart + 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 + gapStart put: each].
      is gapStart: is gapStart + cs].
  c
].

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

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

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