| 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 |