HeapT.hh

/*===========================================================================*\
 *                                                                           *
 *                              OpenFlipper                                  *
 *      Copyright (C) 2001-2009 by Computer Graphics Group, RWTH Aachen      *
 *                           www.openflipper.org                             *
 *                                                                           *
 *---------------------------------------------------------------------------*
 *  This file is part of OpenFlipper.                                        *
 *                                                                           *
 *  OpenFlipper is free software: you can redistribute it and/or modify      *
 *  it under the terms of the GNU Lesser General Public License as           *
 *  published by the Free Software Foundation, either version 3 of           *
 *  the License, or (at your option) any later version with the              *
 *  following exceptions:                                                    *
 *                                                                           *
 *  If other files instantiate templates or use macros                       *
 *  or inline functions from this file, or you compile this file and         *
 *  link it with other files to produce an executable, this file does        *
 *  not by itself cause the resulting executable to be covered by the        *
 *  GNU Lesser General Public License. This exception does not however       *
 *  invalidate any other reasons why the executable file might be            *
 *  covered by the GNU Lesser General Public License.                        *
 *                                                                           *
 *  OpenFlipper is distributed in the hope that it will be useful,           *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
 *  GNU Lesser General Public License for more details.                      *
 *                                                                           *
 *  You should have received a copy of the GNU LesserGeneral Public          *
 *  License along with OpenFlipper. If not,                                  *
 *  see <http://www.gnu.org/licenses/>.                                      *
 *                                                                           *
\*===========================================================================*/

/*===========================================================================*\
 *                                                                           *
 *   $Revision: 8521 $                                                       *
 *   $Author: moebius $                                                      *
 *   $Date: 2010-02-10 15:57:35 +0100 (Mi, 10. Feb 2010) $                   *
 *                                                                           *
\*===========================================================================*/




//=============================================================================
//
//  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)  { 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));
      resize(size()-1);
      downheap(0);
    }
    else 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
//=============================================================================