requires: {#ExtensibleSequence}.
provides: {#SortedSequence}.

prototypes addSlot: #SortedSequence valued: ExtensibleSequence derive.
SortedSequence addSlot: #sortBlock valued: [| :x :y | x <= y].

c@(Collection traits) sort
[| newSC |
  newSC: (SortedSequence newSizeOf: c).
  newSC addAll: c.
  newSC
].

c@(Collection traits) sortBy: block
[| newSC |
  newSC: (SortedSequence newSizeOf: c).
  newSC sortBlock: block.
  newSC addAll: c.
  newSC
].

sc@(SortedSequence traits) at: index put: obj
[
  sc shouldNotImplement
].

sc@(SortedSequence traits) median
[
  sc at: sc size + 1 // 2
].

sc@(SortedSequence traits) add: obj
[
  sc insert: obj before: (sc indexForInserting: obj)
].

sc@(SortedSequence traits) addAll: c
"If the number of elements to add is great enough, add the elements unsafely,
and then sort. Otherwise, add each in turn."
[
  c size > (sc size // 3)
    ifTrue: [c do: [| :each |
        #addLast: sendTo: {sc. each} through: {ExtensibleSequence. each}].
      sc reSort]
    ifFalse: [c do: [| :each | sc add: each]].
  c
].

sc@(SortedSequence traits) addFirst: obj
"Perform the minimal check that this would be the least object."
[
  (sc isEmpty not and: [sc sortBlock values: {obj. sc first}])
    ifFalse: [sc outOfOrder].
  resend
].

sc@(SortedSequence traits) addLast: obj
"Perform the minimal check that this would be the greatest object."
[
  (sc isEmpty not and: [sc sortBlock values: {sc last. obj}])
    ifFalse: [sc outOfOrder].
  resend
].

sc@(SortedSequence traits) = sc2@(SortedSequence traits)
[
  sc sortBlock = sc2 sortBlock and: [resend].
].

sc@(SortedSequence traits) copy
"Make a new SortedSequence with the same sortBlock. Since we know the order
will not change, use the minimally-checking addLast: method vice addAll:."
[| newC |
  newC: sc newSameSize.
  newC do: [| :each | newC addLast: each].
  newC
].

sc@(SortedSequence traits) copyWith: obj
"Non-destructively append, but don't use addLast: as ExtensibleSequence does."
[| newC |
  (newC: sc copy) add: obj.
  newC
].

sc@(SortedSequence traits) copyFrom: start to: end
"Copy the range into a new SortedSequence which keeps the same sortBlock."
[| newC |
  end < start ifTrue: [^ sc newEmpty].
  newC: (sc newSize: end - start + 1).
  start to: end do: [| :index | newC addLast: (sc at: index)].
  newC
].

sc@(SortedSequence traits) reversed
[| newC |
  newC: resend.
  newC sortBlock: sc sortBlock converse.
  newC
].

sc@(SortedSequence traits) collect: block
"Override in order to return an ExtensibleSequence instead of a SortedSequence."
[| newC |
  newC: (ExtensibleSequence newSizeOf: sc).
  sc do: [| :each | newC addLast: (block value: each)].
  newC
].

sc@(SortedSequence traits) indexOf: obj ifAbsent: block
[| index low high |
  low: sc firstIndex.
  high: sc lastIndex.
  [index: high + low // 2. low > high]
    whileFalse: [(sc contents at: index) = object
      ifTrue: [^ index].
      (sc sortBlock value: (sc contents at: index) value: obj)
        ifTrue: [low: index + 1]
        ifFalse: [high: index - 1]].
  block value
].

sc@(SortedSequence traits) indexForInserting: obj
[| index low high |
  low: sc firstIndex.
  high: sc lastIndex.
  [index: high + low // 2. low > high]
    whileFalse: [(sc sortBlock value: (sc contents at: index) value: obj)
      ifTrue: [low: index + 1]
      ifFalse: [high: index - 1]].
  low
].

sc@(SortedSequence traits) sort: start to: end
[| low high pivot |
  start >= end ifTrue: [^ sc].
  low: start.
  high: end.
  pivot: (sc contents at: start).
  [low < high]
    whileTrue:
      [
        [low >= high
          or:
            [sc sortBlock
              value: pivot
              value: (sc contents at: low)]]
          whileFalse:
            [low: low + 1].
        [low < high
          and:
            [sc sortBlock
              value: pivot
              value: (sc contents at: high)]]
          whileTrue:
            [high: high - 1].
        low < high
          ifTrue:
            [sc contents swap: low with: high].
      ].
  low > start
    ifTrue:
      [
        (sc sortBlock value: (sc contents at: low - 1) value: (sc contents at: low))
          ifFalse: [sc contents swap: low with: low - 1].
        sc sort: start to: low - 1
      ].
  low < end
    ifTrue:
      [
        (sc sortBlock value: (sc contents at: low + 1) value: (sc contents at: low))
          ifTrue: [sc contents swap: low with: low + 1].
        sc sort: low + 1 to: end
      ].
  sc
].

sc@(SortedSequence traits) reSort
[
  sc sort: sc firstIndex to: sc lastIndex
].