daily pastebin goal
84%
SHARE
TWEET

Untitled

a guest Oct 12th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. private class SkipList<T> : IEnumerable<T>
  2.         {
  3.             private Node<T> head;
  4.             private Node<T> bottomHead;
  5.             public int Count { get { return count; } }
  6.             private int count;
  7.             private Random r;
  8.             Comparer<T> comparer;
  9.             public T Min { get { return bottomHead.Next.Val; } }
  10.  
  11.             public SkipList()
  12.             {
  13.                 comparer = Comparer<T>.Default;
  14.                 r = new Random();
  15.                 count = 0;
  16.                 head = new Node<T>();
  17.                 bottomHead = head;
  18.             }
  19.  
  20.             public void Add(T val)
  21.             {
  22.                 Node<Node<T>> savedHead = null;
  23.  
  24.                 // Find insert location
  25.                 var node = head;
  26.                 while (true)
  27.                 {
  28.                     if (node.Next != null && comparer.Compare(node.Next.Val, val) != 1)
  29.                         node = node.Next;
  30.                     else if (node.Down != null)
  31.                     {
  32.                         savedHead = new Node<Node<T>>(node, savedHead, null);
  33.                         node = node.Down;
  34.                     }
  35.                     else
  36.                         break;
  37.                 }
  38.  
  39.                 // Add node
  40.                 var newNode = new Node<T>(val, node.Next, null);
  41.                 node.Next = newNode;
  42.                 // Add layers until coinflip is lost
  43.                 while (r.Next(0, 2) == 1)
  44.                 {
  45.                     var newerNode = new Node<T>(val, null, newNode);
  46.                     if (savedHead != null)
  47.                     {
  48.                         newerNode.Next = savedHead.Val.Next;
  49.                         savedHead.Val.Next = newerNode;
  50.                         savedHead = savedHead.Next;
  51.                     }
  52.                     else
  53.                     {
  54.                         var newHead = new Node<T>(default(T), newerNode, head);
  55.                         head = newHead;
  56.                     }
  57.                     newNode = newerNode;
  58.                 }
  59.                 ++count;
  60.             }
  61.  
  62.             public bool Remove(T val)
  63.             {
  64.                 Node<Node<T>> savedHead = null;
  65.                 bool deletedOne = false;
  66.                 // Find node that points to the ndoe we want to delete
  67.                 var node = head;
  68.                 while (node != null)
  69.                 {
  70.                     while (true)
  71.                     {
  72.                         if (node.Next != null && comparer.Compare(node.Next.Val, val) == -1)
  73.                             node = node.Next;
  74.                         else if (node.Next != null && comparer.Compare(node.Next.Val, val) == 0)
  75.                             break;
  76.                         else if (node.Down != null)
  77.                         {
  78.                             savedHead = new Node<Node<T>>(node, savedHead, null);
  79.                             node = node.Down;
  80.                         }
  81.                         else
  82.                             break;
  83.                     }
  84.  
  85.                     if (node.Next == null || comparer.Compare(node.Next.Val, val) != 0) break;
  86.                     deletedOne = true;
  87.                     node.Next = node.Next.Next;
  88.                     node = node.Down;
  89.                 }
  90.                 --count;
  91.                 return deletedOne;
  92.             }
  93.  
  94.             public bool Contains(T val)
  95.             {
  96.                 throw new NotImplementedException();
  97.             }
  98.  
  99.             public override string ToString()
  100.             {
  101.                 var sb = new StringBuilder();
  102.                 var levelNode = head;
  103.                 while (levelNode != null)
  104.                 {
  105.                     var node = levelNode.Next;
  106.                     while (node != null)
  107.                     {
  108.                         sb.Append(node.Val + "->");
  109.                         node = node.Next;
  110.                     }
  111.                     levelNode = levelNode.Down;
  112.                     sb.Append('\n');
  113.                 }
  114.                 return sb.ToString();
  115.             }
  116.  
  117.             public IEnumerator<T> GetEnumerator()
  118.             {
  119.                 var node = bottomHead;
  120.                 while (node.Next != null)
  121.                 {
  122.                     node = node.Next;
  123.                     yield return node.Val;
  124.                 }
  125.             }
  126.  
  127.             IEnumerator IEnumerable.GetEnumerator()
  128.             {
  129.                 return this.GetEnumerator();
  130.             }
  131.  
  132.             private class Node<T>
  133.             {
  134.                 public T Val;
  135.                 public Node<T> Next;
  136.                 public Node<T> Down;
  137.                 public Node() { }
  138.                 public Node(T val, Node<T> next, Node<T> down)
  139.                 {
  140.                     Val = val; Next = next; Down = down;
  141.                 }
  142.             }
  143.         }
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