앱 관리

typedef struct Hash Hash;
const int LM = 102;
const int ALM = LM * LM;
const int TLM = 1 << 15;
const int MASK = TLM - 1;
int R, C, N; // N:테이블 길이
int idCnt, cur;
int tree[TLM + 5];
 
struct App {
    int id, runcnt;
    Hash* ptr;
    void setApp(int nid, int nr, Hash* np) {
        id = nid, runcnt = nr, ptr = np;
    }
    bool operator<(const App& r)const {
        if (id == 0 || r.id == 0) return id > r.id;
        if (runcnt != r.runcnt) return runcnt > r.runcnt;
        return id < r.id;
    }
}idList[ALM], trr[ALM];
 
int bcnt;
struct Hash {
    int appid, sn;
    Hash* prev, *next;
    void alloc(int nid, int nsn, Hash* p) {
        appid = nid, sn = nsn, prev = p, next = NULL;
        idList[sn].setApp(appid, 0, this), idCnt++;
        if (prev) next = prev->next, prev->next = this;
        if (next) next->prev = this;
    }
    void erase() {
        idList[sn].setApp(0, 0, NULL), idCnt--;
        if (prev) prev->next = next;
        if (next) next->prev = prev;
        prev = next = NULL;
    }
}buf[TLM * 10], htab[TLM];
 
void buildTree(int now, int s, int e) {
    if (s == e) {
        tree[now] = s;
        return;
    }
    int lch = now * 2, rch = lch + 1;
    int m = (s + e) / 2;
    buildTree(lch, s, m);
    buildTree(rch, m + 1, e);
    tree[now] = tree[lch];
}
 
void init(int row, int col) {
    R = row, C = col;
    N = row * col;
    buildTree(1, 0, N - 1);
    cur = 0;
    idCnt = 0;
    int i;
    for (i = 0; i < ALM; ++i) idList[i].setApp(0, 0, NULL);
    bcnt = 0;
    for (i = 0; i < TLM; ++i)
        htab[i].next = NULL;
}
 
Hash* probing(int hidx, int appid) {
    Hash* p = htab[hidx].next;
    for (; p; p = p->next) {
        if (p->appid == appid)
            return p;
    }
    return NULL;
}
 
inline int min(int a, int b) { return a < b ? a : b; }
int query(int now, int s, int e, int si, int ei) {
    if (e < si || ei < s) return TLM;
    if (si <= s && e <= ei) return tree[now];
    int lch = now * 2, rch = lch + 1, m = (s + e) / 2;
    int lv = query(lch, s, m, si, ei);
    int rv = query(rch, m + 1, e, si, ei);
    return min(lv, rv);
}
 
void update(int now, int s, int e, int tg, int w) {
    if (s == e) {
        tree[now] = w;
        return;
    }
    int lch = now * 2, rch = lch + 1, m = (s + e) / 2;
    if (tg <= m) update(lch, s, m, tg, w);
    else update(rch, m + 1, e, tg, w);
    tree[now] = min(tree[lch], tree[rch]);
}
 
int installApp(int appid) {
    /// 테이블에 빈 공간이 없는 경우
    if (idCnt == N) return 0;
    int hidx = appid & MASK;
    /// 이미 설치된 앱
    if (probing(hidx, appid)) return 0;
    /// 빈 공간 찾기
    int tg = query(1, 0, N - 1, cur, N - 1);
    if (tg == TLM) {
        tg = query(1, 0, N - 1, 0, cur - 1);
    }
    cur = tg;
    buf[bcnt++].alloc(appid, cur, htab + hidx);
    update(1, 0, N - 1, cur, TLM);
    return 1;
}
 
int uninstallApp() {
    if (idList[cur].id == 0) return 0;
    int ret = idList[cur].id;
    idList[cur].ptr->erase();
    update(1, 0, N - 1, cur, cur);
    return ret;
}
 
void moveDirection(int dir) {
    if (dir == 0) cur = (cur - C + N) % N;
    else if (dir == 1) {
        cur = (cur + C) % N;
    }
    else if (dir == 2) {
        cur = (cur - 1 + N) % N;
    }
    else if (dir == 3) {
        cur = (cur + 1) % N;
    }
}
 
int moveToApp(int appid) {
    int hidx = appid & MASK;
    Hash* p = probing(hidx, appid);
    if (p == NULL) return 0;
    cur = p->sn;
    return 1;
}
 
int runApp() {
    if (idList[cur].id == 0) return 0;
    idList[cur].runcnt++;
    return idList[cur].id;
}
 
void mergeSort(App* arr, int s, int e) {
    if (s >= e) return;
    int m = (s + e) / 2, i = s, j = m + 1, k = s;
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
    for (; k <= e; ++k) {
        if (i > m) trr[k] = arr[j++];
        else if (j > e) trr[k] = arr[i++];
        else if (arr[i] < arr[j])
            trr[k] = arr[i++];
        else trr[k] = arr[j++];
    }
    for (i = s; i <= e; ++i) arr[i] = trr[i];
}
 
void sortApp() {
    mergeSort(idList, 0, N - 1);
    buildTree(1, 0, N - 1);
    for (int i = 0; i < idCnt; ++i) {
        if (idList[i].ptr) {
            idList[i].ptr->sn = i;
            update(1, 0, N - 1, i, TLM);
        }
    }
    cur = 0;
}