/***************************************************************************
 *   Copyright (C) 2007 by Touati Sid                                      *
 *   Sid-nospam.Touati-nospam@univ-cotedazur-nospam.fr                                     *
 *   Copyright  INRIA and the University of Versailles                     *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
***************************************************************************/
 
#include "interval.h"

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
  std::list<INTERVAL> intervals;
	std::list<INTERVAL>::iterator it;	
  int alpha, i, colour[200];
 /*  example of the paper: U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the  channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810 */
  intervals.push_back(INTERVAL(1,4));
  intervals.push_back(INTERVAL(2,8));
  intervals.push_back(INTERVAL(3,6));
  intervals.push_back(INTERVAL(5,10));
  intervals.push_back(INTERVAL(7,13));
  intervals.push_back(INTERVAL(9,11));
  intervals.push_back(INTERVAL(12,14));
  alpha=MAXIMAL_STABLE_SET_IG(intervals, &colour[0]);
  cout<<"The First example is the one explained in the paper : U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the  channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810.\n";
  cout<<"The minimal number of colours is "<<alpha<<endl;
  it=intervals.begin();
  for(i=0;i<intervals.size();i++){
  	cout<<"Interval number "<<i<<" : "<<*it;
  	cout<<" Coloured with colour number "<<colour[i]<<endl;
	it++;
  }

  cout<<"------------------------------\n";
  cout<<"Now another (tricky) example.\n";
  cout<<"-------------------------------\n";
  // another tricky example
  intervals.push_back(INTERVAL(10,11));
  intervals.push_back(INTERVAL(5,14));
  intervals.push_back(INTERVAL(5,10));
  intervals.push_back(INTERVAL(1,9));
  intervals.push_back(INTERVAL(6,8));
  intervals.push_back(INTERVAL(8,10));
  intervals.push_back(INTERVAL(9,12));

  alpha=MAXIMAL_STABLE_SET_IG(intervals, &colour[0]);
	it=intervals.begin();
  cout<<"Now, the minimal number of colours is "<<alpha<<endl;
  for(i=0;i<intervals.size();i++){
  	cout<<"Interval number "<<i<<" : "<<*it;
  	cout<<" Coloured with colour number "<<colour[i]<<endl;
	 it++;
  }
  return EXIT_SUCCESS;
}