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