src/lib/tree.slate

   1 collections define: #OrderedTree
   2   &parents: {LinkedCollection. ExtensibleSequence}
   3   &slots: {#treeParent. "The parent node, Nil for top-level nodes."
   4            #children -> ExtensibleArray new "The sub-nodes."}.
   5 "A Tree node, linking to its parent node and storing its children in a
   6 Sequence."
   7
   8 ot@(OrderedTree traits) clear
   9 [
  10   ot children := ot children new.
  11   ot
  12 ].
  13
  14 ot@(OrderedTree traits) new &capacity: n
  15 [ot clone `setting: #{#children} to: {ot children new &capacity: n}].
  16
  17 ot@(OrderedTree traits) newFor: obj &capacity: n
  18 [(ot new &capacity: n) `>> [add: obj]].
  19
  20 ot@(OrderedTree traits) newForAll: c@(Collection traits)
  21 [ot clone `setting: #{#children} to: {c as: ot children}].
  22
  23 ot@(OrderedTree traits) size [ot children size].
  24
  25 ot@(OrderedTree traits) do: block [ot children do: block].
  26
  27 ot@(OrderedTree traits) at: index [ot children at: index].
  28
  29 ot@(OrderedTree traits) iterator
  30 [ot children iterator].
  31
  32 ot@(OrderedTree traits) reader
  33 [ot children reader].
  34
  35 ot@(OrderedTree traits) writer
  36 "NOTE: If the children object is not Extensible. Otherwise, a new structure
  37 may be constructed which is not placed into the slot implicitly."
  38 [ot children writer].
  39
  40 ot@(OrderedTree traits) siblings
  41 "Return all children of the node's parent, excepting the original node.
  42 Answer Nil if there is no parent or the wrong parent."
  43 [
  44   ot treeParent
  45     ifNil: [ExtensibleArray new]
  46     ifNotNilDo: [| :p | p children copy `>> [remove: ot ifAbsent: [^ Nil]. ]]
  47 ].
  48
  49 ot@(OrderedTree traits) previousSibling
  50 [ot treeParent ifNotNilDo: [| :p | p children before: ot]].
  51
  52 ot@(OrderedTree traits) nextSibling
  53 [ot treeParent ifNotNilDo: [| :p | p children after: ot]].
  54
  55 ot@(OrderedTree traits) raise
  56 "Moves this tree element to the first in the collection list of the parent -
  57 relies on being able to directly manipulate that collection."
  58 [
  59   ot treeParent children move: ot to: ot children indexFirst.
  60 ].
  61
  62 ot@(OrderedTree traits) bury
  63 "Moves this tree element to the last in the children list of the parent -
  64 relies on being able to directly manipulate that collection."
  65 [| siblings |
  66   (siblings := ot treeParent children) move: ot to: siblings indexLast.
  67 ].
  68
  69 ch@(OrderedTree traits) reparentTo: ot
  70 "Handle the aspect of unsetting any parent link and backlink as necessary.
  71 Avoid adding to the new parent, since the position matters."
  72 [
  73   ch treeParent ifNotNilDo: #(remove: ch) `er.
  74   ch treeParent := ot.
  75 ].
  76
  77 obj reparentTo: ot@(OrderedTree traits)
  78 [].
  79
  80 ot@(OrderedTree traits) isLeaf: child
  81 "Answer whether the given element would not count as a sub-tree of the
  82 tree if it were a child of it - if it's anything but a tree itself."
  83 [(child is: ot) not].
  84
  85 ot@(OrderedTree traits) at: index put: ch
  86 [
  87   ch reparentTo: ot.
  88   ot children at: index put: ch.
  89   ot
  90 ].
  91
  92 ot@(OrderedTree traits) addFirst: ch
  93 [
  94   ch reparentTo: ot.
  95   ot children addFirst: ch.
  96   ot
  97 ].
  98
  99 ot@(OrderedTree traits) addLast: ch
 100 "Add a tree node as a child, and set the parent back-link."
 101 [
 102   ch reparentTo: ot.
 103   ot children addLast: ch.
 104   ot
 105 ].
 106
 107 ot@(OrderedTree traits) remove: ch
 108 "Remove the tree node as a child, making sure to remove the parent link."
 109 [
 110   ot children remove: ch ifAbsent: [^ Nil].
 111   ch reparentTo: Nil.
 112   ot
 113 ].
 114
 115 ot@(OrderedTree traits) remove: ch ifAbsent: block
 116 [
 117   ot children remove: ch ifAbsent: [block do]
 118 ].