Class: Btree::Node

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

Instance Method Summary collapse

Constructor Details

#initialize(degree) ⇒ Node

Returns a new instance of Node.



2
3
4
5
6
 
# File 'lib/btree/node.rb', line 2

def initialize(degree)
  @degree = degree
  @keys = []
  @children = []
end

Instance Method Details

#add_child(node) ⇒ Object 



21
22
23
 
# File 'lib/btree/node.rb', line 21

def add_child(node)
  @children << node
end

#children ⇒ Object 



25
26
27
 
# File 'lib/btree/node.rb', line 25

def children
  @children.dup.freeze
end

#dump(level = 0) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
 
# File 'lib/btree/node.rb', line 8

def dump(level = 0)
  @keys.each_with_index do |key, idx|
    puts "LEVEL: #{level} => #{key.first}: full? #{full?} leaf? #{leaf?} children: #{values.inspect}"
    if @children[idx]
       @children[idx].dump(level + 1)
    end
  end
  (@children[@keys.size..-1] || []).each do |c|
    c.dump(level+1)
  end
  nil
end

#full? ⇒ Boolean

Returns:

  • (Boolean) 


37
38
39
 
# File 'lib/btree/node.rb', line 37

def full?
  size >= 2 * @degree - 1
end

#insert(key, value) ⇒ Object 



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/btree/node.rb', line 91

def insert(key, value)
  i = size - 1
  #puts "INSERTING #{key} INTO NODE: #{self.inspect}"
  if leaf?
    raise "Duplicate key" if @keys.any?{|(k,v)| k == key }  #OPTIMIZE: This is inefficient
    while i >= 0 && @keys[i] && key < @keys[i].first
      @keys[i+1] = @keys[i]
      i -= 1
    end
    @keys[i+1] = [key, value]
  else
    while i >= 0 && @keys[i] &&  key < @keys[i].first
      i -= 1
    end
    #puts "   -- INSERT KEY INDEX #{i}"
    if @children[i+1] && @children[i+1].full?
      split(i+1)
      if key > @keys[i+1].first
        i += 1
      end
    end
    @children[i+1].insert(key, value)
  end
end

#keys ⇒ Object 



29
30
31
 
# File 'lib/btree/node.rb', line 29

def keys
  @keys.map(&:first).freeze
end

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/btree/node.rb', line 41

def leaf?
  @children.length == 0
end

#size ⇒ Object 



45
46
47
 
# File 'lib/btree/node.rb', line 45

def size
  @keys.size
end

#split(child_idx) ⇒ Object 



116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/btree/node.rb', line 116

def split(child_idx)
  raise "Invalid child index #{child_idx} in split, num_children = #{@children.size}" if child_idx < 0 || child_idx >= @children.size
  #puts "SPLIT1: #{self.inspect}"
  splitee = @children[child_idx]
  y = Btree::Node.new(@degree)
  z = Btree::Node.new(@degree)
  (@degree-1).times do |j|
    z._keys[j] = splitee._keys[j+@degree]
    y._keys[j] = splitee._keys[j]
  end
  if !splitee.leaf?
    @degree.times do |j|
      z._children[j] = splitee._children[j+@degree]
      y._children[j] = splitee._children[j]
    end
  end
  mid_val = splitee._keys[@degree-1]
  #puts "SPLIT2: #{self.inspect}"
  (@keys.size).downto(child_idx) do |j|
    @children[j+1] = @children[j]
  end

  @children[child_idx+1] = z
  @children[child_idx] = y
  
  #puts "SPLIT3: #{self.inspect}"

  (@keys.size - 1).downto(child_idx) do |j|
    @keys[j+1] = @keys[j]
  end

  #puts "SPLIT4: #{self.inspect}"

  @keys[child_idx] = mid_val
  #puts "SPLIT5: #{self.inspect}"
end

#value_of(key) ⇒ Object 



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/btree/node.rb', line 68

def value_of(key)

  return values_of(key) if key.kind_of? Range

  i = 1
  while i <= size && key > @keys[i-1].first
    i += 1
  end

  #puts "Getting value of key #{key}, i = #{i}, keys = #{@keys.inspect}, leaf? #{leaf?}, numchildren: #{@children.size}"

  if i <= size && key == @keys[i-1].first
    #puts "Found key: #{key.inspect}"
    return @keys[i-1].last
  elsif leaf?
    #puts "We are a leaf, no more children, so val is nil"
    return nil
  else
    #puts "Looking into child #{i}"
    return @children[i-1].value_of(key)
  end
end

#values ⇒ Object 



33
34
35
 
# File 'lib/btree/node.rb', line 33

def values
  @keys.map(&:last).freeze
end

#values_of(range) ⇒ Object 



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/btree/node.rb', line 49

def values_of(range)

  result = Array.new

  i = 1
  while i <= size && range.end >= @keys[i-1].first
    if range.cover? @keys[i-1].first
      result << @keys[i-1].last
      child = @children[i-1].values_of(range) unless leaf?
      result += child if child
    end
    i += 1
  end

  result

end