Simple Kotlin example of working with B-Trees with Apache Mavibot [btree, kotlin, mavibot]

Mavibot.kt

import org.apache.directory.mavibot.btree.*
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException
import org.apache.directory.mavibot.btree.serializer.*
import java.util.*

fun main(args: Array<String>) {
    btreeExample()
}

/**
 * Shows how to work with Apache Mavibot B-Trees.
 * It creates, populates, and navigates the B-Tree.
 *
 * A B-tree database file with one B-tree is created and populated with noOfRecords nodes.
 * Each node has a random String as its key and a Long value as its payload.
 * The nodes have the Long values 0..noOfRecords - 1 as their payload.
 *
 * All the nodes are printed to the console. Note how the order of the keys is in (lexical) order.
 */
fun btreeExample() {
    // Configuration
    val noOfRecords = 1000L
    val btreeName = "test"
    val databaseFileName = "Test.db"

    // Create a RecordManager that contains the B-tree
    val recordManager = RecordManager(databaseFileName)

    // Get the B-tree or create it if there's none
    val btree = recordManager.getManagedTree<String, Long>(btreeName) ?: recordManager.addBTree(btreeName, StringSerializer.INSTANCE, LongSerializer.INSTANCE, true)

    // Either use the B-Tree as is or populate it with data if it has none
    when (btree.nbElems) {
        0L -> {
            // Insert some random data
            val random = Random()
            for (i in 0L..noOfRecords - 1) {
                btree.insert(randomString(random = random), i)
            }
        }
        else -> println("B-Tree already contains ${btree.nbElems} elements")
    }

    // Create a cursor
    val cursor = btree.browse()

    // Iterate over all the nodes (order will be by key, needs O(n) time)
    while (cursor.hasNext()) {
        println(cursor.next())
    }

    // Lookup key for value from middle of range
    val searchValue = btree.nbElems / 2
    // As preparation, find the corresponding key (we SHOULD have it, but we don't; needs O(n) time)
    val searchKey = findKeyForValue(btree, searchValue).orElseThrow {
        throw KeyNotFoundException("No key found for value $searchValue")
    }
    // Find the key (this is the typical use case for a B-Tree, needs O(log(n)) time)
    val searchResult = btree.get(searchKey)
    assert(searchValue == searchResult) // VM option -ea to enable
    println("For key $searchKey found value $searchResult")

    // Close the B-tree
    btree.close()
}

/**
 * Searches a B-Tree for a value and returns the key.
 * This is a very expensive operation as it might traverse the entire tree.
 *
 * @param btree The B-Tree to search for the value
 * @param value The value for which to search in the B-Tree
 *
 * @return An Optional with the key; it is empty if the value is not found
 */
fun <K, V> findKeyForValue(btree: BTree<K, V>, value: V): Optional<K> {
    val cursor = btree.browse()
    while (cursor.hasNext()) {
        val node = cursor.next()
        if (node.value?.equals(value) ?: false) return Optional.of(node.key)
    }
    return Optional.empty()
}

/**
 * Creates a random string.
 * ATTENTION: don't use in production, possibly not thread safe.
 *
 * @param minLength The minimal length of the String, min > 0, defaults to 8
 * @param maxLength The maximal length of the String, max >= min, defaults to 64
 * @param random The Random instance to use. If none is provided, one is created on every call
 *
 * @return A random String with at least min characters and no more than max characters
 */
fun randomString(minLength: Int = 8, maxLength: Int = 64, random: Random = Random()) = (1..minLength + random.nextInt(maxLength - minLength + 1))
        .map { '0' + random.nextInt(75) } // Characters 0..z
        .joinToString(separator = "")