interval.cpp
/***************************************************************************
* 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"
#include <algorithm> //sort
#include <vector> //stal container
/*! \mainpage A C++ implementation of a O(n log n) algorithm computing a maximal stable set of an interval graph.
*/
using namespace std;
ENDPOINT::ENDPOINT(){
val=0;
is_left=true;
}
ENDPOINT::ENDPOINT(double x){
val=x;
is_left=true;
}
ENDPOINT::ENDPOINT(const ENDPOINT &x){
val=x.value();
is_left=x.is_left_endpoint();
}
ENDPOINT::~ENDPOINT(){
}
ENDPOINT & ENDPOINT::operator= (const ENDPOINT& x){
val=x.value();
is_left=x.is_left_endpoint();
}
ENDPOINT & ENDPOINT::operator= (const double& x){
val=x;
is_left=true;
}
INTERVAL::INTERVAL()
{
x=0;
y=0;
w=1;
}
INTERVAL::INTERVAL(double xx, double yy)
{
if(yy<xx) throw INVALID_INTERVAL(xx,yy);
x=xx;
x.set_left_endpoint(true);
y=yy;
y.set_left_endpoint(false);
w=1;
}
INTERVAL::INTERVAL(double xx, double yy, double ww)
{
if(yy<xx) throw INVALID_INTERVAL(xx,yy);
x=xx;
x.set_left_endpoint(true);
y=yy;
y.set_left_endpoint(false);
w=ww;
}
INTERVAL & INTERVAL::operator= (const INTERVAL& z){
x=z.left();
y=z.right();
if(x.value()>y.value()) throw INVALID_INTERVAL(x.value(),y.value());
}
INTERVAL::INTERVAL(ENDPOINT xx, ENDPOINT yy)
{
if(yy<xx) throw INVALID_INTERVAL(xx,yy);
x=xx;
x.set_left_endpoint(true);
y=yy;
y.set_left_endpoint(false);
w=1;
}
INTERVAL::INTERVAL(ENDPOINT xx, ENDPOINT yy, double ww)
{
if(yy<xx) throw INVALID_INTERVAL(xx,yy);
x=xx;
x.set_left_endpoint(true);
y=yy;
y.set_left_endpoint(false);
w=ww;
}
INTERVAL::~INTERVAL()
{
}
bool operator==(const ENDPOINT & x, const ENDPOINT &y){
return (x.value()==y.value()&&x.is_left_endpoint()==y.is_left_endpoint());
}
bool operator<=(const ENDPOINT &x, const ENDPOINT &y){
if (x.value()<y.value()) return true;
else if (x.value()>y.value()) return false;
else{
if (x.is_left_endpoint()&&!y.is_left_endpoint())return false;
else return true;
}
}
bool operator<(const ENDPOINT &x, const ENDPOINT &y){
if (x.value()<y.value()) return true;
else if (x.value()>y.value()) return false;
else{
if (x.is_left_endpoint()==y.is_left_endpoint())return false;
if (x.is_left_endpoint()&&!y.is_left_endpoint())return false;
if (!x.is_left_endpoint()&&y.is_left_endpoint())return true;
}
}
bool operator>(const ENDPOINT &x, const ENDPOINT &y){
if (x.value()>y.value()) return true;
else if (x.value()<y.value()) return false;
else{
if (x.is_left_endpoint()==y.is_left_endpoint())return false;
if (x.is_left_endpoint()&&!y.is_left_endpoint())return true;
if (!x.is_left_endpoint()&&y.is_left_endpoint())return false;
}
}
bool operator>=(const ENDPOINT & x, const ENDPOINT &y){
if (x.value()>y.value()) return true;
else if (x.value()<y.value()) return false;
else{
if (!x.is_left_endpoint()&&y.is_left_endpoint())return true;
else return true;
}
}
bool operator==(const INTERVAL& x, const INTERVAL &y){
return (x.left()==y.left()&&x.right()==y.right());
}
bool operator<(const INTERVAL &x, const INTERVAL &y){
return (x.right()<y.left());
}
bool operator>(const INTERVAL &x, const INTERVAL &y){
return ( x.left()>y.right());
}
INVALID_INTERVAL::INVALID_INTERVAL(double x, double y){
cerr<<"Invalid interval. Leftend="<< x <<". Rightend="<<y<<endl;
}
INVALID_INTERVAL::INVALID_INTERVAL(ENDPOINT x, ENDPOINT y){
cerr<<"Invalid interval. Leftend="<< x <<". Rightend="<<y;
}
ostream& operator<<(ostream &os, ENDPOINT x) /* output stream */
{
os<<x.value()<<' '<<x.is_left_endpoint();
return os;
}
istream& operator>>(istream &is, ENDPOINT &x) /* in stream */
{
double y;
bool isleft;
is>>y>>isleft;
x.setValue(y);
x.set_left_endpoint(isleft);
return is;
}
ostream& operator<<(ostream &os, INTERVAL x) /* output stream */
{
os<<x.left().value()<<' '<<x.right().value();
return os;
}
istream& operator>>(istream &is, INTERVAL &x) /* in stream */
{
ENDPOINT e;
double val;
//read left value
is>>val;
e.setValue(val);
e.set_left_endpoint(true);
x.set_left(e);
//read right value
is>>val;
e.setValue(val);
e.set_left_endpoint(false);
x.set_right(e);
return is;
}
int lexicographic_compare(const ENDPOINT &x, const ENDPOINT&y){
double xx=x.value();
double yy=y.value();
bool leftx=x.is_left_endpoint();
bool lefty=y.is_left_endpoint();
if(xx<yy) return -1;
if(xx>yy) return 1;
if(xx==yy) {
if (leftx && !lefty) return 1;
if (leftx && lefty) return 0;
if (!leftx && lefty) return -1;
if (!leftx && !lefty) return 0;
}
}
bool operator < (const SortTable& m1, const SortTable& m2)
{
return (m1.ep < m2.ep);
}
int MAXIMAL_STABLE_SET_IG(const std::list<INTERVAL> &intervals, int *colour){
std::vector<SortTable> endpoints(2*intervals.size()); // N is the number of intervals
std::list<INTERVAL>::const_iterator it;
std::vector<int> ASGN(intervals.size()), NEXT(intervals.size());
int i=0,j=0, temp, N;
int maxchan=0, counter=0, channel=0;
N=intervals.size();
if (N==0) return 0;
// construct the list of endpoints
for(it = intervals.begin(); it!=intervals.end(); it++){
endpoints[2*i].ep=it->left();
endpoints[2*i].interval_number=i;
endpoints[2*i+1].ep=it->right();
endpoints[2*i+1].interval_number=i;
i++;
}
//step 1 : sort the 2N endpoint tp obtain z_0 <= z_1 <= z_2 <= ....<= z_{2N-1}
// if z_i = z_1{i+1}= z_{i+2} we assure that the right enpoints appear before the left endpoints
std::sort (endpoints.begin(), endpoints.end());
// step 2 already made : maxchan=0, counter=0, channel=0;
//step 3
for(i=0;i<N;i++){
NEXT[i]=i+1;
}
//step 4
for(j=0;j<2*N;j++){
// if zj is a left endpoint of some interval Ik
// here, k = endpoints[j].interval_number
if(endpoints[j].ep.is_left_endpoint()) {
counter++;
maxchan=max(counter,maxchan);
ASGN[endpoints[j].interval_number]=channel;
channel=NEXT[channel];
}
else { // zj is a right endpoint of some interval Ik
counter --;
temp=ASGN[endpoints[j].interval_number];
NEXT[temp]=channel;
channel=temp;
}
}
// returns the colour of each interval
for(i=0;i<N;i++){
colour[i]=ASGN[i];
}
return maxchan;
}
int MAXIMAL_STABLE_SET_IG(const std::list<INTERVAL> &intervals){
std::vector<SortTable> endpoints(2*intervals.size()); // N is the number of intervals
std::list<INTERVAL>::const_iterator it;
std::vector<int> ASGN(intervals.size()), NEXT(intervals.size());
int i=0,j=0, temp, N;
int maxchan=0, counter=0, channel=0;
N=intervals.size();
if (N==0) return 0;
// construct the list of endpoints
for(it = intervals.begin(); it!=intervals.end(); it++){
endpoints[2*i].ep=it->left();
endpoints[2*i].interval_number=i;
endpoints[2*i+1].ep=it->right();
endpoints[2*i+1].interval_number=i;
i++;
}
//step 1 : sort the 2N endpoint tp obtain z_0 <= z_1 <= z_2 <= ....<= z_{2N-1}
// if z_i = z_1{i+1}= z_{i+2} we assure that the right enpoints appear before the left endpoints
std::sort (endpoints.begin(), endpoints.end());
// step 2 already made : maxchan=0, counter=0, channel=0;
//step 3
for(i=0;i<N;i++){
NEXT[i]=i+1;
}
//step 4
for(j=0;j<2*N;j++){
// if zj is a left endpoint of some interval Ik
// here, k = endpoints[j].interval_number
if(endpoints[j].ep.is_left_endpoint()) {
counter++;
maxchan=max(counter,maxchan);
ASGN[endpoints[j].interval_number]=channel;
channel=NEXT[channel];
}
else { // zj is a right endpoint of some interval Ik
counter --;
temp=ASGN[endpoints[j].interval_number];
NEXT[temp]=channel;
channel=temp;
}
}
return maxchan;
}
