src/LibNMeCab/Core/PriorityQueue.cs

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Text;
   4
   5 namespace NMeCab.Core
   6 {
   7     public class PriorityQueue<T>
   8         where T : IComparable<T>
   9     {
  10         private class Node
  11         {
  12             public T Value;
  13
  14             public readonly LinkedList<Node> Childs = new LinkedList<Node>();
  15
  16             public Node(T value)
  17             {
  18                 this.Value = value;
  19             }
  20         }
  21
  22         private Node rootNode;
  23
  24         public int Count { get; private set; }
  25
  26         public T First { get { return this.rootNode.Value; } }
  27
  28         public void Clear()
  29         {
  30             this.rootNode = null;
  31             this.Count = 0;
  32         }
  33
  34         public void Push(T item)
  35         {
  36             this.rootNode = this.Merge(this.rootNode, new Node(item));
  37             this.Count++;
  38         }
  39
  40         public T Pop()
  41         {
  42             T ret = this.First;
  43             this.RemoveFirst();
  44             return ret;
  45         }
  46
  47         public void RemoveFirst()
  48         {
  49             this.rootNode = this.Unify(this.rootNode.Childs);
  50             this.Count--;
  51         }
  52
  53         private Node Merge(Node l, Node r)
  54         {
  55             if (l == null) return r;
  56             if (r == null) return l;
  57
  58             if (l.Value.CompareTo(r.Value) > 0)
  59             {
  60                 r.Childs.AddFirst(l);
  61                 return r;
  62             }
  63             else
  64             {
  65                 l.Childs.AddLast(r);
  66                 return l;
  67             }
  68         }
  69
  70         private Node Unify(LinkedList<Node> nodes)
  71         {
  72             if (nodes == null || nodes.Count == 0) return null;
  73
  74             Node x = nodes.First.Value;
  75             nodes.RemoveFirst();
  76             if (nodes.Count == 0) return x;
  77
  78             Node y = nodes.First.Value;
  79             nodes.RemoveFirst();
  80
  81             return this.Merge(this.Merge(x, y), this.Unify(nodes));
  82         }
  83     }
  84 }