GlueGen v2.6.0-rc-20250712
GlueGen, Native Binding Generator for Java™ (public API).
ArrayHashSet.java
Go to the documentation of this file.
1/**
2 * Copyright 2010 JogAmp Community. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without modification, are
5 * permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice, this list of
8 * conditions and the following disclaimer.
9 *
10 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
11 * of conditions and the following disclaimer in the documentation and/or other materials
12 * provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
15 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
16 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
19 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
20 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
21 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 *
24 * The views and conclusions contained in the software and documentation are those of the
25 * authors and should not be interpreted as representing official policies, either expressed
26 * or implied, of JogAmp Community.
27 */
28
29package com.jogamp.common.util;
30
31import java.util.ArrayList;
32import java.util.Collection;
33import java.util.HashMap;
34import java.util.Iterator;
35import java.util.List;
36import java.util.ListIterator;
37
38/**
39 * Hashed ArrayList implementation of the List and Collection interface.
40 *
41 * Implementation properties are:
42 * <ul>
43 * <li> Unique elements utilizing {@link java.lang.Object#hashCode()} for O(1) operations, see below.</li>
44 * <li> Provides {@link java.util.List} functionality,
45 * ie {@link java.util.List#indexOf(java.lang.Object)}
46 * and {@link java.util.List#get(int)}, hence object identity can be implemented.</li>
47 * <li> Object identity via {@link #get(java.lang.Object)}</li>
48 * <li> Java 1.5 compatible</li>
49 * </ul>
50 *
51 * O(1) operations:
52 * <ul>
53 * <li> adding new element(s) </li>
54 * <li> test for containment </li>
55 * <li> identity </li>
56 * <li> trying to remove non existent elements </li>
57 * </ul>
58 *
59 * O(n) operations:
60 * <ul>
61 * <li> removing existing elements</li>
62 * </ul>
63 *
64 * For thread safety, the application shall decorate access to instances via
65 * {@link com.jogamp.common.util.locks.RecursiveLock}.
66 *
67*/
68public class ArrayHashSet<E>
69 implements Cloneable, Collection<E>, List<E>
70{
71 /**
72 * Default load factor: {@value}
73 */
74 public static final float DEFAULT_LOAD_FACTOR = 0.75f;
75 /**
76 * The default initial capacity: {@value}
77 */
78 public static final int DEFAULT_INITIAL_CAPACITY = 16;
79
80 private final HashMap<E,E> map; // object -> object
81 private final ArrayList<E> data; // list of objects
82 private final boolean supportNullValue;
83
84 /**
85 *
86 * @param supportNullValue Use {@code true} for default behavior, i.e. {@code null} can be a valid value.
87 * Use {@code false} if {@code null} is not a valid value,
88 * here {@link #remove(E)} and {@link #getOrAdd(Object)} will be optimized.
89 * @param initialCapacity use {@link #DEFAULT_INITIAL_CAPACITY} for default
90 * @param loadFactor use {@link #DEFAULT_LOAD_FACTOR} for default
91 * @see #supportsNullValue()
92 */
93 public ArrayHashSet(final boolean supportNullValue, final int initialCapacity, final float loadFactor) {
94 this.map = new HashMap<E,E>(initialCapacity, loadFactor);
95 this.data = new ArrayList<E>(initialCapacity);
96 this.supportNullValue = supportNullValue;
97 }
98
99 /**
100 * @return a shallow copy of this ArrayHashSet, elements are not copied.
101 */
103 map = new HashMap<E, E>(o.map);
104 data = new ArrayList<E>(o.data);
105 supportNullValue = o.supportNullValue;
106 }
107
108 /**
109 * Returns {@code true} for default behavior, i.e. {@code null} can be a valid value.
110 * <p>
111 * Returns {@code false} if {@code null} is not a valid value,
112 * here {@link #remove(E)} and {@link #getOrAdd(Object)} are optimized operations.
113 * </p>
114 * @see #ArrayHashSet(boolean, int, float)
115 */
116 public final boolean supportsNullValue() { return supportNullValue; }
117
118 //
119 // Cloneable
120 //
121
122 /**
123 * @return a shallow copy of this ArrayHashSet, elements are not copied.
124 */
125 @Override
126 public final Object clone() {
127 return new ArrayHashSet<E>(this);
128 }
129
130 /** Returns this object ordered ArrayList. Use w/ care, it's not a copy. */
131 public final ArrayList<E> getData() { return data; }
132 /** Returns this object hash map. Use w/ care, it's not a copy. */
133 public final HashMap<E,E> getMap() { return map; }
134
135 @Override
136 public final String toString() { return data.toString(); }
137
138 //
139 // Collection
140 //
141
142 @Override
143 public final void clear() {
144 data.clear();
145 map.clear();
146 }
147
148 /**
149 * Add element at the end of this list, if it is not contained yet.
150 * <br>
151 * This is an O(1) operation
152 * <p>
153 * {@inheritDoc}
154 * </p>
155 *
156 * @return true if the element was added to this list,
157 * otherwise false (already contained).
158 * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false}
159 */
160 @Override
161 public final boolean add(final E element) throws NullPointerException {
162 if( !supportNullValue ) {
163 checkNull(element);
164 }
165 if( !map.containsKey(element) ) {
166 // !exists
167 if(null != map.put(element, element)) {
168 // slips a valid null ..
169 throw new InternalError("Already existing, but checked before: "+element);
170 }
171 if(!data.add(element)) {
172 throw new InternalError("Couldn't add element: "+element);
173 }
174 return true;
175 }
176 return false;
177 }
178
179 /**
180 * Remove element from this list.
181 * <br>
182 * This is an O(1) operation, in case the element does not exist,
183 * otherwise O(n).
184 * <p>
185 * {@inheritDoc}
186 * </p>
187 *
188 * @return true if the element was removed from this list,
189 * otherwise false (not contained).
190 * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false}
191 */
192 @Override
193 public final boolean remove(final Object element) throws NullPointerException {
194 if( supportNullValue ) {
195 if( map.containsKey(element) ) {
196 // exists
197 map.remove(element);
198 if ( !data.remove(element) ) {
199 throw new InternalError("Couldn't remove prev mapped element: "+element);
200 }
201 return true;
202 }
203 } else {
204 checkNull(element);
205 if ( null != map.remove(element) ) {
206 // exists
207 if ( !data.remove(element) ) {
208 throw new InternalError("Couldn't remove prev mapped element: "+element);
209 }
210 return true;
211 }
212 }
213 return false;
214 }
215
216 /**
217 * Add all elements of given {@link java.util.Collection} at the end of this list.
218 * <br>
219 * This is an O(n) operation, over the given Collection size.
220 * <p>
221 * {@inheritDoc}
222 * </p>
223 *
224 * @return true if at least one element was added to this list,
225 * otherwise false (completely container).
226 */
227 @Override
228 public final boolean addAll(final Collection<? extends E> c) {
229 boolean mod = false;
230 for (final E o : c) {
231 mod |= add(o);
232 }
233 return mod;
234 }
235
236 /**
237 * Test for containment
238 * <br>
239 * This is an O(1) operation.
240 * <p>
241 * {@inheritDoc}
242 * </p>
243 *
244 * @return true if the given element is contained by this list using fast hash map,
245 * otherwise false.
246 */
247 @Override
248 public final boolean contains(final Object element) {
249 return map.containsKey(element);
250 }
251
252 /**
253 * Test for containment of given {@link java.util.Collection}
254 * <br>
255 * This is an O(n) operation, over the given Collection size.
256 * <p>
257 * {@inheritDoc}
258 * </p>
259 *
260 * @return true if the given Collection is completly contained by this list using hash map,
261 * otherwise false.
262 */
263 @Override
264 public final boolean containsAll(final Collection<?> c) {
265 for (final Object o : c) {
266 if (!this.contains(o)) {
267 return false;
268 }
269 }
270 return true;
271 }
272
273 /**
274 * Remove all elements of given {@link java.util.Collection} from this list.
275 * <br>
276 * This is an O(n) operation.
277 * <p>
278 * {@inheritDoc}
279 * </p>
280 *
281 * @return true if at least one element of this list was removed,
282 * otherwise false.
283 */
284 @Override
285 public final boolean removeAll(final Collection<?> c) {
286 boolean mod = false;
287 for (final Object o : c) {
288 mod |= this.remove(o);
289 }
290 return mod;
291 }
292
293 /**
294 * Retain all elements of the given {@link java.util.Collection} c, ie
295 * remove all elements not contained by the given {@link java.util.Collection} c.
296 * <br>
297 * This is an O(n) operation.
298 * <p>
299 * {@inheritDoc}
300 * </p>
301 *
302 * @return true if at least one element of this list was removed,
303 * otherwise false.
304 */
305 @Override
306 public final boolean retainAll(final Collection<?> c) {
307 boolean mod = false;
308 for (final Object o : c) {
309 if (!c.contains(o)) {
310 mod |= this.remove(o);
311 }
312 }
313 return mod;
314 }
315
316 /**
317 * This is an O(n) operation.
318 * <p>
319 * {@inheritDoc}
320 * </p>
321 *
322 * @return true if arrayHashSet is of type ArrayHashSet and all entries are equal
323 * Performance: arrayHashSet(1)
324 */
325 @Override
326 public final boolean equals(final Object arrayHashSet) {
327 if ( !(arrayHashSet instanceof ArrayHashSet) ) {
328 return false;
329 }
330 return data.equals(((ArrayHashSet<?>)arrayHashSet).data);
331 }
332
333 /**
334 * This is an O(n) operation over the size of this list.
335 * <p>
336 * {@inheritDoc}
337 * </p>
338 *
339 * @return the hash code of this list as define in {@link java.util.List#hashCode()},
340 * ie hashing all elements of this list.
341 */
342 @Override
343 public final int hashCode() {
344 return data.hashCode();
345 }
346
347 @Override
348 public final boolean isEmpty() {
349 return data.isEmpty();
350 }
351
352 @Override
353 public final Iterator<E> iterator() {
354 return data.iterator();
355 }
356
357 @Override
358 public final int size() {
359 return data.size();
360 }
361
362 @Override
363 public final Object[] toArray() {
364 return data.toArray();
365 }
366
367 @Override
368 public final <T> T[] toArray(final T[] a) {
369 return data.toArray(a);
370 }
371
372 //
373 // List
374 //
375
376 @Override
377 public final E get(final int index) {
378 return data.get(index);
379 }
380
381 @Override
382 public final int indexOf(final Object element) {
383 return data.indexOf(element);
384 }
385
386 /**
387 * Add element at the given index in this list, if it is not contained yet.
388 * <br>
389 * This is an O(1) operation
390 * <p>
391 * {@inheritDoc}
392 * </p>
393 *
394 * @throws IllegalArgumentException if the given element was already contained
395 * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false}
396 */
397 @Override
398 public final void add(final int index, final E element) throws IllegalArgumentException, NullPointerException {
399 if( !supportNullValue ) {
400 checkNull(element);
401 }
402 if ( map.containsKey(element) ) {
403 throw new IllegalArgumentException("Element "+element+" is already contained");
404 }
405 if(null != map.put(element, element)) {
406 // slips a valid null ..
407 throw new InternalError("Already existing, but checked before: "+element);
408 }
409 // !exists
410 data.add(index, element);
411 }
412
413 /**
414 * <p>
415 * {@inheritDoc}
416 * </p>
417 * @throws UnsupportedOperationException
418 */
419 @Override
420 public final boolean addAll(final int index, final Collection<? extends E> c) throws UnsupportedOperationException {
421 throw new UnsupportedOperationException("Not supported yet.");
422 }
423
424 /**
425 * <p>
426 * {@inheritDoc}
427 * </p>
428 */
429 @Override
430 public final E set(final int index, final E element) {
431 final E old = remove(index);
432 if(null!=old) {
433 add(index, element);
434 }
435 return old;
436 }
437
438 /**
439 * Remove element at given index from this list.
440 * <br>
441 * This is an O(n) operation.
442 * <p>
443 * {@inheritDoc}
444 * </p>
445 *
446 * @return the removed object
447 */
448 @Override
449 public final E remove(final int index) {
450 final E o = get(index);
451 if( null!=o && remove(o) ) {
452 return o;
453 }
454 return null;
455 }
456
457 /**
458 * Since this list is unique, equivalent to {@link #indexOf(java.lang.Object)}.
459 * <br>
460 * This is an O(n) operation.
461 * <p>
462 * {@inheritDoc}
463 * </p>
464 *
465 * @return index of element, or -1 if not found
466 */
467 @Override
468 public final int lastIndexOf(final Object o) {
469 return indexOf(o);
470 }
471
472 @Override
473 public final ListIterator<E> listIterator() {
474 return data.listIterator();
475 }
476
477 @Override
478 public final ListIterator<E> listIterator(final int index) {
479 return data.listIterator(index);
480 }
481
482 @Override
483 public final List<E> subList(final int fromIndex, final int toIndex) {
484 return data.subList(fromIndex, toIndex);
485 }
486
487 //
488 // ArrayHashSet
489 //
490
491 /**
492 * @return a shallow copy of this ArrayHashSet's ArrayList, elements are not copied.
493 */
494 public final ArrayList<E> toArrayList() {
495 return new ArrayList<E>(data);
496 }
497
498 /**
499 * Identity method allowing to get the identical object, using the internal hash map.
500 * <br>
501 * This is an O(1) operation.
502 *
503 * @param element hash source to find the identical Object within this list
504 * @return object from this list, identical to the given <code>key</code> hash code,
505 * or null if not contained
506 */
507 public final E get(final Object element) {
508 return map.get(element);
509 }
510
511 /**
512 * Identity method allowing to get the identical object, using the internal hash map.<br>
513 * If the <code>element</code> is not yet contained, add it.
514 * <br>
515 * This is an O(1) operation.
516 *
517 * @param element hash source to find the identical Object within this list
518 * @return object from this list, identical to the given <code>key</code> hash code,
519 * or add the given <code>key</code> and return it.
520 * @throws NullPointerException if {@code element} is {@code null} but {@link #supportsNullValue()} == {@code false}
521 */
522 public final E getOrAdd(final E element) throws NullPointerException {
523 if( supportNullValue ) {
524 if( map.containsKey(element) ) {
525 // existent
526 return map.get(element);
527 }
528 } else {
529 checkNull(element);
530 final E identity = map.get(element);
531 if(null != identity) {
532 // existent
533 return identity;
534 }
535 }
536 // !existent
537 if(!this.add(element)) {
538 throw new InternalError("Element not mapped, but contained in list: "+element);
539 }
540 return element;
541 }
542
543 /**
544 * Test for containment
545 * <br>
546 * This is an O(n) operation, using equals operation over the list.
547 * <br>
548 * You may utilize this method to verify your hash values,<br>
549 * ie {@link #contains(java.lang.Object)} and {@link #containsSafe(java.lang.Object)}
550 * shall have the same result.<br>
551 *
552 * @return true if the given element is contained by this list using slow equals operation,
553 * otherwise false.
554 */
555 public final boolean containsSafe(final Object element) {
556 return data.contains(element);
557 }
558
559 private static final void checkNull(final Object element) throws NullPointerException {
560 if( null == element ) {
561 throw new NullPointerException("Null element not supported");
562 }
563 }
564}
Hashed ArrayList implementation of the List and Collection interface.
final ArrayList< E > getData()
Returns this object ordered ArrayList.
final E getOrAdd(final E element)
Identity method allowing to get the identical object, using the internal hash map.
final int lastIndexOf(final Object o)
Since this list is unique, equivalent to indexOf(java.lang.Object).
final< T > T[] toArray(final T[] a)
final boolean addAll(final int index, final Collection<? extends E > c)
final boolean containsAll(final Collection<?> c)
Test for containment of given java.util.Collection This is an O(n) operation, over the given Collec...
final boolean contains(final Object element)
Test for containment This is an O(1) operation.
final ListIterator< E > listIterator()
ArrayHashSet(final ArrayHashSet< E > o)
final boolean equals(final Object arrayHashSet)
This is an O(n) operation.
final ArrayList< E > toArrayList()
final HashMap< E, E > getMap()
Returns this object hash map.
final List< E > subList(final int fromIndex, final int toIndex)
static final float DEFAULT_LOAD_FACTOR
Default load factor: {@value}.
final boolean supportsNullValue()
Returns true for default behavior, i.e.
final boolean containsSafe(final Object element)
Test for containment This is an O(n) operation, using equals operation over the list.
final int indexOf(final Object element)
final void add(final int index, final E element)
Add element at the given index in this list, if it is not contained yet.
final ListIterator< E > listIterator(final int index)
final boolean addAll(final Collection<? extends E > c)
Add all elements of given java.util.Collection at the end of this list.
final int hashCode()
This is an O(n) operation over the size of this list.
final boolean retainAll(final Collection<?> c)
Retain all elements of the given java.util.Collection c, ie remove all elements not contained by the ...
final boolean add(final E element)
Add element at the end of this list, if it is not contained yet.
ArrayHashSet(final boolean supportNullValue, final int initialCapacity, final float loadFactor)
final boolean removeAll(final Collection<?> c)
Remove all elements of given java.util.Collection from this list.
static final int DEFAULT_INITIAL_CAPACITY
The default initial capacity: {@value}.