danger

Sorry, some sections of this page are currently under construction. Here is a checklist of sections:

danger

This module's API is not yet ready.

Kone: Collections

This module provides revised collections API and their different fine-tuned implementations. The collections may be helpful in the implementation of more demanding algorithms. All further modules are based on the collections.

Applying the dependencies

Gradle Kotlin DSL
Gradle Groovy DSL
Maven

build.gradle.kts
dependencies {
    implementation("dev.lounres:kone.collections:0.0.0-experiment")
}

build.gradle
dependencies {
    implementation 'dev.lounres:kone.collections:0.0.0-experiment'
}

pom.xml
<dependency>
    <groupId>dev.lounres</groupId>
    <artifactId>kone.collections</artifactId>
    <version>0.0.0-experiment</version>
</dependency>

Instead of introduction

There are several problems with Kotlin stdlib's collections:

Such collections like set or map are fixed of the default equality and hashing (and assume that the later one is always available and efficient).
Arrays are always mutable and there are no immutable alternatives.
Iterators API is minimalistic and glues together getting next element and moving forward, which is not that flexible for fine-tuned behaviours.
Maps have no throwing method of getting a value by key in the way lists have it. It's a problem because you have to trace over map's structure twice just to retrieve a value.
Etc.

So there was a decision to revise ~~everything~~ collections API and their implementations.

Iterators and iterables API

Iterators in Kone can be used to iterate over different kinds of structures in different ways. They may iterate over finite or infinite number of elements. They may change the structure. They may interact with the elements in two ways, forward and backward.

Iterator assumes that some set of elements is represented as a linear sequence of elements that is used to iterate over them. This sequence may be finite or infinite (it may have no first element, no last element, or both). In each moment (when it does not perform some operation) it has a cursor that points either between two elements, before the first one, or after the last one. (If there are no elements in the collection, the pointer just points nowhere.) There are 2 types of operations that iterators can perform: non-mutating and mutating ones. Non-mutating operations are:

hasNext — checks if there is next element in the sequence,
getNext — returns the next element if there is one,
moveNext — makes cursor jump over the next element if there is one,
nextIndex — returns index of the next element if the sequence is indexed (in the way that each next element has index one more then previous element) and there is next element,
hasPrevious, getPrevious, movePrevious, and previousIndex — like the three above but in the opposite direction.

Mutating operations are:

addNext — adds new element in the space the cursor is pointing on and puts cursor before the new element,
setNext — changes the next element if there is one,
removeNext — removes the next element if there is one, preserves previous element, and makes next element after the next one the next element,
addPrevious, setPrevious, and removePrevious — like the three above but in the opposite direction.

Iterators form an inheritance hierarchy below.

Iterables are finite structures of certain size that can be iterated using iterators mentioned above. It means that their elements can form a finite sequence that can be iterated using the rules above.

warning

It is guaranteed that after non-mutating operations, the iterator is still usable. However, there is no such guarantee for mutating operations. It means that the inner structure of the iterable may be changed in a such way that state of the iterator may be undefined. For example, adding an element to a hashtable can provoke hashtable reconstruction that changes the sequence of elements to iterate undefinedly. But some structures can guarantee the safety of their iterators (for example, all lists can).

Also, be aware that there are a bit more kinds of iterators that are made especially for other APIs. For example, there are other iterator types for lists and for sets.

Concept: "nodes" and "nodded" collections

As you know, there are several kinds of lists. Let's consider a (doubly) linked list. It has a great performance of insertion in the middle. But there is one nuance: it is that performant only in cases you have a pointer to this middle. So we have to somehow have a pointer to internal parts of the structure. And it's not the only case where we need such pointers. That's why there are nodes and nodded structures in Kone.

Node is a pointer to part of the collection's inner structure where the element is stored. Nodded collection is a collection that provides a node for each of its elements. In particular, one can get element's node the moment it added the element into the collection via specific addition method. For example of the methods, KoneMutableNoddedList.addNode or KoneMutableNoddedSet.addNode.

