tpl_dynBinHeap.H

# ifndef TPL_DYNBINHEAP_H
# define TPL_DYNBINHEAP_H

# include <ahDry.H>
# include <tpl_binNodeUtils.H>
# include <tpl_binHeap.H>

using namespace Aleph;

namespace Aleph {

    template <class T, class Compare = Aleph::less<T>>
class DynBinHeap : public BinHeap<T, Compare>
{
public:

  typedef DynBinHeap Set_Type;

  typedef T Item_Type;

  typedef T Key_Type;

private:

  typedef typename BinHeap<T, Compare>::Node Node;

  T & __insert(Node * p)
  {
    return BinHeap<T, Compare>::insert(p)->get_key();
  }

  void copy(DynBinHeap & src)
  {
    for_each_in_preorder(src.top(), 
                         [this] (Node * p)
                         {
                           this->insert(new Node (p->get_key()));
                         });
  }

public:

  DynBinHeap(Compare & cmp) 
    : BinHeap<T, Compare>(cmp) 
  { /* empty */ }

  DynBinHeap(Compare && cmp = Compare()) 
    : BinHeap<T, Compare>(cmp) 
  { /* empty */ }

  DynBinHeap(const DynBinHeap & h)
  {
    copy(const_cast<DynBinHeap&>(h));
  }

  DynBinHeap(DynBinHeap && h)
  {
    this->swap(h);
  }

  DynBinHeap & operator = (const DynBinHeap & h)
  {
    if (this == &h)
      return *this;

    empty();

    copy(h);

    return *this;
  }

  DynBinHeap & operator = (DynBinHeap && h)
  {
    this->swap(h);
    return *this;
  }

  T & insert(const T & item) throw(std::exception, std::bad_alloc)
  {
    return __insert(new Node (item));
  }

  T & insert(T && item) throw(std::exception, std::bad_alloc)
  {
    return __insert(new Node (std::move(item)));
  }
  
  T & put(const T & item) throw(std::exception, std::bad_alloc)
  {
    return insert(item);
  }

  T & put(T && item) throw(std::exception, std::bad_alloc)
  {
    return insert(std::move(item));
  }

  T getMin() throw(std::exception, std::underflow_error)
  {
    Node * node = BinHeap<T, Compare>::getMin();

    T return_value = std::move(node->get_key());

    delete node;

    return return_value;
  }

  T getMax() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  T get() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  void update(T & data)
  {
    Node * node = Node::key_to_node(data);
    BinHeap<T, Compare>::update(node);
  }

  void remove(T & data)
  {
    Node * node = BinHeap<T, Compare>::Node::key_to_node(data);

    BinHeap<T, Compare>::remove(node);
  }
  
  void erase(T & data)
  {
    remove(data);
  }

  T & top() const throw(std::exception, std::underflow_error)
  {
    return BinHeap<T, Compare>::top()->get_key();
  }

  void empty()
  {
    this->remove_all_and_delete();
  }

  ~DynBinHeap()
  {
    empty();
  }

  template <class Operation>
  bool traverse(Operation & op) 
  {
    return this->level_traverse(this->getRoot(), [&op] (Node * p)
                                {
                                  return op(p->get_key());
                                });
  }

  template <class Operation>
  bool traverse(Operation && op = Operation())
  {
    return traverse(op);
  }

  template <class Operation>
  bool traverse(Operation & op) const
  {
    return this->level_traverse(this->getRoot(), [&op] (Node * p)
                                {
                                  return op(p->get_key());
                                });
  }

  template <class Operation>
  bool traverse(Operation && op = Operation()) const
  {
    return traverse<Operation>(op);
  }

  Functional_Methods(T);
};

} // end namespace Aleph

# endif // TPL_DYNBINHEAP_H