rehashed_heap.hpp

Go to the documentation of this file.

/*
 *
 *                   _/_/_/    _/_/   _/    _/ _/_/_/    _/_/
 *                  _/   _/ _/    _/ _/_/  _/ _/   _/ _/    _/
 *                 _/_/_/  _/_/_/_/ _/  _/_/ _/   _/ _/_/_/_/
 *                _/      _/    _/ _/    _/ _/   _/ _/    _/
 *               _/      _/    _/ _/    _/ _/_/_/  _/    _/
 *
 *             ***********************************************
 *                              PandA Project
 *                     URL: http://panda.dei.polimi.it
 *                       Politecnico di Milano - DEIB
 *                        System Architectures Group
 *             ***********************************************
 *              Copyright (C) 2004-2024 Politecnico di Milano
 *
 *   This file is part of the PandA framework.
 *
 *   The PandA framework is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program 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 General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#ifndef REHASHED_HEAP_HPP
#define REHASHED_HEAP_HPP

#include <algorithm>
#include <queue>
#include <vector>

#include "custom_map.hpp"
#include "graph.hpp"
#include "priority.hpp"
#include "refcount.hpp"



template <class _Type>
struct rehashed_heap : public std::priority_queue<vertex, std::vector<vertex>, priority_compare_functor<_Type>>
{
   rehashed_heap(const priority_compare_functor<_Type>& _comp)
       : std::priority_queue<vertex, std::vector<vertex>, priority_compare_functor<_Type>>(_comp)
   {
   }
   void rehash()
   {
      std::make_heap(std::priority_queue<vertex, std::vector<vertex>, priority_compare_functor<_Type>>::c.begin(),
                     std::priority_queue<vertex, std::vector<vertex>, priority_compare_functor<_Type>>::c.end(),
                     std::priority_queue<vertex, std::vector<vertex>, priority_compare_functor<_Type>>::comp);
   }

   std::vector<vertex>::const_iterator begin()
   {
      return rehashed_heap::c.begin();
   }
   std::vector<vertex>::const_iterator end()
   {
      return rehashed_heap::c.end();
   }
};

template <class _Type>
struct tree_rehashed_heap : public CustomUnorderedMap<vertex, std::vector<rehashed_heap<_Type>>>
{
   typename std::vector<rehashed_heap<_Type>>::iterator
   top(const CustomUnorderedMap<vertex, CustomOrderedSet<unsigned int>>& curren_black_list,
       const priority_data<_Type>& priority_functor, vertex& controlling_vertex, unsigned int& b_tag, bool& found)
   {
      found = false;
      typename std::vector<rehashed_heap<_Type>>::iterator res;
      typename tree_rehashed_heap::const_iterator it_end = this->end();
      for(typename tree_rehashed_heap::iterator it = this->begin(); it != it_end; ++it)
      {
         typename std::vector<rehashed_heap<_Type>>::const_iterator vit_end = it->second.end();
         unsigned int i = 0;
         bool cv_not_in_bl = curren_black_list.find(it->first) == curren_black_list.end();
         for(typename std::vector<rehashed_heap<_Type>>::iterator vit = it->second.begin(); vit != vit_end; ++vit, ++i)
         {
            if(!vit->empty() && (cv_not_in_bl || curren_black_list.find(it->first)->second.find(i) ==
                                                     curren_black_list.find(it->first)->second.end()))
            {
               if(!found)
               {
                  found = true;
                  res = vit;
                  controlling_vertex = it->first;
                  b_tag = i;
               }
               else if(priority_functor(vit->top()) > priority_functor(res->top()))
               {
                  res = vit;
                  controlling_vertex = it->first;
                  b_tag = i;
               }
            }
         }
      }
      return res;
   }

   void rehash()
   {
      typename tree_rehashed_heap::iterator it_end = this->end();
      for(typename tree_rehashed_heap::iterator it = this->begin(); it != it_end; ++it)
      {
         typename std::vector<rehashed_heap<_Type>>::iterator vit_end = it->second.end();
         for(typename std::vector<rehashed_heap<_Type>>::iterator vit = it->second.begin(); vit != vit_end; ++vit)
         {
            vit->rehash();
         }
      }
   }
};

#endif