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 // ***************************************************************************
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;
27 // --------------------------------
28 // static BamToolsIndex constants
29 // --------------------------------
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);
36 // ----------------------------
37 // RaiiWrapper implementation
38 // ----------------------------
40 BamToolsIndex::RaiiWrapper::RaiiWrapper(void)
44 BamToolsIndex::RaiiWrapper::~RaiiWrapper(void) {
49 // ------------------------------
50 // BamToolsIndex implementation
51 // ------------------------------
54 BamToolsIndex::BamToolsIndex(Internal::BamReaderPrivate* reader)
56 , m_cacheMode(BamIndex::LimitedIndexCaching)
57 , m_blockSize(BamToolsIndex::DEFAULT_BLOCK_LENGTH)
59 , m_outputVersion(BTI_2_0) // latest version - used for writing new index files
61 m_isBigEndian = BamTools::SystemIsBigEndian();
65 BamToolsIndex::~BamToolsIndex(void) {
69 void BamToolsIndex::CheckMagicNumber(void) {
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");
77 // validate expected magic number
78 if ( strncmp(magic, BamToolsIndex::BTI_MAGIC, 4) != 0 )
79 throw BamException("BamToolsIndex::CheckMagicNumber", "invalid BTI magic number");
82 // check index file version, return true if OK
83 void BamToolsIndex::CheckVersion(void) {
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);
91 // if version is negative, or zero
92 if ( m_inputVersion <= 0 )
93 throw BamException("BamToolsIndex::CheckVersion", "invalid format version");
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);
102 // ------------------------------------------------------------------
103 // check for deprecated, unsupported versions
104 // (the format had to be modified to accomodate a particular bug fix)
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);
116 void BamToolsIndex::ClearReferenceEntry(BtiReferenceEntry& refEntry) {
118 refEntry.Blocks.clear();
121 void BamToolsIndex::CloseFile(void) {
122 if ( IsFileOpen() ) {
123 fclose(Resources.IndexStream);
124 Resources.IndexStream = 0;
126 m_indexFileSummary.clear();
129 // builds index from associated BAM file & writes out to index file
130 bool BamToolsIndex::Create(void) {
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");
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);
147 // open new index file (read & write)
148 const string indexFilename = m_reader->Filename() + Extension();
149 OpenFile(indexFilename, "w+b");
151 // initialize BtiFileSummary with number of references
152 const int& numReferences = m_reader->GetReferenceCount();
153 InitializeFileSummary(numReferences);
155 // intialize output file header
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;
166 // plow through alignments, storing index entries
168 BtiReferenceEntry refEntry;
169 while ( m_reader->LoadNextAlignment(al) ) {
171 // if moved to new reference
172 if ( al.RefID != blockRefId ) {
174 // if first pass, check:
175 if ( currentBlockCount == 0 ) {
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) );
185 // store previous BTI block data in reference entry
186 const BtiBlock block(blockMaxEndPosition, blockStartOffset, blockStartPosition);
187 refEntry.Blocks.push_back(block);
189 // write reference entry, then clear
190 WriteReferenceEntry(refEntry);
191 ClearReferenceEntry(refEntry);
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) );
199 currentBlockCount = 0;
202 // set ID for new reference entry
203 refEntry.ID = al.RefID;
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();
214 // increment block counter
217 // check end position
218 const int32_t alignmentEndPosition = al.GetEndPosition();
219 if ( alignmentEndPosition > blockMaxEndPosition )
220 blockMaxEndPosition = alignmentEndPosition;
222 // if block is full, get offset for next block, reset currentBlockCount
223 if ( currentBlockCount == m_blockSize ) {
225 // store previous block data in reference entry
226 const BtiBlock block(blockMaxEndPosition, blockStartOffset, blockStartPosition);
227 refEntry.Blocks.push_back(block);
230 blockStartOffset = m_reader->Tell();
231 currentBlockCount = 0;
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();
240 // after finishing alignments, if any data was read, check:
241 if ( blockRefId >= 0 ) {
243 // store last BTI block data in reference entry
244 const BtiBlock block(blockMaxEndPosition, blockStartOffset, blockStartPosition);
245 refEntry.Blocks.push_back(block);
247 // write last reference entry, then clear
248 WriteReferenceEntry(refEntry);
249 ClearReferenceEntry(refEntry);
251 // then write any empty references remaining at end of file
252 for ( int i = blockRefId+1; i < numReferences; ++i )
253 WriteReferenceEntry( BtiReferenceEntry(i) );
256 } catch ( BamException& e ) {
257 m_errorString = e.what();
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);
273 // returns format's file extension
274 const std::string BamToolsIndex::Extension(void) {
275 return BamToolsIndex::BTI_EXTENSION;
278 void BamToolsIndex::GetOffset(const BamRegion& region, int64_t& offset, bool* hasAlignmentsInRegion) {
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");
284 // retrieve reference index data for left bound reference
285 BtiReferenceEntry refEntry(region.LeftRefID);
286 ReadReferenceEntry(refEntry);
288 // binary search for an overlapping block (may not be first one though)
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;
299 advance(blockIter, step);
301 const BtiBlock& block = (*blockIter);
302 if ( block.StartPosition <= region.RightPosition ) {
303 if ( block.MaxEndPosition > region.LeftPosition ) {
304 offset = block.StartOffset;
307 blockFirst = ++blockIter;
313 // if we didn't search "off the end" of the blocks
314 if ( blockIter != blockLast ) {
316 // "walk back" until we've gone too far
317 while ( blockIter != blockFirst ) {
318 const BtiBlock& currentBlock = (*blockIter);
321 const BtiBlock& previousBlock = (*blockIter);
322 if ( previousBlock.MaxEndPosition <= region.LeftPosition ) {
323 offset = currentBlock.StartOffset;
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;
339 // sets to false if blocks container is empty, or if no matching block could be found
340 *hasAlignmentsInRegion = found;
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() )
347 const BtiReferenceSummary& refSummary = m_indexFileSummary.at(referenceID);
348 return ( refSummary.NumBlocks > 0 );
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() );
358 // returns true if the index stream is open
359 bool BamToolsIndex::IsFileOpen(void) const {
360 return ( Resources.IndexStream != 0 );
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) {
370 *hasAlignmentsInRegion = false;
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");
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");
385 // calculate nearest offset to jump to
388 GetOffset(region, offset, hasAlignmentsInRegion);
389 } catch ( BamException& e ) {
390 m_errorString = e.what();
394 // return success/failure of seek
395 return m_reader->Seek(offset);
398 // loads existing data from file into memory
399 bool BamToolsIndex::Load(const std::string& filename) {
403 // attempt to open file (read-only)
404 OpenFile(filename, "rb");
406 // load metadata & generate in-memory summary
413 } catch ( BamException& e ) {
414 m_errorString = e.what();
419 void BamToolsIndex::LoadFileSummary(void) {
421 // load number of reference sequences
423 LoadNumReferences(numReferences);
425 // initialize file summary data
426 InitializeFileSummary(numReferences);
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);
435 void BamToolsIndex::LoadHeader(void) {
437 // check BTI file metadata
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");
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");
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");
462 void BamToolsIndex::LoadReferenceSummary(BtiReferenceSummary& refSummary) {
464 // load number of blocks
466 LoadNumBlocks(numBlocks);
468 // store block summary data for this reference
469 refSummary.NumBlocks = numBlocks;
470 refSummary.FirstBlockFilePosition = Tell();
472 // skip reference's blocks
473 SkipBlocks(numBlocks);
476 void BamToolsIndex::OpenFile(const std::string& filename, const char* mode) {
478 // make sure any previous index file is closed
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);
489 void BamToolsIndex::ReadBlock(BtiBlock& block) {
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);
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);
504 if ( elementsRead != 3 )
505 throw BamException("BamToolsIndex::ReadBlock", "could not read block");
508 void BamToolsIndex::ReadBlocks(const BtiReferenceSummary& refSummary, BtiBlockVector& blocks) {
510 // prep blocks container
512 blocks.reserve(refSummary.NumBlocks);
514 // skip to first block entry
515 Seek( refSummary.FirstBlockFilePosition, SEEK_SET );
517 // read & store block entries
519 for ( int i = 0; i < refSummary.NumBlocks; ++i ) {
521 blocks.push_back(block);
525 void BamToolsIndex::ReadReferenceEntry(BtiReferenceEntry& refEntry) {
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");
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);
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");
541 // change the index caching behavior
542 void BamToolsIndex::SetCacheMode(const BamIndex::IndexCacheMode& mode) {
544 // do nothing else here ? cache mode will be ignored from now on, most likely
547 void BamToolsIndex::SkipBlocks(const int& numBlocks) {
548 Seek( numBlocks*BamToolsIndex::SIZEOF_BLOCK, SEEK_CUR );
551 int64_t BamToolsIndex::Tell(void) const {
552 return ftell64(Resources.IndexStream);
555 void BamToolsIndex::WriteBlock(const BtiBlock& block) {
558 int32_t maxEndPosition = block.MaxEndPosition;
559 int64_t startOffset = block.StartOffset;
560 int32_t startPosition = block.StartPosition;
562 // swap endian-ness if necessary
563 if ( m_isBigEndian ) {
564 SwapEndian_32(maxEndPosition);
565 SwapEndian_64(startOffset);
566 SwapEndian_32(startPosition);
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");
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);
585 void BamToolsIndex::WriteHeader(void) {
587 size_t elementsWritten = 0;
589 // write BTI index format 'magic number'
590 elementsWritten += fwrite(BamToolsIndex::BTI_MAGIC, 1, 4, Resources.IndexStream);
592 // write BTI index format version
593 int32_t currentVersion = (int32_t)m_outputVersion;
594 if ( m_isBigEndian ) SwapEndian_32(currentVersion);
595 elementsWritten += fwrite(¤tVersion, sizeof(currentVersion), 1, Resources.IndexStream);
598 uint32_t blockSize = m_blockSize;
599 if ( m_isBigEndian ) SwapEndian_32(blockSize);
600 elementsWritten += fwrite(&blockSize, sizeof(blockSize), 1, Resources.IndexStream);
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);
607 if ( elementsWritten != 7 )
608 throw BamException("BamToolsIndex::WriteHeader", "could not write BTI header");
611 void BamToolsIndex::WriteReferenceEntry(const BtiReferenceEntry& refEntry) {
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");
620 // write actual block entries
621 WriteBlocks(refEntry.Blocks);