warning

Collections return (should return) the same node instance on any request for the same element's node. I.e. there aren't (should not be) two different instances that are nodes of the same element.

All nodes provide API to get their element, isDetached property to know if the node is no longer part of corresponding structure, and other methods.

Lists and arrays API

Lists are finite sequences of elements with indices from zero to its size exclusively. There are different kinds of lists: immutable, settable, mutable, and growable mutable. Each kind has two variants: usual and nodded.

Nodes API

There are three kinds of nodes: immutable KoneListNode, settable KoneSettableListNode, and mutable KoneMutableListNode.

Immutable node provides:

element and index properties to get an element at specified place and the place's index. (In particular, the element and index properties may return different values. And index property may throw exception if the node was detached.)
isDetached property that indicates that the node is detached and is no longer part of the list's structure.
nextNode and previousNode properties to get next and previous nodes (or null if there is no one).
iteratorFromAfterHere and iteratorFromBeforeHere methods that create iterators with cursors pointing on a space after and before the node respectively.

Settable node also provides a mutable version of element property that allows changing element at the corresponding place in the list. Mutable node also provides remove method that allows to detach the node from the structure removing its element from the list.

List iterators API

List iterators form a hierarchy below.

The three interfaces KoneListIterator, KoneSettableListIterator, and KoneMutableListIterator are actually type aliases to KoneLinearIterator, KoneSettableLinearIterator, and KoneMutableLinearIterator. The bottom three interface KoneNoddedListIterator, KoneSettableNoddedListIterator, and KoneMutableNoddedListIterator inherit the interfaces above correspondingly and introduce methods getNextNode and getPreviousNode to get nodes of next and previous elements.

info

When iterator of a list is constructed, the iteration sequence is the list itself. And there is a guarantee that mutable iterator operations would leave iterator still usable. (But there is no guarantee that mutable list operations and other iterators operations would leave iterator still usable.)

🏗 Lists API

There are several kinds of lists that are presented in Kone:

Immutable lists &mdash lists which are read-only.
Settable lists — lists of fixed size that can only accept new elements instead old ones. Cannot be extended nor reduced.
Fixed capacity lists — mutable lists that are backed by fixed arrays of fixed size. Thus, they can be mutated but with a condition that at each moment number of elements won't be higher than specified capacity.
Resizable lists — mutable lists that are backed by array that will be expanded or shrunk (i.e. reinitialised with new capacity higher or lower than the previous one) depending on the current number of elements. Usually their capacity is a power of two.
Growable lists — mutable lists that are backed by array that will be expanded (i.e. reinitialised with new capacity higher than the previous one) depending on the current number of elements. Usually their capacity is a power of two.
GC-backed lists — mutable lists that do not contain any array in their structure. Thus, they are equivalent to (doubly) linked lists.

Each kind has two variants: usual and nodded. But on the level of interfaces, fixed capacity, resizable lists, and GC-backed lists have no differences, so they are represented with just KoneMutableList. And growable lists introduce only ensureCapacity method, so they are represented with KoneGrowableMutableList.

danger

This "Lists API" section is not yet finished, but you can look at API reference.

Arrays API

In Kone, arrays are just value classes that wrap Kotlin stdlib arrays. But they have a bit of advantage:

There are KoneArray and KoneXXXArrays variants (XXX is a name of primitive type) that are immutable. It allows one to use performant arrays on JVM while providing safe API. Of course, there are mutable KoneArray and KoneMutableXXXArrays variants.
They inherit KoneList and KoneSettableList interfaces which makes their usage a bit more flexible.

info

Unfortunately, there is no way to inherit KoneArray by KoneMutableArray for now. (See KT-42977 for more.) So for corner cases when you want to convert a mutable array into an immutable array without extra allocations, there are asKoneArray and asKoneXXXArray extensions.