Class: CompSci::KeyNode
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
-
#duplicates ⇒ Object
readonly
Returns the value of attribute duplicates.
-
#key ⇒ Object
readonly
Returns the value of attribute key.
Attributes inherited from Node
Class Method Summary collapse
Instance Method Summary collapse
-
#cidx(key) ⇒ Object
which child idx should handle key?.
-
#initialize(val, key: nil, children: 2, duplicates: false) ⇒ KeyNode
constructor
A new instance of KeyNode.
-
#insert(key, val) ⇒ Object
works for 2 or 3 children.
-
#search(key) ⇒ Object
returns a single node for binary search returns multiple nodes for ternary search.
-
#search2(key) ⇒ Object
returns a single node or nil.
-
#search3(key) ⇒ Object
returns an array of nodes, possibly empty.
- #to_s ⇒ Object
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 |