1 // ***************************************************************************
2 // Sort.h (c) 2009 Derek Barnett
3 // Marth Lab, Department of Biology, Boston College
4 // All rights reserved.
5 // ---------------------------------------------------------------------------
6 // Last modified: 29 September 2011 (DB)
7 // ---------------------------------------------------------------------------
8 // Provides sorting functionality.
9 // ***************************************************************************
11 #ifndef ALGORITHMS_SORT_H
12 #define ALGORITHMS_SORT_H
14 #include <api/api_global.h>
15 #include <api/BamAlignment.h>
16 #include <api/BamReader.h>
17 #include <api/BamMultiReader.h>
25 namespace Algorithms {
27 struct API_EXPORT Sort {
29 enum Order { AscendingOrder = 0
33 template<typename ElemType>
34 static inline bool sort_helper(const Sort::Order& order,
39 case ( Sort::AscendingOrder ) : { std::less<ElemType> comp; return comp(lhs, rhs); }
40 case ( Sort::DescendingOrder ) : { std::greater<ElemType> comp; return comp(lhs, rhs); }
41 default : assert(false);
43 return false; // <-- unreachable
46 typedef std::binary_function<BamAlignment, BamAlignment, bool> AlignmentSortBase;
48 // compare alignments by name
49 struct ByName : public AlignmentSortBase {
51 ByName(const Sort::Order& order = Sort::AscendingOrder)
55 bool operator()(const BamTools::BamAlignment& lhs,
56 const BamTools::BamAlignment& rhs)
58 return sort_helper(m_order, lhs.Name, rhs.Name);
61 static inline bool UsesCharData(void) { return true; }
64 const Sort::Order& m_order;
67 // compare alignments by position
68 struct ByPosition : public AlignmentSortBase {
70 ByPosition(const Sort::Order& order = Sort::AscendingOrder)
74 bool operator()(const BamTools::BamAlignment& lhs,
75 const BamTools::BamAlignment& rhs)
77 // force unmapped aligmnents to end
78 if ( lhs.RefID == -1 ) return false;
79 if ( rhs.RefID == -1 ) return true;
81 // if on same reference, sort on position
82 if ( lhs.RefID == rhs.RefID )
83 return sort_helper(m_order, lhs.Position, rhs.Position);
85 // otherwise sort on reference ID
86 return sort_helper(m_order, lhs.RefID, rhs.RefID);
89 static inline bool UsesCharData(void) { return false; }
95 // compare alignments by tag value
97 struct ByTag : public AlignmentSortBase {
99 ByTag(const std::string& tag,
100 const Sort::Order& order = Sort::AscendingOrder)
105 bool operator()(const BamTools::BamAlignment& lhs,
106 const BamTools::BamAlignment& rhs)
108 // force alignments without tag to end
111 if ( !lhs.GetTag(m_tag, lhsTagValue) ) return false;
112 if ( !rhs.GetTag(m_tag, rhsTagValue) ) return true;
114 // otherwise compare on tag values
115 return sort_helper(m_order, lhsTagValue, rhsTagValue);
118 static inline bool UsesCharData(void) { return true; }
125 // essentially a placeholder comparison object, ignores the alignments' data
126 // N.B. - returning false tends to retain insertion order
127 struct Unsorted : public AlignmentSortBase {
128 inline bool operator()(const BamTools::BamAlignment& /*lhs*/,
129 const BamTools::BamAlignment& /*rhs*/)
134 static inline bool UsesCharData(void) { return false; }
138 // in-place sorting of alignment vector
139 template<typename Compare>
141 void SortAlignments(std::vector<BamAlignment>& data,
142 const Compare& comp = Compare())
144 std::sort(data.begin(), data.end(), comp);
147 // returns sorted copy of input alignment vector
148 template<typename Compare>
150 std::vector<BamAlignment> SortAlignmentsCopy(const std::vector<BamAlignment>& input,
151 const Compare& comp = Compare())
153 std::vector<BamAlignment> output(input);
154 SortAlignments(output, comp);
158 // pulls a region from a position-sorted BAM file
159 // returns the alignments sorted by user-defined Compare type
160 template<typename Compare>
161 std::vector<BamAlignment> GetSortedRegion(BamReader& reader,
162 const BamRegion& region,
163 const Compare& comp = Compare())
165 // return empty container if unable to find region
166 if ( !reader.IsOpen() ) return std::vector<BamAlignment>();
167 if ( !reader.SetRegion(region) ) return std::vector<BamAlignment>();
169 // iterate through region, grabbing alignments
171 std::vector<BamAlignment> results;
172 while ( reader.GetNextAlignmentCore(al) )
173 results.push_back(al);
175 // sort & return alignments
176 SortAlignments(results, comp);
180 template<typename Compare>
181 std::vector<BamAlignment> GetSortedRegion(BamMultiReader& reader,
182 const BamRegion& region,
183 const Compare& comp = Compare())
185 // return empty container if unable to find region
186 if ( !reader.HasOpenReaders() ) return std::vector<BamAlignment>();
187 if ( !reader.SetRegion(region) ) return std::vector<BamAlignment>();
189 // iterate through region, grabbing alignments
191 std::vector<BamAlignment> results;
192 while ( reader.GetNextAlignmentCore(al) )
193 results.push_back(al);
195 // sort & return alignments
196 SortAlignments(results, comp);
200 } // namespace Algorithms
201 } // namespace BamTools
203 #endif // ALGORITHMS_SORT_H