CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

1
#
2
# Rabal Tree,rb
3
# A basic Tree structure
4
#
5

6
class Tree
7

8
  include Enumerable
9

10
  # The name of this Tree
11
  attr_accessor :name
12

13
  # The parent of this node.  If this is nil then this Tree is a
14
  # root.
15
  attr_accessor :parent
16

17
  # The children of this node.  If this Hash is empty, then this
18
  # Tree is a leaf.
19
  attr_accessor :children
20

21
  # An abstract data point that can be utilized by child classes
22
  # for whatever they like.  If this is non-nil and responds to
23
  # method calls it will be searched as part of the
24
  # 'method_missing' protocol.
25
  attr_accessor :parameters
26

27
  #
28
  # Create a new Tree with the given object.to_s as its +name+.
29
  #
30

31
  def initialize(name)
32
    @name   	= name.to_s
33
    @parent 	= nil
34
    @children   = {}
35
    @parameters = nil
36
  end
37

38
  #
39
  # Return true if this Tree has no children.
40
  #
41
  def is_leaf?
42
    @children.empty?
43
  end
44

45
  # 
46
  # Return true if this Tree has no parent.
47
  #
48
  def is_root?
49
    @parent.nil?
50
  end
51

52
  # 
53
  # Return the root node of the tree
54
  #
55
  def root
56
    return self if is_root?
57
    return @parent.root
58
  end
59

60
  #
61
  # Return the distance from the root
62
  #
63
  def depth
64
    return 0 if is_root?
65
    return (1 + @parent.depth)
66
  end
67

68
  #
69
  # Attach the given tree at the indicated path.  The path given
70
  # is always assumed to be from the root of the Tree being
71
  # attached to.
72
  #
73
  # The path is given as a string separated by '/'.  Each portion
74
  # of the string is matched against the name of the particular
75
  # tree.  
76
  #
77
  # Given :
78
  #
79
  #   a --- b --- c
80
  #	\ 
81
  # 	d - e --- f
82
  #  		\
83
  #   		g - h
84
  #
85
  # * the path +a/b/c+ will match the path to Tree +c+
86
  # * the path +d/e/g+ will _not_ match anything as the path must start at +a+ here
87
  # * the path +a/d/e+ will _not_ match anytthin as +e+ is not a child of +d+
88
  # * the path +a/d/e/g+ will match node +g+
89
  #
90
  # Leading and trailing '/' on the path are not necessary and removed.
91
  #
92
  def add_at_path(path,subtree)
93
    parent_tree = tree_at_path(path)
94
    parent_tree << subtree
95
    return self
96
  end
97

98
  #
99
  # Return the Tree that resides at the given path
100
  #
101
  def tree_at_path(path_str)
102
    path_str = path_str.chomp("/").reverse.chomp("/").reverse
103
    path 	= path_str.split("/")
104

105
    # strip of the redundant first match if it is the same as
106
    # the current node
107
    find_subtree(path)
108
  end
109

110
  #
111
  # Add the given object to the Tree as a child of this node.  If
112
  # the given object is not a Tree then wrap it with a Tree.
113
  #
114
  def <<(subtree)
115
    # this should not generally be the case, but wrap things
116
    # up to be nice.
117
    if not subtree.kind_of?(Tree) then
118
      subtree = Tree.new(subtree)
119
    end
120

121
    subtree.parent = self
122

123
    # FIXME: technically this should no longer be called 'post_add' 
124
    # but maybe 'add_hook'  
125
    subtree.post_add
126

127
    # Don't overwrite any existing children with the same name,
128
    # just put the new subtree's children into the children of
129
    # the already existing subtree.
130

131
    if children.has_key?(subtree.name) then
132
      subtree.children.each_pair do |subtree_child_name,subtree_child_tree|
133
        children[subtree.name] << subtree_child_tree
134
      end
135
    else
136
      children[subtree.name] = subtree
137
    end
138

139
    return self
140
  end
141

142
  alias :add :<<
143

144
  #
145
  # Allow for Enumerable to be included.  This just wraps walk.
146
  #
147
  def each
148
    self.walk(self,lambda { |tree| yield tree }) 
149
  end
150

151
  #
152
  # Count how many items are in the tree
153
  #
154
  def size
155
    inject(0) { |count,n| count + 1 }
156
  end
157

158
  # 
159
  # Walk the tree in a depth first manner, visiting the Tree
160
  # first, then its children
161
  #
162
  def walk(tree,method)
163
    method.call(tree)
164
    tree.children.each_pair do |name,child|
165
      walk(child,method) 
166
    end
167
    #for depth first
168
    #method.call(tree)
169
  end
170

171
  # 
172
  # Allow for a method call to cascade up the tree looking for a
173
  # Tree that responds to the call.
174
  #
175
  def method_missing(method_id,*params,&block)
176
    if not parameters.nil? and parameters.respond_to?(method_id, true) then
177
      return parameters.send(method_id, *params, &block)
178
    elsif not is_root? then
179
      @parent.send method_id, *params, &block
180
    else
181
      raise NoMethodError, "undefined method `#{method_id}' for #{name}:Tree"
182
    end
183
  end
184

185
  #
186
  # allow for a hook so newly added Tree objects may do custom
187
  # processing after being added to the tree, but before the tree
188
  # is walked or processed
189
  #
190
  def post_add
191
  end
192
  #
193
  # find the current path of the tree from root to here, return it
194
  # as a '/' separates string.
195
  #
196
  def current_path
197
    #
198
    # WMAP: removed the asterixs and modified the first return
199
    # to just return a '/'
200
    # 
201
    return "/" if is_root? 
202
    return ([name,parent.current_path]).flatten.reverse.join("/")
203
  end
204

205
  #
206
  # Given the initial path to match as an Array find the Tree that
207
  # matches that path.
208
  # 
209
  def find_subtree(path)
210
    if path.empty? then
211
      return self
212
    else
213
      possible_child = path.shift
214
      if children.has_key?(possible_child) then
215
        children[possible_child].find_subtree(path)
216
      else
217
        raise PathNotFoundError, "`#{possible_child}' does not match anything at the current path in the Tree (#{current_path})"
218
      end
219
    end
220
  end
221

222
  #
223
  # Return true of false if the given subtree exists or not
224
  #
225
  def has_subtree?(path)
226
    begin
227
      find_subtree(path)
228
      return true
229
    rescue PathNotFoundError
230
      return false
231
    end
232
  end
233

234
  #
235
  # Allow for numerable to be included. This just wraps walk
236
  #
237
  def each
238
    self.walk(self,lambda { |tree| yield tree })	
239
  end
240

241
  def each_datum
242
    self.walk(self,lambda { |tree| yield tree.data})
243
  end
244
end
245

246