Class: CompSci::KeyNode

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

Overview

adds a key to Node; often the key is used to place the node in the tree, independent of the value; e.g. key=priority, value=process_id

Defined Under Namespace

Classes: DuplicateKey, SearchError

Instance Attribute Summary collapse

Attributes inherited from Node

#children, #metadata, #value

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Node

#[], #[]=, #display, display_line, #inspect

Constructor Details

#initialize(val, key: nil, children: 2, duplicates: false) ⇒ KeyNode

Returns a new instance of KeyNode.



79
80
81
82
 
# File 'lib/compsci/node.rb', line 79

def initialize(val, key: nil, children: 2, duplicates: false)
  super(val, children: children)
  @key, @duplicates = key, duplicates
end

Instance Attribute Details

#duplicates ⇒ Object (readonly)

Returns the value of attribute duplicates.



64
65
66
 
# File 'lib/compsci/node.rb', line 64

def duplicates
  @duplicates
end

#key ⇒ Object (readonly)

Returns the value of attribute key.



64
65
66
 
# File 'lib/compsci/node.rb', line 64

def key
  @key
end

Class Method Details

.key_cmp_idx(new_key, key, child_slots: 2, duplicates: false) ⇒ Object 



66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/compsci/node.rb', line 66

def self.key_cmp_idx(new_key, key, child_slots: 2, duplicates: false)
  if child_slots < 2
    raise(ArgumentError, "child_slots: #{child_slots} too small")
  elsif child_slots == 2
    raise(DuplicateKey, "#{new_key}") if new_key == key and !duplicates
    new_key < key ? 0 : 1
  elsif child_slots == 3
    (new_key <=> key) + 1
  else
    raise(ArgumentError: "child_slots: #{child_slots} too big")
  end
end

Instance Method Details

#cidx(key) ⇒ Object

which child idx should handle key?



89
90
91
92
93
 
# File 'lib/compsci/node.rb', line 89

def cidx(key)
  self.class.key_cmp_idx(key, @key,
                         child_slots: @children.size,
                         duplicates: @duplicates)
end

#insert(key, val) ⇒ Object

works for 2 or 3 children



96
97
98
99
100
101
102
103
104
105
 
# File 'lib/compsci/node.rb', line 96

def insert(key, val)
  idx = self.cidx(key)
  if @children[idx]
    @children[idx].insert(key, val)
  else
    @children[idx] = self.class.new(val, key: key,
                                    children: @children.size,
                                    duplicates: @duplicates)
  end
end

#search(key) ⇒ Object

returns a single node for binary search returns multiple nodes for ternary search



109
110
111
112
113
114
115
116
117
 
# File 'lib/compsci/node.rb', line 109

def search(key)
  if @children.size == 2
    self.search2(key)
  elsif @children.size == 3
    self.search3(key)
  else
    raise(SearchError, "can't search for @children.size children")
  end
end

#search2(key) ⇒ Object

returns a single node or nil



120
121
122
123
124
 
# File 'lib/compsci/node.rb', line 120

def search2(key)
  return self if key == @key
  child = @children[self.cidx(key)]
  child.search(key) if child
end

#search3(key) ⇒ Object

returns an array of nodes, possibly empty



127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/compsci/node.rb', line 127

def search3(key)
  if key == @key
    nodes = [self]
    node = @children[1]
    while node
      nodes << node
      node = node.children[1]
    end
    return nodes
  end
  child = @children[self.cidx(key)]
  child ? child.search(key) : []
end

#to_s ⇒ Object 



84
85
86
 
# File 'lib/compsci/node.rb', line 84

def to_s
  [@key, @value].join(':')
end