trees_nodes.rb

module CompSci
  # has a value and an array of children; allows child gaps
  class Node
    attr_accessor :value
    attr_reader :children

    def initialize(value, children: [])
      @value = value
      if children.is_a?(Integer)
        @children = Array.new(children)
      else
        @children = children
      end
      # @metadata = {}
    end

    def [](idx)
      @children[idx]
    end

    def set_child(idx, node)
      @children[idx] = node
    end
    alias_method :[]=, :set_child

    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(', ')]
    end
  end


  # like Node but with a reference to its parent
  class ChildNode < Node
    attr_accessor :parent

    def initialize(value, children: [])
      @parent = nil
      super(value, children: children)
    end

    # O(log n) recursive
    def gen
      @parent ? @parent.gen + 1 : 0
    end

    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
    alias_method :[]=, :set_child

    def set_parent(idx, node)
      @parent = node
      @parent.set_child(idx, self)
    end
  end


  #
  # FlexNodes - they accumulate children; no child gaps
  #

  # FlexNode API is #add_child, #add_parent, #new_child

  class FlexNode < Node
    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
  end

  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


  # for now at least, this assumes children simply stack up
  # children like: [nil, child1, child2] are not supported
  class Tree
    attr_reader :root

    def initialize(node_class, val)
      @root = node_class.new val
    end

    # does not support children gaps
    def df_search(node: nil, &blk)
      node ||= @root
      return node if yield node
      node.children.each { |c|
        stop_node = self.df_search(node: c, &blk)
        return stop_node if stop_node
      }
      nil
    end

    # does not support children gaps
    def bf_search(node: nil, &blk)
      node ||= @root
      destinations = [node]
      while !destinations.empty?
        node = destinations.shift
        return node if yield node
        destinations += node.children
      end
      nil
    end

    def df_search_generic(node: nil, &blk)
      # Perform pre-order operation
      # children.each { Perform in-order operation }
      # Perform post-order operation
      puts "not defined yet"
    end
  end

  # mixin methods for FlexNode based trees
  module PushTree
    # this only works if @root.respond_to? :new_child
    def push(value)
      self.open_parent.new_child value
    end

    def open_parent?(node)
      node.children.size < @child_slots
    end

    def open_sibling
      # try siblings first, only possible with Node#parent
      if @open_parent.respond_to?(:siblings)
        @open_parent.siblings.find { |s| self.open_parent?(s) }
      end
    end

    def open_parent
      @open_parent ||= @root
      return @open_parent if self.open_parent?(@open_parent)
      open_sibling = self.open_sibling
      return @open_parent = open_sibling if open_sibling
      @open_parent = self.bf_search { |n| self.open_parent?(n) }
    end
  end

  class NaryTree < Tree
    def self.display_level(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

    # thanks apeiros
    # https://gist.github.com/rickhull/d0b579aa08c85430b0dc82a791ff12d6
    def self.power_of?(num, base)
      return false if base <= 1
      mod = 0
      num, mod = num.divmod(base) until num == 1 || mod > 0
      mod == 0
    end

    attr_reader :child_slots

    def initialize(node_class, val, child_slots:)
      case node_class
      when CompSci::FlexNode, CompSci::ChildFlexNode
        include PushTree
      end
      super(node_class, val)
      @child_slots = child_slots
    end

    def display(node: @root, width: 80)
      levels = [self.class.display_level(nodes: [node], width: width)]
      nodes = node.children
      while nodes.any? { |n| !n.nil? }
        levels << self.class.display_level(nodes: nodes, width: width)
        children = []
        nodes.each { |n|
          children += Array.new(@child_slots) { |i| n and n.children[i] }
        }
        nodes = children
      end
      levels.join("\n")
    end
    alias_method :to_s, :display
  end
end