Custom collections
The skeleton classes implement most of a collection interface on top of a few primitive methods. Implement the
primitives and you inherit contains, indexOf, subList, equals/hashCode/toString, bulk operations, stream(),
spliterator(), for..of, sequenced methods such as getFirst/reversed, and fail-fast iteration. The result works
anywhere a library collection does: in Collections.*, as a copy-constructor argument, in equals against built-in
collections, and as a stream source.
AbstractCollection iterator(), size()├── AbstractList + get(i) (has modCount)│ └── AbstractSequentialList + listIterator(i)├── AbstractQueue + offer(e), poll(), peek()└── AbstractSetAbstractMap entrySet() (separate root: a map is not a collection)What each skeleton requires
Section titled “What each skeleton requires”Mutators (add, set, put, …) default to throwing UnsupportedOperationException; override them to make the
collection modifiable.
| Skeleton | Read-only: implement | Modifiable: also override | Gives you |
|---|---|---|---|
AbstractCollection<E> |
iterator(), size() |
add(e); an iterator whose remove() works |
the whole Collection interface, stream(), for..of |
AbstractList<E> |
get(i), size() |
set(i, e); to grow or shrink, addAtIndex(i, e) and removeAt(i) that bump modCount |
List + SequencedCollection: iterators, subList, reversed(), sort, value equals/hashCode |
AbstractSequentialList<E> |
listIterator(index), size() |
a list iterator with set/add/remove and its own modCount tracking |
positional get/set/add/removeAt built on the list iterator |
AbstractQueue<E> |
offer, poll, peek, iterator(), size() |
nothing more | add (throws IllegalStateException when offer refuses), remove(), element(), clear, addAll |
AbstractSet<E> |
iterator(), size() |
add(e); an iterator with remove() |
set equals/hashCode, a fast removeAll, a DISTINCT (or SORTED) spliterator |
AbstractMap<K, V> |
entrySet() |
put(k, v); an entry-set iterator with remove() |
the whole Map interface, keySet()/values() views, compute*, merge |
The defaults are correct but generic: AbstractCollection.contains is a linear scan and AbstractMap.get walks
entrySet(). Override what your storage does faster (contains, size, and findEntry on a map).
AbstractQueue assumes the queue rejects null, because poll() and peek() return null for “empty”.
AbstractMap also exports SimpleEntry (mutable) and SimpleImmutableEntry (setValue throws) for building entry sets.
Contracts to keep
Section titled “Contracts to keep”modCount
Section titled “modCount”Every iterator, subList view and spliterator of an AbstractList records modCount and throws
ConcurrentModificationException when it changes underneath them. Increment it once per structural change.
| Operation | Bump modCount? |
|---|---|
addAtIndex, removeAt, clear, an eviction |
yes, once per call |
set(i, e), and sort (which uses set) |
no |
| a failed operation that changed nothing | no |
The iterator’s own remove()/add() go through removeAt/addAtIndex and then adopt the new count, so they keep
working. AbstractCollection, AbstractSet and AbstractMap have no modCount: their iterators are whatever you
return. Delegate to a library collection’s iterator to inherit fail-fast behaviour, or keep a counter yourself.
Override addAtIndex, not add
Section titled “Override addAtIndex, not add”List.add(e) appends and add(index, e) inserts. AbstractList.add tells them apart by argument count and routes both
to one protected hook, as do the other insert paths:
add(e) → addAtIndex(size(), e); return trueadd(index, e) → addAtIndex(index, e)addAll(c) → addAllAt(size(), c)addAll(index, c) → addAllAt(index, c)addFirst / addLast, listIterator().add, subList(...).add → addAtIndexOverriding only add(e) would turn add(0, x) into a wrong append and miss inserts through views and iterators.
addAllAt defaults to a loop of addAtIndex; override it if your storage can insert a batch at once. Validate indices
with Objects.checkIndex (for get/set/removeAt) and 0 <= index <= size() (for addAtIndex), throwing
IndexOutOfBoundsException.
The RANDOM_ACCESS brand
Section titled “The RANDOM_ACCESS brand”Add get [RANDOM_ACCESS](): true (and implements RandomAccess) when get(i) is O(1); AbstractList does not add it.
With the brand, Collections algorithms use indexed loops, subList views report the brand too, and spliterator()
splits by index. Leave it off for linked storage, or those algorithms become O(n²).
Sorted sets
Section titled “Sorted sets”AbstractSet.spliterator() reports DISTINCT | SIZED | SUBSIZED. If the set also has comparator(), first(),
last() and headSet(), it is treated as sorted: the spliterator adds SORTED | ORDERED and getComparator() returns
your comparator() (null for natural order), so streams can skip a redundant sorted(). The check is structural:
the class need not declare implements SortedSet. For the full NavigableSet API, extending TreeSet is less work.
Example: a computed range (AbstractCollection)
Section titled “Example: a computed range (AbstractCollection)”A collection need not store its elements. IntRange uses O(1) memory and answers contains in O(1).
import { AbstractCollection, HashSet, NoSuchElementException, UnsupportedOperationException } from '@ylcnfrht/collections';import type { Iterator } from '@ylcnfrht/collections';
class IntRange extends AbstractCollection<number> { constructor(private readonly start: number, private readonly end: number, private readonly step = 1) { super(); if (!Number.isInteger(step) || step <= 0) throw new RangeError('step must be a positive integer'); } size(): number { return Math.max(0, Math.ceil((this.end - this.start) / this.step)); } iterator(): Iterator<number> { let i = 0; const n = this.size(); const { start, step } = this; return { hasNext: () => i < n, next: () => { if (i >= n) throw new NoSuchElementException(); return start + step * i++; }, remove: () => { throw new UnsupportedOperationException('read-only'); }, forEachRemaining(action) { while (i < n) action(start + step * i++); }, }; } override contains(o: unknown): boolean { return typeof o === 'number' && Number.isInteger(o) && o >= this.start && o < this.end && (o - this.start) % this.step === 0; }}
const evens = new IntRange(0, 10, 2);console.log(evens.size(), evens); // → 5 [0, 2, 4, 6, 8]console.log(evens.stream().mapToInt((x) => x * x).sum(), new HashSet(evens).contains(8)); // → 120 true
try { evens.add(12);} catch (e) { console.log((e as Error).name); // → UnsupportedOperationException}evens.removeIf((x) => x > 100); // matches nothing, so iterator().remove() is never calledremoveIf and clear work through iterator().remove(), so they throw only when they reach an element to remove. A
plain AbstractCollection uses identity equals; extend AbstractSet or AbstractList for value equality.
Example: a ring list (AbstractList)
Section titled “Example: a ring list (AbstractList)”RingList keeps the last capacity elements; appending to a full list evicts the oldest. It has O(1) get, so it
carries the brand.
import { AbstractList, ConcurrentModificationException, IllegalStateException, IndexOutOfBoundsException, List, Objects, RANDOM_ACCESS } from '@ylcnfrht/collections';import type { RandomAccess } from '@ylcnfrht/collections';
class RingList<E> extends AbstractList<E> implements RandomAccess { private readonly buf: E[]; private head = 0; // physical index of element 0 private count = 0;
constructor(readonly capacity: number) { super(); if (!Number.isInteger(capacity) || capacity <= 0) throw new RangeError('capacity must be a positive integer'); this.buf = new Array<E>(capacity); } get [RANDOM_ACCESS](): true { return true; } private phys(i: number): number { return (this.head + i) % this.capacity; } size(): number { return this.count; } get(index: number): E { Objects.checkIndex(index, this.count); return this.buf[this.phys(index)]; } override set(index: number, e: E): E { Objects.checkIndex(index, this.count); const p = this.phys(index); const old = this.buf[p]; this.buf[p] = e; // not structural: no modCount++ return old; } protected override addAtIndex(index: number, e: E): void { if (!Number.isInteger(index) || index < 0 || index > this.count) { throw new IndexOutOfBoundsException(`Index: ${index}, Size: ${this.count}`); } if (this.count === this.capacity) { if (index !== this.count) throw new IllegalStateException('full: only appends evict'); this.buf[this.head] = e; // overwrite the oldest slot, which becomes the newest this.head = (this.head + 1) % this.capacity; this.modCount++; return; } for (let i = this.count; i > index; i--) this.buf[this.phys(i)] = this.buf[this.phys(i - 1)]; this.buf[this.phys(index)] = e; this.count++; this.modCount++; } override removeAt(index: number): E { Objects.checkIndex(index, this.count); const old = this.buf[this.phys(index)]; for (let i = index; i < this.count - 1; i++) this.buf[this.phys(i)] = this.buf[this.phys(i + 1)]; this.buf[this.phys(this.count - 1)] = undefined as E; // drop the reference this.count--; this.modCount++; return old; }}
const recent = new RingList<number>(3);for (let i = 1; i <= 5; i++) recent.add(i);console.log(recent, recent.equals(List.of(3, 4, 5))); // → [3, 4, 5] true
// inherited: indexOf, subList and reversed views, sort, insert by indexconsole.log(recent.indexOf(4), recent.subList(1, 3), recent.reversed()); // → 1 [4, 5] [5, 4, 3]recent.removeAt(0);recent.add(0, 9);recent.sort(null);console.log(recent); // → [4, 5, 9]
// an eviction is structural, so an open iterator failstry { for (const x of recent) if (x === 4) recent.add(7);} catch (e) { console.log(e instanceof ConcurrentModificationException); // → true}recent.removeIf((x) => x > 5); // goes through the iterator's remove(): no exceptionconsole.log(recent); // → [5]Example: a bounded queue (AbstractQueue)
Section titled “Example: a bounded queue (AbstractQueue)”offer returns false when full, and the inherited add turns that into IllegalStateException. Storage delegates to
an ArrayDeque, which supplies a fail-fast iterator with remove().
import { AbstractQueue, ArrayDeque, IllegalArgumentException, Objects } from '@ylcnfrht/collections';import type { Iterator } from '@ylcnfrht/collections';
class BoundedQueue<E> extends AbstractQueue<E> { private readonly items: ArrayDeque<E>; constructor(readonly capacity: number) { super(); if (!Number.isInteger(capacity) || capacity <= 0) throw new IllegalArgumentException(`capacity: ${capacity}`); this.items = new ArrayDeque<E>(capacity); } offer(e: E): boolean { Objects.requireNonNull(e); // null means "empty" to poll()/peek() if (this.items.size() >= this.capacity) return false; this.items.addLast(e); return true; } poll(): E | null { return this.items.pollFirst(); } peek(): E | null { return this.items.peekFirst(); } iterator(): Iterator<E> { return this.items.iterator(); } size(): number { return this.items.size(); }}
const q = new BoundedQueue<string>(2);console.log(q.offer('a'), q.offer('b'), q.offer('c')); // → true true falsetry { q.add('c');} catch (e) { console.log((e as Error).name, (e as Error).message); // → IllegalStateException Queue full}console.log(q.element(), q.remove(), q.poll(), q.poll()); // → a a b nullExample: a bidirectional map (AbstractMap)
Section titled “Example: a bidirectional map (AbstractMap)”BiMap keeps values unique and offers a live inverse() view. It overrides put (modifiable), findEntry (O(1) get,
containsKey, getOrDefault, replace), and size/clear for speed. The entry-set iterator’s remove() keeps both
directions in sync, which makes keySet().remove, values().removeIf and the inherited remove(key) correct.
import { AbstractMap, AbstractSet, IllegalArgumentException, LinkedHashMap, Map, Objects, SimpleImmutableEntry } from '@ylcnfrht/collections';import type { Iterator, MapEntry, Set } from '@ylcnfrht/collections';
class BiMap<K, V> extends AbstractMap<K, V> { constructor( private readonly fwd = new LinkedHashMap<K, V>(), private readonly bwd = new LinkedHashMap<V, K>(), ) { super(); } inverse(): BiMap<V, K> { return new BiMap<V, K>(this.bwd, this.fwd); } override size(): number { return this.fwd.size(); } protected override findEntry(key: unknown): MapEntry<K, V> | undefined { return this.fwd.containsKey(key) ? new SimpleImmutableEntry(key as K, this.fwd.get(key) as V) : undefined; } override put(key: K, value: V): V | null { if (this.bwd.containsKey(value) && !Objects.equals(this.bwd.get(value), key)) { throw new IllegalArgumentException(`value already bound: ${String(value)}`); } const old = this.fwd.put(key, value); if (old !== null) this.bwd.remove(old); this.bwd.put(value, key); return old; } override clear(): void { this.fwd.clear(); this.bwd.clear(); } entrySet(): Set<MapEntry<K, V>> { const { fwd, bwd } = this; return new (class extends AbstractSet<MapEntry<K, V>> { size(): number { return fwd.size(); } iterator(): Iterator<MapEntry<K, V>> { const it = fwd.entrySet().iterator(); let last: MapEntry<K, V> | null = null; return { hasNext: () => it.hasNext(), next: () => (last = it.next(), new SimpleImmutableEntry(last)), // a snapshot: setValue would bypass bwd remove: () => { it.remove(); // throws IllegalStateException if next() was not called bwd.remove(last!.getValue()); }, forEachRemaining(action) { while (it.hasNext()) action(this.next()); }, }; } })(); }}
const codes = new BiMap<string, number>();codes.put('ok', 200);codes.put('teapot', 418);codes.inverse().put(404, 'not found');console.log(codes, codes.inverse().get(418)); // → {ok=200, teapot=418, not found=404} teapottry { codes.put('fine', 200);} catch (e) { console.log((e as Error).name); // → IllegalArgumentException}codes.keySet().remove('ok');console.log(codes.inverse().containsKey(200), codes.equals(Map.of('teapot', 418, 'not found', 404))); // → false truereplaceAll and entry.setValue throw UnsupportedOperationException here because the entries are immutable
snapshots. To support them, return entries whose setValue also updates bwd.
Checklist
Section titled “Checklist”- Implement the abstract methods from the table; override mutators only for a modifiable collection.
- Lists: override
addAtIndex/removeAt, notadd/remove. BumpmodCounton every structural change, never inset. - Validate indices so callers get
IndexOutOfBoundsException. - Add
[RANDOM_ACCESS]only whenget(i)is O(1). - Iterators implement
hasNext,next,removeandforEachRemaining.next()past the end throwsNoSuchElementException;remove()without a precedingnext()throwsIllegalStateException. Delegating to a library iterator handles both. - Queues on
AbstractQueuerejectnull. - Element types need
equals/hashCode(andcompareTofor sorted use): see Equality.