aboutsummaryrefslogtreecommitdiff
path: root/flatten_nested_iterator.c
blob: 57103a7548d7c64d2b6513b2c9116a0f27e229b9 (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
// 341. Flatten Nested List Iterator
#include <stdbool.h>
#include <stdlib.h>

/**
 * *********************************************************************
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * *********************************************************************
 *
 * // Return true if this NestedInteger holds a single integer, rather than a
 * nested list. bool NestedIntegerIsInteger(struct NestedInteger *);
 *
 * // Return the single integer that this NestedInteger holds, if it holds a
 * single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * int NestedIntegerGetInteger(struct NestedInteger *);
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested
 * list
 * // The result is undefined if this NestedInteger holds a single integer
 * struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);
 *
 * // Return the nested list's size that this NestedInteger holds, if it holds a
 * nested list
 * // The result is undefined if this NestedInteger holds a single integer
 * int NestedIntegerGetListSize(struct NestedInteger *);
 * };
 */

bool NestedIntegerIsInteger(struct NestedInteger *);
int NestedIntegerGetInteger(struct NestedInteger *);
struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);
int NestedIntegerGetListSize(struct NestedInteger *);

struct NestedIterator {
  int *list;
  int cur;
  int n;
};

void process(int *list, int *idx, struct NestedInteger *nestedList) {
  if (NestedIntegerIsInteger(nestedList)) {
    list[*idx] = NestedIntegerGetInteger(nestedList);
    *idx = *idx + 1;
    return;
  }
  struct NestedInteger **newNestedList = NestedIntegerGetList(nestedList);
  int newnestedListSize = NestedIntegerGetListSize(nestedList);
  for (int i = 0; i < newnestedListSize; i++) {
    process(list, idx, newNestedList[i]);
  }
}

struct NestedIterator *nestedIterCreate(struct NestedInteger **nestedList,
                                        int nestedListSize) {
  struct NestedIterator *ret =
      (struct NestedIterator *)malloc(sizeof(struct NestedIterator));
  ret->list = malloc(50000 * sizeof(int));
  int id = 0;
  for (int i = 0; i < nestedListSize; i++) {
    process(ret->list, &id, nestedList[i]);
  }
  ret->list = realloc(ret->list, id * sizeof(int));
  ret->cur = 0;
  ret->n = id;
  return ret;
}

bool nestedIterHasNext(struct NestedIterator *iter) {
  return ((iter->cur) < (iter->n));
}

int nestedIterNext(struct NestedIterator *iter) {
  return (iter->list[iter->cur++]);
}

void nestedIterFree(struct NestedIterator *iter) {
  free(iter->list);
  free(iter);
}