Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.ByteArrayInputStream;
- import java.io.ByteArrayOutputStream;
- import java.io.IOException;
- import java.io.ObjectInputStream;
- import java.io.ObjectOutputStream;
- import java.io.RandomAccessFile;
- import java.util.ArrayList;
- public class Test {
- public static void main(String[] args) throws IOException, ClassNotFoundException {
- //JsoupTestStringManipulating();
- //testAdd();
- //testFindPredecessor();
- //testDelete();
- //testPrefexFind();
- //testSave();
- testSave2();
- }
- public static void JsoupTestStringManipulating(){
- JsoupParser pars = new JsoupParser();
- String word = "Spike Spegal";
- String URL = "http://en.wikipedia.org/wiki/Zombie";
- for(String s: pars.urlTrimming(URL)){
- System.out.println("words: "+s);
- }
- System.out.println(pars.getPadding(word.length()));
- }
- public static void testAdd() throws IOException, ClassNotFoundException{
- BTree tree = new BTree();
- String padding,fixedString;
- ArrayList<String> testWords = new ArrayList<String>();
- testWords.add("apple");
- testWords.add("sand");
- testWords.add("math");
- testWords.add("tree");
- testWords.add("north");
- testWords.add("onion");
- testWords.add("pan");
- testWords.add("pink");
- testWords.add("pool");
- testWords.add("net");
- testWords.add("never");
- for(String k : testWords){
- padding = getPadding(k.length());
- fixedString = k + padding;
- tree.insert(fixedString);
- }
- Node temp1,temp2,temp3,temp4,temp5,temp6,temp7,temp8,root;
- root = tree.per.read(0);
- temp1 = tree.per.read(root.links.get(0));
- temp2 = tree.per.read(root.links.get(1));
- temp3 = tree.per.read(temp1.links.get(0));
- temp4 = tree.per.read(temp1.links.get(1));
- temp5 = tree.per.read(temp1.links.get(2));
- temp6 = tree.per.read(temp2.links.get(0));
- temp7 = tree.per.read(temp2.links.get(1));
- temp8 = tree.per.read(temp2.links.get(2));
- /*
- System.out.println("root: "+root.keys);
- System.out.println("left: "+temp1.keys);
- System.out.println("right: "+temp2.keys);
- System.out.println("left 0: "+temp3.keys);
- System.out.println(" left 1: "+temp4.keys);
- System.out.println(" left 2: "+temp5.keys);
- System.out.println(" right 0: "+temp6.keys);
- System.out.println(" right 1: "+temp7.keys);
- System.out.println(" right 2: "+temp8.keys);
- System.out.println("node count: "+tree.getNodeCount());
- */
- System.out.println("root: "+root.getStartIndex());
- System.out.println("left: "+temp1.getStartIndex());
- System.out.println("right: "+temp2.getStartIndex());
- System.out.println("left 0: "+temp3.getStartIndex());
- System.out.println(" left 1: "+temp4.getStartIndex());
- System.out.println(" left 2: "+temp5.getStartIndex());
- System.out.println(" right 0: "+temp6.getStartIndex());
- System.out.println(" right 1: "+temp7.getStartIndex());
- System.out.println(" right 2: "+temp8.getStartIndex());
- System.out.println("node count: "+tree.getNodeCount());
- }
- public static void testFindPredecessor() throws IOException, ClassNotFoundException{
- BTree tree = new BTree();
- tree.insert("apple");
- tree.insert("sand");
- tree.insert("math");
- tree.insert("tree");
- tree.insert("north");
- tree.insert("onion");
- tree.insert("pan");
- tree.insert("pink");
- tree.insert("pool");
- System.out.println("get predicessor: "+tree.getRoot().predacessor(0));
- }
- public static void testDelete() throws IOException, ClassNotFoundException{
- BTree tree = new BTree();
- tree.insert("apple");
- tree.insert("sand");
- tree.insert("math");
- tree.insert("tree");
- tree.insert("north");
- tree.insert("onion");
- tree.insert("pan");
- tree.insert("pink");
- tree.insert("pool");
- tree.insert("net");
- tree.insert("never");
- tree.delete("apple");
- /*
- System.out.println("root: "+tree.getRoot().keys);
- System.out.println("left: "+tree.getRoot().links.get(0).keys);
- System.out.println("right: "+tree.getRoot().links.get(1).keys);
- System.out.println(" left 0: "+tree.getRoot().links.get(0).links.get(0).keys);
- System.out.println(" left 1: "+tree.getRoot().links.get(0).links.get(1).keys);
- //System.out.println(" left 2: "+tree.getRoot().links.get(0).links.get(2).keys);
- System.out.println(" right 0: "+tree.getRoot().links.get(1).links.get(0).keys);
- System.out.println(" right 1: "+tree.getRoot().links.get(1).links.get(1).keys);
- System.out.println(" right 2: "+tree.getRoot().links.get(1).links.get(2).keys);
- */
- }
- public static void testPrefexFind() throws IOException, ClassNotFoundException{
- BTree tree = new BTree();
- tree.insert("apple");
- tree.insert("sand");
- tree.insert("math");
- tree.insert("tree");
- tree.insert("north");
- tree.insert("onion");
- tree.insert("pan");
- tree.insert("pink");
- tree.insert("pool");
- tree.insert("net");
- tree.insert("never");
- System.out.println(tree.findPrefix("s"));
- }//end prefex test
- private static String getPadding(int wordLength){
- int diffrence;
- String pad =" ";
- String padding = "";
- diffrence = 34 - wordLength;
- for(int i =0; i < diffrence;i++){
- padding = padding + pad;
- }// end for
- return padding;
- }
- public static void testSave() throws IOException,ClassNotFoundException{
- Node node = new Node();
- node.keys.add("apple");
- node.keys.add("math");
- node.keys.add("sand");
- ByteArrayOutputStream b2 = new ByteArrayOutputStream();
- ObjectOutputStream OOS = new ObjectOutputStream(b2);
- OOS.writeObject(node);
- byte[] array = b2.toByteArray();
- ByteArrayInputStream in2 = new ByteArrayInputStream(array);
- ObjectInputStream OIS = new ObjectInputStream(in2);
- Node temp = (Node) OIS.readObject();
- OIS.close();
- for(String s : temp.keys){
- System.out.println(s);
- }
- }
- public static void testSave2() throws IOException,ClassNotFoundException{
- ArrayList<Node>nodeList = new ArrayList<Node>();
- RandomAccessFile raf = new RandomAccessFile("Test.dat","rw");
- byte[] recivingAry;
- Node node = new Node();
- Node node2 = new Node();
- node.setStartIndex(0);
- node2.setStartIndex(560);
- node.keys.add("apple");
- node.keys.add("math");
- node.keys.add("sand");
- node2.keys.add("candle");
- node2.keys.add("final");
- node2.keys.add("better");
- node.links.add((long) 560);
- nodeList.add(node);
- nodeList.add(node2);
- ByteArrayOutputStream b2 = new ByteArrayOutputStream();
- ObjectOutputStream OOS = new ObjectOutputStream(b2);
- for(Node n : nodeList){
- OOS.writeObject(n);
- byte[] array = b2.toByteArray();
- raf.write(array);
- }
- // byte[] array = b2.toByteArray();
- // raf.write(array);
- recivingAry = new byte[560];
- raf.seek(0);
- raf.read(recivingAry);
- ByteArrayInputStream in2 = new ByteArrayInputStream(recivingAry);
- ObjectInputStream OIS = new ObjectInputStream(in2);
- Node temp = (Node) OIS.readObject();
- if(temp.links.size()!= 0){
- recivingAry = new byte[560];
- //System.out.raf.length();
- raf.seek(temp.links.get(0));
- raf.read(recivingAry);
- ByteArrayInputStream in1 = new ByteArrayInputStream(recivingAry);
- ObjectInputStream OIS1 = new ObjectInputStream(in2);
- Node temp1 = (Node) OIS.readObject();
- for(String s1:temp1.keys){
- System.out.println(s1);
- }
- }
- OIS.close();
- for(String s : temp.keys){
- System.out.println(s);
- }
- }
- }//end class
- import java.io.IOException;
- import java.io.Serializable;
- import java.util.ArrayList;
- // this needs to use the trees persist instead of its own.
- public class Node implements Serializable{
- private static final long serialVersionUID = 1L;
- ArrayList<Node> temp = new ArrayList<Node>();
- final int MAXKEYS = 3; //31
- final int middle = MAXKEYS/2;
- ArrayList<String> keys = new ArrayList<String>();
- ArrayList<Long> links = new ArrayList<Long>();
- int incrementSize =2048;//2364 - for 31 keys 32 links/ 394 - for 3 keys 4 links
- long startIndex;
- BTree tree;
- public Node(){
- }
- public boolean isLeaf(){
- if(links.size() == 0)
- {
- return true;
- }
- else
- return false;
- }// end is leaf
- public boolean isFull(){
- if(keys.size() == MAXKEYS)
- {
- return true;
- }
- else{
- return false;
- }
- }//end isFull
- public void split(Node link, int nodeCount) throws IOException{
- Node right = new Node();
- right.setStartIndex(nodeCount * incrementSize);
- String middleVal;
- int count = 0;
- //get right
- while(link.keys.size()> middle+1){
- right.keys.add(link.keys.remove(middle+1));
- }
- //get the middle value
- middleVal= link.keys.remove(link.keys.size()-1);
- //compare the keys to the middle guy
- for(String value: keys){
- if(middleVal.compareTo(value)>0){
- count++;
- }
- }
- //add keys and links in proper spot
- keys.add(count,middleVal);
- links.add(count+1,(long) (nodeCount * incrementSize));
- // i will need to send per the incrament size
- tree.per.write(right);
- }//end split
- //look over how i write to splits
- public void rootSplit(int nodeCount) throws IOException{
- int leftCount = nodeCount -1;
- long offLeft = (leftCount * incrementSize);
- long offRight = (nodeCount * incrementSize);
- Node myLeft = makeNewLeft();
- Node myRight = makeNewRight();
- if(!links.isEmpty()){
- addLeftLinks(myLeft);
- addRightLinks(myRight);
- }
- hookLinks(offLeft,offRight);
- //send in the new incrament size
- temp.add(myLeft);
- temp.add(myRight);
- //tree.per.write(myLeft);
- //tree.per.write(myRight);
- }//end split root
- private Node makeNewLeft(){
- int mid = middle;
- Node left = new Node();
- //get all the left keys
- for(int i =0; i < mid;i++){
- left.keys.add(keys.remove(i));
- }//end for
- return left;
- }// end makeNewLeft
- private void addLeftLinks(Node left){
- int mid = middle+1;
- for(int i =0; i<mid;i++){
- left.links.add(links.remove(0));
- }//end for
- }//end add left links
- private Node makeNewRight(){
- Node right = new Node();
- //get all the keys from the right
- while(keys.size() >1){
- right.keys.add(keys.remove(1));
- }
- return right;
- }// end makeNewRight
- private void addRightLinks(Node right){
- right.links.addAll(links);
- links.clear();
- }//end add right links
- // this needs to take in the incrament size
- private void hookLinks(long offleft,long offright){
- links.add(offleft);
- links.add(offright);
- }
- public void internalRepair(int count) throws ClassNotFoundException, IOException{
- Node temp,temp2;
- long nodeLocA = links.get(count);
- temp = tree.per.read(nodeLocA);
- goRightRepair(temp,count+1);
- for(int i = 0; i < links.size();i++){
- long nodeLocB = links.get(i);
- temp2 = tree.per.read(nodeLocB);
- if(temp2.minSize()){
- repair(i);
- i = 0;
- tree.per.write(temp2);
- }
- }
- }// end internalRepair
- //will repair upto the internal node
- public void goRightRepair(Node myNode,int count) throws ClassNotFoundException, IOException{
- if(myNode.isLeaf()){
- return;
- }//end if
- else{
- goRightRepair(tree.per.read(myNode.links.get(count)),count);
- Node temp;
- for(int i = 0; i < links.size();i++){
- long nodeLocA = links.get(i);
- temp = tree.per.read(nodeLocA);
- if(temp.minSize()){
- repair(i);
- i = 0;
- tree.per.write(temp);
- }
- }
- }
- }
- public void repair(int count) throws ClassNotFoundException, IOException{
- //write node back to file
- Node temp = new Node();
- Node temp2 = new Node();
- long nodeLocA = links.get(count -1);
- long nodeLocB = links.get(count +1);
- temp = tree.per.read(nodeLocA);
- temp2 = tree.per.read(nodeLocB);
- if(count != 0 && temp.keys.size() > middle ){
- rotateLeft(count);
- tree.per.write(temp);
- }
- else if(temp2.keys.size() > middle){
- rotateRight(count);
- tree.per.write(temp2);
- }
- else{
- merge(count);
- }
- }// end steal
- // need to get the link before i remove the key---error
- private void rotateLeft(int count) throws ClassNotFoundException, IOException{
- String parentKey;
- String replaceKey;
- Node temp;
- Node temp2;
- long nodeLocA = links.get(count -1);
- long nodeLocB = links.get(count);
- int apple =tree.per.read(nodeLocA).keys.size()-1;
- //get the link to the deficient right node
- temp2 = tree.per.read(nodeLocA);
- temp = tree.per.read(nodeLocB);
- // the parent key
- parentKey = keys.remove(count -1 );
- // parent key is placed in deficient right node brining it to minimum
- temp.keys.add(0,parentKey);
- // get the key from the over full left node
- replaceKey = temp2.keys.remove(apple);
- //put the new key in the proper spot.
- keys.add(count -1,replaceKey);
- //write node back to file
- tree.per.write(temp);
- tree.per.write(temp2);
- }
- private void rotateRight(int count) throws ClassNotFoundException, IOException{
- String parentKey;
- String replaceKey;
- long nodeLocA = links.get(count);
- long nodeLocB = links.get(count+1);
- Node temp = tree.per.read(nodeLocA);
- Node temp2 = tree.per.read(nodeLocB);
- //the parent key
- parentKey = keys.remove(count);
- //parent key is placed in deficient left node brining it to minimum
- temp.keys.add(parentKey);
- //get the key from the over full right node
- replaceKey = temp2.keys.remove(0);
- //put the new key in the proper spot
- keys.add(count,replaceKey);
- //write node back to file
- tree.per.write(temp);
- tree.per.write(temp2);
- }
- private void merge(int count) throws ClassNotFoundException, IOException{
- String parentKey;
- Node temp,temp2;
- long nodeLocA = links.get(count+1);
- long nodeLocB = links.get(count);
- temp = tree.per.read(nodeLocA);
- temp2 = tree.per.read(nodeLocB);
- //get the parentKey
- parentKey = keys.remove(count);
- //put parentKey into right link
- temp.keys.add(0,parentKey);
- // put left values into right values
- for(String s: temp2.keys) {
- temp.keys.add(0,s);
- }// end for
- //left links go into rights links
- for(long Link: temp2.links){
- temp.links.add(0,Link);
- }// end for
- links.remove(count);
- tree.per.write(temp);
- }// end merge
- public String predacessor(int count) throws ClassNotFoundException, IOException{
- long nodeLocA = links.get(count);
- Node temp = tree.per.read(nodeLocA);
- return goRight(temp,count+1);
- }
- public String goRight(Node myNode,int count) throws ClassNotFoundException, IOException{
- String toReturn;
- if(myNode.isLeaf()){
- toReturn = myNode.keys.remove(myNode.keys.size()-1);
- }//end if
- else{
- toReturn = goRight(tree.per.read(myNode.links.get(count)),count);
- }
- return toReturn;
- }
- public boolean minSize(){
- boolean result;
- if(keys.size() < MAXKEYS/2){
- result = true;
- }
- else{
- result = false;
- }
- return result;
- }// end minSize
- public void setStartIndex(long startIndex){
- this.startIndex = startIndex;
- }
- public long getStartIndex(){
- return startIndex;
- }
- public ArrayList<Node> getNode(){
- return temp;
- }
- }//end node
- public class Persistance implements Serializable {
- .....
- public void test(Node node) throws IOException{
- ByteArrayOutputStream b2= new ByteArrayOutputStream();
- ObjectOutput out2 = new ObjectOutputStream(b2);
- out2.writeObject(node);
- out2.close();
- byte[] array2 = b.toByteArray();
- ByteArrayInputStream in2 = new ByteArrayInputStream(array2);
- ObjectInputStream OIS2 = new ObjectInputStream(in2);
- Node temp = (Node) OIS2.readObject();
- OIS2.close();
- }
- .....
- }
- ByteArrayOutputStream b2= new ByteArrayOutputStream();
- ObjectOutput out2 = new ObjectOutputStream(b2);
- out2.writeObject(node);
- out2.close();
- byte[] array2 = b2.toByteArray();
- int length = array2.length;
- raf.writeInt(length);
- raf.write(array2);
- int length = raf.readInt();
- byte inArray[] = new byte[length];
- raf.read(inArray,0,length);
- ByteArrayInputStream in2 = new ByteArrayInputStream(inArray);
- ObjectInputStream OIS2 = new ObjectInputStream(in2);
- Node temp = (Node) OIS2.readObject();
- OIS2.close();
- import java.io.RandomAccessFile;
- import java.io.IOException;
- import java.io.Serializable;
- /**
- * John
- * Fall 2012
- */
- public class FLRAF extends RandomAccessFile implements Serializable {
- private int blockSize;
- public FLRAF(int blockSize, String file) throws IOException {
- super(file, "rw");
- this.blockSize = blockSize;
- }
- public byte[] read(int blockNumber) throws IOException {
- seek(blockNumber*blockSize);
- byte[] b = new byte[blockSize];
- read(b);
- return b;
- }
- public void write(byte[] b, int blockNumber) throws IOException {
- seek(blockNumber*blockSize);
- write(b);
- return;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement