src/lib/linkedlist.slate

   1 define: #LinkedCollection &parents: {Collection}.
   2 "LinkedCollections are those whose elements include state that encodes the
   3 collection's structure. This includes linked-lists, trees, and graphs. The
   4 collection types may or may not have a facade object which is different from
   5 the elements and may keep track of circularities or such.
   6
   7 The general axioms for LinkedCollections are that they must be singly-
   8 connected (it's a topology term for all-in-one-piece), and that the results of
   9 'c add: a' or 'c remove: a' will side-effect 'a'. Or if add: and remove: are
  10 not defined, consider it in terms of the change between include: results
  11 changing."
  12
  13 lc@(LinkedCollection traits) new
  14 "Links cannot be pre-allocated simply by overall size. This generally
  15 doesn't need to be overridden unless the collection type uses a facade."
  16 [
  17   lc clone clear
  18 ].
  19
  20 lc@(LinkedCollection traits) clear
  21 "Cut off all the links. Override this for each collection type."
  22 [overrideThis].
  23
  24 define: #Link &slots: {#next. #previous}.
  25 "A Link is a kind of mixin that can be added to ordinary objects to allow
  26 them to refer to other Link-mixed objects as a binary-linked structure.
  27 A Link being at an end is represented by an adjacency set to that same Link."
  28
  29 define: #LinkedList &parents: {Link. LinkedCollection. ExtensibleSequence}.
  30 "A LinkedList is a Link extended to be an ExtensibleSequence of Links."
  31
  32 l@(LinkedList traits) clear
  33 "An empty LinkedList circularly points to itself."
  34 [
  35   l next := l.
  36   l previous := l.
  37   l
  38 ].
  39
  40 l@(LinkedList traits) new
  41 [
  42   l clone `>> [clear. ]
  43 ].
  44
  45 ll@(LinkedList traits) accepts: link@(Link traits)
  46 "LinkedList expects Link elements, although it is not necessary for it to
  47 reject non-Link elements if they respond to the protocol logically."
  48 [True].
  49
  50 ll@(LinkedList traits) do: block
  51 [| link |
  52   link := ll next.
  53   [link == ll]
  54     whileFalse:
  55       [| each |
  56         each := link.
  57         link := link next.
  58         block applyWith: each]
  59 ].
  60
  61 ll@(LinkedList traits) reverseDo: block
  62 [| link |
  63   link := ll previous.
  64   [link == ll]
  65     whileFalse:
  66       [| each |
  67         each := link.
  68         link := link previous.
  69         block applyWith: each]
  70 ].
  71
  72 ll@(LinkedList traits) isEmpty [ll next == ll].
  73
  74 ll@(LinkedList traits) first [ll next].
  75 ll@(LinkedList traits) last [ll previous].
  76
  77 ll@(LinkedList traits) at: index
  78 [| position |
  79   position := ll next.
  80   index
  81     timesRepeat: [position := position next].
  82   position
  83 ].
  84
  85 ll@(LinkedList traits) after: link
  86 [
  87   link next == ll ifTrue: [Nil] ifFalse: [link next]
  88 ].
  89
  90 ll@(LinkedList traits) before: link
  91 [
  92   link previous == ll ifTrue: [Nil] ifFalse: [link previous]
  93 ].
  94
  95 ll@(LinkedList traits) add: newObject
  96 [ll addLast: newObject].
  97
  98 ll@(LinkedList traits) add: newObject before: oldObject
  99 [
 100   newObject next := oldObject.
 101   newObject previous := oldObject previous.
 102   oldObject previous := newObject.
 103   newObject previous next := newObject.
 104   newObject
 105 ].
 106
 107 ll@(LinkedList traits) add: newObject after: oldObject
 108 [
 109   ll add: newObject before: oldObject next
 110 ].
 111
 112 ll@(LinkedList traits) addFirst: newObject
 113 [
 114   ll add: newObject before: ll first
 115 ].
 116
 117 ll@(LinkedList traits) addLast: newObject
 118 [
 119   ll add: newObject after: ll last
 120 ].