]> git.donarmstrong.com Git - bamtools.git/blob - src/api/internal/BamToolsIndex_p.cpp
1142fbdbd0db958e7dab476c74ead9b5e3c3c06f
[bamtools.git] / src / api / internal / BamToolsIndex_p.cpp
1 // ***************************************************************************
2 // BamToolsIndex.cpp (c) 2010 Derek Barnett
3 // Marth Lab, Department of Biology, Boston College
4 // ---------------------------------------------------------------------------
5 // Last modified: 8 October 2011 (DB)
6 // ---------------------------------------------------------------------------
7 // Provides index operations for the BamTools index format (".bti")
8 // ***************************************************************************
9
10 #include <api/BamAlignment.h>
11 #include <api/internal/BamException_p.h>
12 #include <api/internal/BamReader_p.h>
13 #include <api/internal/BamToolsIndex_p.h>
14 #include <api/internal/BgzfStream_p.h>
15 using namespace BamTools;
16 using namespace BamTools::Internal;
17
18 #include <cstdio>
19 #include <cstdlib>
20 #include <cstring>
21 #include <algorithm>
22 #include <iostream>
23 #include <iterator>
24 #include <map>
25 using namespace std;
26
27 // --------------------------------
28 // static BamToolsIndex constants
29 // --------------------------------
30
31 const uint32_t BamToolsIndex::DEFAULT_BLOCK_LENGTH = 1000;
32 const string BamToolsIndex::BTI_EXTENSION     = ".bti";
33 const char* const BamToolsIndex::BTI_MAGIC    = "BTI\1";
34 const int BamToolsIndex::SIZEOF_BLOCK         = sizeof(int32_t)*2 + sizeof(int64_t);
35
36 // ----------------------------
37 // RaiiWrapper implementation
38 // ----------------------------
39
40 BamToolsIndex::RaiiWrapper::RaiiWrapper(void)
41     : IndexStream(0)
42 { }
43
44 BamToolsIndex::RaiiWrapper::~RaiiWrapper(void) {
45     if ( IndexStream )
46         fclose(IndexStream);
47 }
48
49 // ------------------------------
50 // BamToolsIndex implementation
51 // ------------------------------
52
53 // ctor
54 BamToolsIndex::BamToolsIndex(Internal::BamReaderPrivate* reader)
55     : BamIndex(reader)
56     , m_cacheMode(BamIndex::LimitedIndexCaching)
57     , m_blockSize(BamToolsIndex::DEFAULT_BLOCK_LENGTH)
58     , m_inputVersion(0)
59     , m_outputVersion(BTI_2_0) // latest version - used for writing new index files
60 {
61     m_isBigEndian = BamTools::SystemIsBigEndian();
62 }
63
64 // dtor
65 BamToolsIndex::~BamToolsIndex(void) {
66     CloseFile();
67 }
68
69 void BamToolsIndex::CheckMagicNumber(void) {
70
71     // read magic number
72     char magic[4];
73     size_t elementsRead = fread(magic, sizeof(char), 4, Resources.IndexStream);
74     if ( elementsRead != 4 )
75         throw BamException("BamToolsIndex::CheckMagicNumber", "could not read BTI magic number");
76
77     // validate expected magic number
78     if ( strncmp(magic, BamToolsIndex::BTI_MAGIC, 4) != 0 )
79         throw BamException("BamToolsIndex::CheckMagicNumber", "invalid BTI magic number");
80 }
81
82 // check index file version, return true if OK
83 void BamToolsIndex::CheckVersion(void) {
84
85     // read version from file
86     size_t elementsRead = fread(&m_inputVersion, sizeof(m_inputVersion), 1, Resources.IndexStream);
87     if ( elementsRead != 1 )
88         throw BamException("BamToolsIndex::CheckVersion", "could not read format version");
89     if ( m_isBigEndian ) SwapEndian_32(m_inputVersion);
90
91     // if version is negative, or zero
92     if ( m_inputVersion <= 0 )
93         throw BamException("BamToolsIndex::CheckVersion", "invalid format version");
94
95     // if version is newer than can be supported by this version of bamtools
96     else if ( m_inputVersion > m_outputVersion ) {
97         const string message = "unsupported format: this index was created by a newer version of BamTools. "
98                                "Update your local version of BamTools to use the index file.";
99         throw BamException("BamToolsIndex::CheckVersion", message);
100     }
101
102     // ------------------------------------------------------------------
103     // check for deprecated, unsupported versions
104     // (the format had to be modified to accomodate a particular bug fix)
105
106     // Version 2.0: introduced support for half-open intervals, instead of the old closed intervals
107     //   respondBy: throwing exception - we're not going to try to handle the old BTI files.
108     else if ( (Version)m_inputVersion < BamToolsIndex::BTI_2_0 ) {
109         const string message = "unsupported format: this version of the index may not properly handle "
110                                "coordinate intervals. Please run 'bamtools index -bti -in yourData.bam' "
111                                "to generate an up-to-date, fixed BTI file.";
112         throw BamException("BamToolsIndex::CheckVersion", message);
113     }
114 }
115
116 void BamToolsIndex::ClearReferenceEntry(BtiReferenceEntry& refEntry) {
117     refEntry.ID = -1;
118     refEntry.Blocks.clear();
119 }
120
121 void BamToolsIndex::CloseFile(void) {
122     if ( IsFileOpen() ) {
123         fclose(Resources.IndexStream);
124         Resources.IndexStream = 0;
125     }
126     m_indexFileSummary.clear();
127 }
128
129 // builds index from associated BAM file & writes out to index file
130 bool BamToolsIndex::Create(void) {
131
132     // skip if BamReader is invalid or not open
133     if ( m_reader == 0 || !m_reader->IsOpen() ) {
134         SetErrorString("BamToolsIndex::Create", "could not create index: reader is not open");
135         return false;
136     }
137
138     // rewind BamReader
139     if ( !m_reader->Rewind() ) {
140         const string readerError = m_reader->GetErrorString();
141         const string message = "could not create index: \n\t" + readerError;
142         SetErrorString("BamToolsIndex::Create", message);
143         return false;
144     }
145
146     try {
147         // open new index file (read & write)
148         const string indexFilename = m_reader->Filename() + Extension();
149         OpenFile(indexFilename, "w+b");
150
151         // initialize BtiFileSummary with number of references
152         const int& numReferences = m_reader->GetReferenceCount();
153         InitializeFileSummary(numReferences);
154
155         // intialize output file header
156         WriteHeader();
157
158         // index building markers
159         uint32_t currentBlockCount      = 0;
160         int64_t currentAlignmentOffset  = m_reader->Tell();
161         int32_t blockRefId              = -1;
162         int32_t blockMaxEndPosition     = -1;
163         int64_t blockStartOffset        = currentAlignmentOffset;
164         int32_t blockStartPosition      = -1;
165
166         // plow through alignments, storing index entries
167         BamAlignment al;
168         BtiReferenceEntry refEntry;
169         while ( m_reader->LoadNextAlignment(al) ) {
170
171             // if moved to new reference
172             if ( al.RefID != blockRefId ) {
173
174                 // if first pass, check:
175                 if ( currentBlockCount == 0 ) {
176
177                     // write any empty references up to (but not including) al.RefID
178                     for ( int i = 0; i < al.RefID; ++i )
179                         WriteReferenceEntry( BtiReferenceEntry(i) );
180                 }
181
182                 // not first pass:
183                 else {
184
185                     // store previous BTI block data in reference entry
186                     const BtiBlock block(blockMaxEndPosition, blockStartOffset, blockStartPosition);
187                     refEntry.Blocks.push_back(block);
188
189                     // write reference entry, then clear
190                     WriteReferenceEntry(refEntry);
191                     ClearReferenceEntry(refEntry);
192
193                     // write any empty references between (but not including)
194                     // the last blockRefID and current al.RefID
195                     for ( int i = blockRefId+1; i < al.RefID; ++i )
196                         WriteReferenceEntry( BtiReferenceEntry(i) );
197
198                     // reset block count
199                     currentBlockCount = 0;
200                 }
201
202                 // set ID for new reference entry
203                 refEntry.ID = al.RefID;
204             }
205
206             // if beginning of block, update counters
207             if ( currentBlockCount == 0 ) {
208                 blockRefId          = al.RefID;
209                 blockStartOffset    = currentAlignmentOffset;
210                 blockStartPosition  = al.Position;
211                 blockMaxEndPosition = al.GetEndPosition();
212             }
213
214             // increment block counter
215             ++currentBlockCount;
216
217             // check end position
218             const int32_t alignmentEndPosition = al.GetEndPosition();
219             if ( alignmentEndPosition > blockMaxEndPosition )
220                 blockMaxEndPosition = alignmentEndPosition;
221
222             // if block is full, get offset for next block, reset currentBlockCount
223             if ( currentBlockCount == m_blockSize ) {
224
225                 // store previous block data in reference entry
226                 const BtiBlock block(blockMaxEndPosition, blockStartOffset, blockStartPosition);
227                 refEntry.Blocks.push_back(block);
228
229                 // update markers
230                 blockStartOffset  = m_reader->Tell();
231                 currentBlockCount = 0;
232             }
233
234             // not the best name, but for the next iteration, this value will be the offset of the
235             // *current* alignment. this is necessary because we won't know if this next alignment
236             // is on a new reference until we actually read it
237             currentAlignmentOffset = m_reader->Tell();
238         }
239
240         // after finishing alignments, if any data was read, check:
241         if ( blockRefId >= 0 ) {
242
243             // store last BTI block data in reference entry
244             const BtiBlock block(blockMaxEndPosition, blockStartOffset, blockStartPosition);
245             refEntry.Blocks.push_back(block);
246
247             // write last reference entry, then clear
248             WriteReferenceEntry(refEntry);
249             ClearReferenceEntry(refEntry);
250
251             // then write any empty references remaining at end of file
252             for ( int i = blockRefId+1; i < numReferences; ++i )
253                 WriteReferenceEntry( BtiReferenceEntry(i) );
254         }
255
256     } catch ( BamException& e ) {
257         m_errorString = e.what();
258         return false;
259     }
260
261     // rewind BamReader
262     if ( !m_reader->Rewind() ) {
263         const string readerError = m_reader->GetErrorString();
264         const string message = "could not create index: \n\t" + readerError;
265         SetErrorString("BamToolsIndex::Create", message);
266         return false;
267     }
268
269     // return success
270     return true;
271 }
272
273 // returns format's file extension
274 const std::string BamToolsIndex::Extension(void) {
275     return BamToolsIndex::BTI_EXTENSION;
276 }
277
278 void BamToolsIndex::GetOffset(const BamRegion& region, int64_t& offset, bool* hasAlignmentsInRegion) {
279
280     // return false ref ID is not a valid index in file summary data
281     if ( region.LeftRefID < 0 || region.LeftRefID >= (int)m_indexFileSummary.size() )
282         throw BamException("BamToolsIndex::GetOffset", "invalid region requested");
283
284     // retrieve reference index data for left bound reference
285     BtiReferenceEntry refEntry(region.LeftRefID);
286     ReadReferenceEntry(refEntry);
287
288     // binary search for an overlapping block (may not be first one though)
289     bool found = false;
290     typedef BtiBlockVector::const_iterator BtiBlockConstIterator;
291     BtiBlockConstIterator blockFirst = refEntry.Blocks.begin();
292     BtiBlockConstIterator blockIter  = blockFirst;
293     BtiBlockConstIterator blockLast  = refEntry.Blocks.end();
294     iterator_traits<BtiBlockConstIterator>::difference_type count = distance(blockFirst, blockLast);
295     iterator_traits<BtiBlockConstIterator>::difference_type step;
296     while ( count > 0 ) {
297         blockIter = blockFirst;
298         step = count/2;
299         advance(blockIter, step);
300
301         const BtiBlock& block = (*blockIter);
302         if ( block.StartPosition <= region.RightPosition ) {
303             if ( block.MaxEndPosition > region.LeftPosition ) {
304                 offset = block.StartOffset;
305                 break;
306             }
307             blockFirst = ++blockIter;
308             count -= step+1;
309         }
310         else count = step;
311     }
312
313     // if we didn't search "off the end" of the blocks
314     if ( blockIter != blockLast ) {
315
316         // "walk back" until we've gone too far
317         while ( blockIter != blockFirst ) {
318             const BtiBlock& currentBlock = (*blockIter);
319
320             --blockIter;
321             const BtiBlock& previousBlock = (*blockIter);
322             if ( previousBlock.MaxEndPosition <= region.LeftPosition ) {
323                 offset = currentBlock.StartOffset;
324                 found = true;
325                 break;
326             }
327         }
328
329         // if we walked all the way to first block, just return that and let the reader's
330         // region overlap parsing do the rest
331         if ( blockIter == blockFirst ) {
332             const BtiBlock& block = (*blockIter);
333             offset = block.StartOffset;
334             found = true;
335         }
336     }
337
338
339     // sets to false if blocks container is empty, or if no matching block could be found
340     *hasAlignmentsInRegion = found;
341 }
342
343 // returns whether reference has alignments or no
344 bool BamToolsIndex::HasAlignments(const int& referenceID) const {
345     if ( referenceID < 0 || referenceID >= (int)m_indexFileSummary.size() )
346         return false;
347     const BtiReferenceSummary& refSummary = m_indexFileSummary.at(referenceID);
348     return ( refSummary.NumBlocks > 0 );
349 }
350
351 // pre-allocates space for each reference's summary data
352 void BamToolsIndex::InitializeFileSummary(const int& numReferences) {
353     m_indexFileSummary.clear();
354     for ( int i = 0; i < numReferences; ++i )
355         m_indexFileSummary.push_back( BtiReferenceSummary() );
356 }
357
358 // returns true if the index stream is open
359 bool BamToolsIndex::IsFileOpen(void) const {
360     return ( Resources.IndexStream != 0 );
361 }
362
363 // attempts to use index data to jump to @region, returns success/fail
364 // a "successful" jump indicates no error, but not whether this region has data
365 //   * thus, the method sets a flag to indicate whether there are alignments
366 //     available after the jump position
367 bool BamToolsIndex::Jump(const BamTools::BamRegion& region, bool* hasAlignmentsInRegion) {
368
369     // clear flag
370     *hasAlignmentsInRegion = false;
371
372     // skip if invalid reader or not open
373     if ( m_reader == 0 || !m_reader->IsOpen() ) {
374         SetErrorString("BamToolsIndex::Jump", "could not jump: reader is not open");
375         return false;
376     }
377
378     // make sure left-bound position is valid
379     const RefVector& references = m_reader->GetReferenceData();
380     if ( region.LeftPosition > references.at(region.LeftRefID).RefLength ) {
381         SetErrorString("BamToolsIndex::Jump", "could not create index: invalid region requested");
382         return false;
383     }
384
385     // calculate nearest offset to jump to
386     int64_t offset;
387     try {
388         GetOffset(region, offset, hasAlignmentsInRegion);
389     } catch ( BamException& e ) {
390         m_errorString = e.what();
391         return false;
392     }
393
394     // return success/failure of seek
395     return m_reader->Seek(offset);
396 }
397
398 // loads existing data from file into memory
399 bool BamToolsIndex::Load(const std::string& filename) {
400
401     try {
402
403         // attempt to open file (read-only)
404         OpenFile(filename, "rb");
405
406         // load metadata & generate in-memory summary
407         LoadHeader();
408         LoadFileSummary();
409
410         // return success
411         return true;
412
413     } catch ( BamException& e ) {
414         m_errorString = e.what();
415         return false;
416     }
417 }
418
419 void BamToolsIndex::LoadFileSummary(void) {
420
421     // load number of reference sequences
422     int numReferences;
423     LoadNumReferences(numReferences);
424
425     // initialize file summary data
426     InitializeFileSummary(numReferences);
427
428     // load summary for each reference
429     BtiFileSummary::iterator summaryIter = m_indexFileSummary.begin();
430     BtiFileSummary::iterator summaryEnd  = m_indexFileSummary.end();
431     for ( ; summaryIter != summaryEnd; ++summaryIter )
432         LoadReferenceSummary(*summaryIter);
433 }
434
435 void BamToolsIndex::LoadHeader(void) {
436
437     // check BTI file metadata
438     CheckMagicNumber();
439     CheckVersion();
440
441     // use file's BTI block size to set member variable
442     const size_t elementsRead = fread(&m_blockSize, sizeof(m_blockSize), 1, Resources.IndexStream);
443     if ( m_isBigEndian ) SwapEndian_32(m_blockSize);
444     if ( elementsRead != 1 )
445         throw BamException("BamToolsIndex::LoadHeader", "could not read BTI block size");
446 }
447
448 void BamToolsIndex::LoadNumBlocks(int& numBlocks) {
449     const size_t elementsRead = fread(&numBlocks, sizeof(numBlocks), 1, Resources.IndexStream);
450     if ( m_isBigEndian ) SwapEndian_32(numBlocks);
451     if ( elementsRead != 1 )
452         throw BamException("BamToolsIndex::LoadNumBlocks", "could not read number of BTI blocks");
453 }
454
455 void BamToolsIndex::LoadNumReferences(int& numReferences) {
456     const size_t elementsRead = fread(&numReferences, sizeof(numReferences), 1, Resources.IndexStream);
457     if ( m_isBigEndian ) SwapEndian_32(numReferences);
458     if ( elementsRead != 1 )
459         throw BamException("BamToolsIndex::LoadNumReferences", "could not read number of references");
460 }
461
462 void BamToolsIndex::LoadReferenceSummary(BtiReferenceSummary& refSummary) {
463
464     // load number of blocks
465     int numBlocks;
466     LoadNumBlocks(numBlocks);
467
468     // store block summary data for this reference
469     refSummary.NumBlocks = numBlocks;
470     refSummary.FirstBlockFilePosition = Tell();
471
472     // skip reference's blocks
473     SkipBlocks(numBlocks);
474 }
475
476 void BamToolsIndex::OpenFile(const std::string& filename, const char* mode) {
477
478     // make sure any previous index file is closed
479     CloseFile();
480
481     // attempt to open file
482     Resources.IndexStream = fopen(filename.c_str(), mode);
483     if ( !IsFileOpen() ) {
484         const string message = string("could not open file: ") + filename;
485         throw BamException("BamToolsIndex::OpenFile", message);
486     }
487 }
488
489 void BamToolsIndex::ReadBlock(BtiBlock& block) {
490
491     // read in block data members
492     size_t elementsRead = 0;
493     elementsRead += fread(&block.MaxEndPosition, sizeof(block.MaxEndPosition), 1, Resources.IndexStream);
494     elementsRead += fread(&block.StartOffset,    sizeof(block.StartOffset),    1, Resources.IndexStream);
495     elementsRead += fread(&block.StartPosition,  sizeof(block.StartPosition),  1, Resources.IndexStream);
496
497     // swap endian-ness if necessary
498     if ( m_isBigEndian ) {
499         SwapEndian_32(block.MaxEndPosition);
500         SwapEndian_64(block.StartOffset);
501         SwapEndian_32(block.StartPosition);
502     }
503
504     if ( elementsRead != 3 )
505         throw BamException("BamToolsIndex::ReadBlock", "could not read block");
506 }
507
508 void BamToolsIndex::ReadBlocks(const BtiReferenceSummary& refSummary, BtiBlockVector& blocks) {
509
510     // prep blocks container
511     blocks.clear();
512     blocks.reserve(refSummary.NumBlocks);
513
514     // skip to first block entry
515     Seek( refSummary.FirstBlockFilePosition, SEEK_SET );
516
517     // read & store block entries
518     BtiBlock block;
519     for ( int i = 0; i < refSummary.NumBlocks; ++i ) {
520         ReadBlock(block);
521         blocks.push_back(block);
522     }
523 }
524
525 void BamToolsIndex::ReadReferenceEntry(BtiReferenceEntry& refEntry) {
526
527     // return false if refId not valid index in file summary structure
528     if ( refEntry.ID < 0 || refEntry.ID >= (int)m_indexFileSummary.size() )
529         throw BamException("BamToolsIndex::ReadReferenceEntry", "invalid reference requested");
530
531     // use index summary to assist reading the reference's BTI blocks
532     const BtiReferenceSummary& refSummary = m_indexFileSummary.at(refEntry.ID);
533     ReadBlocks(refSummary, refEntry.Blocks);
534 }
535
536 void BamToolsIndex::Seek(const int64_t& position, const int& origin) {
537     if ( fseek64(Resources.IndexStream, position, origin) != 0 )
538         throw BamException("BamToolsIndex::Seek", "could not seek in BAI file");
539 }
540
541 // change the index caching behavior
542 void BamToolsIndex::SetCacheMode(const BamIndex::IndexCacheMode& mode) {
543     m_cacheMode = mode;
544     // do nothing else here ? cache mode will be ignored from now on, most likely
545 }
546
547 void BamToolsIndex::SkipBlocks(const int& numBlocks) {
548     Seek( numBlocks*BamToolsIndex::SIZEOF_BLOCK, SEEK_CUR );
549 }
550
551 int64_t BamToolsIndex::Tell(void) const {
552     return ftell64(Resources.IndexStream);
553 }
554
555 void BamToolsIndex::WriteBlock(const BtiBlock& block) {
556
557     // copy entry data
558     int32_t maxEndPosition = block.MaxEndPosition;
559     int64_t startOffset    = block.StartOffset;
560     int32_t startPosition  = block.StartPosition;
561
562     // swap endian-ness if necessary
563     if ( m_isBigEndian ) {
564         SwapEndian_32(maxEndPosition);
565         SwapEndian_64(startOffset);
566         SwapEndian_32(startPosition);
567     }
568
569     // write the reference index entry
570     size_t elementsWritten = 0;
571     elementsWritten += fwrite(&maxEndPosition, sizeof(maxEndPosition), 1, Resources.IndexStream);
572     elementsWritten += fwrite(&startOffset,    sizeof(startOffset),    1, Resources.IndexStream);
573     elementsWritten += fwrite(&startPosition,  sizeof(startPosition),  1, Resources.IndexStream);
574     if ( elementsWritten != 3 )
575         throw BamException("BamToolsIndex::WriteBlock", "could not write BTI block");
576 }
577
578 void BamToolsIndex::WriteBlocks(const BtiBlockVector& blocks) {
579     BtiBlockVector::const_iterator blockIter = blocks.begin();
580     BtiBlockVector::const_iterator blockEnd  = blocks.end();
581     for ( ; blockIter != blockEnd; ++blockIter )
582         WriteBlock(*blockIter);
583 }
584
585 void BamToolsIndex::WriteHeader(void) {
586
587     size_t elementsWritten = 0;
588
589     // write BTI index format 'magic number'
590     elementsWritten += fwrite(BamToolsIndex::BTI_MAGIC, 1, 4, Resources.IndexStream);
591
592     // write BTI index format version
593     int32_t currentVersion = (int32_t)m_outputVersion;
594     if ( m_isBigEndian ) SwapEndian_32(currentVersion);
595     elementsWritten += fwrite(&currentVersion, sizeof(currentVersion), 1, Resources.IndexStream);
596
597     // write block size
598     uint32_t blockSize = m_blockSize;
599     if ( m_isBigEndian ) SwapEndian_32(blockSize);
600     elementsWritten += fwrite(&blockSize, sizeof(blockSize), 1, Resources.IndexStream);
601
602     // write number of references
603     int32_t numReferences = m_indexFileSummary.size();
604     if ( m_isBigEndian ) SwapEndian_32(numReferences);
605     elementsWritten += fwrite(&numReferences, sizeof(numReferences), 1, Resources.IndexStream);
606
607     if ( elementsWritten != 7 )
608         throw BamException("BamToolsIndex::WriteHeader", "could not write BTI header");
609 }
610
611 void BamToolsIndex::WriteReferenceEntry(const BtiReferenceEntry& refEntry) {
612
613     // write number of blocks this reference
614     uint32_t numBlocks = refEntry.Blocks.size();
615     if ( m_isBigEndian ) SwapEndian_32(numBlocks);
616     const size_t elementsWritten = fwrite(&numBlocks, sizeof(numBlocks), 1, Resources.IndexStream);
617     if ( elementsWritten != 1 )
618         throw BamException("BamToolsIndex::WriteReferenceEntry", "could not write number of blocks");
619
620     // write actual block entries
621     WriteBlocks(refEntry.Blocks);
622 }