-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeafNode.java
66 lines (59 loc) · 2.24 KB
/
LeafNode.java
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
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class LeafNode extends Node {
//public class LeafNode {
// use a list of list so that each key can store multiple values
protected List<List<String>> values;
protected LeafNode nextSibling = null;
protected LeafNode preSibling = null;
// this constructor is used to create a brand new leaf node
public LeafNode(Double firstKey, String firstValue) {
isLeafNode = true;
keys = new ArrayList<Double>();
keys.add(firstKey);
values = new ArrayList<>();
List<String> bucket = new ArrayList<>();
bucket.add(firstValue);
values.add(bucket);
}
// this constructor is used to create a leaf node to store right half when a node is split
public LeafNode(List<Double> newKeys, List<List<String>> newValues) {
isLeafNode = true;
keys = new ArrayList<Double>(newKeys);
values = new ArrayList<>(newValues);
}
/*
insert key/value into this node so that it still remains sorted
*/
public void insertSorted(Double key, String value) {
List<String> bucket = new ArrayList<>();
bucket.add(value);
// when the inserting key is the smallest
if (key.compareTo(keys.get(0)) < 0) {
keys.add(0, key);
values.add(0, bucket);
} else if (key.compareTo(keys.get(keys.size() - 1)) > 0) {
//append to key list and values list
keys.add(key);
values.add(bucket);
} else{
ListIterator<Double> iterator = keys.listIterator();
while (iterator.hasNext()) {
Double compKey = iterator.next();
int position = iterator.previousIndex();
// insert into an existing key, append value to existing bucket
if (compKey.compareTo(key) == 0) {
values.get(position).add(value);
break;
}
// insert new key and new bucket
if (compKey.compareTo(key) > 0) {
keys.add(position, key);
values.add(position, bucket);
break;
}
}
}
}
}