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