permutation: Generate permutations of arrays
[ccan] / ccan / permutation / test / api.c
1 #include "config.h"
2
3 #include <assert.h>
4 #include <string.h>
5 #include <stdint.h>
6 #include <inttypes.h>
7
8 #include <ccan/array_size/array_size.h>
9 #include <ccan/permutation/permutation.h>
10 #include <ccan/tap/tap.h>
11
12 #define MAX_ITEMS       10
13
14 #define PERMUTE(pi, arr)                                        \
15         do {                                                    \
16                 ok1(PERMUTATION_CHANGE_ARRAY((pi), (arr)));     \
17         } while (0)
18
19 #define CHECK_ORDER(a, t, ...)                                  \
20         do {                                                    \
21                 t cmp[] = { __VA_ARGS__ };                      \
22                 ok1(memcmp((a), cmp, sizeof(cmp)) == 0);        \
23         } while (0)
24
25 #define WORDLEN         6
26 typedef char word[WORDLEN];
27
28 int main(void)
29 {
30         struct permutation *pi;
31         int single = 12345;
32         char pair[] = { 'P', 'Q' };
33         uint16_t triple[] = {7, 9, 1000};
34         word four[] = {"ZERO", "ONE", "TWO", "THREE"};
35         int i;
36
37         plan_tests(2 * permutation_count(1) + 1
38                    + 2 * permutation_count(2) + 1
39                    + 2 * permutation_count(3) + 1
40                    + 2 * permutation_count(4) + 1
41                    + MAX_ITEMS + 1);
42
43         /* One */
44         pi = permutation_new(1);
45         CHECK_ORDER(&single, int, 12345);
46         ok1(!permutation_change_array(pi, &single, sizeof(single)));
47         CHECK_ORDER(&single, int, 12345);
48         free(pi);
49
50         /* Pair */
51         pi = PERMUTATION_NEW(pair);
52         CHECK_ORDER(pair, char, 'P', 'Q');
53         PERMUTE(pi, pair);
54         CHECK_ORDER(pair, char, 'Q', 'P');
55         ok1(!PERMUTATION_CHANGE_ARRAY(pi, pair));
56         CHECK_ORDER(pair, char, 'Q', 'P');
57         free(pi);
58
59         /* Triple */
60         pi = PERMUTATION_NEW(triple);
61         CHECK_ORDER(triple, uint16_t, 7, 9, 1000);
62         PERMUTE(pi, triple);
63         CHECK_ORDER(triple, uint16_t, 7, 1000, 9);
64         PERMUTE(pi, triple);
65         CHECK_ORDER(triple, uint16_t, 1000, 7, 9);
66         PERMUTE(pi, triple);
67         CHECK_ORDER(triple, uint16_t, 1000, 9, 7);
68         PERMUTE(pi, triple);
69         CHECK_ORDER(triple, uint16_t, 9, 1000, 7);
70         PERMUTE(pi, triple);
71         CHECK_ORDER(triple, uint16_t, 9, 7, 1000);
72         ok1(!PERMUTATION_CHANGE_ARRAY(pi, triple));
73         CHECK_ORDER(triple, uint16_t, 9, 7, 1000);
74         free(pi);
75
76         /* Four */
77         pi = PERMUTATION_NEW(four);
78         CHECK_ORDER(four, word, "ZERO", "ONE", "TWO", "THREE");
79         PERMUTE(pi, four);
80         CHECK_ORDER(four, word, "ZERO", "ONE", "THREE", "TWO");
81         PERMUTE(pi, four);
82         CHECK_ORDER(four, word, "ZERO", "THREE", "ONE", "TWO");
83         PERMUTE(pi, four);
84         CHECK_ORDER(four, word, "THREE", "ZERO", "ONE", "TWO");
85         PERMUTE(pi, four);
86         CHECK_ORDER(four, word, "THREE", "ZERO", "TWO", "ONE");
87         PERMUTE(pi, four);
88         CHECK_ORDER(four, word, "ZERO", "THREE", "TWO", "ONE");
89         PERMUTE(pi, four);
90         CHECK_ORDER(four, word, "ZERO", "TWO", "THREE", "ONE");
91         PERMUTE(pi, four);
92         CHECK_ORDER(four, word, "ZERO", "TWO", "ONE", "THREE");
93         PERMUTE(pi, four);
94         CHECK_ORDER(four, word, "TWO", "ZERO", "ONE", "THREE");
95         PERMUTE(pi, four);
96         CHECK_ORDER(four, word, "TWO", "ZERO", "THREE", "ONE");
97         PERMUTE(pi, four);
98         CHECK_ORDER(four, word, "TWO", "THREE", "ZERO", "ONE");
99         PERMUTE(pi, four);
100         CHECK_ORDER(four, word, "THREE", "TWO", "ZERO", "ONE");
101         PERMUTE(pi, four);
102         CHECK_ORDER(four, word, "THREE", "TWO", "ONE", "ZERO");
103         PERMUTE(pi, four);
104         CHECK_ORDER(four, word, "TWO", "THREE", "ONE", "ZERO");
105         PERMUTE(pi, four);
106         CHECK_ORDER(four, word, "TWO", "ONE", "THREE", "ZERO");
107         PERMUTE(pi, four);
108         CHECK_ORDER(four, word, "TWO", "ONE", "ZERO", "THREE");
109         PERMUTE(pi, four);
110         CHECK_ORDER(four, word, "ONE", "TWO", "ZERO", "THREE");
111         PERMUTE(pi, four);
112         CHECK_ORDER(four, word, "ONE", "TWO", "THREE", "ZERO");
113         PERMUTE(pi, four);
114         CHECK_ORDER(four, word, "ONE", "THREE", "TWO", "ZERO");
115         PERMUTE(pi, four);
116         CHECK_ORDER(four, word, "THREE", "ONE", "TWO", "ZERO");
117         PERMUTE(pi, four);
118         CHECK_ORDER(four, word, "THREE", "ONE", "ZERO", "TWO");
119         PERMUTE(pi, four);
120         CHECK_ORDER(four, word, "ONE", "THREE", "ZERO", "TWO");
121         PERMUTE(pi, four);
122         CHECK_ORDER(four, word, "ONE", "ZERO", "THREE", "TWO");
123         PERMUTE(pi, four);
124         CHECK_ORDER(four, word, "ONE", "ZERO", "TWO", "THREE");
125         ok1(!PERMUTATION_CHANGE_ARRAY(pi, four));
126         CHECK_ORDER(four, word, "ONE", "ZERO", "TWO", "THREE");
127         free(pi);
128
129         for (i = 0; i <= MAX_ITEMS; i++) {
130                 uint64_t nperms = 1;
131
132                 diag("Counting permutations of %d\n", i);
133
134                 pi = permutation_new(i);
135                 while (permutation_change(pi))
136                         nperms++;
137
138                 ok(nperms == permutation_count(i),
139                    "%"PRId64" permutations of %d (%d! == %lld)",
140                    nperms, i, i, permutation_count(i));
141                 free(pi);
142         }
143
144         /* This exits depending on whether all tests passed */
145
146         return exit_status();
147 }