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.*;
021
022import java.util.Comparator;
023import java.util.Iterator;
024import java.util.List;
025import java.util.ListIterator;
026import org.apache.hadoop.hbase.HBaseClassTestRule;
027import org.apache.hadoop.hbase.testclassification.MiscTests;
028import org.apache.hadoop.hbase.testclassification.SmallTests;
029import org.junit.ClassRule;
030import org.junit.Test;
031import org.junit.experimental.categories.Category;
032
033import org.apache.hbase.thirdparty.com.google.common.collect.Lists;
034
035@Category({ MiscTests.class, SmallTests.class })
036public class TestSortedList {
037
038  @ClassRule
039  public static final HBaseClassTestRule CLASS_RULE =
040    HBaseClassTestRule.forClass(TestSortedList.class);
041
042  static class StringComparator implements Comparator<String> {
043    @Override
044    public int compare(String o1, String o2) {
045      return o1.compareTo(o2);
046    }
047  }
048
049  @Test
050  public void testSorting() throws Exception {
051    SortedList<String> list = new SortedList<>(new StringComparator());
052    list.add("c");
053    list.add("d");
054    list.add("a");
055    list.add("b");
056
057    assertEquals(4, list.size());
058    assertArrayEquals(new String[] { "a", "b", "c", "d" }, list.toArray(new String[4]));
059
060    list.add("c");
061    assertEquals(5, list.size());
062    assertArrayEquals(new String[] { "a", "b", "c", "c", "d" }, list.toArray(new String[5]));
063
064    // Test that removal from head or middle maintains sort
065    list.remove("b");
066    assertEquals(4, list.size());
067    assertArrayEquals(new String[] { "a", "c", "c", "d" }, list.toArray(new String[4]));
068    list.remove("c");
069    assertEquals(3, list.size());
070    assertArrayEquals(new String[] { "a", "c", "d" }, list.toArray(new String[3]));
071    list.remove("a");
072    assertEquals(2, list.size());
073    assertArrayEquals(new String[] { "c", "d" }, list.toArray(new String[2]));
074  }
075
076  @Test
077  public void testReadOnlyIterators() throws Exception {
078    SortedList<String> list =
079      new SortedList<>(Lists.newArrayList("a", "b", "c", "d", "e"), new StringComparator());
080
081    Iterator<String> i = list.iterator();
082    i.next();
083    try {
084      i.remove();
085      fail("Iterator should have thrown an exception");
086    } catch (UnsupportedOperationException e) {
087      // ok
088    }
089
090    ListIterator<String> li = list.listIterator();
091    li.next();
092    try {
093      li.add("a");
094      fail("Iterator should have thrown an exception");
095    } catch (UnsupportedOperationException e) {
096      // ok
097    }
098    try {
099      li.set("b");
100      fail("Iterator should have thrown an exception");
101    } catch (UnsupportedOperationException e) {
102      // ok
103    }
104    try {
105      li.remove();
106      fail("Iterator should have thrown an exception");
107    } catch (UnsupportedOperationException e) {
108      // ok
109    }
110  }
111
112  @Test
113  public void testIteratorIsolation() throws Exception {
114    SortedList<String> list =
115      new SortedList<>(Lists.newArrayList("a", "b", "c", "d", "e"), new StringComparator());
116
117    // isolation of remove()
118    Iterator<String> iter = list.iterator();
119    list.remove("c");
120    boolean found = false;
121    while (iter.hasNext() && !found) {
122      found = "c".equals(iter.next());
123    }
124    assertTrue(found);
125
126    iter = list.iterator();
127    found = false;
128    while (iter.hasNext() && !found) {
129      found = "c".equals(iter.next());
130    }
131    assertFalse(found);
132
133    // isolation of add()
134    iter = list.iterator();
135    list.add("f");
136    found = false;
137    while (iter.hasNext() && !found) {
138      String next = iter.next();
139      found = "f".equals(next);
140    }
141    assertFalse(found);
142
143    // isolation of addAll()
144    iter = list.iterator();
145    list.addAll(Lists.newArrayList("g", "h", "i"));
146    found = false;
147    while (iter.hasNext() && !found) {
148      String next = iter.next();
149      found = "g".equals(next) || "h".equals(next) || "i".equals(next);
150    }
151    assertFalse(found);
152
153    // isolation of clear()
154    iter = list.iterator();
155    list.clear();
156    assertEquals(0, list.size());
157    int size = 0;
158    while (iter.hasNext()) {
159      iter.next();
160      size++;
161    }
162    assertTrue(size > 0);
163  }
164
165  @Test
166  public void testRandomAccessIsolation() throws Exception {
167    SortedList<String> list =
168      new SortedList<>(Lists.newArrayList("a", "b", "c"), new StringComparator());
169    List<String> innerList = list.get();
170    assertEquals("a", innerList.get(0));
171    assertEquals("b", innerList.get(1));
172    list.clear();
173    assertEquals("c", innerList.get(2));
174  }
175}