node.rb in compsci-0.3.1.1

- old
+ new

@@ -1,77 +1,151 @@
 module CompSci
   # has a value and an array of children; allows child gaps
   class Node
-    attr_accessor :value
+    def self.display_line(nodes: [], width: 80)
+      block_width = [width / nodes.size, 1].max
+      nodes.map { |node|
+        str = node ? node.to_s : '_'
+        space = [(block_width + str.size) / 2, str.size + 1].max
+        str.ljust(space, ' ').rjust(block_width, ' ')
+      }.join
+    end
+
+    attr_accessor :value, :metadata
     attr_reader :children
 
-    def initialize(value, children: [])
+    def initialize(value, children: 2, metadata: {})
       @value = value
-      if children.is_a?(Integer)
-        @children = Array.new(children)
-      else
-        @children = children
-      end
-      # @metadata = {}
+      @children = Array.new(children)
+      @metadata = metadata
     end
 
-    def to_s
-      @value.to_s
+    def [](idx)
+      @children[idx]
     end
 
-    # This could be done directly with self.children, but #set_child is part
-    # of the Node API.
-    def set_child(idx, node)
+    def []=(idx, node)
       @children[idx] = node
     end
 
+    def to_s
+      @value.to_s
+    end
+
     def inspect
       "#<%s:0x%0xi @value=%s @children=[%s]>" %
-        [self.class,
-         self.object_id,
-         self.to_s,
-         @children.map(&:to_s).join(', ')]
+        [self.class, self.object_id, self, @children.join(', ')]
     end
+
+    def display(width: 80)
+      lines = [self.class.display_line(nodes: [self], width: width)]
+      nodes = @children
+      while nodes.any? { |n| !n.nil? }
+        lines << self.class.display_line(nodes: nodes, width: width)
+        if nodes.size > 3**7
+          lines << "nodes.size = #{nodes.size}; abort render"
+          break
+        end
+        nodes = nodes.reduce([]) { |memo, n|
+          memo + Array.new(@children.size) { |i| n and n.children[i] }
+        }
+      end
+      lines.join("\n")
+    end
   end
 
+  # TODO: implement key with @metadata !?!?!?!?
+
   # 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
+    class DuplicateKey < RuntimeError; end
+    class SearchError < RuntimeError; end
 
-    def initialize(val, key: nil, children: [])
-      @key = key
+    attr_reader :key, :duplicates
+
+    def self.key_cmp_idx(new_key, key, child_slots: 2, duplicates: false)
+      if child_slots < 2
+        raise(ArgumentError, "child_slots: #{child_slots} too small")
+      elsif child_slots == 2
+        raise(DuplicateKey, "#{new_key}") if new_key == key and !duplicates
+        new_key < key ? 0 : 1
+      elsif child_slots == 3
+        (new_key <=> key) + 1
+      else
+        raise(ArgumentError: "child_slots: #{child_slots} too big")
+      end
+    end
+
+    def initialize(val, key: nil, children: 2, duplicates: false)
       super(val, children: children)
+      @key, @duplicates = key, duplicates
     end
 
     def to_s
-      [key, value].join(':')
+      [@key, @value].join(':')
     end
-  end
 
-  # accumulate children; no child gaps
-  class FlexNode < Node
-    # These methods look like convenience methods, but they provide the
-    # FlexNode interface also used by ChildFlexNode
-    def add_child(node)
-      @children << node
+    # which child idx should handle key?
+    def cidx(key)
+      self.class.key_cmp_idx(key, @key,
+                             child_slots: @children.size,
+                             duplicates: @duplicates)
     end
 
-    def new_child(value)
-      self.add_child self.class.new(value)
+    # works for 2 or 3 children
+    def insert(key, val)
+      idx = self.cidx(key)
+      if @children[idx]
+        @children[idx].insert(key, val)
+      else
+        @children[idx] = self.class.new(val, key: key,
+                                        children: @children.size,
+                                        duplicates: @duplicates)
+      end
     end
 
-    def add_parent(node)
-      node.add_child(self)
+    # returns a single node for binary search
+    # returns multiple nodes for ternary search
+    def search(key)
+      if @children.size == 2
+        self.search2(key)
+      elsif @children.size == 3
+        self.search3(key)
+      else
+        raise(SearchError, "can't search for @children.size children")
+      end
     end
+
+    # returns a single node or nil
+    def search2(key)
+      return self if key == @key
+      child = @children[self.cidx(key)]
+      child.search(key) if child
+    end
+
+    # returns an array of nodes, possibly empty
+    def search3(key)
+      if key == @key
+        nodes = [self]
+        node = @children[1]
+        while node
+          nodes << node
+          node = node.children[1]
+        end
+        return nodes
+      end
+      child = @children[self.cidx(key)]
+      child ? child.search(key) : []
+    end
   end
 
   # like Node but with a reference to its parent
   class ChildNode < Node
     attr_accessor :parent
 
-    def initialize(value, children: [])
+    def initialize(value, children: 2)
       @parent = nil
       super(value, children: children)
     end
 
     # O(log n) recursive
@@ -81,37 +155,13 @@
 
     def siblings
       @parent ? @parent.children : []
     end
 
-    def set_child(idx, node)
+    # update both sides of the relationship
+    def []=(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
-  # It meets the FlexNode API but does not inherit from FlexNode since it
-  # needs to reimplement each method; instead get parent stuff from ChildNode
-  class ChildFlexNode < ChildNode
-    def add_child(node)
-      node.parent ||= self
-      raise "node has a parent: #{node.parent}" if node.parent != self
-      @children << node
-    end
-
-    def new_child(value)
-      self.add_child self.class.new(value)
-    end
-
-    def add_parent(node)
-      @parent = node
-      @parent.add_child(self)
     end
   end
 end