1 #if !defined HAVE_PARTITION_ODD_TO_DIST_H__
2 #define HAVE_PARTITION_ODD_TO_DIST_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 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 "sort/sort.h"
9 #include "perm/reverse.h"
10
11 #include "fxttypes.h"
12
13
partition_asc_odd_to_dist(const ulong * a,ulong ma,ulong * t)14 inline ulong partition_asc_odd_to_dist(const ulong *a, ulong ma, ulong *t)
15 // From the partition a[0,1,..,ma-1] into odd parts compute the
16 // corresponding partition t[0,1,...,mt-1] into distinct parts, as
17 // ascending list of parts. Return mt, the number of parts in t[].
18 // a[] only needs to have all identical parts consecutive.
19 {
20 if ( ma <= 1 )
21 {
22 if ( ma != 0 ) t[0] = a[0];
23 return ma;
24 }
25
26 ulong mt = 0;
27 ulong p = a[0]; // last part
28 ulong c = 1; // multiplicity of part
29 for (ulong j=1; j<ma; ++j)
30 {
31 ulong aj = a[j]; // current part;
32 if ( p == a[j] ) c += 1; // same part as last
33 else
34 {
35 do // write parts according to binary expansion of multiplicity c:
36 {
37 if ( (c & 1UL) != 0 ) t[mt++] = p;
38 p *= 2; c >>= 1;
39 }
40 while ( c != 0 );
41
42 p = aj;
43 c = 1;
44 }
45 }
46
47 do // write parts according to binary expansion of multiplicity c:
48 {
49 if ( (c & 1UL) != 0 ) t[mt++] = p;
50 p *= 2; c >>= 1;
51 }
52 while ( c != 0 );
53
54 selection_sort(t, mt);
55 return mt;
56 }
57 // -------------------------
58
59
partition_asc_dist_to_odd(const ulong * a,ulong ma,ulong * t)60 inline ulong partition_asc_dist_to_odd(const ulong *a, ulong ma, ulong *t)
61 // From the partition a[0,1,..,ma-1] into distinct parts compute the
62 // corresponding partition t[0,1,...,mt-1] into odd parts, as weakly
63 // increasing list of parts. Return mt, the number of parts in t[].
64 {
65 ulong mt = 0;
66 for (ulong j=0; j<ma; ++j)
67 {
68 ulong aj = a[j];
69 if ( (aj & 1UL) == 1 ) t[mt++] = aj; // odd part
70 else
71 {
72 ulong e = 0; // 2-valuation of aj
73 do { ++e; aj>>=1; } while ( (aj & 1UL) == 0 );
74 // make that 2**e parts aj / (2**e):
75 e = 1UL << e;
76 while ( e != 0 ) { t[mt++] = aj; --e; }
77 }
78 }
79
80 selection_sort(t, mt);
81 return mt;
82 }
83 // -------------------------
84
85
partition_desc_odd_to_dist(const ulong * a,ulong ma,ulong * t)86 inline ulong partition_desc_odd_to_dist(const ulong *a, ulong ma, ulong *t)
87 // From the partition a[0,1,..,ma-1] into odd parts compute the
88 // corresponding partition t[0,1,...,mt-1] into distinct parts, as
89 // descending list of parts. Return mt, the number of parts in t[].
90 // a[] only needs to have all identical parts consecutive.
91 {
92 ulong mt = partition_asc_odd_to_dist(a, ma, t);
93 reverse(t, mt);
94 return mt;
95 }
96 // -------------------------
97
98
partition_desc_dist_to_odd(const ulong * a,ulong ma,ulong * t)99 inline ulong partition_desc_dist_to_odd(const ulong *a, ulong ma, ulong *t)
100 // From the partition a[0,1,..,ma-1] into distinct parts compute the
101 // corresponding partition t[0,1,...,mt-1] into odd parts, as weakly
102 // decreasing list of parts. Return mt, the number of parts in t[].
103 {
104 ulong mt = partition_asc_dist_to_odd(a, ma, t);
105 reverse(t, mt);
106 return mt;
107 }
108 // -------------------------
109
110 #endif // !defined HAVE_PARTITION_ODD_TO_DIST_H__
111