Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.9 kB
0
Indexable
Never
#include <string>
#include <unordered_map>
#include <vector>
#define MAXL    (11)
#define SIZE 50000
#define HASH_SIZE 75007

using namespace std;

struct Species{
    int id;
    int rank;
    int child[5];
    int prev;
    //vector<int> next;

    Species(){
        rank = -1;
        for(int i = 0; i < 5; i++){
            child[i]  = 0;
        }
        prev = -1;
        //next.resize(0);
    }
} data[SIZE];

unordered_map<string, int> hashTable;
int index;

//int hashKey(char* str){
//    int index = 0;
//    while(*str != 0){
//        index = (index*31 + *str) % HASH_SIZE;
//        *str++;
//    }
//    
//    return index;
//}

void init(char mRootSpecies[MAXL])
{
    index = 0;
    hashTable = unordered_map<string, int>();
    for(int i = 0; i < SIZE; i++){
        data[i] = Species();
    }
    
    data[index].rank = 0;

    hashTable[ mRootSpecies] = index;
}

void add(char mSpecies[MAXL], char mParentSpecies[MAXL])
{
    index++;
    hashTable[mSpecies] = index;
    int idP = hashTable[mParentSpecies];
    

    data[index].rank = data[idP].rank + 1;
    data[index].prev = idP;
    //hashTable[idP].next.push_back(id);

    int tmpParent = index;
    for(int i = 1; i <= 4; i++){
        tmpParent = data[tmpParent].prev;
        if(tmpParent == -1) break;
        data[tmpParent].child[i]++;
    }
}

int findParent(int id1, int id2)
{
    if(id1 == id2)
        return id1;
    if(data[id1].prev == data[id2].prev){
        return data[id1].prev;
    }
    if(data[id1].rank > data[id2].rank){
        return findParent(data[id1].prev, id2);
    }
    if(data[id1].rank < data[id2].rank){
        return findParent(id1, data[id2].prev);
    }
    return findParent(data[id1].prev, data[id2].prev);
}

int getDistance(char mSpecies1[MAXL], char mSpecies2[MAXL])
{
    int cnt = 0;
    int id1 = hashTable[mSpecies1];
    int id2 = hashTable[mSpecies2];
    if(data[id1].rank == 0)
        return data[id2].rank;
    if(data[id2].rank == 0)
        return data[id1].rank;
    int idP = findParent(id1, id2);

    cnt = data[id1].rank - data[idP].rank + data[id2].rank - data[idP].rank;
    return cnt;
}

int getCount(char mSpecies[MAXL], int mDistance)
{
    int id = hashTable[mSpecies];
    int cnt =data[id].child[mDistance];

    if(data[id].rank == 0) return cnt;

    int curId = id;
    int prevId;
    int needCnt;
    for(int i = 1; i <= mDistance; i++){
        if(data[curId].rank == 0) break;

        prevId = data[curId].prev;
        needCnt = mDistance - i;

        if(needCnt == 0) cnt++;
        else if(needCnt == 1){
            cnt += data[prevId].child[needCnt] - 1;
        }
        else{
            cnt += data[prevId].child[needCnt] - data[curId].child[needCnt-1];
        }

        curId = prevId;
    }
    return cnt;
}