#ifdef HAVE_SEQ_HEAP
#include "tsequentialheap.h"
#endif
#include "tstaticheap.h"
#include <iostream>
#include <ctime>
#include <algorithm>

#include <boost/heap/b_heap.hpp>
#include <boost/heap/binomial_heap.hpp>
#include <boost/heap/d_ary_heap.hpp>
#include <boost/heap/fibonacci_heap.hpp>

class OFastCompare;
class OFasterCompare;

// some typedefs to simplify certain experiments.
#ifdef DOUBLECHECK
typedef double value_type;
#else
typedef float value_type;
#endif

#ifdef SLOPPY_COMPARE
typedef OFasterCompare OCompare_t;
#else
typedef OFastCompare OCompare_t;
#endif

/// A functor that allows to test for the differences in
/// performance and output behavior, when comparing only the key
/// or the (key, pointer) pair.
class OFastCompare
{
public:
   static std::size_t m_lNrCall;
   bool operator() (
      const std::pair<value_type,value_type*>& rFirst_p,
      const std::pair<value_type,value_type*>& rSecond_p) const
   {
      ++m_lNrCall;
      return (rFirst_p < rSecond_p);
   }
};
std::size_t OFastCompare::m_lNrCall = 0;

class OFasterCompare
{
public:
   static std::size_t m_lNrCall;
   bool operator() (
      const std::pair<value_type,value_type*>& rFirst_p,
      const std::pair<value_type,value_type*>& rSecond_p) const
   {
      //++m_lNrCall;
      return (rFirst_p.first < rSecond_p.first);
   }
};
std::size_t OFasterCompare::m_lNrCall = 0;

class OStaticTestHeap
{
   TStaticHeap<std::pair<value_type, value_type*>, OCompare_t> m_tHeap;

public:
   void Insert (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      return m_tHeap.Update (lOffset_p, std::make_pair (*(pBase_p+lOffset_p), pBase_p+lOffset_p));
   }

   void Update (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      return Insert (pBase_p, lOffset_p);
   }

   value_type* Pop()
   {
      if (m_tHeap.Is_Empty())
      {
         return 0;
      }
      std::size_t lIndex;
      std::pair<value_type, value_type*> tRet (m_tHeap.Get_Top (lIndex));
      m_tHeap.Remove (lIndex);
      return tRet.second;
   }

   std::size_t Set_Size (
      std::size_t lSize_p)
   {
      m_tHeap.Set_NrIndex (lSize_p);
      return lSize_p;
   }
};

#ifdef HAVE_SEQ_HEAP
class OUglyTestHeap
{
   TUglyHeap<std::pair<value_type, value_type*>, OCompare_t> m_tHeap;

public:
   void Insert (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      m_tHeap.Push (std::make_pair (*(pBase_p+lOffset_p), pBase_p+lOffset_p));
   }

   void Update (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      return Insert (pBase_p, lOffset_p);
   }

   value_type* Pop()
   {
      if (!m_tHeap.Is_Empty())
      {
         std::pair<value_type, value_type*> tRet (m_tHeap.Get_Top());
         m_tHeap.Pop();
         return tRet.second;
      }
      else
      {
         return 0;
      }
   }

   std::size_t Set_Size (
      std::size_t lSize_p)
   {
      return m_tHeap.m_lCapacity;
   }
};

class OSequentialTestHeap
{
   TSequentialHeap<value_type, value_type*, OCompare_t> m_tHeap;

public:
   void Insert (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      return m_tHeap.Insert (pBase_p+lOffset_p);
   }

   void Update (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      return Insert (pBase_p, lOffset_p);
   }

   value_type* Pop()
   {
      return m_tHeap.Pop();
   }

   std::size_t Set_Size (
      std::size_t lSize_p)
   {
      return lSize_p;
   }
};
#endif

class OCompareI : public OCompare_t
{
public:
   bool operator() (
      const std::pair<value_type,value_type*>& rFirst_p,
      const std::pair<value_type,value_type*>& rSecond_p) const
   {
      return OCompare_t::operator()(rSecond_p, rFirst_p);
   }
};

template <typename HeapType>
class OBoostTestHeap
{
   typedef HeapType heap_type;
   heap_type m_tHeap;
   std::vector<typename heap_type::handle_type> m_tBackpointer;

public:
   void Insert (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      m_tBackpointer[lOffset_p] = m_tHeap.push (std::make_pair (*(pBase_p+lOffset_p), pBase_p+lOffset_p));
   }

