PriorityQueue.cs

Go to the documentation of this file.

/* 
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using Lucene.Net.Support;

namespace Lucene.Net.Util
{
    
    // TODO: T needs to be able to return null.  Behavior might be unexpected otherwise, since it returns default(T)
    //       I only see a non-nullable type used in PriorityQueue in the tests.  may be possible to re-write tests to
    //       use an IComparable class, and this can be changed back to constraining on class, to return null, or should
    //       we leave as is?
    public abstract class PriorityQueue<T> //where T : class
    {
        private int size;
        private int maxSize;
        protected internal T[] heap;
        
        public abstract bool LessThan(T a, T b);

        protected internal virtual T SentinelObject
        {
            get { return default(T); }
        }

        protected internal void  Initialize(int maxSize)
        {
            size = 0;
            int heapSize;
            if (0 == maxSize)
                // We allocate 1 extra to avoid if statement in top()
                heapSize = 2;
            else
            {
                if (maxSize == Int32.MaxValue)
                {
                    // Don't wrap heapSize to -1, in this case, which
                    // causes a confusing NegativeArraySizeException.
                    // Note that very likely this will simply then hit
                    // an OOME, but at least that's more indicative to
                    // caller that this values is too big.  We don't +1
                    // in this case, but it's very unlikely in practice
                    // one will actually insert this many objects into
                    // the PQ:
                    heapSize = Int32.MaxValue;
                }
                else
                {
                    // NOTE: we add +1 because all access to heap is
                    // 1-based not 0-based.  heap[0] is unused.
                    heapSize = maxSize + 1;
                }
            }
            heap = new T[heapSize];
            this.maxSize = maxSize;
            
            // If sentinel objects are supported, populate the queue with them
            T sentinel = SentinelObject;
            if (sentinel != null)
            {
                heap[1] = sentinel;
                for (int i = 2; i < heap.Length; i++)
                {
                    heap[i] = SentinelObject;
                }
                size = maxSize;
            }
        }
        
        public T Add(T element)
        {
            size++;
            heap[size] = element;
            UpHeap();
            return heap[1];
        }

        public virtual T InsertWithOverflow(T element)
        {
            if (size < maxSize)
            {
                Add(element);
                return default(T);
            }
            else if (size > 0 && !LessThan(element, heap[1]))
            {
                T ret = heap[1];
                heap[1] = element;
                UpdateTop();
                return ret;
            }
            else
            {
                return element;
            }
        }
        
        public T Top()
        {
            // We don't need to check size here: if maxSize is 0,
            // then heap is length 2 array with both entries null.
            // If size is 0 then heap[1] is already null.
            return heap[1];
        }
        
        public T Pop()
        {
            if (size > 0)
            {
                T result = heap[1]; // save first value
                heap[1] = heap[size]; // move last to first
                heap[size] = default(T); // permit GC of objects
                size--;
                DownHeap(); // adjust heap
                return result;
            }
            else
                return default(T);
        }
        
        public T UpdateTop()
        {
            DownHeap();
            return heap[1];
        }
        
        public int Size()
        {
            return size;
        }
        
        public void  Clear()
        {
            for (int i = 0; i <= size; i++)
            {
                heap[i] = default(T);
            }
            size = 0;
        }
        
        private void  UpHeap()
        {
            int i = size;
            T node = heap[i]; // save bottom node
            int j = Number.URShift(i, 1);
            while (j > 0 && LessThan(node, heap[j]))
            {
                heap[i] = heap[j]; // shift parents down
                i = j;
                j = Number.URShift(j, 1);
            }
            heap[i] = node; // install saved node
        }
        
        private void  DownHeap()
        {
            int i = 1;
            T node = heap[i]; // save top node
            int j = i << 1; // find smaller child
            int k = j + 1;
            if (k <= size && LessThan(heap[k], heap[j]))
            {
                j = k;
            }
            while (j <= size && LessThan(heap[j], node))
            {
                heap[i] = heap[j]; // shift up child
                i = j;
                j = i << 1;
                k = j + 1;
                if (k <= size && LessThan(heap[k], heap[j]))
                {
                    j = k;
                }
            }
            heap[i] = node; // install saved node
        }
    }
}