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 = new SortedList<>(Lists.newArrayList("a", "b", "c", "d", "e"), new StringComparator()); 079 080 Iterator<String> i = list.iterator(); 081 i.next(); 082 try { 083 i.remove(); 084 fail("Iterator should have thrown an exception"); 085 } catch (UnsupportedOperationException e) { 086 // ok 087 } 088 089 ListIterator<String> li = list.listIterator(); 090 li.next(); 091 try { 092 li.add("a"); 093 fail("Iterator should have thrown an exception"); 094 } catch (UnsupportedOperationException e) { 095 // ok 096 } 097 try { 098 li.set("b"); 099 fail("Iterator should have thrown an exception"); 100 } catch (UnsupportedOperationException e) { 101 // ok 102 } 103 try { 104 li.remove(); 105 fail("Iterator should have thrown an exception"); 106 } catch (UnsupportedOperationException e) { 107 // ok 108 } 109 } 110 111 @Test 112 public void testIteratorIsolation() throws Exception { 113 SortedList<String> list = new SortedList<>(Lists.newArrayList("a", "b", "c", "d", "e"), new StringComparator()); 114 115 // isolation of remove() 116 Iterator<String> iter = list.iterator(); 117 list.remove("c"); 118 boolean found = false; 119 while (iter.hasNext() && !found) { 120 found = "c".equals(iter.next()); 121 } 122 assertTrue(found); 123 124 iter = list.iterator(); 125 found = false; 126 while (iter.hasNext() && !found) { 127 found = "c".equals(iter.next()); 128 } 129 assertFalse(found); 130 131 // isolation of add() 132 iter = list.iterator(); 133 list.add("f"); 134 found = false; 135 while (iter.hasNext() && !found) { 136 String next = iter.next(); 137 found = "f".equals(next); 138 } 139 assertFalse(found); 140 141 // isolation of addAll() 142 iter = list.iterator(); 143 list.addAll(Lists.newArrayList("g", "h", "i")); 144 found = false; 145 while (iter.hasNext() && !found) { 146 String next = iter.next(); 147 found = "g".equals(next) || "h".equals(next) || "i".equals(next); 148 } 149 assertFalse(found); 150 151 // isolation of clear() 152 iter = list.iterator(); 153 list.clear(); 154 assertEquals(0, list.size()); 155 int size = 0; 156 while (iter.hasNext()) { 157 iter.next(); 158 size++; 159 } 160 assertTrue(size > 0); 161 } 162 163 @Test 164 public void testRandomAccessIsolation() throws Exception { 165 SortedList<String> list = new SortedList<>(Lists.newArrayList("a", "b", "c"), new StringComparator()); 166 List<String> innerList = list.get(); 167 assertEquals("a", innerList.get(0)); 168 assertEquals("b", innerList.get(1)); 169 list.clear(); 170 assertEquals("c", innerList.get(2)); 171 } 172} 173