Class: Imp::Tree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/imp/tree.rb

Overview

A directory-esque tree with labeled nodes and edges.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(val = nil) ⇒ Tree

Creates a new Tree.

Parameters:

  • val (Object) (defaults to: nil) —

    The node label of the tree.



16
17
18
19
 
# File 'lib/imp/tree.rb', line 16

def initialize(val = nil)
  @val = val
  @succ = {}
end

Instance Attribute Details

#val ⇒ Object

The value of the current node in the tree.



11
12
13
 
# File 'lib/imp/tree.rb', line 11

def val
  @val
end

Instance Method Details

#[](key, create = false) ⇒ Tree?

Gets a subtree by the label of the edge leading to it.

Parameters:

  • key (String) —

    The edge label.

  • create (Boolean) (defaults to: false) —

    Whether or not the create a new Node if there is no edge with the label given.

Returns:

  • (Tree, nil) —

    The tree at the edge, or nil if it didn’t exist annd create was false.



28
29
30
31
32
33
34
 
# File 'lib/imp/tree.rb', line 28

def [](key, create = false)
  if create and not @succ.include? key
    @succ[key] = Tree.new
  else
    @succ[key]
  end
end

#delete(key) ⇒ Object

Removes a subtree by the label of the edge leading to it.

Parameters:

  • key (String) —

    The edge label.s



39
40
41
 
# File 'lib/imp/tree.rb', line 39

def delete(key)
  @succ.delete key
end

#descendant(key, create = false) ⇒ Tree?

Gets a (more distant descendant of the current node.

Parameters:

  • key (String) —

    A forward-slash seperated list of the edge labels to follow.

  • create (Boolean) (defaults to: false) —

    Whether or not to create nodes if the edge labels aren’t used yet.

Returns:

  • (Tree, nil) —

    The node connected through the edge labels, or nil if there is no such node and create was false.



74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/imp/tree.rb', line 74

def descendant(key, create = false)
  if key.include? '/'
    key, keys = key.split('/', 2)
    child = self[key, create]
    if child
      child.descendant(keys, create)
    end
  else
    self[key, create]
  end
end

#each {|String, Tree| ... } ⇒ Object

Iterates over (edge, node) pairs.

Yields:

  • (String, Tree) —

    Edge, node pairs of connected nodes.



53
54
55
 
# File 'lib/imp/tree.rb', line 53

def each(&block)
  @succ.each(&block)
end

#include?(item) ⇒ Boolean

Checks if an edge is included.

Parameters:

  • item (String) —

    The string to check.

Returns:

  • (Boolean) —

    Whether or not the string is an edge label going out from this node.



62
63
64
 
# File 'lib/imp/tree.rb', line 62

def include? item
  @succ.include? item
end

#leaf? ⇒ Boolean

Checks if this is a leaf node.

Returns:

  • (Boolean) —

    Wheter or not the node is a leaf.



46
47
48
 
# File 'lib/imp/tree.rb', line 46

def leaf?
  @succ.length == 0
end

#to_s(indent = 0) ⇒ String

Prints the skeleton of the tree. Node labels are NOT printed.

Parameters:

  • indent (Int) (defaults to: 0) —

    By how many stages to indent the tree.

Returns:

  • (String) —

    The skeleton of the tree.



90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/imp/tree.rb', line 90

def to_s(indent = 0)
  s = ""
  each do |k, v|
    s += '  ' * indent
    s += k
    s += '/' unless v.leaf?
    s += '*' if v.val
    s += "\n"
    s += v.to_s(indent + 1)
  end
  return s
end