chain.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// \file
///
/// A chain with 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: December 3, 2014.


#ifndef _CHAINCON_CHAIN_H_
#define _CHAINCON_CHAIN_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 relevant local header files
#include "chaincon/extarray.h"


// --------------------------------------------------
// --------------------- chain ----------------------
// --------------------------------------------------

/// A chain with coefficients in an arbitrary ring.
template <class CellT, class CoefT>
class tChain
{
public:
        /// The type of cells in the chain.
        typedef CellT CellType;

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

        /// The default constructor of an empty chain.
        tChain ();

        /// Returns the number of elements in the chain.
        int_t size () const;

        /// Returns true if and only if the chain is zero.
        bool empty () const;

        /// Returns the n-th cell of the chain.
        const CellT &getCell (int_t n) const;

        /// Returns the coefficient at the n-th cell of the chain.
        const CoefT &getCoef (int_t n) const;

        /// Returns the position of the given cell in the chain
        /// or -1 if the cell is not there.
        int_t position (const CellT &c) const;

        /// Adds a given cell to the chain with the given coefficient.
        void add (const CellT &cell, const CoefT &coef);

        /// Adds a given chain to the chain.
        tChain<CellT,CoefT> &operator += (const tChain<CellT,CoefT> &ch);

        /// Negates all the coefficients in the chain.
        tChain<CellT,CoefT> &negate ();

        /// Multiples the chain by a given coefficient.
        tChain<CellT,CoefT> &operator *= (const CoefT &coef);

        /// Compares if the two chains are equal.
        bool operator == (const tChain<CellT,CoefT> &ch) const;

        /// Swaps the data with another chain.
        void swap (tChain<CellT,CoefT> &ch);

private:
        /// The set of elements in the chain.
        chomp::homology::hashedset<CellT> cells;

        /// The coefficients that appear at the cells in the chain.
        extarray<CoefT> coefs;

}; /* class tChain */

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

template <class CellT, class CoefT>
inline tChain<CellT,CoefT>::tChain ():
        cells (1), coefs ()
{
        return;
} /* tChain::tChain */

template <class CellT, class CoefT>
inline int_t tChain<CellT,CoefT>::size () const
{
        return cells. size ();
} /* tChain::size */

template <class CellT, class CoefT>
inline bool tChain<CellT,CoefT>::empty () const
{
        return cells. empty ();
} /* tChain::empty */

template <class CellT, class CoefT>
inline const CellT &tChain<CellT,CoefT>::getCell (int_t n) const
{
        return cells [n];
} /* tChain::operator [] */

template <class CellT, class CoefT>
inline const CoefT &tChain<CellT,CoefT>::getCoef (int_t n) const
{
        return coefs [n];
} /* tChain::operator [] */

template <class CellT, class CoefT>
inline int_t tChain<CellT,CoefT>::position (const CellT &c) const
{
        return cells. getnumber (c);
} /* tChain::position */

template <class CellT, class CoefT>
inline void tChain<CellT,CoefT>::add (const CellT &cell, const CoefT &coef)
{
        int_t pos = cells. getnumber (cell);
        if (pos < 0)
        {
                pos = cells. size ();
                cells. add (cell);
                coefs [pos] = coef;
        }
        else
        {
                CoefT &c = coefs [pos];
                c += coef;
                if (c == 0)
                {
                        cells. removenum (pos);
                        int_t size = cells. size ();
                        if (pos != size)
                        {
                                coefs [pos]. swap (coefs [size]);
                        }
                }
        }
        return;
} /* tChain::add */

template <class CellT, class CoefT>
inline tChain<CellT,CoefT> &tChain<CellT,CoefT>::operator +=
        (const tChain<CellT,CoefT> &ch)
{
        if (empty ())
        {
                tChain<CellT,CoefT> chainCopy (ch);
                swap (chainCopy);
        }
        else
        {
                int_t size = ch. size ();
                for (int_t i = 0; i < size; ++ i)
                        add (ch. getCell (i), ch. getCoef (i));
        }
        return *this;
} /* tChain::operator += */

template <class CellT, class CoefT>
inline tChain<CellT,CoefT> &tChain<CellT,CoefT>::negate ()
{
        int_t size = cells. size ();
        for (int_t i = 0; i < size; ++ i)
                coefs [i]. negate ();
        return *this;
} /* tChain::negate */

template <class CellT, class CoefT>
inline tChain<CellT,CoefT> &tChain<CellT,CoefT>::operator *=
        (const CoefT &coef)
{
        if (coef == 0)
        {
                chomp::homology::hashedset<CellT> emptyCells (1);
                cells. swap (emptyCells);
                extarray<CoefT> emptyCoefs;
                coefs. swap (emptyCoefs);
        }
        else
        {
                int_t size = cells. size ();
                for (int_t i = 0; i < size; ++ i)
                        coefs [i] *= coef;
        }
        return *this;
} /* tChain::operator *= */

template <class CellT, class CoefT>
inline bool tChain<CellT,CoefT>::operator == (const tChain<CellT,CoefT> &ch)
        const
{
        int_t size = cells. size ();
        if (size != ch. cells. size ())
                return false;
        for (int_t pos = 0; pos < size; ++ pos)
        {
                int_t chPos = ch. cells. getnumber (cells [pos]);
                if (chPos < 0)
                        return false;
                if (!(coefs [pos] == ch. coefs [chPos]))
                        return false;
        }
        return true;
} /* tChain::operator == */

template <class CellT, class CoefT>
inline void tChain<CellT,CoefT>::swap (tChain<CellT,CoefT> &ch)
{
        cells. swap (ch. cells);
        coefs. swap (ch. coefs);
        return;
} /* tChain::swap */

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

/// Writes a chain to an output stream.
template <class CellT, class CoefT>
std::ostream &operator << (std::ostream &out, const tChain<CellT,CoefT> &c)
{
        int_t size = c. size ();
        if (!size)
                out << '0';
        else
        {
                for (int_t i = 0; i < size; ++ i)
                {
                        if (i)
                                out << " + ";
                        out << c. getCoef (i) << " * " << c. getCell (i);
                }
        }
        return out;
} /* operator << */

/// Reads a chain from an input stream.
template <class CellT, class CoefT>
std::istream &operator >> (std::istream &in, tChain<CellT,CoefT> &c)
{
        throw "Operator >> not implemented for tChain.";
        return in;
} /* operator >> */

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

/// Computes the sum of two chains.
template <class CellT, class CoefT>
tChain<CellT,CoefT> operator + (const tChain<CellT,CoefT> &a,
        const tChain<CellT,CoefT> &b)
{
        tChain<CellT,CoefT> c (a);
        c += b;
        return c;
} /* operator + */

/// Computes the dot product of two chains.
template <class CellT, class CoefT>
CoefT operator * (const tChain<CellT,CoefT> &a,
        const tChain<CellT,CoefT> &b)
{
        // determine the shorter and the longer of the two chains
        const tChain<CellT,CoefT> &shorter
                ((a. size () < b. size ()) ? a : b);
        const tChain<CellT,CoefT> &longer
                ((a. size () < b. size ()) ? b : a);

        // prepare a ring element for the dot product
        CoefT c (0);

        // scan the shorter chain
        int_t length = shorter. length ();
        for (int_t i = 0; i < length; ++ i)
        {
                // find the cell in the longer chain
                int_t j = longer. position (a. getCell (i));
                if (j < 0)
                        continue;

                // add the product of the coefficients to the result
                CoefT x (a. getCoef (i));
                x *= b. getCoef (j);
                c += x;
        }

        return c;
} /* operator * */


#endif // _CHAINCON_CHAIN_H_