Over a million developers have joined DZone.
Platinum Partner

Scala Tree Sort Example

· Big Data Zone

The Big Data Zone is presented by Exaptive.  Learn about how to rapidly iterate data applications, while reusing existing code and leveraging open source technologies.

This 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);
}



The Big Data Zone is presented by Exaptive.  Learn howrapid data application development can address the data science shortage.

Topics:

Published at DZone with permission of Gary Sieling , DZone MVB .

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}