SnippyHolloW-BroodwarBotQ-f01ab56/src/Macro/Heap.h

Go to the documentation of this file.

#pragma once

#include <vector>
#include <map>
#include <utility>

  template <class _Tp,class _Val> 
  class Heap
  {
    private :
    std::vector< std::pair< _Tp, _Val > > data;

    std::map< _Tp, int> mapping;

    bool minHeap;

    int percolate_up(int index);

    int percolate_down(int index);

    public :
    Heap(bool isMinHeap = false) : minHeap(isMinHeap) {}
    ~Heap() {}
    void push(std::pair< _Tp, _Val > x);
    void pop();
    const std::pair< _Tp, _Val >& top() const;
    bool set(_Tp& x,_Val& v);
    const _Val& get(_Tp& x) const;

    bool contains(_Tp& x) const;

    bool empty() const;
    int size() const;
    void clear();
    bool erase(_Tp& x);
  };

  //------------------------------- PERCOLATE UP ---------------------------------
  template <class _Tp, class _Val>
  int Heap<_Tp,_Val>::percolate_up(int index)
  {
    if (index<0 || index>=(int)data.size())
      return -1;
    unsigned int parent=(index-1)/2;
    int m=1;
    if (this->minHeap) m=-1;
    while(index>0 && m*data[parent].second<m*data[index].second)
    {
      std::pair<_Tp,_Val> temp=data[parent];
      data[parent]=data[index];
      data[index]=temp;
      (*mapping.find(data[index].first)).second=index;
      index=parent;
      parent=(index-1)/2;
    }
    (*mapping.find(data[index].first)).second=index;
    return index;
  }

  //------------------------------ PERCOLATE DOWN --------------------------------
  template <class _Tp, class _Val>
  int Heap<_Tp,_Val>::percolate_down(int index)
  {
    if (index<0 || index>=(int)data.size())
      return -1;
    unsigned int lchild=index*2+1;
    unsigned int rchild=index*2+2;
    unsigned int mchild;
    int m=1;
    if (this->minHeap) m=-1;
    while((data.size()>lchild && m*data[index].second<m*data[lchild].second) ||
      (data.size()>rchild && m*data[index].second<m*data[rchild].second))
    {
      mchild=lchild;
      if (data.size()>rchild && m*data[rchild].second>m*data[lchild].second)
        mchild=rchild;
      std::pair< _Tp, _Val > temp=data[mchild];
      data[mchild]=data[index];
      data[index]=temp;
      (*mapping.find(data[index].first)).second=index;
      index=mchild;
      lchild=index*2+1;
      rchild=index*2+2;
    }
    (*mapping.find(data[index].first)).second=index;
    return index;
  }
  //----------------------------------- PUSH -------------------------------------
  template <class _Tp, class _Val>
  void Heap<_Tp,_Val>::push(std::pair< _Tp, _Val > x)
  {
    int index=data.size();
    if (mapping.insert(std::make_pair(x.first,index)).second)
    {
      data.push_back(x);
      percolate_up(index);
    }
  }

  //----------------------------------- POP --------------------------------------
  template <class _Tp, class _Val>
  void Heap<_Tp,_Val>::pop()
  {
    if (data.empty())
      return;
    mapping.erase(data.front().first);
    data.front()=data.back();
    data.pop_back();
    if (data.empty())
      return;
    std::map<_Tp,int>::iterator iter=mapping.find(data.front().first);
    if (iter!=mapping.end())
    {
      (*iter).second=0;
      percolate_down(0);
    }
  }

  //----------------------------------- TOP --------------------------------------
  template <class _Tp, class _Val>
  const std::pair< _Tp, _Val >& Heap<_Tp,_Val>::top() const
  {
    return data.front();
  }

  //---------------------------------- EMPTY -------------------------------------
  template <class _Tp, class _Val>
  bool Heap<_Tp,_Val>::empty() const
  {
    return data.empty();
  }

  //----------------------------------- SET --------------------------------------
  template <class _Tp, class _Val>
  bool Heap<_Tp,_Val>::set(_Tp& x,_Val& v)
  {
    std::map<_Tp,int>::iterator iter=mapping.find(x);
    if (iter==mapping.end())
    {
      push(std::make_pair(x,v));
      return true;
    }
    int index=(*iter).second;
    data[index].second=v;
    index=percolate_up(index);
    if (index>=0 && index<(int)data.size())
    {
      percolate_down(index);
      return true;
    }
    return false;
  }

  //----------------------------------- GET --------------------------------------
  template <class _Tp, class _Val>
  const _Val& Heap<_Tp,_Val>::get(_Tp& x) const
  {
    std::map<_Tp,int>::const_iterator iter=mapping.find(x);
    int index=(*iter).second;
    return data[index].second;
  }

  //--------------------------------- CONTAINS -----------------------------------
  template <class _Tp, class _Val>
  bool Heap<_Tp,_Val>::contains(_Tp& x) const
  {
    std::map<_Tp,int>::const_iterator iter=mapping.find(x);
    return (iter!=mapping.end());
  }

  //---------------------------------- SIZE --------------------------------------
  template <class _Tp, class _Val>
  int Heap<_Tp,_Val>::size() const
  {
    return data.size();
  }

  //---------------------------------- CLEAR -------------------------------------
  template <class _Tp, class _Val>
  void Heap<_Tp,_Val>::clear()
  {
    data.clear();
    mapping.clear();
  }

  //---------------------------------- ERASE -------------------------------------
  template <class _Tp, class _Val>
  bool Heap<_Tp,_Val>::erase(_Tp& x)
  {
    std::map<_Tp,int>::iterator iter=mapping.find(x);
    if (iter==mapping.end())
      return false;
    if (data.size()==1)
      this->clear();
    else
    {
      int index=(*iter).second;
      data[index]=data.back();
      data.pop_back();
      mapping.erase(iter);
      percolate_down(index);
    }
    return true;
  }
  //------------------------------------------------------------------------------