xapian-core/common/heap.h

   1 /** @file heap.h
   2  * @brief C++ STL heap implementation with extensions
   3  *
   4  * Adapted from libc++'s <algorithm>, with the following additions:
   5  *
   6  * * replace() - pop() followed by push(), but as efficient as just pop()
   7  *   (i.e. at most 2 * log(N) compares rather than at most 3 * log(N))
   8  * * siftdown() - sink adjusted entry to restore heap invariant
   9  *
  10  * Complexity:
  11  *
  12  * make() : At most 3*N comparisons
  13  * pop()/replace()/siftdown() : At most 2*log(N) comparisons
  14  * push() : At most log(N) comparisons (O(1) average)
  15  * sort() : At most 2*N*log(N) comparisons
  16  */
  17
  18 // This file is dual licensed under the MIT and the University of Illinois Open
  19 // Source Licenses:
  20 //
  21 // ==============================================================================
  22 // libc++ License
  23 // ==============================================================================
  24 //
  25 // The libc++ library is dual licensed under both the University of Illinois
  26 // "BSD-Like" license and the MIT license.  As a user of this code you may choose
  27 // to use it under either license.  As a contributor, you agree to allow your code
  28 // to be used under both.
  29 //
  30 // Full text of the relevant licenses is included below.
  31 //
  32 // ==============================================================================
  33 //
  34 // University of Illinois/NCSA
  35 // Open Source License
  36 //
  37 // Copyright (c) 2009-2016 by the contributors listed in CREDITS.TXT
  38 //
  39 // All rights reserved.
  40 //
  41 // Developed by:
  42 //
  43 //     LLVM Team
  44 //
  45 //     University of Illinois at Urbana-Champaign
  46 //
  47 //     http://llvm.org
  48 //
  49 // Permission is hereby granted, free of charge, to any person obtaining a copy of
  50 // this software and associated documentation files (the "Software"), to deal with
  51 // the Software without restriction, including without limitation the rights to
  52 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  53 // of the Software, and to permit persons to whom the Software is furnished to do
  54 // so, subject to the following conditions:
  55 //
  56 //     * Redistributions of source code must retain the above copyright notice,
  57 //       this list of conditions and the following disclaimers.
  58 //
  59 //     * Redistributions in binary form must reproduce the above copyright notice,
  60 //       this list of conditions and the following disclaimers in the
  61 //       documentation and/or other materials provided with the distribution.
  62 //
  63 //     * Neither the names of the LLVM Team, University of Illinois at
  64 //       Urbana-Champaign, nor the names of its contributors may be used to
  65 //       endorse or promote products derived from this Software without specific
  66 //       prior written permission.
  67 //
  68 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  69 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  70 // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  71 // CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  72 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  73 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
  74 // SOFTWARE.
  75 //
  76 // ==============================================================================
  77 //
  78 // Copyright (c) 2009-2014 by the contributors listed in CREDITS.TXT
  79 //
  80 // Permission is hereby granted, free of charge, to any person obtaining a copy
  81 // of this software and associated documentation files (the "Software"), to deal
  82 // in the Software without restriction, including without limitation the rights
  83 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  84 // copies of the Software, and to permit persons to whom the Software is
  85 // furnished to do so, subject to the following conditions:
  86 //
  87 // The above copyright notice and this permission notice shall be included in
  88 // all copies or substantial portions of the Software.
  89 //
  90 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  91 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  92 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  93 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  94 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  95 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  96 // THE SOFTWARE.
  97
  98 #ifndef XAPIAN_INCLUDED_HEAP_H
  99 #define XAPIAN_INCLUDED_HEAP_H
 100
 101 namespace Heap {
 102
 103 // push_heap
 104
 105 template <class _Compare, class _RandomAccessIterator>
 106 void
 107 sift_up_(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp,
 108           typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
 109 {
 110     typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
 111     if (len > 1)
 112     {
 113         len = (len - 2) / 2;
 114         _RandomAccessIterator ptr = first + len;
 115         if (comp(*ptr, *--last))
 116         {
 117             value_type t(std::move(*last));
 118             do
 119             {
 120                 *last = std::move(*ptr);
 121                 last = ptr;
 122                 if (len == 0)
 123                     break;
 124                 len = (len - 1) / 2;
 125                 ptr = first + len;
 126             } while (comp(*ptr, t));
 127             *last = std::move(t);
 128         }
 129     }
 130 }
 131
 132 template <class _RandomAccessIterator, class _Compare>
 133 inline
 134 void
 135 push(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
 136 {
 137     sift_up_(first, last, comp, last - first);
 138 }
 139
 140 // pop_heap
 141
 142 template <class _Compare, class _RandomAccessIterator>
 143 void
 144 sift_down_(_RandomAccessIterator first, _Compare comp,
 145             typename std::iterator_traits<_RandomAccessIterator>::difference_type len,
 146             _RandomAccessIterator start)
 147 {
 148     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 149     typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
 150     // left-child of start is at 2 * start + 1
 151     // right-child of start is at 2 * start + 2
 152     difference_type child = start - first;
 153
 154     if (len < 2 || (len - 2) / 2 < child)
 155         return;
 156
 157     child = 2 * child + 1;
 158     _RandomAccessIterator child_i = first + child;
 159
 160     if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
 161         // right-child exists and is greater than left-child
 162         ++child_i;
 163         ++child;
 164     }
 165
 166     // check if we are in heap-order
 167     if (comp(*child_i, *start))
 168         // we are, start is larger than it's largest child
 169         return;
 170
 171     value_type top(std::move(*start));
 172     do
 173     {
 174         // we are not in heap-order, swap the parent with it's largest child
 175         *start = std::move(*child_i);
 176         start = child_i;
 177
 178         if ((len - 2) / 2 < child)
 179             break;
 180
 181         // recompute the child based off of the updated parent
 182         child = 2 * child + 1;
 183         child_i = first + child;
 184
 185         if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
 186             // right-child exists and is greater than left-child
 187             ++child_i;
 188             ++child;
 189         }
 190
 191         // check if we are in heap-order
 192     } while (!comp(*child_i, top));
 193     *start = std::move(top);
 194 }
 195
 196 template <class _Compare, class _RandomAccessIterator>
 197 inline
 198 void
 199 pop_heap_(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp,
 200            typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
 201 {
 202     if (len > 1)
 203     {
 204         using std::swap;
 205         swap(*first, *--last);
 206         sift_down_(first, comp, len - 1, first);
 207     }
 208 }
 209
 210 template <class _RandomAccessIterator, class _Compare>
 211 inline
 212 void
 213 pop(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
 214 {
 215     pop_heap_(first, last, comp, last - first);
 216 }
 217
 218 template <class _Compare, class _RandomAccessIterator>
 219 inline
 220 void
 221 replace_heap_(_RandomAccessIterator first, _Compare comp,
 222               typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
 223 {
 224     sift_down_(first, comp, len, first);
 225 }
 226
 227 // Replace the tip of the heap then call replace() to restore the invariant.
 228 template <class _RandomAccessIterator, class _Compare>
 229 inline void
 230 replace(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
 231 {
 232     replace_heap_(first, comp, last - first);
 233 }
 234
 235 template <class _Compare, class _RandomAccessIterator>
 236 inline void
 237 siftdown_heap_(_RandomAccessIterator first,
 238                _RandomAccessIterator elt, _Compare comp,
 239                typename std::iterator_traits<_RandomAccessIterator>::difference_type len)
 240 {
 241     sift_down_(first, comp, len, elt);
 242 }
 243
 244 // Replace an element with a "worse" one (in _Compare terms) and call siftdown_heap()
 245 // to restore the invariant.
 246 template <class _RandomAccessIterator, class _Compare>
 247 inline
 248 void
 249 siftdown(_RandomAccessIterator first, _RandomAccessIterator last,
 250          _RandomAccessIterator elt, _Compare comp)
 251 {
 252     siftdown_heap_(first, elt, comp, last - first);
 253 }
 254
 255 // make_heap
 256
 257 template <class _RandomAccessIterator, class _Compare>
 258 void
 259 make(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
 260 {
 261     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 262     difference_type n = last - first;
 263     if (n > 1)
 264     {
 265         // start from the first parent, there is no need to consider children
 266         for (difference_type start = (n - 2) / 2; start >= 0; --start)
 267         {
 268             sift_down_(first, comp, n, first + start);
 269         }
 270     }
 271 }
 272
 273 // sort_heap
 274
 275 template <class _Compare, class _RandomAccessIterator>
 276 void
 277 sort(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
 278 {
 279     typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 280     for (difference_type n = last - first; n > 1; --last, --n)
 281         pop_heap_<_Compare>(first, last, comp, n);
 282 }
 283
 284 }
 285
 286 #endif