Class: Salgo::Btree::Node

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Node

Returns a new instance of Node.



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

def initialize()
    @keys  = []
    @nodes = []
end

Instance Attribute Details

#keys ⇒ Object

Returns the value of attribute keys.



30
31
32
 
# File 'lib/salgo/btree.rb', line 30

def keys
  @keys
end

#nodes ⇒ Object

Returns the value of attribute nodes.



30
31
32
 
# File 'lib/salgo/btree.rb', line 30

def nodes
  @nodes
end

Instance Method Details

#find_node_containing_key(key) ⇒ Object 



110
111
112
113
114
115
116
117
118
119
 
# File 'lib/salgo/btree.rb', line 110

def find_node_containing_key(key)
    @keys.each_with_index do |node_key, i|
        if ( key < node_key )
            return @nodes[i]
        end
    end
        
    # If no throw, we assign the last node because key is bigger (or equal to) all our keys.
    return @nodes[-1]
end

#find_node_or_key_containing_key(key) ⇒ Object

Similar to find_node_containing_key, but considers keys as they node is iterated through. An array of Salgo::Btree::Node or Salgo::Btree::Key object will be returned with the second element set to the index of the node.

If it is a key, then the key holds a match. If a node, then the node subtree that should be expanded and searched.



97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/salgo/btree.rb', line 97

def find_node_or_key_containing_key(key)

    @keys.each_with_index do |node_key, i|
        if ( key == node_key )
            return [ node_key, i ]
        elsif ( key < node_key )
            return [ @nodes[i], i ]
        end
    end

    return [ @nodes[-1], @nodes.size - 1 ]
end

#first_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


156
157
158
 
# File 'lib/salgo/btree.rb', line 156

def first_node?(node)
    @nodes[0].equal?(node)
end

#insert(new_key, left_node = nil, right_node = nil) ⇒ Object

Assume we have enough space to insert in the node. If two sub-trees are specified, it is assumed that they are replacing the subtree that the new_key was in. That sub-tree is replaced with the left_node and the right_node is inserted after the left_node’s index.



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/salgo/btree.rb', line 42

def insert(new_key, left_node=nil, right_node=nil)
    
    # Caution code.
    throw Exception.new(
        "Both right and left nodes must be nil or defined. One is not: #{right_node} #{left_node}") if (
            right_node.nil? ^ left_node.nil? )
    
    insertion_point = 0
    
    catch(:foundI) do
        @keys.each_with_index do |node_key, index| 
            if ( new_key < node_key )
                insertion_point = index
                throw :foundI
            end
        end
        
        insertion_point = @keys.size
    end
    
    @keys.insert(insertion_point, new_key)
    @nodes[insertion_point] = left_node if left_node
    @nodes.insert(insertion_point+1, right_node) if right_node
    
end

#last_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


152
153
154
 
# File 'lib/salgo/btree.rb', line 152

def last_node?(node)
    @nodes[-1].equal?(node)
end

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


86
87
88
 
# File 'lib/salgo/btree.rb', line 86

def leaf?()
    @nodes.size == 0
end

#put(index, key, node) ⇒ Object 



142
143
144
145
 
# File 'lib/salgo/btree.rb', line 142

def put(index, key, node)
    @keys.insert(index, key)
    @nodes.insert(index, node) if node
end

#put_max(key, node) ⇒ Object 



137
138
139
140
 
# File 'lib/salgo/btree.rb', line 137

def put_max(key, node)
    @keys.push(key)
    @nodes.push(node) if node
end

#put_min(key, node) ⇒ Object 



147
148
149
150
 
# File 'lib/salgo/btree.rb', line 147

def put_min(key, node)
    @keys.unshift(key)
    @nodes.unshift(node) if node
end

#split ⇒ Object

This node will split itself and return a list of 3 items, [key, left_node, right_node ].



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/salgo/btree.rb', line 69

def split()
    
    node_partition = @nodes.size / 2
    key_partition = @keys.size / 2
    
    left_node = Node.new()
    right_node = Node.new()
    
    left_node.nodes = @nodes[0...node_partition]
    right_node.nodes = @nodes[node_partition..-1]

    left_node.keys = @keys[0...key_partition]
    right_node.keys = @keys[key_partition+1..-1]
    
    [ @keys[key_partition], left_node, right_node ]
end

#take(index) ⇒ Object 



127
128
129
 
# File 'lib/salgo/btree.rb', line 127

def take(index)
    [ @keys.delete_at(index), @nodes.delete_at(index) ]
end

#take_max ⇒ Object

Return an array of the max-key and the max-node from this node. There may or may not be a max-node.



133
134
135
 
# File 'lib/salgo/btree.rb', line 133

def take_max()
    [ @keys.pop, @nodes.pop ]
end

#take_min ⇒ Object

Return an array of the min-key and min-node from this node. There may or may not be a min-node.



123
124
125
 
# File 'lib/salgo/btree.rb', line 123

def take_min()
    [ @keys.shift, @nodes.shift ]
end