aboutsummaryrefslogtreecommitdiff
path: root/sort_items_dependencies.c
blob: e8a03a6e4eca1d96b86d549bd2f66852a2acd019 (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
// 1203. Sort Items by Groups Respecting Dependencies
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * there are 'n' items in each belonging to zero or one of 'm' groups where
 * 'group[i]' is the group that the i'th item beglons to and it's equal to '-1'
 * if the i'th item beglongs to no group. the items and the groups are zero
 * indexed. a group can have no item belonging to it. return a sorted list of
 * the items such that
 * - the items that belong to the same group are next to each other in the
 * sorted list
 * - there are some relations between these items where 'beforeItems[i]' is a
 * list containing all the items that should come before the i'th item in the
 * sorted array (to the left of the i'th item) return any solution if there is
 * more than one solution and return an empty list if there is no solution.
 */

typedef enum {
  UnVisited,
  Exploring,
  Visited,
} Status;

typedef struct Node_t {
  Status status;
  int id;
  bool isVertex;
  struct AdjNode_t *next;
  struct AdjNode_t *adj;
} Node;

typedef struct AdjNode_t {
  Node *data;
  struct AdjNode_t *next;
} AdjNode;

void append_adj(Node *head, Node *data) {
  AdjNode *adj = head->adj;
  if (adj) {
    while (adj->next)
      adj = adj->next;
    adj->next = malloc(sizeof(AdjNode));
    memset(adj->next, 0, sizeof(AdjNode));
    adj->next->data = data;
  } else {
    head->adj = malloc(sizeof(AdjNode));
    memset(head->adj, 0, sizeof(AdjNode));
    head->adj->data = data;
  }
  return;
}

void append_next(Node *head, Node *data) {
  AdjNode *node = (AdjNode *)head->next;
  if (node) {
    while (node->next)
      node = node->next;
    node->next = malloc(sizeof(AdjNode));
    memset(node->next, 0, sizeof(AdjNode));
    node->next->data = data;
  } else {
    head->next = malloc(sizeof(AdjNode));
    memset(head->next, 0, sizeof(AdjNode));
    head->next->data = data;
  }
  return;
}

int N = 0;  // return size
int *R = 0; // return array

bool dfs(Node *node) {
  if (node == 0 || node->status == Visited)
    return true;
  else if (node->status == Exploring)
    return false;
  node->status = Exploring;

  AdjNode *next = node->next;
  while (next) {
    if (!dfs(next->data))
      return false;
    next = next->next;
  }
  if (!node->isVertex) {
    AdjNode *adj = node->adj;
    while (adj) {
      if (!dfs(adj->data))
        return false;
      adj = adj->next;
    }
  }
  if (node->isVertex)
    R[--N] = node->id;
  node->status = Visited;
  return true;
}

int *sortItems(int n, int m, int *group, int groupSize, int **beforeItems,
               int beforeItemsSize, int *beforeItemsColSize, int *returnSize) {
  R = malloc(sizeof(int) * n);
  N = n;
  Node items[n];
  memset(items, 0, sizeof(Node) * n);
  for (int i = 0; i < n; i++) {
    items[i].id = i;
    items[i].isVertex = true;
    if (group[i] == -1)
      group[i] = m++;
  }
  Node groupheads[m];
  memset(groupheads, 0, sizeof(Node) * m);
  for (int i = 0; i < n; i++) {
    append_adj(&(groupheads[group[i]]), &(items[i]));
    for (int j = 0; j < beforeItemsColSize[i]; j++) {
      int before = beforeItems[i][j];
      if (group[before] == group[i])
        append_next(&(items[before]), &(items[i]));
      else
        append_next(&(groupheads[group[before]]), &(groupheads[group[i]]));
    }
  }
  for (int i = 0; i < m; i++)
    if (!dfs(&(groupheads[i]))) {
      printf("\ncycle detected...\n");
      *returnSize = 0;
      return 0;
    }
  *returnSize = n;
  return R;
}