//  (C) Copyright Herve Bronnimann, Ben Gear 2007.
//  Use, modification and distribution are subject to the
//  Boost Software License, Version 1.0. (See accompanying file
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <numeric>
#include <utility>
#include <vector>

#include <boost/config.hpp>
#include <boost/algorithm/combination.hpp>
#include <boost/test/included/test_exec_monitor.hpp>

int verbose;
int veryVerbose;

using namespace boost;

namespace {

template <class Incrementable>
bool print(std::ostream& stream, Incrementable const& ) { return false; }

bool print(std::ostream& stream, int x) { stream << x; return true; }

bool print(std::ostream& stream, std::vector<int>::iterator x) {
    stream << (void*)&(*x); return true;
}

} // unnamed namespace

/* TESTING:  next_partial_permutation(begin, middle, end)
 *           prev_partial_permutation(begin, middle, end)
 * METHOD:   exhaustive, for r (= middle - first) <= n and n (= last - first) <= 5.
 * CONCERNS:
 */

template <class Container>
void test_partial_permutations(int r, Container cont)
{
    int n = cont.size();

    std::vector<Container> permutations;
    
    // Testing the number of permutations (stated in the documentation)
    // n! / (n - r)!;  see "permutation numbers"
    int power = 1;
    for (int i = n; i > n - r; --i) {
        power *= i;
    }
    permutations.reserve(power);
    
    if (veryVerbose) 
        std::cout << "\tnext_partial_permutations (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << power << " permutations" << std::endl;

    // Prepare first permutation, container will be sorted.
    typename Container::iterator begin  = cont.begin();
    typename Container::iterator middle = begin;
    typename Container::iterator end    = cont.end();
    std::advance(middle, r);

    typename Container::iterator current = cont.begin();
    for (int i = 0; current != end; ++current, ++i) {
        *current = i;
    }

    // Push back all the permutations as we visit them.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ "; print(std::cout, *current);
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", "; print(std::cout, *(++current));
            }
            std::cout << " ]\n" << std::flush;
        }
        permutations.push_back(cont);
    } while(next_partial_permutation(begin, middle, end));
    BOOST_CHECK_EQUAL(permutations.size(), power);
    
    // Check first the guarantees that the output is ordered lexicographically.
    for (int i = 1; i < (int)permutations.size(); ++i) {
        BOOST_CHECK(std::lexicographical_compare(permutations[i - 1].begin(),
                                                 permutations[i - 1].end(),
                                                 permutations[i].begin(),
                                                 permutations[i].end()));
    }

    // Check wraparound.
    BOOST_CHECK(std::equal(permutations[0].begin(), permutations[0].end(),
                           cont.begin()));
    
    if (veryVerbose) 
        std::cout << "\tprev_partial_permutation"
                  << " (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << power << " permutations" << std::endl;

    // Check wraparound (concern #).
    prev_partial_permutation(begin, middle, end);

    // Check that prev_partial_permutation reverses the sequence of
    // permutations.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ "; print(std::cout, *current);
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", "; print(std::cout, *(++current));
            }
            std::cout << " ]\n" << std::flush;
        }
        --power;
        BOOST_CHECK(std::equal(permutations[power].begin(),
                               permutations[power].end(),
                               cont.begin()));
    } while(0 < power && prev_partial_permutation(begin, middle, end));

    // Check that we unwinded all the way.
    BOOST_CHECK_EQUAL(power, 0);
    BOOST_CHECK(std::equal(permutations[0].begin(), permutations[0].end(),
                           cont.begin()));
}

/* TESTING:  next_combination(begin, middle, end)
 *           prev_combination(begin, middle, end)
 * METHOD:   exhaustive, for r (= middle - first) <= n and n (= last - first) <= 5.
 * CONCERNS:
 */

