beagled/Lucene.Net/Util/PriorityQueue.cs

   1 /*
   2  * Copyright 2004 The Apache Software Foundation
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 using System;
  18
  19 namespace Lucene.Net.Util
  20 {
  21
  22         /// <summary>A PriorityQueue maintains a partial ordering of its elements such that the
  23         /// least element can always be found in constant time.  Put()'s and pop()'s
  24         /// require log(size) time.
  25         /// </summary>
  26         public abstract class PriorityQueue
  27         {
  28                 private System.Object[] heap;
  29                 private int size;
  30                 private int maxSize;
  31
  32                 /// <summary>Determines the ordering of objects in this priority queue.  Subclasses
  33                 /// must define this one method.
  34                 /// </summary>
  35                 public abstract bool LessThan(System.Object a, System.Object b);
  36
  37                 /// <summary>Subclass constructors must call this. </summary>
  38                 protected internal void  Initialize(int maxSize)
  39                 {
  40                         size = 0;
  41                         int heapSize = maxSize + 1;
  42                         heap = new System.Object[heapSize];
  43                         this.maxSize = maxSize;
  44                 }
  45
  46                 /// <summary> Adds an Object to a PriorityQueue in log(size) time.
  47                 /// If one tries to add more objects than maxSize from initialize
  48                 /// a RuntimeException (ArrayIndexOutOfBound) is thrown.
  49                 /// </summary>
  50                 public void  Put(System.Object element)
  51                 {
  52                         size++;
  53                         heap[size] = element;
  54                         UpHeap();
  55                 }
  56
  57                 /// <summary> Adds element to the PriorityQueue in log(size) time if either
  58                 /// the PriorityQueue is not full, or not lessThan(element, top()).
  59                 /// </summary>
  60                 /// <param name="element">
  61                 /// </param>
  62                 /// <returns> true if element is added, false otherwise.
  63                 /// </returns>
  64                 public virtual bool Insert(System.Object element)
  65                 {
  66                         if (size < maxSize)
  67                         {
  68                                 Put(element);
  69                                 return true;
  70                         }
  71                         else if (size > 0 && !LessThan(element, Top()))
  72                         {
  73                                 heap[1] = element;
  74                                 AdjustTop();
  75                                 return true;
  76                         }
  77                         else
  78                                 return false;
  79                 }
  80
  81                 /// <summary>Returns the least element of the PriorityQueue in constant time. </summary>
  82                 public System.Object Top()
  83                 {
  84                         if (size > 0)
  85                                 return heap[1];
  86                         else
  87                                 return null;
  88                 }
  89
  90                 /// <summary>Removes and returns the least element of the PriorityQueue in log(size)
  91                 /// time.
  92                 /// </summary>
  93                 public System.Object Pop()
  94                 {
  95                         if (size > 0)
  96                         {
  97                                 System.Object result = heap[1]; // save first value
  98                                 heap[1] = heap[size]; // move last to first
  99                                 heap[size] = null; // permit GC of objects
 100                                 size--;
 101                                 DownHeap(); // adjust heap
 102                                 return result;
 103                         }
 104                         else
 105                                 return null;
 106                 }
 107
 108                 /// <summary>Should be called when the Object at top changes values.  Still log(n)
 109                 /// worst case, but it's at least twice as fast to <pre>
 110                 /// { pq.top().change(); pq.adjustTop(); }
 111                 /// </pre> instead of <pre>
 112                 /// { o = pq.pop(); o.change(); pq.push(o); }
 113                 /// </pre>
 114                 /// </summary>
 115                 public void  AdjustTop()
 116                 {
 117                         DownHeap();
 118                 }
 119
 120
 121                 /// <summary>Returns the number of elements currently stored in the PriorityQueue. </summary>
 122                 public int Size()
 123                 {
 124                         return size;
 125                 }
 126
 127                 /// <summary>Removes all entries from the PriorityQueue. </summary>
 128                 public void  Clear()
 129                 {
 130                         for (int i = 0; i <= size; i++)
 131                                 heap[i] = null;
 132                         size = 0;
 133                 }
 134
 135                 private void  UpHeap()
 136                 {
 137                         int i = size;
 138                         System.Object node = heap[i]; // save bottom node
 139                         int j = SupportClass.Number.URShift(i, 1);
 140                         while (j > 0 && LessThan(node, heap[j]))
 141                         {
 142                                 heap[i] = heap[j]; // shift parents down
 143                                 i = j;
 144                                 j = SupportClass.Number.URShift(j, 1);
 145                         }
 146                         heap[i] = node; // install saved node
 147                 }
 148
 149                 private void  DownHeap()
 150                 {
 151                         int i = 1;
 152                         System.Object node = heap[i]; // save top node
 153                         int j = i << 1; // find smaller child
 154                         int k = j + 1;
 155                         if (k <= size && LessThan(heap[k], heap[j]))
 156                         {
 157                                 j = k;
 158                         }
 159                         while (j <= size && LessThan(heap[j], node))
 160                         {
 161                                 heap[i] = heap[j]; // shift up child
 162                                 i = j;
 163                                 j = i << 1;
 164                                 k = j + 1;
 165                                 if (k <= size && LessThan(heap[k], heap[j]))
 166                                 {
 167                                         j = k;
 168                                 }
 169                         }
 170                         heap[i] = node; // install saved node
 171                 }
 172         }
 173 }