Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

SparseVec.h

Go to the documentation of this file.
00001 /*
00002     File:           SparseVec.h
00003 
00004     Function:       Defines a sparse vector.
00005                     
00006     Author(s):      Andrew Willmott
00007 
00008     Copyright:      (c) 1995-2000, Andrew Willmott
00009  */
00010 
00011 #ifndef __SparseVec__
00012 #define __SparseVec__
00013 
00014 #include "vl/VL.h"
00015 #include "vl/Vec.h"
00016 #include "vl/SubSVec.h"
00017 #include "cl/Array.h"
00018 #include <iostream.h>
00019 
00020 #define TSVList Array< TSparsePair >
00021 
00022 class TSparsePair
00023 {   
00024 public:
00025     
00026     TSparsePair() {};
00027     TSparsePair(Int i, TVReal elt) : index(i), elt(elt) {};
00028     
00029     Int     index;      // Index
00030     TVReal  elt;        // Non-zero element at that index
00031     
00032     Bool operator == (const TSparsePair &sp) const
00033     {   return(index == sp.index && elt == sp.elt); };
00034     Bool operator != (const TSparsePair &sp) const
00035     {   return(index != sp.index || elt != sp.elt); };
00036     
00037     friend ostream &operator << (ostream &s, const TSparsePair &sp);
00038     friend istream &operator >> (istream &s, TSparsePair &sp);
00039 };
00040 
00041 class TSubSVec;
00042 class TSVIter;
00043 
00044 class TSparseVec : public TSVList
00045 /*
00046     Function:   Provides a sparse vector class
00047 
00048     NOTE: SparseVecs can be manipulated as follows:
00049     
00050     1] Use SetElts() -- e.g., 
00051         sv.SetSize(5); sv.SetElts(1, 1.0, 4, 4.0, VL_SV_END);
00052         Sets sv to [0.0, 1.0, 0.0, 0.0 4.0]
00053     
00054     2] Use the SVIter iterator. (See description below.)
00055             
00056     3] Use the Overlay method: a.Overlay(b) performs a[i] = b[i] for all non-zero b[i].
00057 
00058     4] Direct access:
00059         SetNumElts(size), Begin(), AddElt()/AddNZElt() new element pairs in
00060         order, then End(). (Use AddNZElt if you know the element will 
00061         be non-zero.)
00062     
00063     5] As a last resort, use Get()/Set(). 
00064         These calls are not efficient for multiple accesses. 
00065 */
00066 {
00067 public:         
00068     TSparseVec();                       // Null vector: space allocated later
00069     TSparseVec(Int n);                                      
00070     TSparseVec(Int n, Int indices[], TVReal elts[]);    
00071     TSparseVec(Int n, Int idx0, double elt0, ...);              
00072     TSparseVec(const TSparseVec &v);    // Copy constructor
00073     TSparseVec(const TSubSVec &v);              
00074     TSparseVec(const TVec &v);              
00075     TSparseVec(Int n, ZeroOrOne);       // Zero or all-ones vector  
00076     TSparseVec(Int n, Axis a);          // Unit vector
00077     
00078    ~TSparseVec();                       // Destructor
00079 
00080     // Accessor functions
00081         
00082     Int         Elts() const { return elts; };
00083 
00084     TSparseVec  &operator =  (const TSparseVec &v);
00085     TSparseVec  &operator =  (ZeroOrOne k) { MakeBlock(k); return(SELF); };                     
00086     TSparseVec  &operator =  (Axis k) { MakeUnit(k); return(SELF); };                       
00087     TSparseVec  &operator =  (const TSubSVec &v);
00088     TSparseVec  &operator =  (const TVec &v);
00089     
00090     Void        SetSize(Int n);
00091 
00092     //  Sparse methods
00093     
00094     TSparseVec  Overlay(const TSparseVec &a) const;
00095     Void        SetElts(Int idx0, double elt0, ...);
00096     Void        Set(Int index, TVReal elt);
00097     TVReal      Get(Int index) const;
00098     
00099     //  Vector initialisers
00100     
00101     Void        MakeZero();
00102     Void        MakeUnit(Int i, TVReal k = vl_one);
00103     Void        MakeBlock(TVReal k = vl_one);
00104 
00105     //  Low level Utils
00106 
00107     Void        SetNumElts(Int n)
00108                 { elts = n; };
00109     Void        Begin()
00110                 { Clear(); };
00111     Void        AddElt(Int i, TVReal a)
00112                 { if (len(a) > fuzz) {Add(); Last().index = i; Last().elt = a;} };
00113     Void        AddNZElt(Int i, TVReal a)
00114                 { Add(); Last().index = i; Last().elt = a; };
00115     Void        AddNZElt(const TSparsePair &p)
00116                 { Append(p); };
00117     Void        End()
00118                 { Add(); Last().index = VL_SV_MAX_INDEX; };
00119 
00120     //  Settings
00121 
00122     static Void SetCompactPrint(Bool on);
00123     static Bool IsCompact() { return compactPrint; };
00124     static Void SetFuzz(TVReal fuzz);
00125     static Bool IsNonZero(TVReal a)
00126                 { return(len(a) > fuzz); };
00127 
00128 protected: 
00129     // Private...
00130     static Bool     compactPrint;   //   Print in normal or compact (only non-zero elts) style
00131     static TVReal   fuzz;           //   x s.t. |x| <= fuzz is considered zero.
00132     Int             elts;
00133 };
00134     
00135 class TSVIter
00136 /*
00137     Function:   Useful for iterating over a sparse vector.
00138     
00139     Data() :    returns the current element's data
00140     Index() :   returns the current element's index
00141 
00142     1] Use Begin(), Inc(), AtEnd() to iterate over the non-zero elements 
00143         of the vector:
00144         
00145         // sv = sv * 2
00146         for (j.Begin(sv); !j.AtEnd(); j.Inc())
00147             j.Data() *= 2.0;        
00148 
00149     2]  Use one of the following:
00150 
00151         Inc(Int i)    moves on to elt i, where i will increase by 1 on each call
00152         IncTo(Int i)  moves on to elt i, where i will increase monotonically
00153 
00154         within another for-loop to access the elements of the sparse vector
00155         corresponding to i. For example:
00156 
00157         // v = v + sv
00158         for (j.Begin(sv), i = 0; i < v.NumItems(); i++)
00159         {
00160             j.Inc(i);
00161             if (j.Exists())
00162                 v[i] += j.Data();
00163         }
00164 
00165         // a += dot(sv1, sv2)
00166         for (j.Begin(sv2), k.Begin(sv1); !k.AtEnd(); k.Inc())
00167         {
00168             j.IncTo(k.Index());     // find corresponding elt in sv2
00169             if (j.Exists())
00170                 a += j.Data() * k.Data();
00171         }
00172 */
00173 {
00174 public:
00175     TSVIter() {};
00176     TSVIter(const TSparseVec &sv) : pairIdx(0), list(&sv) {};
00177 
00178     Void    Begin()
00179             { pairIdx = 0; };
00180             // move to the beginning of the current sparse vector
00181             
00182     Void    Begin(const TSparseVec &sv)
00183             { pairIdx = 0; list = &sv; };
00184             // move to the beginning of sparse vector sv
00185 
00186     Void    Inc()
00187             { pairIdx++; };
00188             // move to the next non-zero element in the vector
00189             
00190     Bool    AtEnd()
00191             { return(pairIdx >= list->NumItems() - 1); };
00192             // returns true if we're at the end of the vector
00193 
00194     TVReal  Data()
00195             { return(list->Item(pairIdx).elt); };
00196             // WARNING: only call this if you *know* the element is non-zero
00197     Int     Index()
00198             { return(list->Item(pairIdx).index); };
00199     TSparsePair Pair()
00200             { return(list->Item(pairIdx)); };
00201 
00202     Void    Inc(Int i)
00203             { if (i > list->Item(pairIdx).index) pairIdx++; };
00204             // Move on to the element indicated by i. i must increase by
00205             // 1 on each subsequent call.
00206 
00207     Bool    IncTo(Int i)
00208             { OrdFindBinary(i); return(i == list->Item(pairIdx).index); };
00209             // Move on to the element with index i.
00210             // returns true if element i is non-zero.
00211     
00212     Bool    Exists(Int i)
00213             { return(i == list->Item(pairIdx).index); };
00214 
00215     Int     PairIdx()
00216             { return(pairIdx); };
00217             
00218     Void OrdFindBinary(Int i);  // Find the pair with index i using binary search
00219     Void OrdFindLinear(Int i);  // Find the pair with index i using linear search
00220 
00221 protected:
00222     Int             pairIdx;    // current index into sparse list
00223     const TSVList   *list;      // sparse list
00224 };
00225 
00226 
00227 // --- Vec In-Place operators -------------------------------------------------
00228 
00229 TSparseVec      &operator += (TSparseVec &a, const TSparseVec &b);
00230 TSparseVec      &operator -= (TSparseVec &a, const TSparseVec &b);
00231 TSparseVec      &operator *= (TSparseVec &a, const TSparseVec &b);
00232 TSparseVec      &operator *= (TSparseVec &v, TVReal s);
00233 TSparseVec      &operator /= (TSparseVec &a, const TSparseVec &b);
00234 TSparseVec      &operator /= (TSparseVec &v, TVReal s);
00235 
00236 // --- Vec Comparison Operators -----------------------------------------------
00237 
00238 Bool            operator == (const TSparseVec &a, const TSparseVec &b);
00239 Bool            operator != (const TSparseVec &a, const TSparseVec &b);
00240 
00241 // --- Vec Arithmetic Operators -----------------------------------------------
00242 
00243 TSparseVec      operator + (const TSparseVec &a, const TSparseVec &b);
00244 TSparseVec      operator - (const TSparseVec &a, const TSparseVec &b);
00245 TSparseVec      operator - (const TSparseVec &v);
00246 TSparseVec      operator * (const TSparseVec &a, const TSparseVec &b);      
00247 TSparseVec      operator * (const TSparseVec &v, TVReal s);
00248 TSparseVec      operator / (const TSparseVec &a, const TSparseVec &b);
00249 TSparseVec      operator / (const TSparseVec &v, TVReal s);
00250 TSparseVec      operator * (TVReal s, const TSparseVec &v);
00251 
00252 
00253 TVReal          dot(const TSparseVec &a, const TSparseVec &b);
00254 TVReal          dot(const TSparseVec &a, const TVec &b);
00255 TVReal          len(const TSparseVec &v);
00256 TVReal          sqrlen(const TSparseVec &v);
00257 TSparseVec      norm(const TSparseVec &v);
00258 
00259 // --- Vec Input & Output -----------------------------------------------------
00260 
00261 ostream         &operator << (ostream &s, const TSparseVec &v);
00262 istream         &operator >> (istream &s, TSparseVec &v);
00263 
00264 
00265 #endif

Generated at Sat Aug 5 00:16:48 2000 for Class Library by doxygen 1.1.0 written by Dimitri van Heesch, © 1997-2000