Scala Tree Sort Example
Join the DZone community and get the full member experience.
Join For FreeThis demonstrates basic language features – case classes, iteration, anonymous functions, etc.
abstract class Node case class LeafNode(data: String) extends Node; case class FullNode(data: String, left: Node, right: Node) extends Node case class LeftNode(data: String, left: Node) extends Node case class RightNode(data: String, right: Node) extends Node object test extends App { val words = List("revertively", "dispelled", "overmoral", "sylphid", "nonhabitability", "noiselessness", "undisconnected", "shoveling", "visalia", "ilo"); def construct(A: List[String]): Node = { def insert(tree: Node, value: String): Node = { tree match { case null => LeafNode(value) case LeafNode(data) => if (value > data) { LeftNode(data, LeafNode(value)) } else { RightNode(data, LeafNode(value)) } case LeftNode(data, left) => if (value > data) { LeftNode(value, LeftNode(data, left)) } else { FullNode(data, left, LeafNode(value)) } case RightNode(data, right) => if (value > data) { FullNode(data, LeafNode(value), right) } else { RightNode(value, RightNode(data, right)) } case FullNode(data, left, right) => if (value > data) { FullNode(data, insert(left, value), right) } else { FullNode(data, left, insert(right, value)) } } } var tree: Node = null; for (item <- A) { tree = insert(tree, item) } return tree }; val f = (A: String) => System.out.println(A); words.map(f); var x = construct(words); def recurseNode(A: Node, depth: Int) { def display(data: String, depth: Int) { for (i <- 1 to depth * 2) { System.out.print("-") } System.out.println(data); } A match { case null => { display("[]", depth) } case LeafNode(data) => { display(data, depth) recurseNode(null, depth + 1) recurseNode(null, depth + 1) } case FullNode(data, left, right) => { display(data, depth) recurseNode(left, depth + 1) recurseNode(right, depth + 1) } case RightNode(data, right) => { display(data, depth) recurseNode(null, depth + 1) recurseNode(right, depth + 1) } case LeftNode(data, left) => { display(data, depth) recurseNode(left, depth + 1) recurseNode(null, depth + 1) } } } def output(A: Node, recurse: (Node, Int) => Unit) = { recurse(A, 0) } def renderTree(A: Node) = { output(x, recurseNode); } renderTree(x); def sortedRender(A: Node, depth: Int) { def display(data: String, depth: Int) { System.out.println(data); } A match { case null => { } case LeafNode(data) => { display(data, depth) } case FullNode(data, left, right) => { sortedRender(left, depth + 1) display(data, depth) sortedRender(right, depth + 1) } case RightNode(data, right) => { sortedRender(null, depth + 1) display(data, depth) sortedRender(right, depth + 1) } case LeftNode(data, left) => { sortedRender(left, depth + 1) display(data, depth) } } } def renderTreeSorted(A: Node) = { output(x, sortedRender); } System.out.println("") renderTreeSorted(x); }
Scala (programming language)
Tree (data structure)
Sort (Unix)
Published at DZone with permission of Gary Sieling, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Trending
-
What to Pay Attention to as Automation Upends the Developer Experience
-
Constructing Real-Time Analytics: Fundamental Components and Architectural Framework — Part 2
-
Web Development Checklist
-
Alpha Testing Tutorial: A Comprehensive Guide With Best Practices
Comments