mcs/class/referencesource/System.Core/System/Linq/Parallel/Utils/FixedMaxHeap.cs

   1 // ==++==
   2 //
   3 //   Copyright (c) Microsoft Corporation.  All rights reserved.
   4 //
   5 // ==--==
   6 // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
   7 //
   8 // FixedMaxHeap.cs
   9 //
  10 // <OWNER>[....]</OWNER>
  11 //
  12 // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  13
  14 using System.Collections.Generic;
  15 using System.Diagnostics.Contracts;
  16 #if SILVERLIGHT
  17 using System.Core; // for System.Core.SR
  18 #endif
  19
  20 namespace System.Linq.Parallel
  21 {
  22     /// <summary>
  23     /// Very simple heap data structure, of fixed size.
  24     /// </summary>
  25     /// <typeparam name="TElement"></typeparam>
  26     internal class FixedMaxHeap<TElement>
  27     {
  28
  29         private TElement[] m_elements; // Element array.
  30         private int m_count; // Current count.
  31         private IComparer<TElement> m_comparer; // Element comparison routine.
  32
  33         //-----------------------------------------------------------------------------------
  34         // Create a new heap with the specified maximum size.
  35         //
  36
  37         internal FixedMaxHeap(int maximumSize)
  38             : this(maximumSize, Util.GetDefaultComparer<TElement>())
  39         {
  40         }
  41
  42         internal FixedMaxHeap(int maximumSize, IComparer<TElement> comparer)
  43         {
  44             Contract.Assert(comparer != null);
  45
  46             m_elements = new TElement[maximumSize];
  47             m_comparer = comparer;
  48         }
  49
  50         //-----------------------------------------------------------------------------------
  51         // Retrieve the count (i.e. how many elements are in the heap).
  52         //
  53
  54         internal int Count
  55         {
  56             get { return m_count; }
  57         }
  58
  59         //-----------------------------------------------------------------------------------
  60         // Retrieve the size (i.e. the maximum size of the heap).
  61         //
  62
  63         internal int Size
  64         {
  65             get { return m_elements.Length; }
  66         }
  67
  68         //-----------------------------------------------------------------------------------
  69         // Get the current maximum value in the max-heap.
  70         //
  71         // Note: The heap stores the maximumSize smallest elements that were inserted.
  72         // So, if the heap is full, the value returned is the maximumSize-th smallest
  73         // element that was inserted into the heap.
  74         //
  75
  76         internal TElement MaxValue
  77         {
  78             get
  79             {
  80                 if (m_count == 0)
  81                 {
  82                     throw new InvalidOperationException(SR.GetString(SR.NoElements));
  83                 }
  84
  85                 // The maximum element is in the 0th position.
  86                 return m_elements[0];
  87             }
  88         }
  89
  90
  91         //-----------------------------------------------------------------------------------
  92         // Removes all elements from the heap.
  93         //
  94
  95         internal void Clear()
  96         {
  97             m_count = 0;
  98         }
  99
 100         //-----------------------------------------------------------------------------------
 101         // Inserts the new element, maintaining the heap property.
 102         //
 103         // Return Value:
 104         //     If the element is greater than the current max element, this function returns
 105         //     false without modifying the heap. Otherwise, it returns true.
 106         //
 107
 108         internal bool Insert(TElement e)
 109         {
 110             if (m_count < m_elements.Length)
 111             {
 112                 // There is room. We can add it and then max-heapify.
 113                 m_elements[m_count] = e;
 114                 m_count++;
 115                 HeapifyLastLeaf();
 116                 return true;
 117             }
 118             else
 119             {
 120                 // No more room. The element might not even fit in the heap. The check
 121                 // is simple: if it's greater than the maximum element, then it can't be
 122                 // inserted. Otherwise, we replace the head with it and reheapify.
 123                 if (m_comparer.Compare(e, m_elements[0]) < 0)
 124                 {
 125                     m_elements[0] = e;
 126                     HeapifyRoot();
 127                     return true;
 128                 }
 129
 130                 return false;
 131             }
 132         }
 133
 134         //-----------------------------------------------------------------------------------
 135         // Replaces the maximum value in the heap with the user-provided value, and restores
 136         // the heap property.
 137         //
 138
 139         internal void ReplaceMax(TElement newValue)
 140         {
 141             Contract.Assert(m_count > 0);
 142             m_elements[0] = newValue;
 143             HeapifyRoot();
 144         }
 145
 146         //-----------------------------------------------------------------------------------
 147         // Removes the maximum value from the heap, and restores the heap property.
 148         //
 149
 150         internal void RemoveMax()
 151         {
 152             Contract.Assert(m_count > 0);
 153             m_count--;
 154
 155             if (m_count > 0)
 156             {
 157                 m_elements[0] = m_elements[m_count];
 158                 HeapifyRoot();
 159             }
 160         }
 161
 162         //-----------------------------------------------------------------------------------
 163         // Private helpers to swap elements, and to reheapify starting from the root or
 164         // from a leaf element, depending on what is needed.
 165         //
 166
 167         private void Swap(int i, int j)
 168         {
 169             TElement tmpElement = m_elements[i];
 170             m_elements[i] = m_elements[j];
 171             m_elements[j] = tmpElement;
 172         }
 173
 174         private void HeapifyRoot()
 175         {
 176             // We are heapifying from the head of the list.
 177             int i = 0;
 178             int n = m_count;
 179
 180             while (i < n)
 181             {
 182                 // Calculate the current child node indexes.
 183                 int n0 = ((i + 1) * 2) - 1;
 184                 int n1 = n0 + 1;
 185
 186                 if (n0 < n && m_comparer.Compare(m_elements[i], m_elements[n0]) < 0)
 187                 {
 188                     // We have to select the bigger of the two subtrees, and float
 189                     // the current element down. This maintains the max-heap property.
 190                     if (n1 < n && m_comparer.Compare(m_elements[n0], m_elements[n1]) < 0)
 191                     {
 192                         Swap(i, n1);
 193                         i = n1;
 194                     }
 195                     else
 196                     {
 197                         Swap(i, n0);
 198                         i = n0;
 199                     }
 200                 }
 201                 else if (n1 < n && m_comparer.Compare(m_elements[i], m_elements[n1]) < 0)
 202                 {
 203                     // Float down the "right" subtree. We needn't compare this subtree
 204                     // to the "left", because if the element was smaller than that, the
 205                     // first if statement's predicate would have evaluated to true.
 206                     Swap(i, n1);
 207                     i = n1;
 208                 }
 209                 else
 210                 {
 211                     // Else, the current key is in its final position. Break out
 212                     // of the current loop and return.
 213                     break;
 214                 }
 215             }
 216         }
 217
 218         private void HeapifyLastLeaf()
 219         {
 220             int i = m_count - 1;
 221             while (i > 0)
 222             {
 223                 int j = ((i + 1) / 2) - 1;
 224
 225                 if (m_comparer.Compare(m_elements[i], m_elements[j]) > 0)
 226                 {
 227                     Swap(i, j);
 228                     i = j;
 229                 }
 230                 else
 231                 {
 232                     break;
 233                 }
 234             }
 235         }
 236     }
 237 }