   void Update (
      value_type* pBase_p,
      std::size_t lOffset_p)
   {
      (*m_tBackpointer[lOffset_p]).first = *(pBase_p+lOffset_p);
      // This form of update is really slow for a fibonacci_heap:
      //m_tHeap.update (m_tBackpointer[lOffset_p]);
      // This form of update works much better for a fibonacci_heap:
      //m_tHeap.update (m_tBackpointer[lOffset_p], std::make_pair (*(pBase_p+lOffset_p), pBase_p+lOffset_p));
      // But because we know that the value has increased, this form is fastest:
      m_tHeap.increase (m_tBackpointer[lOffset_p]);
   }

   value_type* Pop()
   {
      if (!m_tHeap.empty())
      {
         std::pair<value_type, value_type*> tRet (m_tHeap.top());
         m_tHeap.pop();
         return tRet.second;
      }
      else
      {
         return 0;
      }
   }

   std::size_t Set_Size (
      std::size_t lSize_p)
   {
      if (!m_tHeap.empty())
      {
         exit(1);
      }
      // FIXME: I don't understand why the fibonacci_heap shows undefined behavior if clear() is not called.
      m_tHeap.clear();
      m_tBackpointer.clear();
      m_tBackpointer.resize(lSize_p);
      return lSize_p;
   }
};

typedef OBoostTestHeap<boost::heap::b_heap_mutable<std::pair<value_type, value_type*>, boost::heap::compare<OCompareI> > > OBTestHeap;
typedef OBoostTestHeap<boost::heap::binomial_heap<std::pair<value_type, value_type*>, boost::heap::compare<OCompareI> > > OBinomialTestHeap;
typedef OBoostTestHeap<boost::heap::d_ary_heap_mutable<std::pair<value_type, value_type*>, boost::heap::arity<4>, boost::heap::compare<OCompareI> > > ODAryTestHeap;
typedef OBoostTestHeap<boost::heap::fibonacci_heap<std::pair<value_type, value_type*>, boost::heap::compare<OCompareI> > > OFibonacciTestHeap;


template <class THEAP>
bool
Pass_Small_HeapTest (
      THEAP& riHeap_p,
      bool bPrint_p = false)
{
   bool bPass = true;
   //Some arbitrary data for basic tests.
   value_type pdData[] = {3.0, 2.0, 2.4, 1.1,
      0.3, 3.72, 6.1, 7.2,
      -1.3, -0.3, -0.2, -0.1,
      -3.1, 11.5, 13.2, 21.3,
      3.0, 2.0, 2.4, 1.1,
      0.3, 3.72, 6.1, 7.2,
      -1.3, -0.3, -0.2, -0.1,
      -3.1, 11.5, 13.2, 21.3};
   std::size_t pInsert[] = {7, 32};
   std::size_t pPop[] = {4, 32};
   std::pair<value_type,value_type*> tMinVal (-1000.0, 0);

   OCompare_t oCompare;
   std::size_t lSize = riHeap_p.Set_Size (32);

   std::size_t lCount = 0;
   std::size_t lStart = 0;
   for (std::size_t lTime = 0; lTime < 2; ++lTime)
   {
      pInsert[lTime] = std::min (pInsert[lTime], lSize);
      for (std::size_t i = lStart; i < pInsert[lTime]; ++i)
      {
         riHeap_p.Insert (pdData, i);
         ++lCount;
      }
      lStart = pInsert[lTime];
      std::size_t lNewCount = 0;
      if (lCount > pPop[lTime])
      {
         lNewCount = lCount - pPop[lTime];
      }
      std::pair<value_type,value_type*> tOldVal = tMinVal;
      for (std::size_t i = 0; i < pPop[lTime]; ++i)
      {
         value_type* pVal = riHeap_p.Pop();
         if (bPrint_p)
         {
            std::cout << pVal;
         }
         if (pVal)
         {
            std::pair<value_type,value_type*> tActVal (*pVal, pVal);
            --lCount;
            if (oCompare (tActVal, tOldVal) || *tActVal.second != tActVal.first)
            {
               bPass = false;
               bPrint_p = true;
            }
            tOldVal = tActVal;
            if (bPrint_p)
            {
               std::cout << " " << tActVal.first << std::endl;
            }
         }
         else
         {
            if (bPrint_p)
            {
               std::cout << " --" << std::endl;
            }
         }
      }
      if (lCount != lNewCount)
      {
         bPass = false;
      }
   }
   return bPass;
}

