https://github.com/ASchidler/coloring
Tip revision: dd03517187447fd44cfd9f03db6ab7313a21a64a authored by Andre Schidler on 14 March 2022, 12:24:58 UTC
Initial commit
Initial commit
Tip revision: dd03517
bucket_queue.h
//
// Created on 12.10.21.
//
#ifndef CPP_BUCKET_QUEUE_H
#define CPP_BUCKET_QUEUE_H
#include<vector>
#include<boost/dynamic_bitset.hpp>
#include "planarity.h"
using namespace std;
using namespace boost;
namespace planarity {
class BucketQueue {
private:
vector<dynamic_bitset<>> _queue;
vector<size_t> _values;
node_t _nodes;
size_t _cmin;
bool _increasing;
inline void verify() {
if (_increasing) {
while (_cmin < _queue.size() && !_queue[_cmin].any()) {
_cmin++;
}
} else {
while (_cmin > 0 && !_queue[_cmin].any()) {
_cmin--;
}
}
}
public:
explicit BucketQueue(node_t nodes, bool increasing=true) : _nodes(nodes), _cmin(increasing ? nodes : 0), _increasing(increasing), _values(nodes) {
_queue = vector<dynamic_bitset<>>();
_queue.reserve(nodes);
}
void add(size_t priority, node_t node) {
for (auto i = _queue.size(); i <= priority; i++)
_queue.emplace_back(_nodes);
if ((_increasing && priority < _cmin) || (!_increasing && priority > _cmin))
_cmin = priority;
_queue[priority][node] = true;
_values[node] = priority;
}
void change(size_t old, size_t modified, node_t node) {
for (auto i = _queue.size(); i <= modified; i++)
_queue.emplace_back(_nodes);
if ((_increasing && modified < _cmin) || (!_increasing && modified > _cmin))
_cmin = modified;
assert(_queue[old][node]);
_queue[old][node] = false;
_queue[modified][node] = true;
_values[node] = modified;
verify();
}
void change(size_t modified, node_t node) {
for (auto i = _queue.size(); i <= modified; i++)
_queue.emplace_back(_nodes);
if ((_increasing && modified < _cmin) || (!_increasing && modified > _cmin))
_cmin = modified;
assert(_queue[_values[node]][node]);
_queue[_values[node]][node] = false;
_queue[modified][node] = true;
_values[node] = modified;
verify();
}
tuple<size_t, node_t> next() {
auto new_node = _queue[_cmin].find_first();
_queue[_cmin][new_node] = false;
verify();
return tuple<size_t, int>(_cmin, new_node);
}
bool empty() {
return (_increasing && _cmin >= _queue.size()) || (!_increasing && _cmin == 0 && !_queue[0].any());
}
};
}
#endif //CPP_BUCKET_QUEUE_H