001package algs62; // section 6.2 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac BTree.java 005 * Execution: java BTree 006 * 007 * B-tree. 008 * 009 * Limitations 010 * ----------- 011 * - Assumes M is even and M >= 4 012 * - should b be an array of children or list (it would help with 013 * casting to make it a list) 014 * 015 *************************************************************************/ 016 017@SuppressWarnings({"rawtypes","unchecked"}) 018public class XBTreeWithCasts<K extends Comparable<? super K>, V> { 019 private static final int M = 4; // max children per B-tree node = M-1 020 021 private Node root; // root of the B-tree 022 private int HT; // height of the B-tree 023 private int N; // number of key-value pairs in the B-tree 024 025 // helper B-tree node data type 026 private static final class Node { 027 public int m; // number of children 028 public final Entry[] children = new Entry[M]; // the array of children 029 public Node(int k) { m = k; } // create a node with k children 030 } 031 032 // internal nodes: only use key and next 033 // external nodes: only use key and value 034 private static class Entry { 035 Comparable key; 036 Object value; 037 Node next; // helper field to iterate over array entries 038 public Entry(Comparable key, Object value, Node next) { 039 this.key = key; 040 this.value = value; 041 this.next = next; 042 } 043 } 044 045 // constructor 046 public XBTreeWithCasts() { root = new Node(0); } 047 048 // return number of key-value pairs in the B-tree 049 public int size() { return N; } 050 051 // return height of B-tree 052 public int height() { return HT; } 053 054 055 // search for given key, return associated value; return null if no such key 056 public V get(K key) { return search(root, key, HT); } 057 private V search(Node x, K key, int ht) { 058 Entry[] children = x.children; 059 060 // external node 061 if (ht == 0) { 062 for (int j = 0; j < x.m; j++) { 063 if (eq(key, children[j].key)) return (V) children[j].value; 064 } 065 } 066 067 // internal node 068 else { 069 for (int j = 0; j < x.m; j++) { 070 if (j+1 == x.m || less(key, children[j+1].key)) 071 return search(children[j].next, key, ht-1); 072 } 073 } 074 return null; 075 } 076 077 078 // insert key-value pair 079 // add code to check for duplicate keys 080 public void put(K key, V value) { 081 Node u = insert(root, key, value, HT); 082 N++; 083 if (u == null) return; 084 085 // need to split root 086 Node t = new Node(2); 087 t.children[0] = new Entry(root.children[0].key, null, root); 088 t.children[1] = new Entry(u.children[0].key, null, u); 089 root = t; 090 HT++; 091 } 092 093 094 private Node insert(Node h, K key, V value, int ht) { 095 int j; 096 Entry t = new Entry(key, value, null); 097 098 // external node 099 if (ht == 0) { 100 for (j = 0; j < h.m; j++) { 101 if (less(key, h.children[j].key)) break; 102 } 103 } 104 105 // internal node 106 else { 107 for (j = 0; j < h.m; j++) { 108 if ((j+1 == h.m) || less(key, h.children[j+1].key)) { 109 Node u = insert(h.children[j++].next, key, value, ht-1); 110 if (u == null) return null; 111 t.key = u.children[0].key; 112 t.next = u; 113 break; 114 } 115 } 116 } 117 118 for (int i = h.m; i > j; i--) h.children[i] = h.children[i-1]; 119 h.children[j] = t; 120 h.m++; 121 if (h.m < M) return null; 122 else return split(h); 123 } 124 125 // split node in half 126 private Node split(Node h) { 127 Node t = new Node(M/2); 128 h.m = M/2; 129 for (int j = 0; j < M/2; j++) 130 t.children[j] = h.children[M/2+j]; 131 return t; 132 } 133 134 // for debugging 135 public String toString() { 136 return toString(root, HT, "") + "\n"; 137 } 138 private String toString(Node h, int ht, String indent) { 139 String s = ""; 140 Entry[] children = h.children; 141 142 if (ht == 0) { 143 for (int j = 0; j < h.m; j++) { 144 s += indent + children[j].key + " " + children[j].value + "\n"; 145 } 146 } 147 else { 148 for (int j = 0; j < h.m; j++) { 149 if (j > 0) s += indent + "(" + children[j].key + ")\n"; 150 s += toString(children[j].next, ht-1, indent + " "); 151 } 152 } 153 return s; 154 } 155 156 157 // comparison functions - make Comparable instead of K to avoid casts 158 private boolean less(Comparable k1, Comparable k2) { 159 return k1.compareTo(k2) < 0; 160 } 161 162 private boolean eq(Comparable k1, Comparable k2) { 163 return k1.compareTo(k2) == 0; 164 } 165 166 167 /* *********************************************************************** 168 * test client 169 *************************************************************************/ 170 public static void main(String[] args) { 171 XBTreeWithCasts<String, String> st = new XBTreeWithCasts<>(); 172 173 // st.put("www.cs.princeton.edu", "128.112.136.12"); 174 st.put("www.cs.princeton.edu", "128.112.136.11"); 175 st.put("www.princeton.edu", "128.112.128.15"); 176 st.put("www.yale.edu", "130.132.143.21"); 177 st.put("www.simpsons.com", "209.052.165.60"); 178 st.put("www.apple.com", "17.112.152.32"); 179 st.put("www.amazon.com", "207.171.182.16"); 180 st.put("www.ebay.com", "66.135.192.87"); 181 st.put("www.cnn.com", "64.236.16.20"); 182 st.put("www.google.com", "216.239.41.99"); 183 st.put("www.nytimes.com", "199.239.136.200"); 184 st.put("www.microsoft.com", "207.126.99.140"); 185 st.put("www.dell.com", "143.166.224.230"); 186 st.put("www.slashdot.org", "66.35.250.151"); 187 st.put("www.espn.com", "199.181.135.201"); 188 st.put("www.weather.com", "63.111.66.11"); 189 st.put("www.yahoo.com", "216.109.118.65"); 190 191 192 StdOut.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu")); 193 StdOut.println("hardvardsucks.com: " + st.get("www.harvardsucks.com")); 194 StdOut.println("simpsons.com: " + st.get("www.simpsons.com")); 195 StdOut.println("apple.com: " + st.get("www.apple.com")); 196 StdOut.println("ebay.com: " + st.get("www.ebay.com")); 197 StdOut.println("dell.com: " + st.get("www.dell.com")); 198 StdOut.println(); 199 200 StdOut.println("size: " + st.size()); 201 StdOut.println("height: " + st.height()); 202 StdOut.println(st); 203 StdOut.println(); 204 } 205 206}