SHARE
TWEET

Juliet

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