requires: {#Collection. #ExtensibleSequence}.
provides: {#LinkedCollection. #Link. #LinkedList}.

collections addPrototype: #LinkedCollection derivedFrom: {Collection}.

"LinkedCollections are those whose elements include state that encodes the
collection's structure. This includes linked-lists, trees, and graphs. The
collection types may or may not have a facade object which is different from
the elements and may keep track of circularities or such."

"The general axioms for LinkedCollections are that they must be singly-
connected (it's a topology term for all-in-one-piece), and that the results of
'c add: a' or 'c remove: a' will side-effect 'a'. Or if add: and remove: are
not defined, consider it in terms of the change between include: results
changing."

lc@(LinkedCollection traits) newEmpty
"This generally doesn't need to be overridden unless the collection type uses
a facade."
[
  lc clone clear
].

lc@(LinkedCollection traits) clear
"Cut off all the links. Override this for each collection type."
[overrideThis].

lc@(LinkedCollection traits) newSize: _
"Links cannot be pre-allocated simply by overall size."
[
  lc clone clear
].

collections addPrototype: #Link derivedFrom: {Cloneable}.
Link addSlot: #next.
Link addSlot: #previous.

l@(Link traits) clear
[
  l next: l.
  l previous: l.
  l
].

collections addPrototype: #LinkedList
  derivedFrom: {Link. LinkedCollection. ExtensibleSequence}.

ll@(LinkedList traits) do: block
[| link |
  link: ll next.
  [link == ll]
    whileFalse:
      [link: link next.
        block applyWith: link previous]
].

ll@(LinkedList traits) reverseDo: block
[| link |
  link: ll previous.
  [link == ll]
    whileFalse:
      [link: link previous.
        block applyWith: link next]
].

ll@(LinkedList traits) isEmpty [ll next == ll].

ll@(LinkedList traits) first [ll next].
ll@(LinkedList traits) last [ll previous].

ll@(LinkedList traits) at: index
[| position |
  position: ll next.
  index
    timesRepeat: [position: position next].
  position
].

ll@(LinkedList traits) add: newObject
[ll addLast: newObject].

ll@(LinkedList traits) add: newObject before: oldObject
[
  newObject next: oldObject.
  newObject previous: oldObject previous.
  oldObject previous: newObject.
  newObject previous next: newObject.
  newObject
].

ll@(LinkedList traits) add: newObject after: oldObject
[
  ll add: newObject before: oldObject next
].

ll@(LinkedList traits) addFirst: newObject
[
  ll add: newObject before: ll first
].

ll@(LinkedList traits) addLast: newObject
[
  ll add: newObject after: ll last
].