// Created for this challenge: // https://www.sololearn.com/post/467153 // Implement Your Own Map // Create a class (generic or not) that does // not use any language provided classes to // implement a map of a key to a value. The // class must provide an add, delete, lookup, // and update methods. Use a binary tree // structure to sort and store the keys. You // may use operator overloading if language // supported. // Generic data class for the binary search // tree node. Properties are the key, its // value, the parent node, the left node // (lower keys), and the right node (higher // keys.) The first two are required. The // rest default to null. The types K is for // the keys and V is for the values. data class Node, V>( var key: K, var value: V, var parent: Node? = null, var left: Node? = null, var right: Node? = null) { // Method to generate the display string. // The default method can not be used // because the parent node makes it loop // forever. override fun toString() = "([$key]$value,$left,$right)" } // Node // Generic class for our map. Property is // the binary search tree root. The types // K is for the keys and V is for the // values. class Keyed, V> { var root: Node? = null // Method to add a new key and value to // the map. Find the parent. If it is // the first, create and store it as our // root. If it is higher than its parent, // create it and place on the right side // with a link back to the parent. If it // is lower than its parent, create it // and place on the left side with a link // back to the parent. Otherwise, it is a // duplication so throw an exception. fun add(key: K, value: V) { val parent = find(key) when { parent == null -> root = Node(key, value) parent.key < key && parent.right == null -> parent.right = Node(key, value, parent) parent.key > key && parent.left == null -> parent.left = Node(key, value, parent) else -> throw IllegalStateException( "Add failed!") } // when } // add // Method to remove a key and value from // our map. fun delete(key: K) { // Find the node and if it failed, // throw an exception. val node = find(key) if (node == null || node.key != key) throw IllegalStateException( "Delete failed!") // Otherwise, we found the node so // delete it. When it does not have // any branches, we just unlink from // its parent. Based on the key // comparison, set the parent's branch // to null. else when { node.left == null && node.right == null -> when { node.parent == null -> root = null node.parent!!.key < key -> node.parent!!.right = null else -> node.parent!!.left = null } // when // When the left branch is null, // we copy the right branch here // tossing that node. node.left == null -> with (node.right!!) { node.key = this.key node.value = value node.left = left node.right = right } // with // When the right branch is null, // we copy the left branch here // tossing that node. node.right == null -> with (node.left!!) { node.key = this.key node.value = value node.left = left node.right = right } // with // Otherwise, both branches are // used so we have two similar // options to move a node with the // closest value to the one being // remove from the bottom of either // banch. We picked the next higher // key so start with our right // branch and keep going left // until we reach the bottom. If // the parent of our bottom node // is the node being deleted, just // update its right branch to be // our bottom's right node. // Otherwise, the bottom node's // parent must have its left // branch be the right branch of // our bottom node. The key and // value of the bottom node must // replace our node being deleted // key and value. else -> { var replacement = node.right while (replacement!!.left != null) replacement = replacement.left if (replacement.parent == node) node.right = replacement.right else replacement.parent!!.left = replacement.right node.key = replacement.key node.value = replacement.value } // else } // when } // delete // Method to display the map. fun display() { // Recursive function to generate the // display string for the tree. If it // is null, return an empty node. // Otherwise, fill in the node and // recurse on both branches to create // our return. fun value(node: Node?): String = if (node == null) "()" else "([${node.key}]\"${node.value}\","+ value(node.left)+","+ value(node.right)+")" // Start the recursive call and print // the result. println(value(root)) } // display // Method to find the desired node // matching the key or its possible // parent when the key is not found. fun find(key: K): Node? { // Default to the root. While we // have a node, check it out. If the // node's key is less than our key // and there are some higher, move // to that node. If the node's key // is greater than our key and there // are some lower, move to that // node. Otherwise, we found the // node or its possible parent. var node = root loop@ while (node != null) when { node.key < key && node.right != null -> node = node.right node.key > key && node.left != null -> node = node.left else -> break@loop } // when return node } // find // Method to provide the get operator by // calling the lookup method to do it. If // the lookup failed, throw an exception. // Otherwise, return the value. operator fun get(key: K): V { val value = lookup(key) if (value == null) throw IllegalStateException( "Get failed!") else return value } // get // Method to lookup a key and return its // value or null. Find the node or its // possible parent. If we found the // parent, return null. Otherwise, return // the node's value. fun lookup(key: K): V? { val node = find(key) return ( if (node == null || node.key != key) null else node.value) } // lookup // Method to provide the set operator by // calling the update method to do it. operator fun set(key: K, value: V) { update(key, value) } // set // Method to update a key with a new // value. Find the node. If not found, // we add instead. Otherwise, change // the value. fun update(key: K, value: V) { val node = find(key) if (node == null || node.key != key) add(key, value) else node.value = value } // update } // Keyed // Main function test the map for the // challenge. fun main(args: Array) { // Test the map add. val map = Keyed() print("Initial: ") map.display() map.add(5, "five") print("Add 5: ") map.display() map.add(2, "two") print("Add 2: ") map.display() map.add(7, "seven") print("Add 7: ") map.display() try { map.add(7, "seventh") } catch (error: IllegalStateException) { println("Add 7: "+error.message) } // try // Test the map lookup and update. println("Lookup 2: "+map.lookup(2)) map.update(2, "second") print("Update 2: ") map.display() println("Lookup 2: "+map.lookup(2)) println("Lookup 9: "+map.lookup(9)) map.update(1, "one") print("Update 1: ") println(map.lookup(1)) map.display() // Test the map delete. try { map.delete(8) } catch (error: IllegalStateException) { println("Delete 8: "+error.message) } // try map.delete(5) print("Delete 5: ") map.display() map.delete(2) print("Delete 2: ") map.display() map.delete(7) print("Delete 7: ") map.display() map.delete(1) print("Delete 1: ") map.display() // Test the map set and get. map[6] = "six" print("Set 6: ") map.display() println("Get 6: "+map[6]) try { map[8] } catch (error: IllegalStateException) { println("Get 8: "+error.message) } // try } // main

keyed ch