requires: {#Sequence. #ExtensibleCollection}.
provides: {#ExtensibleSequence. #Stack}.

collections addSlot: #ExtensibleSequence
  valued: (Sequence deriveWith: {ExtensibleCollection}).
"An Extensible Sequence implemented by an array with padding on both ends for
the contents."
ExtensibleSequence addSlot: #contents valued: {}.
"The Array used for storage."
ExtensibleSequence addSlot: #firstIndex valued: 0.
"The first index of the array which contains the Sequence' contents."
ExtensibleSequence addSlot: #lastIndex valued: -1.
"The last index of the array which contains the Sequence' contents."

es@(ExtensibleSequence traits) newEmpty
[
  es newSize: 4
].

es@(ExtensibleSequence traits) newSize: capacity
[| newES |
  newES: es clone.
  newES contents: (es contents newSize: capacity).
  newES
].

es@(ExtensibleSequence traits) size
[
  es lastIndex - es firstIndex + 1
].

es@(ExtensibleSequence traits) capacity
[
  es contents size
].

es@(ExtensibleSequence traits) at: index
[
  es contents at: es firstIndex + index
].

es@(ExtensibleSequence traits) at: index put: value
[
  es contents
    at: es firstIndex + index
    put: value
].

es@(ExtensibleSequence traits) clear
"Resets to the values for being empty. lastIndex is -1 to coordinate with the
size method and addLast:."
[
  es firstIndex: 0.
  es lastIndex: -1.
  es
].

es@(ExtensibleSequence traits) copy
[| newES |
  newES: es clone.
  newES contents: es contents clone.
  newES
].

es@(ExtensibleSequence traits) copyFrom: start to: end
[| newES |
  end < start ifTrue: [^ es newEmpty].
  newES: (es newSize: end + 1 - start).
  start to: end do: [| :index | newES addLast: (es at: index)].
  newES
].

es@(ExtensibleSequence traits) copyReplaceFrom: start to: end with: c
"Performs an insert or append as necessary if the replacing collection doesn't
fit in the bounds. eg start < 0 prepends, start > size appends."
[| newES delta startIndex endIndex ess cs |
  delta: 0.
  ess: es size.
  cs: c size.
  start < 0 ifTrue: [startIndex: (endIndex: 0)]
    ifFalse: [
      endIndex: end.
      (startIndex: start) > ess
        ifTrue: [startIndex: (endIndex: size + 1)]
        ifFalse: [(endIndex < (startIndex - 1) or: [endIndex > (ess - 1)])
          ifTrue: [^ Nil].
        delta: endIndex - startIndex + 1]].
  newES: (c newSize: ess + cs - delta).
  0 below: startIndex do: [| :index | newES add: (es at: index)].
  0 below: cs do: [| :index |
    newES add: (c at: index)].
  endIndex + 1 below: ess do: [| :index |
    newES add: (es at: index)].
  newES
].

es@(ExtensibleSequence traits) copyWith: obj
"Non-destructively append."
[| newES |
  (newES: es copy) addLast: obj.
  newES
].

es@(ExtensibleSequence traits) reversed
[| newC |
  newC: c newSameSize.
  c reverseDo: [| :obj |
    newC addLast: obj].
  newC
].

es@(ExtensibleSequence traits) growFirst
"Provide a larger array and map the contents in to yield more growth area at
the beginning. The growth factor is 2."
[| newContents offset |
  es lastIndex >= (es capacity - 1)
    ifTrue:
      [newContents: (es contents newSize: es capacity * 2)]
    ifFalse:
      [newContents: es contents].
  offset: newContents size - es lastIndex - 1.
  es lastIndex
    downTo: es firstIndex
    do:
      [| :index |
        newContents 
          at: index + offset
          put: (es contents at: index)
      ].
  es firstIndex: es firstIndex + offset.
  es lastIndex: es lastIndex + offset.
  es contents: newContents
].

es@(ExtensibleSequence traits) growLast
"Provide a larger array and map the contents in to yield more growth area at
the end. The growth factor is 2."
[| newContents |
  es firstIndex = 0
    ifTrue:
      [newContents: (es contents newSize: es capacity * 2)]
    ifFalse:
      [newContents: es contents].
  es firstIndex
    upTo: es lastIndex
    do:
      [| :index |
        newContents
          at: index - es firstIndex
          put: (es contents at: index)
      ].
  es lastIndex: es lastIndex - es firstIndex.
  es firstIndex: 0.
  es contents: newContents
].

es@(ExtensibleSequence traits) grow
[es growLast].

es@(ExtensibleSequence traits) addFirst: obj
[| firstIndex |
  (firstIndex: es firstIndex) = 0 ifTrue: [es growFirst].
  es firstIndex: es firstIndex - 1.
  es contents at: es firstIndex put: obj.
  obj
].

es@(ExtensibleSequence traits) addLast: obj
[
  es lastIndex + 1 < es capacity ifFalse: [es growLast].
  es lastIndex: es lastIndex + 1.
  es contents at: es lastIndex put: obj.
  obj
].

es@(ExtensibleSequence traits) add: obj
[
  es addLast: obj
].

es@(ExtensibleSequence traits) add: obj after: member
[| index |
  (index: (es find: member)) ifNil: [^ Nil].
  es insert: obj before: index + 1.
  obj
].

es@(ExtensibleSequence traits) add: obj afterIndex: n
[
  es insert: obj before: es firstIndex + index.
  obj
].

es@(ExtensibleSequence traits) add: obj before: member
[| index |
  (index: (es find: member)) ifNil: [^ Nil].
  es insert: obj before: index.
  obj
].

es@(ExtensibleSequence traits) addAll: c
[
  es addAllLast: c
].

es@(ExtensibleSequence traits) addAllFirst: seq
[
  seq reverseDo: [| :each | es addFirst: each].
  seq
].

es@(ExtensibleSequence traits) addAllLast: seq
[
  seq do: [| :each | es addLast: each].
  seq
].

es@(ExtensibleSequence traits) remove: obj ifAbsent: block
[| index |
  index: es firstIndex.
  [index <= es lastIndex] whileTrue:
    [obj = (es contents at: index)
      ifTrue: [es contents replaceFrom: index to: es lastIndex - 1
          with: es contents startingAt: index + 1.
          es contents at: es lastIndex pu: Nil.
          es lastIndex: es lastIndex - 1.
          ^ obj]
      ifFalse: [index: index + 1]].
  block value
].

es@(ExtensibleSequence traits) removeAllSuchThat: block
[| n |
  (n: es firstIndex) to: es lastIndex do: [| :index |
    (block value: (es contents at: index)) ifFalse:
      [es contents at: n put: (es at: index).
       n: n + 1]].
  n to: es lastIndex do: [| :index |
    es contents at: index put: Nil].
  es lastIndex: n - 1.
  es
].

es@(ExtensibleSequence traits) removeAt: index
[| removed localIndex |
  removed: (es at: index).
  localIndex: index + es firstIndex.
  es contents replaceFrom: localIndex - 1 to: es lastIndex - 1
      with: es contents startingAt: localIndex.
  es contents at: es lastIndex put: Nil.
  es lastIndex: es lastIndex - 1.
  es
].

es@(ExtensibleSequence traits) removeFirst
[| firstObj |
  es isEmpty ifTrue: [^ Nil].
  firstObj: (es contents at: es firstIndex).
  es contents at: es firstIndex put: Nil.
  es firstIndex: es firstIndex + 1.
  firstObj
].

es@(ExtensibleSequence traits) removeLast
[| lastObj |
  es isEmpty ifTrue: [^ Nil].
  lastObj: (es contents at: es lastIndex).
  es contents at: es lastIndex put: Nil.
  es lastIndex: es lastIndex - 1.
  lastObj
].

es@(ExtensibleSequence traits) collect: block
"Override to use addLast: vice at:put:."
[| newC |
  newC: es newSameSize.
  es firstIndex to: es lastIndex do: [| :index |
    newC addLast: (block value: (es contents at: index))].
  newC
].

es@(ExtensibleSequence traits) collect: block from: start to: end
"Override to use addLast: vice at:put:."
[| newC |
  (start < 0 or: [end + es firstIndex - 1]) ifTrue: [^ Nil].
  newC: (es newSize: end - start + 1).
  es firstIndex + start - 1 to: es firstIndex + end - 1 do: [| :index |
    newC addLast: (block value: (es at: index))].
  newC
].

es@(ExtensibleSequence traits) do: block
[| index limit |
  index: es firstIndex.
  limit: es lastIndex.
  [index <= limit]
    whileTrue: [block value: (es at: index).
      index: index + 1].
  es
].

es@(ExtensibleSequence traits) reverseDo: block
[| index |
  index: es lastIndex.
  [index >= es firstIndex]
    whileTrue: [block value: (es at: index).
      index: index - 1].
  es
].

es@(ExtensibleSequence traits) select: block
[| newC elem |
  newC: es traits newEmpty.
  es firstIndex to: es lastIndex do: [| :index |
    (block value: (elem: (es contents at: index)))
      ifTrue: [newC addLast: elem]].
  newC
].

es@(ExtensibleSequence traits) with: seq collect: binBlock
[| newC |
  newC: (es newSize: (es size min: seq size)).
  0 below: newC capacity do: [| :index |
    newC addLast: (binBlock value: (es at: index) value: (seq at: index))].
  newC
].

es@(ExtensibleSequence traits) collectWithIndex: binBlock
"Override to use addLast: vice at:put:."
[| newC |
  newC: es newSameSize.
  es firstIndex to: es lastIndex do: [| :index |
    newC addLast: (binBlock value: (es contents at: index) value: index - es firstIndex + 1)].
  newc
].

es@(ExtensibleSequence traits) find: obj
[| index |
  index: es firstIndex.
  [index <= es lastIndex] whileTrue:
    [(es contents at: index) = obj ifTrue: [^ index].
      index: index + 1].
  Nil
].

es@(ExtensibleSequence traits) insert: obj before: index
[
  (es firstIndex > 0 and: [index = es firstIndex])
    ifTrue: 
      [es firstIndex: es firstIndex - 1.
        ^ (es contents at: es firstIndex put: obj)].
  es lastIndex + 1 < es capacity 
    ifFalse: [es growLast].
  index > es lastIndex
    ifTrue: 
      [es lastIndex: es lastIndex + 1.
        ^ (es contents at: es lastIndex put: obj)].
  es contents
    replaceFrom: index + 1
    to: es lastIndex + 1
    with: es contents
    startingAt: index.
  es lastIndex: es lastIndex + 1.
  es contents at: index put: obj
].

es@(ExtensibleSequence traits) move: obj to: index
"Re-position the object so that it has the given index, and slide up/down other
objects as needed."
[| src tgt |
  src: (es find: obj).
  tgt: index + es startIndex.
  src ifNil: [^ Nil].
  src = tgt
    ifTrue: [^ es].
  src > tgt
    ifTrue: [es contents
      replaceFrom: tgt + 1
      to: src
      with: es contents
      startingAt: tgt]
    ifFalse: [es contents
      replaceFrom: src
      to: es contents lastIndex
      with: es contents
      startingAt: src + 1].
  es contents at: tgt put: obj.
  es
].

prototypes addSlot: #Stack.
prototypes Stack: ExtensibleSequence derive.

s@(Stack traits) push: obj
[
  s addLast: obj
].

s@(Stack traits) pop
[
  s removeLast
].

s@(Stack traits) top
[
  s last
].

s@(Stack traits) bottom
[
  s first
].

s@(Stack traits) bottomToTopDo: block
[
  s do: block
].

s@(Stack traits) topToBottomDo: block
[
  s reverseDo: block
].