lib/compsci/node.rb in compsci-0.1.1.1 vs lib/compsci/node.rb in compsci-0.2.0.1

@@ -1,49 +1,78 @@
 module CompSci
-  # has a value and an array of children
+  # has a value and an array of children; allows child gaps
   class Node
     attr_accessor :value
     attr_reader :children
 
-    def initialize(value)
+    def initialize(value, children: [])
       @value = value
-      @children = []
+      if children.is_a?(Integer)
+        @children = Array.new(children)
+      else
+        @children = children
+      end
       # @metadata = {}
     end
 
-    def add_child(node)
-      @children << node
-    end
-
-    def new_child(value)
-      self.add_child self.class.new(value)
-    end
-
-    def add_parent(node)
-      node.add_child(self)
-    end
-
     def to_s
       @value.to_s
     end
 
+    # This could be done directly with self.children, but #set_child is part
+    # of the Node API.
+    def set_child(idx, node)
+      @children[idx] = node
+    end
+
     def inspect
       "#<%s:0x%0xi @value=%s @children=[%s]>" %
         [self.class,
          self.object_id,
          self.to_s,
          @children.map(&:to_s).join(', ')]
     end
   end
 
+  # adds a key to Node; often the key is used to place the node in the
+  # tree, independent of the value; e.g. key=priority, value=process_id
+  class KeyNode < Node
+    attr_accessor :key
+
+    def initialize(val, key: nil, children: [])
+      @key = key
+      super(val, children: children)
+    end
+
+    def to_s
+      [key, value].join(':')
+    end
+  end
+
+  # accumulate children; no child gaps
+  class FlexNode < Node
+    def add_child(node)
+      @children << node
+    end
+
+    # TODO: are we passing everything needed to self.class.new ?
+    def new_child(value)
+      self.add_child self.class.new(value)
+    end
+
+    def add_parent(node)
+      node.add_child(self)
+    end
+  end
+
   # like Node but with a reference to its parent
   class ChildNode < Node
     attr_accessor :parent
 
-    def initialize(value)
+    def initialize(value, children: [])
       @parent = nil
-      super(value)
+      super(value, children: children)
     end
 
     # O(log n) recursive
     def gen
       @parent ? @parent.gen + 1 : 0
@@ -51,17 +80,35 @@
 
     def siblings
       @parent ? @parent.children : []
     end
 
+    def set_child(idx, node)
+      node.parent ||= self
+      raise "node has a parent: #{node.parent}" if node.parent != self
+      @children[idx] = node
+    end
+
+    def set_parent(idx, node)
+      @parent = node
+      @parent.set_child(idx, self)
+    end
+  end
+
+  # ChildNode which accumulates children with no gaps
+  class ChildFlexNode < ChildNode
     def add_child(node)
       node.parent ||= self
       raise "node has a parent: #{node.parent}" if node.parent != self
-      super(node)
+      @children << node
     end
 
+    def new_child(value)
+      self.add_child self.class.new(value)
+    end
+
     def add_parent(node)
       @parent = node
-      super(node)
+      @parent.add_child(self)
     end
   end
 end