#include <iostream>
using namespace std;

class IntervalSet;
class Interval
	{
   public:
		double begin, end;
		bool left, right;
		bool empty;
		
		Interval():empty(true) {}
		Interval(double b, double e, bool l = false, bool r = false): begin(b), end(e), left(l), right(r), empty(false)
			{if ((b == e) && (l == r) && !l )  empty = true; }	
		Interval(double b): begin(b), end(b), left(true), right(true), empty(false){}
		Interval& operator=(const Interval &a);
		friend ostream& operator<<(ostream& stream, const Interval &a);
		friend bool operator==(const Interval &b, const Interval &a);
		friend bool contains(const Interval &b, double a);
		friend IntervalSet operator-(const Interval &b, const Interval &a);
		friend IntervalSet operator+(const Interval &b, const Interval &a);
		friend IntervalSet operator^(const Interval &b, const Interval &a);
		friend IntervalSet operator-(const IntervalSet &b, const Interval &a);
		friend IntervalSet operator+(const IntervalSet &b, const Interval &a);
		friend IntervalSet operator^(const IntervalSet &b, const Interval &a);
		friend IntervalSet operator-(const IntervalSet &b, const IntervalSet &a);
		friend IntervalSet operator+(const IntervalSet &b, const IntervalSet &a);
		friend IntervalSet operator^(const IntervalSet &b, const IntervalSet &a);
	};

class IntervalSet 
	{
    public:
		Interval *mass;
		int length;
		bool empty;
		
		IntervalSet () : mass(NULL), length(0), empty(true) {};
		IntervalSet (const Interval &a) 
			{
			if (!a.empty)
				{
				mass = new Interval[1];
				mass[0] = a;
				length = 1;
				empty = false;
				}
			else
				{
				mass = NULL;
				empty = true;
				length = 0;
				}
			}
		IntervalSet (const IntervalSet &a) 
			{
			int i;
			
			empty = a.empty;
			if (!empty)
				{
				length = a.length;
				mass = new Interval[length];
				for(i = 0; i < length; i++) mass[i] = a.mass[i];
				empty = a.empty;
				}
			};
		IntervalSet& operator=(const IntervalSet &a);
		IntervalSet& operator+=(const Interval &a);
		IntervalSet& operator-=(const Interval &a);
		IntervalSet& operator+=(const IntervalSet &a);
		IntervalSet& operator-=(const IntervalSet &a);
		friend bool contains(const IntervalSet &b, double a);
		friend bool contains(const Interval &b, double a);
		friend ostream& operator<<(ostream& stream, const IntervalSet &a);
		friend bool operator==(const IntervalSet &b, const IntervalSet &a);
		friend IntervalSet operator-(const Interval &b, const Interval &a);
		friend IntervalSet operator+(const Interval &b, const Interval &a);
		friend IntervalSet operator^(const Interval &b, const Interval &a);
		friend IntervalSet operator-(const IntervalSet &b, const Interval &a);
		friend IntervalSet operator+(const IntervalSet &b, const Interval &a);
		friend IntervalSet operator^(const IntervalSet &b, const Interval &a);
		friend IntervalSet operator-(const IntervalSet &b, const IntervalSet &a);
		friend IntervalSet operator+(const IntervalSet &b, const IntervalSet &a);
		friend IntervalSet operator^(const IntervalSet &b, const IntervalSet &a);
	};



ostream& operator<<(ostream& stream, const Interval &a)
	{
	
	if (!a.empty)
		{
		if (a.left) stream << '[';
			else stream << '(';
		if (a.begin != a.end) stream << a.begin << ';';
		stream << a.end;
		if (a.right) stream << ']';
			else stream << ')';
		}
	else stream << "empty";
	
	return stream;
	}

ostream& operator<<(ostream& stream, const IntervalSet &a)
	{
    int i;
	
	if (!a.empty)
		{
		for (i = 0; i < a.length; i++)
			{
			stream << a.mass[i];
			if (i != a.length - 1) stream << " + ";
			}
		}
	else stream << "empty";
	
	return stream;
	}



Interval& Interval:: operator=(const Interval &a)
	{
	
	begin = a.begin;
	end = a.end;
	left = a.left;
	right = a.right;
	empty = a.empty;
		
	return (*this);
	}

IntervalSet& IntervalSet:: operator=(const IntervalSet &a)
	{
    int i;
	
	length = a.length;
	mass = new Interval[length];
	for (i = 0; i < length; i++) mass[i] = a.mass[i];
	empty = a.empty;
	
 //cout << (*this);
	return (*this);
	}	   



bool operator==(const Interval &b, const Interval &a)
	{
	return ((b.begin == a.begin) && (b.end == a.end) && (b.left == a.left) && (b.right == a.right) && (b.empty == a.empty));
	}

