DataStructure-In-C/WinnerTree.c at main · cwh555/DataStructure-In-C · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include "WinnerTree.h"

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>

//--dataStruct
struct winner{
    //list store in leaf
    LinkedList **data;
    int dataNum;

    int *tree;
    int treeSize;
};

//--end

//--helper
inline static int getlc(int index){
    return index * 2 + 1;
}

inline static int getrc(int index){
    return index * 2 + 2;
}

inline static int getparent(int index){
    return (index - 1) / 2;
}
//--end


WinnerTree *createWinnerTree(LinkedList **data, int num){
    WinnerTree *winner = (WinnerTree *)malloc(sizeof(WinnerTree));

    //complement num to the nearest 2^n
    winner->dataNum = 1;
    while(winner->dataNum < num)
        winner->dataNum *= 2;


    //init list in tree
    winner->data = (LinkedList **)malloc(sizeof(LinkedList *) * winner->dataNum);
    for(int i = 0; i < winner->dataNum; i++){
        if(i < num)
            winner->data[i] = data[i];
        else{
            //init a linked list with INTMAX(which will not affect result)
            winner->data[i] = initList();
            Element temp = {.key = INT32_MAX};
            addlistHead(winner->data[i], temp);
        }
    }

    //init tree
    winner->treeSize = winner->dataNum * 2 - 1;
    winner->tree = (int *)malloc(sizeof(int) * winner->treeSize);

    //init leaf
    int treeIndex = winner->treeSize - 1;
    for(int i = 0; i < winner->dataNum; i++, treeIndex--)
        winner->tree[treeIndex] = i;

    //init internal node
    for(; treeIndex >= 0; treeIndex--){
        int lcList = winner->tree[getlc(treeIndex)];
        int rcList = winner->tree[getrc(treeIndex)];

        if(getlistTop(winner->data[lcList]).key < getlistTop(winner->data[rcList]).key)
            winner->tree[treeIndex] = lcList;
        else
            winner->tree[treeIndex] = rcList;
    }

    return winner;
}

Element getWinnerTop(WinnerTree *winner){
    Element top = getlistTop(winner->data[winner->tree[0]]);
    if(top.key == INT32_MAX){
        fprintf(stderr, "winner tree is empty\n");
        exit(-1);
    }

    deletelistTop(winner->data[winner->tree[0]]);
    if(listEmpty(winner->data[winner->tree[0]])){
        Element temp = {.key = INT32_MAX};
        addlistHead(winner->data[winner->tree[0]], temp);
    }

    //update leaf
    int indexNow = winner->treeSize - 1 - winner->tree[0];
    while(indexNow != 0){
        indexNow = getparent(indexNow);

        int lcList= winner->tree[getlc(indexNow)];
        int rcList = winner->tree[getrc(indexNow)];

        if(getlistTop(winner->data[lcList]).key < getlistTop(winner->data[rcList]).key)
            winner->tree[indexNow] = lcList;
        else
            winner->tree[indexNow] = rcList;
    }

    return top;
}

bool WinnerEmpty(WinnerTree *winner){
    return getlistTop(winner->data[winner->tree[0]]).key == INT32_MAX;
}

void destroyWinner(WinnerTree *winner){
    for(int i = 0; i < winner->dataNum; i++)
        destroylist(winner->data[i]);

    free(winner->data);
    free(winner->tree);
    free(winner);

    return;
}