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.              *
 *                                                                           *
\*===========================================================================*/
 
 
 
 
 
 
//=============================================================================
//
//  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
//=============================================================================