#include <iostream>

#include <boost/assert.hpp>

#include <origin/utility/typestr.hpp>
#include <origin/lists/circular_list.hpp>
#include <origin/lists/paired_list.hpp>
#include <origin/lists/dummy_list.hpp>
#include <origin/lists/counted_list.hpp>

using std::cout;
using namespace origin;

// Structure used in emplacement testing.
struct emplace_struct {
    emplace_struct(int&& i)
        : i(std::move(i))
    { }
    
    int i;
};

/**
 * Ensure that all lists are
 * a) Initializeable (constructible over an initializer list),
 * b) CopyConstructible, and
 * c) MoveConstructible.
 */
template <typename List>
void test_init() {
    // Test initializer list construction
    List x = { 1, 2, 3, };
    auto test = x.begin();    
    BOOST_ASSERT(( x.size() == 3 ));
    {
        auto i = x.begin();
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( i == x.end() ));
    }

    // Test copy construction.
    List y = x;
    BOOST_ASSERT(( y.size() == 3 ));
    {
        auto i = y.begin();
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( i == y.end() ));
    }

    // Test move construction
    List z = std::move(y);
    BOOST_ASSERT(( z.size() == 3 ));
    BOOST_ASSERT(( y.empty() ));
    {
        auto i = z.begin();
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( i == z.end() ));
    }
    
    {
        // Test fill construction.
        List j(typename List::size_type(3), 3);
        BOOST_ASSERT(( j.size() == 3 ));
        
        auto it = j.begin();
        BOOST_ASSERT(( *it++ == 3 ));
        BOOST_ASSERT(( *it++ == 3 ));
        BOOST_ASSERT(( *it++ == 3 ));
    }
}

template <typename List>
void test_assignment() {
    List x = { 1, 2, 3, };
    
    // Test copy assignment.
    {
        List l;
        l = x;
        
        BOOST_ASSERT(( x.size() == l.size() ));
        auto i1 = x.begin();
        auto i2 = l.begin();
        BOOST_ASSERT(( *i1++ == *i2++ ));
        BOOST_ASSERT(( *i1++ == *i2++ ));
        BOOST_ASSERT(( *i1++ == *i2++ ));
    }
    
    // Test initializer assignment.
    {
        x = { 3, 4, };
        
        BOOST_ASSERT(( x.size() == 2 ));
        auto i = x.begin();
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( *i++ == 4 ));
        BOOST_ASSERT(( i == x.end() ));
    }
    
    // Test move assignment.
    {
        List l;
        l = std::move(x);
        
        BOOST_ASSERT(( x.empty() ));
        BOOST_ASSERT(( l.size() == 2 ));
        
        auto i = l.begin();
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( *i++ == 4 ));
        BOOST_ASSERT(( i == l.end() ));
    }
}

/**
 * Tests all the front functions of the list.
 */
template <typename List>
void test_front() {
    List x;
    
    // Test push front (copy).
    int v = 5;
    x.push_front(v);
    BOOST_ASSERT(( x.size() == 1 ));
    BOOST_ASSERT(( x.front() == v ));
    
    // Test push front (move).
    x.push_front(10);
    BOOST_ASSERT(( x.size() == 2 ));
    BOOST_ASSERT(( x.front() == 10 ));
    
    x.pop_front();
    x.pop_front();
    BOOST_ASSERT(( x.size() == 0 ));

}

/**
 * Tests all the back functions of the list.
 */
template <typename List>
void test_back() {
    List x;
    
    // Test push back (copy).
    int v = 5;
    x.push_back(v);
    BOOST_ASSERT(( x.size() == 1 ));
    BOOST_ASSERT(( x.back() == v ));
    
    // Test push back (move).
    x.push_back(10);
    BOOST_ASSERT(( x.size() == 2 ));
    BOOST_ASSERT(( x.back() == 10 ));
    
    x.pop_back();
    x.pop_back();
    BOOST_ASSERT(( x.size() == 0 ));
}

/**
 * Tests the insert before functions.
 */
