linmap.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// \file
///
/// A linear map for coefficients in an arbitrary commutative ring.
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2009-2016 by Pawel Pilarczyk.
//
// This file is part of my research software package. This is free software:
// you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this software; see the file "license.txt". If not,
// please, see <http://www.gnu.org/licenses/>.

// Started on March 24, 2009. Last revision: April 12, 2013.


#ifndef _CHAINCON_LINMAP_H_
#define _CHAINCON_LINMAP_H_


// include some standard C++ header files
#include <istream>
#include <ostream>

// include selected header files from the CHomP library
#include "chomp/system/config.h"
#include "chomp/struct/hashsets.h"
#include "chomp/struct/multitab.h"

// include relevant local header files
#include "chaincon/chain.h"
#include "chaincon/tensor.h"


// --------------------------------------------------
// ------------------- linear map -------------------
// --------------------------------------------------

/// A linear map.
/// This is in fact a finite set of cells mapped to a chain each.
/// It corresponds to a linear map on the vector space
/// generated by the cells over the coefficients field F_2 (a.k.a. Z_2).
template <class CellDomT, class CellImgT, class CoefT>
class tLinMap
{
public:
        /// The type of cells in the domain of the linear map.
        typedef CellDomT CellDomType;

        /// The type of cells in the images of the linear map.
        typedef CellImgT CellImgType;

        /// The type of coefficients in the chain.
        typedef CoefT CoefType;

        /// The type of the corresponding domain chain.
        typedef tChain<CellDomT,CoefT> ChainDomType;

        /// The type of the corresponding image chain.
        typedef tChain<CellImgT,CoefT> ChainImgType;

        /// The type of the corresponding domain chain.
        typedef tTensor<CellDomT,CellDomT,CoefT> TensorDomType;

        /// The type of the corresponding image chain.
        typedef tTensor<CellImgT,CellImgT,CoefT> TensorImgType;

        /// The default constructor.
        tLinMap ();

        /// Adds a cell to the domain of the map, with zero image,
        /// and returns its number.
        int_t add (const CellDomT &c);

        /// Adds a cell to the image of the given cell.
        void add (const CellDomT &c, const CellImgT &d, const CoefT &coef);

        /// Adds a chain to the image of the given cell.
        void add (const CellDomT &c, const tChain<CellImgT,CoefT> &ch);

        // Swaps the image of the given cell with the provided chain.
        // This method is much faster than using "add".
//      void swapImage (const CellDomT &c, tChain<CellImgT,CoefT> &ch);

        /// Adds another map to the given map.
        tLinMap<CellDomT,CellImgT,CoefT> &operator +=
                (const tLinMap<CellDomT,CellImgT,CoefT> &f);

        /// Replaces all the coefficients in the map with their negation.
        tLinMap<CellDomT,CellImgT,CoefT> &negate ();

        /// Multiplies all the coefficients in the map by the given number.
        tLinMap<CellDomT,CellImgT,CoefT> &operator *= (const CoefT &c);

        /// Removes the given cell from the domain of the map.
        /// Note that this may change the order of cells in the domain.
        void removenum (int_t n);

        /// Removes the given cell from the domain of the map.
        /// Note that this may change the order of cells in the domain.
        void remove (const CellDomT &c);

        /// Returns the image of the given cell.
        const tChain<CellImgT,CoefT> &operator () (int_t n) const;

        /// Returns the image of the given cell.
        tChain<CellImgT,CoefT> operator () (const CellDomT &c) const;

        /// Computes the image of the given chain.
        tChain<CellImgT,CoefT> operator ()
                (const tChain<CellDomT,CoefT> &ch) const;

        /// Computes the image of the given tensor.
        tTensor<CellImgT,CellImgT,CoefT> operator ()
                (const tTensor<CellDomT,CellDomT,CoefT> &ch) const;

        /// Returns the number of elements in the domain
        /// of the map. Note that the images
        /// of some of the elements might be zero.
        int_t size () const;

