Class: Melos::Tree

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Tree

attr_reader @array



5
6
7
8
 
# File 'lib/melos/tree.rb', line 5

def initialize
  @array = []
  @leaf_count = 0
end

Instance Attribute Details

#array ⇒ Object

Returns the value of attribute array.



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

def array
  @array
end

#leaf_count ⇒ Object

Returns the value of attribute leaf_count.



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

def leaf_count
  @leaf_count
end

Class Method Details

.common_ancestor_semantic(x, y, n) ⇒ Object 



179
180
181
182
183
184
185
186
187
188
 
# File 'lib/melos/tree.rb', line 179

def common_ancestor_semantic(x, y, n)
  dx = Set.new([x]) | Set.new(direct_path(x, n))
  dy = Set.new([y]) | Set.new(direct_path(y, n))
  dxy = dx & dy
  if dxy.size == 0
    raise ArgumentError.new('Failed to find common ancestor')
  end

  dxy.min { level(_1) }
end

.copath(x, n_leaves) ⇒ Object 



169
170
171
172
173
174
175
176
177
 
# File 'lib/melos/tree.rb', line 169

def copath(x, n_leaves)
  return [] if x == root(n_leaves)

  d = direct_path(x, n_leaves)
  d.insert(0, x)
  d.pop

  d.map { sibling(_1, n_leaves) }
end

.copath_nodes_of_filtered_direct_path(tree, node_index) ⇒ Object 



219
220
221
222
223
 
# File 'lib/melos/tree.rb', line 219

def copath_nodes_of_filtered_direct_path(tree, node_index)
  filtered_direct_path(tree, node_index).map do |a|
    sibling_from_leaf(node_index, a, n_leaves(tree))
  end
end

.direct_path(x, n_leaves) ⇒ Object 



158
159
160
161
162
163
164
165
166
167
 
# File 'lib/melos/tree.rb', line 158

def direct_path(x, n_leaves)
  r = root(n_leaves)
  return [] if x == r
  d = []
  while x != r
    x = parent(x, n_leaves)
    d << x
  end
  return d
end

.empty_tree(n_leaves) ⇒ Object 



10
11
12
13
14
15
 
# File 'lib/melos/tree.rb', line 10

def self.empty_tree(n_leaves)
  instance = self.allocate
  instance.leaf_count = n_leaves
  instance.array = Array.new(node_width(n_leaves))
  instance
end

.filtered_direct_path(tree, node_index) ⇒ Object 



214
215
216
217
 
# File 'lib/melos/tree.rb', line 214

def filtered_direct_path(tree, node_index)
  n_l = n_leaves(tree)
  direct_path(node_index, n_l).reject { resolution(tree, sibling_from_leaf(node_index, _1, n_l)) == [] }
end

.leaf?(node_index) ⇒ Boolean

Returns:

  • (Boolean) 


201
202
203
 
# File 'lib/melos/tree.rb', line 201

def leaf?(node_index)
  node_index % 2 == 0
end

.left(x) ⇒ Object

Raises:

  • (ArgumentError) 


117
118
119
120
121
 
# File 'lib/melos/tree.rb', line 117

def left(x)
  k = level(x)
  raise ArgumentError.new('leaf node has no children') if k == 0
  x ^ (0x01 << (k - 1))
end

.level(x) ⇒ Object 



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

def level(x)
  if x & 0x01 == 0
    return 0
  end
  k = 0
  while ((x >> k) & 0x01) == 1
    k += 1
  end
  return k
end

.log2(x) ⇒ Object 



81
82
83
84
85
86
87
88
89
90
 
# File 'lib/melos/tree.rb', line 81

def log2(x)
  if x == 0
    return 0
  end
  k = 0
  while (x >> k) > 0
    k += 1
  end
  return (k - 1)
end

.n_leaves(tree) ⇒ Object 



77
78
79
 
# File 'lib/melos/tree.rb', line 77

def n_leaves(tree)
  (tree.size + 1) / 2
end

.node_width(n) ⇒ Object 



103
104
105
106
107
108
109
 
# File 'lib/melos/tree.rb', line 103

def node_width(n)
  if n == 0
    0
  else
    2 * (n - 1) + 1
  end
end

.overlap_with_filtered_direct_path(x, filtered_direct_path, n) ⇒ Object 



190
191
192
193
194
195
196
197
198
199
 
# File 'lib/melos/tree.rb', line 190

def overlap_with_filtered_direct_path(x, filtered_direct_path, n)
  dx = Set.new([x]) | Set.new(direct_path(x, n))
  df = Set.new(filtered_direct_path)
  dxf = dx & df
  if dxf.size == 0
    raise ArgumentError.new('Failed to find overlap')
  end

  dxf.min { level(_1) }
end

.parent(x, n_leaves) ⇒ Object

Raises:

  • (ArgumentError) 


129
130
131
132
133
134
 
# File 'lib/melos/tree.rb', line 129

def parent(x, n_leaves)
  raise ArgumentError.new('root node has no parent') if x == root(n_leaves)
  k = level(x)
  b = (x >> (k + 1)) & 0x01
  (x | (1 << k)) ^ (b << (k + 1))