template <typename List>
void test_insert_before() {
    List x = { 1, 4, };
    BOOST_ASSERT(( x.size() == 2 ));
    {
        auto i = x.begin();
        BOOST_ASSERT(( *(++i) == 4 ));
        
        // Test insert before (copy);
        int j = 3;
        x.insert_before(i, j);
        BOOST_ASSERT(( x.size() == 3 ));
        BOOST_ASSERT(( *(--i) == j ));
        
        // Test insert before (move).
        x.insert_before(i, 2);
        BOOST_ASSERT(( x.size() == 4 ));
        BOOST_ASSERT(( *(--i) == 2 ));
    }
    
    // Test insert before (range).
    List y = { 1, 4, };
    List test = { 2, 3, };
    BOOST_ASSERT(( y.size() == 2 ));
    {
        auto i = y.begin();
        BOOST_ASSERT(( *(++i) == 4 ));
        
        y.insert_before(i, test.begin(), test.end());
        BOOST_ASSERT(( y.size() == 4 ));
        i = y.begin();
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( *i++ == 4 ));
    }
    
    // Test insert before (init).
    {
        List z = { 3, };
        auto it = z.begin();
        z.insert_before(it, { 1, 2, });
        BOOST_ASSERT(( z.size() == 3 ));
        BOOST_ASSERT(( *it-- == 3 ));
        BOOST_ASSERT(( *it-- == 2 ));
        BOOST_ASSERT(( *it-- == 1 ));
        BOOST_ASSERT(( it == z.end() ));
    }
    
    // Test insert before (fill).
    {
        List z = { 1, };
        auto it = z.begin();
        
        z.insert_before(it, typename List::size_type(3), 2);
        --it;
        BOOST_ASSERT(( z.size() == 4 ));
        BOOST_ASSERT(( *it-- == 2 ));
        BOOST_ASSERT(( *it-- == 2 ));
        BOOST_ASSERT(( *it-- == 2 ));
    }
}

template <typename List>
void test_emplacement() {
    // Test Emplace front.
    {
        List l;
        l.emplace_front(std::move(3));
        BOOST_ASSERT(( l.size() == 1 ));
        
        auto i = l.front();
        BOOST_ASSERT(( i.i == 3 ));
    }
    
    // Test emplace back.
    {
        List l;
        l.emplace_back(std::move(3));
        BOOST_ASSERT(( l.size() == 1 ));
        auto i = l.back();
        BOOST_ASSERT(( i.i == 3 ));
    }
    
    List x;
    x.emplace_front(std::move(1));
    auto it = x.begin();
    
    // Test emplace (after).
    {
        it = x.emplace_after(it, std::move(3));
        BOOST_ASSERT(( x.size() == 2 ));
        BOOST_ASSERT(( (*it).i == 3 ));
    }
    
    // Test emplace (before).
    {
        it = x.emplace_before(it, 2);
        BOOST_ASSERT(( x.size() == 3 ));
        BOOST_ASSERT(( (*it).i == 2 ));
    }
}

/**
 * Tests the insert after functions.
 */
template <typename List>
void test_insert_after() {
    List x = { 1, 4, };
    
    BOOST_ASSERT(( x.size() == 2 ));
    {
        auto i = x.begin();
        // Test insert_after (copy).
        int j = 2;
        x.insert_after(i, j);
        BOOST_ASSERT(( x.size() == 3 ));
        BOOST_ASSERT(( *(++i) == j ));
        
        // Test insert_after (move).
        x.insert_after(i, 3);
        BOOST_ASSERT(( x.size() == 4 ));
        BOOST_ASSERT(( *(++i) == 3 ));

        i = x.begin();
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( *i++ == 4 ));
    }
    
    // Test insert after (range).
    List y = { 1, 4, };
    List test = { 2, 3, };
    BOOST_ASSERT(( y.size() == 2 ));
    {
        auto i = y.begin();
        y.insert_after(i, test.begin(), test.end());
        BOOST_ASSERT(( y.size() == 4 ));
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( *i++ == 3 ));
        BOOST_ASSERT(( *i++ == 4 ));
    }
    
    // Test insert after (init).
    {
        List z = { 1, };
        auto it = z.begin();
        z.insert_after(it, { 2, 3, });
        
        BOOST_ASSERT(( z.size() == 3 ));
        BOOST_ASSERT(( *it++ == 1 ));
        BOOST_ASSERT(( *it++ == 2 ));
        BOOST_ASSERT(( *it++ == 3 ));
        BOOST_ASSERT(( it == z.end() ));
    }
    
    // Test insert after (fill).
    {
        List z = { 1, };
        auto it = z.begin();
        
        z.insert_after(it, typename List::size_type(3), 2);
        BOOST_ASSERT(( z.size() == 4 ));
        BOOST_ASSERT(( *it++ == 1 ));
        BOOST_ASSERT(( *it++ == 2 ));
        BOOST_ASSERT(( *it++ == 2 ));
        BOOST_ASSERT(( *it++ == 2 ));
        BOOST_ASSERT(( it == z.end() ));
    }
}

/**
 * Tests the erase functionality of the list.
 */
