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