// ==========================================================================
//                 SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2013, 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: David Weese <david.weese@fu-berlin.de>
// ==========================================================================

#ifndef SEQAN_HEADER_INDEX_MERGER7_H
#define SEQAN_HEADER_INDEX_MERGER7_H

namespace SEQAN_NAMESPACE_MAIN
{

//namespace SEQAN_NAMESPACE_PIPELINING
//{

	template <int I, typename T = void>
	struct SkewShift_;

	template <int I, typename T = void>
	struct SkewNIndex_;


	template <typename T>
	struct SkewShift_<7, T>
    {
		static const unsigned VALUE[7][7];
	};

	template <typename T>
	struct SkewNIndex_<7, T>
    {
		static const unsigned VALUE[7][7];
	};


	template <typename T>
	const unsigned SkewShift_<7, T>::VALUE[7][7] =
								  {{0,6,5,6,3,3,5},
                                   {6,0,0,6,0,4,4},
                                   {5,0,0,1,0,1,5},
                                   {6,6,1,0,2,1,2},
                                   {3,0,0,2,0,3,2},
                                   {3,4,1,1,3,0,4},
                                   {5,4,5,2,2,4,0}};


	template <typename T>
	const unsigned SkewNIndex_<7, T>::VALUE[7][7] =
								  {{0,0,0,0,0,1,2},
                                   {0,0,0,0,1,1,2},
                                   {0,1,1,1,1,2,2},
                                   {0,0,1,1,1,1,2},
                                   {0,0,1,2,2,2,2},
                                   {0,0,0,1,2,2,2},
                                   {0,0,0,0,1,2,2}};


    template <typename TValue>
    struct SkewDCStream
    {
        TValue      i;
        unsigned    stream;
    };
    
    template <typename TValue>
	std::ostream& operator<<(std::ostream &out, const SkewDCStream<TValue> &s)
    {
		out << "< " << s.i.i1 << " , [ ";
		for(unsigned i = 0; i < 3; ++i)
			out << s.i.i2[i] << " ";
		out << "] , [ ";
		for(unsigned i = 0; i < 6; ++i)
			out << s.i.i3[i] << " ";
		out << "] , " << s.stream << " >";
		return out;
	}


	// greater-operator for two SkewDCStreams
    template <typename TValue>
    struct CompareSkewDCStream :
        public ::std::binary_function < SkewDCStream<TValue>,
                                        SkewDCStream<TValue>,
                                        bool >
    {
        inline bool operator()(const SkewDCStream<TValue> &a,
			                   const SkewDCStream<TValue> &b) const 
        {
            typedef typename Value<TValue, 2>::Type     TNameTuple;
            typedef typename Value<TNameTuple>::Type    TName;

            int shft = SkewShift_<7>::VALUE[a.stream][b.stream];

            for (int i = 0; i < shft; ++i)
            {
                if (a.i.i3[i] < b.i.i3[i]) return false;
                if (a.i.i3[i] > b.i.i3[i]) return true;
            }
            
            TName na = a.i.i2[SkewNIndex_<7>::VALUE[a.stream][shft]];
            TName nb = b.i.i2[SkewNIndex_<7>::VALUE[b.stream][shft]];
            if (na < nb) return false;
            if (na > nb) return true;

			// we get here, only if a septet crosses the border of
			// the single text or a sequence in a multiple sequence text
			return a.stream - 1 > b.stream - 1; // this is NOT the same as a.stream > b.stream, 0 should be bigger than 6
        }
    };


