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 */ 018 019package org.apache.hadoop.hbase.util; 020 021import java.util.ArrayList; 022import java.util.Collection; 023import java.util.Collections; 024import java.util.Comparator; 025import java.util.Iterator; 026import java.util.List; 027import java.util.ListIterator; 028import java.util.RandomAccess; 029import org.apache.yetus.audience.InterfaceAudience; 030 031/** 032 * Simple sorted list implementation that uses {@link java.util.ArrayList} as 033 * the underlying collection so we can support RandomAccess. All mutations 034 * create a new copy of the <code>ArrayList</code> instance, so can be 035 * expensive. This class is only intended for use on small, very rarely 036 * written collections that expect highly concurrent reads. 037 * <p> 038 * Read operations are performed on a reference to the internal list at the 039 * time of invocation, so will not see any mutations to the collection during 040 * their operation. Iterating over list elements manually using the 041 * RandomAccess pattern involves multiple operations. For this to be safe get 042 * a reference to the internal list first using get(). 043 * <p> 044 * If constructed with a {@link java.util.Comparator}, the list will be sorted 045 * using the comparator. Adding or changing an element using an index will 046 * trigger a resort. 047 * <p> 048 * Iterators are read-only. They cannot be used to remove elements. 049 */ 050@edu.umd.cs.findbugs.annotations.SuppressWarnings(value="UG_SYNC_SET_UNSYNC_GET", 051 justification="TODO: synchronization in here needs review!!!") 052@InterfaceAudience.Private 053public class SortedList<E> implements List<E>, RandomAccess { 054 private volatile List<E> list; 055 private final Comparator<? super E> comparator; 056 057 /** 058 * Constructs an empty list with the default initial capacity that will be 059 * sorted using the given comparator. 060 * 061 * @param comparator the comparator 062 */ 063 public SortedList(Comparator<? super E> comparator) { 064 this.list = Collections.emptyList(); 065 this.comparator = comparator; 066 } 067 068 /** 069 * Constructs a list containing the elements of the given collection, in the 070 * order returned by the collection's iterator, that will be sorted with the 071 * given comparator. 072 * 073 * @param c the collection 074 * @param comparator the comparator 075 */ 076 public SortedList(Collection<? extends E> c, Comparator<? super E> comparator) { 077 this.list = Collections.unmodifiableList(new ArrayList<E>(c)); 078 this.comparator = comparator; 079 } 080 081 /** 082 * Returns a reference to the unmodifiable list currently backing the SortedList. 083 * Changes to the SortedList will not be reflected in this list. Use this 084 * method to get a reference for iterating over using the RandomAccess 085 * pattern. 086 */ 087 public List<E> get() { // FindBugs: UG_SYNC_SET_UNSYNC_GET complaint. Fix!! 088 return list; 089 } 090 091 @Override 092 public int size() { 093 return list.size(); 094 } 095 096 @Override 097 public boolean isEmpty() { 098 return list.isEmpty(); 099 } 100 101 @Override 102 public boolean contains(Object o) { 103 return list.contains(o); 104 } 105 106 @Override 107 public Iterator<E> iterator() { 108 return list.iterator(); 109 } 110 111 @Override 112 public Object[] toArray() { 113 return list.toArray(); 114 } 115 116 @Override 117 public <T> T[] toArray(T[] a) { 118 return list.toArray(a); 119 } 120 121 @Override 122 public synchronized boolean add(E e) { 123 ArrayList<E> newList = new ArrayList<>(list); 124 boolean changed = newList.add(e); 125 if (changed) { 126 Collections.sort(newList, comparator); 127 } 128 list = Collections.unmodifiableList(newList); 129 return changed; 130 } 131 132 @Override 133 public synchronized boolean remove(Object o) { 134 ArrayList<E> newList = new ArrayList<>(list); 135 // Removals in ArrayList won't break sorting 136 boolean changed = newList.remove(o); 137 list = Collections.unmodifiableList(newList); 138 return changed; 139 } 140 141 @Override 142 public boolean containsAll(Collection<?> c) { 143 return list.containsAll(c); 144 } 145 146 @Override 147 public synchronized boolean addAll(Collection<? extends E> c) { 148 ArrayList<E> newList = new ArrayList<>(list); 149 boolean changed = newList.addAll(c); 150 if (changed) { 151 Collections.sort(newList, comparator); 152 } 153 list = Collections.unmodifiableList(newList); 154 return changed; 155 } 156 157 @Override 158 public synchronized boolean addAll(int index, Collection<? extends E> c) { 159 ArrayList<E> newList = new ArrayList<>(list); 160 boolean changed = newList.addAll(index, c); 161 if (changed) { 162 Collections.sort(newList, comparator); 163 } 164 list = Collections.unmodifiableList(newList); 165 return changed; 166 } 167 168 @Override 169 public synchronized boolean removeAll(Collection<?> c) { 170 ArrayList<E> newList = new ArrayList<>(list); 171 // Removals in ArrayList won't break sorting 172 boolean changed = newList.removeAll(c); 173 list = Collections.unmodifiableList(newList); 174 return changed; 175 } 176 177 @Override 178 public synchronized boolean retainAll(Collection<?> c) { 179 ArrayList<E> newList = new ArrayList<>(list); 180 // Removals in ArrayList won't break sorting 181 boolean changed = newList.retainAll(c); 182 list = Collections.unmodifiableList(newList); 183 return changed; 184 } 185 186 @Override 187 public synchronized void clear() { 188 list = Collections.emptyList(); 189 } 190 191 @Override 192 public synchronized E get(int index) { 193 return list.get(index); 194 } 195 196 @Override 197 public synchronized E set(int index, E element) { 198 ArrayList<E> newList = new ArrayList<>(list); 199 E result = newList.set(index, element); 200 Collections.sort(list, comparator); 201 list = Collections.unmodifiableList(newList); 202 return result; 203 } 204 205 @Override 206 public synchronized void add(int index, E element) { 207 ArrayList<E> newList = new ArrayList<>(list); 208 newList.add(index, element); 209 Collections.sort(list, comparator); 210 list = Collections.unmodifiableList(newList); 211 } 212 213 @Override 214 public synchronized E remove(int index) { 215 ArrayList<E> newList = new ArrayList<>(list); 216 // Removals in ArrayList won't break sorting 217 E result = newList.remove(index); 218 list = Collections.unmodifiableList(newList); 219 return result; 220 } 221 222 @Override 223 public int indexOf(Object o) { 224 return list.indexOf(o); 225 } 226 227 @Override 228 public int lastIndexOf(Object o) { 229 return list.lastIndexOf(o); 230 } 231 232 @Override 233 public ListIterator<E> listIterator() { 234 return list.listIterator(); 235 } 236 237 @Override 238 public ListIterator<E> listIterator(int index) { 239 return list.listIterator(index); 240 } 241 242 @Override 243 public List<E> subList(int fromIndex, int toIndex) { 244 return list.subList(fromIndex, toIndex); 245 } 246}