/****************************************************************************** * Compilation: javac BTree.java * Execution: java BTree * Dependencies: StdOut.java * * B-tree. * * Limitations * ----------- * - Assumes M is even and M >= 4 * - should b be an array of children or list (it would help with * casting to make it a list) * ******************************************************************************/ /** * The {@code BTree} class represents an ordered symbol table of generic * key-value pairs. * It supports the put, get, contains, * size, and is-empty methods. * A symbol table implements the associative array abstraction: * when associating a value with a key that is already in the symbol table, * the convention is to replace the old value with the new value. * Unlike {@link java.util.Map}, this class uses the convention that * values cannot be {@code null}—setting the * value associated with a key to {@code null} is equivalent to deleting the key * from the symbol table. *

* This implementation uses a B-tree. It requires that * the key type implements the {@code Comparable} interface and calls the * {@code compareTo()} and method to compare two keys. It does not call either * {@code equals()} or {@code hashCode()}. * The get, put, and contains operations * each make logm(n) probes in the worst case, * where n is the number of key-value pairs * and m is the branching factor. * The size, and is-empty operations take constant time. * Construction takes constant time. *

* For additional documentation, see * Section 6.2 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class BTree, Value> { // max children per B-tree node = M-1 // (must be even and greater than 2) private static final int M = 4; private Node root; // root of the B-tree private int height; // height of the B-tree private int n; // number of key-value pairs in the B-tree // helper B-tree node data type private static final class Node { private int m; // number of children private Entry[] children = new Entry[M]; // the array of children // create a node with k children private Node(int k) { m = k; } } // internal nodes: only use key and next // external nodes: only use key and value private static class Entry { private Comparable key; private Object val; private Node next; // helper field to iterate over array entries public Entry(Comparable key, Object val, Node next) { this.key = key; this.val = val; this.next = next; } } /** * Initializes an empty B-tree. */ public BTree() { root = new Node(0); } /** * Returns true if this symbol table is empty. * @return {@code true} if this symbol table is empty; {@code false} otherwise */ public boolean isEmpty() { return size() == 0; } /** * Returns the number of key-value pairs in this symbol table. * @return the number of key-value pairs in this symbol table */ public int size() { return n; } /** * Returns the height of this B-tree (for debugging). * * @return the height of this B-tree */ public int height() { return height; } /** * Returns the value associated with the given key. * * @param key the key * @return the value associated with the given key if the key is in the symbol table * and {@code null} if the key is not in the symbol table * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); return search(root, key, height); } private Value search(Node x, Key key, int ht) { Entry[] children = x.children; // external node if (ht == 0) { for (int j = 0; j < x.m; j++) { if (eq(key, children[j].key)) return (Value) children[j].val; } } // internal node else { for (int j = 0; j < x.m; j++) { if (j+1 == x.m || less(key, children[j+1].key)) return search(children[j].next, key, ht-1); } } return null; } /** * Inserts the key-value pair into the symbol table, overwriting the old value * with the new value if the key is already in the symbol table. * If the value is {@code null}, this effectively deletes the key from the symbol table. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("argument key to put() is null"); Node u = insert(root, key, val, height); n++; if (u == null) return; // need to split root Node t = new Node(2); t.children[0] = new Entry(root.children[0].key, null, root); t.children[1] = new Entry(u.children[0].key, null, u); root = t; height++; } private Node insert(Node h, Key key, Value val, int ht) { int j; Entry t = new Entry(key, val, null); // external node if (ht == 0) { for (j = 0; j < h.m; j++) { if (less(key, h.children[j].key)) break; } } // internal node else { for (j = 0; j < h.m; j++) { if ((j+1 == h.m) || less(key, h.children[j+1].key)) { Node u = insert(h.children[j++].next, key, val, ht-1); if (u == null) return null; t.key = u.children[0].key; t.val = null; t.next = u; break; } } } for (int i = h.m; i > j; i--) h.children[i] = h.children[i-1]; h.children[j] = t; h.m++; if (h.m < M) return null; else return split(h); } // split node in half private Node split(Node h) { Node t = new Node(M/2); h.m = M/2; for (int j = 0; j < M/2; j++) t.children[j] = h.children[M/2+j]; return t; } /** * Returns a string representation of this B-tree (for debugging). * * @return a string representation of this B-tree. */ public String toString() { return toString(root, height, "") + "\n"; } private String toString(Node h, int ht, String indent) { StringBuilder s = new StringBuilder(); Entry[] children = h.children; if (ht == 0) { for (int j = 0; j < h.m; j++) { s.append(indent + children[j].key + " " + children[j].val + "\n"); } } else { for (int j = 0; j < h.m; j++) { if (j > 0) s.append(indent + "(" + children[j].key + ")\n"); s.append(toString(children[j].next, ht-1, indent + " ")); } } return s.toString(); } // comparison functions - make Comparable instead of Key to avoid casts private boolean less(Comparable k1, Comparable k2) { return k1.compareTo(k2) < 0; } private boolean eq(Comparable k1, Comparable k2) { return k1.compareTo(k2) == 0; } /** * Unit tests the {@code BTree} data type. * * @param args the command-line arguments */ public static void main(String[] args) { BTree st = new BTree(); st.put("www.cs.princeton.edu", "128.112.136.12"); st.put("www.cs.princeton.edu", "128.112.136.11"); st.put("www.princeton.edu", "128.112.128.15"); st.put("www.yale.edu", "130.132.143.21"); st.put("www.simpsons.com", "209.052.165.60"); st.put("www.apple.com", "17.112.152.32"); st.put("www.amazon.com", "207.171.182.16"); st.put("www.ebay.com", "66.135.192.87"); st.put("www.cnn.com", "64.236.16.20"); st.put("www.google.com", "216.239.41.99"); st.put("www.nytimes.com", "199.239.136.200"); st.put("www.microsoft.com", "207.126.99.140"); st.put("www.dell.com", "143.166.224.230"); st.put("www.slashdot.org", "66.35.250.151"); st.put("www.espn.com", "199.181.135.201"); st.put("www.weather.com", "63.111.66.11"); st.put("www.yahoo.com", "216.109.118.65"); StdOut.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu")); StdOut.println("hardvardsucks.com: " + st.get("www.harvardsucks.com")); StdOut.println("simpsons.com: " + st.get("www.simpsons.com")); StdOut.println("apple.com: " + st.get("www.apple.com")); StdOut.println("ebay.com: " + st.get("www.ebay.com")); StdOut.println("dell.com: " + st.get("www.dell.com")); StdOut.println(); StdOut.println("size: " + st.size()); StdOut.println("height: " + st.height()); StdOut.println(st); StdOut.println(); } }