	// greater-operator for two SkewDCStreams (optimized for bit-packed character tuples)
    template <typename T1, typename T2, typename T, unsigned SIZE>
    struct CompareSkewDCStream< Triple<T1, T2, Tuple<T, SIZE, BitPacked<> >, Pack> > :
        public ::std::binary_function < SkewDCStream<Triple<T1, T2, Tuple<T, SIZE, BitPacked<> >, Pack> >,
                                        SkewDCStream<Triple<T1, T2, Tuple<T, SIZE, BitPacked<> >, Pack> >,
                                        bool >
    {
        typedef Tuple<T,SIZE, BitPacked<> > T3;
        inline bool operator()(const SkewDCStream<Triple<T1, T2, T3, Pack> > &a,
			                   const SkewDCStream<Triple<T1, T2, T3, Pack> > &b) const 
        {
            typedef typename Value<T2>::Type TName;
            typedef typename Value<T3>::Type TValue3;
            
            int shft = SkewShift_<7>::VALUE[a.stream][b.stream];
            typename T3::TBitVector mask = ~((1 << ((SIZE - shft) * BitsPerValue<TValue3>::VALUE)) - 1);

            if ((a.i.i3.i & mask) < (b.i.i3.i & mask)) return false;
            if ((a.i.i3.i & mask) > (b.i.i3.i & mask)) return true;

            TName na = a.i.i2[SkewNIndex_<7>::VALUE[a.stream][shft]];
            TName nb = b.i.i2[SkewNIndex_<7>::VALUE[b.stream][shft]];
            if (na < nb) return false;
            if (na > nb) return true;

			// we get here, only if a septet crosses the border of
			// the single text or a sequence in a multiple sequence text
			return a.stream - 1 > b.stream - 1; // this is NOT the same as a.stream > b.stream, 0 should be bigger than 6
		}
    };




	struct Merger7;

    template < typename TInput0, typename TInput3, typename TInput5, typename TInput6, typename TInput124 >
    struct Value< Pipe< Bundle5< TInput0, TInput3, TInput5, TInput6, TInput124 >, Merger7 > >
    {
		typedef typename Value<TInput0>::Type       TInValue0;
        typedef typename Value<TInValue0, 1>::Type  Type;
    };


	template <typename TLimitsString>
	struct Merger7Multi;

    template < typename TInput0, typename TInput3, typename TInput5, typename TInput6, typename TInput124, typename TLimitsString >
    struct Value< Pipe< Bundle5< TInput0, TInput3, TInput5, TInput6, TInput124 >, Merger7Multi<TLimitsString> > >
    {
		typedef typename Value<TInput0>::Type       TInValue0;
        typedef typename Value<TInValue0, 1>::Type  Type;
    };


    //////////////////////////////////////////////////////////////////////////////
    // merger7 class
    template < typename TInput0, typename TInput3, typename TInput5, typename TInput6, typename TInput124 >
    struct Pipe< Bundle5< TInput0, TInput3, TInput5, TInput6, TInput124 >, Merger7 >
    {
        typedef typename Value<TInput0>::Type       TInValue0;
        typedef typename Value<TInput3>::Type       TInValue3;
        typedef typename Value<TInput5>::Type       TInValue5;
        typedef typename Value<TInput6>::Type       TInValue6;
        typedef typename Value<TInput124>::Type     TInValue124;
        typedef typename Size<Pipe>::Type           TSize;

        typedef typename Value<TInValue0, 3>::Type  TInTuple0;
//        typedef typename Value<TInTuple0>::Type     Type;

        typedef SkewDCStream<TInValue0>             TSkewDCStream;

		TSkewDCStream								inValue[7];
		unsigned									rank[5];
		unsigned									first;
        CompareSkewDCStream<TInValue0>				streamGreater;

        Bundle5 <
            TInput0,
            TInput3,
            TInput5,
            TInput6,
            TInput124 > in;
        TSize N;
        
        Pipe(Bundle5< TInput0, TInput3, TInput5, TInput6, TInput124 > _in):
            in(_in) {}

        template <typename T1, typename T2, typename T3>
        inline static void _copy(TSkewDCStream &dst, Triple<T1,T2,T3, Pack> const &src)
        {
            memcpy(&dst.i.i2, &src.i2, sizeof(T2));
            memcpy(&dst.i.i3, &src.i3, sizeof(T3));
        }

        template <typename T1, typename T2, typename T, unsigned SIZE>
        inline static void _copy(TSkewDCStream &dst, Triple<T1,T2,Tuple<T,SIZE, BitPacked<> >, Pack> const &src)
		{
			typedef typename Value<TInValue0, 3>::Type TCharTuple;
            memcpy(&dst.i.i2, &src.i2, sizeof(T2));
            dst.i.i3 = src.i3;
            dst.i.i3 <<= LENGTH<TCharTuple>::VALUE - SIZE;
        }

        inline typename Value<Pipe>::Type const operator*()
        {
            return getValueI1(inValue[rank[first]].i);
        }