template <typename List>
void test_erase() {
    // Test erase after.
    List w = { 1, 3, 2, };
    {
        auto i = w.begin();
        w.erase_after(i);
        BOOST_ASSERT(( w.size() == 2 ));
        BOOST_ASSERT(( *i++ == 1 ));
        BOOST_ASSERT(( *i++ == 2 ));
        BOOST_ASSERT(( i == w.end() ));
    }
    
    // Test erase before.
    List y = { 3, 1, 2, };
    {
        auto i = y.begin();
        y.erase_before(++i);
        BOOST_ASSERT(( y.size() == 2 ));
        BOOST_ASSERT(( y.front() == 1 ));
    }
    
    // Test erase (range).
    {
        y.erase_after(y.begin(), y.end());
        
        BOOST_ASSERT(y.size() == 1);
    }
}

/**
 * Tests the splice after functionality.
 */
template <typename List>
void test_splice_after() {
    List x = { 1, 2, 3, };
    
    // Test splice after (single node).
    {
        List y = { 4, };
        auto it = x.begin();
        ++it; ++it;
        x.splice_after(it, y, y.begin());
        
        BOOST_ASSERT(( y.empty() ));
        BOOST_ASSERT(( x.size() == 4 ));
        BOOST_ASSERT(( *(++it) == 4 ));
    }
    
    // Test splice after (range).
    {
        List y = { 0, };
        List z = { 1, 2, };
        
        auto it = y.begin();
        y.splice_after(it, z, z.begin(), z.end());
        
        BOOST_ASSERT(( z.empty() ));
        BOOST_ASSERT(( y.size() == 3 ));
        BOOST_ASSERT(( *it++ == 0 ));
        BOOST_ASSERT(( *it++ == 1 ));
        BOOST_ASSERT(( *it++ == 2 ));
    }

    // Test splice after (whole list).
    {
        List y = { 0, };
        
        auto it = y.begin();
        y.splice_after(it, x);
        
        BOOST_ASSERT(( x.empty() ));
        BOOST_ASSERT(( y.size() == 5 ));
        BOOST_ASSERT(( *it++ == 0 ));
        BOOST_ASSERT(( *it++ == 1 ));
        BOOST_ASSERT(( *it++ == 2 ));
        BOOST_ASSERT(( *it++ == 3 ));
        BOOST_ASSERT(( *it++ == 4 ));
    }
}

/**
 * Tests the splice before functionality.
 */
template <typename List>
void test_splice_before() {
    List x = { 4, };
    
    // Test splice before (single element).
    {
        List y = { 3, };
        
        auto it = y.begin();
        
        x.splice_before(x.begin(), y, it);
        
        BOOST_ASSERT(( y.empty() ));
        BOOST_ASSERT(( x.size() == 2 ));
        BOOST_ASSERT(( x.front() == *it ));
    }
    
    // Test splice before (range).
    {
        List y = { 1, 2, };
        
        x.splice_before(x.begin(), y, y.begin(), y.end());
        
        BOOST_ASSERT(( y.empty() ));
        
        auto it = x.begin();
        BOOST_ASSERT(( *it++ == 1 ));
        BOOST_ASSERT(( *it++ == 2 ));
    }
    
    // Test splice before (whole list).
    {
        List y = { 5, };
        
        y.splice_before(y.begin(), x);
        
        BOOST_ASSERT(( x.empty() ));
        
        auto it = y.begin();
        BOOST_ASSERT(( *it++ == 1 ));
        BOOST_ASSERT(( *it++ == 2 ));
        BOOST_ASSERT(( *it++ == 3 ));
        BOOST_ASSERT(( *it++ == 4 ));
        BOOST_ASSERT(( *it++ == 5 ));
        BOOST_ASSERT(( it == y.end() ));
    }
}

/**
 * Tests the resizing functions of a list.
 */
template <typename List>
void test_resize() {
    List x;
    
    // Test resizing when the list is empty.
    {
        x.resize(2);
        auto it = x.begin();
        BOOST_ASSERT(( x.size() == 2 ));
        BOOST_ASSERT(( *it++ == 0 ));
        BOOST_ASSERT(( *it++ == 0 ));
        BOOST_ASSERT(( it == x.end() ));
    }

    x.clear();
    x.push_front(10);
    
    // Test adding more nodes to the list.
    {
        x.resize(3);
        auto it = x.begin();
        BOOST_ASSERT(( x.size() == 3 ));
        BOOST_ASSERT(( *it++ == 10 ));
        BOOST_ASSERT(( *it++ == 0 ));
        BOOST_ASSERT(( *it++ == 0 ));
        BOOST_ASSERT(( it == x.end() ));
    }
    
    // Test removing nodes from the list.
    {
        x.resize(1);
        auto it = x.begin();
        BOOST_ASSERT(( x.size() == 1 ));
        BOOST_ASSERT(( *it++ == 10 ));
        BOOST_ASSERT(( it == x.end() ));
    }
    
    // Make sure no new nodes are added.
    {
        x.resize(1);
        auto it = x.begin();
        BOOST_ASSERT(( x.size() == 1 ));
        BOOST_ASSERT(( *it++ == 10 ));
        BOOST_ASSERT(( it == x.end() ));
    }
    
    x.resize(0);
    BOOST_ASSERT(( x.empty() ));
    BOOST_ASSERT(( x.begin() == x.end() ));
}

