interval_set.h

Go to the documentation of this file.

// Interval Union Class -*- C++ -*-

// $Id: interval_set.h 972 2010-02-09 08:18:05Z herman $
// Copyright (C) 2005 Ferenc Domes
//
// This file is part of the COCONUT API.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library 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
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

//------------------------------------------------------------------------------
// IMPLEMENTAION
//------------------------------------------------------------------------------
#ifndef __INTERVAL_SET_H__
#define __INTERVAL_SET_H__

#include <math.h>
#include "interval.h"

#define SET_BASE_LENGTH 5
#define SET_EXT 5
#define SET_DEF_MAX_LENGTH 20
#define SET_DEF_FILL 2


namespace coco{

//CLASSDEF
class interval_set
{
        private:
                interval *data;
                int length;
                mutable int maxlength,extension;
                bool sorting;
                unsigned int MAXLEN,fillextension;

                void sort();
        public:

                inline interval_set(void);
                inline interval_set(double a);
                inline interval_set(double a, double b);
                inline interval_set(const interval &a);
                inline interval_set(const interval &a,const  interval &b);
                inline interval_set(const interval_set &a);
                virtual ~interval_set();
                interval_set& operator=(const interval_set &a);
                
                void setSorting(bool s);
                inline bool getSorting() const;
                inline int getLength() const;

                inline unsigned int get_maxlen() const;
                inline void set_maxlen(unsigned int m);
                inline unsigned int get_fillext() const;
                inline void set_fillext(unsigned int m);

                inline unsigned int num_of_gaps() const;
                
                inline bool is_empty() const;
                bool is_subset(const interval_set &a) const;
                bool is_subset(const interval &a) const;
                
                inline interval &operator[](int pos) const;
                void add(const interval &a);
                inline void add(const interval_set &a);
                interval remove(int pos);
                inline interval removeFirst ();
                inline void trimToSize();
                inline void trimintervaloSize();

                //finds the interval a in the set.not found:-1
                inline int find(const interval &a);
                //checks if the interval in the set contains a
                inline bool contains(double a) const;
                inline bool contains(const interval &a) const;
                //concatenates the set with a
                inline void conc(const interval &a);
                //substracts an interval from the sets: set.conc(!(set.conc(a)))
                interval_set remove(const interval &a);

                //returns the minimum/maximum interval of the set
                interval minimum() const;
                interval maximum() const;
                //hull
                interval hull() const;
                double width() const;
                
                interval_set& round_to_integer();
  