        /// Returns the n-th element of the domain of the map.
        const CellDomT &operator [] (int_t n) const;

        /// Returns the domain of the map.
        const chomp::homology::hashedset<CellDomT> &getDomain () const;

        /// Returns the image of the given cell for editing.
        tChain<CellImgT,CoefT> &getImage (int_t n);

        /// Returns the image of the given cell for editing.
        tChain<CellImgT,CoefT> &getImage (const CellDomT &c);

        /// Verifies if the two linear maps are the same.
        bool operator == (const tLinMap<CellDomT,CellImgT,CoefT> &f) const;

        /// Swaps the data with another linear map.
        void swap (tLinMap<CellDomT,CellImgT,CoefT> &f);

private:
        /// The domain of the map.
        chomp::homology::hashedset<CellDomT> domain;

        /// The chains in the images of each domain element.
        chomp::homology::multitable<tChain<CellImgT,CoefT> > images;

}; /* class tLinMap */

// --------------------------------------------------

template <class CellDomT, class CellImgT, class CoefT>
inline tLinMap<CellDomT,CellImgT,CoefT>::tLinMap ():
        domain (1000), images (256)
{
        return;
} /* tLinMap::tLinMap */

template <class CellDomT, class CellImgT, class CoefT>
inline int_t tLinMap<CellDomT,CellImgT,CoefT>::add (const CellDomT &c)
{
        return domain. add (c);
} /* tLinMap::add */

template <class CellDomT, class CellImgT, class CoefT>
inline void tLinMap<CellDomT,CellImgT,CoefT>::add
        (const CellDomT &c, const CellImgT &d, const CoefT &coef)
{
        int_t n = domain. getnumber (c);
        if (n < 0)
        {
                n = domain. size ();
                domain. add (c);
        }
        images [n]. add (d, coef);
        return;
} /* tLinMap::add */

template <class CellDomT, class CellImgT, class CoefT>
inline void tLinMap<CellDomT,CellImgT,CoefT>::add
        (const CellDomT &c, const tChain<CellImgT,CoefT> &ch)
{
        int_t n = domain. getnumber (c);
        if (n < 0)
        {
                n = domain. size ();
                domain. add (c);
        }
        images [n] += ch;
        return;
} /* tLinMap::add */

/*
template <class CellDomT, class CellImgT, class CoefT>
inline void tLinMap<CellDomT,CellImgT,CoefT>::swapImage
        (const CellDomT &c, tChain<CellImgT,CoefT> &ch)
{
        int_t n = domain. getnumber (c);
        if (n < 0)
        {
                n = domain. size ();
                domain. add (c);
        }
        images [n]. swap (ch);
        return;
}*/ /* tLinMap::swapImage */

template <class CellDomT, class CellImgT, class CoefT>
inline tLinMap<CellDomT,CellImgT,CoefT> &
        tLinMap<CellDomT,CellImgT,CoefT>::operator +=
        (const tLinMap<CellDomT,CellImgT,CoefT> &f)
{
        int_t size = f. domain. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                if (f. images [i]. empty ())
                        continue;
                add (f. domain [i], f. images [i]);
        }
        return *this;
} /* tLinMap::operator += */

template <class CellDomT, class CellImgT, class CoefT>
inline tLinMap<CellDomT,CellImgT,CoefT> &
        tLinMap<CellDomT,CellImgT,CoefT>::negate ()
{
        int_t size = domain. size ();
        for (int_t i = 0; i < size; ++ i)
                images [i]. negate ();
        return *this;
} /* tLinMap::negate */

template <class CellDomT, class CellImgT, class CoefT>
inline tLinMap<CellDomT,CellImgT,CoefT> &
        tLinMap<CellDomT,CellImgT,CoefT>::operator *= (const CoefT &c)
{
        int_t size = domain. size ();
        for (int_t i = 0; i < size; ++ i)
                images [i] *= c;
        return *this;
} /* tLinMap::operator *= */

