Fiduccia-Mattheyses-algorithm/gain_container.h at main · leokondrashov/Fiduccia-Mattheyses-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#ifndef GAIN_CONTAINER_H
#define GAIN_CONTAINER_H

#include <list>
#include <ostream>
#include <vector>

#include "graph.h"

struct Move {
    int gain;
    unsigned cell;
    bool from, to;
};

class GainContainer {
public:
    GainContainer(unsigned max_gain, unsigned num_cells, bool lifo);

    void update_gain(unsigned cell, int value);
    void initialize_gain(const Graph& g);
    void lock_cell(unsigned i);
    bool empty() const { return num_locked == num_cells; }
    bool empty_bucket(bool partition) const { return current_max_gain[partition] < (int) -MAX_GAIN; }

    Move best_move(int disbalance, int max_disbalance) const;

    struct CellInfo {
        int gain;
        std::list<unsigned>::iterator it;
        bool locked;
        bool partition;
    };

    void dump(std::ostream& out) const;

private:
    void update_max_gain(int max_gain, bool partition);

    std::vector<std::list<unsigned>> buckets[2];
    std::vector<CellInfo> cells;
    const unsigned MAX_GAIN;
    int current_max_gain[2];

    auto& gain_bucket(bool part, int gain) { return buckets[part][gain + MAX_GAIN]; }
    const auto& gain_bucket(bool part, int gain) const
        { return buckets[part][gain + MAX_GAIN]; }

    unsigned num_cells;
    unsigned num_locked = 0;

    bool lifo;
};

#endif // GAIN_CONTAINER_H