001/**
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.util;
019
020import static org.junit.Assert.assertEquals;
021import static org.junit.Assert.assertFalse;
022import static org.junit.Assert.assertNotNull;
023import static org.junit.Assert.assertTrue;
024
025import java.util.Random;
026import java.util.TreeMap;
027import org.apache.hadoop.hbase.HBaseClassTestRule;
028import org.apache.hadoop.hbase.testclassification.MiscTests;
029import org.apache.hadoop.hbase.testclassification.SmallTests;
030import org.apache.hadoop.hbase.util.AvlUtil.AvlIterableList;
031import org.apache.hadoop.hbase.util.AvlUtil.AvlKeyComparator;
032import org.apache.hadoop.hbase.util.AvlUtil.AvlLinkedNode;
033import org.apache.hadoop.hbase.util.AvlUtil.AvlNode;
034import org.apache.hadoop.hbase.util.AvlUtil.AvlNodeVisitor;
035import org.apache.hadoop.hbase.util.AvlUtil.AvlTree;
036import org.apache.hadoop.hbase.util.AvlUtil.AvlTreeIterator;
037import org.junit.ClassRule;
038import org.junit.Test;
039import org.junit.experimental.categories.Category;
040
041@Category({MiscTests.class, SmallTests.class})
042public class TestAvlUtil {
043
044  @ClassRule
045  public static final HBaseClassTestRule CLASS_RULE =
046      HBaseClassTestRule.forClass(TestAvlUtil.class);
047
048  private static final TestAvlKeyComparator KEY_COMPARATOR = new TestAvlKeyComparator();
049
050  @Test
051  public void testAvlTreeCrud() {
052    final int MAX_KEY = 99999999;
053    final int NELEM = 10000;
054
055    final TreeMap<Integer, Object> treeMap = new TreeMap<>();
056    TestAvlNode root = null;
057
058    final Random rand = new Random();
059    for (int i = 0; i < NELEM; ++i) {
060      int key = rand.nextInt(MAX_KEY);
061      if (AvlTree.get(root, key, KEY_COMPARATOR) != null) {
062        i--;
063        continue;
064      }
065      root = AvlTree.insert(root, new TestAvlNode(key));
066      treeMap.put(key, null);
067      for (Integer keyX: treeMap.keySet()) {
068        TestAvlNode node = AvlTree.get(root, keyX, KEY_COMPARATOR);
069        assertNotNull(node);
070        assertEquals(keyX.intValue(), node.getKey());
071      }
072    }
073
074    for (int i = 0; i < NELEM; ++i) {
075      int key = rand.nextInt(MAX_KEY);
076      TestAvlNode node = AvlTree.get(root, key, KEY_COMPARATOR);
077      if (!treeMap.containsKey(key)) {
078        assert node == null;
079        continue;
080      }
081      treeMap.remove(key);
082      assertEquals(key, node.getKey());
083      root = AvlTree.remove(root, key, KEY_COMPARATOR);
084      for (Integer keyX: treeMap.keySet()) {
085        node = AvlTree.get(root, keyX, KEY_COMPARATOR);
086        assertNotNull(node);
087        assertEquals(keyX.intValue(), node.getKey());
088      }
089    }
090  }
091
092  @Test
093  public void testAvlTreeVisitor() {
094    final int MIN_KEY = 0;
095    final int MAX_KEY = 50;
096
097    TestAvlNode root = null;
098    for (int i = MAX_KEY; i >= MIN_KEY; --i) {
099      root = AvlTree.insert(root, new TestAvlNode(i));
100    }
101
102    AvlTree.visit(root, new AvlNodeVisitor<TestAvlNode>() {
103      private int prevKey = -1;
104      @Override
105      public boolean visitNode(TestAvlNode node) {
106        assertEquals(prevKey, node.getKey() - 1);
107        assertTrue(node.getKey() >= MIN_KEY);
108        assertTrue(node.getKey() <= MAX_KEY);
109        prevKey = node.getKey();
110        return node.getKey() <= MAX_KEY;
111      }
112    });
113  }
114
115  @Test
116  public void testAvlTreeIterSeekFirst() {
117    final int MIN_KEY = 1;
118    final int MAX_KEY = 50;
119
120    TestAvlNode root = null;
121    for (int i = MIN_KEY; i < MAX_KEY; ++i) {
122      root = AvlTree.insert(root, new TestAvlNode(i));
123    }
124
125    AvlTreeIterator<TestAvlNode> iter = new AvlTreeIterator<>(root);
126    assertTrue(iter.hasNext());
127    long prevKey = 0;
128    while (iter.hasNext()) {
129      TestAvlNode node = iter.next();
130      assertEquals(prevKey + 1, node.getKey());
131      prevKey = node.getKey();
132    }
133    assertEquals(MAX_KEY - 1, prevKey);
134  }
135
136  @Test
137  public void testAvlTreeIterSeekTo() {
138    final int MIN_KEY = 1;
139    final int MAX_KEY = 50;
140
141    TestAvlNode root = null;
142    for (int i = MIN_KEY; i < MAX_KEY; i += 2) {
143      root = AvlTree.insert(root, new TestAvlNode(i));
144    }
145
146    for (int i = MIN_KEY - 1; i < MAX_KEY + 1; ++i) {
147      AvlTreeIterator<TestAvlNode> iter = new AvlTreeIterator<>(root, i, KEY_COMPARATOR);
148      if (i < MAX_KEY) {
149        assertTrue(iter.hasNext());
150      } else {
151        // searching for something greater than the last node
152        assertFalse(iter.hasNext());
153        break;
154      }
155
156      TestAvlNode node = iter.next();
157      assertEquals((i % 2 == 0) ? i + 1 : i, node.getKey());
158
159      long prevKey = node.getKey();
160      while (iter.hasNext()) {
161        node = iter.next();
162        assertTrue(node.getKey() > prevKey);
163        prevKey = node.getKey();
164      }
165    }
166  }
167
168  @Test
169  public void testAvlIterableListCrud() {
170    final int NITEMS = 10;
171    TestLinkedAvlNode prependHead = null;
172    TestLinkedAvlNode appendHead = null;
173    // prepend()/append()
174    for (int i = 0; i <= NITEMS; ++i) {
175      TestLinkedAvlNode pNode = new TestLinkedAvlNode(i);
176      assertFalse(AvlIterableList.isLinked(pNode));
177      prependHead = AvlIterableList.prepend(prependHead, pNode);
178      assertTrue(AvlIterableList.isLinked(pNode));
179
180      TestLinkedAvlNode aNode = new TestLinkedAvlNode(i);
181      assertFalse(AvlIterableList.isLinked(aNode));
182      appendHead = AvlIterableList.append(appendHead, aNode);
183      assertTrue(AvlIterableList.isLinked(aNode));
184    }
185    // readNext()
186    TestLinkedAvlNode pNode = prependHead;
187    TestLinkedAvlNode aNode = appendHead;
188    for (int i = 0; i <= NITEMS; ++i) {
189      assertEquals(NITEMS - i, pNode.getKey());
190      pNode = AvlIterableList.readNext(pNode);
191
192      assertEquals(i, aNode.getKey());
193      aNode = AvlIterableList.readNext(aNode);
194    }
195    // readPrev()
196    pNode = AvlIterableList.readPrev(prependHead);
197    aNode = AvlIterableList.readPrev(appendHead);
198    for (int i = 0; i <= NITEMS; ++i) {
199      assertEquals(i, pNode.getKey());
200      pNode = AvlIterableList.readPrev(pNode);
201
202      assertEquals(NITEMS - i, aNode.getKey());
203      aNode = AvlIterableList.readPrev(aNode);
204    }
205    // appendList()
206    TestLinkedAvlNode node = AvlIterableList.appendList(prependHead, appendHead);
207    for (int i = NITEMS; i >= 0; --i) {
208      assertEquals(i, node.getKey());
209      node = AvlIterableList.readNext(node);
210    }
211    for (int i = 0; i <= NITEMS; ++i) {
212      assertEquals(i, node.getKey());
213      node = AvlIterableList.readNext(node);
214    }
215  }
216
217  private static class TestAvlNode extends AvlNode<TestAvlNode> {
218    private final int key;
219
220    public TestAvlNode(int key) {
221      this.key = key;
222    }
223
224    public int getKey() {
225      return key;
226    }
227
228    @Override
229    public int compareTo(TestAvlNode other) {
230      return this.key - other.key;
231    }
232
233    @Override
234    public String toString() {
235      return String.format("TestAvlNode(%d)", key);
236    }
237  }
238
239  private static class TestLinkedAvlNode extends AvlLinkedNode<TestLinkedAvlNode> {
240    private final int key;
241
242    public TestLinkedAvlNode(int key) {
243      this.key = key;
244    }
245
246    public int getKey() {
247      return key;
248    }
249
250    @Override
251    public int compareTo(TestLinkedAvlNode other) {
252      return this.key - other.key;
253    }
254
255    @Override
256    public String toString() {
257      return String.format("TestLinkedAvlNode(%d)", key);
258    }
259  }
260
261  private static class TestAvlKeyComparator implements AvlKeyComparator<TestAvlNode> {
262    @Override
263    public int compareKey(TestAvlNode node, Object key) {
264      return node.getKey() - (int)key;
265    }
266  }
267}