BamTools  2.5.1
Sort.h
Go to the documentation of this file.
1 // ***************************************************************************
2 // Sort.h (c) 2009 Derek Barnett
3 // Marth Lab, Department of Biology, Boston College
4 // All rights reserved.
5 // ---------------------------------------------------------------------------
6 // Last modified: 4 April 2012 (DB)
7 // ---------------------------------------------------------------------------
8 // Provides sorting functionality.
9 // ***************************************************************************
10 
11 #ifndef ALGORITHMS_SORT_H
12 #define ALGORITHMS_SORT_H
13 
14 #include <algorithm>
15 #include <cassert>
16 #include <functional>
17 #include <string>
18 #include <vector>
19 #include "api/BamAlignment.h"
20 #include "api/BamMultiReader.h"
21 #include "api/BamReader.h"
22 #include "api/api_global.h"
23 
24 namespace BamTools {
25 namespace Algorithms {
26 
31 {
32 
34  enum Order
35  {
36  AscendingOrder = 0,
37  DescendingOrder
38  };
39 
45  template <typename ElemType>
46  static inline bool sort_helper(const Sort::Order& order, const ElemType& lhs,
47  const ElemType& rhs)
48  {
49  switch (order) {
50  case (Sort::AscendingOrder): {
51  std::less<ElemType> comp;
52  return comp(lhs, rhs);
53  }
54  case (Sort::DescendingOrder): {
55  std::greater<ElemType> comp;
56  return comp(lhs, rhs);
57  }
58  default:
59  BT_ASSERT_UNREACHABLE;
60  }
61  return false; // <-- unreachable
62  }
63 
65  typedef std::binary_function<BamAlignment, BamAlignment, bool> AlignmentSortBase;
66 
83  struct ByName : public AlignmentSortBase
84  {
85 
86  // ctor
88  : m_order(order)
89  {}
90 
91  // comparison function
93  {
94  return sort_helper(m_order, lhs.Name, rhs.Name);
95  }
96 
97  // used by BamMultiReader internals
98  static inline bool UsesCharData()
99  {
100  return true;
101  }
102 
103  // data members
104  private:
105  const Sort::Order m_order;
106  };
107 
124  struct ByPosition : public AlignmentSortBase
125  {
126 
127  // ctor
129  : m_order(order)
130  {}
131 
132  // comparison function
134  {
135 
136  // force unmapped aligmnents to end
137  if (lhs.RefID == -1) return false;
138  if (rhs.RefID == -1) return true;
139 
140  // if on same reference, sort on position
141  if (lhs.RefID == rhs.RefID) return sort_helper(m_order, lhs.Position, rhs.Position);
142 
143  // otherwise sort on reference ID
144  return sort_helper(m_order, lhs.RefID, rhs.RefID);
145  }
146 
147  // used by BamMultiReader internals
148  static inline bool UsesCharData()
149  {
150  return false;
151  }
152 
153  // data members
154  private:
155  const Sort::Order m_order;
156  };
157 
174  template <typename T>
175  struct ByTag : public AlignmentSortBase
176  {
177 
178  // ctor
179  ByTag(const std::string& tag, const Sort::Order& order = Sort::AscendingOrder)
180  : m_tag(tag)
181  , m_order(order)
182  {}
183 
184  // comparison function
186  {
187 
188  // force alignments without tag to end
189  T lhsTagValue;
190  T rhsTagValue;
191  if (!lhs.GetTag(m_tag, lhsTagValue)) return false;
192  if (!rhs.GetTag(m_tag, rhsTagValue)) return true;
193 
194  // otherwise compare on tag values
195  return sort_helper(m_order, lhsTagValue, rhsTagValue);
196  }
197 
198  // used by BamMultiReader internals
199  static inline bool UsesCharData()
200  {
201  return true;
202  }
203 
204  // data members
205  private:
206  const std::string m_tag;
207  const Sort::Order m_order;
208  };
209 
221  struct Unsorted : public AlignmentSortBase
222  {
223 
224  // comparison function
226  {
227  return false; // returning false tends to retain insertion order
228  }
229 
230  // used by BamMultiReader internals
231  static inline bool UsesCharData()
232  {
233  return false;
234  }
235  };
236 
250  template <typename Compare>
251  static inline void SortAlignments(std::vector<BamAlignment>& data,
252  const Compare& comp = Compare())
253  {
254  std::sort(data.begin(), data.end(), comp);
255  }
256 
272  template <typename Compare>
273  static inline std::vector<BamAlignment> SortAlignments(const std::vector<BamAlignment>& input,
274  const Compare& comp = Compare())
275  {
276  std::vector<BamAlignment> output(input);
277  SortAlignments(output, comp);
278  return output;
279  }
280 
301  template <typename Compare>
302  static std::vector<BamAlignment> GetSortedRegion(BamReader& reader, const BamRegion& region,
303  const Compare& comp = Compare())
304  {
305  // return empty container if unable to find region
306  if (!reader.IsOpen()) return std::vector<BamAlignment>();
307  if (!reader.SetRegion(region)) return std::vector<BamAlignment>();
308 
309  // iterate through region, grabbing alignments
310  BamAlignment al;
311  std::vector<BamAlignment> results;
312  while (reader.GetNextAlignmentCore(al))
313  results.push_back(al);
314 
315  // sort & return alignments
316  SortAlignments(results, comp);
317  return results;
318  }
319 
340  template <typename Compare>
341  static std::vector<BamAlignment> GetSortedRegion(BamMultiReader& reader,
342  const BamRegion& region,
343  const Compare& comp = Compare())
344  {
345  // return empty container if unable to find region
346  if (!reader.HasOpenReaders()) return std::vector<BamAlignment>();
347  if (!reader.SetRegion(region)) return std::vector<BamAlignment>();
348 
349  // iterate through region, grabbing alignments
350  BamAlignment al;
351  std::vector<BamAlignment> results;
352  while (reader.GetNextAlignmentCore(al))
353  results.push_back(al);
354 
355  // sort & return alignments
356  SortAlignments(results, comp);
357  return results;
358  }
359 };
360 
361 } // namespace Algorithms
362 } // namespace BamTools
363 
364 #endif // ALGORITHMS_SORT_H
#define API_EXPORT
Definition: api_global.h:18
The main BAM alignment data structure.
Definition: BamAlignment.h:34
bool GetTag(const std::string &tag, T &destination) const
Definition: BamAlignment.h:426
int32_t RefID
ID number for reference sequence.
Definition: BamAlignment.h:134
std::string Name
read name
Definition: BamAlignment.h:127
int32_t Position
position (0-based) where alignment starts
Definition: BamAlignment.h:135
Convenience class for reading multiple BAM files.
Definition: BamMultiReader.h:27
bool GetNextAlignmentCore(BamAlignment &alignment)
Retrieves next available alignment.
Definition: BamMultiReader.cpp:197
bool SetRegion(const BamRegion &region)
Sets a target region of interest.
Definition: BamMultiReader.cpp:413
bool HasOpenReaders() const
Returns true if there are any open BAM files.
Definition: BamMultiReader.cpp:245
Provides read access to BAM files.
Definition: BamReader.h:26
bool SetRegion(const BamRegion &region)
Sets a target region of interest.
Definition: BamReader.cpp:373
bool IsOpen() const
Returns true if a BAM file is open for reading.
Definition: BamReader.cpp:234
bool GetNextAlignmentCore(BamAlignment &alignment)
Retrieves next available alignment, without populating the alignment's string data fields.
Definition: BamReader.cpp:189
Contains all BamTools classes & methods.
Definition: Sort.h:24
Function object for comparing alignments by name.
Definition: Sort.h:84
ByName(const Sort::Order &order=Sort::AscendingOrder)
Definition: Sort.h:87
bool operator()(const BamTools::BamAlignment &lhs, const BamTools::BamAlignment &rhs)
Definition: Sort.h:92
Function object for comparing alignments by position.
Definition: Sort.h:125
bool operator()(const BamTools::BamAlignment &lhs, const BamTools::BamAlignment &rhs)
Definition: Sort.h:133
ByPosition(const Sort::Order &order=Sort::AscendingOrder)
Definition: Sort.h:128
Function object for comparing alignments by tag value.
Definition: Sort.h:176
ByTag(const std::string &tag, const Sort::Order &order=Sort::AscendingOrder)
Definition: Sort.h:179
bool operator()(const BamTools::BamAlignment &lhs, const BamTools::BamAlignment &rhs)
Definition: Sort.h:185
Placeholder function object.
Definition: Sort.h:222
bool operator()(const BamTools::BamAlignment &, const BamTools::BamAlignment &)
Definition: Sort.h:225
Provides classes & methods related to sorting BamAlignments.
Definition: Sort.h:31
static void SortAlignments(std::vector< BamAlignment > &data, const Compare &comp=Compare())
Definition: Sort.h:251
static std::vector< BamAlignment > SortAlignments(const std::vector< BamAlignment > &input, const Compare &comp=Compare())
Definition: Sort.h:273
static std::vector< BamAlignment > GetSortedRegion(BamReader &reader, const BamRegion &region, const Compare &comp=Compare())
Definition: Sort.h:302
Order
Provides explicit values for specifying desired sort ordering.
Definition: Sort.h:35
@ DescendingOrder
Definition: Sort.h:37
@ AscendingOrder
Definition: Sort.h:36
static std::vector< BamAlignment > GetSortedRegion(BamMultiReader &reader, const BamRegion &region, const Compare &comp=Compare())
Definition: Sort.h:341
Represents a sequential genomic region.
Definition: BamAux.h:90