#ifndef LIVERANGE_HPP
#define LIVERANGE_HPP

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

#include <iostream>
#include <map>
#include <set>
#include <vector>

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

#define UNINITIAL -1

#define __LRA_PRINT__
#define __USE_DFS_ORDER__

namespace LRA {

struct Interval {
    Interval(int a = UNINITIAL, int b = UNINITIAL) : 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;
    }
};
using LVITS = set<LiveInterval, LiveIntervalCMP>;

class LiveRangeAnalyzer {
    friend class CodeGen;

  public:
    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 = false,
               bool printInt = false) const;
    static string print_liveSet(const LiveSet &ls) {
        string s = "[ ";
        for (auto k : ls)
            s += k->get_name() + " ";
        s += "]";
        return s;
    }
    static string print_interval(const Interval &i) {
        return "<" + to_string(i.i) + ", " + to_string(i.j) + ">";
    }
    const LVITS &get() { return liveIntervals; }

  private:
    Module *m;
    // Function *func;
    int ir_cnt;
    vector<BasicBlock*> BB_DFS_Order;
    map<int, LiveSet> IN, OUT;
    map<Value *, int> instr_id;
    map<pair<Value *, Value *>, int> cpstmt_id;
    const PhiMap &phi_map;
    LVITS liveIntervals;
    map<Value *, Interval> intervalmap;

    void get_dfs_order(Function*);
    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 *);

  public:
    const decltype(instr_id) &get_instr_id() const { return instr_id; }
    const decltype(intervalmap) &get_interval_map() const {
        return intervalmap;
    }
    const decltype(IN) &get_in_set() const { return IN; }
    const decltype(OUT) &get_out_set() const { return OUT; }
};
} // namespace LRA
#endif