/*******************************************************************************
+
+  LEDA 3.5
+
+  rat_vector.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef LEDA_RAT_VECTOR_H
#define LEDA_RAT_VECTOR_H 


#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350114
#include <LEDA/REDEFINE_NAMES.h>
#endif


#include <LEDA/array.h>
#include <LEDA/integer.h>
#include <LEDA/rational.h>
#include <LEDA/integer_vector.h>
#include <LEDA/geo_rep.h> 
#include <LEDA/vector.h> 

/*{\Manpage {rat_vector} {} {Rational Vectors} {v}}*/

class rat_vector:public handle_base{

/*{\Mdefinition

An instance of data type |rat_vector| is a vector of rational
numbers. A $d$-dimensional vector $r = (r_0,\ldots,r_{d-1})$ is
represented in homogeneous coordinates $(h_0,\ldots,h_d)$, where $r_i
= h_i/h_d$ and the $h_i$'s are of type |integer|. We call the $r_i$'s
the cartesian coordinates of the vector. The homogenizing coordinate
$h_d$ is positive.

This data type is meant for use in computational geometry. It realizes
free vectors as opposed to position vectors (type |rat_point|). The
main difference between position vectors and free vectors is their
behavior under affine transformations, e.g., free vectors are
invariant under translations.

|rat_vector| is an item type.}*/

geo_rep*ptr()const{return(geo_rep*)PTR;}

rat_vector(const handle_base&p):handle_base(p){}

friend class rat_point;

void print(ostream&)const;
void read(istream&);

public:

/*{\Mcreation 6}*/

rat_vector(int d=2);
/*{\Mcreate introduces a variable |\Mvar| of type |rat_vector| initialized
            to the zero vector of dimension $d$.}*/

rat_vector(integer a,integer b,integer D);
/*{\Mcreate introduces a variable  |\Mvar| of type |rat_vector|
            initialized to the two-dimensional vector with homogeneous
            representation $(a,b,D)$ if $D$ is positive and representation
            $(-a,-b,-D)$ if $D$ is negative.\\
            \precond $D$ is non-zero.}*/

rat_vector(integer a,integer b,integer c,integer D);
/*{\Mcreate introduces a variable  |\Mvar| of type |rat_vector|
            initialized to the two-dimensional vector with homogeneous
            representation $(a,b,c,D)$ if $D$ is positive and representation
            $(-a,-b,-c,-D)$ if $D$ is negative.\\
            \precond $D$ is non-zero.}*/


rat_vector(integer a,integer b) { PTR= new geo_rep(a,b,1); }
/*{\Mcreate introduces a variable  |\Mvar| of type |rat_vector|
            initialized to the two-dimensional vector with homogeneous
            representation $(a,b,1)$.}*/

rat_vector(const integer_vector&c,integer D);
/*{\Mcreate introduces a variable |\Mvar| of type |rat_vector|
            initialized to the vector with homogeneous
            coordinates $(\pm c_0,\ldots,\pm c_{d-1},\pm D)$,
            where $d$ is the dimension of $c$ and the sign
            chosen is the sign of $D$.\\
            \precond $D$ is non-zero.}*/

rat_vector(const integer_vector&c);
/*{\Mcreate introduces a variable |\Mvar| of type |rat_vector|
            initialized to the direction with homogeneous coordinate
            vector $\pm c$, where the sign chosen is the sign of the
            last component of $c$. \\
            \precond The last component of $c$ is non-zero.}*/


