Class: StringTree::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/stringtree/node.rb

Overview

Node represents a node in a StringTree::Tree.

This is essentially a binary tree node with additional up and down pointers.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(char, parent = nil, value = nil) ⇒ Node

Create a new Node with the given char and optionally, parent node and value



20
21
22
23
24
 
# File 'lib/stringtree/node.rb', line 20

def initialize(char, parent = nil, value = nil)
  @char = char
  @up = parent
  @value = value
end

Instance Attribute Details

#char ⇒ Object

The char Character value of this node



7
8
9
 
# File 'lib/stringtree/node.rb', line 7

def char
  @char
end

#down ⇒ Object

The child (down) node of this node, or nil



13
14
15
 
# File 'lib/stringtree/node.rb', line 13

def down
  @down
end

#left ⇒ Object

The next left node to this node, or nil



9
10
11
 
# File 'lib/stringtree/node.rb', line 9

def left
  @left
end

#right ⇒ Object

The next right node to this node, or nil



11
12
13
 
# File 'lib/stringtree/node.rb', line 11

def right
  @right
end

#up ⇒ Object

The parent (up) node to this node, or nil



15
16
17
 
# File 'lib/stringtree/node.rb', line 15

def up
  @up
end

#value ⇒ Object

The value of this node, or nil



17
18
19
 
# File 'lib/stringtree/node.rb', line 17

def value
  @value
end

Instance Method Details

#add_horizontal(node) ⇒ Object

Add another node horizontally (within the left-right binary tree of this Node)



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/stringtree/node.rb', line 28

def add_horizontal(node)
  if(node.char > @char)
    if (@right === nil)
      @right = node
    else
      @right.add_horizontal(node)
    end
  else
    if (@left === nil)
      @left = node
    else
      @left.add_horizontal(node)
    end
  end
end

#add_horizontal_char(char) ⇒ Object

Add and return a new, or return the existing, node with the given char horizontally (within the left-right binary tree of this Node)



46
47
48
49
50
51
52
53
54
 
# File 'lib/stringtree/node.rb', line 46

def add_horizontal_char(char)
  node = find_horizontal(char);
  if node != nil
    return node
  end
  node = Node.new(char, up)
  add_horizontal(node)
  return node
end

#add_vertical(str, value) ⇒ Object

Add the given String str and value vertically to this node, by adding or finding each character horizontally, then stepping down and repeating with the next character and so on, writing the value to the last node.



78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/stringtree/node.rb', line 78

def add_vertical(str, value)
  node = nil
  str.each_char { |c|
    if (node == nil)
      node = self.add_horizontal_char(c)
    elsif (node.down != nil)
      node = node.down.add_horizontal_char(c)
    else
      node.down = Node.new(c, node)
      node = node.down
    end
  }
  node.value = value
end

#all_partials(str = "") ⇒ Object

Return an Array of Strings of all possible partial string from this node. Optionally, use the given prefix String str.



210
211
212
213
214
 
# File 'lib/stringtree/node.rb', line 210

def all_partials(str = "")
  list = []      
  @down.walk(str) { |str| list << str } unless @down.nil?
  list
end

#balance ⇒ Object

Recursively balance this node in its own tree, and every node in all four directions, and return the new root node.



152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
# File 'lib/stringtree/node.rb', line 152

def balance
  node = self
  i = (node.count(:right) - node.count(:left))/2
  while (i!=0)
    if (i>0)
      mvnode = node.right
      node.right = nil
      mvnode.add_horizontal node
      i -= 1
    else
      mvnode = node.left
      node.left = nil
      mvnode.add_horizontal node
      i += 1
    end
    node = mvnode
  end
  if (node.left != nil)
    node.left = node.left.balance
  end
  if (node.right != nil)
    node.right = node.right.balance
  end
  if (node.down != nil)
    node.down = node.down.balance
  end
  node
end

#count(direction) ⇒ Object

Count the number of nodes in the given direction (:up,:down,:left,:right) until the edge of the tree.



140
141
142
143
144
145
146
147
148
 
# File 'lib/stringtree/node.rb', line 140

def count(direction)
  i = 0
  node = self
  while (node != nil)
    node = node.send(direction)
    i += 1
  end
  i
end

#find_forward(data, offset = 0, length = data.length) ⇒ Object

Find the next match (terminating node with value non-nil) in the String data Optionally, set the offset into the data and its length



118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/stringtree/node.rb', line 118

def find_forward(data, offset = 0, length = data.length)
  node = nil
  lastvaluenode = nil
  i = offset
  while (i<offset+length)
    c = data[i]
    if (node == nil)
      node = self.find_horizontal(c)
    elsif (node.down != nil)
      node = node.down.find_horizontal(c)
    else
      return lastvaluenode
    end
    return lastvaluenode  if (node == nil)
    lastvaluenode = node if (node.value != nil)
    i += 1
  end
  lastvaluenode
end

#find_horizontal(char) ⇒ Object

Find and return the node corresponding to the given char horizontally, or nil if not found (within the left-right binary tree of this Node)



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/stringtree/node.rb', line 58

def find_horizontal(char)
  return self if @char == char
  if(char > @char)
    if (@right === nil)
      return nil
    else
      return @right.find_horizontal(char)
    end
  else
    if (@left === nil)
      return nil
    else
      return @left.find_horizontal(char)
    end
  end
end

#find_vertical(str, offset = 0, length = str.length) ⇒ Object

Find the given String str vertically by finding each character horizontally, then stepping down and repeating with the next character and so on. Return the last node if found, or nil if any horizontal search fails. Optionally, set the offset into the string and its length



97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/stringtree/node.rb', line 97

def find_vertical(str, offset = 0, length = str.length)
  node = nil
  i = offset
  while (i<offset+length)
    c = str[i]
    if (node == nil)
      node = self.find_horizontal(c)
    elsif (node.down != nil)
      node = node.down.find_horizontal(c)
    else
      return nil
    end

    return nil if (node == nil)
    i += 1
  end
  node
end

#length ⇒ Object

Return the length of the total string key for this node from root.



204
205
206
 
# File 'lib/stringtree/node.rb', line 204

def length
  count(:up)
end

#to_s ⇒ Object

Return the complete string from the tree root up to and including this node i.e. The total string key for this node from root.



192
193
194
195
196
197
198
199
200
201
 
# File 'lib/stringtree/node.rb', line 192

def to_s
  st = @char
  node = self
  while node != nil
    node = node.up
    break if node==nil
    st = node.char+st
  end
  st
end

#walk(str = "") {|str+@char, @value| ... } ⇒ Object

Walk the tree from this node, yielding all strings and values where the value is not nil. Optionally, use the given prefix String str.

Yields:



183
184
185
186
187
188
 
# File 'lib/stringtree/node.rb', line 183

def walk(str="", &block)
  @down.walk(str+char, &block) if @down != nil
  @left.walk(str, &block) if @left != nil
  yield str+@char, @value if @value != nil
  @right.walk(str, &block) if @right != nil
end