SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Polynomial/internal/Isolating_interval.h

Go to the documentation of this file.

// Copyright (c) 2005  Stanford University (USA).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Kinetic_data_structures/include/CGAL/Polynomial/internal/Isolating_interval.h $
// $Id: Isolating_interval.h 40832 2007-11-08 00:27:20Z ameyer $
// 
//
// Author(s)     : Daniel Russel <drussel@alumni.princeton.edu>

#ifndef CGAL_POLYNOMIAL_INTERNAL_ISOLATING_INTERVAL_H
#define CGAL_POLYNOMIAL_INTERNAL_ISOLATING_INTERVAL_H
#include <CGAL/Polynomial/basic.h>
#include <CGAL/Polynomial/internal/interval_arithmetic.h>
#include <iostream>

CGAL_POLYNOMIAL_BEGIN_INTERNAL_NAMESPACE

template <class NT, class Functor>
typename Functor::result_type apply(const Functor &f,  const NT &a)
{
  return f(a);
}


template <class NT, class Functor>
typename Functor::result_type apply(const Functor &f,  const NT &a,
                                    const NT &b)
{
  return f( a, b);
}


template <class NT, class Functor, class Data>
typename Functor::result_type apply(const Functor &f,  const NT &a,
                                    const NT &b, const Data &da, const Data &db)
{
  return f( a, b, da, db);
}



template <class FT_t>
class Isolating_interval
{
  typedef Isolating_interval<FT_t> This;
public:
  typedef FT_t NT;
  Isolating_interval(): b_(1, -1){}
  Isolating_interval(const NT &lbi): b_(lbi, lbi) {
  }
  Isolating_interval(const NT &lbi, const NT &ubi): b_(lbi, ubi) {
    if(0) print();                        // make sure it is instantiated
    if (lb() > ub()) {
      std::cerr << "b_.first=" << lb() << " and b_.second=" << ub() << std::endl;
    }
    CGAL_Polynomial_assertion(lb() <= ub());
  }

  typedef enum Endpoint {UPPER, LOWER}
    Endpoint;

