Class: BiDimensionalTree

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initializeBiDimensionalTree

Initialize the tree creating it’s root

[View source]

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

def initialize
  @root = nil
end

Instance Attribute Details

#rootObject (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

#balanceObject

[View source]

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

[View source]

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

[View source]

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)
[View source]

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_treeObject

[View source]

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)
[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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

[View source]

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 all the branchs

[View source]

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_fileObject

Save the current tree in a file

[View source]

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

[View source]

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

[View source]

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