aboutsummaryrefslogtreecommitdiff
path: root/all_o_one_data_structure.c
blob: bf76788c7433010e7235f7aa9d682876547841a9 (plain)
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// 432. All O`one Data Structure
#include "leetcode.h"

/*
 * design a data structure to store the strings' count with the ability to
 * return the strings with minimum and maximum counts. implement the 'allOne'
 * class. Note that each function must run in O(1) average time complexity
 */

struct data {
  char key[12];
  int val;
  void *next;
  void *above;
  void *below;
};

typedef struct {
  int table_size;
  struct data **hash_table;
  struct data *top;
  struct data *bottom;
} AllOne;

AllOne *allOneCreate() {
  AllOne *obj = (AllOne *)malloc(sizeof(AllOne));
  obj->table_size = 1024;
  obj->hash_table = calloc(sizeof(struct data), obj->table_size);
  obj->top = NULL;
  obj->bottom = NULL;
  return obj;
}

void allOneInc(AllOne *obj, char *key) {
  AllOne self = *obj;
  int hash = 0;
  for (int i = 0; i < strlen(key); i++)
    hash += key[i];
  hash %= self.table_size;
  struct data *check = self.hash_table[hash];
  while (check) {
    if (!strcmp(key, check->key)) {
      struct data *whirl = check->above;
      while (whirl && check->val > whirl->val) {
        if (check->below)
          ((struct data *)(check->below))->above = whirl;
        if (whirl->above)
          ((struct data *)(whirl->above))->below = check;
        whirl->below = check->below;
        check->above = whirl->above;
        check->below = (void *)whirl;
        whirl->above = (void *)check;
        whirl = (struct data *)check->above;
        if (self.bottom == check)
          self.bottom = check->below;
      }
      if (!whirl)
        self.top = check;
      *obj = self;
      return;
    }
    check = check->next;
  }
  struct data *new = (struct data *)malloc(sizeof(struct data));
  strcpy(new->key, key);
  new->val = 1;
  new->next = (void *)self.hash_table[hash];
  self.hash_table[hash] = new;
  if (!self.top)
    self.top = new;
  new->below = NULL;
  new->above = self.bottom;
  if (self.bottom)
    self.bottom->below = new;
  self.bottom = new;
  *obj = self;
}

void allOneDec(AllOne *obj, char *key) {
  AllOne self = *obj;
  int hash = 0;
  for (int i = 0; i < strlen(key); i++)
    hash += key[i];
  hash %= self.table_size;
  struct data *old_check = NULL, *check = self.hash_table[hash];
  while (check) {
    if (!strcmp(key, check->key)) {
      if (!check->val) {
        if (!old_check)
          self.hash_table[hash] = check->next;
        else
          old_check->next = check->next;
        if (check == self.top)
          self.top = check->below;
        if (check == self.bottom)
          self.bottom = check->above;
        if (check->above)
          ((struct data *)(check->below))->above = check->above;
        free(check);
        *obj = self;
        return;
      }
      struct data *whirl = (struct data *)check->below;
      while (whirl && check->val < whirl->val) {
        if (check->above)
          ((struct data *)(check->above))->below = whirl;
        if (whirl->below)
          ((struct data *)(whirl->below))->above = check;
        whirl->above = check->above;
        check->below = whirl->below;
        check->above = (void *)whirl;
        whirl->below = (void *)check;
        whirl = (struct data *)check->below;
        if (self.top == check)
          self.top = check->above;
      }
      if (!whirl)
        self.bottom = check;
      *obj = self;
      return;
    }
    old_check = check;
    check = check->next;
  }
  return;
}

char *allOneGetMaxKey(AllOne *obj) {
  if (!obj->top)
    return "";
  return obj->top->key;
}

char *allOneGetMinKey(AllOne *obj) {
  if (!obj->bottom)
    return "";
  return obj->bottom->key;
}

void allOneFree(AllOne *obj) {
  AllOne self = *obj;
  for (int i = 0; i < self.table_size; i++) {
    struct data *old_check, *check = self.hash_table[i];
    while (check) {
      old_check = check;
      check = check->next;
      free(old_check);
    }
  }
  free(self.hash_table);
  free(obj);
}

int main() {
  AllOne *obj = allOneCreate();
  char *k1 = "hello", *k2 = "hello", *k3 = "leet";
  allOneInc(obj, k1);
  allOneInc(obj, k2);
  printf("%s\n", allOneGetMaxKey(obj)); // expect: hello
  printf("%s\n", allOneGetMinKey(obj)); // expect: hello
  allOneInc(obj, k3);
  printf("%s\n", allOneGetMaxKey(obj)); // expect: hello
  printf("%s\n", allOneGetMinKey(obj)); // expect: leet
  allOneFree(obj);
}