Sort.h

Go to the documentation of this file.

// ***************************************************************************
// Sort.h (c) 2009 Derek Barnett
// Marth Lab, Department of Biology, Boston College
// All rights reserved.
// ---------------------------------------------------------------------------
// Last modified: 4 April 2012 (DB)
// ---------------------------------------------------------------------------
// Provides sorting functionality.
// ***************************************************************************

#ifndef ALGORITHMS_SORT_H
#define ALGORITHMS_SORT_H

#include "api/api_global.h"
#include "api/BamAlignment.h"
#include "api/BamReader.h"
#include "api/BamMultiReader.h"
#include <cassert>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

namespace BamTools {
namespace Algorithms {

struct API_EXPORT Sort {

    enum Order { AscendingOrder = 0
               , DescendingOrder
               };

    template<typename ElemType>
    static inline bool sort_helper(const Sort::Order& order, const ElemType& lhs, const ElemType& rhs) {
        switch ( order ) {
            case ( Sort::AscendingOrder  ) : { std::less<ElemType> comp;    return comp(lhs, rhs); }
            case ( Sort::DescendingOrder ) : { std::greater<ElemType> comp; return comp(lhs, rhs); }
            default : BT_ASSERT_UNREACHABLE;
        }
        return false; // <-- unreachable
    }

    typedef std::binary_function<BamAlignment, BamAlignment, bool> AlignmentSortBase;

    struct ByName : public AlignmentSortBase {

        // ctor
        ByName(const Sort::Order& order = Sort::AscendingOrder)
            : m_order(order)
        { }

        // comparison function
        bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) {
            return sort_helper(m_order, lhs.Name, rhs.Name);
        }

        // used by BamMultiReader internals
        static inline bool UsesCharData(void) { return true; }

        // data members
        private:
            const Sort::Order m_order;
    };

    struct ByPosition : public AlignmentSortBase {

        // ctor
        ByPosition(const Sort::Order& order = Sort::AscendingOrder)
            : m_order(order)
        { }

        // comparison function
        bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) {

            // force unmapped aligmnents to end
            if ( lhs.RefID == -1 ) return false;
            if ( rhs.RefID == -1 ) return true;

            // if on same reference, sort on position
            if ( lhs.RefID == rhs.RefID )
                return sort_helper(m_order, lhs.Position, rhs.Position);

            // otherwise sort on reference ID
            return sort_helper(m_order, lhs.RefID, rhs.RefID);
        }

        // used by BamMultiReader internals
        static inline bool UsesCharData(void) { return false; }

        // data members
        private:
            const Sort::Order m_order;
    };

    template<typename T>
    struct ByTag : public AlignmentSortBase {

        // ctor
        ByTag(const std::string& tag,
              const Sort::Order& order = Sort::AscendingOrder)
            : m_tag(tag)
            , m_order(order)
        { }

        // comparison function
        bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) {

            // force alignments without tag to end
            T lhsTagValue;
            T rhsTagValue;
            if ( !lhs.GetTag(m_tag, lhsTagValue) ) return false;
            if ( !rhs.GetTag(m_tag, rhsTagValue) ) return true;

            // otherwise compare on tag values
            return sort_helper(m_order, lhsTagValue, rhsTagValue);
        }

        // used by BamMultiReader internals
        static inline bool UsesCharData(void) { return true; }

        // data members
        private:
            const std::string m_tag;
            const Sort::Order m_order;
    };

    struct Unsorted : public AlignmentSortBase {

        // comparison function
        inline bool operator()(const BamTools::BamAlignment&, const BamTools::BamAlignment&) {
            return false;   // returning false tends to retain insertion order
        }

        // used by BamMultiReader internals
        static inline bool UsesCharData(void) { return false; }
    };

    template<typename Compare>
    static inline void SortAlignments(std::vector<BamAlignment>& data,
                                      const Compare& comp = Compare())
    {
        std::sort(data.begin(), data.end(), comp);
    }

    template<typename Compare>
    static inline std::vector<BamAlignment> SortAlignments(const std::vector<BamAlignment>& input,
                                                           const Compare& comp = Compare())
    {
        std::vector<BamAlignment> output(input);
        SortAlignments(output, comp);
        return output;
    }

    template<typename Compare>
    static std::vector<BamAlignment> GetSortedRegion(BamReader& reader,
                                                     const BamRegion& region,
                                                     const Compare& comp = Compare())
    {
        // return empty container if unable to find region
        if ( !reader.IsOpen() )          return std::vector<BamAlignment>();
        if ( !reader.SetRegion(region) ) return std::vector<BamAlignment>();

        // iterate through region, grabbing alignments
        BamAlignment al;
        std::vector<BamAlignment> results;
        while ( reader.GetNextAlignmentCore(al) )
            results.push_back(al);

        // sort & return alignments
        SortAlignments(results, comp);
        return results;
    }

    template<typename Compare>
    static std::vector<BamAlignment> GetSortedRegion(BamMultiReader& reader,
                                                     const BamRegion& region,
                                                     const Compare& comp = Compare())
    {
        // return empty container if unable to find region
        if ( !reader.HasOpenReaders() )  return std::vector<BamAlignment>();
        if ( !reader.SetRegion(region) ) return std::vector<BamAlignment>();

        // iterate through region, grabbing alignments
        BamAlignment al;
        std::vector<BamAlignment> results;
        while ( reader.GetNextAlignmentCore(al) )
            results.push_back(al);

        // sort & return alignments
        SortAlignments(results, comp);
        return results;
    }
};

} // namespace Algorithms
} // namespace BamTools

#endif // ALGORITHMS_SORT_H