template <class Container>
void test_combinations(int r, Container cont)
{
    int n = cont.size();

    std::vector<Container> combinations;
    
    // Testing the number of combinations (stated in documentation):
    // n! / r! / (n - r)!;  see "binomial coefficients"
    int binomial = 1;
    for (int i = n; i > n - r; --i) {
        binomial *= i;
    }
    for (int i = r; i > 0; --i) {
        binomial /= i;
    }

    if (0 == binomial) binomial = 1;  // Even if there are no combinations, we
                                      // will push one onto combinations.
    combinations.reserve(binomial);
    
    if (veryVerbose) 
        std::cout << "\tnext_combination"
                  << " (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << binomial << " combinations" << std::endl;

    // Prepare initial combination counts.
    typename Container::iterator begin  = cont.begin();
    typename Container::iterator middle = begin;
    typename Container::iterator end    = cont.end();
    std::advance(middle, r);

    typename Container::iterator current = cont.begin();
    for (int i = 0; current != end; ++current, ++i) {
        *current = i;
    }

    // Push back all the combinations as we visit them.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ " << *current;
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", " << *(++current);
            }
            std::cout << " ]\n" << std::flush;
        }
        combinations.push_back(cont);
    } while(next_combination(begin, middle, end));

    BOOST_CHECK_EQUAL(combinations.size(), binomial);
    
    // Check first the guarantees that the output is ordered
    // lexicographically and that it sums up to the proper amount.
    for (int i = 1; i < (int)combinations.size(); ++i) {
        BOOST_CHECK(std::lexicographical_compare(combinations[i - 1].begin(),
                                                 combinations[i - 1].end(),
                                                 combinations[i].begin(),
                                                 combinations[i].end()));
    }

    // Check wraparound (concern #).
    BOOST_CHECK(std::equal(combinations[0].begin(), combinations[0].end(),
                           cont.begin()));

    if (veryVerbose) 
        std::cout << "\tprev_combination"
                  << " (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << binomial << " combinations" << std::endl;

    // Check wraparound (concern #).
    prev_combination(begin, middle, end);

    // Check that prev_combination_counts reverses the sequence of
    // combinations.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ " << *current;
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", " << *(++current);
            }
            std::cout << " ]\n" << std::flush;
        }
        --binomial;
        BOOST_CHECK(std::equal(combinations[binomial].begin(),
                               combinations[binomial].end(),
                               cont.begin()));
    } while(0 < binomial && prev_combination(begin, middle, end));

    // Check that we unwinded all the way.
    BOOST_CHECK_EQUAL(binomial, 0);
    BOOST_CHECK(std::equal(combinations[0].begin(), combinations[0].end(),
                           cont.begin()));
}

/* TESTING:  next_mapping(begin, end, first, last)
 *           prev_mapping(begin, end, first, last)
 * METHOD:   exhaustive, for 10 >= r (= cont.size()) and 5 == n (= last - first).
 * CONCERNS:
 *  1.
 */

template <class Incrementable, class Container>
void test_mappings(Incrementable first, Incrementable last, Container cont)
{
    int r = cont.size();
    std::vector<Container> permutations;
    
    // Compute number of permutations, n^r, and reserve space.
    // It's not because we're testing that we should be sloppy or inefficient!
    int n = 0, power = 1;
    for (Incrementable current = first; current != last; ++n, ++current) ;
    for (int i = r; i > 0; --i) {
        power *= n;
    }
    permutations.reserve(power);
    
    if (veryVerbose) 
        std::cout << "next_mapping (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << power << " mappings" << std::endl;

    // Prepare first mapping.
    std::fill(cont.begin(), cont.end(), first);

    // Push back all the permutations as we visit them.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ "; print(std::cout, *current);
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", "; print(std::cout, *(++current));
            }
            std::cout << " ]\n" << std::flush;
        }
        permutations.push_back(cont);
    } while(next_mapping(cont.begin(), cont.end(), first, last));
    BOOST_CHECK_EQUAL(permutations.size(), power);
    
    // Check first the guarantees that the output is ordered lexicographically.
    for (int i = 1; i < (int)permutations.size(); ++i) {
        BOOST_CHECK(std::lexicographical_compare(permutations[i - 1].begin(),
                                                 permutations[i - 1].end(),
                                                 permutations[i].begin(),
                                                 permutations[i].end()));
    }

    // Check wraparound.
    BOOST_CHECK(std::equal(permutations[0].begin(), permutations[0].end(),
                           cont.begin()));
    
    if (veryVerbose) 
        std::cout << "\tprev_mapping"
                  << " (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << power << " mappings" << std::endl;

    // Check wraparound (concern #).
    prev_mapping(cont.begin(), cont.end(), first, last);

    // Check that prev_combination_counts reverses the sequence of
    // combinations.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ "; print(std::cout, *current);
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", "; print(std::cout, *(++current));
            }
            std::cout << " ]\n" << std::flush;
        }
        --power;
        BOOST_CHECK(std::equal(permutations[power].begin(),
                               permutations[power].end(),
                               cont.begin()));
    } while(0 < power&&
            prev_mapping(cont.begin(), cont.end(), first, last));

    // Check that we unwinded all the way.
    BOOST_CHECK_EQUAL(power, 0);
    BOOST_CHECK(std::equal(permutations[0].begin(), permutations[0].end(),
                           cont.begin()));
}

