Debian Codegraph @

libkmer/positionDB-sort.C

raw
1 #include "positionDB.H"
2 #include "bio++.H"
3
4
5 void
6 adjustHeap(uint64 *C,
7 uint64 *P, int64 i, int64 n) {
8 uint64 c = C[i];
9 uint64 p = P[i];
10 int64 j = (i << 1) + 1; // let j be the left child
11
12 while (j < n) {
13 if (j<n-1 && C[j] < C[j+1])
14 j++; // j is the larger child
15
16 if (c >= C[j]) // a position for M[i] has been found
17 break;
18
19 C[(j-1)/2] = C[j]; // Move larger child up a level
20 P[(j-1)/2] = P[j];
21
22 j = (j << 1) + 1;
23 }
24
25 C[(j-1)/2] = c;
26 P[(j-1)/2] = p;
27 }
28
29
30 void
31 positionDB::sortAndRepackBucket(uint64 b) {
32 uint64 st = _bucketSizes[b];
33 uint64 ed = _bucketSizes[b+1];
34 uint32 le = (uint32)(ed - st);
35
36 if (ed < st)
37 fprintf(stdout, "ERROR: Bucket "uint64FMT" starts at "uint64FMT" ends at "uint64FMT"?\n", b, st, ed);
38
39 if (le == 0)
40 return;
41
42 // One mer in the list? It's distinct and unique! (and doesn't
43 // contribute to the position list space count)
44 //
45 if (le == 1) {
46 _numberOfDistinct++;
47 _numberOfUnique++;
48 return;
49 }
50
51 // Allocate more space, if we need to.
52 //
53 if (_sortedMax <= le) {
54 _sortedMax = le + 1024;
55 delete [] _sortedChck;
56 delete [] _sortedPosn;
57 _sortedChck = new uint64 [_sortedMax];
58 _sortedPosn = new uint64 [_sortedMax];
59 }
60
61 // Unpack the bucket
62 //
63 uint64 lens[3] = {_chckWidth, _posnWidth, 1 + _sizeWidth};
64 uint64 vals[3] = {0};
65 for (uint64 i=st, J=st * _wCnt; i<ed; i++, J += _wCnt) {
66 getDecodedValues(_countingBuckets, J, 2, lens, vals);
67 _sortedChck[i-st] = vals[0];
68 _sortedPosn[i-st] = vals[1];
69 }
70
71 // Create the heap of lines.
72 //
73 int unsetBucket = 0;
74
75 for (int64 t=(le-2)/2; t>=0; t--) {
76 if (_sortedPosn[t] == uint64MASK(_posnWidth)) {
77 unsetBucket = 1;
78 fprintf(stdout, "ERROR: unset posn bucket="uint64FMT" t="int64FMT" le="uint32FMT"\n", b, t, le);
79 }
80
81 adjustHeap(_sortedChck, _sortedPosn, t, le);
82 }
83
84 if (unsetBucket)
85 for (uint32 t=0; t<le; t++)
86 fprintf(stdout, uint32FMTW(4)"] chck="uint64HEX" posn="uint64FMT"\n", t, _sortedChck[t], _sortedPosn[t]);
87
88 // Interchange the new maximum with the element at the end of the tree
89 //
90 for (int64 t=le-1; t>0; t--) {
91 uint64 tc = _sortedChck[t];
92 uint64 tp = _sortedPosn[t];
93
94 _sortedChck[t] = _sortedChck[0];
95 _sortedPosn[t] = _sortedPosn[0];
96
97 _sortedChck[0] = tc;
98 _sortedPosn[0] = tp;
99
100 adjustHeap(_sortedChck, _sortedPosn, 0, t);
101 }
102
103 // Scan the list of sorted mers, counting the number of distinct and unique,
104 // and the space needed in the position list.
105
106 uint64 entries = 1; // For t=0
107
108 for (uint32 t=1; t<le; t++) {
109 if (_sortedChck[t-1] > _sortedChck[t])
110 fprintf(stdout, "ERROR: bucket="uint64FMT" t="uint32FMT" le="uint32FMT": "uint64HEX" > "uint64HEX"\n",
111 b, t, le, _sortedChck[t-1], _sortedChck[t]);
112
113 if (_sortedChck[t-1] != _sortedChck[t]) {
114 _numberOfDistinct++;
115
116 if (_maximumEntries < entries)
117 _maximumEntries = entries;
118
119 if (entries == 1)
120 _numberOfUnique++;
121 else
122 _numberOfEntries += entries + 1; // +1 for the length
123
124 entries = 0;
125 }
126
127 entries++;
128 }
129
130 // Don't forget the last mer!
131 //
132 _numberOfDistinct++;
133 if (_maximumEntries < entries)
134 _maximumEntries = entries;
135 if (entries == 1)
136 _numberOfUnique++;
137 else
138 _numberOfEntries += entries + 1;
139
140
141 // Repack the sorted entries
142 //
143 for (uint64 i=st, J=st * _wCnt; i<ed; i++, J += _wCnt) {
144 vals[0] = _sortedChck[i-st];
145 vals[1] = _sortedPosn[i-st];
146 vals[2] = 0;
147 setDecodedValues(_countingBuckets, J, 3, lens, vals);
148 }
149 }
150