Kds is a Date Structure library for Multiplatform Kotlin 1.3.
https://github.com/korlibs/kds
Table of contents:
IntArrayList
, FloatArrayList
and DoubleArrayList
Array2
, IntArray2
, FloatArray2
, DoubleArray2
Deque
, ByteDeque
, IntDeque
, FloatDeque
, DoubleDeque
FastIntMap
, FastStringMap
IntMap
, IntIntMap
, IntFloatMap
PriorityQueue
, IntPriorityQueue
, FloatPriorityQueue
, DoublePriorityQueue
Queue
, IntQueue
, FloatQueue
, DoubleQueue
Stack
, IntStack
, FloatStack
, DoubleStack
genericBinarySearch
, binarySearch
mapWhile
, mapWhileArray
, mapWhileInt
, mapWhileFloat
, mapWhileDouble
List.getCyclic
, Array.getCyclic
Extra.Property
, Computed
, WeakProperty
Requires Gradle 4.7
(JVM 8~10
) for building and Kotlin >=1.3.11
for running:
def kdsVersion = "1.0.0"
repositories {
maven { url "https://dl.bintray.com/soywiz/soywiz" }
}
dependencies {
// For multiplatform projects
implementation "com.soywiz:kds:$kdsVersion"
// For JVM/Android only
implementation "com.soywiz:kds-jvm:$kdsVersion"
// For JS only
implementation "com.soywiz:kds-js:$kdsVersion"
}
// settigs.gradle
enableFeaturePreview('GRADLE_METADATA')
IntArrayList
, FloatArrayList
and DoubleArrayList
Kds provides specialized equivalents of ArrayList
so it doesn’t involve object allocation through boxing. It uses typed arrays internally to store the elements of the ArrayList so it just requires one additional object allocation per list (the Array
). It will just allocate a new object when the capacity of the list is exhausted.
You can construct literals using the *arrayListOf
constructors:
val ilist = intArrayListOf(10, 20)
val flist = floatArrayListOf(10f, 20f)
val dlist = doubleArrayListOf(10.0, 20.0)
IntArrayList
, FloatArrayList
and DoubleArrayList
work like a normal ArrayList
but without incurring into boxing.
val list = IntArrayList()
list += 10
list += 20
list[0] = 15
println(list[0])
println(list.toList().map { it * 20 })
println(list.getCyclic(-1))
mapInt
, mapFloat
and mapDouble
generate optimized *ArrayList
. And *ArrayList
have an specialized filter
function too.
val filter = (0 until 10).mapInt { it * 3 }.filter { it % 2 == 0 }
Array2
, IntArray2
, FloatArray2
, DoubleArray2
Array2 is a bidimensional version of Array variants. It includes a width
and a height
instead of size (length) measuing its dimensions.
It provides bidimensional indexers and some convenience methods.
val biarray = IntArray2(64, 64) { 0 }
val biarray = IntArray2(64, 64, 0)
biarray[0, 0] = 1
biarray.width == 64
biarray.height == 64
Internally it is represented as a single 1D Array and actual indices are computed using simple arithmetic.
BitSet
structure that works like a BoolArray
but it is more efficient in terms of memory usage.
val array = BitSet(100) // Stores 100 bits
array[99] = true
val bool: Boolean = array[99]
It packs bits in an IntArray
internally so it requires up to eight times less space than a BoolArray that potentially uses internally a ByteArray.
Works like a LinkedHashMap
with a limited amount of elements. When inserting new elements after reaching the maximum amount of elements, the oldest element inserted is deleted.
val cache = CacheMap<String, Int>(maxSize = 2)
cache["a"] = 1
cache["b"] = 2
cache["c"] = 3
assertEquals("{b=2, c=3}", cache.toString())
Map with String
keys considered case insensitive. Case of the original keys is preserved, but keys can be accessed with any case.
val map = CaseInsensitiveStringMap("hELLo" to 1, "World" to 2)
assertEquals(2, map.size)
assertEquals(1, map["hello"])
assertEquals(2, map["world"])
It is possible to convert a normal Map<String, *>
to a CaseInsensitive one with the toCaseInsensitiveMap
extension:
val map = mapOf("hELLo" to 1, "World" to 2).toCaseInsensitiveMap()
Deque
, ByteDeque
, IntDeque
, FloatDeque
, DoubleDeque
Deque
variants (and its CircularList
typealias) allows to insert and delete elements to/from the start or the end of the deque in constant time except when growing the collection. It can be used to implement queues or produce/consumers in an efficient way. The typed variants allow to reduce memory and allocation usage.
val l = IntDeque()
for (n in 0 until 1000) l.addFirst(n)
for (n in 0 until 1000) l.removeFirst()
for (n in 0 until 1000) l.addLast(n)
FastIntMap
, FastStringMap
Simpler Map-like structures that uses native specific implementations to improve performance and reduce allocations.
val map = FastIntMap<String>()
assertEquals(0, map.size)
map[1] = "a"
map[2] = "b"
assertEquals(listOf(1, 2), map.keys.sorted())
assertEquals(2, map.size)
assertEquals("a", map[1])
assertEquals("b", map[2])
assertEquals(null, map[3])
IntMap
, IntIntMap
, IntFloatMap
Variants of a hashmap implementation using int as keys without boxing (and Object, int or float for values). The implementation requires just a couple of arrays for working (no nodes at all). It uses a multihash approach for filling as much as possible with a logarithmic stash. Just allocates when growing.
val m = IntIntMap()
m[0] = 98
assertEquals(1, m.size)
assertEquals(98, m[0])
assertEquals(0, m[1])
A set working with integers without boxing.
val set = intSetOf(1, 2, 4)
assertEquals(3, set.size)
assertEquals(true, 1 in set)
assertEquals(true, 2 in set)
assertEquals(false, 3 in set)
assertEquals(true, 4 in set)
set.remove(2)
assertEquals(2, set.size)
assertEquals(true, 1 in set)
assertEquals(false, 2 in set)
assertEquals(true, 4 in set)
A reader for lists. It can peek
, read
or expect
a specific value in order.
val reader = listOf(1, 2, 3).reader()
assertEquals(true, reader.hasMore)
assertEquals(1, reader.peek())
assertEquals(1, reader.peek())
assertEquals(1, reader.read())
assertEquals(2, reader.read())
assertEquals(3, reader.expect(3))
assertEquals(false, reader.hasMore)
A simple pool implementation allowing to preallocate, to reset objects and to temporally allocate (freeing automatically) using an inline function. It accepts an instance allocator, and an optional function to reset instances.
val pool = Pool { Demo() }
pool.alloc { demo ->
println("Temporarilly allocated $demo")
}
val pool = Pool(reset = {
totalResetCount++
it.x = 0
it.y = 0
}, gen = {
totalAllocCount++
Demo()
})
val a = pool.alloc()
val b = pool.alloc()
assertEquals(0, pool.itemsInPool)
pool.free(c)
assertEquals(1, pool.itemsInPool)
pool.free(b)
pool.alloc {
assertEquals(1, pool.itemsInPool)
}
assertEquals(2, pool.itemsInPool)
assertEquals(5, totalResetCount) // Number of resets
assertEquals(3, totalAllocCount) // Number of allocs
PriorityQueue
, IntPriorityQueue
, FloatPriorityQueue
, DoublePriorityQueue
Provides a PriorityQueue that allows to insert items in a Queue by priority. It allows reordering specific items after modification.
val pq = IntPriorityQueue()
pq.add(10)
pq.add(15)
pq.add(5)
assertEquals(5, pq.removeHead())
assertEquals(10, pq.removeHead())
assertEquals(15, pq.removeHead())
assertEquals(0, pq.size)
Allows to provide a custom Comparator
:
val pq = IntPriorityQueue { a, b -> (-a).compareTo(-b) }
pq.addAll(listOf(1, 2, 3, 4))
assertEquals(listOf(4, 3, 2, 1), pq.toList())
And to repriorize objects after modification:
val item = Item(10)
pq.add(item)
item.value = 20
pq.updateObject(item)
It is implemented using a Min Heap so addition, removing and updating happens in O(log(n)).
Queue
, IntQueue
, FloatQueue
, DoubleQueue
A FIFO (First In First Out) collection.
val queue = IntQueue()
queue.enqueue(1)
queue.enqueue(2)
assertEquals(1, queue.dequeue())
Internally implemented using a Deque
.
Stack
, IntStack
, FloatStack
, DoubleStack
A LIFO (Last In First Out) collection.
val queue = IntStack()
queue.push(1)
queue.push(2)
assertEquals(2, queue.pop())
Internally implemented using an ArrayList
.
Provides a WeakMap data structure that internally uses JS’s WeakMap
, JVM’s WeakHashMap
and Native’s WeakReference
. WeakProperty allow to define external/extrinsic properties to objects that are collected once the object is not referenced anymore.
val map = WeakMap<Demo, String>()
val demo1 = Demo()
map[demo1] = "hello"
assertEquals("hello", map[demo1])
Note that using this primitive on JavaScript requires ES6 support (and it doesn’t work on IE10 or lower). Check the JS’s WeakMap compatibility table for more information.
Instead of providing a MutableMap<K, MutableList<V>>
implementation. Kds provides a set of methods and extension methods to easily work with those kind of maps.
val map = linkedHashMapListOf("a" to 10, "a" to 20, "b" to 30)
assertEquals(10, map.getFirst("a"))
assertEquals(20, map.getLast("a"))
assertEquals(30, map.getFirst("b"))
assertEquals(30, map.getLast("b"))
assertEquals(null, map.getLast("c"))
assertEquals(listOf("a" to 10, "a" to 20, "b" to 30), map.flatten())
genericBinarySearch
, binarySearch
Kds provides binarySearch for its collections limiting the indices used. Also provides a genericBinarySearch
to execute the algorithm in any possible kind of collection. It allows to get exact possitions or nearest positionss when no value is found:
val v = intArrayOf(10, 20, 30, 40, 50)
assertEquals(0, v.binarySearch(10).index)
assertEquals(1, v.binarySearch(20).index)
assertEquals(2, v.binarySearch(30).index)
assertEquals(3, v.binarySearch(40).index)
assertEquals(4, v.binarySearch(50).index)
assertEquals(true, v.binarySearch(10).found)
assertEquals(false, v.binarySearch(11).found)
assertEquals(2, v.binarySearch(21).nearIndex)
genericSort
allows to sort any array-like structure fully or partially without allocating and without having to reimplementing any sort algorithm again.
You just have to implement a compare
and swap
methods that receive indices
in the array to compare and optionally a shiftLeft
method (that fallbacks to use the swap
one). The SortOps implementation is usually an object
to prevent allocating.
fun <T> genericSort(subject: T, left: Int, right: Int, ops: SortOps<T>): T
abstract class SortOps<T> {
abstract fun compare(subject: T, l: Int, r: Int): Int
abstract fun swap(subject: T, indexL: Int, indexR: Int)
open fun shiftLeft(subject: T, indexL: Int, indexR: Int)
}
So a simple implementation that would sort any MutableList
could be:
val result = genericSort(arrayListOf(10, 30, 20, 10, 5, 3, 40, 7), 0, 7, ArrayListSortOps)
assertEquals(listOf(3, 5, 7, 10, 10, 20, 30, 40), result)
object ArrayListSortOps : SortOps<ArrayList<Int>>() {
override fun compare(subject: ArrayList<Int>, l: Int, r: Int): Int {
return subject[l].compareTo(subject[r])
}
override fun swap(subject: ArrayList<Int>, indexL: Int, indexR: Int) {
val tmp = subject[indexA]
subject[indexA] = subject[indexB]
subject[indexB] = tmp
}
}
mapWhile
, mapWhileArray
, mapWhileInt
, mapWhileFloat
, mapWhileDouble
This method allows to generate a collection by providing a condition and a generator:
val iterator = listOf(1, 2, 3).iterator()
assertEquals(listOf(1, 2, 3), mapWhile({ iterator.hasNext() }) { iterator.next()})
List.getCyclic
, Array.getCyclic
For lists and arrays Kds defines a getCyclic
extension method to get an element wrapping its bounds. So list.getCylic(-1)
would return the last element of the List, and list.getCyclic(size)
would return the element at 0:
assertEquals("a", arrayOf("a", "b").getCyclic(2))
assertEquals("b", arrayOf("a", "b").getCyclic(-1))
Extra.Property
, Computed
, WeakProperty
Provides a Extra funtionality to define extrinsic properties to an object that has been decorated with Extra interface implemented by Extra.Mixin. It just adds a extra hashmap to the object, so it can be used to externally define properties. The idea is similar to WeakProperty
but doesn’t require weak references at all. But just works with objects that implements Extra interface.
class Demo : Extra by Extra.Mixin() {
val default = 9
}
// Externally defined for classes implementing Extra
var Demo.demo by Extra.Property { 0 }
var Demo.demo2 by Extra.PropertyThis<Demo, Int> { default }
val demo = Demo()
assertEquals(0, demo.demo)
assertEquals(9, demo.demo2)
demo.demo = 7
assertEquals(7, demo.demo)
assertEquals("{demo=7, demo2=9}", demo.extra.toString())
Allows to create nullable properties with a parent object that tries to get its value from the parent or from a default when it is not defined locally:
class Format(override var parent: Format? = null) : Computed.WithParent<Format> {
var size: Int? = null
val computedSize by Computed(Format::size) { 10 }
}
val f2 = Format()
val f1 = Format(f2)
assertEquals(10, f1.computedSize)
f2.size = 12
assertEquals(12, f1.computedSize)
f1.size = 15
assertEquals(15, f1.computedSize)
Similar to Extra, to extend objects, but do not require the objects to implement the Extra
interface. Each externally defined property creates a WeakMap whose keys are the objects that are going to contain the extra properties. But those properties do not retain the object themselves, so they can be collected when not referenced anywhere else.
class C {
val value = 1
}
var C.prop by WeakProperty { 0 }
var C.prop2 by WeakPropertyThis<C, String> { "${value * 2}" }
val c1 = C()
val c2 = C()
assertEquals(0, c1.prop)
assertEquals(0, c2.prop)
c1.prop = 1
c2.prop = 2
assertEquals(1, c1.prop)
assertEquals(2, c2.prop)
assertEquals("2", c2.prop2)
c2.prop2 = "3"
assertEquals("3", c2.prop2)