#ifndef LIVERANGE_HPP
#define LIVERANGE_HPP

#include "BasicBlock.h"
#include "Function.h"
#include "Instruction.h"
#include "Module.h"
#include "Value.h"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

using std::map;
using std::pair;
using std::set;
using std::string;
using std::to_string;
using std::vector;

#define __LRA_PRINT__

namespace LRA {

struct Interval {
    Interval(int a = 0, int b = 0) : i(a), j(b) {}
    int i; // 0 means uninitialized
    int j;
};

using LiveSet = set<Value *>;
using PhiMap = map<BasicBlock *, vector<pair<Value *, Value *>>>;
using LiveInterval = pair<Interval, Value *>;

struct LiveIntervalCMP {
    bool operator()(LiveInterval const &lhs, LiveInterval const &rhs) const {
        if (lhs.first.i != rhs.first.i)
            return lhs.first.i < rhs.first.i;
        else
            return lhs.second < rhs.second;
    }
};

class LiveRangeAnalyzer {
  public:
    friend class CodeGen;

    LiveRangeAnalyzer(Module *m_, PhiMap &phi_map_)
        : m(m_), phi_map(phi_map_) {}
    LiveRangeAnalyzer() = delete;

    void run();
    void run(Function *);
    void clear();
    void print(Function *func, bool printSet = true);
    string print_liveSet(const LiveSet &ls) {
        string s = "[ ";
        for (auto k : ls)
            s += k->get_name() + " ";
        s += "]";
        return s;
    }
    string print_interval(Interval &i) {
        return "<" + to_string(i.i) + ", " + to_string(i.j) + ">";
    }

  private:
    Module *m;
    // Function *func;
    int ir_cnt;
    map<int, LiveSet> IN, OUT;
    map<Value *, int> instr_id;
    map<pair<Value *, Value *>, int> cpstmt_id;
    const PhiMap &phi_map;
    set<LiveInterval, LiveIntervalCMP> liveIntervals;

    void make_id(Function *);
    void make_interval(Function *);

    LiveSet joinFor(BasicBlock *bb);
    void union_ip(LiveSet &dest, LiveSet &src) {
        LiveSet res;
        set_union(dest.begin(),
                  dest.end(),
                  src.begin(),
                  src.end(),
                  std::inserter(res, res.begin()));
        dest = res;
    }
    // Require: out-set is already set
    // Return: the in-set(will not set IN-map)
    LiveSet transferFunction(Instruction *);
};
} // namespace LRA
#endif