chaincon/comblinmap.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// \file
///
/// A combinatorial linear map (for coefficients in Z_2).
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2009-2011 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: March 6, 2011.


#ifndef _CHAINCON_COMBLINMAP_H_
#define _CHAINCON_COMBLINMAP_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/combchain.h"
#include "chaincon/combtensor.h"


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

/// A combinatorial 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 tCombLinMap
{
public:
        /// The type of cells in the domain of the combinatorial linear map.
        typedef CellDomT CellDomType;

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

        /// The default constructor.
        tCombLinMap ();

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

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

        /// Adds another map to the given map.
        void add (const tCombLinMap<CellDomT,CellImgT> &f);

        /// 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 tCombChain<CellImgT> &operator () (int_t n) const;

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

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

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

        /// Returns the number of elements in the domain
        /// of the combinatorial 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 combinatorial map.
        const CellDomT &operator [] (int_t n) const;

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

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

        /// Verifies if the two combinatorial linear map are the same.
        bool operator == (const tCombLinMap<CellDomT,CellImgT> &f) const;

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

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

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

}; /* class tCombLinMap */

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

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

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

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

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

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

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

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

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

template <class CellDomT, class CellImgT>
inline tCombChain<CellImgT> tCombLinMap<CellDomT,CellImgT>::operator ()
        (const tCombChain<CellDomT> &ch) const
{
        tCombChain<CellImgT> image;
        int_t size = ch. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                int_t n = domain. getnumber (ch [i]);
                if (n >= 0)
                        image. add (images [n]);
        }
        return image;
} /* tCombLinMap::operator () */

template <class CellDomT, class CellImgT>
inline tCombTensor<CellImgT> tCombLinMap<CellDomT,CellImgT>::operator ()
        (const tCombTensor<CellDomT> &ch) const
{
        tCombTensor<CellImgT> image;
        int_t size = ch. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                int_t n1 = domain. getnumber (ch. left (i));
                int_t n2 = domain. getnumber (ch. right (i));
                if ((n1 >= 0) && (n2 >= 0))
                        image. add (images [n1], images [n2]);
        }
        return image;
} /* tCombLinMap::operator () */

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

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

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

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

template <class CellDomT, class CellImgT>
inline bool tCombLinMap<CellDomT,CellImgT>::operator ==
        (const tCombLinMap<CellDomT,CellImgT> &f) const
{
        int_t thisSize = domain. size ();
        for (int_t i = 0; i < thisSize; ++ i)
        {
                const CellDomT &x = domain [i];
                const tCombChain<CellImgT> &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 tCombChain<CellImgT> &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;
} /* tCombLinMap::operator == */

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

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

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

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

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

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

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

/// Computes the full boundary map for a cellular complex that contains
/// the cells in a provided set and all their boundary cells.
/// The map is assumed to be initially zero.
template <class CellArray, class CellT>
inline void computeBoundaryMap (const CellArray &cells,
        tCombLinMap<CellT,CellT> &f)
{
        // prepare a set of cells whose boundaries yet have to be computed
        chomp::homology::hashedset<CellT> waiting;

        // process all the cells in the domain of the map
        // (note that the domain may increase during this process)
        int_t inputCellNumber = 0;
        const int_t inputCellCount = cells. size ();
        while (1)
        {
                // determine whether a cell from the array should be used
                bool useInput = (inputCellNumber < inputCellCount);

                // if the input array has been used and the set
                // of wating cells as well then exit the loop
                if (!useInput && waiting. empty ())
                        break;

                // take a cell for processing
                int_t waitingPosition = waiting. size () - 1;
                const CellT &c = useInput ? cells [inputCellNumber] :
                        waiting [waitingPosition];

                // determine the length of the boundary of this cell
                int length = c. boundaryLength ();

                // process all the cells in its boundary
                for (int b = 0; b < length; ++ b)
                {
                        // create the subsequent boundary cell
                        CellT bc (c, b);

                        // add the boundary cell to the waiting list
                        if (bc. boundaryLength () &&
                                f. getImage (bc). empty ())
                        {
                                waiting. add (bc);
                        }

                        // add the boundary cell to the image of 'c'
                        f. add (c, bc);
                }

                // increase the counter of cells in the input array
                if (useInput)
                        ++ inputCellNumber;

                // or remove the waiting cell which was taken
                else
                        waiting. removenum (waitingPosition);
        }
        return;
} /* computeBoundaryMap */

/// 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>
inline tCombLinMap<CellXT,CellZT> operator *
        (const tCombLinMap<CellYT,CellZT> &f,
        const tCombLinMap<CellXT,CellYT> &g)
{
        tCombLinMap<CellXT,CellZT> result;
        int_t size = g. size ();
        for (int_t i = 0; i < size; ++ i)
        {
                const CellXT &x = g [i];
                const tCombChain<CellYT> &y = g (i);
                const tCombChain<CellZT> z = f (y);
                if (z. empty ())
                        continue;
                result. add (x, z);
        }
        return result;
} /* operator * */


#endif // _CHAINCON_COMBLINMAP_H_