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 composite list that presents multiple lists as a single unified list. 026 * 027 * <p> 028 * This class allows multiple lists to be viewed and accessed as if they were merged into 029 * a single list, without actually copying the elements. Modifications made through the iterator 030 * or list iterator affect the underlying lists. 031 * 032 * <h5 class='section'>Features:</h5> 033 * <ul class='spaced-list'> 034 * <li><b>Zero-Copy Composition:</b> No data is copied when creating a MultiList; it simply wraps the provided lists 035 * <li><b>Transparent Access:</b> Accessing elements by index or iterating over a MultiList seamlessly traverses all underlying lists in order 036 * <li><b>Modification Support:</b> Elements can be removed via the iterator's {@link Iterator#remove()} method 037 * <li><b>Efficient Size Calculation:</b> The size is computed by summing the sizes of all underlying lists 038 * <li><b>Enumeration Support:</b> Provides an {@link Enumeration} view via {@link #enumerator()} 039 * </ul> 040 * 041 * <h5 class='section'>Usage:</h5> 042 * <p class='bjava'> 043 * <jc>// Create a MultiList from three separate lists</jc> 044 * List<String> <jv>list1</jv> = List.of(<js>"a"</js>, <js>"b"</js>); 045 * List<String> <jv>list2</jv> = List.of(<js>"c"</js>, <js>"d"</js>); 046 * List<String> <jv>list3</jv> = List.of(<js>"e"</js>, <js>"f"</js>); 047 * 048 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(<jv>list1</jv>, <jv>list2</jv>, <jv>list3</jv>); 049 * 050 * <jc>// Access elements by index</jc> 051 * <jv>multiList</jv>.get(0); <jc>// Returns "a"</jc> 052 * <jv>multiList</jv>.get(3); <jc>// Returns "d"</jc> 053 * <jv>multiList</jv>.get(5); <jc>// Returns "f"</jc> 054 * 055 * <jc>// Iterate over all elements from all lists</jc> 056 * <jk>for</jk> (String <jv>element</jv> : <jv>multiList</jv>) { 057 * System.<jsf>out</jsf>.println(<jv>element</jv>); <jc>// Prints: a, b, c, d, e, f</jc> 058 * } 059 * 060 * <jc>// Get total size across all lists</jc> 061 * <jk>int</jk> <jv>totalSize</jv> = <jv>multiList</jv>.size(); <jc>// Returns: 6</jc> 062 * 063 * <jc>// Remove elements via iterator (affects underlying lists)</jc> 064 * Iterator<String> <jv>it</jv> = <jv>multiList</jv>.iterator(); 065 * <jk>while</jk> (<jv>it</jv>.hasNext()) { 066 * <jk>if</jk> (<jv>it</jv>.next().equals(<js>"b"</js>)) { 067 * <jv>it</jv>.remove(); <jc>// Removes "b" from list1</jc> 068 * } 069 * } 070 * </p> 071 * 072 * <h5 class='section'>Behavior Notes:</h5> 073 * <ul class='spaced-list'> 074 * <li>The order of access follows the order of lists as provided in the constructor 075 * <li>Within each list, access order follows the list's natural order 076 * <li>The underlying lists must not be <jk>null</jk>, but can be empty 077 * <li>Modifications via {@link Iterator#remove()} or {@link ListIterator#remove()} are delegated to the underlying list's iterator 078 * <li>This class does not support {@link #add(Object)}, {@link #add(int, Object)}, {@link #set(int, Object)}, or {@link #remove(int)} operations 079 * <li>The {@link #size()} method recomputes the sum each time it's called (not cached) 080 * <li>The {@link #get(int)} method locates the element by traversing lists until the correct index is found 081 * </ul> 082 * 083 * <h5 class='section'>Thread Safety:</h5> 084 * <p> 085 * This class is not inherently thread-safe. If the underlying lists are modified concurrently 086 * during iteration or access, the behavior is undefined. Synchronization must be handled externally if needed. 087 * 088 * <h5 class='section'>Example - Processing Multiple Data Sources:</h5> 089 * <p class='bjava'> 090 * <jc>// Combine results from database, cache, and defaults</jc> 091 * List<User> <jv>dbUsers</jv> = fetchFromDatabase(); 092 * List<User> <jv>cachedUsers</jv> = getCachedUsers(); 093 * List<User> <jv>defaultUsers</jv> = getDefaultUsers(); 094 * 095 * MultiList<User> <jv>allUsers</jv> = <jk>new</jk> MultiList<>(<jv>dbUsers</jv>, <jv>cachedUsers</jv>, <jv>defaultUsers</jv>); 096 * 097 * <jc>// Process all users from all sources</jc> 098 * <jv>allUsers</jv>.forEach(user -> processUser(user)); 099 * 100 * <jc>// Access specific user by index</jc> 101 * User <jv>user</jv> = <jv>allUsers</jv>.get(<jv>10</jv>); 102 * </p> 103 * 104 * <h5 class='section'>See Also:</h5> 105 * <ul> 106 * <li class='link'><a class="doclink" href="../../../../../index.html#juneau-commons">Overview > juneau-commons</a> 107 * </ul> 108 * 109 * @param <E> The element type of this list. 110 */ 111@SuppressWarnings({ 112 "java:S1192", // Duplicated literals (argument/property names) read more clearly inline than as constants 113 "java:S3776" // iterator()'s anonymous iterator (hasNext/next/remove) walks the list-of-lists with nested bounds checks 114}) 115public class MultiList<E> extends AbstractList<E> { 116 117 /** 118 * The underlying lists being wrapped by this MultiList. 119 * <p> 120 * These lists are accessed directly during iteration and index access without copying. 121 */ 122 final List<E>[] l; 123 124 /** 125 * Creates a new MultiList that presents the specified lists as a single unified list. 126 * 127 * <p> 128 * The lists are stored by reference (not copied), so modifications made through the 129 * MultiList's iterator will affect the original lists. 130 * 131 * <h5 class='section'>Example:</h5> 132 * <p class='bjava'> 133 * List<String> <jv>list1</jv> = <jk>new</jk> ArrayList<>(List.of(<js>"a"</js>, <js>"b"</js>)); 134 * List<String> <jv>list2</jv> = <jk>new</jk> ArrayList<>(List.of(<js>"c"</js>, <js>"d"</js>)); 135 * 136 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(<jv>list1</jv>, <jv>list2</jv>); 137 * <jc>// multiList now represents all elements from both lists</jc> 138 * </p> 139 * 140 * @param c Zero or more lists to combine into this list. Must not be <jk>null</jk>, 141 * and no individual list can be <jk>null</jk> (but lists can be empty). 142 * @throws IllegalArgumentException if the lists array or any list within it is <jk>null</jk>. 143 */ 144 @SafeVarargs 145 public MultiList(List<E>...c) { 146 reqnn("c", c); 147 for (var cc : c) 148 reqnn("c", cc); 149 l = c; 150 } 151 152 /** 153 * Returns an {@link Enumeration} view of this list. 154 * 155 * <p> 156 * This is useful for compatibility with legacy APIs that require an {@link Enumeration} 157 * rather than an {@link Iterator}. 158 * 159 * <h5 class='section'>Example:</h5> 160 * <p class='bjava'> 161 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(list1, list2); 162 * Enumeration<String> <jv>enumeration</jv> = <jv>multiList</jv>.enumerator(); 163 * 164 * <jk>while</jk> (<jv>enumeration</jv>.hasMoreElements()) { 165 * String <jv>element</jv> = <jv>enumeration</jv>.nextElement(); 166 * <jc>// Process element</jc> 167 * } 168 * </p> 169 * 170 * @return An {@link Enumeration} that iterates over all elements in all underlying lists. 171 * @see #iterator() 172 */ 173 public Enumeration<E> enumerator() { 174 return Collections.enumeration(this); 175 } 176 177 /** 178 * Returns the element at the specified position in this list. 179 * 180 * <p> 181 * The index is resolved by traversing the underlying lists in order until the 182 * correct list and position within that list is found. 183 * 184 * <h5 class='section'>Example:</h5> 185 * <p class='bjava'> 186 * List<String> <jv>list1</jv> = List.of(<js>"a"</js>, <js>"b"</js>); <jc>// indices 0-1</jc> 187 * List<String> <jv>list2</jv> = List.of(<js>"c"</js>, <js>"d"</js>, <js>"e"</js>); <jc>// indices 2-4</jc> 188 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(<jv>list1</jv>, <jv>list2</jv>); 189 * 190 * <jv>multiList</jv>.get(0); <jc>// Returns "a"</jc> 191 * <jv>multiList</jv>.get(2); <jc>// Returns "c"</jc> 192 * <jv>multiList</jv>.get(4); <jc>// Returns "e"</jc> 193 * </p> 194 * 195 * @param index The index of the element to return. 196 * @return The element at the specified position. 197 * @throws IndexOutOfBoundsException if the index is out of range (index < 0 || index >= size()). 198 */ 199 @Override /* List */ 200 public E get(int index) { 201 if (index < 0) 202 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); 203 var offset = 0; 204 for (var list : l) { 205 var size = list.size(); 206 if (index < offset + size) 207 return list.get(index - offset); 208 offset += size; 209 } 210 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); 211 } 212 213 /** 214 * Returns an iterator over all elements in all underlying lists. 215 * 216 * <p> 217 * The iterator traverses each list in the order they were provided to the constructor. 218 * Within each list, the iteration order follows the list's natural order. 219 * 220 * <p> 221 * The returned iterator supports the {@link Iterator#remove()} operation, which removes 222 * the current element from its underlying list. 223 * 224 * <h5 class='section'>Behavior:</h5> 225 * <ul class='spaced-list'> 226 * <li>Elements from the first list are iterated first, then the second, and so on 227 * <li>If a list is empty, it is skipped during iteration 228 * <li>Calling {@link Iterator#remove()} removes the element from the underlying list 229 * <li>Calling {@link Iterator#next()} when {@link Iterator#hasNext()} returns <jk>false</jk> 230 * throws {@link NoSuchElementException} 231 * <li>Calling {@link Iterator#remove()} before calling {@link Iterator#next()} or calling it twice 232 * in a row may throw {@link IllegalStateException} (behavior depends on underlying list) 233 * </ul> 234 * 235 * <h5 class='section'>Example:</h5> 236 * <p class='bjava'> 237 * List<String> <jv>list1</jv> = <jk>new</jk> ArrayList<>(List.of(<js>"a"</js>, <js>"b"</js>)); 238 * List<String> <jv>list2</jv> = <jk>new</jk> ArrayList<>(List.of(<js>"c"</js>, <js>"d"</js>)); 239 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(<jv>list1</jv>, <jv>list2</jv>); 240 * 241 * Iterator<String> <jv>it</jv> = <jv>multiList</jv>.iterator(); 242 * <jk>while</jk> (<jv>it</jv>.hasNext()) { 243 * String <jv>element</jv> = <jv>it</jv>.next(); 244 * <jk>if</jk> (<jv>element</jv>.equals(<js>"b"</js>)) { 245 * <jv>it</jv>.remove(); <jc>// Removes "b" from list1</jc> 246 * } 247 * } 248 * </p> 249 * 250 * @return An iterator over all elements in all underlying lists. 251 */ 252 @Override /* List */ 253 public Iterator<E> iterator() { 254 return new Iterator<>() { 255 int i = 0; 256 Iterator<E> i2 = (l.length > 0 ? l[i++].iterator() : null); 257 258 @Override /* Overridden from Iterator */ 259 public boolean hasNext() { 260 if (i2 == null) 261 return false; 262 if (i2.hasNext()) 263 return true; 264 for (var j = i; j < l.length; j++) 265 if (l[j].size() > 0) 266 return true; 267 return false; 268 } 269 270 @Override /* Overridden from Iterator */ 271 public E next() { 272 if (i2 == null) 273 throw new NoSuchElementException(); 274 while (! i2.hasNext()) { 275 if (i >= l.length) 276 throw new NoSuchElementException(); 277 i2 = l[i++].iterator(); 278 } 279 return i2.next(); 280 } 281 282 @Override /* Overridden from Iterator */ 283 public void remove() { 284 if (i2 == null) 285 throw new IllegalStateException(); 286 i2.remove(); 287 } 288 }; 289 } 290 291 /** 292 * Returns a list iterator over all elements in all underlying lists. 293 * 294 * <p> 295 * The list iterator traverses each list in the order they were provided to the constructor. 296 * The iterator starts at the beginning of the first list. 297 * 298 * <p> 299 * The returned list iterator supports the {@link ListIterator#remove()} operation, which removes 300 * the current element from its underlying list. 301 * 302 * <h5 class='section'>Behavior:</h5> 303 * <ul class='spaced-list'> 304 * <li>Elements from the first list are iterated first, then the second, and so on 305 * <li>If a list is empty, it is skipped during iteration 306 * <li>Calling {@link ListIterator#remove()} removes the element from the underlying list 307 * <li>Bidirectional navigation is supported, but may be less efficient than forward-only iteration 308 * </ul> 309 * 310 * @return A list iterator over all elements in all underlying lists, starting at the beginning. 311 */ 312 @Override /* List */ 313 public ListIterator<E> listIterator() { 314 return listIterator(0); 315 } 316 317 /** 318 * Returns a list iterator over all elements in all underlying lists, starting at the specified position. 319 * 320 * <p> 321 * The list iterator traverses each list in the order they were provided to the constructor. 322 * The iterator starts at the specified index. 323 * 324 * @param index The index to start the iterator at. 325 * @return A list iterator over all elements in all underlying lists, starting at the specified index. 326 * @throws IndexOutOfBoundsException if the index is out of range (index < 0 || index > size()). 327 */ 328 @Override /* List */ 329 public ListIterator<E> listIterator(int index) { 330 if (index < 0 || index > size()) 331 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); 332 return new MultiListIterator(index); 333 } 334 335 private final class MultiListIterator implements ListIterator<E> { 336 int currentIndex; 337 int listIndex; 338 int offset; 339 ListIterator<E> currentIterator; 340 341 MultiListIterator(int index) { 342 currentIndex = index; 343 listIndex = 0; 344 offset = 0; 345 currentIterator = null; 346 for (var i = 0; i < l.length; i++) { 347 var size = l[i].size(); 348 if (index < offset + size) { 349 listIndex = i; 350 currentIterator = l[i].listIterator(index - offset); 351 break; 352 } 353 offset += size; 354 } 355 if (currentIterator == null && l.length > 0) { 356 listIndex = l.length - 1; 357 currentIterator = l[listIndex].listIterator(l[listIndex].size()); 358 } 359 } 360 361 @Override 362 public boolean hasNext() { 363 if (currentIterator == null) 364 return false; 365 if (currentIterator.hasNext()) 366 return true; 367 for (var j = listIndex + 1; j < l.length; j++) 368 if (l[j].size() > 0) 369 return true; 370 return false; 371 } 372 373 @Override 374 public E next() { 375 if (currentIterator == null) 376 throw new NoSuchElementException(); 377 while (! currentIterator.hasNext()) { 378 if (listIndex + 1 >= l.length) 379 throw new NoSuchElementException(); 380 listIndex++; 381 currentIterator = l[listIndex].listIterator(); 382 } 383 currentIndex++; 384 return currentIterator.next(); 385 } 386 387 @Override 388 public boolean hasPrevious() { 389 if (currentIterator == null) 390 return false; 391 if (currentIterator.hasPrevious()) 392 return true; 393 for (var j = listIndex - 1; j >= 0; j--) 394 if (l[j].size() > 0) 395 return true; 396 return false; 397 } 398 399 @Override 400 public E previous() { 401 if (currentIterator == null) 402 throw new NoSuchElementException(); 403 while (! currentIterator.hasPrevious()) { 404 if (listIndex == 0) 405 throw new NoSuchElementException(); 406 listIndex--; 407 currentIterator = l[listIndex].listIterator(l[listIndex].size()); 408 } 409 currentIndex--; 410 return currentIterator.previous(); 411 } 412 413 @Override 414 public int nextIndex() { 415 return currentIndex; 416 } 417 418 @Override 419 public int previousIndex() { 420 return currentIndex - 1; 421 } 422 423 @Override 424 public void remove() { 425 if (currentIterator == null) 426 throw new IllegalStateException(); 427 currentIterator.remove(); 428 currentIndex--; 429 } 430 431 @Override 432 public void set(E e) { 433 if (currentIterator == null) 434 throw new IllegalStateException(); 435 currentIterator.set(e); 436 } 437 438 @Override 439 public void add(E e) { 440 throw new UnsupportedOperationException("MultiList does not support add operations"); 441 } 442 } 443 444 /** 445 * Returns the total number of elements across all underlying lists. 446 * 447 * <p> 448 * This method computes the size by summing the {@link List#size()} of each 449 * underlying list. The size is recalculated each time this method is called 450 * (it is not cached). 451 * 452 * <h5 class='section'>Example:</h5> 453 * <p class='bjava'> 454 * List<String> <jv>list1</jv> = List.of(<js>"a"</js>, <js>"b"</js>); <jc>// size = 2</jc> 455 * List<String> <jv>list2</jv> = List.of(<js>"c"</js>, <js>"d"</js>, <js>"e"</js>); <jc>// size = 3</jc> 456 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(<jv>list1</jv>, <jv>list2</jv>); 457 * 458 * <jk>int</jk> <jv>totalSize</jv> = <jv>multiList</jv>.size(); <jc>// Returns: 5</jc> 459 * </p> 460 * 461 * @return The sum of sizes of all underlying lists. 462 */ 463 @Override /* List */ 464 public int size() { 465 var i = 0; 466 for (var list : l) 467 i += list.size(); 468 return i; 469 } 470 471 /** 472 * Returns a string representation of this MultiList. 473 * 474 * <p> 475 * The format is <c>"[[...],[...],...]"</c> where each <c>[...]</c> is the standard 476 * standard string representation of each underlying list (as returned by {@link Object#toString()}). 477 * 478 * <h5 class='section'>Example:</h5> 479 * <p class='bjava'> 480 * List<String> <jv>list1</jv> = List.of(<js>"a"</js>, <js>"b"</js>); 481 * List<String> <jv>list2</jv> = List.of(<js>"c"</js>, <js>"d"</js>); 482 * MultiList<String> <jv>multiList</jv> = <jk>new</jk> MultiList<>(<jv>list1</jv>, <jv>list2</jv>); 483 * <jv>multiList</jv>.toString(); <jc>// Returns: "[[a, b], [c, d]]"</jc> 484 * </p> 485 * 486 * @return A string representation of this MultiList. 487 */ 488 @Override 489 public String toString() { 490 return Arrays.stream(l).map(Object::toString).collect(Collectors.joining(", ", "[", "]")); 491 } 492 493 /** 494 * Compares the specified object with this list for equality. 495 * 496 * <p> 497 * Returns <jk>true</jk> if and only if the specified object is also a list, both lists have the 498 * same size, and all corresponding pairs of elements in the two lists are <i>equal</i>. In other 499 * words, two lists are defined to be equal if they contain the same elements in the same order. 500 * 501 * <p> 502 * This implementation first checks if the specified object is this list. If so, it returns 503 * <jk>true</jk>; if not, it checks if the specified object is a list. If not, it returns 504 * <jk>false</jk>; if so, it iterates over both lists, comparing corresponding pairs of elements. 505 * 506 * @param o The object to be compared for equality with this list. 507 * @return <jk>true</jk> if the specified object is equal to this list. 508 */ 509 @Override 510 public boolean equals(Object o) { 511 if (!(o instanceof List)) 512 return false; 513 return eq(this, (List<?>)o, (x, y) -> { 514 var e1 = x.listIterator(); 515 var e2 = y.listIterator(); 516 while (e1.hasNext() && e2.hasNext()) { 517 var o1 = e1.next(); 518 var o2 = e2.next(); 519 if (neq(o1, o2)) 520 return false; 521 } 522 return !(e1.hasNext() || e2.hasNext()); 523 }); 524 } 525 526 /** 527 * Returns the hash code value for this list. 528 * 529 * <p> 530 * The hash code of a list is defined to be the result of the following calculation: 531 * <p class='bcode w800'> 532 * <jk>int</jk> hashCode = 1; 533 * <jk>for</jk> (E e : list) 534 * hashCode = 31 * hashCode + (e == <jk>null</jk> ? 0 : e.hashCode()); 535 * </p> 536 * 537 * <p> 538 * This ensures that <c>list1.equals(list2)</c> implies that 539 * <c>list1.hashCode()==list2.hashCode()</c> for any two lists <c>list1</c> and <c>list2</c>, 540 * as required by the general contract of {@link Object#hashCode()}. 541 * 542 * @return The hash code value for this list. 543 */ 544 @Override 545 public int hashCode() { 546 int hashCode = 1; 547 for (E e : this) 548 hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); 549 return hashCode; 550 } 551} 552