Debian Codegraph @

libkmer/merTable.H

raw
1 #ifndef MERTABLE_H
2 #define MERTABLE_H
3
4 // The obvious simple small mer table, appropriate for large sequences
5
6 #error merTable should be unused
7
8 class merTable {
9 public:
10 merTable() {
11 };
12 ~merTable() {
13 delete [] merToPositions;
14 delete [] positions;
15 };
16
17 void build(seqStream *CS, uint32 merSize, uint32 merSkip=0) {
18
19 // Allocate the mer table
20 //
21 uint32 tableSize = uint32ONE << (2*merSize);
22 fprintf(stderr, "allocate "uint32FMT" entries for a merTable.\n", tableSize);
23
24 merToPositions = new uint32 [tableSize+1];
25
26 // First pass, count the number of times we see each mer
27 //
28 for (uint32 i=0; i<=tableSize; i++)
29 merToPositions[i] = 0;
30
31 merStream MS(merSize, CS);
32
33 while (MS.nextMer(merSkip)) {
34 uint64 m = (uint64)MS.theFMer();
35 //fprintf(stderr, "add mer "uint64FMT"\n", m);
36 merToPositions[m]++;
37 }
38
39 // Convert those to indexes into positions - m[i] is the start of
40 // the locations in positions[] where positions are stored.
41 //
42 for (uint32 pos=0, val=0, i=0; i<=tableSize; i++) {
43 val = merToPositions[i];
44 merToPositions[i] = pos;
45 pos += val;
46 }
47
48 // Allocate space
49 //
50 fprintf(stderr, "allocate "uint32FMT" entries for positions\n", merToPositions[tableSize]);
51 positions = new uint32 [merToPositions[tableSize]];
52
53 // Second pass, fill in positions
54 //
55 MS.rewind();
56
57 while (MS.nextMer(merSkip))
58 positions[ merToPositions[(uint64)MS.theFMer()]++ ] = MS.thePositionInStream();
59 };
60
61 uint32 numberOfPositions(uint64 mer) {
62 return(merToPositions[mer+1] - merToPositions[mer]);
63 };
64
65 uint32 getPosition(uint64 mer, uint32 index) {
66 if (index >= merToPositions[mer+1] - merToPositions[mer])
67 return(~uint32ZERO);
68 return(merToPositions[mer] + index);
69 };
70
71 private:
72 uint32 *merToPositions; // index into positions[]; merToPositions[mer] is the first base in the mer
73 uint32 *positions; // list of positions for mers, sorted by mer
74 };
75
76 #endif // MERTABLE_H