libstdc++-v3/include/parallel/losertree.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/losertree.h
  32 *  @brief Many generic loser tree variants.
  33 *  This file is a GNU parallel extension to the Standard C++ Library.
  34 */
  35
  36 // Written by Johannes Singler.
  37
  38 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
  39 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
  40
  41 #include <functional>
  42
  43 #include <bits/stl_algobase.h>
  44 #include <parallel/features.h>
  45 #include <parallel/base.h>
  46
  47 namespace __gnu_parallel
  48 {
  49
  50 #if _GLIBCXX_LOSER_TREE_EXPLICIT
  51
  52 /** @brief Guarded loser tree, copying the whole element into the
  53 * tree structure.
  54 *
  55 *  Guarding is done explicitly through two flags per element, inf
  56 *  and sup This is a quite slow variant.
  57 */
  58 template<typename T, typename Comparator = std::less<T> >
  59   class LoserTreeExplicit
  60   {
  61   private:
  62     struct Loser
  63     {
  64       // The relevant element.
  65       T key;
  66
  67       // Is this an infimum or supremum element?
  68       bool inf, sup;
  69
  70       // Number of the sequence the element comes from.
  71       int source;
  72     };
  73
  74     unsigned int size, offset;
  75     Loser* losers;
  76     Comparator comp;
  77
  78   public:
  79     inline
  80     LoserTreeExplicit(unsigned int _size, Comparator _comp = std::less<T>())
  81       : comp(_comp)
  82     {
  83       size = _size;
  84       offset = size;
  85       losers = new Loser[size];
  86       for (unsigned int l = 0; l < size; l++)
  87         {
  88           //losers[l].key = ...         stays unset
  89           losers[l].inf = true;
  90           losers[l].sup = false;
  91           //losers[l].source = -1;      //sentinel
  92         }
  93     }
  94
  95     inline ~LoserTreeExplicit()
  96     { delete[] losers; }
  97
  98     inline int
  99     get_min_source()
 100     { return losers[0].source; }
 101
 102     inline void
 103     insert_start(T key, int source, bool sup)
 104     {
 105       bool inf = false;
 106       for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
 107         {
 108           if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
 109                && comp(losers[pos].key, key)) || losers[pos].inf || sup)
 110             {
 111               // The other one is smaller.
 112               std::swap(losers[pos].key, key);
 113               std::swap(losers[pos].inf, inf);
 114               std::swap(losers[pos].sup, sup);
 115               std::swap(losers[pos].source, source);
 116             }
 117         }
 118
 119       losers[0].key = key;
 120       losers[0].inf = inf;
 121       losers[0].sup = sup;
 122       losers[0].source = source;
 123     }
 124
 125     inline void
 126     init() { }
 127
 128     inline void
 129     delete_min_insert(T key, bool sup)
 130     {
 131       bool inf = false;
 132       int source = losers[0].source;
 133       for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
 134         {
 135           // The smaller one gets promoted.
 136           if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
 137               && comp(losers[pos].key, key))
 138               || losers[pos].inf || sup)
 139             {
 140               // The other one is smaller.
 141               std::swap(losers[pos].key, key);
 142               std::swap(losers[pos].inf, inf);
 143               std::swap(losers[pos].sup, sup);
 144               std::swap(losers[pos].source, source);
 145             }
 146         }
 147
 148       losers[0].key = key;
 149       losers[0].inf = inf;
 150       losers[0].sup = sup;
 151       losers[0].source = source;
 152     }
 153
 154     inline void
 155     insert_start_stable(T key, int source, bool sup)
 156     {
 157       bool inf = false;
 158       for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
 159         {
 160           if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup &&
 161               ((comp(losers[pos].key, key)) ||
 162                 (!comp(key, losers[pos].key) && losers[pos].source < source)))
 163               || losers[pos].inf || sup)
 164             {
 165               // Take next key.
 166               std::swap(losers[pos].key, key);
 167               std::swap(losers[pos].inf, inf);
 168               std::swap(losers[pos].sup, sup);
 169               std::swap(losers[pos].source, source);
 170             }
 171         }
 172
 173       losers[0].key = key;
 174       losers[0].inf = inf;
 175       losers[0].sup = sup;
 176       losers[0].source = source;
 177     }
 178
 179     inline void
 180     init_stable() { }
 181
 182     inline void
 183     delete_min_insert_stable(T key, bool sup)
 184     {
 185       bool inf = false;
 186       int source = losers[0].source;
 187       for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
 188         {
 189           if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
 190               && ((comp(losers[pos].key, key)) ||
 191                 (!comp(key, losers[pos].key) && losers[pos].source < source)))
 192               || losers[pos].inf || sup)
 193             {
 194               std::swap(losers[pos].key, key);
 195               std::swap(losers[pos].inf, inf);
 196               std::swap(losers[pos].sup, sup);
 197               std::swap(losers[pos].source, source);
 198             }
 199         }
 200
 201       losers[0].key = key;
 202       losers[0].inf = inf;
 203       losers[0].sup = sup;
 204       losers[0].source = source;
 205     }
 206   };
 207
 208 #endif
 209
 210 #if _GLIBCXX_LOSER_TREE
 211
 212 /** @brief Guarded loser tree, either copying the whole element into
 213 * the tree structure, or looking up the element via the index.
 214 *
 215 *  Guarding is done explicitly through one flag sup per element,
 216 *  inf is not needed due to a better initialization routine.  This
 217 *  is a well-performing variant.
 218 */
 219 template<typename T, typename Comparator = std::less<T> >
 220   class LoserTree
 221   {
 222   private:
 223     struct Loser
 224     {
 225       bool sup;
 226       int source;
 227       T key;
 228     };
 229
 230     unsigned int ik, k, offset;
 231     Loser* losers;
 232     Comparator comp;
 233     bool first_insert;
 234
 235   public:
 236     inline LoserTree(unsigned int _k, Comparator _comp = std::less<T>())
 237     : comp(_comp)
 238     {
 239       ik = _k;
 240
 241       // Next greater power of 2.
 242       k = 1 << (log2(ik - 1) + 1);
 243       offset = k;
 244       // Avoid default-constructing losers[].key
 245       losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
 246       for (unsigned int i = ik - 1; i < k; ++i)
 247         losers[i + k].sup = true;
 248
 249       first_insert = true;
 250     }
 251
 252     inline ~LoserTree()
 253     { delete[] losers; }
 254
 255     inline int
 256     get_min_source()
 257     { return losers[0].source; }
 258
 259     inline void
 260     insert_start(const T& key, int source, bool sup)
 261     {
 262       unsigned int pos = k + source;
 263
 264       if(first_insert)
 265         {
 266           // Construct all keys, so we can easily deconstruct them.
 267           for (unsigned int i = 0; i < (2 * k); ++i)
 268             new(&(losers[i].key)) T(key);
 269           first_insert = false;
 270         }
 271       else
 272         new(&(losers[pos].key)) T(key);
 273
 274       losers[pos].sup = sup;
 275       losers[pos].source = source;
 276     }
 277
 278     unsigned int
 279     init_winner (unsigned int root)
 280     {
 281       if (root >= k)
 282         {
 283           return root;
 284         }
 285       else
 286         {
 287           unsigned int left = init_winner (2 * root);
 288           unsigned int right = init_winner (2 * root + 1);
 289           if (losers[right].sup ||
 290               (!losers[left].sup
 291                 && !comp(losers[right].key, losers[left].key)))
 292             {
 293               // Left one is less or equal.
 294               losers[root] = losers[right];
 295               return left;
 296             }
 297           else
 298             {
 299               // Right one is less.
 300               losers[root] = losers[left];
 301               return right;
 302             }
 303         }
 304     }
 305
 306     inline void
 307     init()
 308     { losers[0] = losers[init_winner(1)]; }
 309
 310     // Do not pass const reference since key will be used as local variable.
 311     inline void
 312     delete_min_insert(T key, bool sup)
 313     {
 314       int source = losers[0].source;
 315       for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
 316         {
 317           // The smaller one gets promoted.
 318           if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
 319             {
 320               // The other one is smaller.
 321               std::swap(losers[pos].sup, sup);
 322               std::swap(losers[pos].source, source);
 323               std::swap(losers[pos].key, key);
 324             }
 325         }
 326
 327       losers[0].sup = sup;
 328       losers[0].source = source;
 329       losers[0].key = key;
 330     }
 331
 332     inline void
 333     insert_start_stable(const T& key, int source, bool sup)
 334     { return insert_start(key, source, sup); }
 335
 336     unsigned int
 337     init_winner_stable (unsigned int root)
 338     {
 339       if (root >= k)
 340         {
 341           return root;
 342         }
 343       else
 344         {
 345           unsigned int left = init_winner (2 * root);
 346           unsigned int right = init_winner (2 * root + 1);
 347           if (losers[right].sup
 348               || (!losers[left].sup
 349                 && !comp(losers[right].key, losers[left].key)))
 350             {
 351               // Left one is less or equal.
 352               losers[root] = losers[right];
 353               return left;
 354             }
 355           else
 356             {
 357               // Right one is less.
 358               losers[root] = losers[left];
 359               return right;
 360             }
 361         }
 362     }
 363
 364     inline void
 365     init_stable()
 366     { losers[0] = losers[init_winner_stable(1)]; }
 367
 368     // Do not pass const reference since key will be used as local variable.
 369     inline void
 370     delete_min_insert_stable(T key, bool sup)
 371     {
 372       int source = losers[0].source;
 373       for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
 374         {
 375           // The smaller one gets promoted, ties are broken by source.
 376           if (  (sup && (!losers[pos].sup || losers[pos].source < source))
 377                 || (!sup && !losers[pos].sup
 378                   && ((comp(losers[pos].key, key))
 379                     || (!comp(key, losers[pos].key)
 380                       && losers[pos].source < source))))
 381             {
 382               // The other one is smaller.
 383               std::swap(losers[pos].sup, sup);
 384               std::swap(losers[pos].source, source);
 385               std::swap(losers[pos].key, key);
 386             }
 387         }
 388
 389       losers[0].sup = sup;
 390       losers[0].source = source;
 391       losers[0].key = key;
 392     }
 393   };
 394
 395 #endif
 396
 397 #if _GLIBCXX_LOSER_TREE_REFERENCE
 398
 399 /** @brief Guarded loser tree, either copying the whole element into
 400 * the tree structure, or looking up the element via the index.
 401 *
 402 *  Guarding is done explicitly through one flag sup per element,
 403 *  inf is not needed due to a better initialization routine.  This
 404 *  is a well-performing variant.
 405 */
 406 template<typename T, typename Comparator = std::less<T> >
 407   class LoserTreeReference
 408   {
 409 #undef COPY
 410 #ifdef COPY
 411 #define KEY(i) losers[i].key
 412 #define KEY_SOURCE(i) key
 413 #else
 414 #define KEY(i) keys[losers[i].source]
 415 #define KEY_SOURCE(i) keys[i]
 416 #endif
 417   private:
 418     struct Loser
 419     {
 420       bool sup;
 421       int source;
 422 #ifdef COPY
 423       T key;
 424 #endif
 425     };
 426
 427     unsigned int ik, k, offset;
 428     Loser* losers;
 429 #ifndef COPY
 430     T* keys;
 431 #endif
 432     Comparator comp;
 433
 434   public:
 435     inline
 436     LoserTreeReference(unsigned int _k, Comparator _comp = std::less<T>())
 437       : comp(_comp)
 438     {
 439       ik = _k;
 440
 441       // Next greater power of 2.
 442       k = 1 << (log2(ik - 1) + 1);
 443       offset = k;
 444       losers = new Loser[k * 2];
 445 #ifndef COPY
 446       keys = new T[ik];
 447 #endif
 448       for (unsigned int i = ik - 1; i < k; i++)
 449         losers[i + k].sup = true;
 450     }
 451
 452     inline ~LoserTreeReference()
 453     {
 454       delete[] losers;
 455 #ifndef COPY
 456       delete[] keys;
 457 #endif
 458     }
 459
 460     inline int
 461     get_min_source()
 462     { return losers[0].source; }
 463
 464     inline void
 465     insert_start(T key, int source, bool sup)
 466     {
 467       unsigned int pos = k + source;
 468
 469       losers[pos].sup = sup;
 470       losers[pos].source = source;
 471       KEY(pos) = key;
 472     }
 473
 474     unsigned int
 475     init_winner(unsigned int root)
 476     {
 477       if (root >= k)
 478         {
 479           return root;
 480         }
 481       else
 482         {
 483           unsigned int left = init_winner (2 * root);
 484           unsigned int right = init_winner (2 * root + 1);
 485           if (  losers[right].sup ||
 486                 (!losers[left].sup && !comp(KEY(right), KEY(left))))
 487             {
 488               // Left one is less or equal.
 489               losers[root] = losers[right];
 490               return left;
 491             }
 492           else
 493             {
 494               // Right one is less.
 495               losers[root] = losers[left];
 496               return right;
 497             }
 498         }
 499     }
 500
 501     inline void
 502     init()
 503     {
 504       losers[0] = losers[init_winner(1)];
 505     }
 506
 507     inline void
 508     delete_min_insert(T key, bool sup)
 509     {
 510       int source = losers[0].source;
 511       for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
 512         {
 513           // The smaller one gets promoted.
 514           if (sup || (!losers[pos].sup && comp(KEY(pos), KEY_SOURCE(source))))
 515             {
 516               // The other one is smaller.
 517               std::swap(losers[pos].sup, sup);
 518               std::swap(losers[pos].source, source);
 519 #ifdef COPY
 520               std::swap(KEY(pos), KEY_SOURCE(source));
 521 #endif
 522             }
 523         }
 524
 525       losers[0].sup = sup;
 526       losers[0].source = source;
 527 #ifdef COPY
 528       KEY(0) = KEY_SOURCE(source);
 529 #endif
 530     }
 531
 532     inline void
 533     insert_start_stable(T key, int source, bool sup)
 534     { return insert_start(key, source, sup); }
 535
 536     unsigned int
 537     init_winner_stable(unsigned int root)
 538     {
 539       if (root >= k)
 540         {
 541           return root;
 542         }
 543       else
 544         {
 545           unsigned int left = init_winner (2 * root);
 546           unsigned int right = init_winner (2 * root + 1);
 547           if (losers[right].sup
 548               || (!losers[left].sup && !comp(KEY(right), KEY(left))))
 549             {
 550               // Left one is less or equal.
 551               losers[root] = losers[right];
 552               return left;
 553             }
 554           else
 555             {
 556               // Right one is less.
 557               losers[root] = losers[left];
 558               return right;
 559             }
 560         }
 561     }
 562
 563     inline void
 564     init_stable()
 565     { losers[0] = losers[init_winner_stable(1)]; }
 566
 567     inline void
 568     delete_min_insert_stable(T key, bool sup)
 569     {
 570       int source = losers[0].source;
 571       for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
 572         {
 573           // The smaller one gets promoted, ties are broken by source.
 574           if (  (sup && (!losers[pos].sup || losers[pos].source < source)) ||
 575                 (!sup && !losers[pos].sup &&
 576                 ((comp(KEY(pos), KEY_SOURCE(source))) ||
 577                   (!comp(KEY_SOURCE(source), KEY(pos))
 578                     && losers[pos].source < source))))
 579             {
 580               // The other one is smaller.
 581               std::swap(losers[pos].sup, sup);
 582               std::swap(losers[pos].source, source);
 583 #ifdef COPY
 584               std::swap(KEY(pos), KEY_SOURCE(source));
 585 #endif
 586             }
 587         }
 588
 589       losers[0].sup = sup;
 590       losers[0].source = source;
 591 #ifdef COPY
 592       KEY(0) = KEY_SOURCE(source);
 593 #endif
 594     }
 595   };
 596 #undef KEY
 597 #undef KEY_SOURCE
 598
 599 #endif
 600
 601 #if _GLIBCXX_LOSER_TREE_POINTER
 602
 603 /** @brief Guarded loser tree, either copying the whole element into
 604     the tree structure, or looking up the element via the index.
 605 *  Guarding is done explicitly through one flag sup per element,
 606 *  inf is not needed due to a better initialization routine.
 607 *  This is a well-performing variant.
 608 */
 609 template<typename T, typename Comparator = std::less<T> >
 610   class LoserTreePointer
 611   {
 612   private:
 613     struct Loser
 614     {
 615       bool sup;
 616       int source;
 617       const T* keyp;
 618     };
 619
 620     unsigned int ik, k, offset;
 621     Loser* losers;
 622     Comparator comp;
 623
 624   public:
 625     inline
 626     LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
 627       : comp(_comp)
 628     {
 629       ik = _k;
 630
 631       // Next greater power of 2.
 632       k = 1 << (log2(ik - 1) + 1);
 633       offset = k;
 634       losers = new Loser[k * 2];
 635       for (unsigned int i = ik - 1; i < k; i++)
 636         losers[i + k].sup = true;
 637     }
 638
 639     inline ~LoserTreePointer()
 640     { delete[] losers; }
 641
 642     inline int
 643     get_min_source()
 644     { return losers[0].source; }
 645
 646     inline void
 647     insert_start(const T& key, int source, bool sup)
 648     {
 649       unsigned int pos = k + source;
 650
 651       losers[pos].sup = sup;
 652       losers[pos].source = source;
 653       losers[pos].keyp = &key;
 654     }
 655
 656     unsigned int
 657     init_winner(unsigned int root)
 658     {
 659       if (root >= k)
 660         {
 661           return root;
 662         }
 663       else
 664         {
 665           unsigned int left = init_winner (2 * root);
 666           unsigned int right = init_winner (2 * root + 1);
 667           if (losers[right].sup
 668                 || (!losers[left].sup
 669                   && !comp(*losers[right].keyp, *losers[left].keyp)))
 670             {
 671               // Left one is less or equal.
 672               losers[root] = losers[right];
 673               return left;
 674             }
 675           else
 676             {
 677               // Right one is less.
 678               losers[root] = losers[left];
 679               return right;
 680             }
 681         }
 682     }
 683
 684     inline void
 685     init()
 686     { losers[0] = losers[init_winner(1)]; }
 687
 688     inline void
 689     delete_min_insert(const T& key, bool sup)
 690     {
 691       const T* keyp = &key;
 692       int source = losers[0].source;
 693       for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
 694         {
 695           // The smaller one gets promoted.
 696           if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
 697             {
 698               // The other one is smaller.
 699               std::swap(losers[pos].sup, sup);
 700               std::swap(losers[pos].source, source);
 701               std::swap(losers[pos].keyp, keyp);
 702             }
 703         }
 704
 705       losers[0].sup = sup;
 706       losers[0].source = source;
 707       losers[0].keyp = keyp;
 708     }
 709
 710     inline void
 711     insert_start_stable(const T& key, int source, bool sup)
 712     { return insert_start(key, source, sup); }
 713
 714     unsigned int
 715     init_winner_stable(unsigned int root)
 716     {
 717       if (root >= k)
 718         {
 719           return root;
 720         }
 721       else
 722         {
 723           unsigned int left = init_winner (2 * root);
 724           unsigned int right = init_winner (2 * root + 1);
 725           if (losers[right].sup
 726               || (!losers[left].sup && !comp(*losers[right].keyp,
 727                                             *losers[left].keyp)))
 728             {
 729               // Left one is less or equal.
 730               losers[root] = losers[right];
 731               return left;
 732             }
 733           else
 734             {
 735               // Right one is less.
 736               losers[root] = losers[left];
 737               return right;
 738             }
 739         }
 740     }
 741
 742     inline void
 743     init_stable()
 744     { losers[0] = losers[init_winner_stable(1)]; }
 745
 746     inline void
 747     delete_min_insert_stable(const T& key, bool sup)
 748     {
 749       const T* keyp = &key;
 750       int source = losers[0].source;
 751       for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
 752         {
 753           // The smaller one gets promoted, ties are broken by source.
 754           if (  (sup && (!losers[pos].sup || losers[pos].source < source)) ||
 755                 (!sup && !losers[pos].sup &&
 756                 ((comp(*losers[pos].keyp, *keyp)) ||
 757                   (!comp(*keyp, *losers[pos].keyp)
 758                   && losers[pos].source < source))))
 759             {
 760               // The other one is smaller.
 761               std::swap(losers[pos].sup, sup);
 762               std::swap(losers[pos].source, source);
 763               std::swap(losers[pos].keyp, keyp);
 764             }
 765         }
 766
 767       losers[0].sup = sup;
 768       losers[0].source = source;
 769       losers[0].keyp = keyp;
 770     }
 771   };
 772
 773 #endif
 774
 775 #if _GLIBCXX_LOSER_TREE_UNGUARDED
 776
 777 /** @brief Unguarded loser tree, copying the whole element into the
 778 * tree structure.
 779 *
 780 *  No guarding is done, therefore not a single input sequence must
 781 *  run empty.  This is a very fast variant.
 782 */
 783 template<typename T, typename Comparator = std::less<T> >
 784   class LoserTreeUnguarded
 785   {
 786   private:
 787     struct Loser
 788     {
 789       int source;
 790       T key;
 791     };
 792
 793     unsigned int ik, k, offset;
 794     unsigned int* mapping;
 795     Loser* losers;
 796     Comparator comp;
 797
 798     void
 799     map(unsigned int root, unsigned int begin, unsigned int end)
 800     {
 801       if (begin + 1 == end)
 802         mapping[begin] = root;
 803       else
 804         {
 805           // Next greater or equal power of 2.
 806           unsigned int left = 1 << (log2(end - begin - 1));
 807           map(root * 2, begin, begin + left);
 808           map(root * 2 + 1, begin + left, end);
 809         }
 810     }
 811
 812   public:
 813     inline
 814     LoserTreeUnguarded(unsigned int _k, Comparator _comp = std::less<T>())
 815       : comp(_comp)
 816     {
 817       ik = _k;
 818       // Next greater or equal power of 2.
 819       k = 1 << (log2(ik - 1) + 1);
 820       offset = k;
 821       losers = new Loser[k + ik];
 822       mapping = new unsigned int[ik];
 823       map(1, 0, ik);
 824     }
 825
 826     inline ~LoserTreeUnguarded()
 827     {
 828       delete[] losers;
 829       delete[] mapping;
 830     }
 831
 832     inline int
 833     get_min_source()
 834     { return losers[0].source; }
 835
 836     inline void
 837     insert_start(const T& key, int source, bool)
 838     {
 839       unsigned int pos = mapping[source];
 840       losers[pos].source = source;
 841       losers[pos].key = key;
 842     }
 843
 844     unsigned int
 845     init_winner(unsigned int root, unsigned int begin, unsigned int end)
 846     {
 847       if (begin + 1 == end)
 848         return mapping[begin];
 849       else
 850         {
 851           // Next greater or equal power of 2.
 852           unsigned int division = 1 << (log2(end - begin - 1));
 853           unsigned int left = init_winner(2 * root, begin, begin + division);
 854           unsigned int right =
 855                           init_winner(2 * root + 1, begin + division, end);
 856           if (!comp(losers[right].key, losers[left].key))
 857             {
 858               // Left one is less or equal.
 859               losers[root] = losers[right];
 860               return left;
 861             }
 862           else
 863             {
 864               // Right one is less.
 865               losers[root] = losers[left];
 866               return right;
 867             }
 868         }
 869     }
 870
 871     inline void
 872     init()
 873     { losers[0] = losers[init_winner(1, 0, ik)]; }
 874
 875     // Do not pass const reference since key will be used as local variable.
 876     inline void
 877     delete_min_insert(const T& key, bool)
 878     {
 879       losers[0].key = key;
 880       T& keyr = losers[0].key;
 881       int& source = losers[0].source;
 882       for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
 883         {
 884           // The smaller one gets promoted.
 885           if (comp(losers[pos].key, keyr))
 886             {
 887               // The other one is smaller.
 888               std::swap(losers[pos].source, source);
 889               std::swap(losers[pos].key, keyr);
 890             }
 891         }
 892     }
 893
 894     inline void
 895     insert_start_stable(const T& key, int source, bool)
 896     { return insert_start(key, source, false); }
 897
 898     inline void
 899     init_stable()
 900     { init(); }
 901
 902     inline void
 903     delete_min_insert_stable(const T& key, bool)
 904     {
 905       losers[0].key = key;
 906       T& keyr = losers[0].key;
 907       int& source = losers[0].source;
 908       for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
 909         {
 910           // The smaller one gets promoted, ties are broken by source.
 911           if (comp(losers[pos].key, keyr)
 912               || (!comp(keyr, losers[pos].key)
 913                 && losers[pos].source < source))
 914             {
 915               // The other one is smaller.
 916               std::swap(losers[pos].source, source);
 917               std::swap(losers[pos].key, keyr);
 918             }
 919         }
 920     }
 921   };
 922
 923 #endif
 924
 925 #if _GLIBCXX_LOSER_TREE_POINTER_UNGUARDED
 926
 927 /** @brief Unguarded loser tree, keeping only pointers to the
 928 * elements in the tree structure.
 929 *
 930 *  No guarding is done, therefore not a single input sequence must
 931 *  run empty.  This is a very fast variant.
 932 */
 933 template<typename T, typename Comparator = std::less<T> >
 934   class LoserTreePointerUnguarded
 935   {
 936   private:
 937     struct Loser
 938     {
 939       int source;
 940       const T* keyp;
 941     };
 942
 943     unsigned int ik, k, offset;
 944     unsigned int* mapping;
 945     Loser* losers;
 946     Comparator comp;
 947
 948     void map(unsigned int root, unsigned int begin, unsigned int end)
 949     {
 950       if (begin + 1 == end)
 951         mapping[begin] = root;
 952       else
 953         {
 954           // Next greater or equal power of 2.
 955           unsigned int left = 1 << (log2(end - begin - 1));
 956           map(root * 2, begin, begin + left);
 957           map(root * 2 + 1, begin + left, end);
 958         }
 959     }
 960
 961   public:
 962     inline
 963     LoserTreePointerUnguarded(unsigned int _k,
 964                               Comparator _comp = std::less<T>())
 965       : comp(_comp)
 966     {
 967       ik = _k;
 968
 969       // Next greater power of 2.
 970       k = 1 << (log2(ik - 1) + 1);
 971       offset = k;
 972       losers = new Loser[k + ik];
 973       mapping = new unsigned int[ik];
 974       map(1, 0, ik);
 975     }
 976
 977     inline ~LoserTreePointerUnguarded()
 978     {
 979       delete[] losers;
 980       delete[] mapping;
 981     }
 982
 983     inline int
 984     get_min_source()
 985     { return losers[0].source; }
 986
 987     inline void
 988     insert_start(const T& key, int source, bool)
 989     {
 990       unsigned int pos = mapping[source];
 991       losers[pos].source = source;
 992       losers[pos].keyp = &key;
 993     }
 994
 995     unsigned int
 996     init_winner(unsigned int root, unsigned int begin, unsigned int end)
 997     {
 998       if (begin + 1 == end)
 999         return mapping[begin];
1000       else
1001         {
1002           // Next greater or equal power of 2.
1003           unsigned int division = 1 << (log2(end - begin - 1));
1004           unsigned int left = init_winner(2 * root, begin, begin + division);
1005           unsigned int right
1006                           = init_winner(2 * root + 1, begin + division, end);
1007           if (!comp(*losers[right].keyp, *losers[left].keyp))
1008             {
1009               // Left one is less or equal.
1010               losers[root] = losers[right];
1011               return left;
1012             }
1013           else
1014             {
1015               // Right one is less.
1016               losers[root] = losers[left];
1017               return right;
1018             }
1019         }
1020     }
1021
1022     inline void
1023     init()
1024     {
1025       losers[0] = losers[init_winner(1, 0, ik)];
1026     }
1027
1028     inline void
1029     delete_min_insert(const T& key, bool)
1030     {
1031       const T* keyp = &key;
1032       int& source = losers[0].source;
1033       for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
1034         {
1035           // The smaller one gets promoted.
1036           if (comp(*losers[pos].keyp, *keyp))
1037             {
1038               // The other one is smaller.
1039               std::swap(losers[pos].source, source);
1040               std::swap(losers[pos].keyp, keyp);
1041             }
1042         }
1043
1044       losers[0].keyp = keyp;
1045     }
1046
1047     inline void
1048     insert_start_stable(const T& key, int source, bool)
1049     { return insert_start(key, source, false); }
1050
1051     inline void
1052     init_stable()
1053     { init(); }
1054
1055     inline void
1056     delete_min_insert_stable(const T& key, bool)
1057     {
1058       int& source = losers[0].source;
1059       const T* keyp = &key;
1060       for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
1061         {
1062           // The smaller one gets promoted, ties are broken by source.
1063           if (comp(*losers[pos].keyp, *keyp)
1064               || (!comp(*keyp, *losers[pos].keyp)
1065                   && losers[pos].source < source))
1066             {
1067               // The other one is smaller.
1068               std::swap(losers[pos].source, source);
1069               std::swap(losers[pos].keyp, keyp);
1070             }
1071         }
1072       losers[0].keyp = keyp;
1073     }
1074   };
1075 #endif
1076
1077 template<typename _ValueTp, class Comparator>
1078   struct loser_tree_traits
1079   {
1080 #if _GLIBCXX_LOSER_TREE
1081     typedef LoserTree<_ValueTp, Comparator> LT;
1082 #else
1083 #  if _GLIBCXX_LOSER_TREE_POINTER
1084     typedef LoserTreePointer<_ValueTp, Comparator> LT;
1085 #  else
1086 #    error Must define some type in losertree.h.
1087 #  endif
1088 #endif
1089   };
1090
1091 template<typename _ValueTp, class Comparator>
1092   struct loser_tree_unguarded_traits
1093   {
1094 #if _GLIBCXX_LOSER_TREE_UNGUARDED
1095     typedef LoserTreeUnguarded<_ValueTp, Comparator> LT;
1096 #else
1097 #  if _GLIBCXX_LOSER_TREE_POINTER_UNGUARDED
1098     typedef LoserTreePointerUnguarded<_ValueTp, Comparator> LT;
1099 #  else
1100 #    error Must define some unguarded type in losertree.h.
1101 #  endif
1102 #endif
1103   };
1104
1105 }
1106
1107 #endif