module combine;

import std.stdio;

import std.conv;
import std.traits;
import std.range;
import std.typetuple;

import autoRefTuple;

template staticIota( int start, int end, int step = 1 ) {
	static if ( start + step <= end ) {
		alias TypeTuple!( start, staticIota!( start + step, end, step ) ) staticIota;
	} else {
		alias TypeTuple!() staticIota;
	}
}

struct Combiner( R... ) if ( allSatisfy!( isForwardRange, R ) ) {
	struct CombinerImpl {
		R ranges_orig,
				ranges;
		ulong[R.length] pos;
		int[R.length] lockedStack;
		int lastLocked;
		alias staticIota!( 0, R.length ) rangeIndices;
		
		void popFrontRange( int i ) {
			switch ( i ) {
				foreach ( e; rangeIndices ) {
					case e:
						ranges[ e ].popFront( );
						pos[ e ]++;
						return;
				}
				default:
					assert( false );
			}
		}
		
		void pushLocked( int index ) {
			lockedStack[++lastLocked] = index;
		}
		
		int popLocked( ) {
			lastLocked--;
			return lockedStack[lastLocked+1];
		}
		
		int firstUnlocked( ) {
			foreach ( i; rangeIndices ) {
				if ( isLocked( i ) ) {
					break;
				}
				return i;
			}
			return -1;
		}
		
		int unlockedAfter( int i ) {
			foreach ( j; i+1..R.length ) {
				if ( !isLocked( j ) ) {
					return j;
				}
			}
			foreach ( j; 0..i ) {
				if ( !isLocked( j ) ) {
					return j;
				}
			}
			return -1;
		}
		
		bool isLocked( int i ) {
			foreach ( j; 0..lastLocked+1 ) {
				if ( lockedStack[j] == i ) {
					return true;
				}
			}
			return false;
		}
		
		bool rangeEmpty( int i ) {
			switch ( i ) {
				foreach ( e; rangeIndices ) {
					case e:
						return ranges[ e ].empty;
				}
				default:
					assert( false );
			}
		}
		
		bool movedEnough( int current ) {
			if ( rangeEmpty( current ) ) {
				return true;
			} else if ( lastLocked == -1 ) {
				return true;
			} else if ( current > lockedStack[lastLocked] ) {
				return pos[current] >= pos[lockedStack[lastLocked]];
			} else {
				return pos[current] >= pos[lockedStack[lastLocked]] -1;
			}
		}

		int lastUnlocked( ) {
			int result = -1;
			foreach ( i; rangeIndices ) {
				if ( !isLocked( i ) ) {
					result = i;
				}
			}
			return result;
		}
		
		void resetUnlocked( ) {
			foreach ( i; rangeIndices ) {
				if ( !isLocked( i ) ) {
					ranges[i] = ranges_orig[i].save( );
					pos[i] = 0;
				}
			}
		}
		
		void popFront( ) {
			int currentRange = 0;
			if ( lastLocked == R.length ) {
				currentRange = firstUnlocked( );
			} else {
				while ( movedEnough( currentRange ) ) {
					currentRange = popLocked( );
					if ( ( currentRange != lastUnlocked( ) ) || ( lastLocked == -1 ) ) {
						currentRange = unlockedAfter( currentRange );
						break;
					}
				}
			}
			
			popFrontRange( currentRange );
			pushLocked( currentRange );
			
			resetUnlocked( );
		}
	}
	
	CombinerImpl Combiner;
	alias AutoRefTuple!R ElementTuple;
	
	this( R rs ) {
		foreach ( i, e; rs ) {
			Combiner.ranges_orig[i] = e.save( );
			Combiner.ranges[i] = e.save( );
		}
		Combiner.pos[] = 0;
		Combiner.lockedStack[] = 0;
		Combiner.lastLocked = -1;
		Combiner.pushLocked( 0 );
	}
	
	@property
	bool empty( ) const {
		foreach ( e; Combiner.ranges ) {
			if ( e.empty ) {
				return true;
			}
		}
		return false;
	}
	
	@property 
	ElementTuple front( ) {
		return ElementTuple( Combiner.ranges );
	}
	
	void popFront( ) {
		Combiner.popFront( );
	}
}

auto combine( R... )( R ranges ) if ( allSatisfy!( isForwardRange, R ) ) {
	static if ( R.length == 1 ) {
		return ranges[0];
	} else {
		return Combiner!R( ranges );
	}
}

void main( ) {
	auto o = take( combine( [1,2], "ab" ), 10 );
	foreach ( e; o ) {
		writeln( e );
	}
	writeln( "======================================" );
	
	o = take( combine( [1,2,3], "abc" ), 10 );
	foreach ( e; o ) {
		writeln( e );
	}
}