#include "graph.hpp"

#include <algorithm>

#include <iostream>

#include <random>

#include <vector>

template <typename RNG>

bool erasedConfigurationModel(DegreeSequence &ds, Graph &g, RNG &rng) {

    // List of all half-edges

    std::vector<unsigned int> halfEdges;

    for (unsigned int i = 0; i < ds.size(); ++i)

        halfEdges.insert(halfEdges.end(), ds[i], i);

    // Clear the graph

    g.reset(ds.size());

    if (halfEdges.size() % 2 != 0)

        return false;

    std::shuffle(halfEdges.begin(), halfEdges.end(), rng);

    // pair halfEdges[2*i] with halfEdges[2*i+1]

    for (auto iter = halfEdges.begin(); iter != halfEdges.end();) {

        auto u = *iter++;

        auto v = *iter++;

        if (u != v)

            g.addEdge({u, v}); // checks for double edges

    }

    return true;

}

#pragma once

#include "exports.hpp"

#include <algorithm>

#include <vector>

// Histogram over integers with binsize 1

class Histogram {

  public:

    Histogram() : xmin(0) {}

    ~Histogram() {}

    void reset() {

        frequencies.clear();

        xmin = 0;

    }

    void add(int sample) {

        if (frequencies.empty()) {

            xmin = sample;

            frequencies.push_back(1);

            return;

        }

        if (sample < xmin) {

            int extra = xmin - sample;

            frequencies.insert(frequencies.begin(), extra, 0);

            xmin = sample;

            frequencies.front()++;

            return;

        }

        if (sample - xmin >= (int)frequencies.size()) {

            int extra = sample - xmin - frequencies.size() + 1;

            frequencies.insert(frequencies.end(), extra, 0);

            frequencies.back()++;

            return;

        }

        frequencies[sample - xmin]++;

    }

    // For exports

    std::vector<std::pair<int, int>> getHistogram() const {

        std::vector<std::pair<int, int>> histogram;

        int i = xmin;

        for (auto f : frequencies)

            histogram.push_back({i++, f});

        return histogram;

    }

    std::vector<int> frequencies;

    int xmin;

};