template <typename List>
void test_swap() {
    List x = { 1, 2, };
    List y;
    
    // Tests member swap.
    x.swap(y);
    BOOST_ASSERT(( x.empty() ));
    BOOST_ASSERT(( y.size() == 2 ));
    
    // Test the free swap.
    swap(y, x);
    BOOST_ASSERT(( y.empty() ));
    BOOST_ASSERT(( x.size() == 2 ));
}

int main() {
    using namespace origin::lists;
    
    // Test the circular list.
    test_init<circular_list<int>>();
    test_front<circular_list<int>>();
    test_back<circular_list<int>>();    
    test_insert_before<circular_list<int>>();
    test_insert_after<circular_list<int>>();
    test_erase<circular_list<int>>();
    test_assignment<circular_list<int>>();
    test_emplacement<circular_list<emplace_struct>>();
    test_splice_after<circular_list<int>>();
    test_splice_before<circular_list<int>>();
    test_resize<circular_list<int>>();
    test_swap<circular_list<int>>();
    
    // Test the paired list.
    test_init<paired_list<int>>();
    test_front<paired_list<int>>();
    test_back<paired_list<int>>();
    test_insert_before<paired_list<int>>();
    test_insert_after<paired_list<int>>();
    test_erase<paired_list<int>>();
    test_assignment<paired_list<int>>();
    test_emplacement<paired_list<emplace_struct>>();
    test_splice_after<paired_list<int>>();
    test_splice_before<paired_list<int>>();
    test_resize<paired_list<int>>();
    test_swap<paired_list<int>>();
    
    // Test the dummy list.
    test_init<dummy_list<int>>();
    test_front<dummy_list<int>>();
    test_back<dummy_list<int>>();
    test_insert_before<dummy_list<int>>();
    test_insert_after<dummy_list<int>>();
    test_erase<dummy_list<int>>();
    test_assignment<dummy_list<int>>();
    test_emplacement<dummy_list<emplace_struct>>();
    test_splice_after<dummy_list<int>>();
    test_splice_before<dummy_list<int>>();
    test_resize<dummy_list<int>>();
    test_swap<dummy_list<int>>();

    typedef counted_list<circular_list<int>> CountedCircularList;
    typedef counted_list<circular_list<emplace_struct>> CountedCircularEmplaceList;
    
    // Test the (counted) circular list.
    test_init<CountedCircularList>();
    test_front<CountedCircularList>();
    test_back<CountedCircularList>();    
    test_insert_before<CountedCircularList>();
    test_insert_after<CountedCircularList>();
    test_erase<CountedCircularList>();
    test_assignment<CountedCircularList>();
    test_emplacement<CountedCircularEmplaceList>();
    test_splice_after<CountedCircularList>();
    test_splice_before<CountedCircularList>();
    test_resize<CountedCircularList>();
    test_swap<CountedCircularList>();
    
    typedef counted_list<paired_list<int>> CountedPairedList;
    typedef counted_list<paired_list<emplace_struct>> CountedPairedEmplaceList;
    
    // Test the (counted) paired list.
    test_init<CountedPairedList>();
    test_front<CountedPairedList>();
    test_back<CountedPairedList>();
    test_insert_before<CountedPairedList>();
    test_insert_after<CountedPairedList>();
    test_erase<CountedPairedList>();
    test_assignment<CountedPairedList>();
    test_emplacement<CountedPairedEmplaceList>();
    test_splice_after<CountedPairedList>();
    test_splice_before<CountedPairedList>();
    test_resize<CountedPairedList>();
    test_swap<CountedPairedList>();
    
    typedef counted_list<dummy_list<int>> CountedDummyList;
    typedef counted_list<dummy_list<emplace_struct>> CountedDummyEmplaceList;
    
    // Test the (counted) dummy list.
    test_init<CountedDummyList>();
    test_front<CountedDummyList>();
    test_back<CountedDummyList>();
    test_insert_before<CountedDummyList>();
    test_insert_after<CountedDummyList>();
    test_erase<CountedDummyList>();
    test_assignment<CountedDummyList>();
    test_emplacement<CountedDummyEmplaceList>();
    test_splice_after<CountedDummyList>();
    test_splice_before<CountedDummyList>();
    test_resize<CountedDummyList>();
    test_swap<CountedDummyList>();
    
    return 0;
}