  template <class Function>
  typename Function::result_type apply_to_endpoint(const Function &f, Endpoint b) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    if (b==UPPER) {
      return apply(f,ub());
    }
    else {
      return apply(f, lb());
    }
  }

  template <class Function>
  typename Function::result_type apply_to_midpoint(const Function &f) {
    CGAL_Polynomial_assertion(lb() <= ub());
    return apply(f,middle());
  }

  template <class Function>
  typename Function::result_type apply_to_interval(const Function &f) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return apply(f, lb(), ub());
  }

  template <class Function, class Data>
  typename Function::result_type apply_to_interval(const Function &f,
                                                   const Data &d0, const Data &d1) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return apply(f, lb(), ub(), d0, d1);
  }

  This upper_endpoint_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(ub());
  }

  This lower_endpoint_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(lb());
  }

  This endpoint_interval(Endpoint b) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    if (b==UPPER) {
      return This(ub());
    }
    else {
      return This(lb());
    }
  }

  This midpoint_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(middle());
  }

  This first_half() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(lb(), middle());
  }
  This second_half() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(middle(), ub());
  }

  std::pair<This,This> split() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    NT mid = middle();
    return std::pair<This,This>(This(lb(), mid), This(mid, ub()));
  }

  This middle_half() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    NT mid = middle();
    NT mid_left = midpoint(lb(), middle());
    NT mid_right = midpoint(middle(), ub());

    return This(mid_left, mid_right);
  }

  std::pair<This,This> split_at(const NT& x) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_precondition( !is_singular() &&
                       lower_bound() < x && x < upper_bound() );
    return std::pair<This,This>( This(lower_bound(), x),
                                 This(x, upper_bound()) );
  }

  This split_at_first_half(const NT& x) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_precondition( !is_singular() &&
                       lower_bound() < x && x < upper_bound() );
    return This(lower_bound(), x);
  }
  This split_at_second_half(const NT& x) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_precondition( !is_singular() &&
                       lower_bound() < x && x < upper_bound() );
    return This(x, upper_bound());
  }

  This interval_around_endpoint(Endpoint b) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    NT mid = middle();

    if ( b == LOWER ) {
      return This(lower_bound()-NT(1), mid);
    }                                     // end-if

    // b == UPPER
    return This(mid, upper_bound()+NT(1));
  }

  bool is_singular() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return lb()==ub();
  }

  const NT &to_nt() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_precondition(is_singular());
    return lb();
  }

  /*bool overlaps(const This &o) const {
    if (b_.first > o.b_.first && b_.first < o.b_.second) return true;
    else if (b_.second > o.b_.first && b_.first < o.b_.second) return true;
    else if (o.b_.second > b_.first && b_.first < b_.second) return true;
    else if (o.b_.first > b_.first && b_.first < b_.second) return true;
    else if (*this==o) return true;
    else return false;
    }*/

  Order order(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    if (*this < o) return STRICTLY_BELOW;
    else if (o < *this) return STRICTLY_ABOVE;
    else if (lb() <= o.lb() && ub() >= o.ub()) return CONTAINS;
    else if (o.lb() <= lb() && o.ub() >= ub()) return CONTAINED;
    else if (*this == o) return EQUAL;
    else if (lb() < o.lb()) return BELOW;
    else return ABOVE;
  }


  /*This chop(const This &o, Endpoint bd) const {
    if (bd== UPPER) {
    Polynomial_assertion(lb()== o.lb() && ub() > o.ub());
    return This(o.ub(), ub());
    } else {
    Polynomial_assertion(ub()== o.ub() && lb() < o.lb());
    return This(lb(),o.lb());
    }
    }*/

  int number_overlap_intervals(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    Order ord= order(o);
    switch(ord) {
    case CONTAINS:
      return 3;
    case CONTAINED:
      return 1;
    case BELOW:
    case ABOVE:
      return 2;
    case STRICTLY_ABOVE:
    case STRICTLY_BELOW:
      return 1;
    default:
      return -1;
    }
  }

  // If we have two partially overllaping intervals, then
  // *_overlap_interval  return the three possible intervals of *this:
  // the common interval and the non-common remainders of the two
  // intervals.
  This first_overlap_interval(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    Order ord= order(o);
    switch(ord) {
    case CONTAINS:
      return This(lb(), o.lb());
    case CONTAINED:
    case STRICTLY_ABOVE:
    case STRICTLY_BELOW:
      return *this;
    case BELOW:
      return This(lb(), o.lb());
    case ABOVE:
      return This(lb(), o.ub());
    default:
      return This();
    };
  }

  This second_overlap_interval(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    Order ord= order(o);
    switch(ord) {
    case CONTAINS:
      return This(o.lb(), o.ub());
    case BELOW:
      return This(o.lb(), ub());
    case ABOVE:
      return This(o.ub(), ub());
    default:
      return This();
    };
  }

  This third_overlap_interval(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    Order ord= order(o);
    switch(ord) {
    case CONTAINS:
      return This(o.ub(), ub());
    default:
      return This();
    };
  }

  /*std::pair<This, This> split_with(const This &o) const {
    bool I_would_like_to_get_rid_of_this;
    CGAL_precondition(0);
    Order ord= order(o);
    typedef std::pair<This, This> IP;
    switch(ord){
    case STRICTLY_BELOW:
    return IP(*this, endpoint_interval(UPPER));
    case STRICTLY_ABOVE:
    return IP(endpoint_interval(LOWER, *this));
    case BELOW:
    return IP(This(lb(), o.lb()), This(ub(), o.ub()));
    case CONTAINS:
    return IP(This(lb(), o.lb()), This();
    }
    }*/


  /*
    void subintervals(const This &o, This &a, This &b, This &c) const {
    bool I_would_like_to_get_rid_of_this;

    Order ord= order(o);
    switch (ord){
    case BELOW:
    a=This(lb(), o.lb());
    b=This(o.lb(), ub());
    c=This(ub(), o.ub());
    break;
    case CONTAINS:
    a=This(lb, o.lb());
    b=o;
    c=This(o.ub(), ub());
    break;
    case CONTAINED:
    a=This(o.lb, lb());
    b=*this;
    c=This(ub(), o.ub());
    break;
    case ABOVE:
    a=This(o.lb(), lb());
    b=This(lb(), o.ub());
    c=This(o.ub(), ub());
    break;
    case STRICTLY_BELOW:
    a=*this;
    b=This(ub(), o.lb());
    c=o;
    break;
    case STRICTLY_ABOVE:
    a=o;
    b=This(o.ub(), lb());
    c=*this;
    break;
    default:
    CGAL_error();
    }
    CGAL_postcondition(a.ub()==b.lb());
    CGAL_postcondition(b.ub()==c.lb());
    }*/

  
  bool operator<(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    if (ub() < o.lb()) return true;
    return (ub() == o.lb() && (!is_singular() || !o.is_singular()));
    /*
      if (ub() == o.lb() && (!is_singular() || !o.is_singular())) return true;
      else return false;
    */
  }
  bool operator>(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    return o < *this;
  }
  bool operator>=(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    return *this >0 || *this==o;
  }
  bool operator<=(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    return *this < 0 || *this==o;
  }
  bool operator==(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    return lb()==o.lb() && ub()==o.ub();
  }
  bool operator!=(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    CGAL_Polynomial_assertion(o.lb() <= o.ub());
    return lb()!=o.lb() || ub()!=o.ub();
  }

  double approximate_width() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return (std::max)(to_double(ub()) - to_double(lb()), 0.0);
  }

  double approximate_relative_width() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return approximate_width()/(std::max)(to_double(abs(ub())), to_double(abs(lb())));
  }

  bool contains(const This &o) {
    CGAL_Polynomial_assertion(lb() <= ub());
    return lb() <= o.lb() && ub() >= o.ub();
  }

  bool contains(const NT &o) {
    return lb() <= o && ub() >= o;
  }

  template <class OStream>
  void write(OStream &out) const
  {
    if (is_singular()) {
      out << lb();
    }
    else {
      out << "(" << lb() << "..." << ub() << ")";
    }
    if (0) print();
  }
  void print() const ;

  This operator-() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This(-ub(), -lb());
  }

  std::pair<double, double> double_interval() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    std::pair<double, double>
      lbi= CGAL_POLYNOMIAL_TO_INTERVAL(lb()),
      ubi= CGAL_POLYNOMIAL_TO_INTERVAL(ub());
    return std::pair<double, double>(lbi.first, ubi.second);
  }

  const NT& lower_bound() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    //    bool not_recommended;
    return lb();
  }
  const NT& upper_bound() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    //    bool not_recommended;
    return ub();
  }

  void set_upper(const NT& u) {
    CGAL_Polynomial_assertion(lb() <= ub());
    b_.second = u;
  }

  void set_lower(const NT& l) {
    CGAL_Polynomial_assertion(lb() <= ub());
    b_.first = l;
  }

  /*std::pair<NT, NT> () const {
    return std::pair<NT,NT>(b_.first, b_.second);
    }*/

  /*This operator||(const This &o){
    return This((std::min)(lb(), o.lb()), (std::max)(ub(), o.ub()));
    }*/

  This operator||(const This &o) const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return This((std::min)(lb(), o.lb()), (std::max)(ub(), o.ub()));
  }

  NT middle() const
  {
    CGAL_Polynomial_assertion(lb() <= ub());
    return NT(0.5)*(ub()+lb());
  }

  const std::pair<NT,NT>& to_pair() const {
    return b_;
  }

