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.assertNull;
024import static org.junit.Assert.assertTrue;
025
026import java.util.Random;
027import java.util.TreeMap;
028import java.util.concurrent.ThreadLocalRandom;
029import org.apache.hadoop.hbase.HBaseClassTestRule;
030import org.apache.hadoop.hbase.testclassification.MediumTests;
031import org.apache.hadoop.hbase.testclassification.MiscTests;
032import org.apache.hadoop.hbase.util.AvlUtil.AvlIterableList;
033import org.apache.hadoop.hbase.util.AvlUtil.AvlKeyComparator;
034import org.apache.hadoop.hbase.util.AvlUtil.AvlLinkedNode;
035import org.apache.hadoop.hbase.util.AvlUtil.AvlNode;
036import org.apache.hadoop.hbase.util.AvlUtil.AvlNodeVisitor;
037import org.apache.hadoop.hbase.util.AvlUtil.AvlTree;
038import org.apache.hadoop.hbase.util.AvlUtil.AvlTreeIterator;
039import org.junit.ClassRule;
040import org.junit.Test;
041import org.junit.experimental.categories.Category;
042
043@Category({ MiscTests.class, MediumTests.class })
044public class TestAvlUtil {
045
046  @ClassRule
047  public static final HBaseClassTestRule CLASS_RULE =
048    HBaseClassTestRule.forClass(TestAvlUtil.class);
049
050  private static final TestAvlKeyComparator KEY_COMPARATOR = new TestAvlKeyComparator();
051
052  @Test
053  public void testAvlTreeCrud() {
054    final int MAX_KEY = 99999999;
055    final int NELEM = 10000;
056
057    final TreeMap<Integer, Object> treeMap = new TreeMap<>();
058    TestAvlNode root = null;
059
060    Random rand = ThreadLocalRandom.current();
061    for (int i = 0; i < NELEM; ++i) {
062      int key = rand.nextInt(MAX_KEY);
063      if (AvlTree.get(root, key, KEY_COMPARATOR) != null) {
064        i--;
065        continue;
066      }
067      root = AvlTree.insert(root, new TestAvlNode(key));
068      treeMap.put(key, null);
069      for (Integer keyX : treeMap.keySet()) {
070        TestAvlNode node = AvlTree.get(root, keyX, KEY_COMPARATOR);
071        assertNotNull(node);
072        assertEquals(keyX.intValue(), node.getKey());
073      }
074    }
075
076    for (int i = 0; i < NELEM; ++i) {
077      int key = rand.nextInt(MAX_KEY);
078      TestAvlNode node = AvlTree.get(root, key, KEY_COMPARATOR);
079      if (!treeMap.containsKey(key)) {
080        assertNull(node);
081        continue;
082      }
083      treeMap.remove(key);
084      assertEquals(key, node.getKey());
085      root = AvlTree.remove(root, key, KEY_COMPARATOR);
086      for (Integer keyX : treeMap.keySet()) {
087        node = AvlTree.get(root, keyX, KEY_COMPARATOR);
088        assertNotNull(node);
089        assertEquals(keyX.intValue(), node.getKey());
090      }
091    }
092  }
093
094  @Test
095  public void testAvlTreeVisitor() {
096    final int MIN_KEY = 0;
097    final int MAX_KEY = 50;
098
099    TestAvlNode root = null;
100    for (int i = MAX_KEY; i >= MIN_KEY; --i) {
101      root = AvlTree.insert(root, new TestAvlNode(i));
102    }
103
104    AvlTree.visit(root, new AvlNodeVisitor<TestAvlNode>() {
105      private int prevKey = -1;
106
107      @Override
108      public boolean visitNode(TestAvlNode node) {
109        assertEquals(prevKey, node.getKey() - 1);
110        assertTrue(node.getKey() >= MIN_KEY);
111        assertTrue(node.getKey() <= MAX_KEY);
112        prevKey = node.getKey();
113        return node.getKey() <= MAX_KEY;
114      }
115    });
116  }
117
118  @Test
119  public void testAvlTreeIterSeekFirst() {
120    final int MIN_KEY = 1;
121    final int MAX_KEY = 50;
122
123    TestAvlNode root = null;
124    for (int i = MIN_KEY; i < MAX_KEY; ++i) {
125      root = AvlTree.insert(root, new TestAvlNode(i));
126    }
127
128    AvlTreeIterator<TestAvlNode> iter = new AvlTreeIterator<>(root);
129    assertTrue(iter.hasNext());
130    long prevKey = 0;
131    while (iter.hasNext()) {
132      TestAvlNode node = iter.next();
133      assertEquals(prevKey + 1, node.getKey());
134      prevKey = node.getKey();
135    }
136    assertEquals(MAX_KEY - 1, prevKey);
137  }
138
139  @Test
140  public void testAvlTreeIterSeekTo() {
141    final int MIN_KEY = 1;
142    final int MAX_KEY = 50;
143
144    TestAvlNode root = null;
145    for (int i = MIN_KEY; i < MAX_KEY; i += 2) {
146      root = AvlTree.insert(root, new TestAvlNode(i));
147    }
148
149    for (int i = MIN_KEY - 1; i < MAX_KEY + 1; ++i) {
150      AvlTreeIterator<TestAvlNode> iter = new AvlTreeIterator<>(root, i, KEY_COMPARATOR);
151      if (i < MAX_KEY) {
152        assertTrue(iter.hasNext());
153      } else {
154        // searching for something greater than the last node
155        assertFalse(iter.hasNext());
156        break;
157      }
158
159      TestAvlNode node = iter.next();
160      assertEquals((i % 2 == 0) ? i + 1 : i, node.getKey());
161
162      long prevKey = node.getKey();
163      while (iter.hasNext()) {
164        node = iter.next();
165        assertTrue(node.getKey() > prevKey);
166        prevKey = node.getKey();
167      }
168    }
169  }
170
171  @Test
172  public void testAvlIterableListCrud() {
173    final int NITEMS = 10;
174    TestLinkedAvlNode prependHead = null;
175    TestLinkedAvlNode appendHead = null;
176    // prepend()/append()
177    for (int i = 0; i <= NITEMS; ++i) {
178      TestLinkedAvlNode pNode = new TestLinkedAvlNode(i);
179      assertFalse(AvlIterableList.isLinked(pNode));
180      prependHead = AvlIterableList.prepend(prependHead, pNode);
181      assertTrue(AvlIterableList.isLinked(pNode));
182
183      TestLinkedAvlNode aNode = new TestLinkedAvlNode(i);
184      assertFalse(AvlIterableList.isLinked(aNode));
185      appendHead = AvlIterableList.append(appendHead, aNode);
186      assertTrue(AvlIterableList.isLinked(aNode));
187    }
188    // readNext()
189    TestLinkedAvlNode pNode = prependHead;
190    TestLinkedAvlNode aNode = appendHead;
191    for (int i = 0; i <= NITEMS; ++i) {
192      assertEquals(NITEMS - i, pNode.getKey());
193      pNode = AvlIterableList.readNext(pNode);
194
195      assertEquals(i, aNode.getKey());
196      aNode = AvlIterableList.readNext(aNode);
197    }
198    // readPrev()
199    pNode = AvlIterableList.readPrev(prependHead);
200    aNode = AvlIterableList.readPrev(appendHead);
201    for (int i = 0; i <= NITEMS; ++i) {
202      assertEquals(i, pNode.getKey());
203      pNode = AvlIterableList.readPrev(pNode);
204
205      assertEquals(NITEMS - i, aNode.getKey());
206      aNode = AvlIterableList.readPrev(aNode);
207    }
208    // appendList()
209    TestLinkedAvlNode node = AvlIterableList.appendList(prependHead, appendHead);
210    for (int i = NITEMS; i >= 0; --i) {
211      assertEquals(i, node.getKey());
212      node = AvlIterableList.readNext(node);
213    }
214    for (int i = 0; i <= NITEMS; ++i) {
215      assertEquals(i, node.getKey());
216      node = AvlIterableList.readNext(node);
217    }
218  }
219
220  private static class TestAvlNode extends AvlNode<TestAvlNode> {
221    private final int key;
222
223    public TestAvlNode(int key) {
224      this.key = key;
225    }
226
227    public int getKey() {
228      return key;
229    }
230
231    @Override
232    public int compareTo(TestAvlNode other) {
233      return this.key - other.key;
234    }
235
236    @Override
237    public String toString() {
238      return String.format("TestAvlNode(%d)", key);
239    }
240  }
241
242  private static class TestLinkedAvlNode extends AvlLinkedNode<TestLinkedAvlNode> {
243    private final int key;
244
245    public TestLinkedAvlNode(int key) {
246      this.key = key;
247    }
248
249    public int getKey() {
250      return key;
251    }
252
253    @Override
254    public int compareTo(TestLinkedAvlNode other) {
255      return this.key - other.key;
256    }
257
258    @Override
259    public String toString() {
260      return String.format("TestLinkedAvlNode(%d)", key);
261    }
262  }
263
264  private static class TestAvlKeyComparator implements AvlKeyComparator<TestAvlNode> {
265    @Override
266    public int compareKey(TestAvlNode node, Object key) {
267      return node.getKey() - (int) key;
268    }
269  }
270}