#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <limits.h>
#include <assert.h>

class LinkedList
{
	int first, nnz;
	const int EOL = INT_MAX-1;
	std::vector<int> next;
	std::vector<double> value;
public:
	LinkedList(int num_elements)
	{
		first = EOL;
		nnz = 0;
		next.resize(num_elements,INT_MAX);
		value.resize(num_elements,0.0);
	}
	double & operator [](int i)
	{
		if( next[i] == INT_MAX )
		{
			next[i] = first;
			first = i;
			nnz++;
		}
		return value[i];
	}
	void Put(int i1, int i2, const std::vector<int> & ja, const std::vector<double> & a, double coef)
	{
		assert(Empty());
		for(int i = i1; i < i2; ++i)
		{
			value[ja[i]] = a[i]*coef;
			next[ja[i]] = first;
			first = ja[i];
			nnz++;
		}
	}
	void Add(int i1, int i2, const std::vector<int> & ja, const std::vector<double> & a, double coef)
	{
		for(int i = i1; i < i2; ++i)
		{
			value[ja[i]] += a[i]*coef;
			if( next[ja[i]] == INT_MAX )
			{
				next[ja[i]] = first;
				first = ja[i];
				nnz++;
			}
		}
	}
	void Sort()
	{
		std::vector<int> cols(nnz);
		int i = first, k = 0;
		while(i != EOL)
		{
			cols[k++] = i;
			i = next[i];
		}
		if( !cols.empty() )
		{
			std::sort(cols.begin(),cols.end());
			first = cols[0];
			for(int q = 1; q < (int)cols.size(); ++q)
				next[cols[q-1]] = cols[q];
			next[cols.back()] = EOL;
		}
	}
	void Mult(double coef)
	{
		int i = first;
		while( i != EOL )
		{
			value[i] *= coef;
			i = next[i];
		}
	}
	void Get(std::vector<int> & ja, std::vector<double> & a) const
	{
		int i = first;
		while( i != EOL )
		{
			ja.push_back(i);
			a.push_back(value[i]);
			i = next[i];
		}
	}
	void Clear()
	{
		int i = first, j;
		while(i != EOL)
		{
			j = next[i];
			value[i] = 0.0;
			next[i] = INT_MAX;
			i = j;
		}
		first = EOL;
		nnz = 0;
	}
	void Print() const
	{
		int i = first;
		while( i != EOL )
		{
			std::cout << "[" << i << "]: " << value[i] << std::endl;
			i = next[i];
		}
	}
	int Size() const {return nnz;}
	bool Empty() const {return first == EOL;}
};

int main(int argc, char ** argv)
{
	//input vectors
	std::vector<int>    c1 = {    0,     5,   10,    20};
	std::vector<double> v1 = {  0.1,   2.0,  0.5,   4.0};
	
	std::vector<int>    c2 = {    0,     5,   20,    25,    39};
	std::vector<double> v2 = { 0.45, -0.25, -1.5,  0.25,  0.25};
	
	std::vector<int>    c3 = {   10,     5,   15,    35,    25,    39};
	std::vector<double> v3 = { 0.25, -0.25,  0.5,   0.5,  0.25,  0.25};
	//output vectors
	std::vector<int>    co;
	std::vector<double> vo;
	LinkedList List(40);
	List.Add(0,4,c1,v1,1.0);
	List.Add(0,5,c2,v2,2.0);
	List.Add(0,6,c3,v3,2.0);
	List[17] = 1.0;
	List.Sort();
	List.Get(co,vo);
	List.Clear();
	//expect (0, 1) (5, 1) (10, 1) (15, 1) (17, 1) (20, 1) (25, 1) (35, 1) (39, 1)
	for(int i = 0; i < (int)co.size(); ++i)
		std::cout << "(" << co[i] << ", " << vo[i] << ") ";
	std::cout << std::endl;
	return 0;
}