protected:
  std::pair<NT,NT> b_;

  NT midpoint(const NT& a, const NT& b) const
  {
    return NT(0.5)*(a+b);
  }

  const NT &lb() const
  {
    return b_.first;
  }
  const NT &ub() const
  {
    return b_.second;
  }

  /*static NT infinity() {
    if (std::numeric_limits<NT>::has_infinity){
    return std::numeric_limits<NT>::infinity();
    } else if (std::numeric_limits<NT>::is_bounded){
    return (std::numeric_limits<NT>::max)();
    } else {
    return NT(1000000000);
    }
    }*/
};

template <class NT>
void Isolating_interval<NT>::print() const
{
  write(std::cout);
  std::cout << std::endl;
}


template <class OStream, class NT>
OStream &operator<<(OStream &out, const Isolating_interval<NT> &ii)
{
  ii.write(out);
  return out;
}


/*template <class NT>
  std::pair<double, double> to_interval(const Isolating_interval<NT> &ii){
  return ii.to_interval();
  }*/

CGAL_POLYNOMIAL_END_INTERNAL_NAMESPACE

#ifdef CGAL_POLYNOMIAL_USE_CGAL

CGAL_BEGIN_NAMESPACE
template <class NT>
std::pair<double, double> to_interval(const typename CGAL_POLYNOMIAL_NS::internal::Isolating_interval<NT> &ii)
{
  return ii.double_interval();
}


CGAL_END_NAMESPACE
#endif
#endif