/**
* Leaf node for B+Tree
* leaf node has prev and next connections in B+Tree
* @param order
*/
public BLeafNode(int order) {
super(order);
this.prev = null;
this.next = null;
}
/**
* Adds a key to the node. Splitting if necessary.
*
* @param key to be inserted.
*/
@Override
public void insert(T key, List<BNode<T>> path) {
// Ensure input is not null.
if (key == null)
throw new IllegalArgumentException("Input cannot be null");
path.add(this);
for (int i = 0; i < this.keys.size(); i++) {
if (key.compareTo(this.keys.get(i)) <= 0) {
this.keys.add(i, key);
return;
}
}
this.keys.add(key);
}
/**
* Adds a key to the node. Splitting if necessary.
*
* @param key to be inserted.
*/
@Override
public void insert(T key, List<BNode<T>> path) {
// Ensure input is not null.
if (key == null)
throw new IllegalArgumentException("Input cannot be null");
path.add(this);
// non-leaf node does not insert, pass to leaf node to insert in B+Tree
for (int i = 0; i < this.keys.size(); i++) {
if (key.compareTo(this.keys.get(i)) <= 0) {
this.children.get(i).insert(key, path);
return;
}
}
this.children.get(this.children.size() - 1).insert(key, path);
}
/**
* get the key from the node.
*
* @param key to be searched.
*/
@Override
public List<T> get(T key) {
List<T> keys = new ArrayList<>();
BLeafNode<T> current = this;
// search current node
keys.addAll(current.simpleGet(key);
current = current.next;
// search a series of consecutive nodes to get all values in B+Tree
while (current != null) {
List<T> newKeys = current.simpleGet(key);
keys.addAll(newKeys);
if (current.keys.size() != newKeys.size()) {
break;
}
current = current.next;
}
return keys;
}
/**
* get the key from one node only.
*
* @param key to be searched.
*/
public List<T> simpleGet(T key) {
if (key == null) {
return null;
}
List<T> keys = new ArrayList<>();
for (T t : this.keys) {
if (t.compareTo(key) == 0) {
keys.add(t);
}
}
return keys;
}
/**
* Get a key from the tree.
*
* @param key to be searched.
*/
@Override
public List<T> get(T key) {
if (key == null) {
return null;
}
// non-leaf node does not get, pass to leaf node to get in B+Tree
for (int i = 0; i < this.keys.size(); i++) {
if (this.keys.get(i).compareTo(key) >= 0) {
return this.children.get(i).get(key);
}
}
return this.children.get(this.children.size() - 1).get(key);
}
/**
* B+Tree
*
* @param <T> the generic type this B+Tree uses. It extends comparable
* which allows us to order two of the same type.
*/
public class BTree<T extends Comparable<T>> {
/**
* Fields of a B+Tree.
* <p>
* Notice that we keep track of the root of the B+Tree. This is because
* of the nature of the B+Tree. It grows upwards! Unless you can return the
* root each time (which is a possible implementation approach) you will need
* to keep track of the root.
*/
private int order; // Order of the BTree.
private BNode<T> root; // Root node of the BTree.
/**
* Constructor which sets the field 'order'
*
* @param order of the BTree.
*/
public BTree(int order) {
this.order = order;
root = new BLeafNode<T>(order);
}
/**
* Adds key to the BTree.
*
* @param key to be inserted.
*/
public void insert(T key) {
// Ensure input is not null.
if (key == null)
throw new IllegalArgumentException("Input cannot be null");
List<BNode<T>> path = new ArrayList<BNode<T>>();
root.insert(key, path);
// split if required
for (int i = path.size() - 1; i > 0; i--) {
if (path.get(i).keys.size() == order) {
split(path.get(i - 1), path.get(i));
}
}
// split root if required
if (root.keys.size() == order) {
BTreeNode<T> newRoot = new BTreeNode<>(order);
split(newRoot, root);
root = newRoot;
}
}
public List<T> get(T key) {
if (key == null) {
throw new IllegalArgumentException("Input cannot be null");
}
if (root != null) {
return root.get(key);
}
return null;
}
/**
* Will conduct a split on the provided indexed child of the provided node.
*
* @param node The current node whose provided child to split will be split.
* @param childToSplit The child to split within the provided node.
*/
private void split(BNode<T> node, BNode<T> childToSplit) {
// Ensure neither input is null.
if (node == null || childToSplit == null)
throw new IllegalArgumentException("Input cannot be null");
// Get median key
int med = childToSplit.keys.size() / 2;
T medValue = childToSplit.keys.get(med);
if (childToSplit instanceof BTreeNode) {
// not leaf
BTreeNode<T> leftNode = new BTreeNode<>(order);
BTreeNode<T> rightNode = new BTreeNode<>(order);
// here use med not med+1 to let med value goes up
leftNode.keys = childToSplit.keys.get(0, med);
rightNode.keys = childToSplit.keys.get(med + 1, order);
leftNode.children = ((BTreeNode<T>) childToSplit).children.get(0, med + 1);
rightNode.children = ((BTreeNode<T>) childToSplit).children.get(med + 1, order + 1);
boolean found = false;
int i = 0;
for (; i < node.keys.size(); i++) {
if (medValue.compareTo(node.keys.get(i)) <= 0) {
node.keys.add(i, medValue);
found = true;
break;
}
}
if (!found) {
node.keys.add(medValue);
}
((BTreeNode<T>) node).children.remove(childToSplit);
((BTreeNode<T>) node).children.add(i, leftNode);
((BTreeNode<T>) node).children.add(i + 1, rightNode);
} else {
// leaf node
BLeafNode<T> leftNode = new BLeafNode<>(order);
BLeafNode<T> rightNode = new BLeafNode<>(order);
// here use med+1 not med to let the med value also stays at left leaf
leftNode.keys = childToSplit.keys.get(0, med + 1);
rightNode.keys = childToSplit.keys.get(med + 1, order);
// reset connections
leftNode.prev = ((BLeafNode<T>) childToSplit).prev;
leftNode.next = rightNode;
rightNode.prev = leftNode;
rightNode.next = ((BLeafNode<T>) childToSplit).next;
boolean found = false;
int i = 0;
for (; i < node.keys.size(); i++) {
if (medValue.compareTo(node.keys.get(i)) <= 0) {
node.keys.add(i, medValue);
found = true;
break;
}
}
if (!found) {
node.keys.add(medValue);
}
((BTreeNode<T>) node).children.remove(childToSplit);
((BTreeNode<T>) node).children.add(i, leftNode);
((BTreeNode<T>) node).children.add(i + 1, rightNode);
}
}
public class IndexPostObj implements Comparable<IndexPostObj> {
PostObj postObj;
String index;
public IndexPostObj(PostObj postObj, String index) {
this.postObj = postObj;
this.index = index;
}
/**
* compare by index, used in b+tree
* @param indexPostObj the index - post obj
* @return greater or smaller
*/
@Override
public int compareTo(IndexPostObj indexPostObj) {
return this.index.compareTo(indexPostObj.index);
}
}
/**
* extract post object from json string
*
* @param jsonString the json string to extract
* @return list of post obj
*/
public List<PostObj> extractPostObj(String jsonString) {
List<PostObj> postObjs = new ArrayList<PostObj>();
try {
JSONObject json = new JSONObject(jsonString);
JSONArray posts = (JSONArray) json.get("allpost");
// extract all fields, and then create new postobj
for (int i = 0; i < posts.length(); i++) {
JSONObject post = (JSONObject) posts.get(i);
String imageUrl = post.getString("img_url");
int commentCount = post.getInt("comment_count");
int likeCount = post.getInt("like_count");
String text = post.getString("text");
PostObj postObj = new PostObj(imageUrl, commentCount, likeCount, text);
postObjs.add(postObj);
}
} catch (Exception e) {
e.printStackTrace();
}
return postObjs;
}
/**
* extract tag and add tag post obj to b+tree
*
* @param postObjs the list of post obj
* @return btree of index post obj
*/
public BTree<IndexPostObj> extractTagPostObj(List<PostObj> postObjs) {
Pattern pattern = Pattern.compile(HASHTAG_REGEX);
BTree<IndexPostObj> bTree = new BTree<>(ORDER);
for (PostObj postObj : postObjs) {
List<String> indexes = new ArrayList<String>();
boolean matchFound = true;
String textString = postObj.text;
while (matchFound && !textString.equals("")) {
Matcher matcher = pattern.matcher(textString);
matchFound = matcher.find();
if (matchFound) {
String index = matcher.group(0);
if (!indexes.contains(index))
indexes.add(index);
textString = textString.substring(matcher.end());
}
}
if (indexes.size() != 0) {
for (String index : indexes) {
bTree.insert(new IndexPostObj(postObj, index));
}
} else {
bTree.insert(new IndexPostObj(postObj, "#NoTag"));
}
}
return bTree;
}
/**
* query all post obj given tag
*
* @param tag to search
* @return list of post obj
*/
public List<PostObj> queryTag(String tag) {
List<PostObj> returnedPostObjs = new ArrayList<>();
List<IndexPostObj> indexPostObjs = this.tagTree.get(new IndexPostObj(null, tag));
for (IndexPostObj indexPostObj : indexPostObjs) {
returnedPostObjs.add(indexPostObj.postObj);
}
return returnedPostObjs;
}
/**
* query all post obj given user
*
* @param user to search
* @return list of post obj
*/
public List<PostObj> queryUser(String user) {
List<PostObj> returnedPostObjs = new ArrayList<>();
List<IndexPostObj> indexPostObjs = this.userTree.get(new IndexPostObj(null, user));
for (IndexPostObj indexPostObj : indexPostObjs) {
returnedPostObjs.add(indexPostObj.postObj);
}
return returnedPostObjs;
}
public List<PostObj> queryPost() {
return this.postObjs;
}