template <class CellDomT, class CellImgT, class CoefT>
inline void tLinMap<CellDomT,CellImgT,CoefT>::removenum (int_t n)
{
        domain. removenum (n);
        tChain<CellImgT,CoefT> empty;
        images [n] = empty;
        if (n != domain. size ())
                images [n]. swap (images [domain. size ()]);
        return;
} /* tLinMap::removenum */

template <class CellDomT, class CellImgT, class CoefT>
inline void tLinMap<CellDomT,CellImgT,CoefT>::remove (const CellDomT &c)
{
        int_t n = domain. getnumber (c);
        if (n >= 0)
                removenum (n);
        return;
} /* tLinMap::remove */

template <class CellDomT, class CellImgT, class CoefT>
inline const tChain<CellImgT,CoefT> &
        tLinMap<CellDomT,CellImgT,CoefT>::operator () (int_t n) const
{
        return images [n];
} /* tLinMap::operator () */

template <class CellDomT, class CellImgT, class CoefT>
inline tChain<CellImgT,CoefT> tLinMap<CellDomT,CellImgT,CoefT>::operator ()
        (const CellDomT &c) const
{
        int_t n = domain. getnumber (c);
        if (n >= 0)
                return images [n];
        else
                return tChain<CellImgT,CoefT> ();
} /* tLinMap::operator () */

template <class CellDomT, class CellImgT, class CoefT>
inline tChain<CellImgT,CoefT> tLinMap<CellDomT,CellImgT,CoefT>::operator ()
        (const tChain<CellDomT,CoefT> &ch) const
{
        tChain<CellImgT,CoefT> image;
        int_t size = ch. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                int_t n = domain. getnumber (ch. getCell (i));
                if (n < 0)
                        continue;
                const CoefT &coef (ch. getCoef (i));
                if (coef == 1)
                        image += images [n];
                else
                {
                        tChain<CellImgT,CoefT> img (images [n]);
                        img *= coef;
                        image += img;
                }
        }
        return image;
} /* tLinMap::operator () */

template <class CellDomT, class CellImgT, class CoefT>
inline tTensor<CellImgT,CellImgT,CoefT>
        tLinMap<CellDomT,CellImgT,CoefT>::operator ()
        (const tTensor<CellDomT,CellDomT,CoefT> &ch) const
{
        tTensor<CellImgT,CellImgT,CoefT> image;
        int_t size = ch. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                int_t n1 = domain. getnumber (ch. left (i));
                if (n1 < 0)
                        continue;
                int_t n2 = domain. getnumber (ch. right (i));
                if (n2 < 0)
                        continue;
                if (ch. coef (i) == 1)
                        image. add (images [n1], images [n2]);
                else
                {
                        tChain<CellImgT,CoefT> img1 (images [n1]);
                        img1 *= ch. coef (i);
                        image. add (img1, images [n2]);
                }
        }
        return image;
} /* tLinMap::operator () */

template <class CellDomT, class CellImgT, class CoefT>
inline int_t tLinMap<CellDomT,CellImgT,CoefT>::size () const
{
        return domain. size ();
} /* tLinMap::size */

template <class CellDomT, class CellImgT, class CoefT>
inline const CellDomT &tLinMap<CellDomT,CellImgT,CoefT>::operator []
        (int_t n) const
{
        return domain [n];
} /* tLinMap::operator [] */

template <class CellDomT, class CellImgT, class CoefT>
inline const chomp::homology::hashedset<CellDomT> &
        tLinMap<CellDomT,CellImgT,CoefT>::getDomain () const
{
        return domain;
} /* tLinMap::getDomain */

template <class CellDomT, class CellImgT, class CoefT>
inline tChain<CellImgT,CoefT> &tLinMap<CellDomT,CellImgT,CoefT>::getImage
        (int_t n)
{
        return images [n];
} /* tLinMap::getImage */

template <class CellDomT, class CellImgT, class CoefT>
inline tChain<CellImgT,CoefT> &tLinMap<CellDomT,CellImgT,CoefT>::getImage
        (const CellDomT &c)
{
        int_t n = domain. getnumber (c);
        if (n < 0)
        {
                n = domain. size ();
                domain. add (c);
        }
        return images [n];
} /* tLinMap::getImage */