		inline void insertStream(unsigned stream)
        {
            switch (stream) {
                case 0:
					if (eof(in.in1)) {
						++first;
						return;
					}
					inValue[0].i.i1 = N - (*in.in1).i1;
					_copy(inValue[0], *in.in1);
					++in.in1;
                    break;

                case 3:
					if (eof(in.in2)) {
						++first;
						return;
					}
					inValue[3].i.i1 = N - (*in.in2).i1;
					_copy(inValue[3], *in.in2);
					++in.in2;
                    break;

                case 5:
					if (eof(in.in3)) {
						++first;
						return;
					}
					inValue[5].i.i1 = N - (*in.in3).i1;
					_copy(inValue[5], *in.in3);
					++in.in3;
                    break;

                case 6:
					if (eof(in.in4)) {
						++first;
						return;
					}
					inValue[6].i.i1 = N - (*in.in4).i1;
					_copy(inValue[6], *in.in4);
					++in.in4;
					break;

				default:	// case 1, 2, or 4
					if (eof(in.in5)) {
						++first;
						return;
					}
					// calculate residue class from the suffix length
					inValue[1].stream = (*in.in5).i1 % 7;
					inValue[1].i.i1 = N - (*in.in5).i1;
					_copy(inValue[1], *in.in5);
					++in.in5;
            }

			// linear search
			int right;
			for(right = first + 1;  right < 5;  ++right)
				if (!streamGreater(inValue[stream],inValue[rank[right]])) break;

			// remove the least suffix ...
			for(int i = first + 1;  i < right;  ++i)
				rank[i-1] = rank[i];

			// ... and insert the new one
			rank[right-1] = stream;
		}
        
        Pipe& operator++()
        {
			insertStream(rank[first]);
            return *this;
        }

        void fill()
        {
			inValue[0].stream = 0;
			inValue[3].stream = 3;
			inValue[5].stream = 5;
			inValue[6].stream = 6;

			first = 4;	insertStream(0);
			--first;    insertStream(3);
			--first;    insertStream(5);
			--first;    insertStream(6);
			--first;	insertStream(1);
        }
	};
    

    //////////////////////////////////////////////////////////////////////////////
    // merger7 class for multiple sequences
    template < typename TInput0, typename TInput3, typename TInput5, typename TInput6, typename TInput124, typename TLimitsString >
    struct Pipe< Bundle5< TInput0, TInput3, TInput5, TInput6, TInput124 >, Merger7Multi<TLimitsString> >
    {
        typedef typename Value<TInput0>::Type       TInValue0;
        typedef typename Value<TInput3>::Type       TInValue3;
        typedef typename Value<TInput5>::Type       TInValue5;
        typedef typename Value<TInput6>::Type       TInValue6;
        typedef typename Value<TInput124>::Type     TInValue124;
        typedef typename Size<Pipe>::Type           TSize;

        typedef typename Value<TInValue0, 3>::Type  TInTuple0;
//        typedef typename Value<TInTuple0>::Type     Type;

        typedef SkewDCStream<TInValue0>             TSkewDCStream;

		TSkewDCStream								inValue[7];
		unsigned									rank[5];
		unsigned									first;
        CompareSkewDCStream<TInValue0>				streamGreater;

        Bundle5 <
            TInput0,
            TInput3,
            TInput5,
            TInput6,
            TInput124 > in;
		TLimitsString const &limits;
        
        Pipe(Bundle5< TInput0, TInput3, TInput5, TInput6, TInput124 > _in, TLimitsString const &_limits):
            in(_in),
			limits(_limits) {}

        template <typename T1, typename T2, typename T3>
        inline static void _copy(TSkewDCStream &dst, Triple<T1,T2,T3, Pack> const &src)
        {
            memcpy(&dst.i.i1, &src.i1, sizeof(T1));
            memcpy(&dst.i.i2, &src.i2, sizeof(T2));
            memcpy(&dst.i.i3, &src.i3, sizeof(T3));
        }

        template <typename T1, typename T2, typename T, unsigned SIZE>
        inline static void _copy(TSkewDCStream &dst, Triple<T1,T2,Tuple<T,SIZE, BitPacked<> >, Pack> const &src)
		{
			typedef typename Value<TInValue0, 3>::Type TCharTuple;
            memcpy(&dst.i.i1, &src.i1, sizeof(T1));
            memcpy(&dst.i.i2, &src.i2, sizeof(T2));
            dst.i.i3 = src.i3;
            dst.i.i3 <<= LENGTH<TCharTuple>::VALUE - SIZE;
        }

