class Node[K] extends Error
The Node class defines a splittable node type with methods for finding
entries (keys and values).
- Alphabetic
- By Inheritance
- Node
- Error
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
-
new
Node(lt: Node[K], kd: K, rt: Node[K], half: Int)(implicit arg0: (K) ⇒ Ordered[K], arg1: ClassTag[K])
Construct a new root node with one key (and two references) in it.
Construct a new root node with one key (and two references) in it.
- lt
the left node
- kd
the divider key
- rt
the right node
-
new
Node(isLeaf: Boolean = true, half: Int = 2)(implicit arg0: (K) ⇒ Ordered[K], arg1: ClassTag[K])
- isLeaf
whether the node is a leaf (true) or internal node (false)
- half
half the maximum number of keys allowed in a ndoe
Value Members
-
def
find(k: K): Int
Find the "<=" position of key 'k' in 'this' node.
Find the "<=" position of key 'k' in 'this' node. If 'k' is larger than all keys in 'this' node, return 'nkeys'.
- k
the key whose position is sought
-
final
def
flaw(method: String, message: String): Unit
Show the flaw by printing the error message.
Show the flaw by printing the error message.
- method
the method where the error occurred
- message
the error message
- Definition Classes
- Error
- val half: Int
-
def
isFull: Boolean
Determine whether 'this' mode is currently full.
- val isLeaf: Boolean
-
val
key: Array[K]
The array of keys
-
val
mx: Int
The maximum number of keys
-
var
nKeys: Int
The number of active keys
-
val
ref: Array[Any]
The array of references
-
def
split(): (K, Node[K])
Split 'this' node by creating a right sibling 'rt' and moving half the keys and references to that new node.
Split 'this' node by creating a right sibling 'rt' and moving half the keys and references to that new node. Return the divider key and the right sibling node.
-
def
toString(): String
Convert 'this' node to a string.
Convert 'this' node to a string.
- Definition Classes
- Node → AnyRef → Any
-
def
wedge(k: K, v: Any, ip: Int, left: Boolean = true): Unit
When space is available, wedge the new key 'k' and value 'v' into 'this' node at the given insertion position 'ip'.
When space is available, wedge the new key 'k' and value 'v' into 'this' node at the given insertion position 'ip'.
- k
the new key
- v
the new value
- ip
the insertion position
- left
whether to start with from the left size of the key