kform/tech.ostack.kform.collections/PathTrie

PathTrie

class PathTrie<T>(initialCapacity: Int = 100) : MutablePathMultimap<T> (source)

Implementation of a mutable path multimap as a trie. Held values are of type T.

Each node of the trie represents a path fragment. As such, a path can be represented by navigating through the trie's nodes. Each node contains the values associated with the path they represent.

A trie is a good structure to implement a path multimap due to the intended semantics of the get(path) and remove(path) functions: the get function should return all values matching a given path, whilst the remove function removes values contained by a given path (following the matching and containment semantics of paths).

As an example, imagine the following operations on the trie (with simplified notation for the paths):

trie["/"] = 0
trie["/path/x"] = 1
trie["/path/y"] = 2
trie["/path/x/z"] = 3
trie["/∗/path"] = 4
trie["/∗/path"] = 5

The resulting structure would look similar to the following, where the right side represents the values associated with each trie node:

/          -> [0]
├─ path    -> []
│  ├─ x    -> [1]
│  │  └─ z -> [3]
│  └─ y    -> [2]
└─ ∗       -> []
   └─ path -> [4, 5]

Getting values associated with the path "/∗/∗" would return a sequence with values [1, 2, 4, 5].

Constructors

PathTrie

constructor(initialCapacity: Int = 100)

Creates a new path trie given an initialCapacity (defaults to 100).

Properties

entries

open val entries: Sequence<PathMultimapEntry<T>>

Sequence of all entries in the multimap (may have repeated entries).

size

open override val size: Int

Number of entries in the multimap.

values

open val values: Sequence<T>

Sequence of values in the multimap (may have repeated values).

Functions

clear

open override fun clear()

Removes all entries from the path multimap.

contains

open operator fun contains(value: T): Boolean

Returns whether there exists at least one value equal to value in the multimap. Equivalent to containsValue(value).

open operator fun contains(entryId: PathMultimapEntryId): Boolean

Returns whether there exists an entry identified by entryId in the multimap. Equivalent to containsEntry(entryId).

open operator fun contains(path: String): Boolean

open operator fun contains(path: Path): Boolean

Returns whether there exists at least one entry with a path matching path (following the semantics of path matching). Equivalent to containsPath(path).

containsEntry

open override fun containsEntry(entryId: PathMultimapEntryId): Boolean

Returns whether there exists an entry identified by entryId in the multimap.

containsPath

open fun containsPath(path: String): Boolean

Returns whether there exists at least one entry with a path matching path (following the semantics of path matching).

open override fun containsPath(path: Path): Boolean

Returns whether there exists at least one entry with a path matching path (following the semantics of path matching).

containsValue

open override fun containsValue(value: T): Boolean

Returns whether there exists at least one value equal to value in the multimap.

entries

open fun entries(path: String): Sequence<PathMultimapEntry<T>>

Returns a sequence over all entries with a path matching path (following the semantics of path matching).

open override fun entries(path: Path): Sequence<PathTrieEntry<T>>

Returns a sequence over all entries with a path matching path (following the semantics of path matching).

get

open operator fun get(entryId: PathMultimapEntryId): PathMultimapEntry<T>?

Returns the entry identified by entryId or null when no such entry exists. Equivalent to getEntry(entryId).

open operator fun get(path: String): Sequence<T>

Returns a sequence over all values with a path matching path (following the semantics of path matching).

open operator override fun get(path: Path): Sequence<T>

Returns a sequence over all values with a path matching path (following the semantics of path matching).

getEntry

open override fun getEntry(entryId: PathMultimapEntryId): PathTrieEntry<T>?

Returns the entry identified by entryId or null when no such entry exists.

getOne

open fun getOne(path: String): T?

open fun getOne(path: Path): T?

Returns one value matching path or null when no such value exists. Equivalent to get(path).firstOrNull().

isEmpty

open fun isEmpty(): Boolean

Whether the multimap is empty.

put

open fun put(path: String, value: T): PathMultimapEntryId

Inserts a new entry in the multimap with the given path and value and returns an identifier that identifies the inserted entry in the multimap.

open override fun put(path: Path, value: T): PathMultimapEntryId

Inserts a new entry in the multimap with the given path and value and returns an identifier that identifies the inserted entry in the multimap.

putAll

open fun putAll(pathMultimap: PathMultimap<T>): List<PathMultimapEntryId>

Inserts all entries of pathMultimap into this multimap and returns a list with the identifiers of each inserted entry.

remove

open fun remove(path: String): List<PathMultimapEntry<T>>

Removes all entries with a path contained by path (following the semantics of path containment) and returns a list of said entries.

open override fun remove(path: Path): List<PathTrieEntry<T>>

Removes all entries with a path contained by path (following the semantics of path containment) and returns a list of said entries.

removeEntry

open override fun removeEntry(entryId: PathMultimapEntryId): PathTrieEntry<T>?

Removes the entry identified by entryId and returns it or null when no such entry exists.

set

operator fun <T> MutablePathMultimap<T>.set(path: String, value: T): PathMultimapEntryId

operator fun <T> MutablePathMultimap<T>.set(path: Path, value: T): PathMultimapEntryId

Inserts a new entry in the multimap with the given path and value and returns an identifier that identifies the inserted entry in the multimap.

toMap

fun <T> PathMultimap<T>.toMap(): MutableMap<AbsolutePath, MutableList<T>>

Transforms the multimap into a mapping of paths to lists of values associated with them.

toString

open override fun toString(): String

Formats the trie as a mapping of paths to the list of values associated with them.