Repository navigation
Expand file tree
/
Copy pathBTreeLeafNode.java
More file actions
154 lines (122 loc) · 3.98 KB
/
Copy pathBTreeLeafNode.java
File metadata and controls
154 lines (122 loc) · 3.98 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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
152
153
154
class BTreeLeafNode<TKey extends Comparable<TKey>, TValue> extends BTreeNode<TKey> {
protected final static int LEAFORDER = 4;
private Object[] values;
public BTreeLeafNode() {
this.keys = new Object[LEAFORDER + 1];
this.values = new Object[LEAFORDER + 1];
}
@SuppressWarnings("unchecked")
public TValue getValue(int index) {
return (TValue)this.values[index];
}
public void setValue(int index, TValue value) {
this.values[index] = value;
}
@Override
public TreeNodeType getNodeType() {
return TreeNodeType.LeafNode;
}
@Override
public int search(TKey key) {
for (int i = 0; i < this.getKeyCount(); ++i) {
int cmp = this.getKey(i).compareTo(key);
if (cmp == 0) {
return i;
}
else if (cmp > 0) {
return -1;
}
}
return -1;
}
/* The codes below are used to support insertion operation */
public void insertKey(TKey key, TValue value) {
int index = 0;
while (index < this.getKeyCount() && this.getKey(index).compareTo(key) < 0)
++index;
this.insertAt(index, key, value);
}
private void insertAt(int index, TKey key, TValue value) {
// move space for the new key
for (int i = this.getKeyCount() - 1; i >= index; --i) {
this.setKey(i + 1, this.getKey(i));
this.setValue(i + 1, this.getValue(i));
}
// insert new key and value
this.setKey(index, key);
this.setValue(index, value);
++this.keyCount;
}
/**
* When splits a leaf node, the middle key is kept on new node and be pushed to parent node.
*/
@Override
protected BTreeNode<TKey> split() {
int midIndex = this.getKeyCount() / 2;
BTreeLeafNode<TKey, TValue> newRNode = new BTreeLeafNode<TKey, TValue>();
for (int i = midIndex; i < this.getKeyCount(); ++i) {
newRNode.setKey(i - midIndex, this.getKey(i));
newRNode.setValue(i - midIndex, this.getValue(i));
this.setKey(i, null);
this.setValue(i, null);
}
newRNode.keyCount = this.getKeyCount() - midIndex;
this.keyCount = midIndex;
return newRNode;
}
@Override
protected BTreeNode<TKey> pushUpKey(TKey key, BTreeNode<TKey> leftChild, BTreeNode<TKey> rightNode) {
throw new UnsupportedOperationException();
}
/* The codes below are used to support deletion operation */
public boolean delete(TKey key) {
int index = this.search(key);
if (index == -1)
return false;
this.deleteAt(index);
return true;
}
private void deleteAt(int index) {
int i = index;
for (i = index; i < this.getKeyCount() - 1; ++i) {
this.setKey(i, this.getKey(i + 1));
this.setValue(i, this.getValue(i + 1));
}
this.setKey(i, null);
this.setValue(i, null);
--this.keyCount;
}
@Override
protected void processChildrenTransfer(BTreeNode<TKey> borrower, BTreeNode<TKey> lender, int borrowIndex) {
throw new UnsupportedOperationException();
}
@Override
protected BTreeNode<TKey> processChildrenFusion(BTreeNode<TKey> leftChild, BTreeNode<TKey> rightChild) {
throw new UnsupportedOperationException();
}
/**
* Notice that the key sunk from parent is be abandoned.
*/
@Override
@SuppressWarnings("unchecked")
protected void fusionWithSibling(TKey sinkKey, BTreeNode<TKey> rightSibling) {
BTreeLeafNode<TKey, TValue> siblingLeaf = (BTreeLeafNode<TKey, TValue>)rightSibling;
int j = this.getKeyCount();
for (int i = 0; i < siblingLeaf.getKeyCount(); ++i) {
this.setKey(j + i, siblingLeaf.getKey(i));
this.setValue(j + i, siblingLeaf.getValue(i));
}
this.keyCount += siblingLeaf.getKeyCount();
this.setRightSibling(siblingLeaf.rightSibling);
if (siblingLeaf.rightSibling != null)
siblingLeaf.rightSibling.setLeftSibling(this);
}
@Override
@SuppressWarnings("unchecked")
protected TKey transferFromSibling(TKey sinkKey, BTreeNode<TKey> sibling, int borrowIndex) {
BTreeLeafNode<TKey, TValue> siblingNode = (BTreeLeafNode<TKey, TValue>)sibling;
this.insertKey(siblingNode.getKey(borrowIndex), siblingNode.getValue(borrowIndex));
siblingNode.deleteAt(borrowIndex);
return borrowIndex == 0 ? sibling.getKey(0) : this.getKey(0);
}
}