- Upgrade Kotlin version up to 1.9.21
- Support wasmJs and wasmWasi targets
- Upgrade Kotlin version up to 1.9.0
- Support all targets currently supported by the K/N compiler
- Drop support for the Legacy js target
- Upgrade Kotlin version up to 1.6.0
- Raise the JVM bytecode target to 1.8. Now the library cannot be used on JDK 1.6 and 1.7.
- Add other Apple K/N targets
- Implement faster equals function for sets and maps
- Fix PersistentHashMapBuilder.putAll() #114
- Upgrade Kotlin version up to 1.4.30
- Publish the library to Maven Central instead of Bintray #96.
- Add license information to published POMs #98.
- Implement workaround for specialized MutableEntrySet.contains/remove KT-41278.
- Bug in PersistentList - list is broken after removeAll call #92.
- Faster bulk operations for non-ordered sets (removeAll, retainAll, containsAll) #91.
- Faster addAll/putAll implementation for non-ordered sets/maps #83.
- Add extension functions to convert Sequence to persistent collections 84.
- Add missing CharSequence.toImmutableSet() extension function.
- Upgrade Kotlin version up to 1.4.0
- Weaken receiver type of toPersistentHashSet to Iterable #77.
- Throw ConcurrentModificationException if hashCode of ordered set element changes #76.
- Fix transition from PersistentVector to SmallPersistentVector #75
- Add CharSequence.toPersistentHashSet() as an alternative to CharSequence.toPersistentSet()
- Introduce
persistentHashSetOf
,persistentMapOf
andpersistentHashMapOf
methods that take no arguments and create an empty instance #67. - Fix map
entries
/keys
/values
iterators including #68.
- Update Kotlin version up to 1.3.70
- Turn the JVM-only project into a multiplatform library
- Builder iterators are fast-fail only on JVM. On the other platforms modifying the builder during iteration not through the corresponding iterator can invalidate the iterator state in an unspecified way.
- In addition to JVM and JS platforms, macosX64, iosX64, iosArm64, iosArm32, linuxX64, and mingwX64 native platforms are supported.
- Make conversion to persistent collections consistent
toPersistentMap
/Set
always returns an ordered persistent map/settoPersistentHashMap
/Set
always returns an unordered persistent map/settoImmutableMap
/Set
may return any kind of immutable map/set
- Optimize persistent list [builder] batch update operations
addAll(elements)
operation performs ~3 times faster 📉addAll(index, elements)
operation takes O(N + M), down from O(N * M), where N is the size of this collection and M - the size of theelements
collection. 📉removeAll(elements)
operation takes O(N * K), down from O(N * M), where K is the time complexity ofcontains
operation on theelements
collection 📉removeAll(predicate)
operation takes O(N * P), down from O(N * (P + N)), where P is the time complexity of thepredicate
algorithm 📉
- Implement set/map backing trie canonicalization
add
operation afterremove
operations performs ~20% faster 📉- iteration after
remove
operations performs ~3 times faster 📉
- Immutable collections specify by their contract the real immutability of their implementors
ImmutableCollection
extends read-onlyCollection
ImmutableList
extends read-onlyList
andImmutableCollection
, and overridessubList
method that returnsImmutableList
ImmutableSet
extends read-onlySet
andImmutableCollection
ImmutableMap
extends read-onlyMap
, and overrideskeys
,values
andentries
properties types withImmutableSet
,ImmutableCollection
andImmutableSet
respectively
- Persistent collections extend immutable collections and provide modification operations that return new instances with the modification applied
PersistentCollection
extendsImmutableCollection
, and provides modification operations and builderPersistentList
extendsImmutableList
andPersistentCollection
, and provides modification operationsPersistentSet
extendsImmutableSet
andPersistentCollection
, and provides modification operationsPersistentMap
extendsImmutableMap
, and provides modification operations and builder
plus
,minus
andmutate
extension functions are available only for persistent collections- Deprecate
immutableXOf()
top-level functions and introducepersistentXOf()
toImmutableX()
extension functions returnImmutableX
- Introduce
toPersistentX()
extension functions that returnPersistentX
- Document public API
PersistentList
implementation is backed by a bit-mapped trie with branching factor of 32add(element: E)
andremoveAt(size - 1)
operations take O(1) time, down from O(log2n) 📉get
andset
operations take O(log32n), down from O(log2n) (though the same asymptotic) 📉- Iteration has the same time complexity of O(n), but much faster in practice due to the better reference locality 📉
- Unordered
PersistentSet
implementation is backed by a hash-array mapped trie (a.k.a. HAMT) with up to 32 children or elements in a nodecontains
,add
andremove
operations take O(log32n) time, down from O(log2n) 📉- Iteration has the same time complexity of O(n), but much faster in practice due to the better reference locality 📉
- Unordered
PersistentMap
implementation is backed by a compressed hash-array mapped prefix-tree (a.k.a. CHAMP) with up to 32 children or entries in a nodecontains
,get
,put
andremove
operations take O(log32n) time, down from O(log2n) 📉- Iteration has the same time complexity of O(n), but much faster in practice due to the better reference locality 📉
- Ordered
PersistentSet
implementation is backed by the unorderedPersistentMap
which maps elements in this set to next and previous elements in insertion ordercontains
,get
andput
operations take O(log32n) time, down from O(log2n) 📉remove
operation takes O(log32n) time, down from O(n) 📉- Iteration takes O(n log32n) time, up from O(n) 📈
- Ordered
PersistentMap
implementation is backed by the unorderedPersistentMap
which maps keys in this map to values, next and previous keys in insertion ordercontains
,get
andput
operations take O(log32n) time, down from O(log2n) 📉remove
operation takes O(log32n) time, down from O(n) 📉- Iteration takes O(n log32n) time, up from O(n) 📈
- Builders are backed by the same backing storage as the corresponding persistent collections, but apply modifications in-place if the node has already been copied
- Time complexities of all operations are the same as of the corresponding persistent collections. However, avoiding memory allocations leads to significant performance improvement 📉