        inline typename Value<Pipe>::Type const operator*()
        {
            return getValueI1(inValue[rank[first]].i);
        }

		inline void insertStream(unsigned stream)
        {
            switch (stream) {
                case 0:
					if (eof(in.in1)) {
						++first;
						return;
					}
					_copy(inValue[0], *in.in1);
					++in.in1;
                    break;

                case 3:
					if (eof(in.in2)) {
						++first;
						return;
					}
					_copy(inValue[3], *in.in2);
					++in.in2;
                    break;

                case 5:
					if (eof(in.in3)) {
						++first;
						return;
					}
					_copy(inValue[5], *in.in3);
					++in.in3;
                    break;

                case 6:
					if (eof(in.in4)) {
						++first;
						return;
					}
					_copy(inValue[6], *in.in4);
					++in.in4;
					break;

				default:	// case 1, 2, or 4
					if (eof(in.in5)) {
						++first;
						return;
					}
					// calculate residue class from the suffix length
					typename Value<TInValue124,1>::Type in_in5_i1 = getValueI1(*in.in5);
					unsigned seqNo = getValueI1(in_in5_i1);
					inValue[1].stream = ((limits[seqNo + 1] - limits[seqNo]) - getValueI2(in_in5_i1)) % 7;

					_copy(inValue[1], *in.in5);
					++in.in5;
            }

			// linear search
			int right;
			for(right = first + 1;  right < 5;  ++right)
				if (!streamGreater(inValue[stream],inValue[rank[right]])) break;

			// remove the least suffix ...
			for(int i = first + 1;  i < right;  ++i)
				rank[i-1] = rank[i];

			// ... and insert the new one
			rank[right-1] = stream;
		}
        
        Pipe& operator++()
        {
			insertStream(rank[first]);
            return *this;
        }

        void fill()
        {
			inValue[0].stream = 0;
			inValue[3].stream = 3;
			inValue[5].stream = 5;
			inValue[6].stream = 6;

			first = 4;	insertStream(0);
			--first;    insertStream(3);
			--first;    insertStream(5);
			--first;    insertStream(6);
			--first;	insertStream(1);
        }
	};
    

    //////////////////////////////////////////////////////////////////////////////
    // global pipe functions
    template < typename TInput >
	inline bool control(Pipe< TInput, Merger7 > &me, ControlBeginRead const &command)
    {
        if (!control(me.in, command)) return false;
        me.N = length(me);
        me.fill();
		return true;
	}
    
    template < typename TInput >
	inline bool control(Pipe< TInput, Merger7 > &me, ControlEof const &)
    {
		return me.first == 5;
    }

    template < typename TInput >
	inline bool control(Pipe< TInput, Merger7 > &me, ControlEos const &)
    {
		return control(me, ControlEof());
    }

    template < typename TInput >
    inline typename Size< Pipe< TInput, Merger7 > >::Type
    length(Pipe< TInput, Merger7 > const &me)
    {
        return length(me.in.in1) +
               length(me.in.in2) + 
               length(me.in.in3) +
               length(me.in.in4) +
               length(me.in.in5);
    }




    template < typename TInput, typename TLimitsString >
	inline bool control(Pipe< TInput, Merger7Multi<TLimitsString> > &me, ControlBeginRead const &command)
    {
        if (!control(me.in, command)) return false;
        me.fill();
		return true;
	}
    
    template < typename TInput, typename TLimitsString >
	inline bool control(Pipe< TInput, Merger7Multi<TLimitsString> > &me, ControlEof const &)
    {
		return me.first == 5;
    }

    template < typename TInput, typename TLimitsString >
	inline bool control(Pipe< TInput, Merger7Multi<TLimitsString> > &me, ControlEos const &)
    {
		return control(me, ControlEof());
    }

    template < typename TInput, typename TLimitsString >
    inline typename Size< Pipe< TInput, Merger7Multi<TLimitsString> > >::Type
    length(Pipe< TInput, Merger7Multi<TLimitsString> > const &me) {
        return length(me.in.in1) +
               length(me.in.in2) + 
               length(me.in.in3) +
               length(me.in.in4) +
               length(me.in.in5);
    }

//}

}

#endif
