/home/hauberg/Dokumenter/Capture/humim-tracker-0.1/src/OpenTissue/OpenTissue/core/containers/containers_heap.h

Go to the documentation of this file.

#ifndef OPENTISSUE_CORE_CONTAINERS_CONTAINERS_HEAP_H
#define OPENTISSUE_CORE_CONTAINERS_CONTAINERS_HEAP_H
//
// OpenTissue, A toolbox for physical based simulation and animation.
// Copyright (C) 2007 Department of Computer Science, University of Copenhagen
//
#include <OpenTissue/configuration.h>

#include <OpenTissue/core/math/math_constants.h>

#include <list>
#include <map>
#include <cassert>
#include <stdexcept>

namespace OpenTissue
{
  namespace containers
  {

    template<typename feature_type_,typename real_type_>
    class Heap
    {
    public:

      typedef real_type_      real_type;
      typedef feature_type_   feature_type;

    public:

      class heap_element
      {
      protected:

        feature_type   m_feature;
        real_type      m_priority;

      public:

        heap_element(feature_type const & f) 
          : m_feature(f)
          , m_priority( math::detail::highest<real_type>() )
        { }

      public:

        real_type           & priority()           { return m_priority; }
        feature_type  const & get_feature()  const { return m_feature;  }

      public:

        operator real_type () { return m_priority; }

      };

    protected:

      typedef std::list<heap_element>              heap_type;

    public:

      typedef typename heap_type::iterator         heap_iterator;

    protected:

      typedef std::map<feature_type,heap_iterator> lut_type;
      typedef typename lut_type::iterator          lut_iterator;
      typedef typename lut_type::const_iterator    const_lut_iterator;

      heap_type m_heap;  
      lut_type  m_lut;   

    public:

      Heap()
        : m_heap()
        , m_lut()
      {}


      ~Heap()  {  }


      void clear()
      {
        m_lut.clear();
        m_heap.clear();
      }

      std::size_t  size() const { return m_heap.size(); }

      heap_iterator push(feature_type const & f)
      {
        heap_iterator i = m_heap.insert(m_heap.end(), heap_element(f) );
        //m_lut[f]        = i;  //--- Yrk! Copy-constructor from singular iterator!!!
        m_lut.insert( std::make_pair(f, i ));
        return i;
      }

      bool erase(feature_type const & f )
      {
        if(m_heap.empty())
        {
          throw std::logic_error("Heap::erase(): trying to erase from an empty heap!");
          return false;
        }
        lut_iterator lookup = m_lut.find(f);
        if(lookup == m_lut.end())
        {
          throw std::invalid_argument("Heap::erase(): feature not in heap!");
          return false;
        }
        m_heap.erase(lookup->second);
        m_lut.erase(lookup);
        return true;
      }

      heap_iterator get_heap_iterator(feature_type const & f)
      {
        if(m_heap.empty())
        {
          throw std::logic_error("Heap::get_heap_iterator(): trying to get element from empty heap!");
          return m_heap.end();
        }
        lut_iterator lookup = m_lut.find(f);
        if(lookup == m_lut.end())
        {
          throw std::invalid_argument("Heap::get_heap_iterator(): feature not in heap!");
          return m_heap.end();
        }
        return lookup->second;
      }

      void heapify(heap_iterator i)
      {          
        // TODO 2006-09-26 KE: Add assertion to test if i belongs to this container

        if(m_heap.empty())
        {
          throw std::logic_error("Heap::heapify(): trying to heapify an empty heap!");
          return;
        }
        if(i==m_heap.end())
        {
          throw std::out_of_range("Heap::heapify(): can not use end position!");
          return;
        }

        if(i!=m_heap.begin())
        {
          heap_iterator j = i;
          --j;
          while(i!=m_heap.begin() && j->priority() < i->priority() )
          {
            feature_type A = i->get_feature();
            feature_type B = j->get_feature();
            heap_element tmp = *i;
            *i = *j;
            *j = tmp;

            assert( (m_lut.find(A) != m_lut.end()) || !"Heap::heapify(i): A was not stored in lut");
            assert( (m_lut.find(B) != m_lut.end()) || !"Heap::heapify(i): B was not stored in lut");

            m_lut[A] = j;
            m_lut[B] = i;
            if(j!=m_heap.begin())
              --j;
            --i;
          }
        }
        if(i!=m_heap.end())
        {
          heap_iterator j = i;
          ++j;
          while(j!=m_heap.end() && j->priority() > i->priority() )
          {
            feature_type A = i->get_feature();
            feature_type B = j->get_feature();
            heap_element tmp = *i;
            *i = *j;
            *j = tmp;

            assert( (m_lut.find(A) != m_lut.end()) || !"Heap::heapify(i): A was not stored in lut");
            assert( (m_lut.find(B) != m_lut.end()) || !"Heap::heapify(i): B was not stored in lut");

            m_lut[A] = j;
            m_lut[B] = i;
            ++j;
            ++i;
          }
        }
      }

      void heapify() { m_heap.sort( std::greater<real_type>() ); }

      heap_iterator top()  { return m_heap.begin(); }

      heap_iterator begin() { return m_heap.begin(); }

      heap_iterator end() { return m_heap.end(); }

    };

  } //End of namespace containers
} //End of namespace OpenTissue

// OPENTISSUE_CORE_CONTAINERS_CONTAINERS_HEAP_H
#endif