src/test/java/org/xerial/util/RedBlackTreeTest.java

   1 /*--------------------------------------------------------------------------\r
   2  *  Copyright 2008 Taro L. Saito\r
   3  *\r
   4  *  Licensed under the Apache License, Version 2.0 (the "License");\r
   5  *  you may not use this file except in compliance with the License.\r
   6  *  You may obtain a copy of the License at\r
   7  *\r
   8  *     http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  *  Unless required by applicable law or agreed to in writing, software\r
  11  *  distributed under the License is distributed on an "AS IS" BASIS,\r
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  *  See the License for the specific language governing permissions and\r
  14  *  limitations under the License.\r
  15  *--------------------------------------------------------------------------*/\r
  16 //--------------------------------------\r
  17 // XerialJ\r
  18 //\r
  19 // RedBlackTreeTest.java\r
  20 // Since: Dec 5, 2008 6:13:16 PM\r
  21 //\r
  22 // $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/test/java/org/xerial/util/RedBlackTreeTest.java $\r
  23 // $Author: leo $\r
  24 //--------------------------------------\r
  25 package org.xerial.util;\r
  26 \r
  27 import static org.junit.Assert.*;\r
  28 \r
  29 import java.util.Random;\r
  30 import java.util.TreeMap;\r
  31 \r
  32 import org.junit.After;\r
  33 import org.junit.Before;\r
  34 import org.junit.Test;\r
  35 import org.xerial.util.log.Logger;\r
  36 \r
  37 public class RedBlackTreeTest\r
  38 {\r
  39     private static Logger _logger = Logger.getLogger(RedBlackTreeTest.class);\r
  40 \r
  41     RedBlackTree<Integer, String> t = new RedBlackTree<Integer, String>();\r
  42 \r
  43     @Before\r
  44     public void setUp() throws Exception\r
  45     {\r
  46         TreeMap<Integer, String> competitor = new TreeMap<Integer, String>();\r
  47 \r
  48         t.put(10, "world!");\r
  49         t.put(5, "hello");\r
  50         t.put(20, "nice to meet you");\r
  51     }\r
  52 \r
  53     @After\r
  54     public void tearDown() throws Exception\r
  55     {}\r
  56 \r
  57     @Test\r
  58     public void testGetKey()\r
  59     {\r
  60         assertEquals("hello", t.get(5));\r
  61         assertEquals("world!", t.get(10));\r
  62         assertEquals("nice to meet you", t.get(20));\r
  63     }\r
  64 \r
  65     @Test\r
  66     public void testSize()\r
  67     {\r
  68         assertEquals(3, t.size());\r
  69     }\r
  70 \r
  71     @Test\r
  72     public void testContains()\r
  73     {\r
  74 \r
  75         assertTrue(t.containsKey(5));\r
  76         assertTrue(t.containsKey(10));\r
  77         assertTrue(t.containsKey(20));\r
  78 \r
  79         assertTrue(!t.containsKey(0));\r
  80         assertTrue(!t.containsKey(34));\r
  81         assertTrue(!t.containsKey(102));\r
  82         assertTrue(!t.containsKey(-10));\r
  83     }\r
  84 \r
  85     @Test\r
  86     public void testInsert()\r
  87     {\r
  88         t.put(12, "evil");\r
  89 \r
  90         assertEquals("hello", t.get(5));\r
  91         assertEquals("world!", t.get(10));\r
  92         assertEquals("evil", t.get(12));\r
  93         assertEquals("nice to meet you", t.get(20));\r
  94 \r
  95         assertTrue(t.containsKey(5));\r
  96         assertTrue(t.containsKey(10));\r
  97         assertTrue(t.containsKey(20));\r
  98         assertTrue(t.containsKey(12));\r
  99 \r
 100         assertTrue(!t.containsKey(0));\r
 101         assertTrue(!t.containsKey(34));\r
 102         assertTrue(!t.containsKey(102));\r
 103         assertTrue(!t.containsKey(-10));\r
 104 \r
 105         assertEquals(4, t.size());\r
 106     }\r
 107 \r
 108     @Test\r
 109     public void performenceTest()\r
 110     {\r
 111         RedBlackTree<Integer, String> rt = new RedBlackTree<Integer, String>();\r
 112 \r
 113         final int N = 10000;\r
 114 \r
 115         Random r = new Random(0);\r
 116         StopWatch timer = new StopWatch();\r
 117         for (int i = 0; i < N; ++i)\r
 118             rt.put(r.nextInt(), null);\r
 119         _logger.debug("LLRB: " + timer.getElapsedTime());\r
 120         rt.clear();\r
 121 \r
 122         TreeMap<Integer, String> tm = new TreeMap<Integer, String>();\r
 123         r = new Random(0);\r
 124         timer.reset();\r
 125         for (int i = 0; i < N; ++i)\r
 126             tm.put(r.nextInt(), null);\r
 127         _logger.debug("RB:   " + timer.getElapsedTime());\r
 128 \r
 129     }\r
 130 \r
 131 }\r