                interval_set& intersectwith(const interval_set &a);
                void intersect_power(const interval_set &a, int n);
                void intersect_div(const interval_set &a, const interval_set &b);
                void intersect_invsqr_wc(const interval_set &a, double b, double c);
                void intersect_invpower_wc(const interval_set &a, double b, int n);
                void intersect_invsin_wc(const interval_set &a, double b, double c);
                void intersect_invcos_wc(const interval_set &a, double b, double c);
                void intersect_invgauss_wc(const interval_set &a, double b, double c, double d);
                interval_set& operator +=(const interval_set &a);
                interval_set& operator -=(const interval_set &a);
                interval_set& operator *=(const interval_set &a);
                interval_set& operator /=(const interval_set &a);
};

double width(const interval_set& a);
//OPERATORS
inline interval_set operator +(const interval_set &a, const interval_set &b);
inline interval_set operator +(const interval_set &a,const interval &b);
inline interval_set operator +(const interval &a,const interval_set &b);
inline interval_set operator +(const interval_set &a,double b);
inline interval_set operator +(double a,const interval_set &b);

inline interval_set operator -(const interval_set &a,const interval_set &b);
inline interval_set operator -(const interval_set &a,const interval &b);
inline interval_set operator -(const interval &a,const interval_set &b);
inline interval_set operator -(const interval_set &a, double b);
inline interval_set operator -(double a,const interval_set &b);
inline interval_set operator -(const interval_set &a);

inline interval_set operator *(const interval_set &a,const interval_set &b);
inline interval_set operator *(const interval_set &a,const interval &b);
inline interval_set operator *(const interval &a,const interval_set &b);
inline interval_set operator *(const interval_set &a, double b);
inline interval_set operator *(double a,const interval_set &b);

interval_set divide(const interval &a,const interval &b);
inline interval_set divide(const interval &a,double b);
inline interval_set divide(double a,const interval &b);

inline interval_set operator /(const interval_set &a,const interval_set &b);
inline interval_set operator /(const interval_set &a,const interval &b);
inline interval_set operator /(const interval &a,const interval_set &b);
inline interval_set operator /(const interval_set &a, double b);
inline interval_set operator /(double a,const interval_set &b);

bool operator ==(const interval_set &a,const interval_set &b);

//FUNCTIONS
interval_set imin(const interval_set &a, const interval_set &b);
interval_set imax(const interval_set &a, const interval_set &b);
interval_set power(const interval_set &a, int n);
interval_set sqr(const interval_set &a);
interval_set sqrt(const interval_set &a);
interval_set exp(const interval_set &a);
interval_set log(const interval_set &a);
interval_set abs(const interval_set &a);
interval_set sin(const interval_set &a);
interval_set cos(const interval_set &a);
interval_set pow(const interval_set &a, const interval_set &b);
interval_set atan2(const interval_set &a, const interval_set &b);

interval_set round_to_integer(const interval_set &a);
  
//CONSTRUCTORS
inline interval_set::interval_set()
        :length(0), maxlength(SET_BASE_LENGTH), extension(SET_EXT), sorting(true), MAXLEN(SET_DEF_MAX_LENGTH), fillextension(SET_DEF_FILL)
{
        data=new interval[extension];
}
inline interval_set::interval_set(double a)
        :length(1), maxlength(SET_BASE_LENGTH), extension(SET_EXT), sorting(true), MAXLEN(SET_DEF_MAX_LENGTH), fillextension(SET_DEF_FILL)
{
        data=new interval[extension];
        data[0]=interval(a);
}
inline interval_set::interval_set(double a, double b)
        :length(1), maxlength(SET_BASE_LENGTH), extension(SET_EXT), sorting(true), MAXLEN(SET_DEF_MAX_LENGTH), fillextension(SET_DEF_FILL)
{
        data=new interval[extension];
        data[0]=interval(a,b);
}
inline interval_set::interval_set(const interval &a)
        :length(1), maxlength(SET_BASE_LENGTH), extension(SET_EXT), sorting(true), MAXLEN(SET_DEF_MAX_LENGTH), fillextension(SET_DEF_FILL)
{
        data=new interval[extension];
        data[0]=a;
}
inline interval_set::interval_set(const interval &a, const interval &b)
        :length(2), maxlength(SET_BASE_LENGTH), extension(SET_EXT), sorting(true), MAXLEN(SET_DEF_MAX_LENGTH), fillextension(SET_DEF_FILL)
{
        data=new interval[extension];
        data[0]=a;data[1]=b;
}
inline interval_set::interval_set(const interval_set &a)
        :length(a.length), maxlength(a.maxlength), extension(a.extension), sorting(a.sorting), MAXLEN(a.MAXLEN), fillextension(a.fillextension)
{
        data=new interval[maxlength];
        for (int i=0;i<length;i++)
                data[i]=a.data[i];
}
inline interval_set::~interval_set()
{
        if(data) delete[] data;
}
//CLASS METHODS
inline int interval_set::getLength() const
{
        return length;
}

inline bool interval_set::getSorting () const{
        return sorting;
}

inline unsigned int interval_set::get_maxlen () const{
        return MAXLEN;
}

inline void interval_set::set_maxlen (unsigned int m) {
        MAXLEN = m;
}

inline unsigned int interval_set::get_fillext () const{
        return fillextension;
}

inline void interval_set::set_fillext (unsigned int m) {
        fillextension = m;
}

inline bool interval_set::is_empty() const{
        return length==0;
}

inline interval &interval_set::operator[] (int pos) const {
        if(pos<length)
                return data[pos];
        std::cerr <<__FILE__<< " : " <<__LINE__ << " : " <<__COCONUT_PRETTY_FUNCTION__
             <<" index out of bounds: "<< pos << " >= " << length <<" ";
        abort();
}


inline void interval_set::add(const interval_set &a)
{
        for(int i=0;i<a.length;i++)
                add(a.data[i]);
}

inline interval interval_set::removeFirst ()
{
        return remove(0);
}
inline void interval_set::trimToSize(){
        maxlength=length;
        interval *data2=new interval[maxlength];
        for (int i=0;i<maxlength;i++)
                data2[i]=data[i];
        data=data2;
}

inline int interval_set::find(const interval &a)
{
        for(int i=0;i<length;i++){
                if(data[i]==a)
                        return i;
        }
        return -1;
}
inline bool interval_set::contains(const interval &a) const{
        for (int i=0;i<length;i++)
                if (data[i].contains(a)) return true;
        return false;
}

inline bool interval_set::contains(double a) const{
        for (int i=0;i<length;i++)
                if (data[i].contains(a)) return true;
        return false;
}
inline void interval_set::conc(const interval &a){
        for (int i=0;i<length;i++){
                if (a.sup()<data[i].inf() || data[i].sup()<a.inf())
                        remove(i--);
                else
                        data[i]=interval(std::max(a.inf(),data[i].inf()),
                                         std::min(a.sup(),data[i].sup()));
        }
}
inline unsigned int interval_set::num_of_gaps() const {
  return length > 0 ? length-1 : 0;
}
//OPERATORS
inline interval_set operator +(const interval_set &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                for(int j=0;j<b.getLength();j++)
                        c.add(a[i]+b[j]);
        return c;
}
inline interval_set operator +(const interval_set &a,const interval &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(a[i]+b);
        return c;
}
inline interval_set operator +(const interval &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(a+b[i]);
        return c;
}
inline interval_set operator +(const interval_set &a,double b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(a[i]+b);
        return c;
}
inline interval_set operator +(double a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(a+b[i]);
        return c;
}

inline interval_set operator -(const interval_set &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                for(int j=0;j<b.getLength();j++)
                        c.add(a[i]-b[j]);
        return c;
}
inline interval_set operator -(const interval_set &a,const interval &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(a[i]-b);
        return c;
}
inline interval_set operator -(const interval &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(a-b[i]);
        return c;
}
inline interval_set operator -(const interval_set &a,double b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(a[i]-b);
        return c;
}
inline interval_set operator -(double a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(a-b[i]);
        return c;
}
inline interval_set operator -(const interval_set &a)
{
        interval_set c=-1*a;
        return c;
}

inline interval_set operator *(const interval_set &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                for(int j=0;j<b.getLength();j++)
                        c.add(a[i]*b[j]);
        return c;
}
inline interval_set operator *(const interval_set &a,const interval &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(a[i]*b);
        return c;
}
inline interval_set operator *(const interval &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(a*b[i]);
        return c;
}
inline interval_set operator *(const interval_set &a,double b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(a[i]*b);
        return c;
}
inline interval_set operator *(double a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(a*b[i]);
        return c;
}


inline interval_set divide(const interval &a,double b)
{
        return divide(a,interval(b,b));
}
inline interval_set divide(double a,const interval &b)
{
        return divide(interval(a,a),b);
}

inline interval_set operator /(const interval_set &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                for(int j=0;j<b.getLength();j++)
                        c.add(divide(a[i],b[j]));
        return c;
}
inline interval_set operator /(const interval_set &a,const interval &b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(divide(a[i],b));
        return c;
}
inline interval_set operator /(const interval &a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(divide(a,b[i]));
        return c;
}
inline interval_set operator /(const interval_set &a,double b)
{
        interval_set c;
        for(int i=0;i<a.getLength();i++)
                c.add(divide(a[i],b));
        return c;
}
inline interval_set operator /(double a,const interval_set &b)
{
        interval_set c;
        for(int i=0;i<b.getLength();i++)
                c.add(divide(a,b[i]));
        return c;
}

} // end of namespace coco

namespace std {
//OUTPUT
ostream& operator<< (ostream &s, const coco::interval_set &a);

} // end of namespace std

#endif //__INTERVAL_SET_H__

---