template <class THEAP>
bool
Pass_Linear_HeapTest (
      THEAP& riHeap_p,
      std::size_t lTestSize_p,
      bool bDirection_p = false,
      bool bPrint_p = false)
{
   bool bPass = true;
   value_type* pData = new value_type [lTestSize_p];

   if (bDirection_p)
   {
      for (std::size_t i = 0; i < lTestSize_p; ++i)
      {
         pData[i] = i + 1;
      }
   }
   else
   {
      for (std::size_t i = 0; i < lTestSize_p; ++i)
      {
         pData[i] = lTestSize_p - i;
      }
   }
   if (bPrint_p)
   {
      std::cout << "Data generated" << std::endl;
   }
   lTestSize_p = riHeap_p.Set_Size (lTestSize_p);
   std::size_t lCount = 0;
   for (std::size_t i = 0; i < lTestSize_p; ++i)
   {
      riHeap_p.Insert (pData, i);
      ++lCount;
   }
   if (bPrint_p)
   {
      std::cout << "Heap filled" << std::endl;
   }
   value_type dOld = -1.0;
   for (std::size_t i = 0; i < lTestSize_p; ++i)
   {
      value_type* pVal = riHeap_p.Pop();
      if (!pVal)
      {
         bPass = false;
         std::cout << dOld << " - " << i << std::endl;
         continue;
      }
      --lCount;
      value_type dNew = *pVal;
      if (!(dOld < dNew))
      {
         bPass = false;
         std::cout << dOld << " " << dNew << " " << i << std::endl;
      }
      dOld = dNew;
   }
   if (lCount != 0)
   {
      bPass = false;
   }
   if (bPrint_p)
   {
      std::cout << "Heap emptied" << std::endl;
   }
   delete [] pData;
   return bPass;
}

template <class THEAP>
bool
Pass_March_HeapTest (
      THEAP& riHeap_p,
      std::size_t lDimX_p,
      std::size_t lDimY_p,
      std::size_t lDimZ_p,
#ifdef MARCH_SPEED
      std::size_t lSpeed_p = MARCH_SPEED
#else
      std::size_t lSpeed_p = 1
#endif
      )
{
   bool bPass = true;
   if (riHeap_p.Set_Size (lDimX_p*lDimY_p*lDimZ_p) != lDimX_p*lDimY_p*lDimZ_p)
   {
      return false;
   }
   value_type* pData = new value_type [lDimX_p*lDimY_p*lDimZ_p];
   value_type oUntouched = value_type (lDimX_p*lDimY_p*lDimZ_p);
   std::fill (pData, pData+lDimX_p*lDimY_p*lDimZ_p, oUntouched);

   // initializing
   for (std::size_t lY = 0; lY < lDimY_p; ++lY)
   {
      for (std::size_t lX = 0; lX < lDimX_p; ++lX)
      {
         pData[lX+lDimX_p*lY] = lX+lDimX_p*lY;
         riHeap_p.Insert (pData, lX+lDimX_p*lY);
      }
   }

   // marching
   for (std::size_t lZ = 0; lZ < lDimZ_p; ++lZ)
   {
      for (std::size_t lY = 0; lY < lDimY_p; ++lY)
      {
         for (std::size_t lX = 0; lX < lDimX_p; ++lX)
         {
            std::size_t lVal = lX+lDimX_p*(lY+lDimY_p*lZ);
            value_type* pVal = riHeap_p.Pop();
            if (pVal != &pData[lVal])
            {
               std::cout << "lDiff = " << pVal-pData << std::endl;
               bPass = false;
            }
            if (lX < lDimX_p-1)
            {
               value_type dNewVal = lVal + 1;
               if (oUntouched == pData[lVal + 1])
               {
                  pData[lVal + 1] = dNewVal;
                  riHeap_p.Insert (pData, lVal + 1);
               }
               else if (dNewVal < pData[lVal + 1])
               {
                  pData[lVal + 1] = dNewVal;
                  riHeap_p.Update (pData, lVal + 1);
               }
            }
            if (lY < lDimY_p-1)
            {
               value_type dNewVal = lVal + lDimX_p;
               if (lSpeed_p < 1 && lX)
               {
                  dNewVal += 0.25;
               }
               if (oUntouched == pData[lVal + lDimX_p])
               {
                  pData[lVal + lDimX_p] = dNewVal;
                  riHeap_p.Insert (pData, lVal + lDimX_p);
               }
               else if (dNewVal < pData[lVal + lDimX_p])
               {
                  pData[lVal + lDimX_p] = dNewVal;
                  riHeap_p.Update (pData, lVal + lDimX_p);
               }
            }
            if (lZ < lDimZ_p-1)
            {
               value_type dNewVal = lVal + lDimX_p*lDimY_p;
               if (lSpeed_p < 2 && (lX || lY))
               {
                  dNewVal += 0.5;
               }
               if (oUntouched == pData[lVal + lDimX_p*lDimY_p])
               {
                  pData[lVal + lDimX_p*lDimY_p] = dNewVal;
                  riHeap_p.Insert (pData, lVal + lDimX_p*lDimY_p);
               }
               else if (dNewVal < pData[lVal + lDimX_p*lDimY_p])
               {
                  pData[lVal + lDimX_p*lDimY_p] = dNewVal;
                  riHeap_p.Update (pData, lVal + lDimX_p*lDimY_p);
               }
            }
         }
      }
   }

   // Test that the heap is empty
   value_type* pEmptyVal = riHeap_p.Pop();
   if (pEmptyVal)
   {
      std::cout << "pEmptyVal = " << pEmptyVal << std::endl;
      bPass = false;
   }
   delete [] pData;
   return bPass;
}

