SHARE
TWEET

Untitled

a guest Sep 15th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package utils.datastructures.containers
  2.  
  3. import scala.collection.mutable
  4.  
  5.  
  6. object ThreadedAVLTree {
  7.   type OptNode[T] = Option[TreeNode[T]]
  8.  
  9.   /**
  10.     *
  11.     * @param value         value stored in node
  12.     * @param balanceFactor H(L) - H(R)
  13.     * @param parent        node None if this node is root
  14.     * @param left          subtree
  15.     * @param right         subtree
  16.     * @param next          node ordered by 'value'
  17.     * @param prev          node ordered by 'value
  18.     * @tparam T type
  19.     */
  20.   class TreeNode[T](
  21.                      var value: T,
  22.                      var balanceFactor: Int = 0,
  23.                      var parent: OptNode[T] = None,
  24.                      var left: OptNode[T] = None,
  25.                      var right: OptNode[T] = None,
  26.                      var next: OptNode[T] = None,
  27.                      var prev: OptNode[T] = None,
  28.                    ) {
  29.  
  30.     override def toString = s"TreeNode(value=$value, balanceFactor=$balanceFactor)"
  31.   }
  32.  
  33.   class ThreadedAVLTree[T](implicit o: Ordering[T]) {
  34.  
  35.     private var _size: Int = 0
  36.  
  37.     def size: Int = _size
  38.  
  39.     var root: OptNode[T] = None
  40.  
  41.     //    @inline def goLeft(nodeValue: T, value: T): Int = o.compare(nodeValue, value)
  42.  
  43.  
  44.     def add(toAdd: T): TreeNode[T] = {
  45.       if (root.isEmpty) {
  46.         root = Some(new TreeNode[T](toAdd, 0))
  47.         _size += 1
  48.         return root.get
  49.       } else {
  50.         var parent: TreeNode[T] = root.get
  51.         var current: OptNode[T] = root
  52.         var direction: Int = 0
  53.         while (current.isDefined) { //while we on existing node go deeper
  54.           parent = current.get
  55.           direction = o.compare(toAdd, parent.value) // -1 go left, 1 go right
  56.           if (direction == 0) { //parent already holds "to left"
  57.             return parent
  58.           }
  59.           //go deeper
  60.           current = if (direction == -1) parent.left else parent.right
  61.         }
  62.         val newNode = new TreeNode[T](value = toAdd, balanceFactor = 0, parent = Some(parent))
  63.         if (direction == -1) {
  64.           parent.left = Some(newNode)
  65.         } else {
  66.           parent.right = Some(newNode)
  67.         }
  68.         newNode.next = findClothestGreaterParent(newNode)
  69.         newNode.next.foreach(_.prev = Some(newNode))
  70.         newNode.prev = findClothestLesserParent(newNode)
  71.         newNode.prev.foreach(_.next = Some(newNode))
  72.  
  73.         traverseUpAndBalance(parent, if (direction == -1) 1 else -1) //-direction
  74.         _size += 1
  75.         return newNode
  76.       }
  77.  
  78.     }
  79.  
  80.     @inline def cameFromLeft(parent: TreeNode[T], sibling: TreeNode[T]): Boolean = parent.left.isDefined && parent.left.get == sibling
  81.  
  82.     /** min node in subtree, for finding replacement while deleting */
  83.     def minNode(node: TreeNode[T]): TreeNode[T] = {
  84.       var tmp = node
  85.       while (tmp.left.isDefined) {
  86.         tmp = tmp.left.get
  87.       }
  88.       return tmp
  89.     }
  90.  
  91.     /** max node in subtree, for finding replacement while deleting */
  92.     def maxNode(node: TreeNode[T]): TreeNode[T] = {
  93.       var tmp = node
  94.       while (tmp.right.isDefined) {
  95.         tmp = tmp.right.get
  96.       }
  97.       return tmp
  98.     }
  99.  
  100.     /** for finding next and prev nodes after leaf inserted */
  101.     def findClothestLesserParent(node: TreeNode[T]): OptNode[T] = {
  102.       var parentNode = node.parent
  103.       var siblingNode = node
  104.       while (parentNode.isDefined && cameFromLeft(parentNode.get, siblingNode)) {
  105.         siblingNode = parentNode.get
  106.         parentNode = siblingNode.parent
  107.       }
  108.       return parentNode
  109.     }
  110.  
  111.     /** for finding next and prev nodes after leaf inserted */
  112.     def findClothestGreaterParent(node: TreeNode[T]): OptNode[T] = {
  113.       var parentNode = node.parent
  114.       var siblingNode = node
  115.       while (parentNode.isDefined && !cameFromLeft(parentNode.get, siblingNode)) {
  116.         siblingNode = parentNode.get
  117.         parentNode = siblingNode.parent
  118.       }
  119.       return parentNode
  120.     }
  121.  
  122.     def removeChildAndBalance(child: TreeNode[T], parent: TreeNode[T]): Unit =
  123.       if (cameFromLeft(parent, child)) {
  124.         parent.left = None
  125.         traverseUpAndBalanceOnRemove(parent, -1)
  126.       } else {
  127.         parent.right = None
  128.         traverseUpAndBalanceOnRemove(parent, 1)
  129.       }
  130.  
  131.  
  132.     def replaceChildByGrandChildAndBalance(child: TreeNode[T], grandChild: TreeNode[T], parent: TreeNode[T]): Unit =
  133.       if (cameFromLeft(parent, child)) {
  134.         parent.left = Some(grandChild)
  135.         grandChild.parent = Some(parent)
  136.         traverseUpAndBalanceOnRemove(parent, -1)
  137.       } else {
  138.         parent.right = Some(grandChild)
  139.         grandChild.parent = Some(parent)
  140.         traverseUpAndBalanceOnRemove(parent, 1)
  141.       }
  142.  
  143.     def relinkNextPrevsAndCopyVal(from: TreeNode[T], to: TreeNode[T]): Unit = {
  144.       to.value = from.value
  145.       to.prev = from.prev
  146.       from.prev.foreach(p => p.next = Some(to))
  147.       to.next = from.next
  148.       from.next.foreach(n => n.prev = Some(to))
  149.     }
  150.  
  151.     def remove(toRemove: T): Boolean = findNode(toRemove) match {
  152.       case Some(node) =>
  153.         //prev --> node --> next ==> prev --> next
  154.         node.prev.foreach { p =>
  155.           p.next = node.next //works right if node.next == None
  156.         }
  157.         node.next.foreach {
  158.           n => n.prev = node.prev
  159.         }
  160.         //node we trying to delete
  161.         var currentNode = node
  162.         var deleted = false
  163.         while (!deleted) {
  164.           (currentNode.left, currentNode.right, currentNode.parent) match {
  165.             case (None, None, None) =>
  166.               root = None
  167.               deleted = true
  168.             case (Some(l), None, None) =>
  169.               l.parent = None
  170.               root = Some(l)
  171.               deleted = true
  172.             case (None, Some(r), None) =>
  173.               r.parent = None
  174.               root = Some(r)
  175.               deleted = true
  176.             case (None, None, Some(parent)) =>
  177.               removeChildAndBalance(currentNode, parent)
  178.               deleted = true
  179.             case (Some(l), None, Some(parent)) =>
  180.               replaceChildByGrandChildAndBalance(currentNode, l, parent)
  181.               deleted = true
  182.             case (None, Some(r), Some(parent)) =>
  183.               replaceChildByGrandChildAndBalance(currentNode, r, parent)
  184.               deleted = true
  185.             case (Some(l), Some(r), _) =>
  186.               val replacement = if (currentNode.balanceFactor >= 0) { //left deeper
  187.                 maxNode(l) //rightmost in left subtree
  188.               } else {
  189.                 minNode(r) //leftmost in right subtree
  190.               }
  191.               relinkNextPrevsAndCopyVal(replacement, currentNode)
  192.               currentNode = replacement
  193.           }
  194.         }
  195.         _size -= 1
  196.         true
  197.       case None => false
  198.     }
  199.  
  200.  
  201.     private def rotateLeft(a: TreeNode[T]): TreeNode[T] = {
  202.       val b = a.right.get
  203.       a.right = b.left
  204.       //set parent if node non-empty
  205.       a.right.foreach(ar => ar.parent = Some(a)) // a.right.parent = a
  206.       b.left = Some(a)
  207.       a.parent = Some(b)
  208.       return b
  209.     }
  210.  
  211.     private def rotateRight(a: TreeNode[T]): TreeNode[T] = {
  212.       val b = a.left.get
  213.       a.left = b.right
  214.       //set parent if node non-empty
  215.       a.left.foreach(ar => ar.parent = Some(a))
  216.       b.right = Some(a)
  217.       a.parent = Some(b)
  218.       return b
  219.     }
  220.  
  221.     private def bigRotateLeft(a: TreeNode[T]): TreeNode[T] = {
  222.       val b = a.right.get
  223.       val c = b.left.get
  224.       // val p = a.left
  225.       val q = c.left
  226.       val r = c.right
  227.       //val s = b.right
  228.  
  229.       c.left = Some(a)
  230.       a.parent = Some(c)
  231.  
  232.       c.right = Some(b)
  233.       b.parent = Some(c)
  234.  
  235.       //a->p stay same
  236.       a.right = q
  237.       q.foreach(qn => qn.parent = Some(a))
  238.       b.left = r
  239.       r.foreach(rn => rn.parent = Some(b))
  240.       //b->s stay same
  241.       return c
  242.       /*a.right = Some(rotateRight(a.right.get))
  243.       a.right.get.parent = Some(a)
  244.  
  245.       return rotateLeft(a)
  246.       */
  247.  
  248.     }
  249.  
  250.     private def bigRotateRight(a: TreeNode[T]): TreeNode[T] = {
  251.       val b = a.left.get
  252.       val c = b.right.get
  253.  
  254.       //val p = b.left
  255.       val q = c.left
  256.       val r = c.right
  257.       //val s = a.right
  258.  
  259.       c.left = Some(b)
  260.       b.parent = Some(c)
  261.  
  262.       c.right = Some(a)
  263.       a.parent = Some(c)
  264.  
  265.       //b.left -> p stay
  266.       b.right = q
  267.       q.foreach(qn => qn.parent = Some(b))
  268.       a.left = r
  269.       r.foreach(qr => qr.parent = Some(a))
  270.       return c
  271.       //a.right -> s stay
  272.  
  273.       /*a.left = Some(rotateLeft(a.left.get))
  274.       a.left.get.parent = Some(a)
  275.  
  276.       return rotateRight(a)*/
  277.     }
  278.  
  279.     def traverseUpAndBalanceOnRemove(node: TreeNode[T], delta: Int): Unit = {
  280.       node.balanceFactor += delta
  281.       val balanced = balanceNode(node)
  282.       balanced.parent match {
  283.         case Some(parent) =>
  284.           if (balanced.balanceFactor == 0) { //height changed go up
  285.             traverseUpAndBalanceOnRemove(parent, if(cameFromLeft(parent, balanced)) -1 else 1)
  286.           }
  287.         case None =>
  288.           balanced.parent = None
  289.           root = Some(balanced)
  290.       }
  291.     }
  292.    
  293.     def traverseUpAndBalance(node: TreeNode[T], balanceDelta: Int): Unit = {
  294.       node.balanceFactor += balanceDelta
  295.       if (node.balanceFactor == 0) return
  296.       val balanced = balanceNode(node)
  297.       balanced.parent match {
  298.         case Some(parent) =>
  299.           if (balanced.balanceFactor == -1 || balanced.balanceFactor == 1) { //height changed go up
  300.             traverseUpAndBalance(parent, if(cameFromLeft(parent, balanced)) 1 else -1)
  301.           }
  302.         case None =>
  303.           balanced.parent = None
  304.           root = Some(balanced)
  305.       }    
  306.     }
  307.    
  308.     /** balance node if balance factor 2 or -2, changes links to parent */
  309.     def balanceNode(node: TreeNode[T]): TreeNode[T] = {
  310.       val current = node
  311.       val parent = node.parent
  312.       val leftChild: Boolean = parent match {
  313.         case Some(p) => cameFromLeft(p, node)
  314.         case None => false
  315.       }
  316.  
  317.       //right subtree deeper (and exists)
  318.       val res = if (current.balanceFactor == -2) {
  319.         val pivot = node.right.get
  320.         if (pivot.balanceFactor == -1) {
  321.           current.balanceFactor = 0
  322.           pivot.balanceFactor = 0
  323.           rotateLeft(current)
  324.         } else if (pivot.balanceFactor == 0) {
  325.           current.balanceFactor = -1
  326.           pivot.balanceFactor = 1
  327.           rotateLeft(current)
  328.         } else { //pivot.balanceFactor == 1 pivot.left subtree deeper (and exists)
  329.           val bottom = pivot.left.get
  330.           if (bottom.balanceFactor == 1) {
  331.             current.balanceFactor = 0
  332.             pivot.balanceFactor = -1
  333.             bottom.balanceFactor = 0
  334.           } else if (bottom.balanceFactor == -1) {
  335.             current.balanceFactor = 1
  336.             pivot.balanceFactor = 0
  337.             bottom.balanceFactor = 0
  338.           } else { //bottom.balanceFactor == 0
  339.             current.balanceFactor = 0
  340.             pivot.balanceFactor = 0
  341.             bottom.balanceFactor = 0
  342.           }
  343.           bigRotateLeft(current)
  344.         }
  345.       } else if (current.balanceFactor == 2) { // left subtree deeper(and exists)
  346.         val pivot = node.left.get
  347.         if (pivot.balanceFactor == 1) { // pivot.left deeper
  348.           current.balanceFactor = 0
  349.           pivot.balanceFactor = 0
  350.           rotateRight(current)
  351.         } else if (pivot.balanceFactor == 0) {
  352.           current.balanceFactor = 1
  353.           pivot.balanceFactor = -1
  354.           rotateRight(current)
  355.         } else { //pivot.balanceFactor == -1 pivot.right subtree deeper (and exists)
  356.           val bottom = pivot.right.get
  357.           if (bottom.balanceFactor == -1) {
  358.             current.balanceFactor = 0
  359.             pivot.balanceFactor = 1
  360.             bottom.balanceFactor = 0
  361.           } else if (bottom.balanceFactor == 1) {
  362.             current.balanceFactor = -1
  363.             pivot.balanceFactor = 0
  364.             bottom.balanceFactor = 0
  365.           } else { //bottom.balanceFactor == 0
  366.             current.balanceFactor = 0
  367.             pivot.balanceFactor = 0
  368.             bottom.balanceFactor = 0
  369.           }
  370.           bigRotateRight(current)
  371.         }
  372.       } else {
  373.         current
  374.       }
  375.       res.parent = parent
  376.       res.parent.foreach(p =>
  377.         if (leftChild) {
  378.           p.left = Some(res)
  379.         } else {
  380.           p.right = Some(res)
  381.         })
  382.       res
  383.     }
  384.  
  385.  
  386.  
  387.     //Accessors e.t.c.
  388.  
  389.     @inline def notContains(value: T): Boolean = !contains(value)
  390.  
  391.     @inline def contains(value: T): Boolean = containsByPredicate(current => o.compare(value, current))
  392.  
  393.     def findNode(value: T, node: OptNode[T]): OptNode[T] = node match {
  394.       case Some(n) =>
  395.         val cmp = o.compare(value, n.value) //-1 go left
  396.         if (cmp < 0) findNode(value, n.left)
  397.         else if (cmp > 0) findNode(value, n.right)
  398.         else node
  399.       case None => None
  400.     }
  401.  
  402.     def findNode(value: T): OptNode[T] = findNode(value, root)
  403.  
  404.     /** 0 - empty tree */
  405.     def height: Int = height(root)
  406.  
  407.     def height(node: OptNode[T]): Int = node match {
  408.       case Some(n) => 1 + math.max(height(n.left), height(n.right))
  409.       case None => 0
  410.     }
  411.  
  412.  
  413.     def traverseWithDeepness(f: (T, Int) => Unit): Unit = traverseWithDeepness(root, 1, f)
  414.  
  415.     def traverseWithDeepness(node: OptNode[T], deepness: Int, f: (T, Int) => Unit): Unit = node.foreach {
  416.       n =>
  417.         f(n.value, deepness)
  418.         traverseWithDeepness(n.left, deepness + 1, f)
  419.         traverseWithDeepness(n.right, deepness + 1, f)
  420.     }
  421.  
  422.  
  423.     /**
  424.       * @param pred takes node value, returns -1 go left 0 return true 1 go right
  425.       */
  426.     def containsByPredicate(pred: T => Int): Boolean = {
  427.       var current = root
  428.       while (current.isDefined) {
  429.         val cmp = pred(current.get.value) //o.compare( value, current.get.value)
  430.         if (cmp == 0) return true
  431.         if (cmp == -1) {
  432.           current = current.get.left
  433.         } else {
  434.           current = current.get.right
  435.         }
  436.       }
  437.       return false
  438.     }
  439.  
  440.     def minNode: OptNode[T] = root match {
  441.       case Some(node) =>
  442.         var current = node
  443.         while (current.left.isDefined) {
  444.           current = current.left.get
  445.         }
  446.         Some(current)
  447.       case None => None
  448.     }
  449.  
  450.     def maxNode: OptNode[T] = root match {
  451.       case Some(node) =>
  452.         var current = node
  453.         while (current.left.isDefined) {
  454.           current = current.left.get
  455.         }
  456.         Some(current)
  457.       case None => None
  458.     }
  459.  
  460.     def traverseNodes(f: TreeNode[T] => Unit): Unit = {
  461.       val toVisit: mutable.Queue[OptNode[T]] = new mutable.Queue[OptNode[T]]()
  462.       toVisit += root
  463.       while (toVisit.nonEmpty) {
  464.         val cur = toVisit.dequeue()
  465.         cur.foreach {
  466.           node =>
  467.             f(node)
  468.             toVisit += node.left
  469.             toVisit += node.right
  470.         }
  471.       }
  472.     }
  473.  
  474.     def values: Iterator[T] = valuesOrdered
  475.  
  476.     def valuesOrdered: Iterator[T] = minNode.greaterOrEquals
  477.  
  478.     def valuesOrderedReversed: Iterator[T] = maxNode.lesserOrEquals
  479.  
  480.     def min: Option[T] = minNode.map(_.value)
  481.  
  482.     def max: Option[T] = maxNode.map(_.value)
  483.  
  484.  
  485.   }
  486.  
  487.   implicit class NodeIterators[T](val node: OptNode[T]) extends AnyVal {
  488.     def greaterOrEquals: Iterator[T] = forwardIterator(node)
  489.  
  490.     def lesserOrEquals: Iterator[T] = backwardIterator(node)
  491.  
  492.     def greater: Iterator[T] = node match {
  493.       case Some(n) => forwardIterator(n.next)
  494.       case None => Iterator.empty
  495.     }
  496.  
  497.     def lesser: Iterator[T] = node match {
  498.       case Some(n) => backwardIterator(n.prev)
  499.       case None => Iterator.empty
  500.     }
  501.   }
  502.  
  503.   /** Iterator to traverse nodes from given node using .next */
  504.   def forwardIterator[T](node: OptNode[T]): Iterator[T] = new Iterator[T] {
  505.     var current: OptNode[T] = node
  506.  
  507.     override def hasNext: Boolean = current.isDefined
  508.  
  509.     override def next(): T = {
  510.       val res = current.get
  511.       current = res.next
  512.       return res.value
  513.     }
  514.   }
  515.  
  516.   /** Iterator to traverse nodes from given node  using .prev */
  517.   def backwardIterator[T](n: OptNode[T]): Iterator[T] = new Iterator[T] {
  518.     var current: OptNode[T] = n
  519.  
  520.     override def hasNext: Boolean = current.isDefined
  521.  
  522.     override def next(): T = {
  523.       val res = current.get
  524.       current = res.next
  525.       return res.value
  526.     }
  527.   }
  528.  
  529. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top