bool operator==(const IntervalSet &b, const IntervalSet &a)
	{
	bool t = false;
	int i;
	
	if ((b.length == a.length) && (b.empty == a.empty))
		{
		for (i = 0; i < a.length; i++) t = t || (b.mass[i] == a.mass[i]);
		}
	
	return t;
	}



bool contains(const Interval &b, const double a)
	{
	return (((a > b.begin) && (a < b.end)) || ((a == b.begin) && (b.begin)) || ((a == b.begin) && (b.begin)));
	}

bool contains(const IntervalSet &b, const double a)
	{
	bool s, t = false;
	int i;
	
	if ((a >= b.mass[0].begin) && (a <= b.mass[b.length - 1].end))
		for (i = 0; i < b.length; i++) 
          {
          s = contains(b.mass[i], a); 
          t = t || s;
          }
	
	return t;
	}



IntervalSet operator-(const Interval &b, const Interval &a)
	{
	IntervalSet temp(b);
	
	temp = temp - a;
	//for (;;);
	
	return temp;
	}

IntervalSet operator+(const Interval &b, const Interval &a)
	{
	IntervalSet temp(b);
	
	temp = temp + a;
	
	return temp;
	}

IntervalSet operator^(const Interval &b, const Interval &a)
	{
	return ((a + b) - ((a - b) + (b - a)));
	}



IntervalSet operator-(const IntervalSet &b, const Interval &a)
	{
	int bb, be, eb, ee, i, lentmp, t = 0;
	IntervalSet temp;
	bool o,p;
       
	if (!a.empty)
		{
		p = (a.begin == b.mass[0].begin) && (a.left >= b.mass[0].left);
		o = (a.end == b.mass[b.length - 1].end) && (a.right >= b.mass[b.length - 1].right);
		//c = ((((a.begin > b.mass[0].begin) || p) || ((a.end < b.mass[b.length - 1].end)) || o));
		//cout << c << o << p << endl;
		
		if ((((a.begin > b.mass[0].begin) || p) || ((a.end < b.mass[b.length - 1].end)) || o))
			{
			for(i = 0; (((a.begin < b.mass[i].begin) || ((a.begin == b.mass[i].begin) && (a.left <= b.mass[i].left)))&& ( i < b.length )); ++i);
			bb = i;// последний эл-т меньший begin
			for(i = 0; (((a.begin < b.mass[i].end) || ((a.begin == b.mass[i].end) && ((a.left == b.mass[i].right) && (a.left == true)))) && ( i < b.length )); ++i);
			be = i;// последний эл-т меньший end
			for(i = 0; (((a.end < b.mass[i].begin) || ((a.end == b.mass[i].begin) && ((a.right == b.mass[i].left) && (a.left == true))))&& ( i < b.length )); ++i);
			eb = i;// последний эл-т меньший begin
			for(i = 0; (((a.end < b.mass[i].end) || ((a.end == b.mass[i].end) && (a.right <= b.mass[i].right)))&& ( i < b.length )); ++i);
			ee = i;// последний эл-т меньший end
			//cout << bb << be << eb << ee << endl;
			if ((ee == eb) && (ee == bb) && (be == bb)) return (b);
			//if ((ee == eb) || (be == bb)) t = 1;
			//for (;;);
			temp.length = b.length + (be - bb + ee - eb) / 2 ;
			lentmp = (ee - eb + be - bb) / 2;
			      
                  //cout << temp.length << endl;
				temp.mass = new Interval[temp.length];
            temp.empty = false;
                  //cout << b << endl;
                  //cout << a << endl;
				for(i = 0; i <= eb; i++) temp.mass[i] = b.mass[i];
				for(i = eb + lentmp; i < temp.length; i++) temp.mass[i] = b.mass[i - lentmp];
				if (eb != ee)
					{
					if (temp.mass[eb + lentmp].begin != a.end)
						{
						temp.mass[eb + lentmp].begin = a.end;
						temp.mass[eb + lentmp].left = true - a.right;
						}
					else if (temp.mass[eb + lentmp].left < a.left) temp.mass[eb + lentmp].left = true - a.right;
					}
				if (bb != be) 
					{
					if (temp.mass[eb].end != a.begin)
						{
                        temp.mass[eb].end = a.begin;
						temp.mass[eb].right = true - a.left;
						}
					else if (temp.mass[eb].right > a.right) temp.mass[eb].right = true - a.left;
					}
				}
			}
	//cout << temp << endl;
	return temp;
    }

