Complexity¶
Every Zazr collection states the cost of its methods in their javadoc. This page gathers those notes, so it always matches the code.
How to read a cost¶
A cost is the worst case of one call, in big-O notation, unless its note says otherwise. The letters mean:
- n: the number of elements of the collection you call the method on.
- m: the number of elements of the argument.
- k: a count the note names, such as the elements taken or dropped.
- i and j: index arguments; a slice runs from i to j.
- size and step: the window size and the step of
slidingandgrouped.
In the tables, hover a cost to read its whole note.
Classes of cost¶
Each cost falls in one of these classes, cheapest first. The Scala column gives the abbreviation of the same class in Scala's collections documentation, for readers who know it.
| Class | Scala | Meaning | Expressions |
|---|---|---|---|
| constant | C |
the same few steps, whatever the size | O(1) |
| effectively constant | eC |
grows with the size, but so slowly that it stays a handful of steps | effectively O(1) |
| amortised constant | aC |
constant on average over a chain of calls; now and then one call costs O(n) | amortised O(1) |
| logarithmic | Log |
one walk down a balanced tree: a few dozen steps for a million elements | O(log n) |
| lazy | almost nothing now: the elements are computed when the result is read | lazy |
|
| linear | L |
proportional to the sizes in the expression | O(i), O(j), O(k), O(m), O(n), O(i + k), O(i + m), O(n + k), O(n + m), O(n / size), O(n / step), O(k + log n), O(max(n, m)), O(min(n, k)), O(min(n, m)), O(min(i, n - i)), O(min(k, n - k)), O(m + min(i, n - i)) |
| n log n | a sort, or one tree operation per element | O(m log m), O(m log n), O(n log n), O(n + k log k), O(n + k log n), O(n + m log n), O(m log(n + m)), O((n / size) log n), O((n / step) log n) |
|
| polynomial | a product of sizes: searching for a slice, sliding windows, a cartesian product | O(n^2), O(n * m), O(n^power), O(n * size), O(rows * columns), O(power * n^power), O(n + (n / step) * size), O(n + n * min(size, n - size)), O(n + (n / step) * min(size, n - size)) |
|
| combinatorial | one result per combination or permutation | O(n! * n), O(n * 2^n), O(k * C(n, k)) |
Effectively constant¶
Vector, HashSet and HashMap keep their elements in wide, shallow trees of small arrays, 32 slots each. A lookup reads one array per level: four levels hold a million elements, seven hold the largest possible collection. An update copies those few arrays and shares the rest.
This is a worst case, not an average: every call costs a handful of steps.
Amortised constant¶
An amortised cost is an average. Most calls are O(1), and now and then one call pays O(n) for the work the others skipped.
The average holds over a chain of calls, each made on the result of the previous one. A Zazr collection never changes, so you can also call the method again on an older version: each such call may pay the O(n) step again. The note of each amortised method says when that happens.
Lazy¶
A LazyList computes its elements when they are read, and keeps each one once computed. A lazy call returns a LazyList without walking this one: its note says what is computed now, and the rest is computed as you read the result.
"Now" can still be more than one element. A call that keeps only some elements, such as filter, reads until its first kept element; on an infinite LazyList where none is kept, it never returns.
Missing operations¶
n/a in a table means that the type has no such method. HashSet and HashMap have no positional methods (head, take, drop), because their order is not defined.
Sequences¶
NonEmptyVector wraps a Vector, so its costs are those of Vector. LazyList is lazy: most of its operations compute their result as it is read.
| Operation | Vector |
List |
Queue |
LazyList |
NonEmptyVector |
|---|---|---|---|---|---|
head |
O(1) | O(1) | O(1) | O(1) | O(1) |
tail |
effectively O(1) | O(1) | amortised O(1) | O(1) | effectively O(1) |
last |
O(1) | O(n) | O(n) | O(n) | O(1) |
init |
effectively O(1) | O(n) | amortised O(1) | lazy | effectively O(1) |
get |
effectively O(1) | O(i) | O(n) | O(i) | effectively O(1) |
update |
effectively O(1) | O(i) | O(n) | lazy | effectively O(1) |
prepend |
effectively O(1) | O(1) | O(1) | O(1) | effectively O(1) |
append |
effectively O(1) | O(n) | O(1) | O(1) | effectively O(1) |
prependAll |
O(m) | O(m) | O(m) | O(1) | O(m) |
appendAll |
O(m) | O(n + m) | O(m) | O(1) | O(m) |
insert |
O(min(i, n - i)) | O(i) | O(n) | lazy | O(min(i, n - i)) |
removeAt |
O(min(i, n - i)) | O(i) | O(n) | lazy | O(min(i, n - i)) |
take |
effectively O(1) | O(k) | O(n) | lazy | effectively O(1) |
drop |
effectively O(1) | O(k) | O(n) | lazy | effectively O(1) |
slice |
effectively O(1) | O(j) | O(n) | lazy | effectively O(1) |
splitAt(Predicate<? super T>) |
O(k) | O(k) | O(n) | lazy | O(k) |
splitAt(int) |
effectively O(1) | O(k) | O(n) | lazy | effectively O(1) |
reverse |
O(n) | O(n) | O(n) | O(n) | O(n) |
sorted |
O(n log n) | O(n log n) | O(n log n) | O(n log n) | O(n log n) |
size |
O(1) | O(n) | O(n) | O(n) | O(1) |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)) | O(min(n, m)) | O(min(n, m)) | O(min(n, m)) |
sizeCompare(int) |
O(1) | O(min(n, k)) | O(min(n, k)) | O(min(n, k)) | O(1) |
contains |
O(n) | O(n) | O(n) | O(n) | O(n) |
indexOf |
O(n) | O(n) | O(n) | O(n) | O(n) |
zip |
O(min(n, m)) | O(min(n, m)) | O(n) | lazy | O(min(n, m)) |
sliding(int) |
O(n) | O(n * size) | O(n * size) | lazy | O(n) |
sliding(int, int) |
O(n / step) | O(n + (n / step) * size) | O(n + (n / step) * size) | lazy | O(n / step) |
grouped |
O(n / size) | O(n) | O(n) | lazy | O(n / size) |
distinct |
O(n) | O(n) | O(n) | lazy | O(n) |
concat |
n/a | n/a | n/a | n/a | O(m) |
Sets¶
head, take and drop exist only where the order is defined: insertion order on LinkedHashSet, the comparator's order on TreeSet. NonEmptySet and NonEmptySortedSet wrap a HashSet and a TreeSet, so their costs are those of the set they wrap.
| Operation | HashSet |
LinkedHashSet |
TreeSet |
NonEmptySet |
NonEmptySortedSet |
|---|---|---|---|---|---|
contains |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
add |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
remove |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
union |
O(n + m) | O(m) | O(m log(n + m)) | O(m) | O(m log(n + m)) |
intersect |
O(m) | O(n + m) | O(n + m log n) | O(n + m) | O(n + m log n) |
diff |
O(m) | O(n + m) | O(n + m log n) | O(m) | O(n + m log n) |
min |
O(n) | O(n) | O(n) | O(n) | O(n) |
max |
O(n) | O(n) | O(n) | O(n) | O(n) |
head |
n/a | effectively O(1) | O(log n) | n/a | O(log n) |
take |
n/a | O(min(k, n - k)) | O(log n) | n/a | O(log n) |
drop |
n/a | O(min(k, n - k)) | O(log n) | n/a | O(log n) |
Maps¶
As for the sets, only the ordered maps have positional methods. NonEmptyMap and NonEmptySortedMap wrap a HashMap and a TreeMap, so their costs are those of the map they wrap.
| Operation | HashMap |
LinkedHashMap |
TreeMap |
NonEmptyMap |
NonEmptySortedMap |
|---|---|---|---|---|---|
get |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
containsKey |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
put |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
putAll |
O(n + m) | O(m) | O(m log(n + m)) | O(m) | O(m log(n + m)) |
remove |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
updateWith |
effectively O(1) | effectively O(1) | O(log n) | effectively O(1) | O(log n) |
keySet |
O(n) | O(1) | O(n) | O(n) | O(n) |
values |
O(n) | O(n) | O(n) | O(n) | O(n) |
head |
n/a | effectively O(1) | O(log n) | n/a | O(log n) |
take |
n/a | O(min(k, n - k)) | O(log n) | n/a | O(log n) |
drop |
n/a | O(min(k, n - k)) | O(log n) | n/a | O(log n) |
Every method, per type¶
Each type lists its methods that have a cost note, in the order of its source. A method inherited from an interface says so. The paragraph under each type covers its other methods.
Vector¶
The methods without a note of their own (map, filter, flatMap, the folds, groupBy, the conversions, and the factories such as ofAll and range) walk the elements once: O(n), where n is the size of the result for a factory and flatMap. containsAll is O(n * m): one contains per element of its argument.
| Method | Cost | Note |
|---|---|---|
transpose(Vector<Vector<T>>) |
O(rows * columns) | O(rows * columns); the matrix itself is returned when it has no or one element. |
unfold(S, Function<? super S, ? extends Option<? extends Tuple2<? extends A, ? extends S>>>) |
O(n) | O(n) for n elements; f runs n + 1 times now. |
flatten(Iterable<? extends Iterable<? extends T>>) |
O(m) | O(m) for m inner elements in total, each added to the result once. |
append(T) |
effectively O(1) | effectively O(1): the last array, at most 32 elements, is copied; once every 32 appends, a few arrays above it are copied too. |
appendAll(Iterable<? extends T>) |
O(m) | O(m) for m appended elements; O(min(n, m)) when iterable is a Vector: the longer side is shared and only the shorter one is copied. O(1) when this Vector is empty and iterable is a Vector, which is returned as is. |
asJava() |
O(1) | O(1): nothing is copied. get on the view is effectively O(1), as get, and each step of its iterator is O(1). |
combinations() |
O(n * 2^n) | O(n * 2^n): the 2^n combinations hold n * 2^(n - 1) elements in all, each built once. |
combinations(int) |
O(k * C(n, k)) | O(k * C(n, k)): each of the C(n, k) combinations is built from an array of k positions, which moves to the next combination in O(k); the elements are first copied into an array, O(n), which that bound covers. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
distinct() |
O(n) | O(n). |
distinctBy(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctBy(Function<? super T, ? extends U>) |
O(n) | O(n). |
duplicates() |
O(n) | O(n), one hash lookup per element. |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n). |
drop(int) |
effectively O(1) | effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied. |
dropUntil(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) drop. |
dropWhile(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) drop. |
dropRight(int) |
effectively O(1) | effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied. |
dropRightUntil(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) take. |
dropRightWhile(Predicate<? super T>) |
O(k) | O(k) for k dropped elements, then one effectively O(1) take. |
endsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
reject(Predicate<? super T>) |
O(n) | O(n); this Vector itself is returned when no element satisfies predicate. |
foldRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n), walking the elements from the last to the first without copying. |
get(int) |
effectively O(1) | effectively O(1): at most six array reads, whatever the size; one for the first and the last 32 elements. |
head() |
O(1) | O(1): the first elements are kept apart, in their own array. |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) |
O(n) | O(n): one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
indexOf(T) |
O(n) | O(n). |
indexOf(T, int) |
O(n) | O(n). |
indexOfOption(T) |
O(n) | O(n), as indexOf. |
indexOfOption(T, int) |
O(n) | O(n), as indexOf. |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
indexOfSliceOption(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements, as indexOfSlice. |
indexOfSliceOption(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements, as indexOfSlice. |
indexWhere(Predicate<? super T>) |
O(n) | O(n). |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
indexWhereOption(Predicate<? super T>) |
O(n) | O(n), as indexWhere. |
indexWhereOption(Predicate<? super T>, int) |
O(n) | O(n), as indexWhere. |
init() |
effectively O(1) | effectively O(1): the last array, at most 32 elements, is copied without its last element; the few arrays above it change only when it held one element. |
initOption() |
effectively O(1) | effectively O(1), as init. |
insert(int, T) |
O(min(i, n - i)) | O(min(i, n - i)): the elements on the shorter side of i are copied, those on the longer side are shared. |
insertAll(int, Iterable<? extends T>) |
O(m + min(i, n - i)) | O(m + min(i, n - i)) for m inserted elements: the elements on the shorter side of i are copied, those on the longer side are shared. |
intersperse(T) |
O(n) | O(n). |
isEmpty() |
O(1) | O(1). |
toNonEmptyVector() |
O(1) | O(1): the result wraps this Vector, nothing is copied. |
iterator() |
O(1) | O(1) to create, and O(1) per step: moving on to the next block of 32 elements takes at most six array lookups. |
last() |
O(1) | O(1): the last elements are kept apart, in their own array. |
lastIndexOf(T) |
O(n) | O(n). |
lastIndexOf(T, int) |
O(n) | O(n). |
lastIndexOfOption(T) |
O(n) | O(n), as lastIndexOf. |
lastIndexOfOption(T, int) |
O(n) | O(n), as lastIndexOf. |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexOfSliceOption(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements, as lastIndexOfSlice. |
lastIndexOfSliceOption(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements, as lastIndexOfSlice. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n). |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
lastIndexWhereOption(Predicate<? super T>) |
O(n) | O(n), as lastIndexWhere. |
lastIndexWhereOption(Predicate<? super T>, int) |
O(n) | O(n), as lastIndexWhere. |
mapConserve(Function<? super T, ? extends T>) |
O(n) | O(n); mapper runs once per element, in order, and the arrays whose elements are all unchanged are shared, not copied. |
orElse(Iterable<? extends T>) |
O(m) | O(m) for m elements of other when this Vector is empty and other is not a Vector: they are copied. O(1) otherwise. |
orElse(Supplier<? extends Iterable<? extends T>>) |
O(m) | O(m) for m supplied elements when this Vector is empty and they are not a Vector: they are copied. O(1) otherwise. |
padTo(int, T) |
O(k) | O(k) for the k elements appended. |
leftPadTo(int, T) |
O(k) | O(k) for the k elements prepended. |
patch(int, Iterable<? extends T>, int) |
O(n + m) | O(n + m) for m elements of that: that is copied, and the rest is joined as appendAll joins two Vectors, copying the shorter side. A patch near either end is O(m) plus a few small arrays. |
partition(Predicate<? super T>) |
O(n) | O(n), one pass. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n), one pass. |
permutations() |
O(n! * n) | O(n! * n) in the worst case (all elements distinct): there are n! permutations of n elements, each built once, in O(n), from an array of positions that moves to the next permutation in O(n) on average. With repeated elements there are fewer permutations, and a move can cost up to O(n^2). |
prefixLength(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements. |
prepend(T) |
effectively O(1) | effectively O(1): the first array, at most 32 elements, is copied; once every 32 prepends, a few arrays above it are copied too. |
prependAll(Iterable<? extends T>) |
O(m) | O(m) for m prepended elements; O(min(n, m)) when iterable is a Vector: the longer side is shared and only the shorter one is copied. O(1) when this Vector is empty and iterable is a Vector, which is returned as is. |
remove(T) |
O(n) | O(n). |
removeFirst(Predicate<T>) |
O(n) | O(n). |
removeLast(Predicate<T>) |
O(n) | O(n). |
removeAt(int) |
O(min(i, n - i)) | O(min(i, n - i)): the elements on the shorter side of i are copied, those on the longer side are shared. |
removeAll(T) |
O(n) | O(n). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for an argument of m elements: they are hashed once, then one filter pass. |
replace(T, T) |
O(n) | O(n) to find the element, then one effectively O(1) update. |
replaceAll(T, T) |
O(n) | O(n) plus one effectively O(1) update per occurrence. |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for an argument of m elements: they are hashed once, then one filter pass. |
reverse() |
O(n) | O(n). |
rotateLeft(int) |
O(min(k, n - k)) | O(min(k, n - k)), where k is the distance modulo the size: the two parts are joined as appendAll joins two Vectors, copying the shorter one. |
rotateRight(int) |
O(min(k, n - k)) | O(min(k, n - k)), where k is the distance modulo the size: the two parts are joined as appendAll joins two Vectors, copying the shorter one. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
O(n) | O(n). |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n). |
search(T) |
O(log n) | O(log n) comparisons, each an effectively O(1) access. |
search(T, Comparator<? super T>) |
O(log n) | O(log n) comparisons, each an effectively O(1) access. |
segmentLength(Predicate<? super T>, int) |
O(k) | O(k) for a run of k elements. |
shuffle() |
O(n) | O(n). |
slice(int, int) |
effectively O(1) | effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied. |
sorted() |
O(n log n) | O(n log n) comparisons; the elements are copied to an array and sorted there. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons; the elements are copied to an array and sorted there. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; mapper is called again for both elements at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; mapper is called again for both elements at every comparison. |
span(Predicate<? super T>) |
O(k) | O(k) for k elements before the split, then an effectively O(1) split. |
splitAt(int) |
effectively O(1) | effectively O(1): one take and one drop; both parts share their elements with this Vector. |
splitAt(Predicate<? super T>) |
O(k) | O(k) for k elements before the split, then an effectively O(1) split. |
splitAtInclusive(Predicate<? super T>) |
O(k) | O(k) for k elements up to the split, then an effectively O(1) split. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
startsWith(Iterable<? extends T>, int) |
O(m) | O(m) for m elements of that. |
subSequence(int) |
effectively O(1) | effectively O(1), as drop. |
subSequence(int, int) |
effectively O(1) | effectively O(1), as slice. |
tail() |
effectively O(1) | effectively O(1): the first array, at most 32 elements, is copied without its first element; the few arrays above it change only when it held one element. |
tailOption() |
effectively O(1) | effectively O(1), as tail. |
take(int) |
effectively O(1) | effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied. |
takeUntil(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) take. |
takeWhile(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) take. |
takeRight(int) |
effectively O(1) | effectively O(1): the result shares its elements with this Vector; only the few small arrays along the cut are copied. |
takeRightUntil(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) drop. |
takeRightWhile(Predicate<? super T>) |
O(k) | O(k) for k taken elements, then one effectively O(1) drop. |
unzip(Function<? super T, Tuple2<? extends T1, ? extends T2>>) |
O(n) | O(n). |
unzip3(Function<? super T, Tuple3<? extends T1, ? extends T2, ? extends T3>>) |
O(n) | O(n). |
update(int, T) |
effectively O(1) | effectively O(1): the array of 32 elements that holds it is copied, with at most five arrays above it; the rest is shared. |
update(int, Function<? super T, ? extends T>) |
effectively O(1) | effectively O(1): one get and one update. |
zip(Iterable<? extends U>) |
O(min(n, m)) | O(min(n, m)) for m elements of that. |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for m elements of that. |
zipAll(Iterable<? extends U>, T, U) |
O(max(n, m)) | O(max(n, m)) for m elements of that. |
zipWithIndex() |
O(n) | O(n). |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
O(n) | O(n). |
equals(Object) |
O(n + m) | O(n + m) for a sequence of m elements: the sizes are compared first (a List, a Queue or a LazyList counts its elements to answer), then the elements in order, up to the first difference. So it does not terminate when compared with an infinite LazyList. O(1) for an object that is not a sequence. |
hashCode() |
O(n) | O(n), computed again at every call: nothing is cached, which matters for a Vector used as a key of a HashMap or an element of a HashSet. |
grouped(int) |
O(n / size) | O(n / size): one effectively O(1) slice per block; each block shares its elements with this Vector. |
sliding(int) |
O(n) | O(n): one effectively O(1) slice per window; each window shares its elements with this Vector, so no element is copied. |
sliding(int, int) |
O(n / step) | O(n / step): one effectively O(1) slice per window; each window shares its elements with this Vector, so no element is copied. |
slideBy(Function<? super T, ?>) |
O(n) | O(n): one key per element, and one effectively O(1) slice per run; each run shares its elements with this Vector. |
crossProduct() |
O(n^2) | O(n^2); the pairs are built now. |
crossProduct(int) |
O(power * n^power) | O(power * n^power): n^power Vectors of power elements each, built now. |
crossProduct(Iterable<? extends U>) |
O(n * m) | O(n * m) for m elements of that; the pairs are built now. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), walking the elements from the last to the first without copying. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
reduceOption(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), as reduceLeft. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
O(1) | O(1), as head. |
lastOption() |
O(1) | O(1), as last. |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
reduceLeftOption(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), as reduceLeft. |
reduceRightOption(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), as reduceRight. |
size() |
O(1) | O(1): the size is stored. |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
contains(T) (from Traversable) |
O(n) | O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup. |
List¶
The methods without a note of their own (map, flatMap, the folds, groupBy, the conversions, equals, hashCode, toString) walk the elements once: O(n); an Option variant costs what the method it wraps costs, and toLazyList() is O(1), its elements being read as the LazyList reaches them. A List does not store its size, so equals, toArray(), stream() and spliterator() count the elements before they start, and containsAll is O(n * m) for m elements: each one is looked for by a walk.
| Method | Cost | Note |
|---|---|---|
isEmpty() |
O(1) | O(1). |
flatten(Iterable<? extends Iterable<? extends T>>) |
O(m) | O(m) for m inner elements in total: the elements go into an array, then the List is built from the last to the first. |
transpose(List<List<T>>) |
O(rows * columns) | O(rows * columns): every element is copied once. |
unfold(S, Function<? super S, ? extends Option<? extends Tuple2<? extends A, ? extends S>>>) |
O(n) | O(n) for n elements; f runs n + 1 times now. |
append(T) |
O(n) | O(n); every element of this List is copied. |
appendAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m appended elements: this List is copied. A List argument is shared, not copied; any other argument is copied into a new List first. |
asJava() |
O(1) | O(1): nothing is copied. On the view, get(i) is O(i), so a loop by index is O(n^2): iterate the view instead. size() is O(n) the first time, then O(1): the view keeps it. |
combinations() |
O(n * 2^n) | O(n * 2^n): 2^n combinations of up to n elements each. |
combinations(int) |
O(k * C(n, k)) | O(k * C(n, k)): C(n, k) combinations of k elements each, built from an array of k positions that moves to the next combination in O(k). The elements are first read into an array, O(n). |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements: the slice is compared at each position. |
distinct() |
O(n) | O(n): one hash lookup per element. |
distinctBy(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons: the elements seen are kept in a sorted set. |
distinctBy(Function<? super T, ? extends U>) |
O(n) | O(n): one key and one hash lookup per element. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons: the elements seen are kept in a sorted set. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n): one key and one hash lookup per element. |
drop(int) |
O(k) | O(k) for k dropped elements; the rest of this List is shared, not copied. |
dropUntil(Predicate<? super T>) |
O(k) | O(k) for the k dropped elements; the rest of this List is shared, not copied. |
dropWhile(Predicate<? super T>) |
O(k) | O(k) for the k dropped elements; the rest of this List is shared, not copied. |
dropRight(int) |
O(n) | O(n); the length is counted, then the kept elements are copied. |
dropRightUntil(Predicate<? super T>) |
O(n) | O(n); the List is copied twice (reversed, then reversed back). |
dropRightWhile(Predicate<? super T>) |
O(n) | O(n); the List is copied twice (reversed, then reversed back). |
duplicates() |
O(n) | O(n), one hash lookup per element. |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element. |
endsWith(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements of that: both lengths are counted, then the end of this List is compared. |
filter(Predicate<? super T>) |
O(n) | O(n); the elements after the last removed one are shared, not copied, and this List itself is returned when every element is kept. |
reject(Predicate<? super T>) |
O(n) | O(n); this List itself is returned when no element satisfies predicate. |
foldRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); this List is reversed first, a copy. |
get(int) |
O(i) | O(i); the elements before i are walked one by one. |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) |
O(n) | O(n): one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
indexOf(T) |
O(n) | O(n). |
indexOf(T, int) |
O(n) | O(n); the walk starts at the first element, whatever i is. |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements: the slice is compared at each position. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements: the slice is compared at each position. |
indexWhere(Predicate<? super T>) |
O(n) | O(n). |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
init() |
O(n) | O(n); every element but the last is copied. |
initOption() |
O(n) | O(n), as init. |
insert(int, T) |
O(i) | O(i); the elements before i are copied, the rest of this List is shared. |
insertAll(int, Iterable<? extends T>) |
O(i + m) | O(i + m) for m inserted elements; the elements before i are copied, the rest of this List is shared. |
intersperse(T) |
O(n) | O(n). |
last() |
O(n) | O(n); the whole List is walked. |
lastIndexOf(T) |
O(n) | O(n). |
lastIndexOf(T, int) |
O(n) | O(n); the walk stops after index j. |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements: the slice is compared at each position. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements: the slice is compared at each position. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n); the length is counted, then the elements are tested. |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n); the walk stops after index j. |
mapConserve(Function<? super T, ? extends T>) |
O(n) | O(n); mapper runs once per element, in order, and the elements after the last changed one are shared, not copied. |
padTo(int, T) |
O(n + k) | O(n + k) for k added elements; this List is copied. |
leftPadTo(int, T) |
O(n + k) | O(n + k) for k added elements; this List is shared, not copied. A List already long enough is returned as is: its elements are counted only up to the target length. |
patch(int, Iterable<? extends T>, int) |
O(n + m) | O(n + m) for m replacement elements: the elements before and after the replaced ones are copied. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n); each side is built reversed and reversed once. |
peek() |
O(1) | O(1): the first element is stored directly. |
peekOption() |
O(1) | O(1): the first element is stored directly. |
permutations() |
O(n! * n) | O(n! * n) for n distinct elements: n! permutations, each built once, in O(n), from an array of positions that moves to the next permutation in O(n) on average. With repeated elements there are fewer permutations, and a move can cost up to O(n^2). |
pop() |
O(1) | O(1): the rest of the List is stored directly, nothing is copied. |
popOption() |
O(1) | O(1): the rest of the List is stored directly, nothing is copied. |
pop2() |
O(1) | O(1): the first element and the rest of the List are stored directly, nothing is copied. |
pop2Option() |
O(1) | O(1): the first element and the rest of the List are stored directly, nothing is copied. |
prefixLength(Predicate<? super T>) |
O(k) | O(k) for the k elements of the prefix. |
prepend(T) |
O(1) | O(1): one new element is put in front; this List is shared, not copied. |
prependAll(Iterable<? extends T>) |
O(m) | O(m) for m prepended elements; this List is shared, not copied. |
push(T) |
O(1) | O(1): one new element is put in front; this List is shared, not copied. |
push(T[]) |
O(m) | O(m) for m pushed elements; this List is shared, not copied. |
pushAll(Iterable<T>) |
O(m) | O(m) for m pushed elements; this List is shared, not copied. |
remove(T) |
O(k) | O(k) for the k elements before the removed one; the rest of this List is shared, not copied. |
removeFirst(Predicate<T>) |
O(k) | O(k) for the k elements before the removed one; the rest of this List is shared, not copied. |
removeLast(Predicate<T>) |
O(n) | O(n); the List is copied twice (reversed, then reversed back). |
removeAt(int) |
O(i) | O(i); the elements before i are copied, the rest of this List is shared. |
removeAll(T) |
O(n) | O(n). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements: they are put in a hash set, then this List is filtered once. |
replace(T, T) |
O(k) | O(k) for the k elements before the replaced one; the rest of this List is shared, not copied. |
replaceAll(T, T) |
O(n) | O(n). |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements: they are put in a hash set, then this List is filtered once. |
reverse() |
O(n) | O(n). |
rotateLeft(int) |
O(n) | O(n); O(1) when the distance is 0: this List is returned without being walked. |
rotateRight(int) |
O(n) | O(n); O(1) when the distance is 0: this List is returned without being walked. Otherwise the length is counted and the elements are read into an array, then the n cells of the result are built from the end. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
O(n) | O(n). |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); this List is reversed first, a copy. |
search(T) |
O(n) | O(n); a List has no access by index, so the search is linear even on a sorted List. |
search(T, Comparator<? super T>) |
O(n) | O(n); a List has no access by index, so the search is linear even on a sorted List. |
segmentLength(Predicate<? super T>, int) |
O(i + k) | O(i + k) for a run of k elements starting at index i. |
shuffle() |
O(n) | O(n). |
slice(int, int) |
O(j) | O(j); the elements before i are skipped, the ones from i to j are copied. |
sorted() |
O(n log n) | O(n log n) comparisons; the elements are copied to an array and sorted there. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons; the elements are copied to an array and sorted there. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
span(Predicate<? super T>) |
O(k) | O(k) for the k elements of the prefix; they are copied, the rest of this List is shared. |
splitAt(int) |
O(k) | O(k) for the first k elements; they are copied, the rest of this List is shared. |
splitAt(Predicate<? super T>) |
O(k) | O(k) for the k elements before the split; the suffix is shared. |
splitAtInclusive(Predicate<? super T>) |
O(k) | O(k) for the k elements up to the split; the suffix is shared. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that. |
startsWith(Iterable<? extends T>, int) |
O(i + m) | O(i + m) for m elements of that, compared from index i. |
subSequence(int) |
O(i) | O(i); the result shares its elements with this List. |
subSequence(int, int) |
O(j) | O(j); the elements before i are skipped, the ones from i to j are copied. |
tail() |
O(1) | O(1): the rest of the List is stored directly, nothing is copied. |
tailOption() |
O(1) | O(1): the rest of the List is stored directly, nothing is copied. |
take(int) |
O(k) | O(k) for k taken elements; they are copied. A List of at most k elements is returned as is. |
takeUntil(Predicate<? super T>) |
O(k) | O(k) for the k taken elements; they are copied, and this List itself is returned when every element is taken. |
takeWhile(Predicate<? super T>) |
O(k) | O(k) for the k taken elements; they are copied, and this List itself is returned when every element is taken. |
takeRight(int) |
O(n) | O(n); the length is counted, and the List is copied twice (reversed, then reversed back). |
takeRightUntil(Predicate<? super T>) |
O(n) | O(n); the List is copied twice (reversed, then reversed back). |
takeRightWhile(Predicate<? super T>) |
O(n) | O(n); the List is copied twice (reversed, then reversed back). |
update(int, T) |
O(i) | O(i); the elements before i are copied, the rest of this List is shared. |
update(int, Function<? super T, ? extends T>) |
O(i) | O(i); the element is read, then the elements before i are copied. |
zip(Iterable<? extends U>) |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
zipAll(Iterable<? extends U>, T, U) |
O(max(n, m)) | O(max(n, m)) for an argument of m elements. |
zipWithIndex() |
O(n) | O(n). |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
O(n) | O(n). |
head() |
O(1) | O(1): the first element is stored directly. |
iterator() |
O(1) | O(1) to create, O(1) per step. |
grouped(int) |
O(n) | O(n); each group is copied into its own List. |
sliding(int) |
O(n * size) | O(n * size); each window is copied into its own List. |
sliding(int, int) |
O(n + (n / step) * size) | O(n + (n / step) * size); each window is copied into its own List, and the elements between two windows are still walked. |
slideBy(Function<? super T, ?>) |
O(n) | O(n); each run is copied into its own List. |
crossProduct() |
O(n^2) | O(n^2); the pairs are built now. |
crossProduct(int) |
O(power * n^power) | O(power * n^power): n^power Lists of power elements each, built now; each List is copied every time an element is added to it. |
crossProduct(Iterable<? extends U>) |
O(n * m) | O(n * m) for m elements of that; the pairs are built now. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n); this List is reversed first, a copy. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
single() |
O(1) | O(1): at most two elements are read. |
singleOption() |
O(1) | O(1): at most two elements are read. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
O(1) | O(1), as head. |
lastOption() |
O(n) | O(n), as last. |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
reduceRightOption(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), as reduceRight. |
size() |
O(n) | O(n): a List does not store its size, so every call counts the elements. isEmpty is O(1). |
sizeCompare(int) |
O(min(n, k)) | O(min(n, k)) for k = otherSize: at most k + 1 cells are walked, where size() walks them all. |
collect(Collector<? super T, A, R>) |
O(n) | O(n), plus the collector's own work; the elements are counted first, to size the stream. |
collect(Supplier<R>, BiConsumer<R, ? super T>, BiConsumer<R, R>) |
O(n) | O(n), plus the work of the functions; the elements are counted first, to size the stream. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
contains(T) (from Traversable) |
O(n) | O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup. |
Queue¶
A Queue keeps its last elements in reverse order (those added at its back since it last put them in order, or those init moved there), and puts them in order in one O(n) step when a call needs them; the notes call them "the elements held at the back". The methods without a note of their own (map, flatMap, partition, the folds, the conversions, the static factories) walk the elements once: O(n); toSortedSet and toSortedMap sort them, O(n log n); toQueue, and ofAll given a Queue, are O(1).
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(n) | O(n) for n inner elements in total. |
transpose(Queue<Queue<T>>) |
O(rows * columns) | O(rows * columns). |
unfold(S, Function<? super S, ? extends Option<? extends Tuple2<? extends A, ? extends S>>>) |
O(n) | O(n) for n elements; f runs n + 1 times now. |
enqueue(T) |
O(1) | O(1). |
enqueueAll(Iterable<? extends T>) |
O(m) | O(m) for m enqueued elements. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
endsWith(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements of that. |
indexOf(T) |
O(n) | O(n). |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
indexWhere(Predicate<? super T>) |
O(n) | O(n). |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
lastIndexOf(T) |
O(n) | O(n). |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n). |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n). |
prefixLength(Predicate<? super T>) |
O(n) | O(n); O(k) for a prefix of k elements when the walk stops before the elements held at the back, which it must first put in order. On a Queue built by enqueue, most elements are held at the back. |
search(T) |
O(n) | O(n). |
search(T, Comparator<? super T>) |
O(n) | O(n). |
segmentLength(Predicate<? super T>, int) |
O(n) | O(n); O(i + k) for a run of k elements from index i when the walk stops before the elements held at the back, which it must first put in order. |
startsWith(Iterable<? extends T>) |
O(n) | O(n); O(m) for m elements of that when all of them are compared before the elements held at the back, which the comparison must otherwise put in order. On a Queue built by enqueue, most elements are held at the back, and even a one-element prefix costs O(n). |
indexOfOption(T) |
O(n) | O(n), as indexOf. |
indexOfOption(T, int) |
O(n) | O(n), as indexOf. |
indexOfSliceOption(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements, as indexOfSlice. |
indexOfSliceOption(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements, as indexOfSlice. |
indexWhereOption(Predicate<? super T>) |
O(n) | O(n), as indexWhere. |
indexWhereOption(Predicate<? super T>, int) |
O(n) | O(n), as indexWhere. |
lastIndexOfOption(T) |
O(n) | O(n), as lastIndexOf. |
lastIndexOfOption(T, int) |
O(n) | O(n), as lastIndexOf. |
lastIndexOfSliceOption(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements, as lastIndexOfSlice. |
lastIndexOfSliceOption(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements, as lastIndexOfSlice. |
lastIndexWhereOption(Predicate<? super T>) |
O(n) | O(n), as lastIndexWhere. |
lastIndexWhereOption(Predicate<? super T>, int) |
O(n) | O(n), as lastIndexWhere. |
foldRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); the elements are copied into a List first. |
append(T) |
O(1) | O(1), as enqueue. |
appendAll(Iterable<? extends T>) |
O(m) | O(m) for m appended elements. |
asJava() |
O(1) | O(1) to create. get(i) on the view costs what get costs, up to O(n), so an indexed loop over the view is O(n^2): iterate it instead. size() is O(n) the first time, then O(1). |
combinations() |
O(n * 2^n) | O(n * 2^n): 2^n combinations of up to n elements each. |
combinations(int) |
O(k * C(n, k)) | O(k * C(n, k)): C(n, k) combinations of k elements each, after an O(n) copy of this Queue. |
distinct() |
O(n) | O(n). |
distinctBy(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element. |
duplicates() |
O(n) | O(n), one hash lookup per element. |
duplicatesBy(Function<? super T, ? extends U>) |
O(n) | O(n), one key and one hash lookup per element. |
distinctByKeepLast(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
distinctByKeepLast(Function<? super T, ? extends U>) |
O(n) | O(n), one key per element. |
drop(int) |
O(n) | O(n). |
dropWhile(Predicate<? super T>) |
O(n) | O(n). |
dropRight(int) |
O(n) | O(n). |
dropRightUntil(Predicate<? super T>) |
O(n) | O(n). |
dropRightWhile(Predicate<? super T>) |
O(n) | O(n). |
filter(Predicate<? super T>) |
O(n) | O(n). |
get(int) |
O(n) | O(n); O(i) for an index i that falls before the elements held at the back. Every index does on a Queue built by ofAll; on a Queue built by enqueue, only index 0 does. |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) |
O(n) | O(n): one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
head() |
O(1) | O(1). |
indexOf(T, int) |
O(n) | O(n). |
init() |
amortised O(1) | amortised O(1) over a chain of calls, each on the result of the previous one. When no element is held at the back, the call moves the second half of the Queue there in one O(n) step, which the next calls use up. The Queue keeps that result: calling init() again on the same older Queue is O(1). |
insert(int, T) |
O(n) | O(n). |
insertAll(int, Iterable<? extends T>) |
O(n + m) | O(n + m) for m inserted elements. |
intersperse(T) |
O(n) | O(n). |
isEmpty() |
O(1) | O(1), whereas size counts the elements. |
iterator() |
O(1) | O(1) to create, then O(1) per step, apart from the step that reaches the elements held at the back: it copies them into an array, O(n) for n of them, read from its end. With none at the back, as on a Queue built by ofAll, it is the iterator of the front. |
last() |
O(n) | O(n); O(1) when some elements are held at the back, as after an enqueue. |
lastIndexOf(T, int) |
O(n) | O(n). |
mapConserve(Function<? super T, ? extends T>) |
O(n) | O(n); mapper runs once per element, and the elements after the last changed one, at the front and at the back, are shared, not copied. |
padTo(int, T) |
O(n + k) | O(n + k) for k added elements. |
leftPadTo(int, T) |
O(n + k) | O(n + k) for k added elements. |
patch(int, Iterable<? extends T>, int) |
O(n + m) | O(n + m) for m replacement elements. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n). |
permutations() |
O(n! * n) | O(n! * n) when the elements are distinct: n! permutations of n elements each, each built once, as List.permutations builds them, then copied into a Queue. |
prepend(T) |
O(1) | O(1). |
prependAll(Iterable<? extends T>) |
O(m) | O(m) for m prepended elements. |
remove(T) |
O(n) | O(n). |
removeFirst(Predicate<T>) |
O(n) | O(n). |
removeLast(Predicate<T>) |
O(n) | O(n). |
removeAt(int) |
O(n) | O(n). |
removeAll(T) |
O(n) | O(n). |
replace(T, T) |
O(n) | O(n). |
replaceAll(T, T) |
O(n) | O(n). |
reverse() |
O(n) | O(n). |
rotateLeft(int) |
O(n) | O(n); O(1) for a rotation by 0. |
rotateRight(int) |
O(n) | O(n); O(1) for a rotation by 0. Otherwise the elements are read into an array once, and the result is a front of n new cells built from it. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
O(n) | O(n). |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n). |
shuffle() |
O(n) | O(n). |
slice(int, int) |
O(n) | O(n). |
sorted() |
O(n log n) | O(n log n) comparisons. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the key is recomputed at every comparison. |
span(Predicate<? super T>) |
O(n) | O(n). |
splitAt(int) |
O(n) | O(n). |
splitAt(Predicate<? super T>) |
O(n) | O(n). |
splitAtInclusive(Predicate<? super T>) |
O(n) | O(n). |
startsWith(Iterable<? extends T>, int) |
O(n) | O(n); O(i + m) for m elements of that from index i when all of them are compared before the elements held at the back, which the comparison must otherwise put in order. |
subSequence(int) |
O(n) | O(n). |
subSequence(int, int) |
O(n) | O(n). |
tail() |
amortised O(1) | amortised O(1) over a chain of calls, each on the result of the previous one. When the removed element is the last one before the elements held at the back, the call puts those in order in one O(n) step. The Queue keeps that result: calling tail() again on the same older Queue is O(1). |
take(int) |
O(n) | O(n). |
takeUntil(Predicate<? super T>) |
O(n) | O(n). |
takeRight(int) |
O(n) | O(n). |
takeRightUntil(Predicate<? super T>) |
O(n) | O(n). |
takeRightWhile(Predicate<? super T>) |
O(n) | O(n). |
update(int, T) |
O(n) | O(n). |
update(int, Function<? super T, ? extends T>) |
O(n) | O(n). |
zip(Iterable<? extends U>) |
O(n) | O(n); O(min(n, m)) for an argument of m elements when the pairing stops before the elements held at the back, which it must otherwise put in order. On a Queue built by enqueue, even a one-element argument costs O(n). |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
O(n) | O(n); O(min(n, m)) for an argument of m elements when the pairing stops before the elements held at the back, which it must otherwise put in order. On a Queue built by enqueue, even a one-element argument costs O(n). |
zipAll(Iterable<? extends U>, T, U) |
O(max(n, m)) | O(max(n, m)) for an argument of m elements. |
zipWithIndex() |
O(n) | O(n). |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
O(n) | O(n). |
equals(Object) |
O(n + m) | O(n + m) for a sequence of m elements: both sizes are counted, then the elements are compared until two differ. |
hashCode() |
O(n) | O(n). |
dequeue() |
amortised O(1) | amortised O(1) over a chain of calls, as tail, which keeps the result of its O(n) step: calling it again on the same older Queue is O(1). |
dequeueOption() |
amortised O(1) | amortised O(1) over a chain of calls, as tail, which keeps the result of its O(n) step: calling it again on the same older Queue is O(1). |
enqueue(T[]) |
O(m) | O(m) for m enqueued elements. |
peek() |
O(1) | O(1). |
peekOption() |
O(1) | O(1). |
dropUntil(Predicate<? super T>) |
O(n) | O(n). |
initOption() |
amortised O(1) | amortised O(1) over a chain of calls, as init, which keeps the result of its O(n) step: calling it again on the same older Queue is O(1). |
tailOption() |
amortised O(1) | amortised O(1) over a chain of calls, as tail, which keeps the result of its O(n) step: calling it again on the same older Queue is O(1). |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m retained elements (they are hashed once, then one filter pass). |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m removed elements (they are hashed once, then one filter pass). |
reject(Predicate<? super T>) |
O(n) | O(n); this Queue itself is returned when no element satisfies predicate. |
takeWhile(Predicate<? super T>) |
O(n) | O(n). |
grouped(int) |
O(n) | O(n); each block is copied into its own Queue. |
sliding(int) |
O(n * size) | O(n * size); each window is copied into its own Queue. |
sliding(int, int) |
O(n + (n / step) * size) | O(n + (n / step) * size): every element is walked, and each window is copied into its own Queue. |
slideBy(Function<? super T, ?>) |
O(n) | O(n); each run is copied into its own Queue. |
crossProduct() |
O(n^2) | O(n^2); the pairs are built now. |
crossProduct(int) |
O(n^power) | O(n^power): n^power Queues of power elements, built now; each adds one element to a shorter result and shares the rest with it. |
crossProduct(Iterable<? extends U>) |
O(n * m) | O(n * m) for m elements of that; the pairs are built now. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested. |
headOption() |
O(1) | O(1), as head. |
lastOption() |
O(n) | O(n); O(1) when some elements are held at the back, as last. |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n). |
reduceRightOption(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n), as reduceRight. |
size() |
O(n) | O(n): the elements are counted. isEmpty is O(1). |
sizeCompare(int) |
O(min(n, k)) | O(min(n, k)) for k = otherSize: at most k + 1 elements are counted, where size() counts them all. |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when the size of that is stored. The elements held at the back, of this queue and of a Queue that, are counted where they are, not put in order first, as iterator() does once it reaches them. |
contains(T) (from Traversable) |
O(n) | O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup. |
LazyList¶
A lazy call computes now only what its note says, and each further element when the result reaches it. The methods without a note of their own that read every element (the folds, reduce, count, the sums and products, average, mkString, forEach, the conversions to other collections and hashCode) are O(n) and never return on an infinite LazyList; equals compares the elements in order and stops at the first difference or at the end of the shorter side, so it returns when either side is finite, but never on two infinite LazyLists with the same elements; exists, forAll, find and contains stop at the first element that decides, existsUnique at the second match, and each ...Option variant costs what the method it wraps costs. toString computes nothing: it shows the elements already computed, then <not computed> for the rest, or <cycle> where they loop back, as in LazyList(1, 2, 3, <cycle>) for LazyList.of(1, 2, 3).cycle() once read past its third element. It shows only the elements already computed when it reaches them, so it returns on an infinite LazyList too, unless another thread keeps computing further elements while it runs: it shows those as well.
| Method | Cost | Note |
|---|---|---|
concat(Iterable<? extends T>[]) |
lazy | lazy; nothing is computed now. Reading the first element takes the iterators and reads past the empty iterables before it; each further element is read when the result reaches it. |
concat(Iterable<? extends Iterable<? extends T>>) |
lazy | lazy; nothing is computed now. Reading the first element reads the outer iterable whole, so an infinite one never returns then; each element is read when the result reaches it. |
flatten(Iterable<? extends Iterable<? extends T>>) |
lazy | lazy; nothing is computed now. Reading the first element finds it past the empty inner iterables before it, and each further one is found when the result reaches it. An outer iterable with infinitely many empty inner ones and no element after them never returns then. |
defer(Supplier<? extends LazyList<? extends T>>) |
O(1) | O(1); nothing is evaluated now. |
of(T[]) |
O(n) | O(n) now, to copy the array and check it for nulls; the elements are read from the copy, so changing the array afterwards does not change the list. |
ofAll(Iterable<? extends T>) |
lazy | lazy; nothing is read now. The iterator is asked for when the result is first read. A LazyList, or its asJava() view, is returned itself, and an iterable already known to be empty (an empty Zazr collection, a LazyList whose emptiness has been read, an empty ArrayList, List.of() and the like) gives the empty LazyList; any other view is not asked whether it is empty. |
transpose(LazyList<LazyList<T>>) |
O(rows * columns) | O(rows * columns); the whole matrix is computed now. |
unfold(S, Function<? super S, ? extends Option<? extends Tuple2<? extends A, ? extends S>>>) |
lazy | lazy; nothing is computed now, and f runs once for each element read, when the result reaches it, so f may produce an infinite LazyList. |
containsSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements; the elements are computed up to one past the first match. |
endsWith(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements of that; the whole LazyList is computed. |
indexOf(T) |
O(n) | O(n); the elements are computed until the element is found. |
indexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements; the elements are computed up to one past the first match. |
indexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements; the elements are computed up to one past the first match. |
indexWhere(Predicate<? super T>) |
O(n) | O(n); the elements are computed until one satisfies the predicate. |
indexWhere(Predicate<? super T>, int) |
O(n) | O(n); the elements are computed until one at or after from satisfies the predicate. |
lastIndexOf(T) |
O(n) | O(n); the whole LazyList is computed. |
lastIndexOfSlice(Iterable<? extends T>) |
O(n * m) | O(n * m) for a slice of m elements; the whole LazyList is computed. |
lastIndexOfSlice(Iterable<? extends T>, int) |
O(n * m) | O(n * m) for a slice of m elements; the walk stops at most m elements past end, so it works on an infinite LazyList. |
lastIndexWhere(Predicate<? super T>) |
O(n) | O(n); the whole LazyList is computed. |
lastIndexWhere(Predicate<? super T>, int) |
O(n) | O(n); the elements up to one past end are computed, so it works on an infinite LazyList. |
prefixLength(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements; they are computed, and the first element after them. |
search(T) |
O(n) | O(n); the elements are computed until one is not smaller than element. |
search(T, Comparator<? super T>) |
O(n) | O(n); the elements are computed until one is not smaller than element. |
segmentLength(Predicate<? super T>, int) |
O(i + k) | O(i + k) for a run of k elements from index i; the elements up to the end of the run are computed, and the first one after it. |
startsWith(Iterable<? extends T>) |
O(m) | O(m) for m elements of that; at most the first m + 1 elements are computed. |
startsWith(Iterable<? extends T>, int) |
O(i + m) | O(i + m) for m elements of that from index i; at most the first i + m + 1 elements are computed. |
foldRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); the whole LazyList is computed now and copied in reverse before the fold. |
append(T) |
O(1) | O(1); nothing is computed now, and the element comes after the last one of this LazyList. Appending in a loop stays O(1) per call, and reading the result back costs O(1) per element, however many calls built it. |
appendAll(Iterable<? extends T>) |
O(1) | O(1); nothing is computed now, neither of this LazyList nor of the given elements, which are read when the result reaches them, so an infinite argument is fine. They are read once, into a LazyList that every result built from this one shares. Calling appendAll or append in a loop stays O(1) per call, and reading the result back costs O(1) per element, however many calls built it. |
appendSelf(Function<? super LazyList<T>, ? extends LazyList<T>>) |
O(1) | O(1); nothing is computed now, each element when the result reaches it. |
asJava() |
O(1) | O(1); the view computes no element before a read needs it: get(i) computes the first i + 1 elements, the iterator one element per step, and size(), lastIndexOf, hashCode, getLast and every read of reversed() compute the whole LazyList (they never return on an infinite LazyList). The view counts the size once and keeps it. |
combinations() |
lazy | lazy; nothing is computed now. Reading the first combination computes the whole LazyList, and reading the 2^n combinations costs O(n * 2^n). |
combinations(int) |
lazy | lazy; nothing is computed now, and reading the first combination computes the first k elements. Reading every combination costs O(k * C(n, k)): the next combination moves an array of the k chosen cells, in O(k), and reads at most one element more. A k greater than the length computes the whole LazyList when the result is first read, to find it empty. |
cycle() |
O(1) | O(1); nothing is computed now, and the result is infinite. |
cycle(int) |
lazy | lazy; nothing is computed now, and the result reads one element ahead of what it returns. |
distinct() |
lazy | lazy; nothing is computed now. Moving to the next element skips and hashes the repeated ones before it, which never ends on an infinite LazyList with no further new element. |
distinctBy(Comparator<? super T>) |
lazy | lazy; O(log n) comparisons per element read. Moving to the next element skips the repeated ones, as distinct does. |
distinctBy(Function<? super T, ? extends U>) |
lazy | lazy; one key and one hash lookup per element read. Moving to the next element skips the repeated ones, as distinct does. |
duplicates() |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n) with one hash lookup per element, because whether an element repeats is known only at the end. |
duplicatesBy(Function<? super T, ? extends U>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n) with one key and one hash lookup per element. |
distinctByKeepLast(Comparator<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n log n) comparisons, because the last occurrence decides. |
distinctByKeepLast(Function<? super T, ? extends U>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n) with one key per element, because the last occurrence decides. |
drop(int) |
lazy | lazy; nothing is computed now. Reading the first element computes the k dropped elements and the first one kept, O(k); the rest are computed when the result reaches them. A drop of a drop not read yet is one drop of the sum, so a chain of drops is read at the stack depth of one. |
dropUntil(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the k dropped elements and the first one kept, O(k); the rest are computed when the result reaches them. |
dropWhile(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the k dropped elements and the first one kept, O(k); the rest are computed when the result reaches them. |
dropRight(int) |
lazy | lazy; nothing is computed now. Reading the first element computes the first k + 1 elements, O(k), and the result then reads k elements ahead of what it returns, so it works on an infinite LazyList. |
dropRightUntil(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because the last matching element decides. |
dropRightWhile(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because the last matching element decides. |
filter(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the elements up to the first match, and moving to the next element skips every element that does not match, which never ends on an infinite LazyList with no further match. |
reject(Predicate<? super T>) |
lazy | lazy, like filter: nothing is computed now, and reading an element skips every element before it that satisfies the predicate, which never ends on an infinite LazyList with nothing left to keep. |
flatMap(Function<? super T, ? extends Iterable<? extends U>>) |
lazy | lazy; nothing is computed now. Reading an element computes the elements until mapper returns a non-empty result, skipping the empty results, which never ends on an infinite LazyList whose results are all empty from some point on. |
get(int) |
O(i) | O(i); the first i + 1 elements are computed. |
groupBy(Function<? super T, ? extends C>) |
O(n) | O(n): the whole LazyList is computed now, so it never returns on an infinite LazyList; one key and one hash lookup per element. |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) |
O(n) | O(n): the whole LazyList is computed now, so it never returns on an infinite LazyList; one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) |
O(n) | O(n): the whole LazyList is computed now, so it never returns on an infinite LazyList; one key, one value, one hash lookup and at most one reduce per element. |
indexOf(T, int) |
O(n) | O(n); the elements are computed until the element is found at or after from. |
init() |
lazy | lazy; the first element is computed now, to know that this LazyList is not empty, and the result reads one element ahead of what it returns. |
initOption() |
lazy | lazy, as init. |
insert(int, T) |
lazy | lazy; nothing is computed now. The result copies the elements before index i as it reaches them, and shares the rest. |
insertAll(int, Iterable<? extends T>) |
lazy | lazy; nothing is computed now. The result copies the elements before index i as it reaches them, then reads elements and shares the rest of this LazyList, as prependAll does. |
intersperse(T) |
lazy | lazy; nothing is computed now, and reaching a separator computes the element after it. |
last() |
O(n) | O(n); the whole LazyList is computed. |
lastIndexOf(T, int) |
O(n) | O(n); the elements up to one past end are computed, so it works on an infinite LazyList. |
map(Function<? super T, ? extends U>) |
lazy | lazy; nothing is computed now, and mapper runs on each element when the result reaches it. |
collect(Function<? super T, ? extends Option<? extends U>>) |
lazy | lazy, like filter: nothing is computed now, and reading an element skips every element mapper drops before it, which never ends on an infinite LazyList with nothing left to keep. |
padTo(int, T) |
lazy | lazy; nothing is computed now, each element when the result reaches it. |
leftPadTo(int, T) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because its length decides how much padding is needed. |
patch(int, Iterable<? extends T>, int) |
lazy | lazy; nothing is computed now. Each element is computed when the result reaches it, and the replaced ones are skipped then. |
partition(Predicate<? super T>) |
lazy | lazy; nothing is computed now, and each side computes its elements as filter does, so reading a side that stays empty never returns on an infinite LazyList. The predicate runs twice per element, once for each side. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
lazy | lazy; nothing is computed now, each side computes the elements when it reaches them, and f runs once per element. The values one side has passed are kept until the other side passes them too. On an infinite LazyList whose elements all go to one side, reading the other side never returns. |
tap(Consumer<? super T>) |
lazy | lazy; nothing is computed now, and the action runs on each element when the result reaches it. |
permutations() |
lazy | lazy; nothing is computed now. Reading every permutation of n distinct elements costs O(n! * n), O(n) each on average; with repeated elements there are fewer permutations, up to O(n^2) each. Reading the first computes the whole LazyList. |
prepend(T) |
O(1) | O(1); nothing is computed. |
prependAll(Iterable<? extends T>) |
O(1) | O(1); nothing is computed now: the given elements are read when the result reaches them, and this LazyList is shared, not read. Calling prependAll in a loop stays O(1) per call, and reading the result back costs O(1) per element, however many calls built it. |
remove(T) |
lazy | lazy; nothing is computed now. Each element is compared when the result reaches it, and the elements after the removed one are shared. |
removeFirst(Predicate<T>) |
lazy | lazy; nothing is computed now. Each element is tested when the result reaches it, and the elements after the removed one are shared. |
removeLast(Predicate<T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because the last match decides. |
removeAt(int) |
lazy | lazy; nothing is computed now. The result copies the elements before index i as it reaches them, and shares the rest. |
removeAll(T) |
lazy | lazy, like filter: nothing is computed now, and reading an element skips every occurrence of element before it, which never ends on an infinite LazyList with nothing left to keep. |
removeAll(Iterable<? extends T>) |
lazy | lazy, like filter: nothing is computed now. Reading the first element hashes the m given elements, and reading an element skips every removed element before it, which never ends on an infinite LazyList with nothing left to keep. |
replace(T, T) |
lazy | lazy; nothing is computed now. Each element is compared when the result reaches it, and the elements after the replaced one are shared. |
replaceAll(T, T) |
lazy | lazy; nothing is computed now, and each element is compared when the result reaches it. |
retainAll(Iterable<? extends T>) |
lazy | lazy, like filter: nothing is computed now. Reading the first element hashes the m given elements, and reading an element skips every element before it that is not among them, which never ends on an infinite LazyList with nothing left to keep. |
reverse() |
O(n) | O(n); the whole LazyList is computed now. |
rotateLeft(int) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because its length decides the rotation. A rotation by 0 is O(1) and works on an infinite LazyList. |
rotateRight(int) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because its length decides the rotation. A rotation by 0 is O(1) and works on an infinite LazyList. |
scan(T, BiFunction<? super T, ? super T, ? extends T>) |
lazy | lazy; nothing is computed now, each element when the result reaches it. |
scanLeft(U, BiFunction<? super U, ? super T, ? extends U>) |
lazy | lazy; nothing is computed now, each element when the result reaches it. |
scanRight(U, BiFunction<? super T, ? super U, ? extends U>) |
O(n) | O(n); the whole LazyList is computed now, because the fold starts at the end. |
shuffle() |
O(n) | O(n); the whole LazyList is computed now. |
slice(int, int) |
lazy | lazy; nothing is computed now. Reading the first element computes the first i + 1 elements, O(i), and the rest up to index j are computed when the result reaches them, so it works on an infinite LazyList. |
sorted() |
O(n log n) | O(n log n) comparisons; the whole LazyList is computed now. |
sorted(Comparator<? super T>) |
O(n log n) | O(n log n) comparisons; the whole LazyList is computed now. |
sortBy(Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the whole LazyList is computed now. The key is computed again at every comparison. |
sortBy(Comparator<? super U>, Function<? super T, ? extends U>) |
O(n log n) | O(n log n) comparisons; the whole LazyList is computed now. The key is computed again at every comparison. |
span(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Each side computes its elements when it is read: the prefix up to the first element that fails the predicate, the suffix from there. |
splitAt(int) |
lazy | lazy; nothing is computed now, and each side computes its elements when it is read. |
splitAt(Predicate<? super T>) |
lazy | lazy; nothing is computed now, and each side computes its elements when it is read: the suffix starts at the first match. |
splitAtInclusive(Predicate<? super T>) |
lazy | lazy; nothing is computed now, and each side computes its elements when it is read: reading either computes the elements up to the match. |
subSequence(int) |
O(i) | O(i); the first i elements are computed now, to check that the index is within this LazyList, and the rest when the result reaches them. |
subSequence(int, int) |
O(i) | O(i); the first i + 1 elements are computed now, to check the bounds, and the rest up to index j when the result reaches them. An empty range computes its first i elements too, to check that it is within this LazyList, and a reversed range its first j. |
tail() |
O(1) | O(1) once this LazyList is computed: the tail is returned without being computed. If this LazyList is not computed yet, the call computes it first, as head does. On a LazyList built by append or appendAll, computing the first appended element may put the p appended parts in order, O(p) once for the whole walk. |
tailOption() |
O(1) | O(1), as tail. |
take(int) |
lazy | lazy; nothing is computed now, each element when the result reaches it. |
takeUntil(Predicate<? super T>) |
lazy | lazy; nothing is computed now, and each element is tested when the result reaches it. |
takeWhile(Predicate<? super T>) |
lazy | lazy; nothing is computed now, and each element is tested when the result reaches it. |
takeRight(int) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because the last elements are found by walking to the end. For n <= 0, the empty LazyList, and nothing is read. |
takeRightUntil(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because the last matching element decides. |
takeRightWhile(Predicate<? super T>) |
lazy | lazy; nothing is computed now. Reading the first element computes the whole LazyList, O(n), because the last matching element decides. |
unzip(Function<? super T, Tuple2<? extends T1, ? extends T2>>) |
lazy | lazy; nothing is computed now, and unzipper runs once on each element, when either side reaches it. |
unzip3(Function<? super T, Tuple3<? extends T1, ? extends T2, ? extends T3>>) |
lazy | lazy; nothing is computed now, and unzipper runs once on each element, when a side reaches it. |
update(int, T) |
lazy | lazy; nothing is computed now. The result copies the elements before index i as it reaches them and shares those after it; an index past the end throws when the result reaches it. |
update(int, Function<? super T, ? extends T>) |
lazy | lazy, as update: updater runs when the result reaches index i. |
zip(Iterable<? extends U>) |
lazy | lazy; nothing is computed now, and reading every pair costs O(min(n, m)). |
zipWith(Iterable<? extends U>, BiFunction<? super T, ? super U, ? extends R>) |
lazy | lazy; nothing is computed now, and reading every result costs O(min(n, m)). |
zipAll(Iterable<? extends U>, T, U) |
lazy | lazy; nothing is computed now, and reading every pair costs O(max(n, m)). |
zipWithIndex() |
lazy | lazy; nothing is computed now, each element when the result reaches it. |
zipWithIndex(BiFunction<? super T, ? super Integer, ? extends U>) |
lazy | lazy; nothing is computed now, each element when the result reaches it. |
extend(T) |
O(1) | O(1); nothing is computed now, and the result is infinite. |
extend(Supplier<? extends T>) |
O(1) | O(1); nothing is computed now, and the result is infinite. |
extend(Function<? super T, ? extends T>) |
O(1) | O(1); nothing is computed now, and the result, infinite, reads one element ahead of what it returns. |
head() |
O(1) | O(1) once this LazyList is computed; otherwise the call computes it first, which is where a lazy operation does its work (such as the search of filter), and keeps the result. |
grouped(int) |
lazy | lazy; nothing is computed now, and reading every block costs O(n). Moving to the next block computes the elements of the current one and one more, so an infinite LazyList can be grouped. |
sliding(int) |
lazy | lazy; nothing is computed now, and reading every window costs O(n * size). Moving to the next window computes the elements of the current one and one more, so an infinite LazyList can be windowed. |
sliding(int, int) |
lazy | lazy; nothing is computed now, and reading every window costs O(n + (n / step) * size). Moving to the next window computes the elements up to max(size, step) positions after the start of the current one, so an infinite LazyList can be windowed. |
slideBy(Function<? super T, ?>) |
lazy | lazy; nothing is computed now. Reading a run computes it with the first element of the next one. |
crossProduct() |
lazy | lazy; nothing is computed now, and reading every pair costs O(n^2). |
crossProduct(int) |
lazy | lazy; nothing is computed now, and reading the n^power results of power elements each costs O(power * n^power). |
crossProduct(Iterable<? extends U>) |
lazy | lazy; nothing is computed now, and reading every pair costs O(n * m). With an empty that, reading the result computes the whole LazyList, so it never returns on an infinite one. |
reduceRight(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n); the whole LazyList is computed now and copied in reverse. |
max() |
O(n) | O(n), every element compared once; the whole LazyList is computed. |
min() |
O(n) | O(n), every element compared once; the whole LazyList is computed. |
arrangeBy(Function<? super T, ? extends K>) |
O(n) | O(n), as groupBy; the whole LazyList is computed now. |
findLast(Predicate<? super T>) |
O(n) | O(n); every element is tested, so the whole LazyList is computed. |
headOption() |
O(1) | O(1), as head. |
lastOption() |
O(n) | O(n), as last. |
reduceLeft(BiFunction<? super T, ? super T, ? extends T>) |
O(n) | O(n); the whole LazyList is computed. |
size() |
O(n) | O(n): the whole LazyList is computed and walked at each call, so it never returns on an infinite LazyList. |
sizeCompare(int) |
O(min(n, k)) | O(min(n, k)) for k = otherSize: at most k + 1 elements are computed, so it returns on an infinite LazyList, where size() never does. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
contains(T) (from Traversable) |
O(n) | O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup. |
NonEmptyVector¶
Every method costs what the same method of the wrapped Vector costs; wrapping and unwrapping copy nothing. The methods without a note of their own (map, flatMap, filter, the folds, groupBy, the conversions and the factories) walk the elements once: O(n).
| Method | Cost | Note |
|---|---|---|
transpose(NonEmptyVector<? extends NonEmptyVector<? extends A>>) |
O(rows * columns) | O(rows * columns), as Vector.transpose. |
mapConserve(Function<? super A, ? extends A>) |
O(n) | O(n); mapper runs once per element, in order, and the arrays whose elements are all unchanged are shared, not copied. |
append(A) |
effectively O(1) | effectively O(1), as Vector.append. |
appendAll(Vector<? extends A>) |
O(m) | O(m) for m appended elements, as Vector.appendAll. |
appendAll(NonEmptyVector<? extends A>) |
O(m) | O(m) for m appended elements, as Vector.appendAll. |
concat(NonEmptyVector<? extends A>) |
O(m) | O(m) for m appended elements, as appendAll. |
prepend(A) |
effectively O(1) | effectively O(1), as Vector.prepend. |
prependAll(Vector<? extends A>) |
O(m) | O(m) for m prepended elements, as Vector.prependAll. |
prependAll(NonEmptyVector<? extends A>) |
O(m) | O(m) for m prepended elements, as Vector.prependAll. |
reverse() |
O(n) | O(n), as Vector.reverse. |
distinct() |
O(n) | O(n), as Vector.distinct. |
distinctBy(Comparator<? super A>) |
O(n log n) | O(n log n) comparisons, as Vector.distinctBy. |
distinctBy(Function<? super A, ? extends K>) |
O(n) | O(n), as Vector.distinctBy. |
sorted() |
O(n log n) | O(n log n) comparisons, as Vector.sorted. |
sorted(Comparator<? super A>) |
O(n log n) | O(n log n) comparisons, as Vector.sorted. |
sortBy(Function<? super A, ? extends U>) |
O(n log n) | O(n log n) comparisons, as Vector.sortBy. |
sortBy(Comparator<? super U>, Function<? super A, ? extends U>) |
O(n log n) | O(n log n) comparisons, as Vector.sortBy. |
zip(NonEmptyVector<? extends B>) |
O(min(n, m)) | O(min(n, m)) for m elements of that, as Vector.zip. |
zipWith(NonEmptyVector<? extends B>, BiFunction<? super A, ? super B, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for m elements of that, as Vector.zipWith. |
zipWithIndex() |
O(n) | O(n), as Vector.zipWithIndex. |
zipWithIndex(BiFunction<? super A, ? super Integer, ? extends B>) |
O(n) | O(n), as Vector.zipWithIndex. |
scanLeft(B, BiFunction<? super B, ? super A, ? extends B>) |
O(n) | O(n), as Vector.scanLeft. |
update(int, A) |
effectively O(1) | effectively O(1), as Vector.update. |
update(int, Function<? super A, ? extends A>) |
effectively O(1) | effectively O(1), as Vector.update. |
grouped(int) |
O(n / size) | O(n / size), as Vector.grouped: each block shares its elements with this vector. |
groupMap(Function<? super A, ? extends K>, Function<? super A, ? extends B>) |
O(n) | O(n): one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super A, ? extends K>, Function<? super A, ? extends B>, BiFunction<? super B, ? super B, ? extends B>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
sizeCompare(int) |
O(1) | O(1): the stored size is compared. |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most; O(1) when the size of that is stored. |
as(B) |
O(n) | O(n), as Vector.as. |
appendAll(Iterable<? extends A>) |
O(m) | O(m) for m appended elements, as Vector.appendAll. |
prependAll(Iterable<? extends A>) |
O(m) | O(m) for m prepended elements, as Vector.prependAll. |
insert(int, A) |
O(min(i, n - i)) | O(min(i, n - i)), as Vector.insert. |
insertAll(int, Iterable<? extends A>) |
O(m + min(i, n - i)) | O(m + min(i, n - i)) for m inserted elements, as Vector.insertAll. |
intersperse(A) |
O(n) | O(n), as Vector.intersperse. |
padTo(int, A) |
O(k) | O(k) for the k elements appended, as Vector.padTo. |
leftPadTo(int, A) |
O(k) | O(k) for the k elements prepended, as Vector.leftPadTo. |
rotateLeft(int) |
O(min(k, n - k)) | O(min(k, n - k)), where k is the distance modulo the size, as Vector.rotateLeft. |
rotateRight(int) |
O(min(k, n - k)) | O(min(k, n - k)), where k is the distance modulo the size, as Vector.rotateRight. |
shuffle() |
O(n) | O(n), as Vector.shuffle. |
replace(A, A) |
O(n) | O(n) to find the element, then one effectively O(1) update, as Vector.replace. |
replaceAll(A, A) |
O(n) | O(n) plus one effectively O(1) update per occurrence, as Vector.replaceAll. |
scan(A, BiFunction<? super A, ? super A, ? extends A>) |
O(n) | O(n), as Vector.scan. |
scanRight(B, BiFunction<? super A, ? super B, ? extends B>) |
O(n) | O(n), as Vector.scanRight. |
zipAll(Iterable<? extends B>, A, B) |
O(max(n, m)) | O(max(n, m)) for m elements of that, as Vector.zipAll. |
distinctByKeepLast(Comparator<? super A>) |
O(n log n) | O(n log n) comparisons, as Vector.distinctByKeepLast. |
distinctByKeepLast(Function<? super A, ? extends K>) |
O(n) | O(n), as Vector.distinctByKeepLast. |
unzip(Function<? super A, Tuple2<? extends T1, ? extends T2>>) |
O(n) | O(n). |
unzip3(Function<? super A, Tuple3<? extends T1, ? extends T2, ? extends T3>>) |
O(n) | O(n). |
sliding(int) |
O(n) | O(n), as Vector.sliding: each window shares its elements with this vector. |
sliding(int, int) |
O(n / step) | O(n / step), as Vector.sliding: each window shares its elements with this vector. |
slideBy(Function<? super A, ?>) |
O(n) | O(n), as Vector.slideBy: each run shares its elements with this vector. |
permutations() |
O(n! * n) | O(n! * n) in the worst case (all elements distinct), as Vector.permutations. |
combinations() |
O(n * 2^n) | O(n * 2^n), as Vector.combinations. |
crossProduct() |
O(n^2) | O(n^2), as Vector.crossProduct. |
crossProduct(NonEmptyVector<? extends B>) |
O(n * m) | O(n * m) for m elements of that, as Vector.crossProduct. |
toVector() |
O(1) | O(1): the wrapped Vector is returned, nothing is copied. |
duplicates() |
O(n) | O(n), as Vector.duplicates. |
duplicatesBy(Function<? super A, ? extends K>) |
O(n) | O(n), as Vector.duplicatesBy. |
tail() |
effectively O(1) | effectively O(1), as Vector.tail. |
init() |
effectively O(1) | effectively O(1), as Vector.init. |
drop(int) |
effectively O(1) | effectively O(1), as Vector.drop. |
dropRight(int) |
effectively O(1) | effectively O(1), as Vector.dropRight. |
dropWhile(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, as Vector.dropWhile. |
dropUntil(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, as Vector.dropUntil. |
dropRightWhile(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, as Vector.dropRightWhile. |
dropRightUntil(Predicate<? super A>) |
O(k) | O(k) for k dropped elements, as Vector.dropRightUntil. |
take(int) |
effectively O(1) | effectively O(1), as Vector.take. |
takeRight(int) |
effectively O(1) | effectively O(1), as Vector.takeRight. |
takeWhile(Predicate<? super A>) |
O(k) | O(k) for k taken elements, as Vector.takeWhile. |
takeUntil(Predicate<? super A>) |
O(k) | O(k) for k taken elements, as Vector.takeUntil. |
takeRightWhile(Predicate<? super A>) |
O(k) | O(k) for k taken elements, as Vector.takeRightWhile. |
takeRightUntil(Predicate<? super A>) |
O(k) | O(k) for k taken elements, as Vector.takeRightUntil. |
slice(int, int) |
effectively O(1) | effectively O(1), as Vector.slice. |
removeAt(int) |
O(min(i, n - i)) | O(min(i, n - i)), as Vector.removeAt. |
remove(A) |
O(n) | O(n), as Vector.remove. |
removeAll(A) |
O(n) | O(n), as Vector.removeAll. |
removeAll(Iterable<? extends A>) |
O(n + m) | O(n + m) for an argument of m elements, as Vector.removeAll. |
removeFirst(Predicate<? super A>) |
O(n) | O(n), as Vector.removeFirst. |
removeLast(Predicate<? super A>) |
O(n) | O(n), as Vector.removeLast. |
retainAll(Iterable<? extends A>) |
O(n + m) | O(n + m) for an argument of m elements, as Vector.retainAll. |
patch(int, Iterable<? extends A>, int) |
O(n + m) | O(n + m) for m elements of that, as Vector.patch: a patch near the end is O(m). |
subSequence(int) |
effectively O(1) | effectively O(1), as Vector.subSequence. |
subSequence(int, int) |
effectively O(1) | effectively O(1), as Vector.subSequence. |
splitAt(int) |
effectively O(1) | effectively O(1), as Vector.splitAt. |
splitAt(Predicate<? super A>) |
O(k) | O(k) for k elements before the split, then an effectively O(1) split, as Vector.splitAt. |
splitAtInclusive(Predicate<? super A>) |
O(k) | O(k) for k elements up to the split, then an effectively O(1) split, as Vector.splitAtInclusive. |
span(Predicate<? super A>) |
O(k) | O(k) for k elements before the split, then an effectively O(1) split, as Vector.span. |
partition(Predicate<? super A>) |
O(n) | O(n), one pass. |
zip(Iterable<? extends B>) |
O(min(n, m)) | O(min(n, m)) for m elements of that, as Vector.zip. |
zipWith(Iterable<? extends B>, BiFunction<? super A, ? super B, ? extends R>) |
O(min(n, m)) | O(min(n, m)) for m elements of that, as Vector.zipWith. |
crossProduct(Iterable<? extends B>) |
O(n * m) | O(n * m) for m elements of that, as Vector.crossProduct. |
crossProduct(int) |
O(power * n^power) | O(power * n^power), as Vector.crossProduct. |
combinations(int) |
O(k * C(n, k)) | O(k * C(n, k)), as Vector.combinations. |
head() |
O(1) | O(1), as Vector.head. |
last() |
O(1) | O(1), as Vector.last. |
max(Comparator<? super A>) |
O(n) | O(n), every element compared once. |
min(Comparator<? super A>) |
O(n) | O(n), every element compared once. |
reduceLeft(BiFunction<? super A, ? super A, ? extends A>) |
O(n) | O(n), as Vector.reduceLeft. |
reduceRight(BiFunction<? super A, ? super A, ? extends A>) |
O(n) | O(n), as Vector.reduceRight. |
size() |
O(1) | O(1), as Vector.size. |
get(int) |
effectively O(1) | effectively O(1), as Vector.get. |
foldRight(B, BiFunction<? super A, ? super B, ? extends B>) |
O(n) | O(n), as Vector.foldRight. |
contains(A) |
O(n) | O(n). |
indexOf(A) |
O(n) | O(n). |
indexOf(A, int) |
O(n) | O(n), as Vector.indexOf. |
indexWhere(Predicate<? super A>) |
O(n) | O(n), as Vector.indexWhere. |
indexWhere(Predicate<? super A>, int) |
O(n) | O(n), as Vector.indexWhere. |
lastIndexOf(A) |
O(n) | O(n), as Vector.lastIndexOf. |
lastIndexOf(A, int) |
O(n) | O(n), as Vector.lastIndexOf. |
lastIndexWhere(Predicate<? super A>) |
O(n) | O(n), as Vector.lastIndexWhere. |
lastIndexWhere(Predicate<? super A>, int) |
O(n) | O(n), as Vector.lastIndexWhere. |
indexOfSlice(Iterable<? extends A>) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.indexOfSlice. |
indexOfSlice(Iterable<? extends A>, int) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.indexOfSlice. |
lastIndexOfSlice(Iterable<? extends A>) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.lastIndexOfSlice. |
lastIndexOfSlice(Iterable<? extends A>, int) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.lastIndexOfSlice. |
startsWith(Iterable<? extends A>) |
O(m) | O(m) for m elements of that, as Vector.startsWith. |
startsWith(Iterable<? extends A>, int) |
O(m) | O(m) for m elements of that, as Vector.startsWith. |
endsWith(Iterable<? extends A>) |
O(m) | O(m) for m elements of that, as Vector.endsWith. |
containsSlice(Iterable<? extends A>) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.containsSlice. |
containsAll(Iterable<? extends A>) |
O(n * m) | O(n * m) for an argument of m elements: one contains per element, each O(n). |
search(A) |
O(log n) | O(log n) comparisons, each an effectively O(1) access, as Vector.search. |
search(A, Comparator<? super A>) |
O(log n) | O(log n) comparisons, each an effectively O(1) access, as Vector.search. |
segmentLength(Predicate<? super A>, int) |
O(k) | O(k) for a run of k elements, as Vector.segmentLength. |
prefixLength(Predicate<? super A>) |
O(k) | O(k) for a prefix of k elements, as Vector.prefixLength. |
existsUnique(Predicate<? super A>) |
O(n) | O(n). |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
maxBy(Comparator<? super A>) |
O(n) | O(n), every element compared once, as max. |
minBy(Comparator<? super A>) |
O(n) | O(n), every element compared once, as min. |
fold(A, BiFunction<? super A, ? super A, ? extends A>) |
O(n) | O(n), as Vector.fold. |
sumInt(ToIntFunction<? super A>) |
O(n) | O(n). |
sumLong(ToLongFunction<? super A>) |
O(n) | O(n). |
sumDouble(ToDoubleFunction<? super A>) |
O(n) | O(n). |
productInt(ToIntFunction<? super A>) |
O(n) | O(n). |
productLong(ToLongFunction<? super A>) |
O(n) | O(n). |
productDouble(ToDoubleFunction<? super A>) |
O(n) | O(n). |
average(ToDoubleFunction<? super A>) |
O(n) | O(n), one compensated pass. |
single() |
O(1) | O(1). |
arrangeBy(Function<? super A, ? extends K>) |
O(n) | O(n), as Vector.arrangeBy. |
forEachWithIndex(ObjIntConsumer<? super A>) |
O(n) | O(n). |
collect(Collector<? super A, C, R>) |
O(n) | O(n), as Vector.collect. |
collect(Supplier<R>, BiConsumer<R, ? super A>, BiConsumer<R, R>) |
O(n) | O(n), as Vector.collect. |
iterator() |
O(1) | O(1) to create, and O(1) per step, as Vector.iterator. |
asJava() |
O(1) | O(1): nothing is copied. get on the view is effectively O(1), as get. |
toQueue() |
O(n) | O(n). |
toLazyList() |
O(n) | O(n). |
toLinkedSet() |
O(n) | O(n). |
toSortedSet() |
O(n log n) | O(n log n). |
toSortedSet(Comparator<? super A>) |
O(n log n) | O(n log n). |
toArray() |
O(n) | O(n). |
toArray(IntFunction<A[]>) |
O(n) | O(n). |
toMap(Function<? super A, ? extends K>, Function<? super A, ? extends V>) |
O(n) | O(n), one entry built per element. |
toMap(Function<? super A, ? extends Tuple2<? extends K, ? extends V>>) |
O(n) | O(n), one entry built per element. |
toLinkedMap(Function<? super A, ? extends K>, Function<? super A, ? extends V>) |
O(n) | O(n), one entry built per element. |
toLinkedMap(Function<? super A, ? extends Tuple2<? extends K, ? extends V>>) |
O(n) | O(n), one entry built per element. |
toSortedMap(Function<? super A, ? extends K>, Function<? super A, ? extends V>) |
O(n log n) | O(n log n), one entry built per element. |
toSortedMap(Function<? super A, ? extends Tuple2<? extends K, ? extends V>>) |
O(n log n) | O(n log n), one entry built per element. |
toSortedMap(Comparator<? super K>, Function<? super A, ? extends K>, Function<? super A, ? extends V>) |
O(n log n) | O(n log n), one entry built per element. |
toSortedMap(Comparator<? super K>, Function<? super A, ? extends Tuple2<? extends K, ? extends V>>) |
O(n log n) | O(n log n), one entry built per element. |
findLast(Predicate<? super A>) |
O(n) | O(n), as Vector.findLast. |
indexOfOption(A, int) |
O(n) | O(n), as Vector.indexOfOption. |
indexWhereOption(Predicate<? super A>) |
O(n) | O(n), as Vector.indexWhereOption. |
indexWhereOption(Predicate<? super A>, int) |
O(n) | O(n), as Vector.indexWhereOption. |
lastIndexOfOption(A) |
O(n) | O(n), as Vector.lastIndexOfOption. |
lastIndexOfOption(A, int) |
O(n) | O(n), as Vector.lastIndexOfOption. |
lastIndexWhereOption(Predicate<? super A>) |
O(n) | O(n), as Vector.lastIndexWhereOption. |
lastIndexWhereOption(Predicate<? super A>, int) |
O(n) | O(n), as Vector.lastIndexWhereOption. |
indexOfSliceOption(Iterable<? extends A>) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.indexOfSliceOption. |
indexOfSliceOption(Iterable<? extends A>, int) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.indexOfSliceOption. |
lastIndexOfSliceOption(Iterable<? extends A>) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.lastIndexOfSliceOption. |
lastIndexOfSliceOption(Iterable<? extends A>, int) |
O(n * m) | O(n * m) for a slice of m elements, as Vector.lastIndexOfSliceOption. |
tailNonEmpty() |
effectively O(1) | effectively O(1), as Vector.tail. |
initNonEmpty() |
effectively O(1) | effectively O(1), as Vector.init. |
equals(Object) |
O(n) | O(n) when o is a NonEmptyVector of the same size, O(1) otherwise. |
hashCode() |
O(n) | O(n), as Vector.hashCode: computed again at every call. |
HashSet¶
Lookups, insertions and removals are effectively O(1); an insertion or a removal copies a few small arrays and shares the rest with the original set. The methods without a note of their own (map, filter, the folds, the conversions) walk the elements once, O(n), and those that build a new set insert each kept element in effectively O(1).
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(m) | O(m) for m inner elements in total, one effectively O(1) insertion each. |
add(T) |
effectively O(1) | effectively O(1): one hash lookup; a new element also costs a copy of a few small arrays, the rest is shared with this set. |
addAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m elements. A HashSet is merged with this set part by part, and a part only one of them holds is shared without being walked; other elements cost O(m), one effectively O(1) insertion each. O(1) when this set is empty and elements is a HashSet, which is returned as is. |
contains(T) |
effectively O(1) | effectively O(1): one hash lookup. |
diff(Set<? extends T>) |
O(m) | O(m) for a set of m elements, effectively O(1) each, as removeAll; O(n) when it is a HashSet, which is compared with this set part by part: a part of this set that the argument does not reach is kept whole, not walked. A LinkedHashSet larger than this set is not walked: each element of this set is looked up in it, O(n). |
filter(Predicate<? super T>) |
O(n) | O(n), one call of the predicate per element; the parts that lose no element are shared, not copied. |
reject(Predicate<? super T>) |
O(n) | O(n), one call of the predicate per element; the parts that lose no element are shared, not copied. |
containsAll(Iterable<? extends T>) |
O(m) | O(m) for m elements, each an effectively O(1) lookup; a HashSet is compared with this set part by part. |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) (from Set) |
O(n) | O(n): one key, one value and one hash lookup per element, and each group built from its values. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) (from Set) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
intersect(Set<? extends T>) |
O(m) | O(m) for a set of m elements; O(min(n, m)) when it is a HashSet: the elements of the smaller set are checked against the larger one. Another kind of set is first copied into a hash set. |
isEmpty() |
O(1) | O(1). |
size() |
O(1) | O(1): the size is stored, not counted. |
iterator() |
O(1) | O(1) to create; a whole walk is O(n). |
asJava() |
O(1) | O(1): nothing is copied. contains on the view is effectively O(1). |
mapConserve(Function<? super T, ? extends T>) |
O(n) | O(n), effectively: one walk, and the new set built once an element changes. |
partition(Predicate<? super T>) |
O(n) | O(n), one call of the predicate per element, in iteration order; the trie is split node by node, and the parts whose elements all go to one side are shared, not copied. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n): one effectively O(1) insertion per element. |
remove(T) |
effectively O(1) | effectively O(1): one hash lookup, then a copy of a few small arrays; the rest is shared with this set. |
removeAll(Iterable<? extends T>) |
O(m) | O(m) for m given elements, effectively O(1) each, as remove; O(n) when they are a HashSet. Other elements are removed one by one: each node on the path to an element is copied by the first removal that reaches it, and updated in place by the next ones. A HashSet is compared with this set part by part, and a part of this set that the argument does not reach is kept whole, not walked. |
replace(T, T) |
effectively O(1) | effectively O(1): one lookup, one removal and one insertion. |
replaceAll(T, T) |
effectively O(1) | effectively O(1), as replace: a set holds an element once. |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements; O(n) when they are a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it. |
union(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements. A HashSet is merged with this set part by part, and a part only one of them holds is shared without being walked; another kind of set costs O(m), one effectively O(1) insertion per element. This set, or a HashSet argument, is returned as is when the other side is empty. |
toNonEmptySet() |
O(1) | O(1). |
equals(Object) |
O(n log n) | O(n log n) against a TreeSet, as TreeSet.equals; O(n) against a LinkedHashSet: each element of this set is looked up in it; O(n) against a Set of another implementation, with a temporary hash table of this set's elements. O(1) when the sizes differ. Against another HashSet, the two are compared part by part, and a part of a different size or shape answers without looking at an element. |
hashCode() |
O(1) | O(1): the sum of the hashes of the elements is stored. |
max() (from Set) |
O(n) | O(n): every element is compared in its natural order. On a TreeSet, last() gives the greatest element in the set's own order in O(log n). |
min() (from Set) |
O(n) | O(n): every element is compared in its natural order. On a TreeSet, head() gives the least element in the set's own order in O(log n). |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
LinkedHashSet¶
It is a LinkedHashMap of its elements and has the same costs. Lookups, insertions and removals are effectively O(1), on any version of a set, older ones included; finding a position (tail, take, drop) is effectively O(1) too. The methods without a note of their own (map, filter, the folds, the conversions) walk the elements once, O(n).
| Method | Cost | Note |
|---|---|---|
flatten(Iterable<? extends Iterable<? extends T>>) |
O(m) | O(m) for m inner elements in total, one effectively O(1) insertion each. |
add(T) |
effectively O(1) | effectively O(1): one hash lookup; a new element is also inserted and added at the end of the insertion order. |
addAll(Iterable<? extends T>) |
O(m) | O(m) for m elements, each an effectively O(1) add; O(1) when this set is empty and elements is a LinkedHashSet, which is returned as is. |
contains(T) |
effectively O(1) | effectively O(1): one hash lookup. |
diff(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements; O(n) when it is a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it and the kept ones are put in a new set: the whole set is walked even to remove one element, which remove does in effectively O(1). |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) (from Set) |
O(n) | O(n): one key, one value and one hash lookup per element, and each group built from its values. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) (from Set) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
intersect(Set<? extends T>) |
O(n + m) | O(n + m) for a set of m elements; O(n) when it is a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it and the kept ones are put in a new set. |
isEmpty() |
O(1) | O(1). |
size() |
O(1) | O(1): the size is stored, not counted. |
iterator() |
effectively O(1) | effectively O(1) to create; a whole walk is O(n). |
asJava() |
O(1) | O(1): nothing is copied. contains on the view is effectively O(1); its iterators, in either order, walk the whole set in O(n). |
mapConserve(Function<? super T, ? extends T>) |
O(n) | O(n), effectively: one walk, and the new set built once an element changes. The results keep the order of their elements; of two equal results, the first one is kept. |
partitionMap(Function<? super T, ? extends Either<? extends L, ? extends R>>) |
O(n) | O(n): one effectively O(1) insertion per element. |
remove(T) |
effectively O(1) | effectively O(1): one hash removal, and the key taken out of the insertion order on the path from its root, on any version of the set. |
removeAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements; O(n) when they are a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it and the kept ones are put in a new set: the whole set is walked even to remove one element, which remove does in effectively O(1). |
replace(T, T) |
effectively O(1) | effectively O(1): the element is replaced, and newElement is removed from its old position if it is already in the set, as remove. |
replaceAll(T, T) |
effectively O(1) | effectively O(1), as replace: a set holds an element once. |
retainAll(Iterable<? extends T>) |
O(n + m) | O(n + m) for m given elements; O(n) when they are a HashSet. The m elements are put in a hash set (unless they already are one), then every element of this set is checked against it and the kept ones are put in a new set. |
union(Set<? extends T>) |
O(m) | O(m) for a set of m elements, each an effectively O(1) add; this set, or a LinkedHashSet argument, is returned as is when the other side is empty. |
head() |
effectively O(1) | effectively O(1): the first element of the insertion order. |
headOption() |
effectively O(1) | effectively O(1), as head. |
last() |
effectively O(1) | effectively O(1): the last element of the insertion order. |
lastOption() |
effectively O(1) | effectively O(1), as last. |
init() |
effectively O(1) | effectively O(1): the insertion order is cut along one path from its root, and one key is taken out of the hash map, on any version of the set. |
initOption() |
effectively O(1) | effectively O(1), as init. |
tail() |
effectively O(1) | effectively O(1): the insertion order is cut along one path from its root, and one key is taken out of the hash map, on any version of the set. |
tailOption() |
effectively O(1) | effectively O(1), as tail. |
take(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k kept elements: the smaller side, kept or dropped, is added to or taken out of a hash map, and the rest is shared; the insertion order is cut along the paths from its root to the cut. |
takeRight(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k kept elements, as take from the other end. |
takeWhile(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements: one walk, then one take. |
takeUntil(Predicate<? super T>) |
O(k) | O(k) for a prefix of k elements: one walk, then one take. |
drop(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k dropped elements, as take. |
dropRight(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k dropped elements, as take. |
dropWhile(Predicate<? super T>) |
O(k) | O(k) for k dropped elements: one walk, then one drop. |
dropUntil(Predicate<? super T>) |
O(k) | O(k) for k dropped elements: one walk, then one drop. |
zipWithIndex() |
O(n) | O(n). |
grouped(int) |
O(n) | O(n), as sliding with a step of size. |
sliding(int) |
O(n + n * min(size, n - size)) | O(n + n * min(size, n - size)), as sliding with a step of 1. |
sliding(int, int) |
O(n + (n / step) * min(size, n - size)) | O(n + (n / step) * min(size, n - size)): each window costs a take, O(min(size, n - size)). |
slideBy(Function<? super T, ?>) |
O(n) | O(n): one walk, and each run is cut in time proportional to its length. |
equals(Object) |
O(n log n) | O(n log n) against a TreeSet, as TreeSet.equals; O(n) against a HashSet or a LinkedHashSet: each element of this set is looked up in the other one; O(n) against a Set of another implementation, with a temporary hash table of this set's elements. O(1) when the sizes differ. |
hashCode() |
O(n) | O(n): computed from every element on each call; it is not cached. |
max() (from Set) |
O(n) | O(n): every element is compared in its natural order. On a TreeSet, last() gives the greatest element in the set's own order in O(log n). |
min() (from Set) |
O(n) | O(n): every element is compared in its natural order. On a TreeSet, head() gives the least element in the set's own order in O(log n). |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
TreeSet¶
The methods without a note of their own are O(n) at most, one walk over the elements (the folds, find, count, tap, hashCode, toString, toList), except size, isEmpty and comparator, O(1), and containsAll, one lookup per element, O(m log n). toSortedMap and toSortedSet(Comparator) sort, then build the new tree in one pass: O(n log n), O(n) when the new order agrees with this one. The factories ofAll, range, collector and newBuilder do the same: O(m log m) for m elements, O(m) when they come sorted; of, tabulate and fill insert the elements one by one, O(m log m) even when sorted.
| Method | Cost | Note |
|---|---|---|
ofAll(Iterable<? extends T>) |
O(m log m) | O(m log m) for m elements: they are sorted, then the tree is built in one pass; O(m) when they come sorted, and O(1) when values is a TreeSet created without a comparator, or its asJava view: that set is returned as is. |
ofAll(Comparator<? super T>, Iterable<? extends T>) |
O(m log m) | O(m log m) for m elements: they are sorted, then the tree is built in one pass; O(m) when they come sorted, and O(1) when values is a TreeSet, or its asJava view, ordered by the same comparator object: that set is returned as is. |
flatten(Comparator<? super T>, Iterable<? extends Iterable<? extends T>>) |
O(m log m) | O(m log m) for m inner elements in total: each one is inserted into the tree, even when they come sorted. |
flatten(Iterable<? extends Iterable<? extends T>>) |
O(m log m) | O(m log m) for m inner elements in total: each one is inserted into the tree, even when they come sorted. |
add(T) (from SortedSet) |
O(log n) | O(log n): one lookup, then one insertion when the element is new. |
addAll(Iterable<? extends T>) (from SortedSet) |
O(m log(n + m)) | O(m log(n + m)) for m elements. When this set is empty, or when elements is a collection that knows its size and holds at least n elements, they are sorted once and joined with this tree; otherwise each is looked up, and inserted when new. |
asJava() |
O(1) | O(1): nothing is copied. On the view and on its sub-views, contains, size, first, last, ceiling, floor, higher and lower are O(log n); an iterator is O(log n) to create, then O(1) per step on average. |
diff(Set<? extends T>) (from SortedSet) |
O(n + m log n) | O(n + m log n) for a set of m elements: each is looked up in this tree by the comparator. Up to eight elements found (fewer in a tree of fewer than 640 elements, and at least two) are deleted one by one, O(m log n): the tree off the deleted paths is shared. More are removed in one walk of this tree that keeps whole every part that loses no element. When elements is a TreeSet with an equal comparator (for a lambda, the same object), this tree is walked and each element it visits is looked up in the part of the other tree within its bounds, found by going down that tree: O(k log m) for the k nodes visited, at most n and at most about 2m log2 n. A part of this tree that loses no element is kept whole, and nothing of the other tree is copied. |
contains(T) |
O(log n) | O(log n): one walk down the tree, comparing with the comparator, not with equals. |
filter(Predicate<? super T>) |
O(n) | O(n), with no comparator call. |
reject(Predicate<? super T>) |
O(n) | O(n), with no comparator call. |
groupMap(Function<? super T, ? extends K>, Function<? super T, ? extends U>) (from Set) |
O(n) | O(n): one key, one value and one hash lookup per element, and each group built from its values. |
groupMapReduce(Function<? super T, ? extends K>, Function<? super T, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) (from Set) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
intersect(Set<? extends T>) (from SortedSet) |
O(n + m log n) | O(n + m log n) for a set of m elements: each is looked up in this tree by the comparator, then one walk of this tree keeps the elements found and keeps whole every part that loses no element. When elements is a TreeSet with an equal comparator (for a lambda, the same object), the cost is O(m log(n / m + 1)), m then being the smaller of the two sizes: the two trees are cut and joined, not rebuilt. |
size() |
O(1) | O(1): the size is stored. |
iterator() |
O(log n) | O(log n) to create, then O(1) per step on average; a whole walk is O(n). |
mapConserve(Function<? super T, ? extends T>) |
O(n log n) | O(n log n) once an element changes, to build the new set; O(n) when nothing changes. |
collect(Comparator<? super U>, Function<? super T, ? extends Option<? extends U>>) |
O(n log n) | O(n log n): the collected elements are sorted, then the new tree is built in one pass; O(n) when they come out in order. |
partition(Predicate<? super T>) |
O(n) | O(n), with no comparator call. |
remove(T) (from SortedSet) |
O(log n) | O(log n): one walk down the tree, then one deletion on the way back up when the element is present. |
removeAll(Iterable<? extends T>) (from SortedSet) |
O(n + m log n) | O(n + m log n) for m elements: each is looked up in this tree by the comparator. Up to eight elements found (fewer in a tree of fewer than 640 elements, and at least two) are deleted one by one, O(m log n): the tree off the deleted paths is shared. More are removed in one walk of this tree that keeps whole every part that loses no element. A TreeSet with an equal comparator costs what diff of it costs. |
replace(T, T) (from SortedSet) |
O(log n) | O(log n): one lookup, one deletion and one insertion. |
replaceAll(T, T) (from SortedSet) |
O(log n) | O(log n), as replace: a set holds an element once. |
retainAll(Iterable<? extends T>) (from SortedSet) |
O(n + m log n) | O(n + m log n) for m elements: each is looked up in this tree by the comparator, then one walk of this tree keeps the elements found and keeps whole every part that loses no element. A TreeSet with an equal comparator costs what intersect of it costs. |
union(Set<? extends T>) (from SortedSet) |
O(m log(n + m)) | O(m log(n + m)) for a set of m elements. When it holds fewer than n elements, each is looked up, then inserted when new; otherwise they are sorted into a tree, which is cut and joined with this one. When elements is a TreeSet with an equal comparator (for a lambda, the same object), the cost is O(m log(n / m + 1)), m then being the smaller of the two sizes: the two trees are cut and joined, not rebuilt. |
rangeFrom(T) (from SortedSet) |
O(log n) | O(log n): the tree is cut along the path of from without visiting the other elements, and the result shares the rest of the tree. |
rangeUntil(T) (from SortedSet) |
O(log n) | O(log n): the tree is cut along the path of until without visiting the other elements, and the result shares the rest of the tree. |
rangeTo(T) (from SortedSet) |
O(log n) | O(log n): the tree is cut along the path of to without visiting the other elements, and the result shares the rest of the tree. |
rangeFromUntil(T, T) (from SortedSet) |
O(log n) | O(log n): the tree is cut along the paths of the two bounds without visiting the other elements, and the result shares the rest of the tree. |
minAfter(T) (from SortedSet) |
O(log n) | O(log n): one walk down the tree. |
maxBefore(T) (from SortedSet) |
O(log n) | O(log n): one walk down the tree. |
iteratorFrom(T) (from SortedSet) |
O(log n) | O(log n) to create, then O(1) per step on average; a whole walk is O(k + log n) for k elements. |
head() (from SortedSet) |
O(log n) | O(log n): the smallest element is found by walking down the tree, with no comparison. |
last() (from SortedSet) |
O(log n) | O(log n): the largest element is found by walking down the tree, with no comparison. |
init() (from SortedSet) |
O(log n) | O(log n): the tree is cut without visiting the elements, and the result shares the rest of the tree. |
initOption() (from SortedSet) |
O(log n) | O(log n), as init. |
tail() (from SortedSet) |
O(log n) | O(log n): the tree is cut without visiting the elements, and the result shares the rest of the tree. |
tailOption() (from SortedSet) |
O(log n) | O(log n), as tail. |
take(int) (from SortedSet) |
O(log n) | O(log n): the tree is cut at that position without visiting the elements, and the result shares the rest of the tree. |
takeRight(int) (from SortedSet) |
O(log n) | O(log n): the tree is cut at that position without visiting the elements, and the result shares the rest of the tree. |
takeWhile(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for a prefix of k elements: the prefix is walked, then the tree is cut after it. |
takeUntil(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for a prefix of k elements: the prefix is walked, then the tree is cut after it. |
drop(int) (from SortedSet) |
O(log n) | O(log n): the tree is cut at that position without visiting the elements, and the result shares the rest of the tree. |
dropRight(int) (from SortedSet) |
O(log n) | O(log n): the tree is cut at that position without visiting the elements, and the result shares the rest of the tree. |
dropWhile(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for k dropped elements: they are walked, then the tree is cut after them. |
dropUntil(Predicate<? super T>) (from SortedSet) |
O(k + log n) | O(k + log n) for k dropped elements: they are walked, then the tree is cut after them. |
zipWithIndex() (from SortedSet) |
O(n) | O(n): one walk in order. |
grouped(int) (from SortedSet) |
O((n / size) log n) | O((n / size) log n): the tree is cut once per block, in O(log n); the blocks share the tree's structure, and the elements are not copied. |
sliding(int) (from SortedSet) |
O(n log n) | O(n log n): the tree is cut once per window, in O(log n); the windows share the tree's structure, and the elements are not copied. |
sliding(int, int) (from SortedSet) |
O((n / step) log n) | O((n / step) log n): the tree is cut once per window, in O(log n); the windows share the tree's structure, and the elements are not copied. |
slideBy(Function<? super T, ?>) (from SortedSet) |
O(n + k log n) | O(n + k log n) for k runs: one walk finds them, then the tree is cut once per run, in O(log n). |
toNonEmptySortedSet() |
O(1) | O(1). |
equals(Object) |
O(n log n) | O(n log n) against a HashSet or a LinkedHashSet: each of its elements is looked up in this tree by the comparator, and the element found compared with equals. O(n) against a TreeSet with an equal comparator: the two are walked in order, side by side; O(n) against a TreeSet with another comparator, with a temporary hash table of this set's elements. O(1) when the sizes differ. A comparator under which two objects equal by equals compare as different (so that the set can hold both) adds, when the first check cannot decide, one O(n) count of the elements in a temporary hash table. |
flatMap(Comparator<? super U>, Function<? super T, ? extends Iterable<? extends U>>) (from SortedSet) |
O(n + k log k) | O(n + k log k) for k elements produced by mapper: they are sorted, then the new tree is built in one pass; O(n + k) when they come out in order. |
map(Comparator<? super U>, Function<? super T, ? extends U>) (from SortedSet) |
O(n log n) | O(n log n): the results are sorted, then the new tree is built in one pass; O(n) when mapper keeps the order. |
headOption() (from SortedSet) |
O(log n) | O(log n), as head. |
lastOption() (from SortedSet) |
O(log n) | O(log n), as last. |
flatMap(Function<? super T, ? extends Iterable<? extends U>>) (from SortedSet) |
O(n + k log k) | O(n + k log k) for k elements produced by mapper: they are sorted, then the new tree is built in one pass; O(n + k) when they come out in order. |
groupBy(Function<? super T, ? extends C>) (from SortedSet) |
O(n) | O(n): each group gets its elements in order, and its tree is built from them in one pass. |
map(Function<? super T, ? extends U>) (from SortedSet) |
O(n log n) | O(n log n): the results are sorted, then the new tree is built in one pass; O(n) when mapper keeps the order. |
collect(Function<? super T, ? extends Option<? extends U>>) (from SortedSet) |
O(n log n) | O(n log n): the collected elements are sorted, then the new tree is built in one pass; O(n) when they come out in order. |
orElse(Iterable<? extends T>) (from SortedSet) |
O(m log m) | O(m log m) for the m elements of other when this set is empty: they are sorted, then the new tree is built in one pass (O(m) when they come sorted); O(1) when this set is not empty. |
orElse(Supplier<? extends Iterable<? extends T>>) (from SortedSet) |
O(m log m) | O(m log m) for the m supplied elements when this set is empty: they are sorted, then the new tree is built in one pass (O(m) when they come sorted); O(1) when this set is not empty, and the supplier is not called. |
max() (from Set) |
O(n) | O(n): every element is compared in its natural order. On a TreeSet, last() gives the greatest element in the set's own order in O(log n). |
min() (from Set) |
O(n) | O(n): every element is compared in its natural order. On a TreeSet, head() gives the least element in the set's own order in O(log n). |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
NonEmptySet¶
| Method | Cost | Note |
|---|---|---|
fromSet(HashSet<A>) |
O(1) | O(1). |
unsafeFromSet(HashSet<A>) |
O(1) | O(1). |
add(A) |
effectively O(1) | effectively O(1), as HashSet.add. |
addAll(Iterable<? extends A>) |
O(m) | O(m) for m elements, each an effectively O(1) insertion, as HashSet.addAll. |
union(Set<? extends A>) |
O(m) | O(m) for a set of m elements, each an effectively O(1) insertion, as HashSet.union. |
replace(A, A) |
effectively O(1) | effectively O(1), as HashSet.replace. |
replaceAll(A, A) |
effectively O(1) | effectively O(1), as replace: a set holds an element once. |
groupMap(Function<? super A, ? extends K>, Function<? super A, ? extends B>) |
O(n) | O(n): one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super A, ? extends K>, Function<? super A, ? extends B>, BiFunction<? super B, ? super B, ? extends B>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
sizeCompare(int) |
O(1) | O(1): the stored size is compared. |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most; O(1) when the size of that is stored. |
toSet() |
O(1) | O(1). |
remove(A) |
effectively O(1) | effectively O(1), as HashSet.remove. |
removeAll(Iterable<? extends A>) |
O(m) | O(m) for m given elements, as HashSet.removeAll. |
retainAll(Iterable<? extends A>) |
O(n + m) | O(n + m) for m given elements, as HashSet.retainAll. |
intersect(Set<? extends A>) |
O(n + m) | O(n + m) for a set of m elements, as HashSet.intersect. |
diff(Set<? extends A>) |
O(m) | O(m) for a set of m elements; O(n) for a LinkedHashSet larger than this set, as HashSet.diff. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
sumInt(ToIntFunction<? super A>) |
O(n) | O(n). |
sumLong(ToLongFunction<? super A>) |
O(n) | O(n). |
sumDouble(ToDoubleFunction<? super A>) |
O(n) | O(n). |
productInt(ToIntFunction<? super A>) |
O(n) | O(n). |
productLong(ToLongFunction<? super A>) |
O(n) | O(n). |
productDouble(ToDoubleFunction<? super A>) |
O(n) | O(n). |
average(ToDoubleFunction<? super A>) |
O(n) | O(n), one compensated pass. |
size() |
O(1) | O(1): the size is stored. |
contains(A) |
effectively O(1) | effectively O(1), as HashSet.contains. |
iterator() |
O(1) | O(1) to create; a whole walk is O(n), as HashSet.iterator. |
asJava() |
O(1) | O(1); contains on the view is effectively O(1). |
NonEmptySortedSet¶
| Method | Cost | Note |
|---|---|---|
fromSortedSet(TreeSet<A>) |
O(1) | O(1). |
unsafeFromSortedSet(TreeSet<A>) |
O(1) | O(1). |
flatten(NonEmptySortedSet<? extends NonEmptySortedSet<? extends A>>) |
O(n log n) | O(n log n) comparisons for n inner elements in total, as TreeSet.flatten. |
flatten(Comparator<? super A>, NonEmptySortedSet<? extends NonEmptySortedSet<? extends A>>) |
O(n log n) | O(n log n) comparisons for n inner elements in total, that of TreeSet.flatten. |
add(A) |
O(log n) | O(log n), as TreeSet.add. |
addAll(Iterable<? extends A>) |
O(m log(n + m)) | O(m log(n + m)) for m elements, as TreeSet.addAll. |
union(Set<? extends A>) |
O(m log(n + m)) | O(m log(n + m)) for a set of m elements, as TreeSet.union. |
replace(A, A) |
O(log n) | O(log n), as TreeSet.replace. |
replaceAll(A, A) |
O(log n) | O(log n), as replace: a set holds an element once. |
groupMap(Function<? super A, ? extends K>, Function<? super A, ? extends B>) |
O(n) | O(n): one key, one value and one hash lookup per element. |
groupMapReduce(Function<? super A, ? extends K>, Function<? super A, ? extends B>, BiFunction<? super B, ? super B, ? extends B>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per element. |
sizeCompare(int) |
O(1) | O(1): the stored size is compared. |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most; O(1) when the size of that is stored. |
grouped(int) |
O((n / size) log n) | O((n / size) log n), as TreeSet.grouped. |
sliding(int) |
O(n log n) | O(n log n), as TreeSet.sliding. |
sliding(int, int) |
O((n / step) log n) | O((n / step) log n), as TreeSet.sliding. |
slideBy(Function<? super A, ?>) |
O(n + k log n) | O(n + k log n) for k runs, as TreeSet.slideBy. |
zipWithIndex() |
O(n) | O(n), as TreeSet.zipWithIndex. |
toSortedSet() |
O(1) | O(1). |
remove(A) |
O(log n) | O(log n), as TreeSet.remove. |
removeAll(Iterable<? extends A>) |
O(n + m log n) | O(n + m log n) for m given elements, as TreeSet.removeAll. |
retainAll(Iterable<? extends A>) |
O(n + m log n) | O(n + m log n) for m given elements, as TreeSet.retainAll. |
intersect(Set<? extends A>) |
O(n + m log n) | O(n + m log n) for a set of m elements, as TreeSet.intersect. |
diff(Set<? extends A>) |
O(n + m log n) | O(n + m log n) for a set of m elements, as TreeSet.diff. |
tail() |
O(log n) | O(log n), as TreeSet.tail. |
init() |
O(log n) | O(log n), as TreeSet.init. |
take(int) |
O(log n) | O(log n), as TreeSet.take. |
takeRight(int) |
O(log n) | O(log n), as TreeSet.takeRight. |
takeWhile(Predicate<? super A>) |
O(k + log n) | O(k + log n) for a prefix of k elements, as TreeSet.takeWhile. |
takeUntil(Predicate<? super A>) |
O(k + log n) | O(k + log n) for a prefix of k elements, as TreeSet.takeUntil. |
drop(int) |
O(log n) | O(log n), as TreeSet.drop. |
dropRight(int) |
O(log n) | O(log n), as TreeSet.dropRight. |
dropWhile(Predicate<? super A>) |
O(k + log n) | O(k + log n) for k dropped elements, as TreeSet.dropWhile. |
dropUntil(Predicate<? super A>) |
O(k + log n) | O(k + log n) for k dropped elements, as TreeSet.dropUntil. |
head() |
O(log n) | O(log n), as TreeSet.head. |
last() |
O(log n) | O(log n), as TreeSet.last. |
max() |
O(n) | O(n), every element compared once. |
min() |
O(n) | O(n), every element compared once. |
sumInt(ToIntFunction<? super A>) |
O(n) | O(n). |
sumLong(ToLongFunction<? super A>) |
O(n) | O(n). |
sumDouble(ToDoubleFunction<? super A>) |
O(n) | O(n). |
productInt(ToIntFunction<? super A>) |
O(n) | O(n). |
productLong(ToLongFunction<? super A>) |
O(n) | O(n). |
productDouble(ToDoubleFunction<? super A>) |
O(n) | O(n). |
average(ToDoubleFunction<? super A>) |
O(n) | O(n), one compensated pass. |
size() |
O(1) | O(1): the size is stored. |
contains(A) |
O(log n) | O(log n), as TreeSet.contains. |
iterator() |
O(1) | O(1) to create; a whole walk is O(n), in the comparator's order. |
asJava() |
O(1) | O(1); contains on the view is O(log n). |
rangeFrom(A) |
O(log n) | O(log n), as TreeSet.rangeFrom. |
rangeUntil(A) |
O(log n) | O(log n), as TreeSet.rangeUntil. |
rangeTo(A) |
O(log n) | O(log n), as TreeSet.rangeTo. |
rangeFromUntil(A, A) |
O(log n) | O(log n), as TreeSet.rangeFromUntil. |
minAfter(A) |
O(log n) | O(log n), as TreeSet.minAfter. |
maxBefore(A) |
O(log n) | O(log n), as TreeSet.maxBefore. |
iteratorFrom(A) |
O(log n) | O(log n) to create, then O(1) per step on average, as TreeSet.iteratorFrom. |
tailNonEmpty() |
O(log n) | O(log n), as TreeSet.tail. |
initNonEmpty() |
O(log n) | O(log n), as TreeSet.init. |
HashMap¶
Lookups, insertions and removals by key are effectively O(1); an insertion or a removal copies a few small arrays and shares the rest with the original map. The methods without a note of their own (map, filter, the folds, the conversions) walk the entries once, O(n), and those that build a new map insert each kept entry in effectively O(1).
| Method | Cost | Note |
|---|---|---|
computeIfAbsent(K, Function<? super K, ? extends V>) |
effectively O(1) | effectively O(1): one lookup, and one put when the key is absent. |
computeIfPresent(K, BiFunction<? super K, ? super V, ? extends V>) |
effectively O(1) | effectively O(1): one lookup, and one put when the key is present. |
contains(Tuple2<K, V>) |
effectively O(1) | effectively O(1): one lookup of the key, then its value is compared. |
containsKey(K) |
effectively O(1) | effectively O(1): one hash lookup. |
filter(BiPredicate<? super K, ? super V>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
reject(BiPredicate<? super K, ? super V>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
filter(Predicate<? super Tuple2<K, V>>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
reject(Predicate<? super Tuple2<K, V>>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
filterKeys(Predicate<? super K>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
rejectKeys(Predicate<? super K>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
filterValues(Predicate<? super V>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
rejectValues(Predicate<? super V>) |
O(n) | O(n), one call of the predicate per entry; the parts that lose no entry are shared, not copied. |
forEach(BiConsumer<K, V>) |
O(n) | O(n): one walk over the entries, with no Tuple2 made for each. |
get(K) |
effectively O(1) | effectively O(1): one hash lookup. |
getOrElse(K, V) |
effectively O(1) | effectively O(1): one hash lookup. |
getOrElse(K, Supplier<? extends V>) |
effectively O(1) | effectively O(1): one hash lookup. |
groupMap(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>) (from Map) |
O(n) | O(n): one key, one value and one hash lookup per entry. |
groupMapReduce(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) (from Map) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per entry. |
isEmpty() |
O(1) | O(1). |
iterator() |
O(1) | O(1) to create; a whole walk is O(n). |
keySet() |
O(n) | O(n), with no hashing and no key comparison: the keys are copied from the trie of the entries, in the same shape. |
mapValues(Function<? super V, ? extends V2>) |
O(n) | O(n), one call of the mapper per entry; the keys keep their places, so nothing is hashed again. |
merge(Map<? extends K, ? extends V>) |
O(n + m) | O(n + m) for a map of m entries. When that map is a HashMap, the two maps are merged part by part, and a part only one of them holds is shared without being walked. For another map, O(m): one lookup and at most one put per entry. O(1) when that map is empty, or when this map is empty and that map is a HashMap, which is returned as is. |
merge(Map<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
O(m) | O(m) for a map of m entries, one lookup and one put each; O(1) when that map is empty, or when this map is empty and that map is a HashMap, which is returned as is. |
partition(Predicate<? super Tuple2<K, V>>) |
O(n) | O(n), one call of the predicate per entry, in iteration order; the trie is split node by node, and the parts whose entries all go to one side are shared, not copied. |
partition(BiPredicate<? super K, ? super V>) |
O(n) | O(n), one call of the predicate per entry, in iteration order, with no Tuple2 made for each; the trie is split node by node, and the parts whose entries all go to one side are shared, not copied. |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1): one lookup and one put. |
put(K, V) |
effectively O(1) | effectively O(1): one hash lookup, then a copy of a few small arrays; the rest is shared with this map. |
put(Tuple2<? extends K, ? extends V>) |
effectively O(1) | effectively O(1), as put. |
putAll(Iterable<? extends Tuple2<? extends K, ? extends V>>) |
O(n + m) | O(n + m) for a HashMap of m entries (or the asJava view of one): the two maps are merged part by part, and a part only one of them holds is shared without being walked. For other entries, O(m): one effectively O(1) put each. O(1) when either map is empty. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1): one lookup and one put. |
remove(K) |
effectively O(1) | effectively O(1): one hash lookup, then a copy of a few small arrays; the rest is shared with this map. |
updateWith(K, Function<? super Option<V>, ? extends Option<? extends V>>) |
effectively O(1) | effectively O(1): one hash lookup, then at most one put or remove. |
removeAll(Iterable<? extends K>) |
O(m) | O(m) for m given keys, each an effectively O(1) removal. |
replace(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1): one lookup, one removal and one insertion. |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1), as replace: a map holds an entry once. |
replaceValue(K, V) |
effectively O(1) | effectively O(1): one lookup, and one put when the key is present. |
replace(K, V, V) |
effectively O(1) | effectively O(1): one lookup, and one put when the key maps to oldValue. |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) |
O(n) | O(n): every entry is mapped and put in a new map. |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(m) | O(m) for m given entries: each is looked up in this map and, when present, this map's entry is put in a new map. |
size() |
O(1) | O(1): the size is stored, not counted. |
asJavaMap() |
O(1) | O(1): nothing is copied. get and containsKey on the view are effectively O(1). |
values() |
O(n) | O(n): the values are copied into a new Vector. |
toNonEmptyMap() |
O(1) | O(1). |
equals(Object) |
O(n log n) | O(n log n) against a TreeMap, as TreeMap.equals; O(n) against a LinkedHashMap: each entry of this map is looked up in it. O(1) when the sizes differ. Against another HashMap, the two are compared part by part, and a part of a different size or shape answers without looking at a key. |
hashCode() |
O(n) | O(n): computed from every entry on each call; it is not cached. |
containsValue(V) (from Map) |
O(n) | O(n): the entries are walked until the value is found; values are not indexed. |
max() (from Map) |
O(n) | O(n): every entry is compared in the natural order of its key, then of its value. |
min() (from Map) |
O(n) | O(n): every entry is compared in the natural order of its key, then of its value. |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
asJava() (from Traversable) |
O(1) | O(1): nothing is copied. On the view, contains costs what this collection's own contains costs. |
LinkedHashMap¶
Lookups, insertions and removals are effectively O(1), on any version of a map, older ones included; finding a position (tail, take, drop) is effectively O(1) too. The methods without a note of their own (map, filter, the folds, the conversions) walk the entries once, O(n).
| Method | Cost | Note |
|---|---|---|
computeIfAbsent(K, Function<? super K, ? extends V>) |
effectively O(1) | effectively O(1): one lookup, and one put when the key is absent. |
computeIfPresent(K, BiFunction<? super K, ? super V, ? extends V>) |
effectively O(1) | effectively O(1): one lookup, and one put when the key is present. |
contains(Tuple2<K, V>) |
effectively O(1) | effectively O(1): one lookup of the key, then its value is compared. |
containsKey(K) |
effectively O(1) | effectively O(1): one hash lookup. |
get(K) |
effectively O(1) | effectively O(1): one hash lookup. |
getOrElse(K, V) |
effectively O(1) | effectively O(1): one hash lookup. |
getOrElse(K, Supplier<? extends V>) |
effectively O(1) | effectively O(1): one hash lookup. |
groupMap(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>) (from Map) |
O(n) | O(n): one key, one value and one hash lookup per entry. |
groupMapReduce(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) (from Map) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per entry. |
isEmpty() |
O(1) | O(1). |
iterator() |
effectively O(1) | effectively O(1) to create; a whole walk is O(n), one hash lookup per entry. |
asJavaMap() |
O(1) | O(1): nothing is copied. get and containsKey on the view are effectively O(1); its iterators, in either order, walk the whole map in O(n). |
keySet() |
O(1) | O(1): a LinkedHashSet view that shares this map; nothing is copied. |
merge(Map<? extends K, ? extends V>) |
O(m) | O(m) for a map of m entries, one lookup and at most one put each; O(1) when that map is empty, or when this map is empty and that map is a LinkedHashMap, which is returned as is. |
merge(Map<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
O(m) | O(m) for a map of m entries, one lookup and one put each; O(1) when that map is empty, or when this map is empty and that map is a LinkedHashMap, which is returned as is. |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1): one lookup and one put. |
put(K, V) |
effectively O(1) | effectively O(1): one hash lookup and one insertion. An existing key keeps its position; a new key is added at the end of the insertion order. |
put(Tuple2<? extends K, ? extends V>) |
effectively O(1) | effectively O(1), as put. |
putAll(Iterable<? extends Tuple2<? extends K, ? extends V>>) |
O(m) | O(m) for m entries, one effectively O(1) put each. When this map is empty, the entries are built into a new map as ofEntries does, and a LinkedHashMap is returned as is. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1): one lookup and one put. |
remove(K) |
effectively O(1) | effectively O(1): one hash removal, and the key taken out of the insertion order on the path from its root, on any version of the map. |
updateWith(K, Function<? super Option<V>, ? extends Option<? extends V>>) |
effectively O(1) | effectively O(1): one hash lookup, then at most one put or one remove. |
removeAll(Iterable<? extends K>) |
O(n + m) | O(n + m) for m given keys: they are put in a hash set, every entry of this map is checked against it, and the map is rebuilt without the removed ones. |
replace(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1): the entry is replaced, and an entry of the key of newElement elsewhere in the map is removed, as remove. |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1), as replace: a map holds an entry once. The new entry takes the position of the replaced one. |
replaceValue(K, V) |
effectively O(1) | effectively O(1): one lookup, and one put when the key is present. |
replace(K, V, V) |
effectively O(1) | effectively O(1): one lookup, and one put of the existing key when it maps to oldValue. |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) |
O(n) | O(n): every entry is mapped and put in a new map. |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(n + m) | O(n + m) for m given entries: they are put in a hash set, then every entry of this map is checked against it and the kept ones are put in a new map. |
size() |
O(1) | O(1): the size is stored, not counted. |
values() |
O(n) | O(n): the values are copied into a new Vector. |
head() |
effectively O(1) | effectively O(1): the first key of the insertion order, found from its root, then one hash lookup. |
headOption() |
effectively O(1) | effectively O(1), as head. |
last() |
effectively O(1) | effectively O(1): the last key of the insertion order, found from its root, then one hash lookup. |
lastOption() |
effectively O(1) | effectively O(1), as last. |
init() |
effectively O(1) | effectively O(1): the insertion order is cut along one path from its root, and one key is taken out of the hash map, on any version of the map. |
initOption() |
effectively O(1) | effectively O(1), as init. |
tail() |
effectively O(1) | effectively O(1): the insertion order is cut along one path from its root, and one key is taken out of the hash map, on any version of the map. |
tailOption() |
effectively O(1) | effectively O(1), as tail. |
take(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k kept entries: the smaller side, kept or dropped, is added to or taken out of a hash map, and the rest is shared; the insertion order is cut along the paths from its root to the cut. |
takeRight(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k kept entries, as take from the other end. |
takeWhile(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for a prefix of k entries: one walk, then one take. |
takeUntil(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for a prefix of k entries: one walk, then one take. |
drop(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k dropped entries, as take. |
dropRight(int) |
O(min(k, n - k)) | O(min(k, n - k)) for k dropped entries, as take. |
dropWhile(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for k dropped entries: one walk, then one drop. |
dropUntil(Predicate<? super Tuple2<K, V>>) |
O(k) | O(k) for k dropped entries: one walk, then one drop. |
zipWithIndex() |
O(n) | O(n). |
grouped(int) |
O(n) | O(n), as sliding with a step of size. |
sliding(int) |
O(n + n * min(size, n - size)) | O(n + n * min(size, n - size)), as sliding with a step of 1. |
sliding(int, int) |
O(n + (n / step) * min(size, n - size)) | O(n + (n / step) * min(size, n - size)): each window costs a take, O(min(size, n - size)). |
slideBy(Function<? super Tuple2<K, V>, ?>) |
O(n) | O(n): one walk, and each run is cut in time proportional to its length. |
equals(Object) |
O(n log n) | O(n log n) against a TreeMap, as TreeMap.equals; O(n) against a HashMap or a LinkedHashMap: each entry of this map is looked up in the other one. O(1) when the sizes differ. |
hashCode() |
O(n) | O(n): computed from every entry on each call; it is not cached. |
containsValue(V) (from Map) |
O(n) | O(n): the entries are walked until the value is found; values are not indexed. |
max() (from Map) |
O(n) | O(n): every entry is compared in the natural order of its key, then of its value. |
min() (from Map) |
O(n) | O(n): every entry is compared in the natural order of its key, then of its value. |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
asJava() (from Traversable) |
O(1) | O(1): nothing is copied. On the view, contains costs what this collection's own contains costs. |
TreeMap¶
The methods without a note of their own are O(n) at most, one walk over the entries (the folds, find, count, tap, hashCode, toString, toList), except size, isEmpty and comparator, O(1), and containsAll, one lookup per entry, O(m log n). toSortedMap and toSortedSet sort, then build the new tree in one pass: O(n log n), O(n) when the new order agrees with the key order. The factories ofAll, ofEntries, tabulate, fill, collector and newBuilder do the same: O(m log m) for m entries, O(m) when they come sorted. of and the ofAll overloads that take a java.util.stream.Stream insert the entries one by one: O(m log m) even when they come sorted.
| Method | Cost | Note |
|---|---|---|
ofAll(Map<? extends K, ? extends V>) |
O(m log m) | O(m log m) for m entries: they are sorted, then the tree is built in one pass; O(m) when they come sorted, and O(1) when map is the asJavaMap view of a TreeMap created without a comparator: that map is returned as is. |
ofAll(Comparator<? super K>, Map<? extends K, ? extends V>) |
O(m log m) | O(m log m) for m entries: they are sorted, then the tree is built in one pass; O(m) when they come sorted, and O(1) when map is the asJavaMap view of a TreeMap ordered by the same comparator object: that map is returned as is. |
contains(Tuple2<K, V>) |
O(log n) | O(log n): one lookup of the key, then the value found is compared with equals. |
containsKey(K) |
O(log n) | O(log n): one walk down the tree, comparing keys with the comparator. |
filter(BiPredicate<? super K, ? super V>) |
O(n) | O(n), with no comparator call. |
reject(BiPredicate<? super K, ? super V>) |
O(n) | O(n), with no comparator call. |
filter(Predicate<? super Tuple2<K, V>>) |
O(n) | O(n), with no comparator call. |
reject(Predicate<? super Tuple2<K, V>>) |
O(n) | O(n), with no comparator call. |
filterKeys(Predicate<? super K>) |
O(n) | O(n), with no comparator call. |
rejectKeys(Predicate<? super K>) |
O(n) | O(n), with no comparator call. |
filterValues(Predicate<? super V>) |
O(n) | O(n), with no comparator call. |
rejectValues(Predicate<? super V>) |
O(n) | O(n), with no comparator call. |
get(K) |
O(log n) | O(log n): one walk down the tree, comparing keys with the comparator. |
getOrElse(K, V) |
O(log n) | O(log n), as get. |
getOrElse(K, Supplier<? extends V>) |
O(log n) | O(log n), as get. |
groupMap(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>) (from Map) |
O(n) | O(n): one key, one value and one hash lookup per entry. |
groupMapReduce(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) (from Map) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per entry. |
iterator() |
O(log n) | O(log n) to create, then O(1) per step on average; a whole walk is O(n). |
keySet() (from SortedMap) |
O(n) | O(n), with no comparison: the keys are copied from the tree of the entries, in the same shape. |
mapValues(Function<? super V, ? extends W>) |
O(n) | O(n), with no key comparison (a copy of the tree, with the same shape and the new values). |
partition(Predicate<? super Tuple2<K, V>>) |
O(n) | O(n), with no comparator call. |
partition(BiPredicate<? super K, ? super V>) |
O(n) | O(n), with no comparator call. |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) (from SortedMap) |
O(log n) | O(log n): one lookup, then one insertion. |
put(K, V) (from SortedMap) |
O(log n) | O(log n): one insertion; an entry with an equal key is replaced. |
put(Tuple2<? extends K, ? extends V>) (from SortedMap) |
O(log n) | O(log n): one insertion; an entry with an equal key is replaced. |
putAll(Iterable<? extends Tuple2<? extends K, ? extends V>>) (from SortedMap) |
O(m log(n + m)) | O(m log(n + m)) for m entries, one insertion each. When entries is a TreeMap with an equal comparator (for a lambda, the same object), the cost is O(m log(n / m + 1)), m then being the smaller of the two sizes: the two trees are cut and joined, not rebuilt. O(1) when entries is an empty map. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) (from SortedMap) |
O(log n) | O(log n): one lookup, then one insertion. |
remove(K) (from SortedMap) |
O(log n) | O(log n): one walk down the tree, then one deletion on the way back up when the key is present. |
updateWith(K, Function<? super Option<V>, ? extends Option<? extends V>>) (from SortedMap) |
O(log n) | O(log n): one lookup, then at most one insertion or deletion. |
removeAll(Iterable<? extends K>) (from SortedMap) |
O(m log n) | O(m log n) for m keys: one walk down the tree each, then one deletion for each key present. |
replace(Tuple2<K, V>, Tuple2<K, V>) (from SortedMap) |
O(log n) | O(log n): one lookup, one deletion and one insertion. |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) (from SortedMap) |
O(log n) | O(log n), as replace: a map holds an entry once. |
replace(K, V, V) (from SortedMap) |
O(log n) | O(log n): one lookup, then one insertion. |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) (from SortedMap) |
O(n) | O(n), with no comparison: the tree is copied in the same shape, with the new values. |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(m log n) | O(m log n) for m given entries: each is looked up in this map, and the entries of this map found, at most n, are sorted into a new tree. |
size() |
O(1) | O(1): the size is stored. |
values() |
O(n) | O(n): one walk in key order, the values copied into a Vector. |
toNonEmptySortedMap() |
O(1) | O(1). |
rangeFrom(K) (from SortedMap) |
O(log n) | O(log n): the tree is cut along the path of from without visiting the other entries, and the result shares the rest of the tree. |
rangeUntil(K) (from SortedMap) |
O(log n) | O(log n): the tree is cut along the path of until without visiting the other entries, and the result shares the rest of the tree. |
rangeTo(K) (from SortedMap) |
O(log n) | O(log n): the tree is cut along the path of to without visiting the other entries, and the result shares the rest of the tree. |
rangeFromUntil(K, K) (from SortedMap) |
O(log n) | O(log n): the tree is cut along the paths of the two bounds without visiting the other entries, and the result shares the rest of the tree. |
minAfter(K) (from SortedMap) |
O(log n) | O(log n): one walk down the tree. |
maxBefore(K) (from SortedMap) |
O(log n) | O(log n): one walk down the tree. |
iteratorFrom(K) (from SortedMap) |
O(log n) | O(log n) to create, then O(1) per step on average; a whole walk is O(k + log n) for k entries. |
head() (from SortedMap) |
O(log n) | O(log n): the entry with the smallest key is found by walking down the tree, with no comparison. |
last() (from SortedMap) |
O(log n) | O(log n): the entry with the largest key is found by walking down the tree, with no comparison. |
init() (from SortedMap) |
O(log n) | O(log n): the tree is cut without visiting the entries, and the result shares the rest of the tree. |
initOption() (from SortedMap) |
O(log n) | O(log n), as init. |
tail() (from SortedMap) |
O(log n) | O(log n): the tree is cut without visiting the entries, and the result shares the rest of the tree. |
tailOption() (from SortedMap) |
O(log n) | O(log n), as tail. |
take(int) (from SortedMap) |
O(log n) | O(log n): the tree is cut at that position without visiting the entries, and the result shares the rest of the tree. |
takeRight(int) (from SortedMap) |
O(log n) | O(log n): the tree is cut at that position without visiting the entries, and the result shares the rest of the tree. |
takeWhile(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for a prefix of k entries: the prefix is walked, then the tree is cut after it. |
takeUntil(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for a prefix of k entries: the prefix is walked, then the tree is cut after it. |
drop(int) (from SortedMap) |
O(log n) | O(log n): the tree is cut at that position without visiting the entries, and the result shares the rest of the tree. |
dropRight(int) (from SortedMap) |
O(log n) | O(log n): the tree is cut at that position without visiting the entries, and the result shares the rest of the tree. |
dropWhile(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for k dropped entries: they are walked, then the tree is cut after them. |
dropUntil(Predicate<? super Tuple2<K, V>>) (from SortedMap) |
O(k + log n) | O(k + log n) for k dropped entries: they are walked, then the tree is cut after them. |
zipWithIndex() (from SortedMap) |
O(n) | O(n): one walk in key order. |
grouped(int) (from SortedMap) |
O((n / size) log n) | O((n / size) log n): the tree is cut once per block, in O(log n); the blocks share the tree's structure, and the entries are not copied. |
sliding(int) (from SortedMap) |
O(n log n) | O(n log n): the tree is cut once per window, in O(log n); the windows share the tree's structure, and the entries are not copied. |
sliding(int, int) (from SortedMap) |
O((n / step) log n) | O((n / step) log n): the tree is cut once per window, in O(log n); the windows share the tree's structure, and the entries are not copied. |
slideBy(Function<? super Tuple2<K, V>, ?>) (from SortedMap) |
O(n + k log n) | O(n + k log n) for k runs: one walk finds them, then the tree is cut once per run, in O(log n). |
equals(Object) |
O(n log n) | O(n log n) against a HashMap or a LinkedHashMap: the key of each of its entries is looked up in this tree by the comparator, and the entry found compared with equals. O(n) against a TreeMap with an equal comparator: the two are walked in order, side by side; O(n) against a TreeMap with another comparator, with a temporary hash table of this map's entries. O(1) when the sizes differ. A comparator under which two keys equal by equals compare as different (so that the map can hold both) adds, when the first check cannot decide, one O(n) count of the entries in a temporary hash table. |
asJavaMap() |
O(1) | O(1): nothing is copied. On the view and on its sub-views, get, containsKey, size, firstKey, lastKey and the ceiling, floor, higher and lower lookups are O(log n); an iterator is O(log n) to create, then O(1) per step on average. |
mapBoth(Comparator<? super K2>, Function<? super K, ? extends K2>, Function<? super V, ? extends V2>) (from SortedMap) |
O(n log n) | O(n log n): the new entries are sorted, then the new tree is built in one pass; O(n) when the new keys come out in order. |
flatMap(Comparator<? super K2>, BiFunction<? super K, ? super V, ? extends Iterable<Tuple2<K2, V2>>>) (from SortedMap) |
O(n + k log k) | O(n + k log k) for k entries produced by mapper: they are sorted, then the new tree is built in one pass; O(n + k) when their keys come out in order. |
collect(Comparator<? super K2>, BiFunction<? super K, ? super V, ? extends Option<? extends Tuple2<K2, V2>>>) (from SortedMap) |
O(n log n) | O(n log n): the collected entries are sorted, then the new tree is built in one pass; O(n) when their keys come out in order. |
map(Comparator<? super K2>, BiFunction<? super K, ? super V, Tuple2<K2, V2>>) (from SortedMap) |
O(n log n) | O(n log n): the new entries are sorted, then the new tree is built in one pass; O(n) when the new keys come out in order. |
headOption() (from SortedMap) |
O(log n) | O(log n), as head. |
lastOption() (from SortedMap) |
O(log n) | O(log n), as last. |
mapBoth(Function<? super K, ? extends K2>, Function<? super V, ? extends V2>) (from SortedMap) |
O(n log n) | O(n log n): the new entries are sorted, then the new tree is built in one pass; O(n) when the new keys come out in order. |
computeIfAbsent(K, Function<? super K, ? extends V>) (from SortedMap) |
O(log n) | O(log n): one lookup, then one insertion when the key is absent. |
computeIfPresent(K, BiFunction<? super K, ? super V, ? extends V>) (from SortedMap) |
O(log n) | O(log n): one lookup, then one insertion when the key is present. |
flatMap(BiFunction<? super K, ? super V, ? extends Iterable<Tuple2<K2, V2>>>) (from SortedMap) |
O(n + k log k) | O(n + k log k) for k entries produced by mapper: they are sorted, then the new tree is built in one pass; O(n + k) when their keys come out in order. |
groupBy(Function<? super Tuple2<K, V>, ? extends C>) (from SortedMap) |
O(n) | O(n): each group gets its entries in order, and its tree is built from them in one pass. |
collect(BiFunction<? super K, ? super V, ? extends Option<? extends Tuple2<K2, V2>>>) (from SortedMap) |
O(n log n) | O(n log n): the collected entries are sorted, then the new tree is built in one pass; O(n) when their keys come out in order. |
map(BiFunction<? super K, ? super V, Tuple2<K2, V2>>) (from SortedMap) |
O(n log n) | O(n log n): the new entries are sorted, then the new tree is built in one pass; O(n) when the new keys come out in order. |
mapKeys(Function<? super K, ? extends K2>) (from SortedMap) |
O(n log n) | O(n log n): the new entries are sorted, then the new tree is built in one pass; O(n) when the new keys come out in order. |
mapKeys(Function<? super K, ? extends K2>, BiFunction<? super V, ? super V, ? extends V>) (from SortedMap) |
O(n log n) | O(n log n): one lookup and one insertion in a new tree per entry. |
merge(Map<? extends K, ? extends V>) (from SortedMap) |
O(m log(n + m)) | O(m log(n + m)) for the m entries of that: one lookup and at most one insertion each. When this map is empty, the entries of that are sorted and built into a new tree, O(m log m), and a TreeMap with an equal comparator is returned as it is, O(1). |
merge(Map<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) (from SortedMap) |
O(m log(n + m)) | O(m log(n + m)) for the m entries of that: one lookup and at most one insertion each. When this map is empty, the entries of that are sorted and built into a new tree, O(m log m). |
orElse(Iterable<? extends Tuple2<K, V>>) (from SortedMap) |
O(m log m) | O(m log m) for the m entries of other when this map is empty: they are sorted, then the new tree is built in one pass (O(m) when they come sorted); O(1) when this map is not empty. |
orElse(Supplier<? extends Iterable<? extends Tuple2<K, V>>>) (from SortedMap) |
O(m log m) | O(m log m) for the m supplied entries when this map is empty: they are sorted, then the new tree is built in one pass (O(m) when they come sorted); O(1) when this map is not empty, and the supplier is not called. |
replaceValue(K, V) (from SortedMap) |
O(log n) | O(log n): one lookup, then one insertion when the key is present. |
containsValue(V) (from Map) |
O(n) | O(n): the entries are walked until the value is found; values are not indexed. |
max() (from Map) |
O(n) | O(n): every entry is compared in the natural order of its key, then of its value. |
min() (from Map) |
O(n) | O(n): every entry is compared in the natural order of its key, then of its value. |
sizeCompare(int) (from Traversable) |
O(1) | O(1): the stored size is compared. List, Queue and LazyList count their elements up to otherSize + 1. |
sizeCompare(Iterable<?>) (from Traversable) |
O(min(n, m)) | O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when both are stored (Vector, the sets, the maps and the non-empty collections store theirs). A JDK collection is iterated, not asked its size, which may cost a walk or never return. |
asJava() (from Traversable) |
O(1) | O(1): nothing is copied. On the view, contains costs what this collection's own contains costs. |
NonEmptyMap¶
| Method | Cost | Note |
|---|---|---|
fromMap(HashMap<K, V>) |
O(1) | O(1). |
unsafeFromMap(HashMap<K, V>) |
O(1) | O(1). |
put(K, V) |
effectively O(1) | effectively O(1), as HashMap.put. |
put(Tuple2<? extends K, ? extends V>) |
effectively O(1) | effectively O(1), as HashMap.put. |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1), as HashMap.put. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
effectively O(1) | effectively O(1), as HashMap.put. |
putAll(Iterable<? extends Tuple2<? extends K, ? extends V>>) |
O(m) | O(m) for m entries, as HashMap.putAll; O(n + m) when they are a HashMap, merged part by part. |
replace(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1), as HashMap.replace. |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) |
effectively O(1) | effectively O(1), as replace: a map holds an entry once. |
replace(K, V, V) |
effectively O(1) | effectively O(1), as HashMap.replace. |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) |
O(n) | O(n), as HashMap.replaceAll. |
keySet() |
O(n) | O(n), with no hashing and no key comparison, as HashMap.keySet. |
values() |
O(n) | O(n), as HashMap.values. |
groupMap(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>) |
O(n) | O(n): one key, one value and one hash lookup per entry. |
groupMapReduce(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per entry. |
sizeCompare(int) |
O(1) | O(1): the stored size is compared. |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most; O(1) when the size of that is stored. |
toMap() |
O(1) | O(1). |
remove(K) |
effectively O(1) | effectively O(1), as HashMap.remove. |
updateWith(K, Function<? super Option<V>, ? extends Option<? extends V>>) |
effectively O(1) | effectively O(1), as HashMap.updateWith. |
removeAll(Iterable<? extends K>) |
O(m) | O(m) for m given keys, as HashMap.removeAll. |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(m) | O(m) for m given entries, as HashMap.retainAll. |
max() |
O(n) | O(n), every entry compared once. |
min() |
O(n) | O(n), every entry compared once. |
size() |
O(1) | O(1): the size is stored. |
get(K) |
effectively O(1) | effectively O(1), as HashMap.get. |
getOrElse(K, V) |
effectively O(1) | effectively O(1), as HashMap.getOrElse. |
getOrElse(K, Supplier<? extends V>) |
effectively O(1) | effectively O(1), as HashMap.getOrElse. |
containsKey(K) |
effectively O(1) | effectively O(1), as HashMap.containsKey. |
contains(Tuple2<K, V>) |
effectively O(1) | effectively O(1), as HashMap.contains. |
iterator() |
O(1) | O(1) to create; a whole walk is O(n), as HashMap.iterator. |
asJava() |
O(1) | O(1). |
asJavaMap() |
O(1) | O(1); get and containsKey on the view are effectively O(1). |
NonEmptySortedMap¶
| Method | Cost | Note |
|---|---|---|
fromSortedMap(TreeMap<K, V>) |
O(1) | O(1). |
unsafeFromSortedMap(TreeMap<K, V>) |
O(1) | O(1). |
put(K, V) |
O(log n) | O(log n), as TreeMap.put. |
put(Tuple2<? extends K, ? extends V>) |
O(log n) | O(log n), as TreeMap.put. |
put(K, U, BiFunction<? super V, ? super U, ? extends V>) |
O(log n) | O(log n), as TreeMap.put. |
put(Tuple2<? extends K, U>, BiFunction<? super V, ? super U, ? extends V>) |
O(log n) | O(log n), as TreeMap.put. |
putAll(Iterable<? extends Tuple2<? extends K, ? extends V>>) |
O(m log(n + m)) | O(m log(n + m)) for m entries, as TreeMap.putAll. |
replace(Tuple2<K, V>, Tuple2<K, V>) |
O(log n) | O(log n), as TreeMap.replace. |
replaceAll(Tuple2<K, V>, Tuple2<K, V>) |
O(log n) | O(log n), as replace: a map holds an entry once. |
replace(K, V, V) |
O(log n) | O(log n), as TreeMap.replace. |
replaceAll(BiFunction<? super K, ? super V, ? extends V>) |
O(n) | O(n), with no key comparison, as TreeMap.replaceAll. |
keySet() |
O(n) | O(n), with no key comparison, as TreeMap.keySet. |
values() |
O(n) | O(n), as TreeMap.values. |
groupMap(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>) |
O(n) | O(n): one key, one value and one hash lookup per entry. |
groupMapReduce(Function<? super Tuple2<K, V>, ? extends K2>, Function<? super Tuple2<K, V>, ? extends U>, BiFunction<? super U, ? super U, ? extends U>) |
O(n) | O(n): one key, one value, one hash lookup and at most one reduce per entry. |
sizeCompare(int) |
O(1) | O(1): the stored size is compared. |
sizeCompare(Iterable<?>) |
O(min(n, m)) | O(min(n, m)), at most; O(1) when the size of that is stored. |
toSortedMap() |
O(1) | O(1). |
remove(K) |
O(log n) | O(log n), as TreeMap.remove. |
updateWith(K, Function<? super Option<V>, ? extends Option<? extends V>>) |
O(log n) | O(log n), as TreeMap.updateWith. |
removeAll(Iterable<? extends K>) |
O(m log n) | O(m log n) for m given keys, as TreeMap.removeAll. |
retainAll(Iterable<? extends Tuple2<K, V>>) |
O(m log n) | O(m log n) for m given entries, as TreeMap.retainAll. |
tail() |
O(log n) | O(log n), as TreeMap.tail. |
init() |
O(log n) | O(log n), as TreeMap.init. |
take(int) |
O(log n) | O(log n), as TreeMap.take. |
takeRight(int) |
O(log n) | O(log n), as TreeMap.takeRight. |
takeWhile(Predicate<? super Tuple2<K, V>>) |
O(k + log n) | O(k + log n) for a prefix of k entries, as TreeMap.takeWhile. |
takeUntil(Predicate<? super Tuple2<K, V>>) |
O(k + log n) | O(k + log n) for a prefix of k entries, as TreeMap.takeUntil. |
drop(int) |
O(log n) | O(log n), as TreeMap.drop. |
dropRight(int) |
O(log n) | O(log n), as TreeMap.dropRight. |
dropWhile(Predicate<? super Tuple2<K, V>>) |
O(k + log n) | O(k + log n) for k dropped entries, as TreeMap.dropWhile. |
dropUntil(Predicate<? super Tuple2<K, V>>) |
O(k + log n) | O(k + log n) for k dropped entries, as TreeMap.dropUntil. |
grouped(int) |
O((n / size) log n) | O((n / size) log n), as TreeMap.grouped. |
sliding(int) |
O(n log n) | O(n log n), as TreeMap.sliding. |
sliding(int, int) |
O((n / step) log n) | O((n / step) log n), as TreeMap.sliding. |
slideBy(Function<? super Tuple2<K, V>, ?>) |
O(n + k log n) | O(n + k log n) for k runs, as TreeMap.slideBy. |
zipWithIndex() |
O(n) | O(n), as TreeMap.zipWithIndex. |
head() |
O(log n) | O(log n), as TreeMap.head. |
last() |
O(log n) | O(log n), as TreeMap.last. |
max() |
O(n) | O(n), every entry compared once. |
min() |
O(n) | O(n), every entry compared once. |
size() |
O(1) | O(1): the size is stored. |
get(K) |
O(log n) | O(log n), as TreeMap.get. |
getOrElse(K, V) |
O(log n) | O(log n), as TreeMap.getOrElse. |
getOrElse(K, Supplier<? extends V>) |
O(log n) | O(log n), as TreeMap.getOrElse. |
containsKey(K) |
O(log n) | O(log n), as TreeMap.containsKey. |
contains(Tuple2<K, V>) |
O(log n) | O(log n), as TreeMap.contains. |
iterator() |
O(log n) | O(log n) to create; a whole walk is O(n), in the comparator's order, as TreeMap.iterator. |
asJava() |
O(1) | O(1). |
asJavaMap() |
O(1) | O(1); get and containsKey on the view are O(log n). |
rangeFrom(K) |
O(log n) | O(log n), as TreeMap.rangeFrom. |
rangeUntil(K) |
O(log n) | O(log n), as TreeMap.rangeUntil. |
rangeTo(K) |
O(log n) | O(log n), as TreeMap.rangeTo. |
rangeFromUntil(K, K) |
O(log n) | O(log n), as TreeMap.rangeFromUntil. |
minAfter(K) |
O(log n) | O(log n), as TreeMap.minAfter. |
maxBefore(K) |
O(log n) | O(log n), as TreeMap.maxBefore. |
iteratorFrom(K) |
O(log n) | O(log n) to create, then O(1) per step on average, as TreeMap.iteratorFrom. |
tailNonEmpty() |
O(log n) | O(log n), as TreeMap.tail. |
initNonEmpty() |
O(log n) | O(log n), as TreeMap.init. |