SHARE
TWEET

Juliet

a guest Mar 10th, 2010 128 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace Juliet.Collections.Immutable
  5. {
  6.     public abstract class BaseBinaryTree<TreeType, T>
  7.         where TreeType : BaseBinaryTree<TreeType, T>
  8.     {
  9.         protected readonly Func<T, T, int> Comparer;
  10.  
  11.         public BaseBinaryTree(Func<T, T, int> comparer)
  12.         {
  13.             this.Comparer = comparer;
  14.         }
  15.  
  16.         protected abstract TreeType Self();
  17.         protected abstract U Match<U>(Func<U> nilFunc, Func<TreeType, T, TreeType, U> nodeFunc);
  18.         protected abstract TreeType CreateNode(TreeType left, T value, TreeType right);
  19.  
  20.         public virtual TreeType Insert(T value)
  21.         {
  22.             return this.Match(
  23.                 () => CreateNode(Self(), value, Self()),
  24.                 (l, x, r) =>
  25.                     {
  26.                         int compare = this.Comparer(value, x);
  27.                         if (compare < 0) { return CreateNode(l.Insert(value), x, r); }
  28.                         else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); }
  29.                         else { return Self(); }
  30.                     });
  31.         }
  32.     }
  33.  
  34.     public abstract class DerivedAvlTree<T> : BaseBinaryTree<DerivedAvlTree<T>, T>
  35.     {
  36.         #region Nodes
  37.         private sealed class Nil : DerivedAvlTree<T>
  38.         {
  39.             public Nil(Func<T, T, int> comparer) : base(comparer) { }
  40.  
  41.             protected override U Match<U>(Func<U> nilFunc, Func<DerivedAvlTree<T>, T, DerivedAvlTree<T>, U> nodeFunc)
  42.             {
  43.                 return nilFunc();
  44.             }
  45.  
  46.             protected override int GetCount() { return 0; }
  47.             protected override int GetHeight() { return 0; }
  48.         }
  49.  
  50.         private sealed class Node : DerivedAvlTree<T>
  51.         {
  52.             DerivedAvlTree<T> left;
  53.             T value;
  54.             DerivedAvlTree<T> right;
  55.             int count;
  56.             int height;
  57.  
  58.             public Node(Func<T, T, int> comparer, DerivedAvlTree<T> left, T value, DerivedAvlTree<T> right)
  59.                 : base(comparer)
  60.             {
  61.                 this.left = left;
  62.                 this.value = value;
  63.                 this.right = right;
  64.                 this.count = left.Count + right.Count + 1;
  65.                 this.height = Math.Max(left.Height, right.Height) + 1;
  66.             }
  67.  
  68.             protected override U Match<U>(Func<U> nilFunc, Func<DerivedAvlTree<T>, T, DerivedAvlTree<T>, U> nodeFunc)
  69.             {
  70.                 return nodeFunc(this.left, this.value, this.right);
  71.             }
  72.  
  73.             protected override int GetCount() { return count; }
  74.             protected override int GetHeight() { return height; }
  75.         }
  76.         #endregion
  77.  
  78.         public static DerivedAvlTree<T> Create(Func<T, T, int> comparer)
  79.         {
  80.             return new Nil(comparer);
  81.         }
  82.  
  83.         protected DerivedAvlTree(Func<T, T, int> comparer)
  84.             : base(comparer)
  85.         {
  86.         }
  87.  
  88.         #region BaseBinaryTree implementation
  89.         protected override DerivedAvlTree<T> CreateNode(DerivedAvlTree<T> left, T value, DerivedAvlTree<T> right)
  90.         {
  91.             return new Node(this.Comparer, left, value, right);
  92.         }
  93.  
  94.         protected override DerivedAvlTree<T> Self()
  95.         {
  96.             return this;
  97.         }
  98.  
  99.         #endregion
  100.  
  101.         protected abstract int GetCount();
  102.         protected abstract int GetHeight();
  103.  
  104.         protected int Height { get { return GetHeight(); } }
  105.         public int Count { get { return GetCount(); } }
  106.  
  107.         protected int BalanceFactor
  108.         {
  109.             get
  110.             {
  111.                 return this.Match(
  112.                     () => 0,
  113.                     (l, x, r) => l.Height - r.Height);
  114.             }
  115.         }
  116.  
  117.         public override DerivedAvlTree<T> Insert(T value)
  118.         {
  119.             return base.Insert(value).Balance();
  120.         }
  121.  
  122.         protected DerivedAvlTree<T> Balance()
  123.         {
  124.             int balanceFactor = this.BalanceFactor;
  125.             if (balanceFactor >= 2)
  126.             {
  127.                 // heavy left side
  128.  
  129.                 int innerBalanceFactor =
  130.                     this.Match(
  131.                         () => 0,
  132.                         (l, x, r) => l.BalanceFactor);
  133.  
  134.                 if (innerBalanceFactor >= 1)
  135.                 {
  136.                     // left-left case
  137.                     return this.RotateRight();
  138.                 }
  139.                 else if (innerBalanceFactor <= -1)
  140.                 {
  141.                     // left-right case
  142.                     return this.RotateDoubleRight();
  143.                 }
  144.             }
  145.             else if (balanceFactor <= -2)
  146.             {
  147.                 // heavy right side
  148.                 int innerBalanceFactor =
  149.                     this.Match(
  150.                         () => 0,
  151.                         (l, x, r) => r.BalanceFactor);
  152.  
  153.                 if (innerBalanceFactor >= 1)
  154.                 {
  155.                     // right-left case
  156.                     return this.RotateDoubleLeft();
  157.                 }
  158.                 else if (innerBalanceFactor <= -1)
  159.                 {
  160.                     // right-right case
  161.                     return this.RotateLeft();
  162.                 }
  163.             }
  164.  
  165.             return this;
  166.         }
  167.  
  168.         /// <summary>
  169.         /// Left tree rotation.
  170.         /// </summary>
  171.         /// <remarks>
  172.         ///       q      Right Rotation       p
  173.         ///     /   \    --------------+    /   \
  174.         ///    p     c                     a     q
  175.         ///   / \        Left Rotation          / \
  176.         ///  a   b       +-------------        b   c
  177.         /// </remarks>
  178.         protected DerivedAvlTree<T> RotateLeft()
  179.         {
  180.             return this.Match(
  181.                 () => this,
  182.                 (a, p, q) => q.Match(
  183.                     () => this,
  184.                     (b, qx, c) => CreateNode(CreateNode(a, p, b), qx, c)));
  185.         }
  186.  
  187.         /// <summary>
  188.         /// Right tree rotation
  189.         /// </summary>
  190.         /// <remarks>
  191.         ///       q      Right Rotation       p
  192.         ///     /   \    --------------+    /   \
  193.         ///    p     c                     a     q
  194.         ///   / \        Left Rotation          / \
  195.         ///  a   b       +-------------        b   c
  196.         /// </remarks>
  197.         protected DerivedAvlTree<T> RotateRight()
  198.         {
  199.             return this.Match(
  200.                 () => this,
  201.                 (p, q, c) => p.Match(
  202.                     () => this,
  203.                     (a, px, b) => CreateNode(a, px, CreateNode(b, q, c))));
  204.         }
  205.  
  206.         /// <summary>
  207.         /// Performs a double left rotation
  208.         /// </summary>
  209.         /// <remarks>
  210.         ///     p                       p                       q
  211.         ///   /   \                    / \                    /   \
  212.         ///  a      r                 a   q                 p       r
  213.         ///       /   \    ---------+    / \    -------+   / \     / \
  214.         ///      q     d                b   r             a   b   c   d  
  215.         ///     / \                        / \
  216.         ///    b   c                      c   d
  217.         /// </remarks>
  218.         protected DerivedAvlTree<T> RotateDoubleLeft()
  219.         {
  220.             return this.Match(
  221.                 () => this,
  222.                 (l, x, r) => CreateNode(l, x, r.RotateRight()).RotateLeft());
  223.         }
  224.  
  225.         /// <summary>
  226.         /// Performs a double right rotation
  227.         /// </summary>
  228.         /// <remarks>
  229.         ///        r                        r                   q
  230.         ///      /   \                     / \                /   \
  231.         ///    p      d                   q   d             p       r
  232.         ///  /   \         ---------+    / \    -------+   / \     / \
  233.         /// a     q                     p   c             a   b   c   d
  234.         ///      / \                   / \
  235.         ///     b   c                 a   b
  236.         /// </remarks>
  237.         protected DerivedAvlTree<T> RotateDoubleRight()
  238.         {
  239.             return this.Match(
  240.                 () => this,
  241.                 (l, x, r) => CreateNode(l.RotateLeft(), x, r).RotateRight());
  242.         }
  243.     }
  244. }
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