IntervalSet operator+(const IntervalSet &b, const Interval &a)
	{
	int bb, be, eb, ee, i, lentmp, t = 0;
	IntervalSet temp;
	bool o,p;
       
	if (!a.empty)
		{
		p = (a.begin == b.mass[0].begin) && (a.left <= b.mass[0].left);
		o = (a.end == b.mass[b.length - 1].end) && (a.right <= b.mass[b.length - 1].right);
		//c = ((((a.begin > b.mass[0].begin) || p) || ((a.end < b.mass[b.length - 1].end)) || o));
		//cout << c << o << p << endl;
		
		if ((((a.begin > b.mass[0].begin) || p) || ((a.end < b.mass[b.length - 1].end)) || o))
			{
			for(i = 0; (((a.begin > b.mass[i].begin) || ((a.begin == b.mass[i].begin) && (a.left <= b.mass[i].left)))&& ( i < b.length )); ++i);
			bb = i;// последний эл-т меньший begin
			for(i = 0; (((a.begin > b.mass[i].end) || ((a.begin == b.mass[i].end) && ((a.left == b.mass[i].right) && (a.left == true)))) && ( i < b.length )); ++i);
			be = i;// последний эл-т меньший end
			for(i = 0; (((a.end > b.mass[i].begin) || ((a.end == b.mass[i].begin) && ((a.right == b.mass[i].left) && (a.left == true))))&& ( i < b.length )); ++i);
			eb = i;// последний эл-т меньший begin
			for(i = 0; (((a.end > b.mass[i].end) || ((a.end == b.mass[i].end) && (a.right <= b.mass[i].right)))&& ( i < b.length )); ++i);
			ee = i;// последний эл-т меньший end
			//cout << bb << be << eb << ee << endl;
			if ((ee != eb) && (be != bb)) return (b);
			if ((ee == eb) && (be == bb)) t = 1;
			//for (;;);
			temp.length = b.length + t + (be - bb + ee - eb) / 2 ;
			lentmp = t + (ee - eb + be - bb) / 2;
			      
                  //cout << temp.length << endl;
				temp.mass = new Interval[temp.length];
            temp.empty = false;
                  //cout << b << endl;
                  //cout << a << endl;
				for(i = 0; i <= eb; i++) temp.mass[i] = b.mass[i];
				for(i = eb + lentmp; i < temp.length; i++) temp.mass[i] = b.mass[i + lentmp];
				if (eb == ee)
					{
					if (temp.mass[eb + lentmp].begin != a.end)
						{
						temp.mass[eb + lentmp].begin = a.end;
						temp.mass[eb + lentmp].left = a.right;
						}
					else if (temp.mass[eb + lentmp].left < a.left) temp.mass[eb + lentmp].left = a.right;
					}
				if (bb == be) 
					{
					if (temp.mass[eb].end != a.begin)
						{
                        temp.mass[eb].end = a.begin;
						temp.mass[eb].right = a.left;
						}
					else if (temp.mass[eb].right > a.right) temp.mass[eb].right = a.left;
					}
				}
		else 
		     {
           IntervalSet temp1(a);
           return temp1;
           }
		}
	//cout << temp << endl;
	return temp;
    }
	
IntervalSet operator^(const IntervalSet &b, const Interval &a)
	{
	return ((a + b) - ((a - b) + (b - a)));
	}



IntervalSet operator-(const IntervalSet &b, const IntervalSet &a)
	{
	IntervalSet temp;
	int i;
	
	temp = b;
	for (i = 0; i < a.length; i++) temp = temp - a.mass[i];
	
	return temp;
	}

IntervalSet operator+(const IntervalSet &b, const IntervalSet &a)
	{
	IntervalSet temp;
	int i;
	
	temp = b;
	for (i = 0; i < a.length; i++) temp = temp + a.mass[i];
	
	return temp;
	}
	
IntervalSet operator^(const IntervalSet &b, const IntervalSet &a)
	{
	return ((a + b) - ((a - b) + (b - a)));
	}



IntervalSet& IntervalSet:: operator+=(const Interval &a)
	{
	
	(*this) = (*this) + a;
	
	return (*this);
	}
	
IntervalSet& IntervalSet:: operator-=(const Interval &a)
	{
	
	(*this) = (*this) - a;
	
	return (*this);
	}



IntervalSet& IntervalSet:: operator+=(const IntervalSet &a)
	{
	
	(*this) = (*this) + a;
	
	return (*this);
	}

IntervalSet& IntervalSet:: operator-=(const IntervalSet &a)
	{
	
	(*this) = (*this) - a;
	
	return (*this);
	}

int test()
    {
    Interval A(5,8,false,true),B(6,10,false,true); 
    IntervalSet C(A);
    
    
    C = A + B;
    C = A - B;
    //cout << C << endl;
    
    
    for( ; ; );     
    return 0;     
    }
	
#include <check-h2.h>