001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.juneau.commons.collections; 018 019import static org.apache.juneau.commons.utils.Shorts.*; 020 021import java.util.*; 022import java.util.stream.*; 023 024/** 025 * A reversed view of a list that does not modify the underlying list. 026 * 027 * <p> 028 * This class provides a read-only reversed view of a list, where element access is transparently 029 * reversed without copying or modifying the original list. All read operations (get, iterator, etc.) 030 * operate on the underlying list in reverse order. 031 * 032 * <h5 class='section'>Features:</h5> 033 * <ul class='spaced-list'> 034 * <li>Zero-copy reverse view - no data duplication 035 * <li>Efficient random access via index translation 036 * <li>Reflects changes in the underlying list automatically 037 * <li>Read-only - modification operations throw {@link UnsupportedOperationException} 038 * <li>Iterator and ListIterator support in reversed order 039 * </ul> 040 * 041 * <h5 class='section'>Usage:</h5> 042 * <p class='bjava'> 043 * <jc>// Create a list</jc> 044 * List<String> <jv>original</jv> = List.<jsm>of</jsm>(<js>"A"</js>, <js>"B"</js>, <js>"C"</js>); 045 * 046 * <jc>// Create reversed view</jc> 047 * List<String> <jv>reversed</jv> = <jk>new</jk> ReversedList<>(<jv>original</jv>); 048 * 049 * <jc>// Access in reverse order</jc> 050 * <jv>reversed</jv>.get(0); <jc>// Returns "C"</jc> 051 * <jv>reversed</jv>.get(1); <jc>// Returns "B"</jc> 052 * <jv>reversed</jv>.get(2); <jc>// Returns "A"</jc> 053 * 054 * <jc>// Iterate in reverse</jc> 055 * <jk>for</jk> (String <jv>s</jv> : <jv>reversed</jv>) { 056 * <jc>// Iterates: "C", "B", "A"</jc> 057 * } 058 * </p> 059 * 060 * <h5 class='section'>Notes:</h5> 061 * <ul class='spaced-list'> 062 * <li>The underlying list must not be null 063 * <li>Changes to the underlying list are immediately visible in the reversed view 064 * <li>All modification operations (add, remove, set, clear) throw {@link UnsupportedOperationException} 065 * <li>Size changes in the underlying list are reflected in this view 066 * </ul> 067 * 068 * @param <E> The element type. 069 */ 070@SuppressWarnings({ 071 "java:S1192" // Duplicated literals (argument/property names) read more clearly inline than as constants 072}) 073public class ReversedList<E> extends AbstractList<E> implements RandomAccess { 074 075 private final List<E> list; 076 077 /** 078 * Creates a new reversed view of the specified list. 079 * 080 * @param list The list to reverse. Must not be <jk>null</jk>. 081 * @throws IllegalArgumentException if list is <jk>null</jk>. 082 */ 083 public ReversedList(List<E> list) { 084 this.list = reqnn("list", list); 085 } 086 087 /** 088 * Not supported - this is a read-only view. 089 * 090 * @throws UnsupportedOperationException always 091 */ 092 @Override 093 public void add(int index, E element) { 094 throw new UnsupportedOperationException("ReversedList is read-only"); 095 } 096 097 /** 098 * Not supported - this is a read-only view. 099 * 100 * @throws UnsupportedOperationException always 101 */ 102 @Override 103 public void clear() { 104 throw new UnsupportedOperationException("ReversedList is read-only"); 105 } 106 107 /** 108 * Returns the element at the specified position in this reversed view. 109 * 110 * <p> 111 * The position is translated to access the underlying list in reverse order. 112 * For example, index 0 returns the last element of the underlying list. 113 * 114 * @param index The index of the element to return (0-based, in reversed order). 115 * @return The element at the specified position in the reversed view. 116 * @throws IndexOutOfBoundsException if the index is out of range. 117 */ 118 @Override 119 public E get(int index) { 120 return list.get(list.size() - 1 - index); 121 } 122 123 /** 124 * Returns an iterator over the elements in this reversed view in proper sequence. 125 * 126 * <p> 127 * The iterator traverses the underlying list in reverse order. 128 * 129 * @return An iterator over the elements in reversed order. 130 */ 131 @Override 132 public Iterator<E> iterator() { 133 return new Iterator<>() { 134 private final ListIterator<E> it = list.listIterator(list.size()); 135 136 @Override 137 public boolean hasNext() { 138 return it.hasPrevious(); 139 } 140 141 @Override 142 public E next() { 143 return it.previous(); 144 } 145 146 @Override 147 public void remove() { 148 throw new UnsupportedOperationException("ReversedList is read-only"); 149 } 150 }; 151 } 152 153 /** 154 * Returns a list iterator over the elements in this reversed view. 155 * 156 * <p> 157 * The iterator traverses the underlying list in reverse order. 158 * 159 * @return A list iterator over the elements in reversed order. 160 */ 161 @Override 162 public ListIterator<E> listIterator() { 163 return listIterator(0); 164 } 165 166 /** 167 * Returns a list iterator over the elements in this reversed view, starting at the specified position. 168 * 169 * <p> 170 * The iterator traverses the underlying list in reverse order, starting from the translated position. 171 * 172 * @param index The index of the first element to be returned from the list iterator (in reversed order). 173 * @return A list iterator over the elements in reversed order. 174 * @throws IndexOutOfBoundsException if the index is out of range. 175 */ 176 @Override 177 public ListIterator<E> listIterator(int index) { 178 if (index < 0 || index > size()) 179 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); 180 181 return new ListIterator<>() { 182 private final ListIterator<E> it = list.listIterator(list.size() - index); 183 184 @Override 185 public void add(E e) { 186 throw new UnsupportedOperationException("ReversedList is read-only"); 187 } 188 189 @Override 190 public boolean hasNext() { 191 return it.hasPrevious(); 192 } 193 194 @Override 195 public boolean hasPrevious() { 196 return it.hasNext(); 197 } 198 199 @Override 200 public E next() { 201 return it.previous(); 202 } 203 204 @Override 205 public int nextIndex() { 206 return list.size() - it.previousIndex() - 1; 207 } 208 209 @Override 210 public E previous() { 211 return it.next(); 212 } 213 214 @Override 215 public int previousIndex() { 216 return list.size() - it.nextIndex() - 1; 217 } 218 219 @Override 220 public void remove() { 221 throw new UnsupportedOperationException("ReversedList is read-only"); 222 } 223 224 @Override 225 public void set(E e) { 226 throw new UnsupportedOperationException("ReversedList is read-only"); 227 } 228 }; 229 } 230 231 /** 232 * Not supported - this is a read-only view. 233 * 234 * @throws UnsupportedOperationException always 235 */ 236 @Override 237 public E remove(int index) { 238 throw new UnsupportedOperationException("ReversedList is read-only"); 239 } 240 241 /** 242 * Not supported - this is a read-only view. 243 * 244 * @throws UnsupportedOperationException always 245 */ 246 @Override 247 public E set(int index, E element) { 248 throw new UnsupportedOperationException("ReversedList is read-only"); 249 } 250 251 /** 252 * Returns the number of elements in this reversed view. 253 * 254 * <p> 255 * This is always equal to the size of the underlying list. 256 * 257 * @return The number of elements in this reversed view. 258 */ 259 @Override 260 public int size() { 261 return list.size(); 262 } 263 264 /** 265 * Returns a view of the portion of this reversed list between the specified indices. 266 * 267 * <p> 268 * The returned sublist is also a reversed view and reflects changes in the underlying list. 269 * 270 * @param fromIndex Low endpoint (inclusive) of the subList. 271 * @param toIndex High endpoint (exclusive) of the subList. 272 * @return A view of the specified range within this reversed list. 273 * @throws IndexOutOfBoundsException if the indices are out of range. 274 */ 275 @Override 276 public List<E> subList(int fromIndex, int toIndex) { 277 if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex) 278 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex + ", size: " + size()); 279 280 // Translate indices to the underlying list 281 int translatedFrom = list.size() - toIndex; 282 int translatedTo = list.size() - fromIndex; 283 284 return new ReversedList<>(list.subList(translatedFrom, translatedTo)); 285 } 286 287 /** 288 * Returns a string representation of this reversed list. 289 * 290 * <p> 291 * The format follows the standard Java list convention: <c>"[element1, element2, ...]"</c> 292 * Elements are shown in reversed order (as they appear in this view). 293 * 294 * @return A string representation of this reversed list. 295 */ 296 @Override 297 public String toString() { 298 return stream().map(Object::toString).collect(Collectors.joining(", ", "[", "]")); 299 } 300 301 /** 302 * Compares the specified object with this list for equality. 303 * 304 * <p> 305 * Returns <jk>true</jk> if and only if the specified object is also a list, both lists have the 306 * same size, and all corresponding pairs of elements in the two lists are <i>equal</i>. In other 307 * words, two lists are defined to be equal if they contain the same elements in the same order. 308 * 309 * <p> 310 * This implementation compares elements in the reversed order as they appear in this view. 311 * 312 * @param o The object to be compared for equality with this list. 313 * @return <jk>true</jk> if the specified object is equal to this list. 314 */ 315 @Override 316 public boolean equals(Object o) { 317 if (!(o instanceof List)) 318 return false; 319 return eq(this, (List<?>)o, (x, y) -> { 320 var e1 = x.listIterator(); 321 var e2 = y.listIterator(); 322 while (e1.hasNext() && e2.hasNext()) { 323 var o1 = e1.next(); 324 var o2 = e2.next(); 325 if (neq(o1, o2)) 326 return false; 327 } 328 return !(e1.hasNext() || e2.hasNext()); 329 }); 330 } 331 332 /** 333 * Returns the hash code value for this list. 334 * 335 * <p> 336 * The hash code of a list is defined to be the result of the following calculation: 337 * <p class='bcode w800'> 338 * <jk>int</jk> hashCode = 1; 339 * <jk>for</jk> (E e : list) 340 * hashCode = 31 * hashCode + (e == <jk>null</jk> ? 0 : e.hashCode()); 341 * </p> 342 * 343 * <p> 344 * This ensures that <c>list1.equals(list2)</c> implies that 345 * <c>list1.hashCode()==list2.hashCode()</c> for any two lists <c>list1</c> and <c>list2</c>, 346 * as required by the general contract of {@link Object#hashCode()}. 347 * 348 * <p> 349 * This implementation computes the hash code from the elements in reversed order as they appear 350 * in this view. 351 * 352 * @return The hash code value for this list. 353 */ 354 @Override 355 public int hashCode() { 356 int hashCode = 1; 357 for (E e : this) 358 hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); 359 return hashCode; 360 } 361}