1 #if !defined HAVE_FIBREP_SUBSET_LEXREV_H__
2 #define HAVE_FIBREP_SUBSET_LEXREV_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2012, 2014 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8 #include "fxttypes.h"
9
next_subset_lexrev_fib(ulong x)10 static inline ulong next_subset_lexrev_fib(ulong x)
11 // Return next Fibonacci word in subset-lex order.
12 // Start with a one-bit word at position n-1 to
13 // generate all Fibonacci words of length n
14 // E.g., for n==6 the words (and subsets) are
15 // word subset of {0,1,2,3,4,5}
16 // 1: 1..... = { 0 }
17 // 2: 1.1... = { 0, 2 }
18 // 3: 1.1.1. = { 0, 2, 4 }
19 // 4: 1.1..1 = { 0, 2, 5 }
20 // 5: 1..1.. = { 0, 3 }
21 // 6: 1..1.1 = { 0, 3, 5 }
22 // 7: 1...1. = { 0, 4 }
23 // 8: 1....1 = { 0, 5 }
24 // 9: .1.... = { 1 }
25 // 10: .1.1.. = { 1, 3 }
26 // 11: .1.1.1 = { 1, 3, 5 }
27 // 12: .1..1. = { 1, 4 }
28 // 13: .1...1 = { 1, 5 }
29 // 14: ..1... = { 2 }
30 // 15: ..1.1. = { 2, 4 }
31 // 16: ..1..1 = { 2, 5 }
32 // 17: ...1.. = { 3 }
33 // 18: ...1.1 = { 3, 5 }
34 // 19: ....1. = { 4 }
35 // 20: .....1 = { 5 }
36 // 21: ...... = { }
37 //
38 // Note (1): the first element of the subset corresponds
39 // to the highest set bit.
40 // Note (2): the lex order for the delta sets would simply
41 // be the counting order.
42 {
43 ulong x0 = x & -x; // lowest bit
44 ulong xs = x0 >> 2;
45 if ( xs != 0 ) // easy case: set bit right of lowest bit
46 {
47 x |= xs;
48 return x;
49 }
50 else // lowest bit at index 0 or 1
51 {
52 if ( x0 == 2 ) // at index 1
53 {
54 x -= 1;
55 return x;
56 }
57
58 // Same as next_lexrev():
59 x ^= x0; // clear lowest bit
60 x0 = x & -x; // new lowest bit ...
61 x0 >>= 1; x -= x0; // ... is moved one to the right
62 return x;
63 }
64 }
65 // -------------------------
66
67
prev_subset_lexrev_fib(ulong x)68 static inline ulong prev_subset_lexrev_fib(ulong x)
69 // Return previous Fibonacci word in subset-lex order.
70 // Start with zero to generate all words of length n.
71 // E.g., for n==6:
72 // word subset of {0,1,2,3,4,5}
73 // 0: ...... = { }
74 // 1: .....1 = { 5 }
75 // 2: ....1. = { 4 }
76 // 3: ...1.1 = { 3, 5 }
77 // 4: ...1.. = { 3 }
78 // 5: ..1..1 = { 2, 5 }
79 // 6: ..1.1. = { 2, 4 }
80 // 7: ..1... = { 2 }
81 // 8: .1...1 = { 1, 5 }
82 // 9: .1..1. = { 1, 4 }
83 // 10: .1.1.1 = { 1, 3, 5 }
84 // 11: .1.1.. = { 1, 3 }
85 // 12: .1.... = { 1 }
86 // 13: 1....1 = { 0, 5 }
87 // 14: 1...1. = { 0, 4 }
88 // 15: 1..1.1 = { 0, 3, 5 }
89 // 16: 1..1.. = { 0, 3 }
90 // 17: 1.1..1 = { 0, 2, 5 }
91 // 18: 1.1.1. = { 0, 2, 4 }
92 // 19: 1.1... = { 0, 2 }
93 // 20: 1..... = { 0 }
94 //
95 {
96 ulong x0 = x & -x; // lowest bit
97 if ( x & (x0<<2) ) // easy case: next higher bit is set
98 {
99 x ^= x0; // clear lowest bit
100 return x;
101 }
102 else
103 {
104 x += x0; // move lowest bit to the left and
105 x |= (x0!=1); // set rightmost bit unless blocked by next bit
106 return x;
107 }
108 }
109 // -------------------------
110
111
112
113 #endif // !defined HAVE_FIBREP_SUBSET_LEXREV_H__
114