Untitled

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <math.h>
using namespace std;

struct Seg {
  long long a, b; // [a, b]
  string t; // tag
  Seg(long long a, long long b, string t) : a(a), b(b), t(t) { } // constructor
  bool operator<(const Seg &that) const { return a < that.a; }
};

std::set<Seg> myset;

// `s` has higher priority before all current segments in `myset`
void insert(Seg s) {
  // myset.lower_bound(x); // 找第一個 >= x的人
  // myset.upper_bound(x); // 找第一個 >  x的人
  // myset.upper_bound(25); // 找到第一個 a > 25 的人
  // prev(myset.upper_bound(25)); // 最後一個 a <= 25 的人
  auto it = myset.upper_bound(s); // 第一個 a > s.a 的人 // BST找東西log(n)
  if (it != myset.begin()) --it; // BST找prev也是worst case log(n), amortize O(1)
  int ctr = 0;
  while (it != myset.end()) { // n log n (執行n次insert，while加起來最多是5n圈)
    Seg cur = *it;
    ++it;
    if (!(s.b < cur.a || cur.b < s.a)) { // 代表有重疊
      myset.erase(cur);
      if (cur.a < s.a) { // 左邊有圖出來
        myset.emplace(cur.a, s.a-1, cur.t);
      }
      if (cur.b > s.b) { // 右邊有圖出來
        myset.emplace(s.b+1, cur.b, cur.t);
      }
    } else {
      if (++ctr == 2) break;
    }
  }
  myset.insert(s); // O(logn)
}


pair<long long, long long> toInt(string ip){
  const char* ip_char = ip.c_str();
  vector<int> v(4, 0);
  int v1, v2, v3, v4, mask;

  bool singleIP = false;
  if (ip.find('/') == string::npos){
    singleIP = true;
  }

  if(singleIP){
    sscanf(ip_char, "%d.%d.%d.%d", &v[0], &v[1], &v[2], &v[3]);

    long long a = 0;
    for(int i = 0; i < v.size(); i++){
      a *= 256;
      a += v[i];
    }
    cout << "insert or search (without mask) a = " << a << endl;

    return make_pair(a, a);
  } 

  sscanf(ip_char, "%d.%d.%d.%d/%d", &v[0], &v[1], &v[2], &v[3], &mask);

  long long a = 0;
  for(int i = 0; i < v.size(); i++){
    a *= 256;
    a += v[i];
  }
  cout << "original a = " << a << endl;

  long long bitMask = 255*256*256*256 + 255*256*256 + 255*256 + 255;
  a = a & (bitMask << (32 - mask));
  cout << "new a = " << a << endl;

  long long b = a + pow(2, 32-mask) - 1; // it is not guaranteed that a is the smallest !!!!!!!??????????

  return make_pair(a, b);
}

void changeFormat(string action, string ip) {
  pair<long long, long long> p = toInt(ip);
  cout << "changeFormat = " << p.first << " " << p.second << " " << action << endl;
  insert(Seg(p.first, p.second, action));
}


string search(string ip){
  pair<long long, long long> p = toInt(ip);
  long long query = p.first;
  Seg s = Seg(query, query, "SEARCH");

  auto it = myset.upper_bound(s); // 第一個 a > s.a 的人 // BST找東西log(n)
  if (it != myset.begin()) --it;

  return it->t;
}


int main() {
  vector<pair<string, string>> v;
  v.push_back(make_pair("ALLOW", "192.168.100.0/24"));
  v.push_back(make_pair("ALLOW", "192.168.0.5/30"));
  v.push_back(make_pair("DENY", "8.8.8.8/0"));
  v.push_back(make_pair("ALLOW", "1.2.3.4"));

  for(int i = v.size()-1; i >= 0; i--){
    changeFormat(v[i].first, v[i].second);
  }

  vector<string> queries;
  queries.push_back("192.168.100.1");
  queries.push_back("8.8.8.8");

  for(int i = 0; i < queries.size(); i++){
    string result = search(queries[i]);
    cout << "result = " << result << endl;
  }


}

/*
Time complexity:
this method -> O(n log n + m log n) = insert + search time

if direct -> O(n * m)

Problem:
the original ip might not be the smallest in the range!!! (Use bitMask to solve it)
What if the changeFormat has different input format??? (a == b when input is not CIDR)

*/