Class: BiDimensionalTree

Inherits:
Object
  • Object
show all
Defined in:
lib/bi-dimensional-access.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ BiDimensionalTree

Initialize the tree creating it’s root


5
6
7
 
# File 'lib/bi-dimensional-access.rb', line 5

def initialize
  @root = nil
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.


2
3
4
 
# File 'lib/bi-dimensional-access.rb', line 2

def root
  @root
end

Instance Method Details

#balance ⇒ Object 


216
217
218
219
 
# File 'lib/bi-dimensional-access.rb', line 216

def balance
  balance_horiz unless balanced_horiz?
  balance_vert unless balanced_vert?
end

#balance_horiz(node = @root) ⇒ Object 


185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/bi-dimensional-access.rb', line 185

def balance_horiz(node = @root)
  return if balanced_horiz?

  nodes = get_nodes_horiz([], node)

  @root = nodes[nodes.length / 2]
  @root.west = nil
  @root.east = nil

  @root.west = new_balance_nodes_horiz(nodes[0..(nodes.length / 2) - 1])
  @root.east = new_balance_nodes_horiz(nodes[(nodes.length / 2) + 1..-1])
end

#balance_vert(node = @root) ⇒ Object

Balance the tree


165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/bi-dimensional-access.rb', line 165

def balance_vert(node = @root)
  unless balanced_vert_helper(node)
    balance_vert_helper(node, node)
  end
  unless node.east.nil?
    unless balanced_vert_helper(node.east)
      node.east = balance_vert_helper(node.east, node.east)
    else
      balance_vert(node.east)
    end
  end
  unless node.west.nil?
    unless balanced_vert_helper(node.west)
      node.west = balance_vert_helper(node.west, node.west)
    else
      balance_vert(node.west)
    end
  end
end

#balanced_horiz? ⇒ Boolean

Return true if tree is balanced, in other word, if the number of branchs is smaller than 2 raised to the tree’s depth

Returns:

  • (Boolean) 

201
202
203
 
# File 'lib/bi-dimensional-access.rb', line 201

def balanced_horiz?
  number_nodes_horiz.between?(2**(get_depth_horiz - 1), 2**get_depth_horiz)
end

#balanced_tree ⇒ Object 


221
222
223
224
225
 
# File 'lib/bi-dimensional-access.rb', line 221

def balanced_tree
  return false unless balanced_horiz?
  return false unless balanced_vert?
  true
end

#balanced_vert?(node = @root) ⇒ Boolean

Returns:

  • (Boolean) 

205
206
207
208
209
210
211
212
213
214
 
# File 'lib/bi-dimensional-access.rb', line 205

def balanced_vert?(node = @root)
  return false unless balanced_vert_helper(node)
  unless node.east.nil?
    return false unless balanced_vert?(node.east)
  end
  unless node.west.nil?
    return false unless balanced_vert?(node.west)
  end
  true
end

#delete_node(x, y) ⇒ Object

Delete a selected node from the tree


141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/bi-dimensional-access.rb', line 141

def delete_node(x, y)
  node = search_node(x, y)
  nodes = get_nodes_horiz([])
  if nodes.include? node
    nodes.delete(node)
    @root = nodes[nodes.length / 2]
    @root.west = nil
    @root.east = nil

    @root.west = new_balance_nodes_horiz(nodes[0..(nodes.length / 2) - 1])
    @root.east = new_balance_nodes_horiz(nodes[(nodes.length / 2) + 1..-1])
  else
    nodes = get_column(node)
    nodes.delete(node)
    middle = nodes[nodes.length / 2]
    middle.south = nil
    middle.north = nil

    middle.south = new_balance_nodes_vert(nodes[0..(nodes.length / 2) - 1])
    middle.north = new_balance_nodes_vert(nodes[(nodes.length / 2) + 1..-1])
  end
end

#edit_node(x, y, *args) ⇒ Object

Edit an existing node


104
105
106
107
108
 
# File 'lib/bi-dimensional-access.rb', line 104

def edit_node(x, y, *args)
  node = search_node(x, y)
  return if node.nil?
  node.args = args
end

#get_depth_horiz(node = @root, depth = 1, maxdepth = 0) ⇒ Object

Return the max depth of the tree


228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
# File 'lib/bi-dimensional-access.rb', line 228

def get_depth_horiz(node = @root, depth = 1, maxdepth = 0)
  unless node.west.nil?
    maxdepth = get_depth_horiz(node.west, depth + 1, maxdepth)
  end

  unless node.east.nil?
    maxdepth = get_depth_horiz(node.east, depth + 1, maxdepth)
  end

  if node.west.nil? and node.east.nil? and depth > maxdepth
    maxdepth = depth
  end

  maxdepth
end

#get_depth_vert(node = @root, depth = 1, maxdepth = 0) ⇒ Object 


244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/bi-dimensional-access.rb', line 244

def get_depth_vert(node = @root, depth = 1, maxdepth = 0)
  unless node.south.nil?
    maxdepth = get_depth_vert(node.south, depth + 1, maxdepth)
  end

  unless node.north.nil?
    maxdepth = get_depth_vert(node.north, depth + 1, maxdepth)
  end

  if node.south.nil? and node.north.nil? and depth > maxdepth
    maxdepth = depth
  end

  maxdepth
end

#load_file(file) ⇒ Object

Load a file and create a (sub)tree with its data