/* TESTING:  next_combination_counts(begin, end, first, last)
 * METHOD:   exhaustive, for 10 >= r (= cont.size()) and 5 == n (= last - first).
 * CONCERNS:
 */

template <class Value, class Container>
void test_combination_counts(Value total_size, Container cont)
{
    int n = cont.size();
    int r = (int)total_size;
    std::vector<Container> combinations;
    
    // Testing the number of permutations (stated in documentation):
    // (n + r - 1)! / r! / (n - 1)!;  see "multiset coefficients"
    int multiset = 1;
    for (int i = n + r - 1; i >= n; --i) {
        multiset *= i;
    }
    for (int i = r; i > 0; --i) {
        multiset /= i;
    }

    if (0 == multiset) multiset = 1;  // Even if there are no combinations, we
                                      // will push one onto combinations.
    combinations.reserve(multiset);
    
    if (veryVerbose) 
        std::cout << "\tnext_combination_counts"
                  << " (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << multiset << " combinations" << std::endl;

    // Prepare initial combination counts.
    if (0 < cont.size()) {
        typename Container::iterator current = cont.end(); --current;
        std::fill(cont.begin(), current, (Value)0);
        *current = total_size;
    }

    // Push back all the combinations as we visit them.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ " << *current;
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", " << *(++current);
            }
            std::cout << " ]\n" << std::flush;
        }
        combinations.push_back(cont);
    } while(next_combination_counts(cont.begin(), cont.end()));

    BOOST_CHECK_EQUAL(combinations.size(), multiset);
    
    // Check first the guarantees that the output is ordered
    // lexicographically and that it sums up to the proper amount.
    for (int i = 1; i < (int)combinations.size(); ++i) {
        BOOST_CHECK(std::lexicographical_compare(combinations[i - 1].begin(),
                                                 combinations[i - 1].end(),
                                                 combinations[i].begin(),
                                                 combinations[i].end()));
        BOOST_CHECK_EQUAL(std::accumulate(combinations[i].begin(),
                                          combinations[i].end(), (Value)0),
                          total_size);
    }

    // Check wraparound (concern #).
    BOOST_CHECK(std::equal(combinations[0].begin(), combinations[0].end(),
                           cont.begin()));

    if (veryVerbose) 
        std::cout << "\tprev_combination_counts"
                  << " (r = " << r << ", n = " << n << ")" << std::endl
                  << "\texpecting " << multiset << " combinations" << std::endl;

    // Check wraparound (concern #).
    prev_combination_counts(cont.begin(), cont.end());

    // Check that prev_combination_counts reverses the sequence of
    // combinations.
    do {
        if (veryVerbose && 0 < cont.size()) {
            typename Container::iterator current = cont.begin();
            std::cout << "\t\t[ " << *current;
            for (int i = 1; i < cont.size(); ++i) {
                std::cout << ", " << *(++current);
            }
            std::cout << " ]\n" << std::flush;
        }
        --multiset;
        BOOST_CHECK(std::equal(combinations[multiset].begin(),
                               combinations[multiset].end(),
                               cont.begin()));
    } while(0 < multiset &&
            prev_combination_counts(cont.begin(), cont.end()));

    // Check that we unwinded all the way.
    BOOST_CHECK_EQUAL(multiset, 0);
    BOOST_CHECK(std::equal(combinations[0].begin(), combinations[0].end(),
                           cont.begin()));
}

