Last active
April 4, 2022 18:45
-
-
Save toefel18/6b5912a691075b6ae2e194a7752dc845 to your computer and use it in GitHub Desktop.
In-memory data structure that can search over multiple fields of an object
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class IndexingDataStructure<V>(private val lock: Any = Any()) { | |
abstract inner class Index<KEY, RETURN>(val name: String, protected val keyFromValueFunc: (value: V) -> KEY) { | |
abstract fun get(key: KEY): RETURN | |
internal abstract fun internalIncludeItem(value: V) | |
} | |
inner class UniqueIndex<KEY>(name: String, keyFromValueFunc: (value: V) -> KEY, private val map: MutableMap<KEY, V> = mutableMapOf()) : Index<KEY, V?>(name, keyFromValueFunc) { | |
override fun get(key: KEY): V? = synchronized(lock) { map[key] } | |
override fun internalIncludeItem(value: V) { | |
keyFromValueFunc(value).let { key -> | |
synchronized(lock) { | |
require(!map.containsKey(key)) { "item with unique field $name with value $key already in dataset" } | |
map[key] = value | |
} | |
} | |
} | |
} | |
inner class MultiIndex<KEY>(name: String, keyFromValueFunc: (value: V) -> KEY, private val map: MutableMap<KEY, MutableList<V>> = mutableMapOf()) : Index<KEY, List<V>>(name, keyFromValueFunc) { | |
override fun get(key: KEY): List<V> = synchronized(lock) { map[key] ?: listOf() } | |
override fun internalIncludeItem(value: V) { | |
synchronized(lock) { | |
map.computeIfAbsent(keyFromValueFunc(value)) { mutableListOf() }.add(value) | |
} | |
} | |
} | |
private val indexByName: MutableMap<String, Index<*, *>> = mutableMapOf() | |
fun <KEY> createUniqueIndex(name: String, keyFromValueFunc: (value: V) -> KEY): UniqueIndex<KEY> { | |
require(!indexByName.containsKey(name)) { "index $name already exists" } | |
return synchronized(lock) { | |
UniqueIndex(name, keyFromValueFunc).also { | |
indexByName[it.name] = it | |
} | |
} | |
} | |
fun <KEY> createMultiIndex(name: String, keyFromValueFunc: (value: V) -> KEY): MultiIndex<KEY> { | |
require(!indexByName.containsKey(name)) { "index $name already exists" } | |
return synchronized(lock) { | |
MultiIndex(name, keyFromValueFunc).also { | |
indexByName[it.name] = it | |
} | |
} | |
} | |
fun save(vararg values: V) { | |
synchronized(lock) { | |
values.forEach { value -> | |
indexByName.values.forEach { index -> index.internalIncludeItem(value) } | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.time.ZoneOffset | |
import java.time.ZonedDateTime | |
import net.cryptoworkbench.shared.indexable.IndexingDataStructure | |
data class Activity(val id: Int, val time: ZonedDateTime, val type: ActivityType,val spoor: String) | |
enum class ActivityType { A, R, AR } | |
class ActivityRepository { | |
private val activities: IndexingDataStructure<Activity> = IndexingDataStructure() | |
private val idIndex = activities.createUniqueIndex("id") { it.id } | |
private val timeIndex = activities.createUniqueIndex("time") { it.time } | |
private val typeIndex = activities.createMultiIndex("type") { it.type } | |
private val spoorIndex = activities.createMultiIndex("spoor") { it.spoor } | |
fun save(vararg activitiesToSave: Activity) = activities.save(*activitiesToSave) | |
fun getById(id: Int): Activity? = idIndex.get(id) | |
fun getByTime(time: ZonedDateTime): Activity? = timeIndex.get(time) | |
fun getByType(type: ActivityType): List<Activity> = typeIndex.get(type) | |
fun getBySpoor(spoor: String): List<Activity> = spoorIndex.get(spoor) | |
} | |
fun main() { | |
val jan1MidDay = ZonedDateTime.of(2022, 1, 1, 12, 0, 0, 0, ZoneOffset.UTC) | |
val act1 = Activity(1, jan1MidDay, ActivityType.A, "12a") | |
val act2 = Activity(2, jan1MidDay.plusDays(1), ActivityType.AR, "15") | |
val act3 = Activity(3, jan1MidDay.plusDays(2), ActivityType.R, "12a") | |
val act4 = Activity(4, jan1MidDay.plusDays(3), ActivityType.A, "17") | |
val repo = ActivityRepository() | |
repo.save(act1, act2, act3, act4) | |
check(repo.getById(3) == act3) { "item with id 3 did not match act3 $act3"} | |
check(repo.getByTime(jan1MidDay) == act1) { "item with time $jan1MidDay did not match act1 $act1"} | |
check(repo.getByType(ActivityType.A).let { it.size == 2 && it.containsAll(listOf(act1, act4)) }) { "activities with type A did not return expected act1 and act4 alone ${repo.getByType(ActivityType.A)}"} | |
check(repo.getBySpoor("12a").let { it.size == 2 && it.containsAll(listOf(act1, act3)) }) { "items with spoor 12a did not return act1 and act3"} | |
println("repo.getById(3): ${repo.getById(3)}") | |
println("repo.getByTime(jan1MidDay): ${repo.getByTime(jan1MidDay)}") | |
println("repo.getByType(ActivityType.A): ${repo.getByType(ActivityType.A)}") | |
println("repo.getBySpoor(\"12a\"): ${repo.getBySpoor("12a")}") | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment