#include <stdio.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <iostream>

#define MANY 10000

//-------------------------------
// Item implementation

class ads_item
{
	int data;
public:
	// Counters for assignments and comparisons
	static size_t assignments_count, comparisons_count;
	
	// Constructor. Initialize items with random values.
	ads_item() 
	{
		data = rand();
	};
	
	// Constructor with copying.
	ads_item(const ads_item & other) : data(other.data)
	{
		++assignments_count;
	};
	
	// Reset counters to 0.
	static void reset()
	{
		assignments_count = 0;
		comparisons_count = 0;
	}
	
	// Overloading comparison operation.
	bool operator<(const ads_item &other) const
	{
		++comparisons_count;
		return data<other.data;
	}
	
	// Overloading assignment operator.
	const ads_item &operator=(const ads_item &other)
	{
		++assignments_count;
		data = other.data;
		return *this;
	}
	
	// Declare output operation as a friend.
	friend std::ostream & operator<<(std::ostream & out, const ads_item & item);
};

// Initializing static members
size_t ads_item::assignments_count = 0;
size_t ads_item::comparisons_count = 0;

// Overloading output operation as a friend.
std::ostream & operator<<(std::ostream & out, const ads_item & item)
{
	return out << item.data;
}

//-------------------------------
// Dynamic linked list implementation

class ads_link_node
{
    ads_item item;
    ads_link_node* next;
    friend class ads_linked_list;
	
public:
	// Counters for assignments and comparisons
	static size_t assignments_count, comparisons_count;

	// Empty constructor
    ads_link_node()
    {
        next = NULL;
    }

	// Constructor with copying ads_item.
    ads_link_node(const ads_item & initial_item)
	:item(initial_item)
    {
		++assignments_count;
        next = NULL;
    }
};

class ads_linked_list
{
    size_t length;
    ads_link_node* head;
    ads_link_node* tail;
	
protected:

	// Binary search for proper position of item within the sorted list.
	size_t binary_search(const ads_item& item, size_t beg=0, size_t end = INT32_MAX)
	{
		return 0; 
		// Implement this function;
	}
	
public:
    ads_linked_list()
    {
        length = 0;
        head = NULL;
        tail = NULL;
    }
	
	ads_link_node* get(size_t index)
	{
		return NULL; 
		// Implement this function;
	}
	
	ads_link_node* add(size_t index, const ads_item& item)
	{
		return NULL; 
		// Implement this function;
	}
	
	size_t append(const ads_item& item)
	{
		// Locate the proper position for the item to be inserted.
		size_t pos = binary_search(item);
		
		// Insert the new list node into this position.
		add(pos, item);
		
		return pos;
	}
};

//-------------------------------
// Insertion sort implementation

void insertion_sort_list(const std::vector<ads_item>& unsorted, ads_linked_list& sorted)
{
	// Implement insertion sort for dynamic list as a target storage.
	for (size_t i = 0; i<unsorted.size(); ++i)
	{
		sorted.append(unsorted[i]);
	}
}


//-------------------------------
// The main section

using namespace std;

int main(int argc, char* argv[])
{
	// One argument needed (length of the array to be sorted).
    if (argc != 2) 
	{
        cout << "Invalid number of arguments: " << argc-1 << " instead of 1." << endl;
		cout << "Please specify the length of the array to be sorted." << endl;
        return 1;
	}

	// argv[0] = program file name
    int array_len = atoi(argv[1]);
	
	// Initialize random number generator.
	srand(static_cast<unsigned int>(time(NULL)));
	
	// Define an unsorted array (of type 'vector') with random item values.
	std::vector<ads_item> unsorted(array_len);

	// Display info about operations counts.
	cout << "Vectors created : " << array_len << " items\n";
	cout << "Assignments : " << ads_item::assignments_count << " comparisons : ";
	cout << ads_item::comparisons_count << endl;

	// Define a dynamic list for sorted array.
	ads_linked_list sorted;
	
	// Run insertion list based on dinamic list.
	ads_item::reset();
	insertion_sort_list(unsorted, sorted);
	cout << "\nInsertion sort (dynamic list based): assignments : " << ads_item::assignments_count;
	cout << " comparisons : " << ads_item::comparisons_count << endl;

	return 0;
}