| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/TeSparseMatrix.h
Go to the documentation of this file.

    00001 // k9/a4/sparmat.h, templates for sparse matrices
    00002 #ifndef SPARSEMATRIX_H
    00003 #define SPARSEMATRIX_H SPARSEMATRIX_H
    00004
    00005 // selection of implementation
    00006 #ifdef STL_map            // defined in main()
    00007 #include<map>
    00008 #include<cassert>
    00009 #else
    00010 #include<hmap.h>
    00011
    00012 #include "TeDefines.h"
    00013
    00014 /* If at this point the HMap container is chosen, a function for
    00015    calculating the hash table addresses is needed. As opposed to the
    00016    hash functions described up to now, not only one value, but two are
    00017    used for the calculation. Therefore, the function operator of the
    00018    PairHashFun class takes a pair as argument. The address calculation
    00019    itself is simple, but sufficient for our purposes. */
    00020
    00021 using namespace std;
    00022
    00023 template<class IndexType>  // int, long or unsigned
    00024 class PairHashFun
    00025 {
    00026   public:
    00027     PairHashFun(long prime=65537) // another prime number is possible
    00028         // e.g. 2111 for smaller Matrizes
    00029     : tabSize(prime)
    00030     {}
    00031
    00032     // Address calculation with two values
    00033     long operator()(const pair<IndexType, IndexType>& p) const
    00034     {
    00035        return (p.first + p.second) % tabSize;
    00036     }
    00037
    00038     long tableSize() const
    00039     {
    00040        return tabSize;
    00041     }
    00042
    00043   private:
    00044     long tabSize;
    00045 };
    00046 #endif          //  STL_map
    00047
    00048 #ifdef _MSC_VER
    00049 #include <utility>
    00050 using namespace std;
    00051 #endif
    00052
    00053 template<class ValueType, class IndexType, class ContainerType>
    00054 class MatrixElement
    00055 {
    00056   private:
    00057     ContainerType& C;
    00058     typename ContainerType::iterator I;
    00059     IndexType row, column;
    00060
    00061   public:
    00062     typedef pair<IndexType, IndexType> IndexPair;
    00063     typedef MatrixElement<ValueType, IndexType,
    00064                           ContainerType>&  Reference;
    00065
    00066     MatrixElement(ContainerType& Cont, IndexType r, IndexType c)
    00067     : C(Cont), I(C.find(IndexPair(r,c))),
    00068       row(r), column(c)
    00069     {}
    00070
    00071     /* The constructor initializes the private variables with all
    00072        information that is needed. The container itself is located in
    00073        the sparseMatrix class; here, the reference to it is entered.
    00074        If the passed indices for row and column belong to an element
    00075        not yet stored in the container, the iterator has the value
    00076        C.end(). */
    00077
    00078     ValueType asValue() const
    00079     {
    00080        if(I == C.end())
    00081            return ValueType(0);
    00082        else
    00083            return (*I).second;
    00084     }
    00085
    00086     operator ValueType () const  // type conversion operator
    00087     {
    00088        return asValue();
    00089     }
    00090
    00091     /* According to the definition of the sparse matrix, 0 is returned
    00092        if the element is not present in the container. Otherwise, the
    00093        result is the second part of the object of type value_type
    00094        stored in the container. */
    00095
    00096     Reference operator=(const ValueType& x)
    00097     {
    00098        if(x != ValueType(0))        // not equal 0?
    00099        {
    00100          /* If the element does not yet exist, it is put, together
    00101             with the indices, into an object of type value_type and
    00102             inserted with insert(): */
    00103
    00104           if(I == C.end())
    00105           {
    00106              assert(C.size() < C.max_size());
    00107              I = (C.insert(
    00108 #ifndef _MSC_VER
    00109                                   typename
    00110 #endif
    00111                                   ContainerType::value_type(
    00112                         IndexPair(row,column), x))
    00113                  ).first;
    00114           }
    00115           else (*I).second = x;
    00116        }
    00117
    00118        /* insert() returns a pair whose first part is an iterator
    00119           pointing to the inserted object. The second part is of type
    00120           bool and indicates whether the insertion took place because
    00121           no element with this key existed. This is, however, not
    00122           evaluated here because, due to the precondition (I ==
    00123           C.end()), the second part must always have the value true.
    00124           If, instead, the element already exists, the value is
    00125           entered into the second part of the value_type object. If
    00126           the value is equal 0, in order to save space the element is
    00127           deleted if it existed. */
    00128
    00129        else                    // x = 0
    00130           if(I != C.end())
    00131           {
    00132               C.erase(I);
    00133               I = C.end();
    00134           }
    00135        return *this;
    00136     }
    00137
    00138     /* An assignment operator is required which in turn requires a
    00139        reference to an object of type MatrixElement. When both the
    00140        left- and right-hand side are identical, nothing has to happen.
    00141        Otherwise, as above, it has to be checked whether the value of
    00142        the right-hand element is 0 or not. The resulting behavior is
    00143        described together with the above assignment operator, so that
    00144        here it is simply called: */
    00145
    00146     Reference operator=(const Reference rhs)
    00147     {
    00148        if(this != &rhs)      // not identical?
    00149        {
    00150            return operator=(rhs.asValue());  // see above
    00151        }
    00152        return *this;
    00153     }
    00154
    00155 };  // class MatrixElement
    00156
    00157 template<class ValueType, class IndexType>
    00158 class TeSparseMatrix
    00159 {
    00160    public:
    00161      typedef pair<IndexType, IndexType> IndexPair;
    00162
    00163      // The switch STL_map controls the compilation:
    00164
    00165 #ifdef STL_map
    00166      typedef map<IndexPair, ValueType,
    00167                   less<IndexPair> >       ContainerType;
    00168 #else
    00169      typedef HMap<IndexPair, ValueType,
    00170                   PairHashFun<IndexType> > ContainerType;
    00171 #endif
    00172
    00173      typedef MatrixElement<ValueType, IndexType,
    00174                            ContainerType> MatrixElement;
    00175
    00176   public:
    00177     typedef IndexType size_type;
    00178
    00179     /* The constructor only initializes the row and column
    00180        information. The container is created by its standard
    00181        constructor, where in the case of hash implementation, the size
    00182        of the container is given by the hash function object of type
    00183        PairHashFun (see typedef above). */
    00184
    00185   private:
    00186     size_type rows, columns;
    00187     ContainerType C;
    00188
    00189   public:
    00190     sparseMatrix(size_type r, size_type c)
    00191     : rows(r), columns(c)
    00192     {}
    00193
    00194    size_type Rows()  const { return rows;}
    00195    size_type Columns() const { return columns;}
    00196
    00197    // usual container type definitions
    00198    typedef typename ContainerType::iterator iterator;
    00199    typedef typename ContainerType::const_iterator const_iterator;
    00200
    00201    // usual container functions
    00202    size_type size()       const { return C.size();}
    00203    size_type max_size()   const { return C.max_size();}
    00204
    00205    iterator begin()             { return C.begin();}
    00206    iterator end()               { return C.end();}
    00207
    00208    const_iterator begin() const { return C.begin();}
    00209    const_iterator end()   const { return C.end();}
    00210
    00211    void clear()
    00212    {
    00213        C.clear();
    00214
    00215    }
    00216
    00217    class Aux  // for index operator below
    00218    {
    00219      public:
    00220        Aux(size_type r, size_type maxs, ContainerType& Cont)
    00221        : Row(r), maxColumns(maxs), C(Cont)
    00222        {}
    00223
    00224        /* After checking the number of columns, the index operator of
    00225           Aux returns a matrix element which is equipped with all
    00226           necessary information to carry out a successful assignment.
    00227         */
    00228
    00229        MatrixElement operator[](size_type c)
    00230        {
    00231            assert(c >= 0 && c < maxColumns);
    00232            return MatrixElement(C, Row, c);
    00233        }
    00234
    00235      private:
    00236        size_type Row, maxColumns;
    00237        ContainerType& C;
    00238    };
    00239
    00240    /* The index operator of the sparseMatrix class returns the
    00241        auxiliary object, whose class is defined as nested inside
    00242        sparseMatrix. */
    00243    Aux operator[](size_type r)
    00244    {
    00245       assert(r >= 0 && r < rows);
    00246       return Aux(r, columns, C);
    00247    }
    00248
    00249     /* Up to this point, from a functionality point of view, the
    00250        sparseMatrix class is sufficiently equipped. In order, however,
    00251        to avoid writing such horrible things as `(*I).first.first' for
    00252        accessing the elements, some auxiliary functions follow which
    00253        determine the indices and associated values of an iterator in a
    00254        more readable way. */
    00255
    00256    size_type Index1(iterator& I) const
    00257    {
    00258       return (*I).first.first;
    00259    }
    00260
    00261    size_type Index2(iterator& I) const
    00262    {
    00263       return (*I).first.second;
    00264    }
    00265
    00266    ValueType Value(iterator& I) const
    00267    {
    00268       return (*I).second;
    00269    }
    00270 };       // class sparseMatrix
    00271
    00272 #endif   // file sparmat.h
    00273
    00274

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines