src/api/algorithms/Sort.h

   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 // ***************************************************************************
  10
  11 #ifndef ALGORITHMS_SORT_H
  12 #define ALGORITHMS_SORT_H
  13
  14 #include <api/api_global.h>
  15 #include <api/BamAlignment.h>
  16 #include <api/BamReader.h>
  17 #include <api/BamMultiReader.h>
  18 #include <algorithm>
  19 #include <cassert>
  20 #include <functional>
  21 #include <string>
  22 #include <vector>
  23
  24 namespace BamTools {
  25 namespace Algorithms {
  26
  27 struct API_EXPORT Sort {
  28
  29     enum Order { AscendingOrder = 0
  30                , DescendingOrder
  31                };
  32
  33     template<typename ElemType>
  34     static inline bool sort_helper(const Sort::Order& order,
  35                                    const ElemType& lhs,
  36                                    const ElemType& rhs)
  37     {
  38         switch ( 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);
  42         }
  43         return false; // <-- unreachable
  44     }
  45
  46     typedef std::binary_function<BamAlignment, BamAlignment, bool> AlignmentSortBase;
  47
  48     // compare alignments by name
  49     struct ByName : public AlignmentSortBase {
  50
  51         ByName(const Sort::Order& order = Sort::AscendingOrder)
  52             : m_order(order)
  53         { }
  54
  55         bool operator()(const BamTools::BamAlignment& lhs,
  56                         const BamTools::BamAlignment& rhs)
  57         {
  58             return sort_helper(m_order, lhs.Name, rhs.Name);
  59         }
  60
  61         static inline bool UsesCharData(void) { return true; }
  62
  63         private:
  64             const Sort::Order& m_order;
  65     };
  66
  67     // compare alignments by position
  68     struct ByPosition : public AlignmentSortBase {
  69
  70         ByPosition(const Sort::Order& order = Sort::AscendingOrder)
  71             : m_order(order)
  72         { }
  73
  74         bool operator()(const BamTools::BamAlignment& lhs,
  75                         const BamTools::BamAlignment& rhs)
  76         {
  77             // force unmapped aligmnents to end
  78             if ( lhs.RefID == -1 ) return false;
  79             if ( rhs.RefID == -1 ) return true;
  80
  81             // if on same reference, sort on position
  82             if ( lhs.RefID == rhs.RefID )
  83                 return sort_helper(m_order, lhs.Position, rhs.Position);
  84
  85             // otherwise sort on reference ID
  86             return sort_helper(m_order, lhs.RefID, rhs.RefID);
  87         }
  88
  89         static inline bool UsesCharData(void) { return false; }
  90
  91         private:
  92             Sort::Order m_order;
  93     };
  94
  95     // compare alignments by tag value
  96     template<typename T>
  97     struct ByTag : public AlignmentSortBase {
  98
  99         ByTag(const std::string& tag,
 100               const Sort::Order& order = Sort::AscendingOrder)
 101             : m_tag(tag)
 102             , m_order(order)
 103         { }
 104
 105         bool operator()(const BamTools::BamAlignment& lhs,
 106                         const BamTools::BamAlignment& rhs)
 107         {
 108             // force alignments without tag to end
 109             T lhsTagValue;
 110             T rhsTagValue;
 111             if ( !lhs.GetTag(m_tag, lhsTagValue) ) return false;
 112             if ( !rhs.GetTag(m_tag, rhsTagValue) ) return true;
 113
 114             // otherwise compare on tag values
 115             return sort_helper(m_order, lhsTagValue, rhsTagValue);
 116         }
 117
 118         static inline bool UsesCharData(void) { return true; }
 119
 120         private:
 121             std::string m_tag;
 122             Sort::Order m_order;
 123     };
 124
 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*/)
 130         {
 131             return false;
 132         }
 133
 134         static inline bool UsesCharData(void) { return false; }
 135     };
 136 };
 137
 138 // in-place sorting of alignment vector
 139 template<typename Compare>
 140 inline
 141 void SortAlignments(std::vector<BamAlignment>& data,
 142                     const Compare& comp = Compare())
 143 {
 144     std::sort(data.begin(), data.end(), comp);
 145 }
 146
 147 // returns sorted copy of input alignment vector
 148 template<typename Compare>
 149 inline
 150 std::vector<BamAlignment> SortAlignmentsCopy(const std::vector<BamAlignment>& input,
 151                                              const Compare& comp = Compare())
 152 {
 153     std::vector<BamAlignment> output(input);
 154     SortAlignments(output, comp);
 155     return output;
 156 }
 157
 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())
 164 {
 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>();
 168
 169     // iterate through region, grabbing alignments
 170     BamAlignment al;
 171     std::vector<BamAlignment> results;
 172     while ( reader.GetNextAlignmentCore(al) )
 173         results.push_back(al);
 174
 175     // sort & return alignments
 176     SortAlignments(results, comp);
 177     return results;
 178 }
 179
 180 template<typename Compare>
 181 std::vector<BamAlignment> GetSortedRegion(BamMultiReader& reader,
 182                                           const BamRegion& region,
 183                                           const Compare& comp = Compare())
 184 {
 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>();
 188
 189     // iterate through region, grabbing alignments
 190     BamAlignment al;
 191     std::vector<BamAlignment> results;
 192     while ( reader.GetNextAlignmentCore(al) )
 193         results.push_back(al);
 194
 195     // sort & return alignments
 196     SortAlignments(results, comp);
 197     return results;
 198 }
 199
 200 } // namespace Algorithms
 201 } // namespace BamTools
 202
 203 #endif // ALGORITHMS_SORT_H