end

.resolution(tree, node_index) ⇒ Object 



225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
 
# File 'lib/melos/tree.rb', line 225

def resolution(tree, node_index)
  node = tree[node_index]
  if node.nil?
    if Melos::Tree.leaf?(node_index)
      # The resolution of a blank leaf node is the empty list.
      []
    else
      # The resolution of a blank intermediate node is the result of concatenating the resolution of its left child with the resolution of its right child, in that order.
      resolution(tree, Melos::Tree.left(node_index)) + resolution(tree, Melos::Tree.right(node_index))
    end
  else
    # The resolution of a non-blank node comprises the node itself, followed by its list of unmerged leaves, if any.
    if node.parent_node
      [node_index] + node.parent_node.unmerged_leaves.map { _1 * 2} # convert leaf index to node index
    else
      [node_index]
    end
  end
end

.right(x) ⇒ Object

Raises:

  • (ArgumentError) 


123
124
125
126
127
 
# File 'lib/melos/tree.rb', line 123

def right(x)
  k = level(x)
  raise ArgumentError.new('leaf node has no children') if k == 0
  x ^ (0x03 << (k - 1))
end

.root(n_leaves) ⇒ Object 



111
112
113
114
115
 
# File 'lib/melos/tree.rb', line 111

def root(n_leaves)
  w = node_width(n_leaves)

  (1 << log2(w)) - 1
end

.sibling(x, n_leaves) ⇒ Object 



136
137
138
139
140
141
142
143
 
# File 'lib/melos/tree.rb', line 136

def sibling(x, n_leaves)
  p = parent(x, n_leaves)
  if x < p
    right(p)
  else
    left(p)
  end
end

.sibling_from_leaf(x_of_leaf, x_of_ancestor, n_leaves) ⇒ Object

used for determining sibling of a node from an UpdatePath i.e. the node (sibling) on the copath side takes two node indexes and the # of leaves

Raises:

  • (ArgumentError) 


148
149
150
151
152
153
154
155
156
 
# File 'lib/melos/tree.rb', line 148

def sibling_from_leaf(x_of_leaf, x_of_ancestor, n_leaves)
  dp = direct_path(x_of_leaf, n_leaves)
  dp_including_self = [x_of_leaf] + dp
  raise ArgumentError.new('specified node is not an ancestor of leaf') unless dp.include?(x_of_ancestor)
  l = left(x_of_ancestor)
  r = right(x_of_ancestor)
  # if direct path (including self) includes left side, return right, else return left
  dp_including_self.include?(l) ? r : l
end

.truncate!(tree) ⇒ Object 



205
206
207
208
209
210
211
212
 
# File 'lib/melos/tree.rb', line 205

def truncate!(tree)
  root = root(n_leaves(tree))
  if tree[(root + 1)..]&.all?(nil)
    tree.slice!(root..) # keep left half of tree
    truncate!(tree) # then attempt to truncate again
  end
  # right half of tree has an element, so finish
end

Instance Method Details

#add(val) ⇒ Object

Raises:

  • (ArgumentError) 


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
 
# File 'lib/melos/tree.rb', line 17

def add(val)
  raise ArgumentError.new('Cannot add nil element') if val.nil?
  if @leaf_count == 0
    # initialize tree with one node
    @array = [val]
    @leaf_count = 1
  else
    # find leftmost empty leaf
    extend_tree = true
    for k in 0 .. (@leaf_count - 1) do
      if @array[k * 2].nil?
        @array[k * 2] = val
        extend_tree = false
        break
      end
    end
    if extend_tree
      # if tree is full, extend
      @leaf_count = @leaf_count * 2
      for k in 0 .. @leaf_count - 2
        @array[@leaf_count + k] = nil
      end
      @array[@leaf_count] = val
    end
  end
  @array
end

#leaf_at(leaf_index) ⇒ Object 



72
73
74
 
# File 'lib/melos/tree.rb', line 72

def leaf_at(leaf_index)
  @array[leaf_index * 2]
end

#remove_leaf(leaf_idx) ⇒ Object

Raises:

  • (ArgumentError) 


45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/melos/tree.rb', line 45

def remove_leaf(leaf_idx)
  raise ArgumentError.new('Cannot remove from empty tree') if @leaf_count == 0
  remove_node(leaf_idx * 2)
  # then if rigbt half of the tree is empty, truncate tree
  # q: do we recursively shrink tree?
  right_tree_empty = true
  for i in 0 .. (@leaf_count / 2) - 1 do
    if !@array[@leaf_count + 2 * i].nil?
      right_tree_empty = false
      break
    end
  end
  if right_tree_empty
    @array = @array.first(@leaf_count - 1)
    @leaf_count = @leaf_count / 2
  end
  @array
end

#remove_node(node_idx) ⇒ Object 



64
65
66
 
# File 'lib/melos/tree.rb', line 64

def remove_node(node_idx)
  @array[node_idx] = nil
end

#root ⇒ Object 



68
69
70
 
# File 'lib/melos/tree.rb', line 68

def root
  self.class.root(@leaf_count)
end