HeapT.hh

Go to the documentation of this file.

/* ========================================================================= *
 *                                                                           *
 *                               OpenMesh                                    *
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
 *           Department of Computer Graphics and Multimedia                  *
 *                          All rights reserved.                             *
 *                            www.openmesh.org                               *
 *                                                                           *
 *---------------------------------------------------------------------------*
 * This file is part of OpenMesh.                                            *
 *---------------------------------------------------------------------------*
 *                                                                           *
 * 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 OPENMESH_UTILS_HEAPT_HH
#define OPENMESH_UTILS_HEAPT_HH


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

#include "Config.hh"
#include <vector>
#include <OpenMesh/Core/System/omstream.hh>
#if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
#include <utility>
#endif

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

namespace OpenMesh { // BEGIN_NS_OPENMESH
namespace Utils { // BEGIN_NS_UTILS

//== 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 HeapT : private std::vector<HeapEntry>
{
private: 
  typedef std::vector<HeapEntry>            Base;
  
public:

  HeapT() : HeapVector() {}
  
#if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
  HeapT(HeapInterface _interface)
  : HeapVector(),  interface_(std::move(_interface))
  {}
#else
  explicit HeapT(const HeapInterface &_interface)
  : HeapVector(),  interface_(_interface)
  {}
#endif

  ~HeapT(){};

  HeapInterface &getInterface() {
      return interface_;
  }

  const HeapInterface &getInterface() const {
      return interface_;
  }

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

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

  size_t size() const { return HeapVector::size(); }

  void reserve(size_t _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() const
  { 
    assert(!empty()); 
    return HeapVector::front();
  }

  void pop_front()
  {    
    assert(!empty());
    reset_heap_position(HeapVector::front());
    if (size() > 1)
    {
      entry(0, entry(size()-1));
      Base::pop_back();
      downheap(0);
    }
    else
    {
      Base::pop_back();
    }
  }

  void remove(HeapEntry _h)
  {
    int pos = interface_.get_heap_position(_h);
    reset_heap_position(_h);

    assert(pos != -1);
    assert((unsigned int) pos < size());
    
    // last item ?
    if ((unsigned int) pos == size()-1)
    {
      Base::pop_back();    
    }
    else 
    {
      entry(pos, entry(size()-1)); // move last elem to pos
      Base::pop_back();
      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);
    for (unsigned int i=0; i<size(); ++i)
    {
      unsigned int j;
      if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j))) 
      {
        omerr() << "Heap condition violated\n";
        ok=false;
      }
      if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
      {
        omerr() << "Heap condition violated\n";
        ok=false;
      }
    }
    return ok;
  }

protected:  
  HeapInterface interface_;

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

  
  void upheap(size_t _idx);

  
  void downheap(size_t _idx);

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

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

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

};




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


template <class HeapEntry, class HeapInterface>
void
HeapT<HeapEntry, HeapInterface>::
upheap(size_t _idx)
{
  HeapEntry     h = entry(_idx);
  size_t        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(size_t _idx)
{
  const HeapEntry     h = entry(_idx);
  const size_t        s = size();
  
  while(_idx < s)
  {
    size_t 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);
}


//=============================================================================
} // END_NS_UTILS
} // END_NS_OPENMESH
//=============================================================================
#endif // OSG_HEAP_HH defined
//=============================================================================