diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
new file mode 100644
index 0000000..9ec50bf
--- /dev/null
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/IPatriciaTrie.java
@@ -0,0 +1,20 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import java.util.Iterator;
+
+public interface IPatriciaTrie {
+	public Rib put(Prefix p, Rib r);
+	
+	public Rib lookup(Prefix p);
+	
+	public Rib match(Prefix p);
+	
+	public boolean remove(Prefix p, Rib r);
+	
+	public Iterator<Entry> iterator();
+	
+	interface Entry {
+		public Prefix getPrefix();
+		public Rib getRib();
+	}
+}
diff --git a/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
new file mode 100644
index 0000000..514758f
--- /dev/null
+++ b/src/main/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrie.java
@@ -0,0 +1,464 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public class PatriciaTrie implements IPatriciaTrie{
+	private final byte maskBits[] = {(byte)0x00, (byte)0x80, (byte)0xc0, (byte)0xe0, (byte)0xf0, 
+												 (byte)0xf8, (byte)0xfc, (byte)0xfe, (byte)0xff};
+	
+	private int maxPrefixLength;
+	
+	private Node top;
+
+	public PatriciaTrie(int maxPrefixLength) {
+		this.maxPrefixLength = maxPrefixLength;
+	}
+
+	public synchronized Rib put(Prefix p, Rib r) {
+		if (p.getPrefixLength() > maxPrefixLength) {
+			throw new IllegalArgumentException(String.format(
+					"Prefix length %d is greater than max prefix length %d", 
+					p.getPrefixLength(), maxPrefixLength));
+		}
+		
+		if (p == null || r == null) {
+			throw new NullPointerException();
+		}
+		
+		Node node = top;
+		Node match = null;
+		
+		while (node != null
+				&& node.prefix.getPrefixLength() <= p.getPrefixLength()
+				&& key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+		    if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+		    	/*
+		    	 * Prefix is already in tree. This may be an aggregate node, in which case
+		    	 * we are inserting a new prefix, or it could be an actual node, in which 
+		    	 * case we are inserting a new nexthop for the prefix and should return
+		    	 * the old nexthop.
+		    	 */
+		    	Rib oldRib = node.rib;
+		    	node.rib = r;
+		    	return oldRib;
+			}
+
+			match = node;
+			
+			if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+				node = node.right;
+			} else {
+				node = node.left;
+			}
+		}
+
+		Node add = null;
+		
+		if (node == null) {
+			add = new Node(p, r);
+			
+			if (match != null) {
+				node_link(match, add);
+			} else {
+				top = add;
+			}
+		} else {
+			add = node_common(node, p.getAddress(), p.getPrefixLength());
+			if (add == null) {
+				//I think this is -ENOMEM?
+				//return null;
+			}				
+			
+			if (match != null) {
+				node_link(match, add);
+			} else {
+				top = add;
+			}
+			node_link(add, node);
+			
+			if (add.prefix.getPrefixLength() != p.getPrefixLength()) {
+				match = add;
+				
+				add = new Node(p, r);
+				node_link(match, add);
+			}
+			else {
+				add.rib = r;
+			}
+		}
+		
+		//If we added a new Node, there was no previous mapping
+		return null;
+		//return addReference(add);
+	}
+	
+	/*exact match*/
+	public synchronized Rib lookup(Prefix p) {
+		//TODO
+		
+		if (p.getPrefixLength() > maxPrefixLength) {
+			return null;
+		}
+		
+		/*
+		Node node = top;
+		
+		while (node != null
+				&& node.prefix.getPrefixLength() <= p.getPrefixLength()
+				&& key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+			if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+				//return addReference(node);
+				return node.rib;
+			}
+			
+			if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+				node = node.right;
+			} else {
+				node = node.left;
+			}
+		}
+		*/
+		
+		Node node = findNode(p);
+		
+		return node == null ? null : node.rib;
+	}
+	
+	/*closest containing prefix*/
+	public synchronized Rib match(Prefix p) {
+		//TODO
+		return null;
+	}
+	
+	public synchronized boolean remove(Prefix p, Rib r) {
+		Node child;
+		Node parent;
+		
+		if (p == null || r == null) {
+			return false;
+		}
+		
+		Node node = findNode(p);
+		
+		if (node == null || node.rib == null || !node.rib.equals(r)) {
+			//Given <prefix, nexthop> mapping is not in the tree
+			return false;
+		}
+		
+		if (node.left != null && node.right != null) {
+			//Remove the Rib entry and leave this node as an aggregate node
+			//In the future, maybe we should re-evaluate what the aggregate prefix should be?
+			//It shouldn't necessarily stay the same.
+			//More complicated if the above prefix is also aggregate.
+			node.rib = null;
+			return true;
+		}
+		
+		if (node.left != null) {
+			child = node.left;
+		} else {
+			child = node.right;
+		}
+		
+		parent = node.parent;
+		
+		if (child != null) {
+			child.parent = parent;
+		}
+		
+		if (parent != null) {
+			if (parent.left == node) {
+				parent.left = child;
+			} else {
+				parent.right = child;
+			}
+		} else {
+			top = child;
+		}
+		
+		/*
+		 * TODO not sure what to do here. I think this is lazily deleting aggregate nodes,
+		 * notice that it used to do nothing if it detected both children were not null earlier.
+		 * But here, what we really should do is reevaluate the aggregate prefix of the parent
+		 * node (if it is indeed an aggregate). Because at the moment, no aggregate node will ever
+		 * be removed. BUT, I don't actually think this presents a correctness problem, at
+		 * least from an external point of view.
+		 */
+		//if (parent != null && parent.refCount == 0) {
+			//node_remove(parent);
+		//}
+		
+		return true;
+	}
+	
+	public Iterator<Entry> iterator() {
+		return new PatriciaTrieIterator(top);
+	}
+	
+	private Node findNode(Prefix p) {
+		Node node = top;
+		
+		while (node != null
+				&& node.prefix.getPrefixLength() <= p.getPrefixLength()
+				&& key_match(node.prefix.getAddress(), node.prefix.getPrefixLength(), p.getAddress(), p.getPrefixLength()) == true) {
+			if (node.prefix.getPrefixLength() == p.getPrefixLength()) {
+				//return addReference(node);
+				return node;
+			}
+			
+			if (bit_check(p.getAddress(), node.prefix.getPrefixLength()) == true) {
+				node = node.right;
+			} else {
+				node = node.left;
+			}
+		}
+		
+		return null;
+	}
+	
+	/*
+	 * Receives a 1-based bit index
+	 * Returns a 1-based byte index
+	 * eg. (0 => 1), 1 => 1, 8 => 1, 9 => 2, 17 => 3
+	 */
+	private int getByteContainingBit(int bitNumber) {
+		return Math.max((bitNumber + 7) / 8, 1);
+	}
+	
+	private boolean key_match(byte [] key1, int key1_len, byte [] key2, int key2_len) {
+		//int offset;
+		//int shift;
+		
+		if (key1_len > key2_len) {
+			return false;
+		}
+		
+		int offset = (Math.min(key1_len, key2_len)) / 8;
+		int shift = (Math.min(key1_len, key2_len)) % 8;
+		
+		if (shift != 0) {
+			if ((maskBits[shift] & (key1[offset] ^ key2[offset])) != 0) {
+				return false;
+			}
+		}
+		
+		while (offset != 0) {
+			offset--;
+			if (key1[offset] != key2[offset]) {
+				return false;
+			}
+		}
+		return true;
+	}
+	
+	private boolean bit_check(byte [] key, int key_bits) {
+		int offset = key_bits / 8;
+		int shift = 7 - (key_bits % 8);
+		int bit = key[offset] & 0xff;
+
+		bit >>= shift;
+		
+		if ((bit & 1) == 1) {
+			return true;
+		} else {
+			return false;
+		}
+	}
+	
+	private void node_link(Node node, Node add) {
+		boolean bit = bit_check(add.prefix.getAddress(), node.prefix.getPrefixLength());
+		
+		if (bit == true) {
+			node.right = add;
+		} else {
+			node.left = add;
+		}
+		add.parent = node;
+	}
+	
+    private Node node_common(Node node, byte [] key, int key_bits) {
+		int i;
+		int limit = Math.min(node.prefix.getPrefixLength(), key_bits) / 8;
+
+		for (i = 0; i < limit; i++) {
+			if (node.prefix.getAddress()[i] != key[i]) {
+				break;
+			}
+		}
+		
+		int common_len = i * 8;
+		int boundary = 0;
+
+		if (common_len != key_bits) {
+			byte diff = (byte)(node.prefix.getAddress()[i] ^ key[i]);
+			byte mask = (byte)0x80;
+			int shift_mask = 0;
+			
+			while (common_len < key_bits && ((mask & diff) == 0)) {
+				boundary = 1;
+
+				shift_mask = (mask & 0xff);
+				shift_mask >>= 1;
+				mask = (byte)shift_mask;
+
+				common_len++;
+			}
+		}
+		
+		//Node add = new Node(null, common_len, maxKeyOctets);
+		//if (add == null)
+			//Another -ENOMEM;
+			//return null;
+		
+		//Creating a new Prefix with a prefix length of common_len
+		//Bits are copied from node's up until the common_len'th bit
+		//Rib is null, because this is an aggregate prefix - it's not
+		//actually been added to the trie.
+		
+		byte[] newPrefix = new byte[getByteContainingBit(maxPrefixLength)];
+		
+		int j;
+		for (j = 0; j < i; j++)
+			newPrefix[j] = node.prefix.getAddress()[j];
+
+		if (boundary != 0)
+			newPrefix[j] = (byte)(node.prefix.getAddress()[j] & maskBits[common_len % 8]);
+		
+		return new Node(new Prefix(newPrefix, common_len), null);
+		//return add;
+	}
+	
+	private class Node {
+		public Node parent = null;
+		public Node left = null;
+		public Node right = null;
+		
+		public Prefix prefix;
+		public Rib rib;
+		
+		public Node(Prefix p, Rib r) {
+			this.prefix = p;
+			this.rib = r;
+		}
+		
+		public Entry getEntry() {
+			return new PatriciaTrieEntry(prefix, rib);
+		}
+	}
+	
+	private class PatriciaTrieEntry implements Entry {
+		private Prefix prefix;
+		private Rib rib;
+		
+		public PatriciaTrieEntry(Prefix prefix, Rib rib) {
+			this.prefix = prefix;
+			this.rib = rib;
+		}
+		
+		@Override
+		public Prefix getPrefix() {
+			return prefix;
+		}
+		
+		@Override
+		public Rib getRib() {
+			return rib;
+		}
+	}
+	
+	private class PatriciaTrieIterator implements Iterator<Entry> {
+		
+		private Node current;
+		private boolean started = false;
+		
+		public PatriciaTrieIterator(Node start) {
+			current = start;
+			
+			//If the start is an aggregate node fast forward to find the next valid node
+			if (current != null && current.rib == null) {
+				current = findNext(current);
+			}
+		}
+
+		@Override
+		public boolean hasNext() {
+			if (current == null) {
+				return false;
+			}
+			
+			if (!started) {
+				return true;
+			}
+			
+			return findNext(current) != null;
+		}
+
+		@Override
+		public Entry next() {
+			if (current == null) {
+				throw new NoSuchElementException();
+			}
+			
+			if (!started) {
+				started = true;
+				return current.getEntry();
+			}
+			
+			current = findNext(current);
+			if (current == null) {
+				throw new NoSuchElementException();
+			}
+			
+			return current.getEntry();
+		}
+
+		@Override
+		public void remove() {
+			// TODO This could be implemented, if it were needed
+			throw new NoSuchElementException();
+		}
+		
+		private Node findNext(Node node) {
+			Node next = null;
+			
+			if (node.left != null) {
+				next = node.left;
+				//addReference(next);
+				//delReference(node);
+				//return next;
+			}
+			else if (node.right != null) {
+				next = node.right;
+				//addReference(next);
+				//delReference(node);
+				//return next;
+			}
+			else {
+				//Node start = node;
+				while (node.parent != null) {
+					if (node.parent.left == node && node.parent.right != null) {
+						next = node.parent.right;
+						//addReference(next);
+						//delReference(start);
+						//return next;
+						break;
+					}
+					node = node.parent;
+				}
+			}
+			
+			if (next == null) {
+				return null;
+			}
+			
+			//If the node doesn't have a rib, it's not an actual node, it's an artifically
+			//inserted aggregate node. We don't want to return these to the user.
+			if (next.rib == null) {
+				return findNext(next);
+			}
+			
+			return next;
+		}
+	}
+}
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
new file mode 100644
index 0000000..d462d3e
--- /dev/null
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PatriciaTrieTest.java
@@ -0,0 +1,189 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Ignore;
+import org.junit.Test;
+
+public class PatriciaTrieTest {
+
+	IPatriciaTrie ptrie;
+	Prefix[] prefixes;
+	Map<Prefix, Rib> mappings;
+	
+	@Before
+	public void setUp() throws Exception {
+		ptrie = new PatriciaTrie(32);
+		mappings = new HashMap<Prefix, Rib>();
+		
+		prefixes = new Prefix[] {
+			new Prefix("192.168.10.0", 24),
+			new Prefix("192.168.8.0", 23),
+			new Prefix("192.168.8.0", 22),
+			new Prefix("192.0.0.0", 7),
+			new Prefix("192.168.11.0", 24),
+			new Prefix("10.0.23.128", 25),
+			new Prefix("206.17.144.0", 20),
+			new Prefix("9.17.0.0", 12),
+			new Prefix("192.168.0.0", 16)
+		};
+				
+		for (int i = 0; i < prefixes.length; i++) {
+			mappings.put(prefixes[i], new Rib("192.168.10.101", "192.168.20." + i, 32));
+			ptrie.put(prefixes[i], new Rib("192.168.10.101", "192.168.20." + i, 32));
+		}
+	}
+
+	@After
+	public void tearDown() throws Exception {
+	}
+
+	@Test
+	public void testPut() {
+		IPatriciaTrie ptrie = new PatriciaTrie(32);
+		
+		Prefix p1 = new Prefix("192.168.240.0", 20);
+		Rib r1 = new Rib("192.168.10.101", "192.168.60.2", 20);
+		Rib retval = ptrie.put(p1, r1);
+		assertNull(retval);
+		retval = ptrie.lookup(p1);
+		assertTrue(r1 == retval); //should be the same object
+		
+		Prefix p2 = new Prefix("192.160.0.0", 12);
+		Rib r2 = new Rib("192.168.10.101", "192.168.20.1", 12);
+		retval = ptrie.put(p2, r2);
+		assertNull(retval);
+		
+		Prefix p3 = new Prefix("192.168.208.0", 20);
+		Rib r3 = new Rib("192.168.10.101", "192.168.30.1", 20);
+		retval = ptrie.put(p3,  r3);
+		assertNull(retval);
+		
+		//Insert a new Rib entry over a previous one
+		Rib r3new = new Rib("192.168.10.101", "192.168.60.2", 20);
+		retval = ptrie.put(p3, r3new);
+		assertNotNull(retval);
+		assertTrue(retval.equals(r3));
+		assertTrue(retval == r3); //should be the same object
+		
+		//Now we have an aggregate node with prefix 192.168.192.0/18.
+		//We will insert a Rib at this prefix
+		Prefix p4 = new Prefix("192.168.192.0", 18);
+		Rib r4 = new Rib("192.168.10.101", "192.168.40.1", 18);
+		retval = ptrie.put(p4, r4);
+		assertNull(retval);
+		retval = ptrie.lookup(p4);
+		assertTrue(retval == r4); //should be the same object
+	}
+
+	@Test
+	public void testLookup() {
+		for (Map.Entry<Prefix, Rib> entry : mappings.entrySet()) {
+			Rib r = ptrie.lookup(entry.getKey());
+			assertTrue(entry.getValue().equals(r));
+		}
+		
+		//These are aggregate nodes in the tree. Shouldn't be returned by lookup
+		Prefix p1 = new Prefix("0.0.0.0", 0);
+		Rib retval = ptrie.lookup(p1);
+		assertNull(retval);
+		
+		//We'll put a Rib at an aggregate node and check if lookup returns correctly
+		Prefix p2 = new Prefix("192.0.0.0", 4);
+		Rib r2 = new Rib("192.168.10.101", "192.168.60.1", 4);
+		retval = ptrie.put(p2, r2);
+		assertNull(retval);
+		retval = ptrie.lookup(p2);
+		assertTrue(retval.equals(r2));
+	}
+
+	@Ignore
+	@Test
+	public void testMatch() {
+		fail("Not yet implemented");
+	}
+
+	@Test
+	public void testRemove() {
+		Prefix p1 = new Prefix("192.168.8.0", 23);
+		Rib retval = ptrie.lookup(p1);
+		assertNotNull(retval);
+		boolean success = ptrie.remove(p1, retval);
+		assertTrue(success);
+		
+		Prefix p2 = new Prefix("192.168.8.0", 22);
+		Prefix p3 = new Prefix("192.168.10.0", 24);
+		
+		//Test it does the right thing with null arguments
+		success = ptrie.remove(null, null);
+		assertFalse(success);
+		success = ptrie.remove(p2, null);
+		assertFalse(success);
+		
+		//Check other prefixes are still there
+		retval = ptrie.lookup(p2);
+		assertNotNull(retval);
+		retval = ptrie.lookup(p3);
+		assertNotNull(retval);
+		
+		Prefix p4 = new Prefix("9.17.0.0", 12);
+		retval = ptrie.lookup(p4);
+		assertNotNull(retval);
+		success = ptrie.remove(p4, retval);
+		assertTrue(success);
+		success = ptrie.remove(p4, retval);
+		assertFalse(success);
+		
+		//Check other prefixes are still there
+		retval = ptrie.lookup(p2);
+		assertNotNull(retval);
+		retval = ptrie.lookup(p3);
+		assertNotNull(retval);
+		
+		Prefix p5 = new Prefix("192.0.0.0", 7);
+		retval = ptrie.lookup(p5);
+		assertNotNull(retval);
+		success = ptrie.remove(p5, retval);
+		assertTrue(success);
+		
+		//Check other prefixes are still there
+		retval = ptrie.lookup(p2);
+		assertNotNull(retval);
+		retval = ptrie.lookup(p3);
+		assertNotNull(retval);
+		
+		
+	}
+
+	@Test(expected=java.util.NoSuchElementException.class)
+	public void testIterator() {		
+		int[] order = new int[] {7, 5, 3, 8, 2, 1, 0, 4, 6};
+		
+		Iterator<IPatriciaTrie.Entry> it = ptrie.iterator();
+		int i = 0;
+		assertTrue(it.hasNext());
+		while (it.hasNext()) {
+			IPatriciaTrie.Entry entry = it.next();
+			assertTrue(entry.getPrefix().equals(prefixes[order[i]]));
+			i++;
+		}
+		assertFalse(it.hasNext());
+		assertTrue(i == order.length);
+		
+		IPatriciaTrie pt = new PatriciaTrie(32);
+		Iterator<IPatriciaTrie.Entry> it2 = pt.iterator();
+		assertFalse(it2.hasNext());
+		it.next(); //throws NoSuchElementException
+	}
+
+}
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PrefixTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PrefixTest.java
new file mode 100644
index 0000000..01c5ea7
--- /dev/null
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PrefixTest.java
@@ -0,0 +1,66 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import static org.junit.Assert.*;
+
+import java.util.Arrays;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+public class PrefixTest {
+
+	@Before
+	public void setUp() throws Exception {
+	}
+
+	@After
+	public void tearDown() throws Exception {
+	}
+
+	@Test
+	public void testPrefixByteArray() {
+		byte[] b1 = new byte[] {(byte)0x8f, (byte)0xa0, (byte)0x00, (byte)0x00};
+		byte[] b2 = new byte[] {(byte)0x8f, (byte)0xa0, (byte)0xff, (byte)0xff};
+		byte[] b3 = new byte[] {(byte)0x8f, (byte)0xac, (byte)0x00, (byte)0x00};
+		byte[] b4 = new byte[] {(byte)0x8f, (byte)0xa0, (byte)0x00, (byte)0x00};
+		
+		Prefix p1 = new Prefix(b1, 12);
+		Prefix p2 = new Prefix(b2, 12);
+		Prefix p3 = new Prefix(b3, 12);
+		Prefix p4 = new Prefix(b4, 11);
+		
+		//Have different byte arrays, but should be equal after construction
+		assertTrue(p1.equals(p2));
+		assertTrue(p2.equals(p3));
+		
+		//Same byte array, but should be false
+		assertFalse(p1.equals(p4));
+		
+		assertTrue(Arrays.equals(p1.getAddress(), p3.getAddress()));
+		assertTrue(p1.toString().equals(p2.toString()));
+		assertTrue(Arrays.equals(p1.getAddress(), p4.getAddress()));
+		assertFalse(p1.toString().equals(p4.toString()));
+	}
+
+	@Test
+	public void testPrefixString() {
+		Prefix p1 = new Prefix("192.168.166.0", 24);
+		Prefix p2 = new Prefix("192.168.166.0", 23);
+		Prefix p3 = new Prefix("192.168.166.128", 24);
+		Prefix p4 = new Prefix("192.168.166.128", 25);
+		
+		assertFalse(p1.equals(p2));
+		assertTrue(Arrays.equals(p1.getAddress(), p2.getAddress()));
+		
+		assertTrue(p1.equals(p3));
+		assertTrue(Arrays.equals(p1.getAddress(), p2.getAddress()));
+		
+		assertFalse(p3.equals(p4));
+		assertFalse(Arrays.equals(p3.getAddress(), p4.getAddress()));
+		
+		assertTrue(p1.toString().equals(p3.toString()));
+		assertEquals(p1.hashCode(), p3.hashCode());
+	}
+
+}
diff --git a/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
new file mode 100644
index 0000000..1aa451c
--- /dev/null
+++ b/src/test/java/net/onrc/onos/ofcontroller/bgproute/PtreeTest.java
@@ -0,0 +1,227 @@
+package net.onrc.onos.ofcontroller.bgproute;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Ignore;
+import org.junit.Test;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import com.google.common.net.InetAddresses;
+
+public class PtreeTest {
+	
+	private Logger log = LoggerFactory.getLogger(PtreeTest.class);
+	
+	private Ptree ptree;
+	private PatriciaTrie ooptrie;
+	
+	private Map<String, byte[]> byteAddresses;
+
+	@Before
+	public void setUp() throws Exception {
+		ptree = new Ptree(32);
+		ooptrie = new PatriciaTrie(32);
+			
+		String[] strPrefixes = {
+			"192.168.10.0/24",
+			"192.168.10.0/23",
+			"192.168.10.0/22",
+			"192.0.0.0/7",
+			"192.168.11.0/24",
+			"10.0.23.128/25",
+			"206.17.144.0/20",
+			"9.17.0.0/12",
+			"192.168.0.0/16"
+		};
+		
+		byteAddresses = new HashMap<String, byte[]>(strPrefixes.length+10);
+		for (String prefix : strPrefixes) {
+			String address = prefix.split("/")[0];
+			int prefixLength = Integer.parseInt(prefix.split("/")[1]);
+			byteAddresses.put(prefix, InetAddresses.forString(address).getAddress());
+			
+			PtreeNode node = ptree.acquire(byteAddresses.get(prefix), prefixLength);
+			node.rib = new Rib("192.168.10.101", "192.168.60.1", prefixLength);
+			ooptrie.put(new Prefix(byteAddresses.get(prefix), prefixLength), 
+					new Rib("192.168.10.101", "192.168.60.1", prefixLength));
+		}
+	}
+
+	@After
+	public void tearDown() throws Exception {
+	}
+
+	@Ignore
+	@Test
+	public void testAcquireByteArray() {
+		fail("Not yet implemented");
+	}
+
+	@Ignore
+	@Test
+	public void testAcquireByteArrayInt() {
+		//First let's test an empty Ptree
+		Ptree localPtree = new Ptree(32);
+		PtreeNode node = localPtree.acquire(new byte[] {0x00, 0x00, 0x00, 0x00});
+		assertTrue(node != null && node.rib == null);
+		
+		//Now let's look at the prepopulated tree
+		String testPrefix = "206.17.144.0/20";
+		PtreeNode existingNode = ptree.acquire(byteAddresses.get(testPrefix), 20);
+		printByteArray(existingNode.key);
+		printByteArray(byteAddresses.get(testPrefix));
+		assertTrue(existingNode != null && existingNode.rib == null);
+		
+		assertTrue(Arrays.equals(existingNode.key, byteAddresses.get(testPrefix)));
+	}
+
+	@Test
+	public void testLookup() {
+		String prefix1 = "192.168.10.12";
+		int length1 = 29;
+		PtreeNode node1 = ptree.lookup(InetAddresses.forString(prefix1).getAddress(), length1);
+		
+		//There should be no direct match
+		assertTrue(node1 == null);
+		
+		log.debug("{} null: {}", "node1", node1 == null ? "true" : "false");
+		
+		String prefix2 = "206.17.144.0";
+		int length2 = 20;
+		PtreeNode node2 = ptree.lookup(InetAddresses.forString(prefix2).getAddress(), length2);
+		
+		assertTrue(node2 != null);
+		assertTrue(Arrays.equals(node2.key, byteAddresses.get(prefix2 + "/" + length2)));
+		
+		log.debug("{} null: {}", "node2", node2 == null ? "true" : "false");
+		if (node2 != null) {
+			log.debug("{} key: {}, keybits: {}", new Object[] {"node2", node2.key, node2.keyBits});
+		}
+		
+		String prefix3 = "192.0.0.0";
+		int length3 = 7;
+		PtreeNode node3 = ptree.lookup(InetAddresses.forString(prefix3).getAddress(), length3);
+		assertTrue(node3 != null);
+	}
+
+	@Test
+	public void testMatch() {
+		String prefix1 = "192.168.10.12";
+		int length1 = 29;
+		PtreeNode node1 = ptree.match(InetAddresses.forString(prefix1).getAddress(), length1);
+		
+		//There should be no direct match, but we should get the covering prefix
+		assertTrue(node1 != null);
+		assertTrue(Arrays.equals(node1.key, byteAddresses.get("192.168.10.0/24")));
+		
+		log.debug("{} null: {}", "node1", node1 == null ? "true" : "false");
+		if (node1 != null) {
+			log.debug("{} key: {}, keybits: {}", new Object[] {"node1", node1.key, node1.keyBits});
+		}
+	}
+	
+	@Ignore
+	@Test
+	public void testTraverse() {
+		
+		String expected = "[0, 0, 0, 0]/0\n";
+		expected += "[8, 0, 0, 0]/6\n";
+		expected += "[9, 17, 0, 0]/12\n";
+		expected += "[10, 0, 23, -128]/25\n";
+		expected += "[-64, 0, 0, 0]/4\n";
+		expected += "[-64, -88, 0, 0]/16\n";
+		expected += "[-64, -88, 8, 0]/22\n";
+		expected += "[-64, -88, 10, 0]/23\n";
+		expected += "[-64, -88, 10, 0]/24\n";
+		expected += "[-64, -88, 11, 0]/24\n";
+		expected += "[-50, 17, -112, 0]/20\n";
+		
+		PtreeNode node;
+		String result = "";
+		
+		for (node = ptree.begin(); node != null; node = ptree.next(node)) {
+			result += printByteArray(node.key) + "/" + node.keyBits + "\n";
+		}
+		
+		assertEquals(expected, result);
+	}
+
+	@Ignore
+	@Test
+	public void testBegin() {
+		fail("Not yet implemented");
+	}
+
+	@Ignore
+	@Test
+	public void testNext() {
+		fail("Not yet implemented");
+	}
+
+	@Ignore
+	@Test
+	public void testDelReference() {
+		fail("Not yet implemented");
+	}
+	
+	@Test
+	public void testMisc() {
+		int bitIndex = -1;
+		int index = (int)(bitIndex / Byte.SIZE);
+	    int bit = (int)(bitIndex % Byte.SIZE);
+	    
+	    log.debug("index {} bit {}", index, bit); 
+	    log.debug("percent {}", 1%8);
+	    
+	    //PtreeNode node1 = new PtreeNode(new byte[] {0x0, 0x0, 0x0, 0x0}, 0, 4);
+	    PtreeNode node1 = new PtreeNode(null, 0, 4);
+	    log.debug("node1: key {}, keybits {}", printByteArray(node1.key), node1.keyBits);
+	    
+	    //PtreeNode node2 = new PtreeNode(new byte[] {(byte)0xff, (byte)0xff, (byte)0xff, (byte)0xff}, 
+	    PtreeNode node2 = new PtreeNode(null,
+	    		32, 4);
+	    log.debug("node2: key {}, keybits {}", printByteArray(node2.key), node2.keyBits);
+	}
+	
+	@Test
+	public void testIteration() {
+		Iterator<IPatriciaTrie.Entry> it = ooptrie.iterator();
+		
+		while (it.hasNext()) {
+			IPatriciaTrie.Entry entry = it.next();
+			log.debug("PatriciaTrie prefix {} \t {}", entry.getPrefix(), entry.getPrefix().printAsBits());
+		}
+		
+		try {
+			PtreeNode node;
+			for (node = ptree.begin(); node != null; node = ptree.next(node)) {
+				log.debug("Ptree prefix {}/{}", InetAddress.getByAddress(node.key).getHostAddress(), node.keyBits);
+			}
+		} catch (UnknownHostException e) {
+			
+		}
+	}
+	
+	private String printByteArray(byte[] array) {
+		String result = "[";
+		for (byte b : array) {
+			result += b + ", ";
+		}
+		result = result.substring(0, result.length() - 2);
+		result += "]";
+		return result;
+	}
+
+}