class Tree

Public Class Methods

new() click to toggle source
# File lib/generic/tree.rb, line 2
def initialize
  @values = []
  @edges = []
  @parents = []
end

Public Instance Methods

add_edge(from, to) click to toggle source
# File lib/generic/tree.rb, line 59
def add_edge(from, to)
  register_edge(from, to)
  register_parent(to, from)
end
add_node(id, value) click to toggle source
# File lib/generic/tree.rb, line 48
def add_node(id, value)
  @values[id] = value 
end
branch?(id) click to toggle source
# File lib/generic/tree.rb, line 68
def branch?(id)
  ! leaf?(id)
end
children(id) click to toggle source
# File lib/generic/tree.rb, line 44
def children(id)
  @edges[id]
end
depth(id) click to toggle source
# File lib/generic/tree.rb, line 26
def depth(id)
  d = 0
  i = id
  until( i==root_id )
    i = parent(i)
    d += 1
  end
  d
end
leaf?(id) click to toggle source
# File lib/generic/tree.rb, line 64
def leaf?(id)
  @edges[id] == nil
end
list_depth_traverse(under) click to toggle source
# File lib/generic/tree.rb, line 8
def list_depth_traverse(under)
  list = []
  do_list_depth_traverse(under, list)
  return list
end
not_found_link2text!() click to toggle source

NOTE: About Design. In current design, a link node that can not find the tag node it points to is treated as text node.

# File lib/rdtree.rb, line 10
def not_found_link2text!
  list_link_nodes.each do |id|
    if can_not_find_tag(id)
      modify_link2text(id)
    end
  end
end
parent(id) click to toggle source
# File lib/generic/tree.rb, line 22
def parent(id)
  @parents[id]
end
rationalize!() click to toggle source

NOTE: Crazy Design Akira Hayakawa, Aug 23, 2011 This method must be called wherever it needs the rationalized state. For exmaple, a Link node that can not find the tag in the tree should be altered to Text node. But, this is innately a bad design. Because of my incapable of not coming up with a good idea to solve this issue elegantly. The version 2.0.2 scattered this method to to_csv and to_dot. But I do not know if this is sufficient. To solve this issue theoritically, embed this method into every single mutate methods of the instance mattered.

If you embed this method, please leave comment “# CRAZY” there so that you can remove after I find a better solution.

A solution is to simplify the design that lets every paths through RDTree structure. Then call rationalize only one time before it is needed, case of conversion for example.

# File lib/rdtree.rb, line 33
def rationalize!
  not_found_link2text!
end
root_id() click to toggle source
# File lib/generic/tree.rb, line 36
def root_id
  0
end
size() click to toggle source
# File lib/generic/tree.rb, line 18
def size
  @values.size
end
to_csv() click to toggle source
# File lib/rdtree.rb, line 37
def to_csv 
  rationalize! # CRAZY
  m = tree2matrix(self)

  range = [
    0...m.m_size,
    1...m.n_size]
  c = matrix2csv(m, range) do |n|
    s = nil
    if n == nil
      s = ""
    else
      s = n.to_csv
    end
    s
  end
  c
end
to_dot() click to toggle source
# File lib/rdtree2dot.rb, line 5
  def to_dot
    rationalize! # CRAZY
    elems = []
    for i in 0...size
      unless link_node?(i)
        elems << dot_node_desc(i)
      end
    end
    linkmap = mk_id2id
    for i in 0...size
      if link_node?(i)
        to = linkmap[i]
        from = parent(i)
        elems << dot_edge_desc(from, to)
        next
      end
      if leaf?(i)
        next
      end
      children(i).each do |child|
        elems << dot_edge_desc(i, child) unless link_node?(child)
      end
    end
    
    # NOTE: The ratio of the output figure is 1 at default.
    # I/F to change the ratio is the future work.
"""
digraph graphname {
  graph [ratio = 1]
  #{elems.join("\n  ")}
}
"""
  end
to_rd() click to toggle source
# File lib/rdtree2rd.rb, line 8
def to_rd
  nodes = list_depth_traverse(root_id)
  # NOTE: Eliminate the DummyRoot from rd file.
  nodes.delete(root_id) 
  nodes.map do |node|
    value(node).to_rd
  end.join("\n")
end
update_value(id, value) click to toggle source
# File lib/generic/tree.rb, line 52
def update_value(id, value)
  # In current version,
  # update_value is just a wrapper of add_node.
  # but in future version, this may need modification.
  add_node(id, value)
end
value(id) click to toggle source
# File lib/generic/tree.rb, line 40
def value(id)
  @values[id]
end
values() click to toggle source
# File lib/generic/tree.rb, line 14
def values
  @values
end

Private Instance Methods

can_not_find_tag(id) click to toggle source
# File lib/rdtree.rb, line 91
def can_not_find_tag(id)
  tag = mk_id2tag[id]
  ! mk_tag2id.include? tag
end
do_list_depth_traverse(under, list) click to toggle source
# File lib/generic/tree.rb, line 74
def do_list_depth_traverse(under, list)
  list << under
  if leaf?(under)
    return
  end
  children(under).each do |id|
    do_list_depth_traverse(id, list)
  end
end
dot_edge_desc(from, to) click to toggle source
# File lib/rdtree2dot.rb, line 44
def dot_edge_desc(from, to)
  "v#{from} -> v#{to};"
end
dot_node_desc(id) click to toggle source
# File lib/rdtree2dot.rb, line 40
def dot_node_desc(id)
  "v#{id} [label=\"#{value(id).to_desc}\"];" 
end
link2text(linknode) click to toggle source

NOTE: Maybe Under-Engineering. id of node, tmp field are not copied but this time, I decided not because I considered unnessessary.

# File lib/rdtree.rb, line 67
def link2text(linknode)
  depth = linknode.depth
  text = linknode.dest
  Text.new(depth, text)
end
mk_id2id() click to toggle source
# File lib/rdtree.rb, line 107
def mk_id2id
  id2tag = mk_id2tag
  tag2id = mk_tag2id
  id2id = {}
  id2tag.keys.each do |id|
    tag = id2tag[id]
    if tag2id.include?( tag)
      id2id[id] = tag2id[tag]
    end
  end
  id2id
end
mk_id2tag() click to toggle source
# File lib/rdtree.rb, line 131
def mk_id2tag
  id2tag = {}
  for i in 0...size
    n = value(i)
    if n.class == Link  
      id2tag[i] = n.dest
    end
  end
  id2tag
end
mk_linkmap() click to toggle source
# File lib/rdtree.rb, line 101
def mk_linkmap
  # NOTE: is this use of warn method correct?
  warn "Warning: mk_linkmap should not be used. mk_id2id instead."
  mk_id2id
end
mk_tag2id() click to toggle source
# File lib/rdtree.rb, line 120
def mk_tag2id
  tag2id = {}
  for i in 0...size
    n = value(i)
    if n.class == Tag
      tag2id[n.tag] = i
    end
  end
  tag2id
end
modify_link2text(id) click to toggle source
# File lib/rdtree.rb, line 58
def modify_link2text(id)
  linknode = value(id)
  textnode = link2text(linknode)
  update_value(id, textnode)
end
register_edge(from, to) click to toggle source
# File lib/generic/tree.rb, line 84
def register_edge(from, to)
  if @edges[from] == nil
    @edges[from] = Array.new
  end
  @edges[from] << to
end
register_parent(from, to) click to toggle source
# File lib/generic/tree.rb, line 91
def register_parent(from, to)
  @parents[from] = to  
end