enum EHeapTest
{
   eHeapTest_LinearForward,
   eHeapTest_LinearBackward,
   eHeapTest_March
};

template <class THEAP>
void
Measure_HeapPerformance (
      THEAP& riHeap_p,
      const char* pHeapName,
      EHeapTest eHeapTest_p,
      std::size_t lTimes_p)
{
   std::size_t lPerfSize = 7*(1<<16)+7*15;
   std::size_t lMarchSize = 500;
   for (std::size_t i = 0; i< lTimes_p; ++i)
   {
      std::clock_t lTime;
      {
         std::clock_t lOldClock = std::clock();
         OCompare_t::m_lNrCall = 0;         
         switch (eHeapTest_p)
         {
         case eHeapTest_LinearForward:
            Pass_Linear_HeapTest (riHeap_p, lPerfSize, true, false);
            break;
         case eHeapTest_LinearBackward:
            Pass_Linear_HeapTest (riHeap_p, lPerfSize, false, false);
            break;
         case eHeapTest_March:
            Pass_March_HeapTest (riHeap_p, lMarchSize, lMarchSize, 10);
            break;
         }
         lTime = std::clock() - lOldClock;
      }
      std::cout.width(6);
      std::cout << lTime << " ticks and "
         << OCompare_t::m_lNrCall << " compares for " << pHeapName << std::endl;
   }
}


const char*
Get_PassedText (
      bool bPassed_p)
{
   return (bPassed_p ? "passed\n" : "FAILED\n");
}

