src/test/java/net/onrc/onos/apps/bgproute/PatriciaTrieTest.java

package net.onrc.onos.apps.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 java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class PatriciaTrieTest {

	IPatriciaTrie<RibEntry> ptrie;
	Prefix[] prefixes;
	Map<Prefix, RibEntry> mappings;
	
	@Before
	public void setUp() throws Exception {
		ptrie = new PatriciaTrie<RibEntry>(32);
		mappings = new HashMap<Prefix, RibEntry>();
		
		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 RibEntry("192.168.10.101", "192.168.20." + i));
			ptrie.put(prefixes[i], new RibEntry("192.168.10.101", "192.168.20." + i));
		}
	}

	@After
	public void tearDown() throws Exception {
	}

	@Test
	public void testPut() {
		IPatriciaTrie<RibEntry> ptrie = new PatriciaTrie<RibEntry>(32);
		
		Prefix p1 = new Prefix("192.168.240.0", 20);
		RibEntry r1 = new RibEntry("192.168.10.101", "192.168.60.2");
		RibEntry 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);
		RibEntry r2 = new RibEntry("192.168.10.101", "192.168.20.1");
		retval = ptrie.put(p2, r2);
		assertNull(retval);
		
		Prefix p3 = new Prefix("192.168.208.0", 20);
		RibEntry r3 = new RibEntry("192.168.10.101", "192.168.30.1");
		retval = ptrie.put(p3,  r3);
		assertNull(retval);
		
		//Insert a new RibEntry entry over a previous one
		RibEntry r3new = new RibEntry("192.168.10.101", "192.168.60.2");
		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 RibEntry at this prefix
		Prefix p4 = new Prefix("192.168.192.0", 18);
		RibEntry r4 = new RibEntry("192.168.10.101", "192.168.40.1");
		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, RibEntry> entry : mappings.entrySet()) {
			RibEntry 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);
		RibEntry retval = ptrie.lookup(p1);
		assertNull(retval);
		
		//We'll put a RibEntry at an aggregate node and check if lookup returns correctly
		Prefix p2 = new Prefix("192.0.0.0", 4);
		RibEntry r2 = new RibEntry("192.168.10.101", "192.168.60.1");
		retval = ptrie.put(p2, r2);
		assertNull(retval);
		retval = ptrie.lookup(p2);
		assertTrue(retval.equals(r2));
	}

	//@Ignore
	@Test
	public void testMatch() {
		Prefix p1 = new Prefix("192.168.10.30", 32);
		Prefix p2 = new Prefix("192.168.10.30", 31);
		Prefix p3 = new Prefix("192.168.8.241", 32);
		Prefix p4 = new Prefix("1.0.0.0", 32);
		Prefix p5 = new Prefix("192.168.8.0", 22);
		Prefix p6 = new Prefix("192.168.8.0", 21);
		
		assertTrue(ptrie.match(p1).equals(mappings.get(prefixes[0])));
		assertTrue(ptrie.match(p2).equals(mappings.get(prefixes[0])));
		assertTrue(ptrie.match(p3).equals(mappings.get(prefixes[1])));
		assertNull(ptrie.match(p4));
		assertTrue(ptrie.match(p5).equals(mappings.get(prefixes[2])));
		//System.out.println(ptrie.match(p6).getNextHop().getHostAddress());
		assertTrue(ptrie.match(p6).equals(mappings.get(prefixes[8])));
		
		
		//TODO more extensive tests
		//fail("Not yet implemented");
	}

	@Test
	public void testRemove() {
		Prefix p1 = new Prefix("192.168.8.0", 23);
		RibEntry 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<RibEntry>> it = ptrie.iterator();
		int i = 0;
		assertTrue(it.hasNext());
		while (it.hasNext()) {
			IPatriciaTrie.Entry<RibEntry> entry = it.next();
			assertTrue(entry.getPrefix().equals(prefixes[order[i]]));
			i++;
		}
		assertFalse(it.hasNext());
		assertTrue(i == order.length);
		
		IPatriciaTrie<RibEntry> pt = new PatriciaTrie<RibEntry>(32);
		Iterator<IPatriciaTrie.Entry<RibEntry>> it2 = pt.iterator();
		assertFalse(it2.hasNext());
		it.next(); //throws NoSuchElementException
	}

}