111
112
113
114
115
116
117
 
# File 'lib/bi-dimensional-access.rb', line 111

def load_file(file)
  data = File.open(file).readlines.map(&:chomp)
  data.each do |d|
    d = d.split(',')
    new_node(@root, *d[0], *d[1], *d[2..-1]) unless d.nil?
  end
end

#new_node(node, x, y, *args) ⇒ Object

Create a new branch after locating it’s place


10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/bi-dimensional-access.rb', line 10

def new_node(node, x, y, *args)
  if @root.nil?
    puts "Adding the node (#{x}, #{y}) in the root"
    return @root = BiNode.new(x, y, *args)
  elsif node.nil?
    return node = BiNode.new(x, y, *args)
  elsif node.x == x
    if node.y == y
      return node
    elsif y < node.y
      if node.south.nil?
        puts "Adding the node (#{x}, #{y}) in the south of (#{node.x}, #{node.y})"
        node.south = new_node(node.south, x, y, *args)
      else
        new_node(node.south, x, y, *args)
      end
    elsif y > node.y
      if node.north.nil?
        puts "Adding the node (#{x}, #{y}) in the north of (#{node.x}, #{node.y})"
        node.north = new_node(node.north, x, y, *args)
      else
        new_node(node.north, x, y, *args)
      end
    end
  elsif x < node.x
    if node.west.nil?
      puts "Adding the node (#{x}, #{y}) in the west of (#{node.x}, #{node.y})"
      node.west = new_node(node.west, x, y, *args)
    else
      new_node(node.west, x, y, *args)
    end
  elsif x > node.x
    if node.east.nil?
      puts "Adding the node (#{x}, #{y}) in the east of (#{node.x}, #{node.y})"
      node.east = new_node(node.east, x, y, *args)
    else
      new_node(node.east, x, y, *args)
    end
  end
end

#new_node_balanced(node, x, y, *args) ⇒ Object

Create a new node and balance the tree


52
53
54
55
 
# File 'lib/bi-dimensional-access.rb', line 52

def new_node_balanced(node, x, y, *args)
  new_node(node, x, y, *args)
  balance
end

#number_nodes_horiz(node = @root) ⇒ Object

Return the number of branchs


261
262
263
264
265
266
267
268
269
 
# File 'lib/bi-dimensional-access.rb', line 261

def number_nodes_horiz(node = @root)
  if node.nil?
    0
  else
    1 +
    number_nodes_horiz(node.west) +
    number_nodes_horiz(node.east)
  end
end

#number_nodes_total(node = @root) ⇒ Object 


281
282
283
284
285
286
287
288
289
290
291
 
# File 'lib/bi-dimensional-access.rb', line 281

def number_nodes_total(node = @root)
  if node.nil?
    0
  else
    1 +
    number_nodes_total(node.west)  +
    number_nodes_total(node.east)  +
    number_nodes_total(node.south) +
    number_nodes_total(node.north)
  end
end

#number_nodes_vert(node = @root) ⇒ Object 


271
272
273
274
275
276
277
278
279
 
# File 'lib/bi-dimensional-access.rb', line 271

def number_nodes_vert(node = @root)
  if node.nil?
    0
  else
    1 +
    number_nodes_vert(node.south) +
    number_nodes_vert(node.north)
  end
end

#print_tree(node = @root) ⇒ Object

Print all the branchs


130
131
132
133
134
135
136
137
138
 
# File 'lib/bi-dimensional-access.rb', line 130

def print_tree(node = @root)
  return if node.nil?
  print_tree(node.west) unless node.west.nil?
  print_tree(node.south) unless node.south.nil?
  puts "#{node.x} #{node.y} #{node.args}"
  print_tree(node.north) unless node.north.nil?
  print_tree(node.east) unless node.east.nil?
  return
end

#save_file ⇒ Object

Save the current tree in a file


120
121
122
123
124
125
126
127
 
# File 'lib/bi-dimensional-access.rb', line 120

def save_file
  nodes = get_nodes([])
  file = File.open('search_tree', 'w')
  nodes.each do |node|
      file.puts("#{node.x} #{node.y} #{node.args}")
  end
  file.close
end

#search(x, y, node = @root) ⇒ Object

Locate a branch, if it exists


58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/bi-dimensional-access.rb', line 58

def search(x, y, node = @root)
  return false if node.nil?

  if x == node.x
    if y == node.y
      return true
    elsif y < node.y and !node.south.nil?
      search(x, y, node.south)
    elsif y > node.y and !node.north.nil?
      search(x, y, node.north)
    else
      return false
    end
  elsif x < node.x and !node.west.nil?
    search(x, y, node.west)
  elsif x > node.x and !node.east.nil?
    search(x, y, node.east)
  else
    return false
  end
end

#search_node(x, y, node = @root) ⇒ Object

Locate a branch, if it exists


81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/bi-dimensional-access.rb', line 81

def search_node(x, y, node = @root)
  return nil if node.nil?

  if x == node.x
    if y == node.y
      return node
    elsif y < node.y and !node.south.nil?
      search_node(x, y, node.south)
    elsif y > node.y and !node.north.nil?
      search_node(x, y, node.north)
    else
      return nil
    end
  elsif x < node.x and !node.west.nil?
    search_node(x, y, node.west)
  elsif x > node.x and !node.east.nil?
    search_node(x, y, node.east)
  else
    return nil
  end
end