Lucene.Net/Util/PriorityQueue.cs

   1 using System;
   2
   3 namespace Lucene.Net.Util
   4 {
   5         /* ====================================================================
   6          * The Apache Software License, Version 1.1
   7          *
   8          * Copyright (c) 2001 The Apache Software Foundation.  All rights
   9          * reserved.
  10          *
  11          * Redistribution and use in source and binary forms, with or without
  12          * modification, are permitted provided that the following conditions
  13          * are met:
  14          *
  15          * 1. Redistributions of source code must retain the above copyright
  16          *    notice, this list of conditions and the following disclaimer.
  17          *
  18          * 2. Redistributions in binary form must reproduce the above copyright
  19          *    notice, this list of conditions and the following disclaimer in
  20          *    the documentation and/or other materials provided with the
  21          *    distribution.
  22          *
  23          * 3. The end-user documentation included with the redistribution,
  24          *    if any, must include the following acknowledgment:
  25          *       "This product includes software developed by the
  26          *        Apache Software Foundation (http://www.apache.org/)."
  27          *    Alternately, this acknowledgment may appear in the software itself,
  28          *    if and wherever such third-party acknowledgments normally appear.
  29          *
  30          * 4. The names "Apache" and "Apache Software Foundation" and
  31          *    "Apache Lucene" must not be used to endorse or promote products
  32          *    derived from this software without prior written permission. For
  33          *    written permission, please contact apache@apache.org.
  34          *
  35          * 5. Products derived from this software may not be called "Apache",
  36          *    "Apache Lucene", nor may "Apache" appear in their name, without
  37          *    prior written permission of the Apache Software Foundation.
  38          *
  39          * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  40          * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  41          * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  42          * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  43          * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  44          * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  45          * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  46          * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  47          * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  48          * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  49          * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50          * SUCH DAMAGE.
  51          * ====================================================================
  52          *
  53          * This software consists of voluntary contributions made by many
  54          * individuals on behalf of the Apache Software Foundation.  For more
  55          * information on the Apache Software Foundation, please see
  56          * <http://www.apache.org/>.
  57          */
  58
  59         /// <summary>
  60         /// A PriorityQueue maintains a partial ordering of its elements such that the
  61         /// least element can always be found in constant time.  Put()'s and Pop()'s
  62         /// require Log(size) time.
  63         /// </summary>
  64         public abstract class PriorityQueue
  65         {
  66                 private Object[] heap;
  67                 private int size;
  68                 private int maxSize;
  69
  70                 /// <summary>
  71                 /// Determines the ordering of objects in this priority queue.  Subclasses
  72                 /// must define this one method.
  73                 /// </summary>
  74                 /// <param name="a"></param>
  75                 /// <param name="b"></param>
  76                 /// <returns></returns>
  77                 protected abstract bool LessThan(Object a, Object b);
  78
  79                 /// <summary>
  80                 /// Subclass constructors must call this.
  81                 /// </summary>
  82                 /// <param name="max_size"></param>
  83                 protected void Initialize(int max_size)
  84                 {
  85                         size = 0;
  86                         int heap_size = max_size + 1;
  87                         heap = new Object[heap_size];
  88                         this.maxSize = max_size;
  89                 }
  90
  91                 /// <summary>
  92                 /// Adds an Object to a PriorityQueue in Log(size) time.
  93                 /// </summary>
  94                 /// <param name="element"></param>
  95                 public void Put(Object element)
  96                 {
  97                         size++;
  98                         heap[size] = element;
  99                         UpHeap();
 100                 }
 101
 102                 /// <summary>
 103                 /// Adds element to the PriorityQueue in log(size) time if either
 104                 /// the PriorityQueue is not full, or not lessThan(element, top()).
 105                 /// </summary>
 106                 /// <param name="element">element</param>
 107                 /// <returns>true if element is added, false otherwise.</returns>
 108                 public bool Insert(Object element)
 109                 {
 110                         if(size < maxSize)
 111                         {
 112                                 Put(element);
 113                                 return true;
 114                         }
 115                         else if(size > 0 && !LessThan(element, Top()))
 116                         {
 117                                 heap[1] = element;
 118                                 AdjustTop();
 119                                 return true;
 120                         }
 121                         else
 122                                 return false;
 123                 }
 124
 125                 /// <summary>
 126                 /// Returns the least element of the PriorityQueue in constant time.
 127                 /// </summary>
 128                 /// <returns></returns>
 129                 public Object Top()
 130                 {
 131                         if (size > 0)
 132                                 return heap[1];
 133                         else
 134                                 return null;
 135                 }
 136
 137                 /// <summary>
 138                 /// Removes and returns the least element of the PriorityQueue in Log(size)
 139                 ///     time.
 140                 /// </summary>
 141                 /// <returns></returns>
 142                 public Object Pop()
 143                 {
 144                         if (size > 0)
 145                         {
 146                                 Object result = heap[1];                          // save first value
 147                                 heap[1] = heap[size];                     // move last to first
 148                                 heap[size] = null;                        // permit GC of objects
 149                                 size--;
 150                                 DownHeap();                               // adjust heap
 151                                 return result;
 152                         }
 153                         else
 154                                 return null;
 155                 }
 156
 157                 /// <summary>
 158                 /// Should be called when the Object at top changes values.  Still Log(n)
 159                 /// worst case, but it's at least twice as fast to <pre>
 160                 /// { pq.Top().Change(); pq.AdjustTop(); }
 161                 /// </pre> instead of <pre>
 162                 /// { o = pq.Pop(); o.Change(); pq.Push(o); }
 163                 /// </pre>
 164                 /// </summary>
 165                 public void AdjustTop()
 166                 {
 167                         DownHeap();
 168                 }
 169
 170                 /// <summary>
 171                 /// Returns the number of elements currently stored in the PriorityQueue.
 172                 /// </summary>
 173                 /// <returns></returns>
 174                 public int Size()
 175                 {
 176                         return size;
 177                 }
 178
 179                 /// <summary>
 180                 /// Removes all entries from the PriorityQueue.
 181                 /// </summary>
 182                 public void Clear()
 183                 {
 184                         for (int i = 0; i <= size; i++)
 185                                 heap[i] = null;
 186                         size = 0;
 187                 }
 188
 189                 private void UpHeap()
 190                 {
 191                         int i = size;
 192                         Object node = heap[i];                    // save bottom node
 193                         int j = (int)(((uint)i) >> 1);
 194                         while (j > 0 && LessThan(node, heap[j]))
 195                         {
 196                                 heap[i] = heap[j];                        // shift parents down
 197                                 i = j;
 198                                 j = (int)(((uint)j) >> 1);
 199                         }
 200                         heap[i] = node;                           // install saved node
 201                 }
 202
 203                 private void DownHeap()
 204                 {
 205                         int i = 1;
 206                         Object node = heap[i];                    // save top node
 207                         int j = i << 1;                           // find smaller child
 208                         int k = j + 1;
 209                         if (k <= size && LessThan(heap[k], heap[j]))
 210                         {
 211                                 j = k;
 212                         }
 213                         while (j <= size && LessThan(heap[j], node))
 214                         {
 215                                 heap[i] = heap[j];                        // shift up child
 216                                 i = j;
 217                                 j = i << 1;
 218                                 k = j + 1;
 219                                 if (k <= size && LessThan(heap[k], heap[j]))
 220                                 {
 221                                         j = k;
 222                                 }
 223                         }
 224                         heap[i] = node;                           // install saved node
 225                 }
 226         }
 227 }