 rat_vector(const rat_vector&p):handle_base(p){}
~rat_vector(){}

rat_vector&operator= (const rat_vector&p)
{handle_base::operator= (p);return*this;}


/*{\Moperations 3 4.5}*/
/*{\Mtext \headerline{3.1 Initialization, Access and Conversions}}*/

static rat_vector d2(integer a,integer b, integer D);
/*{\Mstatic returns a |rat_vector| of dimension $2$ initialized to a
            vector with homogeneous representation $(a,b,D)$ if $D$
            is positive and representation $(-a,-b,-D)$ if $D$ is
            negative.\\
            \precond $D$ is non-zero.}*/

static rat_vector d3(integer a,integer b,integer c, integer D);
/*{\Mstatic returns a |rat_vector| of dimension $3$ initialized to a
            vector with homogeneous representation $(a,b,c,D)$ if $D$
            is positive and representation $(-a,-b,-c,-D)$ if $D$ is
            negative.\\
            \precond $D$ is non-zero.}*/

static rat_vector unit(int i,int d=2);
/*{\Mstatic  returns a |rat_vector| of dimension $d$ initialized
            to the $i$-th unit vector.\\
            \precond $0 \le i < d$.}*/

static rat_vector zero(int d=2);
/*{\Mstatic  returns the zero vector in d-dimensional space.}*/

int dim() const { return ptr()->dim; }
/*{\Mop     returns the dimension of |\Mvar|.}*/

integer   hcoord(int i) const { return ptr()->v[i];}
/*{\Mop     returns the $i$-th homogeneous coordinate of |\Mvar|.}*/

rational  coord(int i) const  { return rational(hcoord(i),hcoord(dim())); }
/*{\Mop     returns the $i$-th cartesian coordinate of |\Mvar|.}*/

rational  operator[](int i) const { return coord(i); }
/*{\Marrop  returns the $i$-th cartesian coordinate of |\Mvar|.}*/


rational  sqr_length() const;
/*{\Mop     returns the square of the length of |\Mvar|. }*/

vector    to_vector() const;
/*{\Mop     returns a floating point approximation of |\Mvar|. }*/


/*{\Mtext \headerline{Additional Operations for vectors in
two-dimensional space}}*/

rational xcoord()const {return coord(0);}
/*{\Mop     returns the zero-th cartesian coordinate of |\Mvar|.}*/

rational ycoord()const {return coord(1);}
/*{\Mop     returns the first cartesian coordinate of |\Mvar|.}*/

integer X() const {return hcoord(0);}
/*{\Mop     returns the zero-th homogeneous coordinate of |\Mvar|.}*/

integer Y() const {return hcoord(1);}
/*{\Mop     returns the first homogeneous coordinate of |\Mvar|.}*/

integer W() const {return hcoord(ptr()->dim);}
/*{\Mop     returns the homogenizing coordinate of |\Mvar|.}*/

rat_vector rotate90() const;
/*{\Mop     returns the |\Mvar| rotated by 90 degrees.\\
	    \precond |\Mvar.dim() = 2|.}*/


/*{\Mtext \headerline{3.2 Tests}}*/

int cmp(const rat_vector&x,const rat_vector&y)const
{return(identical(x,y)?0:
x.ptr()->cmp_rat_coords(x.ptr(),y.ptr()));}

friend int compare(const rat_vector&p,const rat_vector&q)
{return p.cmp(p,q);}

bool operator==(const rat_vector&w)const
{return cmp(*this,w)==0;}
/*{\Mbinop     Test for equality.}*/

bool operator!=(const rat_vector&w)const
{return cmp(*this,w)!=0;}
/*{\Mbinop     Test for inequality.}*/

/*{\Mtext \headerline{3.3 Arithmetical Operators}}*/

rat_vector scale(integer m,integer n)const;
void  self_scale(integer m,integer n);

friend rat_vector operator*(int n,const rat_vector&v);

friend rat_vector operator*(integer n,const rat_vector&v);
/*{\Mbinopfunc   multiplies all cartesian coordinates by |n|.   }*/

friend rat_vector operator*(rational r,const rat_vector&v);
/*{\Mbinopfunc    multiplies all cartesian coordinates by |r|.   }*/

rat_vector& operator*= (integer n);
/*{\Mbinop  multiplies all cartesian coordinates by |n|.   }*/
rat_vector& operator*= (int n);

rat_vector& operator*= (rational r);
/*{\Mbinop  multiplies all cartesian coordinates by |r|.   }*/

friend rat_vector operator/(const rat_vector&v,int n);

friend rat_vector operator/(const rat_vector&v,integer n);
/*{\Mbinopfunc    divides all cartesian coordinates by $n$.}*/

friend rat_vector operator/(const rat_vector&v,rational r);
/*{\Mbinopfunc    divides all cartesian coordinates by $r$.}*/

rat_vector&operator/= (integer n);
/*{\Mbinop  divides all cartesian coordinates by |n|.   }*/
rat_vector&operator/= (int n);

rat_vector&operator/= (rational r);
/*{\Mbinop  divides all cartesian coordinates by |r|.   }*/

friend rational operator*(const rat_vector v,const rat_vector&w);
/*{\Mbinopfunc  scalar product, i.e., $\sum_{0 \le i < d} v_i w_i$,
                where $v_i$ and $w_i$ are the cartesian coordinates
                of $v$ and $w$ respectively. }*/

friend rat_vector operator+(const rat_vector&v,const rat_vector&w);
/*{\Mbinopfunc   adds cartesian coordinates.   }*/

rat_vector& operator+= (const rat_vector&w);
/*{\Mbinop       addition plus assignment.   }*/

friend rat_vector operator-(const rat_vector&v,const rat_vector&w);
/*{\Mbinopfunc    subtracts cartesian coordinates. }*/

rat_vector& operator-= (const rat_vector&w);
/*{\Mbinop       subtraction plus assignment. }*/

rat_vector operator-() const;
/*{\Munop    returns -|\Mvar|.}*/


/*{\Mtext \headerline{3.4 Input and Output}}*/

friend ostream&operator<<(ostream&O,const rat_vector&v)
{v.print(O);return O;}
/*{\Mbinopfunc  writes $v$'s homogeneous coordinates
                component\-wise to the output stream $O$.}*/

friend istream&operator>>(istream&I,rat_vector&v)
{v.read(I);return I;}
/*{\Mbinopfunc  reads $v$'s homogeneous coordinates
                componentwise from the input stream $I$.
                The operator uses the current dimension of |v|.}*/


};



/*{\Mtext \headerline{3.5 Linear Hull, Dependence and Rank}}*/

bool contained_in_linear_hull(const array<rat_vector>&A,
const rat_vector&x);
/*{\Mfuncl determines whether $x$ is contained in the linear hull
           of the vectors in $A$.}*/

int linear_rank(const array<rat_vector>&A);
/*{\Mfuncl computes the linear rank of the vectors in $A$.}*/

bool linearly_independent(const array<rat_vector>&A);
/*{\Mfuncl decides whether the vectors in $A$ are linearly independent.}*/

array<rat_vector> linear_base(const array<rat_vector>&A);
/*{\Mfuncl computes a basis of the linear space spanned by the vectors
           in $A$.}*/


/*{\Mimplementation
Vectors are implemented by arrays of integers as an item type.  All
operations like creation, initialization, tests, vector arithmetic,
input and output on an vector $v$ take time $O(|v.dim()|)$. |dim()|,
coordinate access and conversions take constant time.  The operations
for linear hull, rank and independence have the cubic costs of the
used matrix operations.  The space requirement is $O(|v.dim()|)$.  }*/


#if LEDA_ROOT_INCL_ID == 350114
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif



