HeapT.hh

/*===========================================================================*\
 *                                                                           *
 *                              OpenFlipper                                  *
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
 *           Department of Computer Graphics and Multimedia                  *
 *                          All rights reserved.                             *
 *                            www.openflipper.org                            *
 *                                                                           *
 *---------------------------------------------------------------------------*
 * This file is part of OpenFlipper.                                         *
 *---------------------------------------------------------------------------*
 *                                                                           *
 * Redistribution and use in source and binary forms, with or without        *
 * modification, are permitted provided that the following conditions        *
 * are met:                                                                  *
 *                                                                           *
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
 *                                                                           *
 * 2. Redistributions in binary form must reproduce the above copyright      *
 *    notice, this list of conditions and the following disclaimer in the    *
 *    documentation and/or other materials provided with the distribution.   *
 *                                                                           *
 * 3. Neither the name of the copyright holder nor the names of its          *
 *    contributors may be used to endorse or promote products derived from   *
 *    this software without specific prior written permission.               *
 *                                                                           *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
 *                                                                           *
\*===========================================================================*/

/*===========================================================================*\
 *                                                                           *
 *   $Revision$                                                       *
 *   $Author$                                                      *
 *   $Date$                   *
 *                                                                           *
\*===========================================================================*/




//=============================================================================
//
//  CLASS HeapT
//
//=============================================================================

#ifndef ACG_HEAP_HH
#define ACG_HEAP_HH


//== INCLUDES =================================================================

#include <vector>
#include "../Config/ACGDefines.hh"


//== NAMESPACE ================================================================


namespace ACG {


//== CLASS DEFINITION =========================================================


template <class HeapEntry>
struct HeapInterfaceT
{
  bool less(const HeapEntry& _e1, const HeapEntry& _e2);

  bool greater(const HeapEntry& _e1, const HeapEntry& _e2);

  int  get_heap_position(const HeapEntry& _e);

  void set_heap_position(HeapEntry& _e, int _i);
};



template <class HeapEntry, class HeapInterface=HeapEntry>
class ACGDLLEXPORT HeapT : private std::vector<HeapEntry>
{
public:

  typedef std::vector<HeapEntry> Base;


  HeapT() : HeapVector() {}

  HeapT(const HeapInterface& _interface)
    : HeapVector(),  interface_(_interface)
  {}

  ~HeapT(){};


  void clear() { HeapVector::clear(); }

  bool empty() { return HeapVector::empty(); }

  unsigned int size() { return HeapVector::size(); }

  void reserve(unsigned int _n) { HeapVector::reserve(_n); }

  void reset_heap_position(HeapEntry _h)
  { interface_.set_heap_position(_h, -1); }

  bool is_stored(HeapEntry _h)
  { return interface_.get_heap_position(_h) != -1; }

  void insert(HeapEntry _h)  { this->push_back(_h); upheap(size()-1); }

  HeapEntry front() { assert(!empty()); return entry(0); }

  void pop_front()
  {
    assert(!empty());
    interface_.set_heap_position(entry(0), -1);
    if (size() > 1)
    {
      entry(0, entry(size()-1));
      this->resize(size()-1);
      downheap(0);
    }
    else this->resize(size()-1);
  }

  void remove(HeapEntry _h)
  {
    int pos = interface_.get_heap_position(_h);
    interface_.set_heap_position(_h, -1);

    assert(pos != -1);
    assert((unsigned int) pos < size());

    // last item ?
    if ((unsigned int) pos == size()-1)
      resize(size()-1);

    else {
      entry(pos, entry(size()-1)); // move last elem to pos
      resize(size()-1);
      downheap(pos);
      upheap(pos);
    }
  }

  void update(HeapEntry _h)
  {
    int pos = interface_.get_heap_position(_h);
    assert(pos != -1);
    assert((unsigned int)pos < size());
    downheap(pos);
    upheap(pos);
  }

  bool check()
  {
    bool ok(true);
    unsigned int i, j;
    for (i=0; i<size(); ++i)
    {
      if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j))) {
        std::cerr << "Heap condition violated\n";
        ok=false;
      }
      if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j))){
        std::cerr << "Heap condition violated\n";
        ok=false;
      }
    }
    return ok;
  }


private:

  // typedef
  typedef std::vector<HeapEntry> HeapVector;


  void upheap(unsigned int _idx);


  void downheap(unsigned int _idx);


  inline HeapEntry entry(unsigned int _idx) {
    assert(_idx < size());
    return (Base::operator[](_idx));
  }


  inline void entry(unsigned int _idx, HeapEntry _h) {
    assert(_idx < size());
    Base::operator[](_idx) = _h;
    interface_.set_heap_position(_h, _idx);
  }


  inline unsigned int parent(unsigned int _i) { return (_i-1)>>1; }
  inline unsigned int left(unsigned int _i)   { return (_i<<1)+1; }
  inline unsigned int right(unsigned int _i)  { return (_i<<1)+2; }


  HeapInterface  interface_;
};




//== IMPLEMENTATION ==========================================================


template <class HeapEntry, class HeapInterface>
void
HeapT<HeapEntry, HeapInterface>::
upheap(unsigned int _idx)
{
  HeapEntry     h = entry(_idx);
  unsigned int  parentIdx;

  while ((_idx>0) &&
         interface_.less(h, entry(parentIdx=parent(_idx))))
  {
    entry(_idx, entry(parentIdx));
    _idx = parentIdx;
  }

  entry(_idx, h);
}


//-----------------------------------------------------------------------------


template <class HeapEntry, class HeapInterface>
void
HeapT<HeapEntry, HeapInterface>::
downheap(unsigned int _idx)
{
  HeapEntry     h = entry(_idx);
  unsigned int  childIdx;
  unsigned int  s = size();

  while(_idx < s)
  {
    childIdx = left(_idx);
    if (childIdx >= s) break;

    if ((childIdx+1 < s) &&
        (interface_.less(entry(childIdx+1), entry(childIdx))))
      ++childIdx;

    if (interface_.less(h, entry(childIdx))) break;

    entry(_idx, entry(childIdx));
    _idx = childIdx;
  }

  entry(_idx, h);
}


//=============================================================================
} // namespace ACG
//=============================================================================
#endif // ACG_HEAP_HH defined
//=============================================================================