int main()
{
#ifdef PROFILE_PERFORMANCE
   if (false)
#endif
   {
      std::cout << "\nSanity Check\n";
      std::size_t lTestSize = 7*(1<<6);
      OStaticTestHeap oStaticTestHeap;
      bool bPass_SmallStaticTest = Pass_Small_HeapTest (oStaticTestHeap);
      bool bPass_LinearStaticTest = Pass_Linear_HeapTest (oStaticTestHeap, lTestSize);
      bool bPass_MarchStaticTest = Pass_March_HeapTest (oStaticTestHeap, 20, 20, 20);
      std::cout << "Small  TStaticHeap     Test : " << Get_PassedText (bPass_SmallStaticTest);
      std::cout << "Linear TStaticHeap     Test : " << Get_PassedText (bPass_LinearStaticTest);
      std::cout << "March  TStaticHeap     Test : " << Get_PassedText (bPass_MarchStaticTest);
#ifdef HAVE_SEQ_HEAP
      OUglyTestHeap oUglyTestHeap;
      bool bPass_SmallUglyTest = Pass_Small_HeapTest (oUglyTestHeap);
      bool bPass_LinearUglyTest = Pass_Linear_HeapTest (oUglyTestHeap, lTestSize);
      std::cout << "Small  TUglyHeap       Test : " << Get_PassedText (bPass_SmallUglyTest);
      std::cout << "Linear TUglyHeap       Test : " << Get_PassedText (bPass_LinearUglyTest);
      OSequentialTestHeap oSequentialTestHeap;
      bool bPass_SmallSeqTest = Pass_Small_HeapTest (oSequentialTestHeap);
      bool bPass_LinearSeqTest = Pass_Linear_HeapTest (oSequentialTestHeap, lTestSize);
      bool bPass_MarchSeqTest = Pass_March_HeapTest (oSequentialTestHeap, 20, 20, 20);
      std::cout << "Small  TSequentialHeap Test : " << Get_PassedText (bPass_SmallSeqTest);
      std::cout << "Linear TSequentialHeap Test : " << Get_PassedText (bPass_LinearSeqTest);
      std::cout << "March  TSequentialHeap Test : " << Get_PassedText (bPass_MarchSeqTest);
#endif
      OBTestHeap oBTestHeap;
      bool bPass_SmallBTest = Pass_Small_HeapTest (oBTestHeap);
      bool bPass_LinearBTest = Pass_Linear_HeapTest (oBTestHeap, lTestSize);
      bool bPass_MarchBTest = Pass_March_HeapTest (oBTestHeap, 20, 20, 20);
      std::cout << "Small  b_heap          Test : " << Get_PassedText (bPass_SmallBTest);
      std::cout << "Linear b_heap          Test : " << Get_PassedText (bPass_LinearBTest);
      std::cout << "March  b_heap          Test : " << Get_PassedText (bPass_MarchBTest);
      OBinomialTestHeap oBinomialTestHeap;
      bool bPass_SmallBinomialTest = Pass_Small_HeapTest (oBinomialTestHeap);
      bool bPass_LinearBinomialTest = Pass_Linear_HeapTest (oBinomialTestHeap, lTestSize);
      bool bPass_MarchBinomialTest = Pass_March_HeapTest (oBinomialTestHeap, 20, 20, 20);
      std::cout << "Small  binomial_heap   Test : " << Get_PassedText (bPass_SmallBinomialTest);
      std::cout << "Linear binomial_heap   Test : " << Get_PassedText (bPass_LinearBinomialTest);
      std::cout << "March  binomial_heap   Test : " << Get_PassedText (bPass_MarchBinomialTest);
      ODAryTestHeap oDAryTestHeap;
      bool bPass_SmallDAryTest = Pass_Small_HeapTest (oDAryTestHeap);
      bool bPass_LinearDAryTest = Pass_Linear_HeapTest (oDAryTestHeap, lTestSize);
      bool bPass_MarchDAryTest = Pass_March_HeapTest (oDAryTestHeap, 20, 20, 20);
      std::cout << "Small  d_ary_heap      Test : " << Get_PassedText (bPass_SmallDAryTest);
      std::cout << "Linear d_ary_heap      Test : " << Get_PassedText (bPass_LinearDAryTest);
      std::cout << "March  d_ary_heap      Test : " << Get_PassedText (bPass_MarchDAryTest);
      OFibonacciTestHeap oFibonacciTestHeap;
      bool bPass_SmallFibonacciTest = Pass_Small_HeapTest (oFibonacciTestHeap);
      bool bPass_LinearFibonacciTest = Pass_Linear_HeapTest (oFibonacciTestHeap, lTestSize);
      bool bPass_MarchFibonacciTest = Pass_March_HeapTest (oFibonacciTestHeap, 20, 20, 20);
      std::cout << "Small  fibonacci_heap  Test : " << Get_PassedText (bPass_SmallFibonacciTest);
      std::cout << "Linear fibonacci_heap  Test : " << Get_PassedText (bPass_LinearFibonacciTest);
      std::cout << "March  fibonacci_heap  Test : " << Get_PassedText (bPass_MarchFibonacciTest);
      if (!(
         bPass_SmallStaticTest &&
         bPass_LinearStaticTest &&
         bPass_MarchStaticTest &&
#ifdef HAVE_SEQ_HEAP
         bPass_SmallUglyTest &&
         bPass_LinearUglyTest &&
         bPass_SmallSeqTest &&
         bPass_LinearSeqTest &&
         bPass_MarchSeqTest &&
#endif
         bPass_SmallFibonacciTest &&
         bPass_LinearFibonacciTest &&
         bPass_MarchFibonacciTest &&
         true))
      {
         exit (1);
      }
   }

   std::size_t lProfileTimes = 1;
   std::size_t lTimes = 2;
#ifdef PROFILE_PERFORMANCE
   lTimes = 0;
#endif
   std::cout << "\nPerformance Check for Linear Forward\n";
   {
      OStaticTestHeap oStaticTestHeap1;
      Measure_HeapPerformance (oStaticTestHeap1, "TStaticHeap",
         eHeapTest_LinearForward, lTimes);
   }
#ifdef HAVE_SEQ_HEAP
   {
      OSequentialTestHeap oSequentialTestHeap1;
      Measure_HeapPerformance (oSequentialTestHeap1, "TSequentialHeap",
         eHeapTest_LinearForward, lTimes);
   }
#endif
   {
      OBTestHeap oBTestHeap1;
      Measure_HeapPerformance (oBTestHeap1, "b_heap",
         eHeapTest_LinearForward, lTimes);
   }
   {
      OBinomialTestHeap oBinomialTestHeap1;
      Measure_HeapPerformance (oBinomialTestHeap1, "binomial_heap",
         eHeapTest_LinearForward, lTimes);
   }
   {
      ODAryTestHeap oDAryTestHeap1;
      Measure_HeapPerformance (oDAryTestHeap1, "d_ary_heap",
         eHeapTest_LinearForward, lTimes);
   }
   {
      OFibonacciTestHeap oFibonacciTestHeap1;
      Measure_HeapPerformance (oFibonacciTestHeap1, "fibonacci_heap",
         eHeapTest_LinearForward, lTimes);
   }
   std::cout << "\nPerformance Check for Linear Backward\n";
   {
      OStaticTestHeap oStaticTestHeap1;
      Measure_HeapPerformance (oStaticTestHeap1, "TStaticHeap",
         eHeapTest_LinearBackward, lTimes);
   }
#ifdef HAVE_SEQ_HEAP
   {
      OSequentialTestHeap oSequentialTestHeap1;
      Measure_HeapPerformance (oSequentialTestHeap1, "TSequentialHeap",
         eHeapTest_LinearBackward, lTimes);
   }
#endif
   {
      OBTestHeap oBTestHeap1;
      Measure_HeapPerformance (oBTestHeap1, "b_heap",
         eHeapTest_LinearBackward, lTimes);
   }
   {
      OBinomialTestHeap oBinomialTestHeap1;
      Measure_HeapPerformance (oBinomialTestHeap1, "binomial_heap",
         eHeapTest_LinearBackward, lTimes);
   }
   {
      ODAryTestHeap oDAryTestHeap1;
      Measure_HeapPerformance (oDAryTestHeap1, "d_ary_heap",
         eHeapTest_LinearBackward, lTimes);
   }
   {
      OFibonacciTestHeap oFibonacciTestHeap1;
      Measure_HeapPerformance (oFibonacciTestHeap1, "fibonacci_heap",
         eHeapTest_LinearBackward, lTimes);
   }
   std::cout << "\nPerformance Check for March\n";
   {
      OStaticTestHeap oStaticTestHeap1;
      Measure_HeapPerformance (oStaticTestHeap1, "TStaticHeap",
         eHeapTest_March, lTimes);
   }
#ifdef HAVE_SEQ_HEAP
   {
      OSequentialTestHeap oSequentialTestHeap1;
      Measure_HeapPerformance (oSequentialTestHeap1, "TSequentialHeap",
         eHeapTest_March, std::max (lProfileTimes, lTimes));
   }
#endif
   {
      OBTestHeap oBTestHeap1;
      Measure_HeapPerformance (oBTestHeap1, "b_heap",
         eHeapTest_March, lTimes);
   }
   {
      OBinomialTestHeap oBinomialTestHeap1;
      Measure_HeapPerformance (oBinomialTestHeap1, "binomial_heap",
         eHeapTest_March, lTimes);
   }
   {
      ODAryTestHeap oDAryTestHeap1;
      Measure_HeapPerformance (oDAryTestHeap1, "d_ary_heap",
         eHeapTest_March, lTimes);
   }
   {
      OFibonacciTestHeap oFibonacciTestHeap1;
      Measure_HeapPerformance (oFibonacciTestHeap1, "fibonacci_heap",
         eHeapTest_March, lTimes);
   }
}