libMems/AbstractMatch.h

Go to the documentation of this file.

/*******************************************************************************
 * $Id: AbstractMatch.h,v 1.8 2004/02/27 23:08:55 darling Exp $
 * This file is copyright 2002-2007 Aaron Darling and authors listed in the AUTHORS file.
 * This file is licensed under the GPL.
 * Please see the file called COPYING for licensing details.
 * **************
 ******************************************************************************/

#ifndef __AbstractMatch_h__
#define __AbstractMatch_h__

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "libGenome/gnClone.h"
#include <vector>
#include <algorithm>
#include <boost/type_traits/remove_pointer.hpp>
#include <boost/type_traits/add_pointer.hpp>
#include <boost/dynamic_bitset.hpp>
#include <libMems/SlotAllocator.h>
#include <libMems/configuration.h>

namespace mems {

static const gnSeqI NO_MATCH = 0;


#ifdef WIN32 

//#define _USE_BOOST_MATCH_ALLOCATOR
//typedef boost::dynamic_bitset<unsigned, boost::pool_allocator<unsigned> > bitset_t;

// slot allocator turns out to have the fastest new/free implementation for single object allocations
#define _USE_SLOT_ALLOCATOR
#else
#define _USE_SLOT_ALLOCATOR
#endif
typedef boost::dynamic_bitset<> bitset_t;

#ifdef _USE_SLOT_ALLOCATOR
#include "libMems/SlotAllocator.h"
#elif defined(_USE_BOOST_MATCH_ALLOCATOR)
#include <boost/pool/pool_alloc.hpp>
#endif

template< typename T >
T* m_allocateAndCopy( const T& t )
{
#ifdef _USE_SLOT_ALLOCATOR
        SlotAllocator<T>& sat = SlotAllocator<T>::GetSlotAllocator();
        T* newt = sat.Allocate();
        newt = new(newt) T(t);  // construct a new T at the address given by newt
//      *newt = t;
        return newt;
#elif defined(_USE_BOOST_MATCH_ALLOCATOR)
        boost::fast_pool_allocator< T > fpa;
        T* newt = boost::fast_pool_allocator< T >::allocate();
        fpa.construct(newt, t);
        return newt;
#else
        return new T(t);
#endif
}

template< typename T >
void m_free( T* t )
{
#ifdef _USE_SLOT_ALLOCATOR
        SlotAllocator<T>& sat = SlotAllocator<T>::GetSlotAllocator();
        sat.Free(t);
#elif defined(_USE_BOOST_MATCH_ALLOCATOR)
        boost::fast_pool_allocator< T > fpa;
        fpa.destroy(t);
        boost::fast_pool_allocator< T >::deallocate(t);
#else
        delete t;
#endif
}

class AbstractMatch : public genome::gnClone {
public:
        
        enum orientation {
                forward,        
                reverse,        
                undefined       
        };

        virtual AbstractMatch* Copy() const = 0;

        virtual void Free() = 0;
        
        virtual gnSeqI Length( uint seqI ) const = 0;

        virtual void SetLength( gnSeqI len, uint seqI ) = 0;

        virtual int64 Start(uint startI) const = 0;

        virtual void SetStart(uint seqI, int64 start) = 0;

        int64 operator[](uint seqI) const{return Start(seqI);}  // this is a synonym for Start()

        virtual int64 End(uint seqI) const;

        virtual gnSeqI LeftEnd(uint seqI) const = 0;

        virtual gnSeqI RightEnd(uint seqI) const{ return LeftEnd(seqI) + Length( seqI ) - 1; };

        virtual orientation Orientation(uint seqI) const = 0;

        virtual void SetLeftEnd(uint seqI, gnSeqI start) = 0;

        virtual void SetOrientation(uint seqI, orientation o) = 0;

        virtual void MoveStart(int64 move_amount) = 0;
        virtual void MoveEnd(int64 move_amount) = 0;

        virtual uint Multiplicity() const = 0;

        virtual uint SeqCount() const = 0;

        virtual uint FirstStart() const = 0;
        
        virtual gnSeqI AlignmentLength() const = 0;

        virtual void Invert() = 0;
        
        //warning:  none of the following do bounds checking.
        virtual void CropStart(gnSeqI crop_amount) = 0;
        virtual void CropEnd(gnSeqI crop_amount) = 0;

        virtual void CropLeft(gnSeqI crop_amount, uint seqI) = 0;
        virtual void CropRight(gnSeqI crop_amount, uint seqI) = 0;
        
//      virtual AbstractMatch* Split( gnSeqI before_column ) = 0;

        virtual void GetAlignment( std::vector< bitset_t >& align_matrix ) const = 0;

