src/lib/traversal.slate

   1 define: #Order.
   2
   3 define: #Priority &parents: {Order}.
   4 "A Stream Priority order specifies the order in which siblings are visited
   5 relative to each other."
   6
   7 Forward ::= Priority clone.
   8 "Standard left-to-right, increasing index traversal of siblings."
   9
  10 Reverse ::= Priority clone.
  11 "Right-to-left, decreasing index reverse traversal of siblings."
  12
  13 LeastToGreatest ::= Priority clone.
  14 GreatestToLeast ::= Priority clone.
  15
  16 define: #Traversal &parents: {Order}.
  17 "A Stream Traversal order specifies when the parent-child boundary is crossed,
  18 e.g. before other siblings or after all siblings."
  19
  20 DepthFirst ::= Traversal clone.
  21 "Recurse through the next element encountered before proceeding on to
  22 following siblings of it."
  23
  24 BreadthFirst ::= Traversal clone.
  25 "Recurse across all siblings at the current level before recursing through
  26 each sibling's children in the same way."
  27
  28 Topological ::= Traversal clone.
  29
  30 define: #Direction &parents: {Order}.
  31 ""
  32
  33 PreOrder ::= Direction clone.
  34 PostOrder ::= Direction clone.
  35
  36 c@(Collection traits) readerTest &priority &direction &traversal
  37 [
  38   c readerWithDirection: direction priority: priority traversal: traversal
  39 ].
  40
  41 c@(Collection traits) readerWithDirection: _ priority: _ traversal: _
  42 "By default, ignore arguments and use the default ReadStream."
  43 [c ReadStream newOn: c].
  44
  45 seq@(Sequence traits) readerWithDirection: _ priority: priority@Reverse traversal: _
  46 "TODO: expand on this.
  47 Don't do explicit reversal, just build it into the Stream type."
  48 [seq ReadStream newOn: seq reversed].
  49
  50 define: #TraversalStream &parents: {ReadStream} &slots:
  51 {#seen -> IdentitySet new. "Remembers seen objects."
  52  #todo -> Stack new. "Should be a LIFO or FIFO."
  53  #childrenBlock -> #reader `er
  54    "Answers a Stream or Collection of the children of each element."}.
  55
  56 s@(TraversalStream traits) on: x &traversal &childrenVia: childrenBlock
  57 "Target the object by making it the contents of the todo Collection.
  58 Set up the traversal order parameters as needed."
  59 [
  60   traversal `defaultsTo: DepthFirst.
  61   s todo :=
  62     s todo as: (traversal caseOf:
  63                   {BreadthFirst -> [Queue].
  64                    DepthFirst -> [Stack]} otherwise: [s todo]).
  65   s todo push: x.
  66   s seen := s seen new.
  67   childrenBlock ifNotNil: [s childrenBlock := childrenBlock].
  68   s
  69 ].
  70
  71 s@(TraversalStream traits) reset
  72 [s seen := s seen new. s todo := s todo new. ].
  73
  74 s@(TraversalStream traits) newOn: x &traversal &childrenVia: childrenBlock
  75 [s clone `>> [reset. on: x &traversal: traversal &childrenVia: childrenBlock. ]].
  76
  77 x@(Root traits) walker &traversal &childrenVia: childrenBlock
  78 "Answers a new TraversalStream targetted to the argument with the given
  79 order and recursion method."
  80 [TraversalStream newOn: x &traversal: traversal &childrenVia: childrenBlock].
  81
  82 s@(TraversalStream traits) traversalOrder
  83 [
  84   (s todo isSameAs: Queue)
  85     ifTrue: [BreadthFirst]
  86     ifFalse: [(s todo isSameAs: Stack) ifTrue: [DepthFirst]]
  87 ].
  88
  89 s@(TraversalStream traits) hasAnEnd [True].
  90
  91 s@(TraversalStream traits) isAtEnd
  92 "The end is reached when the todo list is emptied."
  93 [s todo isEmpty].
  94
  95 s@(TraversalStream traits) cannotVisit: obj
  96 "Whether the particular object should be entirely avoided. TODO: remove?"
  97 [False].
  98
  99 s@(TraversalStream traits) visit: obj
 100 "Mark the object as seen/visited."
 101 [s seen include: obj].
 102
 103 s@(TraversalStream traits) alreadyVisited: obj
 104 "Whether the object has been seen/visited."
 105 [s seen includes: obj].
 106
 107 s@(TraversalStream traits) childrenOf: obj
 108 "Grabs the children of the object according to the Stream's intended use,
 109 specified by a block that acts on the object."
 110 [s childrenBlock applyWith: obj].
 111
 112 s@(TraversalStream traits) next
 113 "Pop the todo list, mark it visited, and use the childrenBlock to push onto
 114 the todo list unseen elements from it."
 115 [
 116   result ::= s todo pop.
 117   s visit: result.
 118   ((s childrenOf: result) reader
 119     reject: [| :c | (s alreadyVisited: c) \/ [s cannotVisit: c]])
 120     >> s todo appender.
 121   result
 122 ].