Class: Tnode

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(data) ⇒ Tnode

Returns a new instance of Tnode.



4
5
6
7
8
 
# File 'lib/tnode.rb', line 4

def initialize(data)
  @data = data
  @links = []
  @trav_links = []
end

Instance Attribute Details

#data ⇒ Object

Returns the value of attribute data.



2
3
4
 
# File 'lib/tnode.rb', line 2

def data
  @data
end

#links ⇒ Object

Returns the value of attribute links.



2
3
4
 
# File 'lib/tnode.rb', line 2

def links
  @links
end

#trav_links ⇒ Object

Returns the value of attribute trav_links.



2
3
4
 
# File 'lib/tnode.rb', line 2

def trav_links
  @trav_links
end

Instance Method Details

#apart?(another) ⇒ Boolean

Returns:

  • (Boolean) 


124
125
126
 
# File 'lib/tnode.rb', line 124

def apart?(another)
  traverse_dfs.intersection(another.traverse_dfs).empty?
end

#init_trav_links ⇒ Object 



16
17
18
 
# File 'lib/tnode.rb', line 16

def init_trav_links
  re_init_trav_links(nil)
end

#insert(data) ⇒ Object 



10
11
12
13
14
 
# File 'lib/tnode.rb', line 10

def insert(data)
  new_node = Tnode.new(data)
  @links << new_node
  new_node.links << self
end

#insert_tnode_under(key_data, newnode) ⇒ Object 



136
137
138
139
 
# File 'lib/tnode.rb', line 136

def insert_tnode_under(key_data, newnode)
  tree_find(key_data).links << newnode
  newnode.links << tree_find(key_data)
end

#insert_under(key_data, data) ⇒ Object 



132
133
134
 
# File 'lib/tnode.rb', line 132

def insert_under(key_data, data)
  tree_find(key_data).insert(data)
end

#merge(another) ⇒ Object 



141
142
143
144
145
146
147
148
149
150
 
# File 'lib/tnode.rb', line 141

def merge(another)
  internodes = tree_inter(another)
  if internodes.count == 1
    another.tree_find(internodes.first).data = nil
    another.tree_find(nil).links.each do |child|
      child.remove_node(nil)
      insert_tnode_under(internodes.first, child)
    end
  end
end

#print_struct ⇒ Object 



55
56
57
58
 
# File 'lib/tnode.rb', line 55

def print_struct
  init_trav_links
  re_print_struct
end

#re_init_trav_links(parent) ⇒ Object 



20
21
22
23
24
25
26
27
 
# File 'lib/tnode.rb', line 20

def re_init_trav_links(parent)
  @trav_links = links.clone
  trav_links.delete(parent)
  trav_links.each do |child|
    child.trav_links.delete(self)
    child.re_init_trav_links(self)
  end
end

#re_print_struct(depth = 0, prefs = []) ⇒ Object

‘├── ’ ‘│ ’ ‘└── ’ ‘ ’



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/tnode.rb', line 64

def re_print_struct(depth = 0, prefs = [])
  puts data if depth == 0

  # prefixes
  trav_links.each_with_index do |child, i|
    prefs.each do |pref|
      print pref
    end
    if i == trav_links.size - 1 # is last?
      prefs.push '    ' unless child.trav_links.empty? # has childs
      print '└── '
      puts child.data
      child.re_print_struct(depth + 1, prefs) unless child.trav_links.empty?
      prefs.pop
    else
      prefs.push '│   ' unless child.trav_links.empty? # has childs
      print '├── '
      puts child.data
      child.re_print_struct(depth + 1, prefs) unless child.trav_links.empty?
    end
  end
end

#re_remove_node(key_data) ⇒ Object 



113
114
115
116
117
118
119
120
121
122
 
# File 'lib/tnode.rb', line 113

def re_remove_node(key_data)
  trav_links.each do |child|
    if child.data == key_data
      links.delete(child)
      return
    else
      child.re_remove_node(key_data)
    end
  end
end

#re_traverse_dfs ⇒ Object 



34
35
36
37
38
39
40
41
42
 
# File 'lib/tnode.rb', line 34

def re_traverse_dfs
  traverse_dfs_arr = [data]
  unless trav_links.empty?
    trav_links.each do |child|
      traverse_dfs_arr += child.re_traverse_dfs
    end
  end
  traverse_dfs_arr
end

#re_tree_find(key_data) ⇒ Object 



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/tnode.rb', line 92

def re_tree_find(key_data)
  target_node = nil
  if key_data == data
    return self
  else
    unless trav_links.empty?
      trav_links.each do |child|
        target_node = child.re_tree_find(key_data)
        return target_node unless target_node.nil?
      end
    end
  end

  nil
end

#remove_node(key_data) ⇒ Object 



108
109
110
111
 
# File 'lib/tnode.rb', line 108

def remove_node(key_data)
  init_trav_links
  re_remove_node(key_data)
end

#traverse_bfs ⇒ Object 



44
45
46
47
48
49
50
51
52
53
 
# File 'lib/tnode.rb', line 44

def traverse_bfs
  init_trav_links
  traverse_bfs_arr = [data]
  @traverse_bfs_q = trav_links.clone
  until @traverse_bfs_q.empty?
    traverse_bfs_arr << @traverse_bfs_q.first.data
    @traverse_bfs_q += @traverse_bfs_q.shift.trav_links
  end
  traverse_bfs_arr
end

#traverse_dfs ⇒ Object 



29
30
31
32
 
# File 'lib/tnode.rb', line 29

def traverse_dfs
  init_trav_links
  re_traverse_dfs
end

#tree_find(key_data) ⇒ Object 



87
88
89
90
 
# File 'lib/tnode.rb', line 87

def tree_find(key_data)
  init_trav_links
  re_tree_find(key_data)
end

#tree_inter(another) ⇒ Object 



128
129
130
 
# File 'lib/tnode.rb', line 128

def tree_inter(another)
  traverse_dfs.intersection(another.traverse_dfs)
end