/* TESTNG:   APPARATUS
 * CONCERNS:
 *   1. That we can instantiate next_mapping with different kinds of
 *      incrementables, and different kinds of iterators.
 *   2. That we can instantiate next_combination counts with
 *      different kinds of iterators.
 *   3. That we can correctly handle empty sequences whenever allowed.
 * PLAN:     
 *   1. Call test_mappings and test_combination_counts with all possible
 *      values of n and r such that n = 0 .. 8 and 0 <= r <= 2 * n.
 *   2. Try test_mappings<int, std::vector> and test_mappingsint, std::list>
 *      as well as next_mapping<std::vector::iterator, std::vector> and
 *      next_mapping<std::vector::iterator, std::list>.
 *   3. Try test_combination_counts<std::vector> and test_combination_counts<std::list>.
 */

template <class Value>
void test()
{
    for (int n = 0; n <= 5; ++n) {
        std::vector<Value> c(n);
        for (int i = 0; i < n; ++i) {
            c[i] = i;
        }
        
        // Testing:  permutations(r, n) without repetitions.
        if (verbose)
            std::cout << "Testing permutations without repetitions,"
                      << " with int: n = " << n << std::endl;
        for (int r = 0; r <= n; ++r) {
            if (verbose) std::cout << ". . . with r = " << r << std::endl;
            std::vector<int> v(n);
            test_partial_permutations(r, v);
            std::list<int> l(n);
            test_partial_permutations(r, l);
        }

        // Testing:  combinations(r, n) without repetitions.
        if (verbose) std::cout << "Testing combinations without repetitions,"
                               << " with int: n = " << n << std::endl;
        for (int r = 0; r <= n; ++r) {
            if (verbose) std::cout << ". . . with r = " << r << std::endl;
            std::vector<int> v(n);
            test_combinations(r, v);
            std::list<int> l(n);
            test_combinations(r, l);
        }

        if (0 < n) {
            // Testing:  permutations(r, n) with repetitions, with int for
            // incrementable values.
            if (verbose)
                std::cout << "Testing permutations with repetitions,"
                          << " with int: n = " << n << std::endl;
            for (int r = 0; r <= n + 3; ++r) {
                if (verbose) std::cout << ". . . with r = " << r << std::endl;
                std::vector<int> v(r);
                test_mappings(0, n, v);
                std::list<int> l(r);
                test_mappings(0, n, l);
            }
            
            // Testing:  permutations(r, n) with repetitions, with
            // vector<int>::iterator for incrementable values.
            if (verbose)
                std::cout << "Testing permutations with repetitions,"
                          << " with vector<int>::iterator: n = " << n << std::endl;
            for (int r = 0; r <= n + 3; ++r) {
                if (verbose) std::cout << ". . . with r = " << r << std::endl;
                std::vector<std::vector<int>::iterator> v(r);
                test_mappings(c.begin(), c.end(), v);
                std::list<std::vector<int>::iterator> l(r);
                test_mappings(c.begin(), c.end(), l);
            }
        } else {
            if (verbose)
                std::cout << "Cannot test permutations with repetitions"
                          << " with n = " << n << std::endl;
        }

        // Testing:  combinations(r, n) with repetitions.
        if (verbose)
            std::cout << "Testing combinations with repetitions:"
                      << " n = " << n << std::endl;
        for (int r = 0; r <= n + 3; ++r) {
            if (verbose) std::cout << ". . . with r = " << r << std::endl;
            std::vector<int> v(c.size());
            test_combination_counts(r, v);
            std::list<int> l(c.size());
            test_combination_counts(r, l);
        }
    }
}

/* MAIN */

int test_main( int argc, char* argv[] )
{
    verbose = argc > 1;
    veryVerbose = argc > 2;
    test<int>(); // ("builtin");

    return 0;
}