001/* 002 * ============================================================================ 003 * Copyright © 2002-2023 by Thomas Thrien. 004 * All Rights Reserved. 005 * ============================================================================ 006 * 007 * Licensed to the public under the agreements of the GNU Lesser General Public 008 * License, version 3.0 (the "License"). You may obtain a copy of the License at 009 * 010 * http://www.gnu.org/licenses/lgpl.html 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, WITHOUT 014 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 015 * License for the specific language governing permissions and limitations 016 * under the License. 017 */ 018 019package org.tquadrat.foundation.util; 020 021import static java.util.Collections.reverse; 022import static org.apiguardian.api.API.Status.STABLE; 023import static org.tquadrat.foundation.lang.Objects.nonNull; 024import static org.tquadrat.foundation.lang.Objects.requireNonNullArgument; 025 026import java.util.ArrayList; 027import java.util.Collection; 028import java.util.Iterator; 029import java.util.Optional; 030import java.util.function.Consumer; 031import java.util.function.IntFunction; 032import java.util.stream.Stream; 033 034import org.apiguardian.api.API; 035import org.tquadrat.foundation.annotation.ClassVersion; 036import org.tquadrat.foundation.util.internal.HeadTailListImpl; 037 038/** 039 * <p>{@summary A {@code HeadTailList} is an unmodifiable list data 040 * structure}.</p> 041 * <p>Each modifying operation on it will create a new instance <i>of the 042 * list</i>, leaving the original list one unchanged.</p> 043 * <p>But only the list itself is copied, not the entries in it – these are 044 * shared amongst all copies of the list. Consequently changes to the data 045 * stored in the list should be avoided.</p> 046 * <p>To create a new instance of {@code HeadTailList}, call one of</p> 047 * <ul> 048 * <li>{@link #empty()} for an empty list</li> 049 * <li>{@link #from(Object[])} to initialise the list with some 050 * elements</li> 051 * <li>{@link #from(Collection)} to initialise the new list from a 052 * {@link Collection}</li> 053 * </ul> 054 * 055 * @param <T> The element type of the list. 056 * 057 * @extauthor Thomas Thrien - thomas.thrien@tquadrat.org 058 * @version $Id: HeadTailList.java 1060 2023-09-24 19:21:40Z tquadrat $ 059 * @since 0.0.4 060 * 061 * @UMLGraph.link 062 */ 063@SuppressWarnings( "ClassWithTooManyMethods" ) 064@ClassVersion( sourceVersion = "$Id: HeadTailList.java 1060 2023-09-24 19:21:40Z tquadrat $" ) 065@API( status = STABLE, since = "0.0.4" ) 066public sealed interface HeadTailList<T> extends Iterable<T> 067 permits HeadTailListImpl 068{ 069 /*---------*\ 070 ====** Methods **========================================================== 071 \*---------*/ 072 /** 073 * Returns a new list with the given element as the head, and this list as 074 * the tail. 075 * 076 * @param element The head for the new list. 077 * @return The new list. 078 */ 079 public HeadTailList<T> add( final T element ); 080 081 /** 082 * Returns a new list where the given list is appended to the end of this 083 * list. 084 * 085 * @param list The list to append. 086 * @return The new list. 087 */ 088 public default HeadTailList<T> append( final HeadTailList<T> list ) 089 { 090 final var retValue = requireNonNullArgument( list, "list" ).prepend( this ); 091 092 //---* Done *---------------------------------------------------------- 093 return retValue; 094 } // append() 095 096 /** 097 * Returns a new list where the given list is appended to the end of this 098 * list. 099 * 100 * @param list The list to append. 101 * @return The new list. 102 */ 103 public default HeadTailList<T> append( final Collection<T> list ) 104 { 105 final var retValue = from( requireNonNullArgument( list, "list" ) ).prepend( this ); 106 107 //---* Done *---------------------------------------------------------- 108 return retValue; 109 } // append() 110 111 /** 112 * Checks whether the list contains an element that is equal to the given 113 * one. 114 * 115 * @param element The element to look for. 116 * @return {@code true} if the element is in the list, {@code false} 117 * otherwise. 118 */ 119 public default boolean contains( final T element ) 120 { 121 var retValue = false; 122 if( nonNull( element ) ) 123 { 124 for( final var iterator = iterator(); iterator.hasNext() && !retValue; ) retValue = iterator.next().equals( element ); 125 } 126 127 //---* Done *---------------------------------------------------------- 128 return retValue; 129 } // contains() 130 131 /** 132 * <p>{@summary Returns an empty list.}</p> 133 * <p>Each call to this method will return the same instance.</p> 134 * 135 * @param <E> The element type for the list. 136 * @return The empty list. 137 */ 138 public static <E> HeadTailList<E> empty() { return HeadTailListImpl.empty(); } 139 140 /** 141 * {@inheritDoc} 142 */ 143 @Override 144 public boolean equals( Object o ); 145 146 /** 147 * Does the same as 148 * {@link #forEach(Consumer)}, but starting with last element first. 149 * 150 * @param action The action to perform. 151 */ 152 public void forEachReverse( final Consumer<? super T> action ); 153 154 /** 155 * Creates a new list from the given 156 * {@link Collection}. 157 * 158 * @param <E> The element type for the list. 159 * @param source The collection. 160 * @return The new list. 161 */ 162 public static <E> HeadTailList<E> from( final Collection<E> source ) 163 { 164 HeadTailList<E> retValue = empty(); 165 if( !requireNonNullArgument( source, "source" ).isEmpty() ) 166 { 167 final var list = new ArrayList<>( source ); 168 reverse( list ); 169 for( final var e : list ) retValue = retValue.add( e ); 170 } 171 172 //---* Done *---------------------------------------------------------- 173 return retValue; 174 } // from() 175 176 /** 177 * Creates a new list from the given elements. 178 * 179 * @param <E> The element type for the list. 180 * @param elements The elements. 181 * @return The new list. 182 */ 183 @SafeVarargs 184 public static <E> HeadTailList<E> from( final E... elements ) 185 { 186 HeadTailList<E> retValue = empty(); 187 for( var i = requireNonNullArgument( elements, "elements" ).length; i > 0; --i ) 188 { 189 retValue = retValue.add( elements [i - 1] ); 190 } 191 192 //---* Done *---------------------------------------------------------- 193 return retValue; 194 } // from() 195 196 /** 197 * <p>{@summary Returns the element that is identified by the given 198 * index}</p> 199 * <p>The index is in reverse order of the insertion sequence; this means 200 * tha the element added first has the highest index value 201 * (<code>size() - 1</code>).</p> 202 * 203 * @param index The index for the wanted element; 0 indicates the head. 204 * @return The element with the given index. 205 * @throws IndexOutOfBoundsException The given index is out of the range 206 * <code>index < 0 || index >= size()</code>. 207 */ 208 public default T get( final int index ) throws IndexOutOfBoundsException 209 { 210 if( head().isEmpty() || (index < 0) ) throw new IndexOutOfBoundsException( Integer.toString( index ) ); 211 final var retValue = index == 0 ? head().get() : tail().get( index - 1 ); 212 213 //---* Done *---------------------------------------------------------- 214 return retValue; 215 } // get() 216 217 /** 218 * {@inheritDoc} 219 */ 220 @Override 221 public int hashCode(); 222 223 /** 224 * <p>{@summary Returns the head of the list.}</p> 225 * <p>This will be 226 * {@linkplain Optional#empty() empty} 227 * only for the 228 * {@linkplain #empty() empty list}.</p> 229 * 230 * @return An instance of 231 * {@link Optional} 232 * that holds the head. 233 */ 234 public Optional<T> head(); 235 236 /** 237 * Checks whether the list is empty. 238 * 239 * @return {@code true} if the list is empty, {@code false} otherwise. 240 */ 241 public boolean isEmpty(); 242 243 /** 244 * {@inheritDoc} 245 */ 246 @Override 247 public Iterator<T> iterator(); 248 249 /** 250 * <p>{@summary Returns a new list where the given list is merged into 251 * this list.}</p> 252 * <p>This means that each element from this list is followed by an 253 * element of the other list; if one list is shorter than the other one, 254 * the elements of the longer one will just be appended to the end of the 255 * new list.</p> 256 * 257 * @param list The list to merge into this one. 258 * @return The new list. 259 */ 260 public default HeadTailList<T> merge( final HeadTailList<? extends T> list ) 261 { 262 @SuppressWarnings( "unchecked" ) 263 var retValue = (HeadTailList<T>) empty(); 264 final var otherIterator = requireNonNullArgument( list, "list" ) 265 .revert() 266 .iterator(); 267 final var thisIterator = revert() 268 .iterator(); 269 while( thisIterator.hasNext() && otherIterator.hasNext() ) 270 { 271 retValue = retValue.add( thisIterator.next() ) 272 .add( otherIterator.next() ); 273 } 274 275 //---* Add the remainders *-------------------------------------------- 276 while( thisIterator.hasNext() ) retValue = retValue.add( thisIterator.next() ); 277 while( otherIterator.hasNext() ) retValue = retValue.add( otherIterator.next() ); 278 279 //---* Done *---------------------------------------------------------- 280 return retValue; 281 } // merge() 282 283 /** 284 * Returns a new list where this list is appended to the end of the given 285 * list. 286 * 287 * @param list The list to prepend. 288 * @return The new list. 289 */ 290 public default HeadTailList<T> prepend( final HeadTailList<T> list ) 291 { 292 final var arg = requireNonNullArgument( list, "list" ); 293 var retValue = this; 294 for( final var e : arg.revert() ) retValue = retValue.add( e ); 295 296 //---* Done *---------------------------------------------------------- 297 return retValue; 298 } // prepend() 299 300 /** 301 * Returns a new list where the entries of the given list are placed 302 * before the first entry of this list. 303 * 304 * @param list The list to prepend. 305 * @return The new list. 306 */ 307 public default HeadTailList<T> prepend( final Collection<T> list ) 308 { 309 var retValue = this; 310 if( !requireNonNullArgument( list, "list" ).isEmpty() ) 311 { 312 final var temporaryList = new ArrayList<>( list ); 313 reverse( temporaryList ); 314 for( final var e : temporaryList ) retValue = retValue.add( e ); 315 } 316 317 //---* Done *---------------------------------------------------------- 318 return retValue; 319 } // prepend() 320 321 /** 322 * Returns a copy of this list that does not contain the given element. 323 * 324 * @param element The element to be removed. 325 * @return The copy of the list. 326 */ 327 public default HeadTailList<T> remove( final T element ) 328 { 329 var retValue = this; 330 if( nonNull( element ) ) 331 { 332 retValue = empty(); 333 for( final var e : revert() ) 334 { 335 if( !e.equals( element ) ) retValue = retValue.add( e ); 336 } 337 } 338 339 //---* Done *---------------------------------------------------------- 340 return retValue; 341 } // remove() 342 343 /** 344 * Returns a new copy of this list where the head element is replaced by 345 * the given element. 346 * 347 * @param newHead The element that is the new head for the list. 348 * @return The copy with the new head. 349 */ 350 public default HeadTailList<T> replaceHead( final T newHead ) 351 { 352 final var retValue = tail().add( requireNonNullArgument( newHead, "newHead" ) ); 353 354 //---* Done *---------------------------------------------------------- 355 return retValue; 356 } // replaceHead() 357 358 /** 359 * Revert the list; that means that the sequence of the elements in the 360 * new list is in reverse order that in this one. 361 * 362 * @return The new list with the reverted order of the elements. 363 */ 364 public default HeadTailList<T> revert() 365 { 366 @SuppressWarnings( "unchecked" ) 367 var retValue = (HeadTailList<T>) empty(); 368 for( final var e : this ) retValue = retValue.add( e ); 369 370 //---* Done *---------------------------------------------------------- 371 return retValue; 372 } // revert() 373 374 /** 375 * Returns the size of the list. 376 * 377 * @return The size of the list. 378 */ 379 public int size(); 380 381 /** 382 * Returns a 383 * {@link Stream} 384 * that is backed by this list. 385 * 386 * @return The stream. 387 */ 388 public Stream<T> stream(); 389 390 /** 391 * Returns the tail of the list. 392 * 393 * @return The tail list. 394 */ 395 public HeadTailList<T> tail(); 396 397 /** 398 * Returns the contents of this list as an array. 399 * 400 * @return The array. 401 */ 402 public Object [] toArray(); 403 404 /** 405 * <p>{@summary Returns the contents of this list in the provided 406 * array.}</p> 407 * <p>If the provided array is larger that the number of elements on the 408 * stack, the exceeding entries on that array remained unchanged.</p> 409 * 410 * @param target The target array; if this array has an insufficient 411 * size, a new array will be created. 412 * @return An array with all entries from the list; never {@code null}. If 413 * the provided array was large enough to take all elements, it will 414 * be returned, otherwise the returned array is a new one and the 415 * provided array is unchanged. 416 */ 417 @SuppressWarnings( "MethodCanBeVariableArityMethod" ) 418 public T [] toArray( final T [] target ); 419 420 /** 421 * <p>{@summary Returns the contents of this list in array that is 422 * provided by the given supplier.}</p> 423 * <p>If the provided array is larger that the number of elements on the 424 * stack, the exceeding entries on that array remained unchanged.</p> 425 * <p>If the array is too small, a new array will be created.</p> 426 * 427 * @param supplier The supplier for the target array. 428 * @return An array with all entries on the stack; never {@code null}. If 429 * the provided array was large enough to take all elements, it will 430 * be returned, otherwise the returned array is a new one and the 431 * provided array is unchanged. 432 */ 433 public default T [] toArray( final IntFunction<T []> supplier ) 434 { 435 return toArray( supplier.apply( size() ) ); 436 } // toArray() 437} 438// interface HeadTailList 439 440/* 441 * End of File 442 */