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: 10 October 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 <cassert>
  19 #include <algorithm>
  20 #include <functional>
  21 #include <string>
  22 #include <vector>
  23
  24 namespace BamTools {
  25 namespace Algorithms {
  26
  27 /*! \struct BamTools::Algorithms::Sort
  28     \brief Provides classes & methods related to sorting BamAlignments
  29 */
  30 struct API_EXPORT Sort {
  31
  32     //! Provides explicit values for specifying desired sort ordering
  33     enum Order { AscendingOrder = 0
  34                , DescendingOrder
  35                };
  36
  37     /*! \fn template<typename ElemType> static inline bool sort_helper(const Sort::Order& order, const ElemType& lhs, const ElemType& rhs)
  38         \internal
  39
  40         Determines necessary STL function object depending on requested Sort::Order
  41     */
  42     template<typename ElemType>
  43     static inline bool sort_helper(const Sort::Order& order, const ElemType& lhs, const ElemType& rhs) {
  44         switch ( order ) {
  45             case ( Sort::AscendingOrder  ) : { std::less<ElemType> comp;    return comp(lhs, rhs); }
  46             case ( Sort::DescendingOrder ) : { std::greater<ElemType> comp; return comp(lhs, rhs); }
  47             default : BT_ASSERT_UNREACHABLE;
  48         }
  49         return false; // <-- unreachable
  50     }
  51
  52     //! Base class for our sorting function objects
  53     typedef std::binary_function<BamAlignment, BamAlignment, bool> AlignmentSortBase;
  54
  55     /*! \struct BamTools::Algorithms::Sort::ByName
  56         \brief Function object for comparing alignments by name
  57
  58         Default sort order is Sort::AscendingOrder.
  59
  60         \code
  61             std::vector<BamAlignment> a;
  62
  63             // sort by name, in ascending order (the following two lines are equivalent):
  64             std::sort( a.begin(), a.end(), Sort::ByName() );
  65             std::sort( a.begin(), a.end(), Sort::ByName(Sort::AscendingOrder) );
  66
  67             // OR sort in descending order
  68             std::sort( a.begin(), a.end(), Sort::ByName(Sort::DescendingOrder) );
  69         \endcode
  70     */
  71     struct ByName : public AlignmentSortBase {
  72
  73         // ctor
  74         ByName(const Sort::Order& order = Sort::AscendingOrder)
  75             : m_order(order)
  76         { }
  77
  78         // comparison function
  79         bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) {
  80             return sort_helper(m_order, lhs.Name, rhs.Name);
  81         }
  82
  83         // used by BamMultiReader internals
  84         static inline bool UsesCharData(void) { return true; }
  85
  86         // data members
  87         private:
  88             const Sort::Order& m_order;
  89     };
  90
  91     /*! \struct BamTools::Algorithms::Sort::ByPosition
  92         \brief Function object for comparing alignments by position
  93
  94         Default sort order is Sort::AscendingOrder.
  95
  96         \code
  97             std::vector<BamAlignment> a;
  98
  99             // sort by position, in ascending order (the following two lines are equivalent):
 100             std::sort( a.begin(), a.end(), Sort::ByPosition() );
 101             std::sort( a.begin(), a.end(), Sort::ByPosition(Sort::AscendingOrder) );
 102
 103             // OR sort in descending order
 104             std::sort( a.begin(), a.end(), Sort::ByPosition(Sort::DescendingOrder) );
 105         \endcode
 106     */
 107     struct ByPosition : public AlignmentSortBase {
 108
 109         // ctor
 110         ByPosition(const Sort::Order& order = Sort::AscendingOrder)
 111             : m_order(order)
 112         { }
 113
 114         // comparison function
 115         bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) {
 116
 117             // force unmapped aligmnents to end
 118             if ( lhs.RefID == -1 ) return false;
 119             if ( rhs.RefID == -1 ) return true;
 120
 121             // if on same reference, sort on position
 122             if ( lhs.RefID == rhs.RefID )
 123                 return sort_helper(m_order, lhs.Position, rhs.Position);
 124
 125             // otherwise sort on reference ID
 126             return sort_helper(m_order, lhs.RefID, rhs.RefID);
 127         }
 128
 129         // used by BamMultiReader internals
 130         static inline bool UsesCharData(void) { return false; }
 131
 132         // data members
 133         private:
 134             Sort::Order m_order;
 135     };
 136
 137     /*! \struct BamTools::Algorithms::Sort::ByTag
 138         \brief Function object for comparing alignments by tag value
 139
 140         Default sort order is Sort::AscendingOrder.
 141
 142         \code
 143             std::vector<BamAlignment> a;
 144
 145             // sort by edit distance, in ascending order (the following two lines are equivalent):
 146             std::sort( a.begin(), a.end(), Sort::ByTag<int>("NM") );
 147             std::sort( a.begin(), a.end(), Sort::ByTag<int>("NM", Sort::AscendingOrder) );
 148
 149             // OR sort in descending order
 150             std::sort( a.begin(), a.end(), Sort::ByTag<int>("NM", Sort::DescendingOrder) );
 151         \endcode
 152     */
 153     template<typename T>
 154     struct ByTag : public AlignmentSortBase {
 155
 156         // ctor
 157         ByTag(const std::string& tag,
 158               const Sort::Order& order = Sort::AscendingOrder)
 159             : m_tag(tag)
 160             , m_order(order)
 161         { }
 162
 163         // comparison function
 164         bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) {
 165
 166             // force alignments without tag to end
 167             T lhsTagValue;
 168             T rhsTagValue;
 169             if ( !lhs.GetTag(m_tag, lhsTagValue) ) return false;
 170             if ( !rhs.GetTag(m_tag, rhsTagValue) ) return true;
 171
 172             // otherwise compare on tag values
 173             return sort_helper(m_order, lhsTagValue, rhsTagValue);
 174         }
 175
 176         // used by BamMultiReader internals
 177         static inline bool UsesCharData(void) { return true; }
 178
 179         // data members
 180         private:
 181             std::string m_tag;
 182             Sort::Order m_order;
 183     };
 184
 185     /*! \struct BamTools::Algorithms::Sort::Unsorted
 186         \brief Placeholder function object
 187
 188         This function object exists purely to allow for dropping a "do not care" ordering
 189         into methods, containers, etc that are designed to work with the other sorting objects.
 190
 191         \code
 192             std::set<BamAlignment, Sort::ByName>;   // STL set, ordered on alignment name
 193             std::set<BamAlignment, Sort::Unsorted>; // STL set, unsorted (but probably insertion order)
 194         \endcode
 195     */
 196     struct Unsorted : public AlignmentSortBase {
 197
 198         // comparison function
 199         inline bool operator()(const BamTools::BamAlignment&, const BamTools::BamAlignment&) {
 200             return false;   // returning false tends to retain insertion order
 201         }
 202
 203         // used by BamMultiReader internals
 204         static inline bool UsesCharData(void) { return false; }
 205     };
 206
 207     /*! Sorts a std::vector of alignments (in-place), using the provided compare function.
 208
 209         \code
 210             std::vector<BamAlignemnt> a;
 211             // populate data
 212
 213             // sort our alignment list by edit distance
 214             Sort::SortAlignments(a, Sort::ByTag<int>("NM"));
 215         \endcode
 216
 217         \param[in,out] data vector of alignments to be sorted
 218         \param[in]     comp comparison function object
 219     */
 220     template<typename Compare>
 221     static inline void SortAlignments(std::vector<BamAlignment>& data,
 222                                       const Compare& comp = Compare())
 223     {
 224         std::sort(data.begin(), data.end(), comp);
 225     }
 226
 227     /*! Returns a sorted copy of the input alignments, using the provided compare function.
 228
 229         \code
 230             std::vector<BamAlignemnt> a;
 231             // populate data
 232
 233             // get a copy of our original data, sorted by edit distance (descending order)
 234             std::vector<BamAligment> sortedData;
 235             sortedData = Sort::SortAlignments(a, Sort::ByTag<int>("NM", Sort::DescendingOrder));
 236         \endcode
 237
 238         \param[in] input vector of alignments to be sorted
 239         \param[in] comp  comparison function object
 240         \return sorted copy of the input data
 241     */
 242     template<typename Compare>
 243     static inline std::vector<BamAlignment> SortAlignments(const std::vector<BamAlignment>& input,
 244                                                            const Compare& comp = Compare())
 245     {
 246         std::vector<BamAlignment> output(input);
 247         SortAlignments(output, comp);
 248         return output;
 249     }
 250
 251     /*! Reads a region of alignments from a position-sorted BAM file,
 252         then sorts by the provided compare function
 253
 254         \code
 255             BamReader reader;
 256             // open BAM file & index file
 257
 258             BamRegion region;
 259             // define a region of interest (i.e. a exon or some other feature)
 260
 261             // get all alignments covering that region, sorted by read group name
 262             std::vector<BamAlignments> a;
 263             a = Sort::GetSortedRegion(reader, region, Sort::ByTag<std::string>("RG"));
 264         \endcode
 265
 266         \param[in] reader BamReader opened on desired BAM file
 267         \param[in] region desired region-of-interest
 268         \param[in] comp   comparison function object
 269         \return sorted vector of the region's alignments
 270     */
 271     template<typename Compare>
 272     static std::vector<BamAlignment> GetSortedRegion(BamReader& reader,
 273                                                      const BamRegion& region,
 274                                                      const Compare& comp = Compare())
 275     {
 276         // return empty container if unable to find region
 277         if ( !reader.IsOpen() )          return std::vector<BamAlignment>();
 278         if ( !reader.SetRegion(region) ) return std::vector<BamAlignment>();
 279
 280         // iterate through region, grabbing alignments
 281         BamAlignment al;
 282         std::vector<BamAlignment> results;
 283         while ( reader.GetNextAlignmentCore(al) )
 284             results.push_back(al);
 285
 286         // sort & return alignments
 287         SortAlignments(results, comp);
 288         return results;
 289     }
 290
 291     /*! Reads a region of alignments from position-sorted BAM files,
 292         then sorts by the provided compare function
 293
 294         \code
 295             BamMultiReader reader;
 296             // open BAM files & index files
 297
 298             BamRegion region;
 299             // define a region of interest (i.e. a exon or some other feature)
 300
 301             // get all alignments covering that region, sorted by read group name
 302             std::vector<BamAlignments> a;
 303             a = Sort::GetSortedRegion(reader, region, Sort::ByTag<std::string>("RG"));
 304         \endcode
 305
 306         \param[in] reader BamMultiReader opened on desired BAM files
 307         \param[in] region desired region-of-interest
 308         \param[in] comp   comparison function object
 309         \return sorted vector of the region's alignments
 310     */
 311     template<typename Compare>
 312     static std::vector<BamAlignment> GetSortedRegion(BamMultiReader& reader,
 313                                                      const BamRegion& region,
 314                                                      const Compare& comp = Compare())
 315     {
 316         // return empty container if unable to find region
 317         if ( !reader.HasOpenReaders() )  return std::vector<BamAlignment>();
 318         if ( !reader.SetRegion(region) ) return std::vector<BamAlignment>();
 319
 320         // iterate through region, grabbing alignments
 321         BamAlignment al;
 322         std::vector<BamAlignment> results;
 323         while ( reader.GetNextAlignmentCore(al) )
 324             results.push_back(al);
 325
 326         // sort & return alignments
 327         SortAlignments(results, comp);
 328         return results;
 329     }
 330 };
 331
 332 } // namespace Algorithms
 333 } // namespace BamTools
 334
 335 #endif // ALGORITHMS_SORT_H