View Javadoc

1   /*
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  
20  package org.apache.hadoop.hbase.util;
21  
22  import static org.junit.Assert.*;
23  
24  import java.util.Comparator;
25  import java.util.Iterator;
26  import java.util.List;
27  import java.util.ListIterator;
28  
29  import com.google.common.collect.Lists;
30  
31  import org.apache.hadoop.hbase.testclassification.SmallTests;
32  import org.junit.Test;
33  import org.junit.experimental.categories.Category;
34  
35  @Category(SmallTests.class)
36  public class TestSortedList {
37  
38    static class StringComparator implements Comparator<String> {
39      @Override
40      public int compare(String o1, String o2) {
41        return o1.compareTo(o2);
42      }
43    }
44  
45    @Test
46    public void testSorting() throws Exception {
47      SortedList<String> list = new SortedList<String>(new StringComparator());
48      list.add("c");
49      list.add("d");
50      list.add("a");
51      list.add("b");
52  
53      assertEquals(4, list.size());
54      assertArrayEquals(new String[]{"a", "b", "c", "d"}, list.toArray(new String[4]));
55  
56      list.add("c");
57      assertEquals(5, list.size());
58      assertArrayEquals(new String[]{"a", "b", "c", "c", "d"}, list.toArray(new String[5]));
59  
60      // Test that removal from head or middle maintains sort
61      list.remove("b");
62      assertEquals(4, list.size());
63      assertArrayEquals(new String[]{"a", "c", "c", "d"}, list.toArray(new String[4]));
64      list.remove("c");
65      assertEquals(3, list.size());
66      assertArrayEquals(new String[]{"a", "c", "d"}, list.toArray(new String[3]));
67      list.remove("a");
68      assertEquals(2, list.size());
69      assertArrayEquals(new String[]{"c", "d"}, list.toArray(new String[2]));
70    }
71  
72    @Test
73    public void testReadOnlyIterators() throws Exception {
74      SortedList<String> list = new SortedList<String>(
75          Lists.newArrayList("a", "b", "c", "d", "e"), new StringComparator());
76  
77      Iterator<String> i = list.iterator();
78      i.next();
79      try {
80        i.remove();
81        fail("Iterator should have thrown an exception");
82      } catch (UnsupportedOperationException e) {
83        // ok
84      }
85  
86      ListIterator<String> li = list.listIterator();
87      li.next();
88      try {
89        li.add("a");
90        fail("Iterator should have thrown an exception");
91      } catch (UnsupportedOperationException e) {
92        // ok
93      }
94      try {
95        li.set("b");
96        fail("Iterator should have thrown an exception");
97      } catch (UnsupportedOperationException e) {
98        // ok
99      }
100     try {
101       li.remove();
102       fail("Iterator should have thrown an exception");
103     } catch (UnsupportedOperationException e) {
104       // ok
105     }
106   }
107 
108   @Test
109   public void testIteratorIsolation() throws Exception {
110     SortedList<String> list = new SortedList<String>(
111         Lists.newArrayList("a", "b", "c", "d", "e"), new StringComparator());
112 
113     // isolation of remove()
114     Iterator<String> iter = list.iterator();
115     list.remove("c");
116     boolean found = false;
117     while (iter.hasNext() && !found) {
118       found = "c".equals(iter.next());
119     }
120     assertTrue(found);
121 
122     iter = list.iterator();
123     found = false;
124     while (iter.hasNext() && !found) {
125       found = "c".equals(iter.next());
126     }
127     assertFalse(found);
128 
129     // isolation of add()
130     iter = list.iterator();
131     list.add("f");
132     found = false;
133     while (iter.hasNext() && !found) {
134       String next = iter.next();
135       found = "f".equals(next);
136     }
137     assertFalse(found);
138 
139     // isolation of addAll()
140     iter = list.iterator();
141     list.addAll(Lists.newArrayList("g", "h", "i"));
142     found = false;
143     while (iter.hasNext() && !found) {
144       String next = iter.next();
145       found = "g".equals(next) || "h".equals(next) || "i".equals(next);
146     }
147     assertFalse(found);
148 
149     // isolation of clear()
150     iter = list.iterator();
151     list.clear();
152     assertEquals(0, list.size());
153     int size = 0;
154     while (iter.hasNext()) {
155       iter.next();
156       size++;
157     }
158     assertTrue(size > 0);
159   }
160 
161   @Test
162   public void testRandomAccessIsolation() throws Exception {
163     SortedList<String> list = new SortedList<String>(
164         Lists.newArrayList("a", "b", "c"), new StringComparator());
165     List<String> innerList = list.get();
166     assertEquals("a", innerList.get(0));
167     assertEquals("b", innerList.get(1));
168     list.clear();
169     assertEquals("c", innerList.get(2));
170   }
171 }
172