RhodeCode

            //break;

          } else {

            if( container[ch].left_child ) {

              child_right=container[ch].parent;

              container[ch].parent = i;

              --container[i].degree;

            }

            else {

              child_right=ch;

              container[i].child=-1;

              container[i].degree=0;

            }

            container[child_right].parent = -1;

            TreeArray[num_child] = child_right;

            i = child_right;

            ++num_child;

          }

        }

        int other;

        for( i=0; i<num_child-1; i+=2 ) {

          if ( !comp(container[TreeArray[i]].prio,

                     container[TreeArray[i+1]].prio) ) {

            other=TreeArray[i];

            TreeArray[i]=TreeArray[i+1];

            TreeArray[i+1]=other;

          }

          fuse( TreeArray[i], TreeArray[i+1] );

        }

        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;

        while(i>=2) {

          if ( comp(container[TreeArray[i]].prio,

                    container[TreeArray[i-2]].prio) ) {

            other=TreeArray[i];

            TreeArray[i]=TreeArray[i-2];

            TreeArray[i-2]=other;

          }

          fuse( TreeArray[i-2], TreeArray[i] );

          i-=2;

        }

        minimum = TreeArray[0];

      }

      if ( 0==num_child ) {

        minimum = container[minimum].child;

      }

      --num_items;

    }

    /// \brief Deletes \c item from the heap.

    ///

    /// This method deletes \c item from the heap, if \c item was already

    /// stored in the heap. It is quite inefficient in Pairing heaps.

    void erase (const Item& item) {

      int i=iimap[item];

      if ( i>=0 && container[i].in ) {

        decrease( item, container[minimum].prio-1 );

        pop();

      }

    }

    /// \brief Decreases the priority of \c item to \c value.

    ///

    /// This method decreases the priority of \c item to \c value.

    /// \pre \c item must be stored in the heap with priority at least \c

    ///   value relative to \c Compare.

    void decrease (Item item, const Prio& value) {

      int i=iimap[item];

      container[i].prio=value;

      int p=container[i].parent;

      if( container[i].left_child && i!=container[p].child ) {

        p=container[p].parent;

      }

      if ( p!=-1 && comp(value,container[p].prio) ) {

        cut(i,p);

        if ( comp(container[minimum].prio,value) ) {

          fuse(minimum,i);

        } else {

          fuse(i,minimum);

          minimum=i;

        }

      }

    }

    /// \brief Increases the priority of \c item to \c value.

    ///

    /// This method sets the priority of \c item to \c value. Though

    /// there is no precondition on the priority of \c item, this

    /// method should be used only if it is indeed necessary to increase

    /// (relative to \c Compare) the priority of \c item, because this

    /// method is inefficient.

    void increase (Item item, const Prio& value) {

  {

    typedef BinHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BinHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // FouraryHeap

  {

    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // KaryHeap

  {

    typedef KaryHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // FibHeap

  {

    typedef FibHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef FibHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // PairingHeap

  // RadixHeap

  {

    typedef RadixHeap<ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef RadixHeap<IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // BinomHeap

  {

    typedef BinomHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  // BucketHeap, SimpleBucketHeap

  {

    typedef BucketHeap<ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BucketHeap<IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;

    heapSortTest<SimpleIntHeap>();

  }

  return 0;

}