interval.h
/***************************************************************************
* 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. *
***************************************************************************/
#ifndef __interval_H
#define __interval_H
/*! \file interval.h
\brief This is a header file of the classes and functions implementing an O(n log n) algorithm computing a maximal stable set in an interval graph. In fact, our implementation takes a set of intervals, not an interval graph.
*/
#include <iostream>
#include <list> // stl standard container
using namespace std;
/** \internal
* \class ENDPOINT
* \brief this class represents the endpoints of the intervals. An ENDPOINT object is defined by its value, and by its side (left or right endpoint).
@author Sid Touati
*/
class ENDPOINT{
private:
double val;
bool is_left;
public:
/** \internal
*
* Construct a zero left endpoint.
*/
ENDPOINT();
/** \internal
*
* Construct a left endpoint with an initial value.
*/
ENDPOINT(double val);
/** \internal
*
* Construct a left endpoint from another endpoint.
*/
ENDPOINT(const ENDPOINT &x);
~ENDPOINT();
/** \internal
*
* Copy operator from another endpoint.
*/
ENDPOINT &operator= (const ENDPOINT&);
/** \internal
*
* Copy operator from a value of type double. It creates a left endpoint with the given value.
*/
ENDPOINT &operator= (const double&);
/** \internal
*
* Prints the value of the endpoint and the flag saying whether it is a left or a right endpoint. The flag is true if the endpoint is a left one, and is false if the endpoint is a right one.
*/
friend ostream& operator<<(ostream &os, ENDPOINT x);
/** \internal
*
* Reads the value of the endpoint and the flag saying whether it is a left or a right endpoint. The flag should be true if the endpoint is a left one, and set to false if the endpoint is a right one.
*/
friend istream& operator>>(istream &is, ENDPOINT &x);
/** \internal
*
* Sets a flag saying wether the endpoint is a left endpoint or a right endpoint. The flag should be set to true if the endpoint is a left one, and set to false if the endpoint is a right one.
*/
void set_left_endpoint ( bool theValue )
{
is_left = theValue;
}
/** \internal
*
* @return true if the endpoint is a left endpoint. Returns false if it is a right endpoint.
*/
bool is_left_endpoint() const
{
return is_left;
}
/** \internal
*
* Sets the value of the endpoint.
*/
void setValue ( double theValue )
{
val = theValue;
}
/** \internal
*
* \returns the value of the endpoint.
*/
double value() const
{
return val;
}
};
/** \internal
*
* Two endpoints are said equal if they have the same value and if they are both left endpoint (or both are right endpoint).
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator==(const ENDPOINT&x, const ENDPOINT&y);
/** \internal
*
* \returns true if the value of x is lower than the value of y. If the values are the same, returns true if the two endpoints are both left ones (or both right ones).
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator<=(const ENDPOINT&x, const ENDPOINT&y);
/** \internal
*
* \returns true if the value of x is lower than the value of y. If the values are the same, returns true if x is a right endpoint and y a left endpoint.
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator<(const ENDPOINT&x, const ENDPOINT&y);
/** \internal
*
* \returns true if the value of x is greater than the value of y. If the values are the same, returns true if x is a left endpoint and y a right endpoint.
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator>(const ENDPOINT&x, const ENDPOINT&y);
/** \internal
*
* \returns true if the value of x is greater than the value of y. If the values are the same, returns true if x and y are both left points (or both right points).
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator>=(const ENDPOINT&x, const ENDPOINT&y);
/*! \class INTERVAL
\brief This class represents a closed interval object. An interval is a pair of double values [x,y], representing all values (of type double) starting from x to y. We name them the left and the right of the interval. Also, we ca associate a cost (weight) to an interval.
\author Sid Touati
*/
class INTERVAL{
private:
ENDPOINT x;
ENDPOINT y;
double w;
public:
/** \name Creation */
//@{
/**
* Constructor of an empty interval [0,0] with a unit cost.
*/
INTERVAL();
/**
* Constructor with two arguments, the left and the right values of the interval.
* @param x the left value
* @param y the right value
* \throw INVALID_INTERVAL if x>y
*/
INTERVAL(double x, double y);
/**
* Constructor with three arguments.
* @param x the left value
* @param y the right value
* @param w the weight
* \throw INVALID_INTERVAL if x>y
*/
INTERVAL(double x, double y, double w);
INTERVAL(ENDPOINT x, ENDPOINT y);
INTERVAL(ENDPOINT x, ENDPOINT y, double w);
INTERVAL &operator= (const INTERVAL&);
~INTERVAL();
//@}
/** \name INPUT/OUTPUT*/
//@{
/**
* Output stream. Prints left and right values in this order.
*/
friend ostream& operator<<(ostream &os, INTERVAL x);
/**
* Input stream. Reads left and right values in this order.
*/
friend istream& operator>>(istream &is, INTERVAL &x);
//@}
/** \name Access operations*/
//@{
/**
* Returns the weight of the interval.
*/
double weight() const
{
return w;
}
ENDPOINT left() const
{
return x;
}
ENDPOINT right() const
{
return y;
}
/**
* Returns the left value of the interval.
*/
double left_value()
{
return x.value();
}
/**
* Returns the right value of the interval.
*/
double right_value()
{
return y.value();
}
//@}
/** \name Update operations*/
//@{
/**
* Sets the weight of the interval.
*/
void setWeight ( double theValue )
{
w = theValue;
}
void set_left ( ENDPOINT theValue )
{
x = theValue;
}
void set_right ( ENDPOINT theValue )
{
y = theValue;
}
/**
* Sets the left value of the interval.
*/
void set_left_value ( double theValue )
{
x.setValue(theValue);
}
/**
* Sets the right value of the interval.
*/
void set_right_value ( double theValue )
{
y.setValue(theValue);
}
//@}
};
/* for internal use */
struct SortTable
{
ENDPOINT ep;
int interval_number;
};
/** \internal
*
* \returns true if the endpoints of the two intervals are equal, side by side.
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator==(const INTERVAL& I , const INTERVAL& J);
/** \internal
*
* \returns true if the right endpoint of I is before the left endpoint of J.
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator<(const INTERVAL& I, const INTERVAL& J);
/** \internal
*
* \returns true if the left endpoint of I is after the right endpoint of J.
*
\remarks if two endpoints have the same value, we assume that right endpoints are before left endpoint.
*/
bool operator>(const INTERVAL& I, const INTERVAL& J);
/** \internal
@author Sid Touati
* This is an exception class thrown when an interval is invalid.
*/
class INVALID_INTERVAL{
public:
INVALID_INTERVAL(double x, double y);
INVALID_INTERVAL(ENDPOINT x, ENDPOINT y);
INVALID_INTERVAL();
};
int lexicographic_compare(const ENDPOINT &, const ENDPOINT&);
/*! \fn int MAXIMAL_STABLE_SET_IG(const std::list<INTERVAL> & intervals, int *colour);
* This function implements the algorithm described in
* 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
* It computes the minimal number of colour for a set of intervals. Two interfering intervals should not have the same colour. The algorithms runs in \f$ O(n \times \log n) \f$.
* @param[in] intervals A list containing the intervals to be processed
* @param[out] colour \f$ colour[i] \f$ is the colour of the interval number i. Two interfering intervals should not have the same colour. \f$ \forall I,J: I \cap J \neq \phi \Longrightarrow colour[I] \neq colour[J] \f$.
* @return \f$ \alpha \f$ the minimal number of colours. Colours are numbered from 0 to \f$ \alpha-1 \f$. This function returns -1 if error.
\remarks The weight of the intervals are useless for this algorithm.
* \pre the size of the coulour vector should at least equal to the number of input intervals.
*/
int MAXIMAL_STABLE_SET_IG(const std::list<INTERVAL> & intervals, int *colour);
/*! \fn int MAXIMAL_STABLE_SET_IG(const std::list<INTERVAL> & intervals, int *colour);
* This function implements the algorithm described in
* 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
* It computes the minimal number of colour for a set of intervals. Two interfering intervals should not have the same colour. The algorithms runs in \f$ O(n \times \log n) \f$.
* @param[in] intervals A list containing the intervals to be processed
* @return \f$ \alpha \f$ the minimal number of colours. This function returns -1 if error.
\remarks The weight of the intervals are useless for this algorithm.
*/
int MAXIMAL_STABLE_SET_IG(const std::list<INTERVAL> & intervals);
#endif
