// ==========================================================================
// SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2018, Knut Reinert, FU Berlin
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// * Neither the name of Knut Reinert or the FU Berlin nor the names of
// its contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.
//
// ==========================================================================
// Author: Rene Rahn <rene.rahn@fu-berlin.de>
// ==========================================================================
//
// The TraceSegment structure is used to store the traceback in a common
// structure such that we can easiely adapt them afterwards in the
// user-defined structure, such as Align or AlignmentGraph objects.
// ==========================================================================
#ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_
#define SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_
namespace seqan {
// ============================================================================
// Forwards
// ============================================================================
// ============================================================================
// Tags, Classes, Enums
// ============================================================================
// ----------------------------------------------------------------------------
// Class TraceSegment
// ----------------------------------------------------------------------------
// TraceSegments are used as a common interface to all structures that can represent an alignment.
//
// See alignment_dp_traceback_adaptor.h to find methods for adaption.
template <typename TPosition, typename TSize>
class TraceSegment_
{
public:
typedef typename TraceBitMap_<>::Type TTraceValue;
TPosition _horizontalBeginPos; // the begin position in horizontal dimension
TPosition _verticalBeginPos; // the begin position in vertical dimension
TSize _length; // the length of the segment
TTraceValue _traceValue; // the trace direction
TraceSegment_() :
_horizontalBeginPos(0), _verticalBeginPos(0), _length(0), _traceValue(TraceBitMap_<TTraceValue>::NONE){}
TraceSegment_(TraceSegment_ const & other) :
_horizontalBeginPos(other._horizontalBeginPos),
_verticalBeginPos(other._verticalBeginPos),
_length(other._length),
_traceValue(other._traceValue) {}
TraceSegment_(TPosition const & horizontalBeginPos, TPosition const & verticalBeginPos, TSize const & length,
TTraceValue const & traceValue) :
_horizontalBeginPos(horizontalBeginPos),
_verticalBeginPos(verticalBeginPos),
_length(length),
_traceValue(traceValue) {}
TraceSegment_ &
operator=(TraceSegment_ const & other)
{
if (this != &other)
{
_horizontalBeginPos = other._horizontalBeginPos;
_verticalBeginPos = other._verticalBeginPos;
_length = other._length;
_traceValue = other._traceValue;
}
return *this;
}
};
// ============================================================================
// Metafunctions
// ============================================================================
// ----------------------------------------------------------------------------
// Metafunction Position
// ----------------------------------------------------------------------------
template <typename TPosition, typename TSize>
struct Position<TraceSegment_<TPosition, TSize> >
{
typedef TPosition Type;
};
template <typename TPosition, typename TSize>
struct Position<TraceSegment_<TPosition, TSize> const>:
Position<TraceSegment_<TPosition, TSize> >{};
// ----------------------------------------------------------------------------
// Metafunction Size
// ----------------------------------------------------------------------------
template <typename TPosition, typename TSize>
struct Size<TraceSegment_<TPosition, TSize> >
{
typedef TSize Type;
};
template <typename TPosition, typename TSize>
struct Size<TraceSegment_<TPosition, TSize> const>:
Size<TraceSegment_<TPosition, TSize> >{};
// ============================================================================
// Functions
// ============================================================================
// ----------------------------------------------------------------------------
// Function _getBeginHorizontal()
// ----------------------------------------------------------------------------
// The begin position of the segment in horizontal dimension.
template <typename TPosition, typename TSize>
inline TPosition
_getBeginHorizontal(TraceSegment_<TPosition, TSize> const & traceSegment)
{
return traceSegment._horizontalBeginPos;
}
// ----------------------------------------------------------------------------
// Function _getBeginVertical()
// ----------------------------------------------------------------------------
// The begin position of the segment in vertical dimension.
template <typename TPosition, typename TSize>
inline TPosition
_getBeginVertical(TraceSegment_<TPosition, TSize> const & traceSegment)
{
return traceSegment._verticalBeginPos;
}
// ----------------------------------------------------------------------------
// Function _getEndHorizontal()
// ----------------------------------------------------------------------------
// The end position of the segment in horizontal dimension.
template <typename TPosition, typename TSize>
inline TPosition
_getEndHorizontal(TraceSegment_<TPosition, TSize> const & traceSegment)
{
typedef typename std::remove_const<decltype(traceSegment._traceValue)>::type TTraceValue;
if (traceSegment._traceValue & (TraceBitMap_<TTraceValue>::HORIZONTAL | TraceBitMap_<TTraceValue>::DIAGONAL))
{
return traceSegment._horizontalBeginPos + traceSegment._length;
}
return traceSegment._horizontalBeginPos;
}
// ----------------------------------------------------------------------------
// Function _getEndVertical()
// ----------------------------------------------------------------------------
// The end position of the segment in vertical dimension.
template <typename TPosition, typename TSize>
inline TPosition
_getEndVertical(TraceSegment_<TPosition, TSize> const & traceSegment)
{
typedef typename std::remove_const<decltype(traceSegment._traceValue)>::type TTraceValue;
if (traceSegment._traceValue & (TraceBitMap_<TTraceValue>::VERTICAL | TraceBitMap_<TTraceValue>::DIAGONAL))
{
return traceSegment._verticalBeginPos + traceSegment._length;
}
return traceSegment._verticalBeginPos;
}
// ----------------------------------------------------------------------------
// Function _getTraceValue()
// ----------------------------------------------------------------------------
// The end position of the segment in vertical dimension.
template <typename TPosition, typename TSize>
inline typename TraceSegment_<TPosition, TSize>::TTraceValue
_getTraceValue(TraceSegment_<TPosition, TSize> const & traceSegment)
{
return traceSegment._traceValue;
}
// ----------------------------------------------------------------------------
// Function length()
// ----------------------------------------------------------------------------
// The length of the segment.
template <typename TPosition, typename TSize>
inline TSize
length(TraceSegment_<TPosition, TSize> const & traceSegment)
{
return traceSegment._length;
}
// ----------------------------------------------------------------------------
// Function _setLength()
// ----------------------------------------------------------------------------
// The length of the segment.
template <typename TPosition, typename TSize>
inline void
_setLength(TraceSegment_<TPosition, TSize> & traceSegment, TSize newLength)
{
traceSegment._length = newLength;
}
// ----------------------------------------------------------------------------
// Function _translateTraceValue()
// ----------------------------------------------------------------------------
// Translates the trace value into a human-readable format.
//
// Note, used for debugging reasons only.
template <typename TTraceValue>
String<char> _translateTraceValue(TTraceValue const & traceValue)
{
String<char> transcript;
if ((traceValue & TraceBitMap_<TTraceValue>::DIAGONAL) == TraceBitMap_<TTraceValue>::DIAGONAL)
append(transcript, 'D');
if ((traceValue & TraceBitMap_<TTraceValue>::VERTICAL) == TraceBitMap_<TTraceValue>::VERTICAL)
append(transcript, 'V');
if ((traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL) == TraceBitMap_<TTraceValue>::HORIZONTAL)
append(transcript, 'H');
if ((traceValue & TraceBitMap_<TTraceValue>::VERTICAL_OPEN) == TraceBitMap_<TTraceValue>::VERTICAL_OPEN)
append(transcript, 'v');
if ((traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL_OPEN) == TraceBitMap_<TTraceValue>::HORIZONTAL_OPEN)
append(transcript, 'h');
if ((traceValue & TraceBitMap_<TTraceValue>::MAX_FROM_VERTICAL_MATRIX) == TraceBitMap_<TTraceValue>::MAX_FROM_VERTICAL_MATRIX)
append(transcript, '|');
if ((traceValue & TraceBitMap_<TTraceValue>::MAX_FROM_HORIZONTAL_MATRIX) == TraceBitMap_<TTraceValue>::MAX_FROM_HORIZONTAL_MATRIX)
append(transcript, '-');
if ((traceValue) == TraceBitMap_<TTraceValue>::NONE)
append(transcript, '0');
return transcript;
}
// ----------------------------------------------------------------------------
// Function oerpator<<()
// ----------------------------------------------------------------------------
template <typename TStream, typename TSize, typename TPosition>
TStream & operator<<(TStream & stream, TraceSegment_<TSize, TPosition> const & traceSegment)
{
stream << _translateTraceValue(traceSegment._traceValue) << "-";
stream << "(" << traceSegment._horizontalBeginPos << ", " << traceSegment._verticalBeginPos << ", " <<
traceSegment._length << ")";
return stream;
}
// ----------------------------------------------------------------------------
// Function oerpator==()
// ----------------------------------------------------------------------------
template <typename TPosition, typename TSize>
inline bool operator==(TraceSegment_<TPosition, TSize> const & left, TraceSegment_<TPosition, TSize> const & right)
{
if (left._horizontalBeginPos != right._horizontalBeginPos)
return false;
if (left._verticalBeginPos != right._verticalBeginPos)
return false;
if (left._length != right._length)
return false;
if (left._traceValue != right._traceValue)
return false;
return true;
}
// ----------------------------------------------------------------------------
// Function oerpator!=()
// ----------------------------------------------------------------------------
template <typename TPosition, typename TSize>
inline bool operator!=(TraceSegment_<TPosition, TSize> const & left, TraceSegment_<TPosition, TSize> const & right)
{
return !(left == right);
}
// ----------------------------------------------------------------------------
// Function recordSegment()
// ----------------------------------------------------------------------------
// Records a segment given the horizontal and vertical begin position, the length,
// and the corrsponding trace value.
//
// The first parameter is the container the segment is recorded to.
template <typename TTraceSegments, typename TPositionH, typename TPositionV, typename TSize, typename TTraceValue>
inline void _recordSegment(TTraceSegments & traceSegments,
TPositionH const & horizontalBeginPos,
TPositionV const & verticalBeginPos,
TSize const & segmentLength,
TTraceValue const & traceValue)
{
typedef typename Value<TTraceSegments>::Type TTraceSegment;
if (segmentLength == 0)
return; // we don't store empty segments
if (traceValue & TraceBitMap_<TTraceValue>::DIAGONAL)
appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::DIAGONAL));
else if (traceValue & TraceBitMap_<TTraceValue>::VERTICAL)
appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::VERTICAL));
else if (traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL)
appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::HORIZONTAL));
// everything else is not tracked.
}
} // namespace seqan
#endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_
