001/* 002 * ============================================================================ 003 * Copyright © 2002-2020 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 org.apiguardian.api.API.Status.STABLE; 022import static org.tquadrat.foundation.lang.Objects.isNull; 023import static org.tquadrat.foundation.lang.Objects.nonNull; 024import static org.tquadrat.foundation.lang.Objects.requireNonNullArgument; 025 026import java.lang.reflect.Array; 027import java.util.Optional; 028import java.util.concurrent.locks.ReentrantReadWriteLock; 029import java.util.function.IntFunction; 030 031import org.apiguardian.api.API; 032import org.tquadrat.foundation.annotation.ClassVersion; 033import org.tquadrat.foundation.exception.ValidationException; 034import org.tquadrat.foundation.lang.AutoLock; 035 036/** 037 * <p>{@summary A stand-alone implementation for stack, without the ballast 038 * from the Collections framework.}</p> 039 * <p>This implementation is not synchronised, but thread-safe.</p> 040 * 041 * @extauthor Thomas Thrien - thomas.thrien@tquadrat.org 042 * @version $Id: Stack.java 1061 2023-09-25 16:32:43Z tquadrat $ 043 * @since 0.0.5 044 * 045 * @param <T> The type for the stack entries. 046 * 047 * @UMLGraph.link 048 * 049 * @see java.util.Stack 050 */ 051@SuppressWarnings( "NewClassNamingConvention" ) 052@ClassVersion( sourceVersion = "$Id: Stack.java 1061 2023-09-25 16:32:43Z tquadrat $" ) 053@API( status = STABLE, since = "0.0.5" ) 054public final class Stack<T> 055{ 056 /*---------------*\ 057 ====** Inner Classes **==================================================== 058 \*---------------*/ 059 /** 060 * The stack entries. 061 * 062 * @note This class cannot be changed to a {@code record} (instead of 063 * being a {@code class}) because a {@code record} as an inner class 064 * is implicitly static, and that collides with the type argument 065 * {@code <T>} that is inherited from the surrounding class. 066 * 067 * @extauthor Thomas Thrien - thomas.thrien@tquadrat.org 068 * @version $Id: Stack.java 1061 2023-09-25 16:32:43Z tquadrat $ 069 * @since 0.0.5 070 * 071 * @UMLGraph.link 072 */ 073 @ClassVersion( sourceVersion = "$Id: Stack.java 1061 2023-09-25 16:32:43Z tquadrat $" ) 074 @API( status = STABLE, since = "0.0.5" ) 075 private final class Entry 076 { 077 /*------------*\ 078 ====** Attributes **=================================================== 079 \*------------*/ 080 /** 081 * The current head element. 082 */ 083 private final T m_Head; 084 085 /** 086 * The remaining elements. 087 */ 088 @SuppressWarnings( "UseOfConcreteClass" ) 089 private final Entry m_Tail; 090 091 /*--------------*\ 092 ====** Constructors **================================================= 093 \*--------------*/ 094 /** 095 * Creates a new {@code Stack} object. 096 * 097 * @param head The current head. 098 * @param tail The current tail; may be {@code null}, indicating 099 * an empty tail. 100 */ 101 @SuppressWarnings( "UseOfConcreteClass" ) 102 public Entry( final T head, final Entry tail ) 103 { 104 m_Head = head; 105 m_Tail = tail; 106 } // Entry() 107 108 /*---------*\ 109 ====** Methods **====================================================== 110 \*---------*/ 111 /** 112 * Returns the current head. 113 * 114 * @return The head. 115 */ 116 public final T head() { return m_Head; } 117 118 /** 119 * Returns the current tail. 120 * 121 * @return The tail. 122 */ 123 @SuppressWarnings( "ReturnOfInnerClass" ) 124 public final Entry tail() { return m_Tail; } 125 } 126 // class Entry 127 128 /*-----------*\ 129 ====** Constants **======================================================== 130 \*-----------*/ 131 /** 132 * An empty array of {@code Stack} objects. 133 */ 134 @SuppressWarnings( "rawtypes" ) 135 public static final Stack [] EMPTY_Stack_ARRAY = new Stack [0]; 136 137 /*------------*\ 138 ====** Attributes **======================================================= 139 \*------------*/ 140 /** 141 * The number of entries on the stack. 142 */ 143 private int m_Count = 0; 144 145 /** 146 * The entries. 147 */ 148 @SuppressWarnings( "UseOfConcreteClass" ) 149 private Entry m_Entries = null; 150 151 /** 152 * The "read" lock. 153 */ 154 private final AutoLock m_ReadLock; 155 156 /** 157 * The "write" lock. 158 */ 159 private final AutoLock m_WriteLock; 160 161 /*--------------*\ 162 ====** Constructors **===================================================== 163 \*--------------*/ 164 /** 165 * Creates a new {@code Stack} object. 166 */ 167 public Stack() 168 { 169 final var lock = new ReentrantReadWriteLock( false ); 170 m_ReadLock = AutoLock.of( lock.readLock() ); 171 m_WriteLock = AutoLock.of( lock.writeLock() ); 172 } // Stack() 173 174 /*---------*\ 175 ====** Methods **========================================================== 176 \*---------*/ 177 /** 178 * Empties the whole stack in one go. 179 */ 180 public final void clear() 181 { 182 m_WriteLock.execute( () -> 183 { 184 m_Entries = null; 185 m_Count = 0; 186 } ); 187 } // clear() 188 189 /** 190 * <p>{@summary Tests if the stack is not empty.}</p> 191 * <p>If concurrent threads will access the stack, it is still possible 192 * that this method will return {@code true}, but a call to 193 * {@link #pop()} 194 * immediately after returns {@code null}.</p> 195 * 196 * @return {@code true} if there are still entries on the stack, 197 * {@code false} otherwise. 198 * 199 * @see #isEmpty() 200 */ 201 public final boolean hasMore() { return !isEmpty(); } 202 203 /** 204 * <p>{@summary Tests if the stack is empty.}</p> 205 * <p>If concurrent threads will access the stack, it is still possible 206 * that this method will return {@code false}, but a call to 207 * {@link #pop()} 208 * immediately after returns {@code null}.</p> 209 * 210 * @return {@code true} if there are no entries on the stack, 211 * {@code false} otherwise. 212 * 213 * @see #hasMore() 214 */ 215 public final boolean isEmpty() 216 { 217 var retValue = false; 218 try( final var ignore = m_ReadLock.lock() ) 219 { 220 retValue = isNull( m_Entries ); 221 } 222 223 //---* Done *---------------------------------------------------------- 224 return retValue; 225 } // isEmpty() 226 227 /** 228 * <p>{@summary Returns the first entry from the stack <i>without</i> 229 * removing it from the stack.}</p> 230 * <p>If concurrent threads will access the stack, it is still possible 231 * that this method will return a different value than a consecutive call 232 * to 233 * {@link #pop()}.</p> 234 * 235 * @return An instance of 236 * {@link Optional} 237 * that holds the first entry; it will be empty if the stack is empty. 238 */ 239 public final Optional<T> peek() 240 { 241 final var retValue = m_ReadLock.execute( () -> nonNull( m_Entries ) ? m_Entries.head() : null ); 242 243 //---* Done *---------------------------------------------------------- 244 return retValue; 245 } // peek() 246 247 /** 248 * Returns the first entry from the stack and removes it. 249 * 250 * @return An instance of 251 * {@link Optional} 252 * that holds the first entry; it will be empty if the stack is empty. 253 */ 254 public final Optional<T> pop() 255 { 256 Optional<T> retValue = Optional.empty(); 257 try( final var ignore = m_WriteLock.lock() ) 258 { 259 if( nonNull( m_Entries ) ) 260 { 261 retValue = Optional.of( m_Entries.head() ); 262 m_Entries = m_Entries.tail(); 263 --m_Count; 264 } 265 } 266 267 //---* Done *---------------------------------------------------------- 268 return retValue; 269 } // pop() 270 271 /** 272 * Add the given entry to the stack. 273 * 274 * @param entry The value to add. 275 */ 276 public final void push( final T entry ) 277 { 278 requireNonNullArgument( entry, "entry" ); 279 m_WriteLock.execute( () -> 280 { 281 m_Entries = new Entry( entry, m_Entries ); 282 ++m_Count; 283 } ); 284 } // push() 285 286 /** 287 * <p>{@summary Adds the given entries to the stack, in LIFO order.} 288 * Nothing happens, if the provided array is empty.</p> 289 * <p>The provided array may not contain {@code null} elements.</p> 290 * <p>If the push failed for anyone element of the array, the stack 291 * remained unchanged.</p> 292 * <p>The method guarantees that the elements of the array are stored to 293 * the stack in consecutive order, even in a multithreaded 294 * environment.</p> 295 * 296 * @param entries The values to add. 297 * @throws IllegalArgumentException At least one element of the 298 * provided array is {@code null}. 299 */ 300 @SafeVarargs 301 public final void push( final T... entries ) throws IllegalArgumentException 302 { 303 for( var i = 0; i < requireNonNullArgument( entries, "entries" ).length; ++i ) 304 { 305 if( isNull( entries [i] ) ) throw new ValidationException( "The entry %1$d of the arguments list is null".formatted( i ) ); 306 } 307 308 m_WriteLock.execute( () -> 309 { 310 for( final var entry : entries ) 311 { 312 m_Entries = new Entry( entry, m_Entries ); 313 ++m_Count; 314 } 315 } ); 316 } // push() 317 318 /** 319 * Returns the number of entries on the stack. 320 * 321 * @return The number of entries. 322 */ 323 public final int size() { return m_Count; } 324 325 /** 326 * <p>{@summary Returns all entries that are currently on the stack as an 327 * array without removing them, with the top most entry as the first.} 328 * Therefore, this is more or less a 329 * {@link #peek()} 330 * on the whole stack.</p> 331 * <p>If the provided array is larger that the number of elements on the 332 * stack, the exceeding entries on that array remained unchanged.</p> 333 * 334 * @param target The target array; if this array has an insufficient 335 * size, a new array will be created. 336 * @return An array with all entries on the stack; never {@code null}. If 337 * the provided array was large enough to take all elements, it will 338 * be returned, otherwise the returned array is a new one and the 339 * provided array is unchanged. 340 */ 341 @SuppressWarnings( {"unchecked", "MethodCanBeVariableArityMethod"} ) 342 public final T [] toArray( final T [] target ) 343 { 344 requireNonNullArgument( target, "target" ); 345 346 @SuppressWarnings( {"OptionalGetWithoutIsPresent", "OverlyLongLambda"} ) 347 final var retValue = m_ReadLock.execute( () -> 348 { 349 final var result = target.length >= m_Count ? target : (T []) Array.newInstance( target.getClass().getComponentType(), m_Count ); 350 var index = 0; 351 var entries = m_Entries; 352 while( nonNull( entries ) ) 353 { 354 result [index++] = entries.head(); 355 entries = entries.tail(); 356 } 357 return result; 358 } ).get(); 359 360 //---* Done *---------------------------------------------------------- 361 return retValue; 362 } // toArray() 363 364 /** 365 * <p>{@summary Returns all entries that are currently on the stack as an 366 * array without removing them, with the top most entry as the first.} 367 * Therefore, this is more or less a 368 * {@link #peek()} 369 * on the whole stack.</p> 370 * 371 * @param supplier The supplier for the target array. 372 * @return An array with all entries on the stack; never {@code null}. 373 */ 374 public final T [] toArray( final IntFunction<T []> supplier ) 375 { 376 @SuppressWarnings( "OptionalGetWithoutIsPresent" ) 377 final var retValue = m_ReadLock.execute( () -> toArray( requireNonNullArgument( supplier, "supplier" ).apply( m_Count ) ) ) 378 .get(); 379 380 //---* Done *---------------------------------------------------------- 381 return retValue; 382 } // toArray() 383} 384// class Stack 385 386/* 387 * End of File 388 */