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 <algorithm>
#include <cassert>
#include <functional>
#include <string>
#include <vector>
#include "api/BamAlignment.h"
#include "api/BamMultiReader.h"
#include "api/BamReader.h"
#include "api/api_global.h"
 
namespace BamTools {
namespace Algorithms {
 
struct API_EXPORT Sort
{
 
    enum Order
    {
        AscendingOrder = 0,
        DescendingOrder
    };
 
    template <typename ElemType>
    static 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
    }
 
    struct ByName
    {
 
        // ctor
        ByName(const Sort::Order& order = Sort::AscendingOrder)
            : m_order(order)
        {}
 
        // comparison function
        bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) const
        {
            return sort_helper(m_order, lhs.Name, rhs.Name);
        }
 
        // used by BamMultiReader internals
        static bool UsesCharData()
        {
            return true;
        }
 
        // data members
    private:
        const Sort::Order m_order;
    };
 
    struct ByPosition
    {
 
        // ctor
        ByPosition(const Sort::Order& order = Sort::AscendingOrder)
            : m_order(order)
        {}
 
        // comparison function
        bool operator()(const BamTools::BamAlignment& lhs, const BamTools::BamAlignment& rhs) const
        {
 
            // 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 bool UsesCharData()
        {
            return false;
        }
 
        // data members
    private:
        const Sort::Order m_order;
    };
 
    template <typename T>
    struct ByTag
    {
 
        // 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) const
        {
 
            // 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 bool UsesCharData()
        {
            return true;
        }
 
        // data members
    private:
        const std::string m_tag;
        const Sort::Order m_order;
    };
 
    struct Unsorted
    {
 
        // comparison function
        bool operator()(const BamTools::BamAlignment&, const BamTools::BamAlignment&) const
        {
            return false;  // returning false tends to retain insertion order
        }
 
        // used by BamMultiReader internals
        static bool UsesCharData()
        {
            return false;
        }
    };
 
    template <typename Compare>
    static void SortAlignments(std::vector<BamAlignment>& data, const Compare& comp = Compare())
    {
        std::sort(data.begin(), data.end(), comp);
    }
 
    template <typename Compare>
    static 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