Streaming

[Hsue66]

define MAXLength (10000)

define MAXServer (10)

include

using namespace std;

int min(int a, int b) { if (a < b) return a; return b; } void swap(int &a, int &b) { int temp = a; if (a < b) { a = b; b = temp; } }

struct Pri { int id, dist; };

Pri buf[10]; void mergesort(Pri *p,int len) { if (len < 2) return; int i, j, k, mid; i = k = 0; j = mid = (len / 2);

mergesort(p, mid);
mergesort(p + mid, len - mid);

while (i < mid && j < len) {
    if (p[i].dist > p[j].dist)
        buf[k++] = p[i++];
    else if (p[i].dist == p[j].dist) {
        if(p[i].id > p[j].id)
            buf[k++] = p[i++];
        else
            buf[k++] = p[j++];
    }
    else
        buf[k++] = p[j++];
}
while(i<mid)
    buf[k++] = p[i++];
while(j<len)
    buf[k++] = p[j++];

for (int i = 0; i < len; i++)
    p[i] = buf[i];

}

struct Server { int capa, pos; };

Server S[MAXServer]; int numOfS; int Length; int Capa;

struct User { int Priority, id, sid,sidx; Pri sSeq[MAXServer]; User prev, next; };

struct List { User HEAD, TAIL; User user[MAXLength*2]; int numOfU;

User* alloc() {
    return &user[numOfU++];
}
void initU() {
    numOfU = 0;
    HEAD = alloc();
    HEAD->Priority = MAXLength + 1;
    TAIL = alloc();
    HEAD->next = TAIL;
    TAIL->prev = HEAD;
}

int pushU(int id, int axis) {
    User *nuw = alloc();
    nuw->id = id;
    nuw->sidx = numOfS-1;
    for (int i = 0; i < numOfS; i++) {
        int l = axis;
        int s = S[i].pos;
        swap(l, s);
        int t1 = l - s;
        int t2 = (Length - l) + s;
        nuw->sSeq[i].dist = min(t1, t2);
        nuw->sSeq[i].id = i;
    }
    mergesort(nuw->sSeq, numOfS);
    nuw->Priority = nuw->sSeq[0].dist;
    //for (int i = 0; i < numOfS; i++) {
    //  cout << nuw->sSeq[i].id << "," << nuw->sSeq[i].dist << " " ;
    //}
    // 연결하기
    User* it = TAIL->prev;
    for (; it != HEAD; it = it->prev) {
        if (it->Priority < nuw->Priority)
            S[it->sid].capa++;
        else {  // 정지&연결
            User *N = it->next;
            it->next = nuw;
            nuw->prev = it;
            N->prev = nuw;
            nuw->next = N;
            break;
        }
    }
    if (it == HEAD) {
        User *N = HEAD->next;
        HEAD->next = nuw;
        nuw->prev = HEAD;
        N->prev = nuw;
        nuw->next = N;
    }
    //감소시킨애들 다시 할당
    it = it->next;
    int res;
    for (; it != TAIL; it = it->next) { //현재 sid부터
        for (int i = it->sidx; i >= 0; i--) {
            int sid = it->sSeq[i].id;
            if (S[sid].capa > 0) {
                S[sid].capa--;
                it->sid = sid;
                it->sidx = i;
                break;
            }
        }
        if (it->id == id)
            res = it->sid;
    }
    //show();
    return res;
}

int removeU(int uid) {
    // 뒤에서 부터 찾기
    int res;
    User* it = TAIL->prev;
    for (; it != HEAD; it = it->prev) {
        if (it->id != uid) // 안 같을때
            S[it->sid].capa++;
        else {  //같을때 & 제거
            res = it->sid;
            S[it->sid].capa++;
            User *N = it->next;
            N->prev = it->prev;
            N->prev->next = N;
            it = N;
            break;
        }
    }
    //감소시킨애들 다시 할당
    for (; it != TAIL; it = it->next) { //현재 sid부터
        for (int i = numOfS-1; i >= 0; i--) {
            int sid = it->sSeq[i].id;
            if (S[sid].capa > 0) {
                S[sid].capa--;
                it->sid = sid;
                it->sidx = i;
                break;
            }
        }
    }
    //show();
    return res;
}

void show() {
    User* it = HEAD->next;
    for (; it != TAIL; it = it->next)
        cout << it->id <<","<< it->sid<<" ";
    cout << endl<<endl;
}

};

List user;

void init(int L, int N, int C, int axis[MAXServer]) { Length = L; Capa = C; numOfS = N; user.initU(); for (int i = 0; i < N; i++) { S[i].capa = C; S[i].pos = axis[i]; //cout << S[i].pos << " " << S[i].capa << endl; } } int add_user(int uid, int axis) { int res = user.pushU(uid,axis); return res; }

int remove_user(int uid) { int res = user.removeU(uid); return res; }

int get_users(int sid) { return Capa-S[sid].capa; }

void test() { cout << "HI" << endl; int d[3] = { 2,6,8 }; init(10, 3, 2, d); cout<<add_user(0, 2) << endl; cout << add_user(1, 2) << endl; cout << add_user(2, 1) << endl; cout << add_user(3, 0) << endl; cout << add_user(4, 0)<<endl; cout << remove_user(0) << endl; cout << remove_user(2) << endl; cout << get_users(1) << endl; }