/* Created for this lesson: https://www.sololearn.com/learn/12453 Mutant Hash Table A hash table is a data structure that implements an associative array (a collection of key, value pairs). The hash table is the structure that takes in a key and returns a hash value which maps to an index in the array. A hash function is used to compute an index into an array of slots, from which the desired value can be found. The hash function could generate the same index for more than one key, which will lead to hash collisions. A mutant hash table stores the values in a sorted linked list and thus accommodates for such collisions, in a sorted order. The sorted linked lists store two additional pointers for greater and lesser neighboring slots. This allows the values to be iterated over both in ascending and descending order. Design and implement a mutant hash table which contains the following public functions: - insert(): inserts an item into the hash table - remove(): removes an item from the hash table by its key - merge(): merges the given hash table with the current one - count(): returns the number of elements in the hash table - getList(): returns the sorted linked list containing the elements that have the same key - find(): finds an element with a specific key A mutant hash table can effectively transform into other data structures or data structure adapters, such as stack, queue or an array. This can be performed by using the following functions: - toStack(): transforms the hash table into a stack and returns it - toQueue(): transforms the hash table into a queue and returns it - toBST(): transforms the hash table into a binary search tree and returns it */ //================================================== // The following are the classes required for a // generic queue structure supporting any type. // Data class for a node storing the element and a // link to the next node in the queue. data class QueueNode(var element: T, var next: QueueNode?) // Class to provide a generic queue. class Queue() { // The first and last nodes in the queue. private var head: QueueNode? = null private var tail: QueueNode? = null // ------------------------------------------------ // Method to return true when the queue is empty. fun isEmpty() = head == null // ------------------------------------------------ // Method to add the element in a new node at the // end of the queue. Allocate the node. If the // queue is empty, put it at the head. Otherwise, // put it after the last one. In both cases, make // it the last one. fun enqueue(element: T) { val node = QueueNode(element, null) if (head == null) head = node else tail!!.next = node tail = node } // enqueue // ------------------------------------------------ // Method to remove the first element from the // queue. Grab the element from the head. Move the // head to the next node. If the head became null, // make the tail null too. fun dequeue(): T { val element = head!!.element head = head!!.next if (head == null) tail = null return element } // dequeue } // Queue //================================================== // The following are the classes required for a // generic stack structure supporting any type. // Data class for a node storing the element and a // link to the next node in the stack. data class StackNode(var element: T, var next: StackNode?) // Class to provide a generic stack. class Stack() { // The last node in the stack. private var tail: StackNode? = null // ------------------------------------------------ // Method to return true when the stack is empty. fun isEmpty() = tail == null // ------------------------------------------------ // Method to add the element in a new node at the // end of the stack. Allocate the node making it // point to the previous tail of the stack. Make // the new node the tail. fun push(element: T) { tail = StackNode(element, tail) } // push // ------------------------------------------------ // Method to remove the last element from the // stack. Grab the element from the tail. Move the // tail to the previous node. fun pop(): T { val element = tail!!.element tail = tail!!.next return element } // pop } // Stack //================================================== // The following are the classes required for a // generic AVL binary tree structure supporting any // type. // Enumerate class to remember which side of the // tree we are processing. enum class AVLSide {Left, Right} // Class for a node storing the element and // performing required processing of it. class AVLNode(private val element: T) { // The height of this node from the deepest point. private var height = 0 // A pointer to the left subtree. private var leftChild: AVLNode? = null // A pointer to the node's parent. private var parent: AVLNode? = null // A pointer to the right subtree. private var rightChild: AVLNode? = null // ------------------------------------------------ // Calculate the balance point. Negative, when the // right side is deeper. Zero, when both sides are // the same. Positive, when the left side is deeper. fun getBalance() = // If we don't have a left subtree, check the // right. if (leftChild == null) // If neither subtree exists, return zero. if (rightChild == null) 0 // Otherwise, the right subtree exists so make // it's height negative and subtract one. else -rightChild!!.height-1 // Otherwise, we have a left subtree so if we // don't have a right one, return the left's // height plus one. else if (rightChild == null) leftChild!!.height+1 // Otherwise, both subtrees exist so subtract // them to return the difference. else leftChild!!.height-rightChild!!.height // ------------------------------------------------ // Get the actual data. fun getData() = element // ------------------------------------------------ // Get the height. fun getHeight() = height // ------------------------------------------------ // Get the left subtree. fun getLeftChild() = leftChild // ------------------------------------------------ // Get the node's parent. fun getParent() = parent // ------------------------------------------------ // Get the right subtree. fun getRightChild() = rightChild // ------------------------------------------------ // Remove the node's parent. fun removeParent() { parent = null } // removeParent // ------------------------------------------------ // Set the left subtree. fun setLeftChild(newLeft: AVLNode?): AVLNode? { // If there is a left node, set it's parent to // be us. In any event, make it our left subtree // and update the height. if (newLeft != null) newLeft.parent = this leftChild = newLeft updateHeight() return leftChild } // setLeftChild // ------------------------------------------------ // Set the right subtree. fun setRightChild(newRight: AVLNode?): AVLNode? { // If there is a right node, set it's parent to // be us. In any event, make it our right subtree // and update the height. if (newRight != null) newRight.parent = this rightChild = newRight updateHeight() return rightChild } // setRightChild // ------------------------------------------------ // Set the node's height. fun updateHeight(): Int { // If we don't have a left subtree, check the // right. if (leftChild == null) // If we don't have either subtree, the height // is zero. if (rightChild == null) height = 0 // Otherwise, we only have the right subtree so // our height is one more than it's height. else height = rightChild!!.height+1 // Otherwise, the left subtree exists so if we // don't have a right one, our height is one // more than it's height. else if (rightChild == null) height = leftChild!!.height+1 // Otherwise, we have both subtree's so if the // left's height is greater than the right, our // height is one more than it. else if (leftChild!!.height > rightChild!!.height) height = leftChild!!.height+1 // Otherwise, the right subtree's height will be // used so our height is one more than it. else height = rightChild!!.height+1 return height } // updateHeight } // AVLNode // Adelson-Velskii and Landis dynamically balanced // binary tree class. Require the compare function // to decide left or right direction. class AVLTree(private val compare: (T, T) -> Int) { // A pointer to the top node of the tree. private var root: AVLNode? = null // -------------------------------------------------- // Balance the subtree. private fun balanceAtNode(node: AVLNode) { // Get the current balance and if it is bad // enough on the left side, rotate it right // adjusting the subtree left, if required. val bal = node.getBalance() if (bal > 1) { if (node.getLeftChild()!!.getBalance() < 0) rotateLeft(node.getLeftChild()!!); rotateRight(node) // Otherwise, if the balance is bad enough on // the right side, rotate it left adjusting the // subtree right, if required. } else if (bal < -1) { if (node.getRightChild()!!.getBalance() > 0) rotateRight(node.getRightChild()!!) rotateLeft(node) } // if } // balanceAtNode // -------------------------------------------------- // Find the node containing the data. private fun findNode(value: T): AVLNode? { // While nodes remain, if we found the right // node, exit the loop. If the value we want // is less than the current, check the left // subtree, otherwise, the right. var temp = root; while (temp != null) { if (value == temp.getData()) break else if (compare(value, temp.getData()) < 0) temp = temp.getLeftChild() else temp = temp.getRightChild() } // while return temp } // findNode // -------------------------------------------------- // Get the tree's height. fun getHeight() = root!!.getHeight() // -------------------------------------------------- // Insert the value into the tree. // Returns: // true: If addition is successful // false: If item already exists // fun insert(value: T): Boolean { // If the tree is empty, add the new node as the // root. if (root == null) root = AVLNode(value) // Otherwise, we need to find the insertion point. else { // Starting at the tree root search for the // insertion point, until we have added the // new node. var added_node: AVLNode? = null var temp = root while (temp != null && added_node == null) { // If the value is less than the current // node's value, go left. If there isn't a // left subtree, insert the node, otherwise, // it is next to check. if (compare(value, temp.getData()) < 0) { if (temp.getLeftChild() == null) { added_node = temp.setLeftChild( AVLNode(value)) } else temp = temp.getLeftChild() // Otherwise, if the value is greater than // the current node's value, go right. If // there isn't a right subtree, insert the // node, otherwise, it is next to check. } else if (compare(value, temp.getData()) > 0) { if (temp.getRightChild() == null) { added_node = temp.setRightChild( AVLNode(value)) } else temp = temp.getRightChild() // Otherwise, the value is already in the // tree so abort. } else return false } // while // From the new node upwards to the root, // updated the height and make sure the // subtree is balanced. temp = added_node while(temp != null) { temp.updateHeight() balanceAtNode(temp) temp = temp.getParent() } // while } // if return true; } // insert // -------------------------------------------------- // Print the tree in this pattern complaining if // too deep, non integer, or empty. // 08 // 04 12 // 02 06 10 14 //01 03 05 07 09 11 13 15 fun print() { // If the tree is empty, say so. if (root == null) println("Tree is empty!") // Otherwise, if the tree has a height more than 4 // (5 rows), it is too wide. If the data type isn't // an integer, we can't process it either. else if (root!!.getHeight() > 4 || root!!.getData() !is Int) println("Not currently supported!") // Otherwise, set up to display the tree. Get // the maximum depth and for each possible // level, output that level's elements and // finish off the line. else { var max = root!!.getHeight(); for (depth in 0..max) { printSubtree(root, depth, max-depth+1, true) println() } // for } // if } // print // -------------------------------------------------- // Print the subtree. The leftmost branch will have // first true. The level counts up from the bottom // for the line we are doing. The depth is how // many layers to skip over. private fun printSubtree(subtree: AVLNode?, depth: Int, level: Int, first: Boolean) { // If we need to go deeper in the subtree, do so. // If the subtree is empty, pass it down, otherwise // pass both left and right subtrees. if (depth > 0) { if (subtree == null) { printSubtree(subtree, depth-1, level, first); printSubtree(subtree, depth-1, level, false); } else { printSubtree(subtree.getLeftChild(), depth-1, level, first); printSubtree(subtree.getRightChild(), depth-1, level, false); } // if // Otherwise, if the subtree is empty, display // an empty element. The leftmost element only // needs half the spacing. } else { val space = if (first) spacing(level)/2 else spacing(level) if (subtree == null) print("%${space}s".format("-")) // Otherwise, we have a live element so display // it. Once more, use half spacing for the // leftmost element. else print("%${space}d".format(subtree.getData())) } // if } // printSubtree // -------------------------------------------------- // Remove the value from the tree. // Returns: // true: If removal is successful // false: If item is not found in the tree // fun remove(value: T): Boolean { // Find the node to delete and if none, exit. val toBeRemoved = findNode(value) if (toBeRemoved == null) return false // Get the parent and set the side the node is // on of the parent. val p = toBeRemoved.getParent() val side = if (p != null && p.getLeftChild() == toBeRemoved) AVLSide.Left; else AVLSide.Right; // If the node to be removed doesn't have a left // subtree, check it's right subtree to figure // out our next move. if (toBeRemoved.getLeftChild() == null) // If we don't have any subtrees, we are the // leaf so our parent doesn't need us. if (toBeRemoved.getRightChild() == null) { // If we don't have a parent, the tree is now // empty so change the root to null and delete // our node. if (p == null) setRoot(null) // Otherwise, change the parent so it doesn't // point to us, delete ourself, update the // parent's height, and rebalance the tree. else { if (side == AVLSide.Left) p.setLeftChild(null) else p.setRightChild(null) p.updateHeight() balanceAtNode(p) } // if // Otherwise, there is a right subtree so use // it to replace ourself. } else { // If we don't have a parent, the tree is now // the right subtree and delete our node. if (p == null) setRoot(toBeRemoved.getRightChild()) // Otherwise, change the parent so it doesn't // point to us, delete ourself, update the // parent's height, and rebalance the tree. else { if (side == AVLSide.Left) p.setLeftChild(toBeRemoved. getRightChild()) else p.setRightChild(toBeRemoved. getRightChild()) p.updateHeight() balanceAtNode(p) } // if } // if // Otherwise, we have a left subtree so check the // right one of the node being removed to decide // what is next. If there isn't a right subtree, // the left one will replace ourself. else if (toBeRemoved.getRightChild() == null) { // If we don't have a parent, the tree is now // the left subtree and delete our node. if (p == null) setRoot(toBeRemoved.getLeftChild()) // Otherwise, change the parent so it doesn't // point to us, delete ourself, update the // parent's height, and rebalance the tree. else { if (side == AVLSide.Left) p.setLeftChild(toBeRemoved. getLeftChild()) else p.setRightChild(toBeRemoved. getLeftChild()) p.updateHeight(); balanceAtNode(p); } // if // Otherwise, the node to remove has both subtrees // so decide the best method to remove it. } else { // Check the balance to see which way to go. // If the left side is deeper, modify it. var replacement: AVLNode? var replacement_parent: AVLNode? var temp_node: AVLNode? val bal = toBeRemoved.getBalance(); if (bal > 0) { // If the right subtree of the node's // left subtree is empty, we can move the // node's right subtree there. if (toBeRemoved.getLeftChild()!!. getRightChild() == null) { replacement = toBeRemoved.getLeftChild() replacement!!.setRightChild( toBeRemoved.getRightChild()); temp_node = replacement; // Otherwise, find the right most empty subtree // of our node's left subtree and it's // parent. This is our replacement. Make it's // parent point to it's left child instead // of itself. It is now free to replace the // deleted node. Copy both of the deleted // nodes subtrees into the replacement leaving // fixing up the parent below. } else { replacement = toBeRemoved. getLeftChild()!!.getRightChild() while (replacement!!.getRightChild() != null) replacement = replacement.getRightChild() replacement_parent = replacement.getParent() replacement_parent!!.setRightChild( replacement.getLeftChild()) temp_node = replacement_parent replacement.setLeftChild( toBeRemoved.getLeftChild()) replacement.setRightChild( toBeRemoved.getRightChild()) } // if // Otherwise, we are going to modify the right // side so, if the left subtree of the node's // right subtree is empty, we can move the // node's left subtree there. } else if (toBeRemoved.getRightChild()!!. getLeftChild() == null) { replacement = toBeRemoved.getRightChild() replacement!!.setLeftChild( toBeRemoved.getLeftChild()) temp_node = replacement; // Otherwise, find the left most empty subtree // of our node's right subtree and it's // parent. This is our replacement. Make it's // parent point to it's right child instead // of itself. It is now free to replace the // deleted node. Copy both of the deleted // nodes subtrees into the replacement leaving // fixing up the parent below. } else { replacement = toBeRemoved. getRightChild()!!.getLeftChild() while (replacement!!.getLeftChild() != null) replacement = replacement.getLeftChild() replacement_parent = replacement.getParent(); replacement_parent!!.setLeftChild( replacement.getRightChild()); temp_node = replacement_parent; replacement.setLeftChild( toBeRemoved.getLeftChild()); replacement.setRightChild( toBeRemoved.getRightChild()); } // if // Fix the parent to point to the new root. // If there isn't a parent, update the actual // tree root. Otherwise, there is a parent so // if we were the left subtree, update it, // otherwise, the right. In all cases, delete // the node and rebalance the tree. if (p == null) setRoot(replacement) else if (side == AVLSide.Left) p.setLeftChild(replacement) else p.setRightChild(replacement) balanceAtNode(temp_node); } // if return true } // remove // ------------------------------------------------- // Rotate the subtree left. private fun rotateLeft(node: AVLNode) { // Get the node's parent and if it exists and the // node was it's left subtree, remember we are // processing the left, otherwise, the right. val p = node.getParent() val side = if (p != null && p.getLeftChild() == node) AVLSide.Left else AVLSide.Right // Get the node's right subtree as the new root // and that subtree's left subtree. Make that // left subtree the node's new right. Put our // original node as the left subtree of our // new root. val temp = node.getRightChild()!! node.setRightChild(temp.getLeftChild()) temp.setLeftChild(node) // Fix the original parent to point to the new // root. If there isn't a parent, update the // actual tree root. Otherwise, there is a // parent so if we were the left subtree, update // it, otherwise, the right. if (p == null) setRoot(temp) else if (side == AVLSide.Left) p.setLeftChild(temp) else p.setRightChild(temp) } // rotateLeft // ------------------------------------------------- // Rotate the subtree right. private fun rotateRight(node: AVLNode) { // Get the node's parent and if it exists and the // node was it's left subtree, remember we are // processing the left, otherwise, the right. val p = node.getParent() var side: AVLSide = if (p != null && p.getLeftChild() == node) AVLSide.Left else AVLSide.Right // Get the node's left subtree as the new root // and that subtree's right subtree. Make that // right subtree the node's new left. Put our // original node as the right subtree of our // new root. val temp = node.getLeftChild()!! node.setLeftChild(temp.getRightChild()) temp.setRightChild(node) // Fix the original parent to point to the new // root. If there isn't a parent, update the // actual tree root. Otherwise, there is a // parent so if we were the left subtree, update // it, otherwise, the right. if (p == null) setRoot(temp) else if (side == AVLSide.Left) p.setLeftChild(temp) else p.setRightChild(temp) } // rotateRight // ------------------------------------------------- // Set the root. Change the tree root to the node // and if it exists, remove it's parent. private fun setRoot(node: AVLNode?) { root = node if (root != null) root!!.removeParent() } // setRoot // ------------------------------------------------- // Figure out the default spacing for element. Each // higher level doubles the preceeding. The bottom // level is one. private fun spacing(level: Int): Int { var result = 2 for (i in 0 until level) result += result return result } // spacing } // AVLTree //================================================== // The following are the classes required for a // generic hash table structure supporting any type. // Data class for a node storing the element and a // link to the next node in the hash table forming // a link list. data class LinkList(val value: T, var next: LinkList?) // Class to provide a generic hash table. Duplicate keys // are stored in a link list. Need the maximum key value // to allocate the array and two functions. The first // must give the key for the element. The second must // return -1, 0, or 1 stating the compareTo like result. class HashTable(private val maxKey: Int, private val getKey: (T) -> Int, private val compare: (T, T) -> Int) { // Keep track of the number of elements being stored in // our hash table and the array for the table. private var size = 0 private val table = Array?>(maxKey) {null} // Method to return the number of elements in the table. fun count() = size // Method to search for the element in the table. The // only required fields in element is whatever is used // by the compare function passed in during the hash // table creation. It will be called for each element // until it states they are equal or we ran out of them. fun find(element: T): T? { // Get the key for the current element, get the // first element within the table, default the // found element to null, and search the link list. val key = getKey(element) var link = table[key] var result: T? = null while (link != null) { // If the compare states the elements match, // store the real element into the result to // return and exit the loop. val match = compare(link.value, element) if (match == 0) { result = link.value break // Otherwise, if this element is greater than, // the one we are looking for, it doesn't exist // so exit the loop. } else if (match > 0) break // Otherwise, the element is less than the one // we are looking for so keep going. link = link.next } // while return result } // find // Method to create a linked list from the hash // table. fun getList(): LinkList? { // The head of the resultant link list. var head: LinkList? = null // Function to add an element to the list. fun add(element: T) { // If the list is empty, just store the new // element as the head of the list. if (head == null) head = LinkList(element, null) // Otherwise, we need to figure out where the // element must be placed. else { // Allocate the new node, setup the first node, // the previous node, and for each node in the // linked list, check to see if we need to insert // our element here. val node = LinkList(element, null) var link = head var last: LinkList? = null while (link != null && compare(link.value, element) < 0) { last = link link = link.next; } // while // If the new element is first, stuff it there. if (last == null) { node.next = head head = node // Otherwise, the new element is in the middle // or end so stuff it there. } else { node.next = last.next last.next = node } // if } // if } // add // Create a lambda to do the processing and // process all elements in the table. var get = {element: T -> add(element)} process(get) return head } // getList // Method to insert a new element into the hash // table. fun insert(element: T) { val key = getKey(element) if (table[key] == null) table[key] = LinkList(element, null) else { // Allocate the new node, setup the first node, // the previous node, and for each node in the // hash table, check to see if we need to insert // our element here. val node = LinkList(element, null) var link = table[key] var last: LinkList? = null while (link != null && compare(link.value, element) < 0) { last = link link = link.next; } // while // If the new element is first, stuff it there. if (last == null) { node.next = table[key] table[key] = node // Otherwise, the new element is in the middle // or end so stuff it there. } else { node.next = last.next last.next = node } // if } // if // Increment the number of elements in the table. size++ } // insert // Method to merge two hash tables. Get a linked list // from the second table and for each element in it, // insert it into our table. fun merge(second: HashTable) { var list = second.getList() while (list != null) { insert(list.value) list = list.next } // while } // merge // Method to process every element in the hash // table. Loop throught the array and the linked // list it contains to call the passed in function. private fun process(yield: (T) -> Unit) { for (index in 0 until maxKey) { var link = table[index] while (link != null) { yield(link.value) link = link.next } // while } // for } // process // Method to remove an element from the hash table. fun remove(element: T) { // Get the key for the current element, get the // first element within the table, default the // found element to null, and search the link list. val key = getKey(element) var link = table[key] var last: LinkList? = null while (link != null) { // If the compare states the elements match, // remove the element from the list, decrement // the table size, and exit the loop. val match = compare(link.value, element) if (match == 0) { if (last == null) table[key] = link.next else last.next = link.next size-- break // Otherwise, if this element is greater than, // the one we are looking for, it doesn't exist // so exit the loop. } else if (match > 0) break // Otherwise, the element is less than the one // we are looking for so keep going. last = link link = link.next } // while } // remove // Method to create a binary search tree out of the // hash table. We will use the AVL version we had coded // in C++. Allocate the tree, make a lambda function // to do the insert of each element, and call the // method to process each element in the table. fun toBST(): AVLTree { val tree = AVLTree(compare) val add = {element: T -> val x = tree.insert(element)} process(add) return tree } // toStack // Method to create a queue out of the hash table. We // created a simple class for this. Allocate the // queue, make a lambda function to do the insert of // each element, and call the method to process each // element in the table. fun toQueue(): Queue { val queue = Queue() val add = {element: T -> queue.enqueue(element)} process(add) return queue } // toStack // Method to create a stack out of the hash table. We // created a simple class for this. Allocate the // stack, make a lambda function to do the insert of // each element, and call the method to process each // element in the table. fun toStack(): Stack { val stack = Stack() val add = {element: T -> stack.push(element)} process(add) return stack } // toStack } // hashTable //================================================== // Various test functions and the main program. data class Data(val key: String, val info: String) fun realUsage() { fun getKey(key: String): Int { var result = 0 for (c in key) result = result xor c.toInt() return result%10 } // getKey val key = {element: Data -> getKey(element.key)} val compare = {first: Data, second: Data -> first.key.compareTo(second.key)} val hash = HashTable(10, key, compare) hash.insert(Data("John Smith", "521-1234")) hash.insert(Data("Lisa Smith", "521-8976")) hash.insert(Data("Sam Doe", "521-5030")) hash.insert(Data("Sandra Dee", "521-9655")) hash.insert(Data("Ted Baker", "418-4165")) println("\nOriginal table:") var stack = hash.toStack() while (!stack.isEmpty()) { val element = stack.pop() println("${element.key} ${element.info}") } // while var element = hash.find(Data("Lisa Smith", "")) println("Found: ${element?.key} ${element?.info}") hash.remove(Data("Lisa Smith", "")) println("\nUpdated table:") stack = hash.toStack() while (!stack.isEmpty()) { element = stack.pop() println("${element.key} ${element.info}") } // while } // realUsage // Function to test the queue to make sure it works. // Inserts: 5, 4, 3, 2, & 1; Removes: 5, 4, 3, 2, & 1. fun testQueue() { val queue = Queue() for (element in 5 downTo 1) queue.enqueue(element) print("Queue ") while (!queue.isEmpty()) print("${queue.dequeue()} ") println() } // testQueue // Function to test the stack to make sure it works. // Inserts: 5, 4, 3, 2, & 1; Removes: 1, 2, 3, 4, & 5. fun testStack() { val stack = Stack() for (element in 5 downTo 1) stack.push(element) print("Stack ") while (!stack.isEmpty()) print("${stack.pop()} ") println() } // testStack // Function to test the AVL tree to make sure it works. // Inserts: 5, 3, 1, 4, & 2; Removes: 3, 1, 4, 2, & 5. fun testAVL() { val compare = {first: Int, second: Int -> first.compareTo(second)} val tree = AVLTree(compare) var count = 4 println("AVL Tree:") for (index in 1..5) { tree.insert(count%5+1) if (index == 3) tree.print() count += 3 } // for println() tree.print() println() count = 2 for (index in 1..5) { tree.remove(count%5+1) if (index == 3) tree.print() count += 3 } // for println() tree.print() } // testAVL fun testHash() { val key = {element: Int -> element%2} val compare = {first: Int, second: Int -> first.compareTo(second)} val hash = HashTable(2, key, compare) for (element in 5 downTo 1) hash.insert(element) val bst = hash.toBST() println() println("Table has ${hash.count()} elements") println() println("Binary search tree:") bst.print() println() val queue = hash.toQueue() print("Queue ") while (!queue.isEmpty()) print("${queue.dequeue()} ") println() val stack = hash.toStack() print("Stack ") while (!stack.isEmpty()) print("${stack.pop()} ") println() val hash2 = HashTable(2, key, compare) for (element in 10 downTo 6) hash2.insert(element) hash.merge(hash2) var list = hash.getList() print("List ") while (list != null) { print("${list.value} ") list = list.next } // while println() for (element in 0..10 step 2) hash.remove(element) list = hash.getList() print("List ") while (list != null) { print("${list.value} ") list = list.next } // while println() } // testHash // Main program to test each of the data structures. fun main(args: Array) { testQueue() testStack() testAVL() testHash() realUsage() } // main

hashtable ch