#include "Utilities_stdafx.h"

/* this define is necessary: while running the unit test in a debug version,
we want to check the correctness of all operations on containers & iterators */
#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE

#include "multi_index_algorithms.hpp"
#include <algorithm>

using namespace ::std;
using namespace ::boost;
using namespace ::boost::multi_index;


// test TestData structure
struct TestData {
  int m_value;
  TestData( int name ) : m_value( name ) {}
};

// comparison functor not discerning 2k and 2k+1
struct comp2 {
	bool operator()( const TestData& x, const TestData& y ) const {
		return (x.m_value/2) <  (y.m_value/2);
	}
};

// a weaker comparison functor, doesn't discern 3k, 3k+1 and 3k+2
struct comp3 {
	bool operator()( const TestData& x, const TestData& y ) const {
		return (x.m_value/3) <  (y.m_value/3);
	}
};

// a very weak operator<, doesn't discern 4k, 4k+1, 4k+2 and 4k+3
bool operator<( const TestData& x, const TestData& y ) {
	return (x.m_value/4) <  (y.m_value/4);
}

// define a multiply indexed set with one index
typedef multi_index_container<
  TestData,
  indexed_by< ordered_non_unique<identity<TestData>, comp2 > > 
> MCont;

// abbreviations
typedef MCont::nth_index<0>::type MSet;
typedef MSet::iterator MSetIterator;

UNITTESTIMPL( MultiIndexAlgorithms_Test ) {
	MCont mcTest;
	MSet &msTest = mcTest.get<0>();

	/* prepare a multi index container with some data
	and initialize iterators bounding our range */
	int nA = 5, nZ = 20, nS = 9, nT = 16;
	MSetIterator itS, itT;
	for(int i = nA; i < nZ; ++i) {
		MSetIterator iNewElement = mcTest.insert( TestData(i) ).first;
		if(i == nS) itS = iNewElement;
		if(i == nT) itT = iNewElement;
	}
	if(nS <  nA) itS = msTest.begin();
	if(nT >= nZ) itT = msTest.end();

	for( int x = nA; x < nZ; ++x ) {
		/* In the given container's range [itS,itT), for each value x, find its
		upper_bound, lower_bound, equal_range and determine its presense using
		both STL and our versions, and compare results - they must be equal.
		To force the compiler to distinguish STL and our versions, we explicitly
		specify template parameter for STL version: our template's 1st parameter
		is NodeBase (Boost's internal data structure), and STL template has
		iterator type instead */
		_ASSERT(   lower_bound(itS, itT, TestData(x), comp2()) ==   lower_bound<MSetIterator>(itS, itT, TestData(x), comp2()) );
		_ASSERT(   upper_bound(itS, itT, TestData(x), comp2()) ==   upper_bound<MSetIterator>(itS, itT, TestData(x), comp2()) );
		_ASSERT(   equal_range(itS, itT, TestData(x), comp2()) ==   equal_range<MSetIterator>(itS, itT, TestData(x), comp2()) );
		_ASSERT( binary_search(itS, itT, TestData(x), comp2()) == binary_search<MSetIterator>(itS, itT, TestData(x), comp2()) );

		_ASSERT(   lower_bound(itS, itT, TestData(x), comp3()) ==   lower_bound<MSetIterator>(itS, itT, TestData(x), comp3()) );
		_ASSERT(   upper_bound(itS, itT, TestData(x), comp3()) ==   upper_bound<MSetIterator>(itS, itT, TestData(x), comp3()) );
		_ASSERT(   equal_range(itS, itT, TestData(x), comp3()) ==   equal_range<MSetIterator>(itS, itT, TestData(x), comp3()) );
		_ASSERT( binary_search(itS, itT, TestData(x), comp3()) == binary_search<MSetIterator>(itS, itT, TestData(x), comp3()) );

		_ASSERT(   lower_bound(itS, itT, TestData(x)  /* < */) ==   lower_bound<MSetIterator>(itS, itT, TestData(x)  /* < */) );
		_ASSERT(   upper_bound(itS, itT, TestData(x)  /* < */) ==   upper_bound<MSetIterator>(itS, itT, TestData(x)  /* < */) );
		_ASSERT(   equal_range(itS, itT, TestData(x)  /* < */) ==   equal_range<MSetIterator>(itS, itT, TestData(x)  /* < */) );
		_ASSERT( binary_search(itS, itT, TestData(x)  /* < */) == binary_search<MSetIterator>(itS, itT, TestData(x)  /* < */) );
	}
}