        virtual void GetColumn( gnSeqI col, std::vector<gnSeqI>& pos, std::vector<bool>& column ) const = 0;

//      gnSeqI SeqPosToColumn( uint seq, int64 pos) const = 0;
        virtual bool IsGap( uint seq, gnSeqI col ) const = 0;
        virtual uint UsedSeq( uint seqI ) const = 0;
};

inline
int64 AbstractMatch::End(uint endI) const
{
        if( Start(endI) > 0 )
                return Start(endI) + Length(endI) - 1;
        return Start(endI);
}


template< typename MatchType >
class AbstractMatchStartComparator {
public:
        AbstractMatchStartComparator( unsigned seq = 0 ){
                m_seq = seq;
        }
        AbstractMatchStartComparator( const AbstractMatchStartComparator& msc ){
                m_seq = msc.m_seq;
        }
        AbstractMatchStartComparator<MatchType>& operator=( const AbstractMatchStartComparator<MatchType>& msc )
        {
                m_seq = msc.m_seq;
        }
        // TODO??  make this do a wraparound comparison if all is equal?
        boolean operator()(const MatchType& a, const MatchType& b) const{
                int start_diff = std::max( a.FirstStart(), m_seq ) - std::max( a.FirstStart(), m_seq );
                if(start_diff == 0){
                        uint m_count = a.SeqCount();
                        m_count = m_count <= b.SeqCount() ? m_count : b.SeqCount();
                        for(uint seqI = m_seq; seqI < m_count; seqI++){
                                gnSeqI a_start = a.Orientation(seqI) == AbstractMatch::forward ? a.LeftEnd( seqI ) : a.RightEnd( seqI );
                                gnSeqI b_start = b.Orientation(seqI) == AbstractMatch::forward ? b.LeftEnd( seqI ) : b.RightEnd( seqI );
                                int64 diff = a_start - b_start;
                                if(a_start == NO_MATCH || b_start == NO_MATCH)
                                        continue;
                                else if(a_start == b_start)
                                        continue;
                                else
                                        return a_start < b_start;
                        }
                }
                return start_diff < 0;
        }
private:
        unsigned m_seq;
};

template< typename MatchType >
class AbstractMatchSingleStartComparator {
public:
        AbstractMatchSingleStartComparator( unsigned seq = 0 ){
                m_seq = seq;
        }
        AbstractMatchSingleStartComparator( const AbstractMatchSingleStartComparator& msc ){
                m_seq = msc.m_seq;
        }
        AbstractMatchSingleStartComparator<MatchType>& operator=( const AbstractMatchSingleStartComparator<MatchType>& msc )
        {
                m_seq = msc.m_seq;
        }
        boolean operator()(const MatchType& a, const MatchType& b) const{
                int64 a_start = a.LeftEnd( m_seq ), b_start = b.LeftEnd( m_seq );
                if( a_start == NO_MATCH || b_start == NO_MATCH ){
                        if( b_start != NO_MATCH )
                                return true;
                        return false;
                }

                return a_start < b_start;
        }
private:
        unsigned m_seq;
};



template< typename MatchType >
class MatchStartComparator {
public:
        MatchStartComparator( unsigned seq = 0 ){
                m_seq = seq;
        }
        MatchStartComparator( const MatchStartComparator& msc ){
                m_seq = msc.m_seq;
        }
        MatchStartComparator<MatchType>& operator=( const MatchStartComparator<MatchType>& msc )
        {
                m_seq = msc.m_seq;
        }
        // TODO??  make this do a wraparound comparison if all is equal?
        boolean operator()(const MatchType* a, const MatchType* b) const{
                int start_diff = std::max( a->FirstStart(), m_seq ) - std::max( a->FirstStart(), m_seq );
                if(start_diff == 0){
                        uint m_count = a->SeqCount();
                        m_count = m_count <= b->SeqCount() ? m_count : b->SeqCount();
                        for(uint seqI = m_seq; seqI < m_count; seqI++){
                                gnSeqI a_start = a->Orientation(seqI) == AbstractMatch::forward ? a->LeftEnd( seqI ) : a->RightEnd( seqI );
                                gnSeqI b_start = b->Orientation(seqI) == AbstractMatch::forward ? b->LeftEnd( seqI ) : b->RightEnd( seqI );
                                int64 diff = a_start - b_start;
                                if(a_start == NO_MATCH || b_start == NO_MATCH)
                                        continue;
                                else if(a_start == b_start)
                                        continue;
                                else
                                        return a_start < b_start;
                        }
                }
                return start_diff < 0;
        }
private:
        unsigned m_seq;
};

template< typename MatchType >
class SingleStartComparator {
public:
        SingleStartComparator( unsigned seq = 0 ){
                m_seq = seq;
        }
        SingleStartComparator( const SingleStartComparator& msc ){
                m_seq = msc.m_seq;
        }
        SingleStartComparator<MatchType>& operator=( const SingleStartComparator<MatchType>& msc )
        {
                m_seq = msc.m_seq;
        }
        boolean operator()(const MatchType* a, const MatchType* b) const{
                int64 a_start = a->LeftEnd( m_seq ), b_start = b->LeftEnd( m_seq );
                if( a_start == NO_MATCH || b_start == NO_MATCH ){
                        if( b_start != NO_MATCH )
                                return true;
                        return false;
                }

                return a_start < b_start;
        }
private:
        unsigned m_seq;
};


template< typename MatchType >
class SSC {
public:
        SSC( unsigned seq = 0 ){
                m_seq = seq;
        }
        SSC( const SSC<MatchType>& msc ){
                m_seq = msc.m_seq;
        }
        SSC<MatchType>& operator=( const SSC<MatchType>& msc )
        {
                m_seq = msc.m_seq;
        }
        boolean operator()( const typename boost::add_pointer<MatchType>::type& a, 
                const typename boost::add_pointer<MatchType>::type& b) const
        {
                return operator()(*a,*b);
        }
        boolean operator()(const typename boost::remove_pointer<MatchType>::type& a, 
                const typename boost::remove_pointer<MatchType>::type& b) const{
                int64 a_start = a.LeftEnd( m_seq ), b_start = b.LeftEnd( m_seq );
                if( a_start == NO_MATCH || b_start == NO_MATCH ){
                        if( b_start != NO_MATCH )
                                return true;
                        return false;
                }

                return a_start < b_start;
        }
private:
        unsigned m_seq;
};

}

#endif // __AbstractMatch_h__

---