template <class CellDomT, class CellImgT, class CoefT>
inline bool tLinMap<CellDomT,CellImgT,CoefT>::operator ==
        (const tLinMap<CellDomT,CellImgT,CoefT> &f) const
{
        int_t thisSize = domain. size ();
        for (int_t i = 0; i < thisSize; ++ i)
        {
                const CellDomT &x = domain [i];
                const tChain<CellImgT,CoefT> &y = images [i];
                if (y. empty ())
                        continue;
                int_t n = f. domain. getnumber (x);
                if (n < 0)
                        return false;
                if (!(y == f. images [n]))
                        return false;
        }
        int_t fSize = f. domain. size ();
        for (int_t i = 0; i < fSize; ++ i)
        {
                const CellDomT &x = f. domain [i];
                const tChain<CellImgT,CoefT> &y = f. images [i];
                if (y. empty ())
                        continue;
                int_t n = domain. getnumber (x);
                if (n < 0)
                        return false;
                if (!(y == images [n]))
                        return false;
        }
        return true;
} /* tLinMap::operator == */

template <class CellDomT, class CellImgT, class CoefT>
inline void tLinMap<CellDomT,CellImgT,CoefT>::swap
        (tLinMap<CellDomT,CellImgT,CoefT> &f)
{
        domain. swap (f. domain);
        images. swap (f. images);
        return;
} /* tLinMap::swap */

// --------------------------------------------------

/// Writes a linear map to an output stream in the text mode.
template <class CellDomT, class CellImgT, class CoefT>
inline std::ostream &operator << (std::ostream &out,
        const tLinMap<CellDomT,CellImgT,CoefT> &f)
{
        bool trivial = true;
        int_t size = f. size ();
        for (int_t n = 0; n < size; ++ n)
        {
                const tChain<CellImgT,CoefT> &ch = f (n);
                if (ch. empty ())
                        continue;
                trivial = false;
                const CellDomT &c = f [n];
                out << c << " -> " << ch << "\n";
        }
        if (trivial)
                out << '0';
        return out;
} /* operator << */

/// Reads a linear map from an input stream.
template <class CellDomT, class CellImgT, class CoefT>
inline std::istream &operator >> (std::istream &in,
        tLinMap<CellDomT,CellImgT,CoefT> &f)
{
        throw "Operator >> not implemented for tLinMap.";
        return in;
} /* operator >> */

// --------------------------------------------------

/// Adds the identity map on the given domain to the map 'f'.
template <class CellArray, class CellT, class CoefT>
inline void addIdentity (const CellArray &domain,
        tLinMap<CellT,CellT,CoefT> &f)
{
        int_t size = domain. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                const CellT &c = domain [i];
                f. add (c, c, CoefT (1));
        }
        return;
} /* addIdentity */

/// Returns the identity map on the given domain.
template <class CellArray, class CellT, class CoefT>
inline tLinMap<CellT,CellT,CoefT> identity (const CellArray &domain)
{
        tLinMap<CellT,CellT,CoefT> f;
        addIdentity (domain, f);
        return f;
} /* identity */

/// Computes the composition of the two given maps.
/// More precisely, for each x in the domain of g,
/// the new map on x is defined as f(g(x)).
template <class CellXT, class CellYT, class CellZT, class CoefT>
inline tLinMap<CellXT,CellZT,CoefT> operator *
        (const tLinMap<CellYT,CellZT,CoefT> &f,
        const tLinMap<CellXT,CellYT,CoefT> &g)
{
        tLinMap<CellXT,CellZT,CoefT> result;
        int_t size = g. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                const CellXT &x = g [i];
                const tChain<CellYT,CoefT> &y = g (i);
                const tChain<CellZT,CoefT> z = f (y);
                if (z. empty ())
                        continue;
                result. add (x, z);
        }
        return result;
} /* operator * */


#endif // _CHAINCON_LINMAP_H_