1 // This file is part of the FXT library.
2 // Copyright (C) 2010, 2012 Joerg Arndt
3 // License: GNU General Public License version 3 or later,
4 // see the file COPYING.txt in the main directory.
5
6 #include "bits/bitcount.h"
7 #include "bits/graycode.h"
8 //#include "bits/revgraycode.h"
9 #include "bits/bitlex.h"
10 #include "bits/revbin.h"
11 #include "bits/bitlow.h"
12 #include "bits/bithigh.h"
13 #include "bits/bitsequency.h"
14 #include "bits/bittransforms.h"
15
16 #include "fxttypes.h"
17
18 // ==================================
19 //
20 // The functions CF quickly lead to Gray codes
21 // for sizes P as follows:
22 //
23 // CF: P =
24 // 0: 3 5 7 11 13
25 // 1: 3 5 7 11 17 19
26 // 2: 3 5 7 11 13 17
27 // 3: 3 5 7 11 13 17 19 23
28 // 4: 3 5 7 11 13
29 // 5: 3 5 7 11 13 19 23
30 // 6: 3 5 7 11 13 17 19
31 // 7: 3 5 7 11 13 17 19 23 (29 31)
32 //
33 // ==================================
34
35 int
lyndon_cmp0(const ulong & a,const ulong & b)36 lyndon_cmp0(const ulong &a, const ulong &b)
37 {
38 int bc = bit_count_cmp(a, b);
39 if ( bc ) return -bc; // more bits first
40 else
41 {
42 if ( a==b ) return 0;
43 return (a>b ? +1 : -1); // greater numbers last
44 }
45 }
46 // -------------------------
47
48 int
lyndon_cmp1(const ulong & a,const ulong & b)49 lyndon_cmp1(const ulong &a, const ulong &b)
50 {
51 if ( a==b ) return 0;
52 #define CODE(x) gray_code(blue_code(x))
53 ulong ta = CODE(a), tb = CODE(b);
54 return ( ta<tb ? +1 : -1);
55 #undef CODE
56 }
57 // -------------------------
58
59 int
lyndon_cmp2(const ulong & a,const ulong & b)60 lyndon_cmp2(const ulong &a, const ulong &b)
61 {
62 if ( a==b ) return 0;
63 #define CODE(x) gray_code(x)
64 ulong ta = CODE(a), tb = CODE(b);
65 return ( ta<tb ? +1 : -1);
66 #undef CODE
67 }
68 // -------------------------
69
70 int
lyndon_cmp3(const ulong & a,const ulong & b)71 lyndon_cmp3(const ulong &a, const ulong &b)
72 {
73 if ( a==b ) return 0;
74 #define CODE(x) inverse_gray_code(x)
75 ulong ta = CODE(a), tb = CODE(b);
76 return ( ta<tb ? +1 : -1);
77 #undef CODE
78 }
79 // -------------------------
80
81 int
lyndon_cmp4(const ulong & a,const ulong & b)82 lyndon_cmp4(const ulong &a, const ulong &b)
83 {
84 if ( a==b ) return 0;
85 int bc = bit_count_cmp(a, b);
86 if ( bc ) return -bc;
87 #define CODE(x) inverse_gray_code( inverse_gray_code(x))
88 ulong ta = CODE(a), tb = CODE(b);
89 return ( ta<tb ? +1 : -1);
90 #undef CODE
91 }
92 // -------------------------
93
94 int
lyndon_cmp5(const ulong & a,const ulong & b)95 lyndon_cmp5(const ulong &a, const ulong &b)
96 {
97 if ( a==b ) return 0;
98 #define CODE(x) inverse_gray_code( inverse_gray_code(x) )
99 ulong ta = CODE(a), tb = CODE(b);
100 return ( ta<tb ? +1 : -1);
101 #undef CODE
102 }
103 // -------------------------
104
105 int
lyndon_cmp6(const ulong & a,const ulong & b)106 lyndon_cmp6(const ulong &a, const ulong &b)
107 {
108 if ( a==b ) return 0;
109 #define CODE(x) inverse_gray_code( negidx2lexrev(x) )
110 ulong ta = CODE(a), tb = CODE(b);
111 return ( ta<tb ? +1 : -1);
112 #undef CODE
113 }
114 // -------------------------
115
g21(ulong x)116 static inline ulong g21(ulong x)
117 // Gray code to the 21. power
118 {
119 x ^= x>>1; // gray ** 1
120 x ^= x>>4; // gray ** 4
121 x ^= x>>16; // gray ** 16
122 return x;
123 }
124 // -------------------------
125 // used for:
126 int
lyndon_cmp7(const ulong & a,const ulong & b)127 lyndon_cmp7(const ulong &a, const ulong &b)
128 {
129 if ( a==b ) return 0;
130 #define CODE(x) g21(x)
131 ulong ta = CODE(a), tb = CODE(b);
132 return ( ta<tb ? +1 : -1);
133 #undef CODE
134 }
135 // -------------------------
136