Changeset 900

Timestamp:

11/07/07 11:50:09 (2 years ago)

Author:

vasi

Message:

worky....

Location:

cs420

Files:

• .classpath (modified) (1 diff)
• asst5/asst5420.java (modified) (2 diffs)

cs420/.classpath

@@ -2 +2 @@
 <classpath>
         <classpathentry kind="src" path="asst1"/>
+        <classpathentry kind="src" path="asst5"/>
         <classpathentry kind="src" path="asst2"/>
         <classpathentry kind="src" path="asst3"/>

cs420/asst5/asst5420.java

@@ -1 @@
-/* CS 420 assignment 4: seek in a file
+/* CS 420 assignment 5: search in a B-tree
  * David Vasilevsky, ID 110126642
  */
@@ -5 +5 @@
 import java.io.*;
 
-public class asst4420 {
-        private static final String COURSE = "/home/course/cs420";
-        private static final int BLOCKSIZE = 81;
-        
+public class asst5420 {
         // Find a file given a relative path
         private static File findFile(String rel) {
                 File f = new File(rel); // prefer using the relative path
-                if (!f.exists())
+                if (!f.exists()) {
+                        final String COURSE = "/home/course/cs420";
                         f = new File(COURSE, rel); // fall back to the course dir
+                }
                 return f;
         }
         
-        
-        // Simple struct-like class to represent a record of the file
-        public static class Record {
-                public String name, address, phone;
+        public static class BTree {
+                public static final int RECORDSIZE = 80;
+                public static final int ORDER = 19;
+                public static final int DATASIZE = (ORDER - 1) * RECORDSIZE;
+                public static final int NODESIZE = DATASIZE + ORDER * 4;
+                public static final String NULLRECORDTOKEN = "~~~~~~~";
+                public static final int NULLPOINTER = -1;
                 
-                // Read the next record in the input
-                public Record(DataInput di) throws IOException {
-                        byte[] data = new byte[81];
-                        di.readFully(data);
-                        String ds = new String(data);
-                        name = ds.substring(0, 40).trim();
-                        address = ds.substring(40, 68).trim();
-                        phone = ds.substring(68, 80).trim();
+                private RandomAccessFile file;
+                private int baseNode;
+                
+                private class Node {
+                        private byte[] data = new byte[NODESIZE];
+                        
+                        // Re-use this node for the given node/block number
+                        private void setNode(int blockno) throws IOException {
+                                file.seek(4 + blockno * NODESIZE);
+                                file.readFully(data);
+                        }
+                        
+                        public Node(int blockno) throws IOException {
+                                setNode(blockno);
+                        }
+                        
+                        public Record getRecord(int idx) {
+                                return new Record(data, idx * RECORDSIZE);
+                        }
+                        
+                        public int getPointer(int idx) {
+                                return bytechars.byte2int(data, DATASIZE + idx * 4);
+                        }
                 }
                 
-                public String toString() {
-                        return "name: '" + name + "', address: '" + address
-                                        + "', phone: '" + phone + "'\n";
-                }               
+                public class Record {
+                        private byte[] data;
+                        private int offset;
+                        
+                        public Record(byte[] d, int off) {
+                                data = d;
+                                offset = off;
+                        }
+                        
+                        public String getName() {
+                                return bytechars.byte2string(data, offset, 40);
+                        }
+                        
+                        public String getAddress() {
+                                return bytechars.byte2string(data, offset + 40, 33);
+                        }
+                        
+                        public String getPhone() {
+                                return bytechars.byte2string(data, offset + 73, 7);
+                        }
+                        
+                        public boolean isNull() {
+                                return getPhone().equals(NULLRECORDTOKEN);
+                        }
+                        
+                        public String toString() {
+                                return "name: '" + getName() + "', address: '" + getAddress()
+                                                + "', phone: '" + getPhone() + "'\n";
+                        }
+                }
+                
+                public BTree(String relPath) throws IOException {
+                        file = new RandomAccessFile(findFile(relPath), "r");
+                        baseNode = file.readInt();
+                }
+                
+                public Node root() throws IOException {
+                        return new Node(baseNode);
+                }
+                
+                
+                // Test tree traversal
+                public static class Functor {
+                        public void run(Record r) { }
+                }
+                
+                public void traverse(Functor f, Node n) throws IOException {
+                        for (int i = 0; i < ORDER; ++i) {
+                                int ptr = n.getPointer(i);
+                                if (ptr != NULLPOINTER)
+                                        traverse(f, new Node(ptr));
+                                if (i != ORDER - 1) {
+                                        Record r = n.getRecord(i);
+                                        if (!r.isNull())
+                                                f.run(r);
+                                }
+                        }
+                }
+                
+                public void traverse(Functor f) throws IOException {
+                        traverse(f, root());
+                }
         }
         
         public static void main(String[] args) {
                 try {
-                        int[] offsets = { 5, 4, 6, 3, 7, 2, 8, 1, 9, 0 };
-                        
-                        RandomAccessFile in = new RandomAccessFile(
-                                findFile("data/tbook"), "r");
-                        for (int i = 0; i < offsets.length; ++i) {
-                                in.seek(offsets[i] * BLOCKSIZE);
-                                Record r = new Record(in);
-                                System.out.print(r);
-                        }
-                        
+                        BTree bt = new BTree("data/btree");
+                        bt.traverse(new BTree.Functor() {
+                                public void run(BTree.Record r) {
+                                        System.out.print(r);
+                                }
+                        });
+                        System.out.println("done!");
                 } catch (IOException e) {
                         e.printStackTrace();