// file: kpoint1d.h
// update: 10/18/02
#ifndef _KPOINT1D_H
#define _KPOINT1D_H
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <bigrational.h>
#include <root1.h>
#include <kratpoly.h>
using namespace std;
class K_POINT1D
{
friend class K_POINT2D;
mutable unsigned int type; // type == 1 if ROOT1
// 2 if bigrational
mutable ROOT1* PtR; // the interval for *this, 0 if type == 2
mutable bigrational PtB; // the point for *this, undefined if type == 1
K_RATPOLY* poly; // a polynomial that vanished at *this
unsigned long ref_count; // reference counter
// stream
ostream& output(ostream&) const;
// primitive
// int cut(const bigrational& b) const
// cut *this at the point b, i.e.,
// refine the interval for *this
// by setting get_low() or get_high() to be b.
int cut(const bigrational&) const;
// int halve() const
// cut *this at the point half that halves the interval for *this, i.e.,
// refine the interval for *this
// by setting get_low() or get_high() to be half.
int halve() const;
// int reduce(const unsigned long num_bits) const
// reduce *this s.t.
// [get_low(), get_high()] will contain all the numbers
// approximated by float_est to num_bits precision.
// return 1 if some reduction occurs and
// 0 otherwise.
int reduce(const unsigned long) const;
// int contract(const bigrational& tol) const
// contract *this s.t. [get_low(), get_high()] will be no larger than tol.
int contract(const bigrational&) const;
// int shrink(const bigrational& fac) const
// shrink *this s.t. [get_low(), get_high()] will become smaller by fac.
// e.g. fac == 1/10 => [get_low(), get_high()] becomes 1/10.
int shrink(const bigrational&) const;
// int K_POINT1D :: separate(const K_POINT1D& x) const
// separate *this and x s.t. they will not overlap.
// POSSIBLY DOES NOT TERMINATE.
int separate(const K_POINT1D&) const;
// arithmetic
// K_POINT1D add(const K_POINT1D& x) const
// return *this + x
K_POINT1D add(const K_POINT1D&) const;
// K_POINT1D sub(const K_POINT1D& x) const
// return *this - x
K_POINT1D sub(const K_POINT1D&) const;
// K_POINT1D mul(const K_POINT1D& x) const
// return *this * x
K_POINT1D mul(const K_POINT1D&) const;
// K_POINT1D div(const K_POINT1D& x) const
// return *this / x
K_POINT1D div(const K_POINT1D&) const;
public:
// constructors, assignment and destructor
// K_POINT1D()
// constructs a type 0 instance.
K_POINT1D();
// K_POINT1D(const ROOT1& r)
// construct a type1 instance from ROOT1 r.
// r.num_root must have been 1.
K_POINT1D(const ROOT1&);
// K_POINT1D(const ROOT1& r)
// construct a type1 instance from ROOT1 r of a root of K_RATPOLY P.
// r.num_roots must have been 1.
K_POINT1D(const ROOT1&, const K_RATPOLY&);
// K_POINT1D(const bigrational& b)
// construct a type2 instance from bigrational b.
K_POINT1D(const bigrational&);
// K_POINT1D(const bigrational& b, const K_RATPOLY& P)
// construct a type2 instance from bigrational b and K_RATPOLY P.
// P must vanish at b.
K_POINT1D(const bigrational&, const K_RATPOLY&);
K_POINT1D(const K_POINT1D&);
K_POINT1D& operator =(const K_POINT1D&);
~K_POINT1D();
// stream
friend ostream& operator <<(ostream&, const K_POINT1D&);
// primitive
bigrational get_low() const;
bigrational get_high() const;
// arithmetic
friend K_POINT1D operator +(const K_POINT1D&, const K_POINT1D&);
friend K_POINT1D operator -(const K_POINT1D&, const K_POINT1D&);
friend K_POINT1D operator *(const K_POINT1D&, const K_POINT1D&);
friend K_POINT1D operator /(const K_POINT1D&, const K_POINT1D&);
// comparison
// int compare(const K_POINT1D& x) const
// return 1 if *this > x,
// 0 if *this == x, and
// - 1 if *this < x.
int compare(const K_POINT1D&) const;
// int compare(const bigrational& b) const
// return 1 if *this > b,
// 0 if *this == b, and
// - 1 if *this < b.
int compare(const bigrational&) const;
// int sort(K_POINT1D** const X, const unsigned long n)
// perform insertion sort on the array X of length n.
// return 1 if elements are distinct and
// 0 otherwise.
friend int sort(K_POINT1D** const, const unsigned long);
// int overlap(const K_POINT1D& x) const
// return 1 if *this and x overlap, and
// 0 otherwise.
int overlap(const K_POINT1D&) const;
// get_pts(): get algebraic points
// unsigned long get_pts(const bigrational& l, const bigrational& h,
// const K_RATPOLY& P,
// K_POINT1D**& pts,
// const bigrational& tol, const int count_endpts)
// computes the roots "pts" of a univariate polynomial P
// on/in the interval [l, h].
// returns the number of roots.
// if tol > 0 then an interval for each root is no larger than tol.
// if tol = 0 then there is no limit on the size of intervals for roots.
// if count_endpts = 1 then
// the roots at the endpoints of the interval [l, h] are counted.
// if count_endpts = 0 then
// the roots on the endpoints of the interval [l, h] are ignored.
friend unsigned long get_pts(const bigrational&, const bigrational&,
const K_RATPOLY&,
K_POINT1D**&,
const bigrational&, const int);
// unsigned long get_all_pts(const K_RATPOLY& P,
// K_POINT1D**& pts,
// const bigrational& tol)
// computes all the intersections "pts" of a univariate polynomials P.
// returns the number of roots.
// if tol > 0 then an interval for each root is no larger than tol.
// if tol = 0 then there is no limit on the size of intervals for roots.
friend unsigned long get_all_pts(const K_RATPOLY&,
K_POINT1D**&,
const bigrational);
// other
friend unsigned long match_intervals(const bigrational* const,
const bigrational* const,
const unsigned long,
K_POINT1D** const,
long*&,
const unsigned long);
friend unsigned long get_pts_interior(const bigrational&, const bigrational&,
const bigrational&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&);
friend int refine_interior(K_POINT1D* const, K_POINT1D* const,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D*&,
const bigrational&);
};
#endif