This class defines objects which represent chains as finite sequences of elements identified by integral numbers with coefficients in a given Euclidean domain. More...

#include <chains.h>

Public Member Functions
	chain ()
	The default constructor. More...

	chain (const chain< euclidom > &c)
	The copy constructor. More...

chain< euclidom > &	operator= (const chain< euclidom > &c)
	The assignment operator. More...

	~chain ()
	The destructor. More...

int_t	size () const
	Returns the size of the chain, that is, the number of elements with non-zero coefficients. More...

bool	empty () const
	Returns true if the chain is empty (zero), false otherwise. More...

euclidom	getcoefficient (int_t n=-1) const
	Finds and returns the coefficient in front of the given element. More...

int_t	findnumber (int_t n) const
	Find the position of an element with the given identifier. More...

euclidom	coef (int_t i) const
	Returns the coefficient in front of the i-th element in the chain. More...

int_t	num (int_t i) const
	Returns the number (identifier) of the i-th element in the chain. More...

bool	contains_non_invertible () const
	Determines if the chain contains a non-invertible coefficient. More...

int_t	findbest (chain< euclidom > *table=NULL) const
	Finds the best element in the chain for reduction, that is, the element with minimal value of delta. More...

chain< euclidom > &	add (int_t n, euclidom e)
	Adds an element algebraically to the chain. More...

chain< euclidom > &	remove (int_t n)
	Removes an element with the given identifier from the chain. More...

chain< euclidom > &	add (const chain< euclidom > &other, euclidom e, int_t number=-1, chain< euclidom > *table=NULL)
	Adds one chain to another with a given coefficient. More...

chain< euclidom > &	swap (chain< euclidom > &other, int_t number=-1, int_t othernumber=-1, chain< euclidom > *table=NULL)
	Swaps one chain with another. More...

chain< euclidom > &	take (chain< euclidom > &c)
	Takes data from another chain. Destroys the other chain. More...

chain< euclidom > &	multiply (euclidom e, int_t number=-1)
	Multiplies one or all the coefficients in the chain by the given number. More...

outputstream &	show (outputstream &out, const char *label=NULL) const
	Shows the chain to the output stream. More...

std::ostream &	show (std::ostream &out, const char *label=NULL) const
	Shows the chain to the standard output stream. More...

Private Member Functions
chain< euclidom > &	insertpair (int_t i, int_t n, euclidom e)
	Inserts one chain element at the given position. More...

chain< euclidom > &	removepair (int_t i)
	Removes one chain element at the given position. More...

chain< euclidom > &	swapnumbers (int_t number1, int_t number2)
	Swaps two numbers (identifiers) in the chain. More...

Private Attributes
int_t	len
	The length of the list and the length of the table. More...

int_t *	_n
	Identifiers of the elements of the chain (sorted). More...

euclidom *	_e
	Coefficients of the elements of the chain. More...

Detailed Description

template<class euclidom>
class chomp::homology::chain< euclidom >

This class defines objects which represent chains as finite sequences of elements identified by integral numbers with coefficients in a given Euclidean domain.

Definition at line 93 of file chains.h.

Constructor & Destructor Documentation

◆ chain() [1/2]

template<class euclidom >

chomp::homology::chain< euclidom >::chain

inline

The default constructor.

Definition at line 207 of file chains.h.

                              : len(0)
{
        return;
} /* chain<euclidom>::chain */

◆ chain() [2/2]

template<class euclidom >

chomp::homology::chain< euclidom >::chain ( const chain< euclidom > & c )

inline

The copy constructor.

Definition at line 213 of file chains.h.

{
        // copy the length of the chain
        len = c. len;
 
        // allocate new tables and copy the data
        if (len)
        {
                _n = new int_t [len];
                _e = new euclidom [len];
                if (!_n || !_e)
                        throw "Not enough memory to create a chain copy.";
        }
        for (int_t i = 0; i < len; ++ i)
        {
                _n [i] = c. _n [i];
                _e [i] = c. _e [i];
        }
        return;
} /* chain<euclidom>::chain */

◆ ~chain()

template<class euclidom >

chomp::homology::chain< euclidom >::~chain

inline

The destructor.

Definition at line 270 of file chains.h.

{
        if (len)
        {
                delete [] _n;
                delete [] _e;
        }
        return;
} /* chain<euclidom>::~chain */

Member Function Documentation

◆ add() [1/2]

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::add	(	const chain< euclidom > &	other,
		euclidom	e,
		int_t	number = `-1`,
		chain< euclidom > *	table = `NULL`
	)

inline

Adds one chain to another with a given coefficient.

If the chain is a row of a matrix, then its number and the table of columns must be given for proper modification. If this is a column, its number and rows(?) must be given.

Definition at line 598 of file chains.h.

{
        // if the coefficient is zero or the other chain is zero,
        // then there is nothing to do
        if ((e == 0) || !other. len)
                return *this;
 
        // prepare big tables for the new chain
        int_t tablen = len + other. len;
        int_t *bigntab = new int_t [tablen];
        euclidom *bigetab = new euclidom [tablen];
        if (!bigntab || !bigetab)
                throw "Not enough memory to add chains.";
 
        // prepare the counters of elements of the two input chains
        // and of the output chain
        int_t i = 0, j = 0, k = 0;
 
        // go through both input chains and compute the output chain
        while ((i < len) || (j < other. len))
        {
                // if the first chain has already been processed
                if (i >= len)
                {
                        bigntab [k] = other. _n [j];
                        bigetab [k] = e * other. _e [j];
                        ++ j;
                        if (table)
                        {
                                table [bigntab [k]]. add (number,
                                        bigetab [k]);
                        }
                        ++ k;
                }
                // if an element from the first chain should be taken
                else if ((j >= other. len) || (_n [i] < other. _n [j]))
                {
                        bigntab [k] = _n [i];
                        bigetab [k] = _e [i];
                        ++ i;
                        ++ k;
                }
                // if an element from the other chain should be taken
                else if (_n [i] > other. _n [j])
                {
                        bigntab [k] = other. _n [j];
                        bigetab [k] = e * other. _e [j];
                        ++ j;
                        if (table)
                        {
                                table [bigntab [k]]. add (number,
                                        bigetab [k]);
                        }
                        ++ k;
                }
                else // if (_n [i] == other. _n [j])
                {
                        bigntab [k] = _n [i];
                        euclidom addelem = e * other. _e [j];
                        ++ j;
                        bigetab [k] = _e [i] + addelem;
                        ++ i;
                        if (!(bigetab [k] == 0))
                        {
                                if (table)
                                {
                                        table [bigntab [k]]. add (number,
                                                addelem);
                                }
                                ++ k;
                        }
                        else if (table)
                        {
                                table [bigntab [k]]. remove (number);
                        }
                }
        }
 
        // release the old tables if they are useless now
        if ((k != len) || (k == tablen))
        {
                if (len)
                {
                        delete [] _n;
                        delete [] _e;
                }
        }
 
        // use the previous tables and release the big table if beneficial
        if ((k == len) && (k != tablen))
        {
                for (int_t i = 0; i < len; ++ i)
                {
                        _n [i] = bigntab [i];
                        _e [i] = bigetab [i];
                }
                delete [] bigntab;
                delete [] bigetab;
                return *this;
        }
 
        // if the new chain is empty then accomodate for this
        if (k == 0)
        {
                len = 0;
                delete [] bigntab;
                delete [] bigetab;
                return *this;
        }
 
        // if the big tables cannot be used, allocate new tables
        if (k != tablen)
        {
                _n = new int_t [k];
                _e = new euclidom [k];
                if (!_n || !_e)
                        throw "Cannot shorten a sum of chains.";
                len = k;
                for (int_t i = 0; i < len; ++ i)
                {
                        _n [i] = bigntab [i];
                        _e [i] = bigetab [i];
                }
                delete [] bigntab;
                delete [] bigetab;
        }
 
        // otherwise, simply use the big tables
        else
        {
                len = k;
                _n = bigntab;
                _e = bigetab;
        }
 
        return *this;
} /* chain<euclidom>::add */

◆ add() [2/2]

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::add	(	int_t	n,
		euclidom	e
	)

inline

Adds an element algebraically to the chain.

Definition at line 551 of file chains.h.

{
        // if the coefficient is zero, ignore the pair
        if (e == 0)
                return *this;
 
        // find the position in the table for adding this pair
        int_t i = 0;
        while ((i < len) && (_n [i] < n))
                ++ i;
 
        // if an element with this identifier was found, add the coefficients
        if ((i < len) && (_n [i] == n))
        {
                // add the coefficient
                _e [i] += e;
 
                // if the coefficient became zero, remove this pair
                if (_e [i] == 0)
                        return removepair (i);
 
                // otherwise we are done
                else
                        return *this;
        }
 
        // otherwise insert this pair into the chain
        return insertpair (i, n, e);
 
} /* chain<euclidom>::add */

◆ coef()

template<class euclidom >

euclidom chomp::homology::chain< euclidom >::coef ( int_t i ) const

inline

Returns the coefficient in front of the i-th element in the chain.

The coefficient is non-zero.

Definition at line 331 of file chains.h.

{
        if (i >= len)
                throw "Wrong coefficient requested from a chain.";
        return _e [i];
} /* chain<euclidom>::coef */

◆ contains_non_invertible()

template<class euclidom >

bool chomp::homology::chain< euclidom >::contains_non_invertible

inline

Determines if the chain contains a non-invertible coefficient.

Returns true if yes, false if not.

Definition at line 347 of file chains.h.

{
        for (int_t i = 0; i < len; ++ i)
        {
                if (_e [i]. delta () > 1)
                        return true;
        }
        return false;
} /* chain<euclidom>::contains_non_invertible */

◆ empty()

template<class euclidom >

bool chomp::homology::chain< euclidom >::empty

inline

Returns true if the chain is empty (zero), false otherwise.

Definition at line 287 of file chains.h.

{
        return !len;
} /* chain<euclidom>::empty */

◆ findbest()

template<class euclidom >

int_t chomp::homology::chain< euclidom >::findbest ( chain< euclidom > * table = NULL ) const

inline

Finds the best element in the chain for reduction, that is, the element with minimal value of delta.

If the given table is given, then additionally an element with the shortest chain length in the table is searched for. Returns the actual index of this element in the chain (not its identifier) or -1 if the chain is empty (zero).

Definition at line 358 of file chains.h.

{
        // if the chain is so short that the answer is obvious, return it
        if (!len)
                return -1;
        if (len == 1)
                return 0;
 
        // find the number which has the smallest delta function value
        int_t best_delta = _e [0]. delta ();
        int_t best_i = 0;
 
        // go through the whole table to find the first element
        // with the lowest delta possible (1 is the smallest value)
        for (int_t i = 1; (i < len) && (best_delta > 1); ++ i)
        {
                // compute the value of the function delta
                int_t this_delta = _e [i]. delta ();
 
                // if this delta is better, remember it
                if (this_delta < best_delta)
                {
                        best_delta = this_delta;
                        best_i = i;
                }
        }
 
        // if no further analysis is required, return the result just now
        if (!table)
                return best_i;
 
        // analyze which element has the shortest corresponding chain
        // and update "best_i"
        int_t best_length = table [_n [best_i]]. size ();
        for (int_t i = best_i + 1; i < len; ++ i)
        {
                if (_e [i]. delta () != best_delta)
                        continue;
                int_t this_length = table [_n [i]]. size ();
                if (best_length > this_length)
                {
                        best_length = this_length;
                        best_i = i;
                }
        }
 
        return best_i;
} /* chain<euclidom>::findbest */

◆ findnumber()

template<class euclidom >

int_t chomp::homology::chain< euclidom >::findnumber ( int_t n ) const

inline

Find the position of an element with the given identifier.

Returns -1 if not found.

Definition at line 318 of file chains.h.

{
        for (int_t i = 0; i < len; ++ i)
        {
                if (_n [i] == n)
                        return i;
                else if (_n [i] > n)
                        return -1;
        }
        return -1;
} /* chain<euclidom>::findnumber */

◆ getcoefficient()

template<class euclidom >

euclidom chomp::homology::chain< euclidom >::getcoefficient ( int_t n = -1 ) const

Finds and returns the coefficient in front of the given element.

If the identifier is negative then returns the first nonzero coefficient or 0 if none.

Definition at line 293 of file chains.h.

{
        if (n < 0)
        {
                if (len > 0)
                        return _e [0];
                else
                {
                        euclidom zero;
                        zero = 0;
                        return zero;
                }
        }
 
        int_t i = 0;
        while ((i < len) && (_n [i] < n))
                ++ i;
        if ((i < len) && (_n [i] == n))
                return _e [i];
        euclidom zero;
        zero = 0;
        return zero;
} /* chain<euclidom>::getcoefficient */

◆ insertpair()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::insertpair	(	int_t	i,
		int_t	n,
		euclidom	e
	)

inlineprivate

Inserts one chain element at the given position.

The correctness of the position is not verified.

Definition at line 410 of file chains.h.

{
        // remember the addresses of the old tables
        int_t *old_n = _n;
        euclidom *old_e = _e;
 
        // allocate new tables
        _n = new int_t [len + 1];
        _e = new euclidom [len + 1];
        if (!_n || !_e)
                throw "Cannot add an element to a chain.";
 
        // increase the length
        ++ len;
 
        // copy the old data and insert the new pair
        for (int_t j = 0; j < i; ++ j)
        {
                _n [j] = old_n [j];
                _e [j] = old_e [j];
        }
        _n [i] = n;
        _e [i] = e;
        for (int_t j = i + 1; j < len; ++ j)
        {
                _n [j] = old_n [j - 1];
                _e [j] = old_e [j - 1];
        }
 
        // release the previous tables if they were allocated
        if (len > 1)
        {
                delete [] old_n;
                delete [] old_e;
        }
 
        return *this;
} /* chain<euclidom>::insertpair */

◆ multiply()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::multiply	(	euclidom	e,
		int_t	number = `-1`
	)

inline

Multiplies one or all the coefficients in the chain by the given number.

Definition at line 801 of file chains.h.

{
        // if there is only one element to be multiplied, find it and do it
        if (number >= 0)
        {
                for (int_t i = 0; i < len; ++ i)
                {
                        if (_n [i] == number)
                        {
                                if (e == 0)
                                        removepair (i);
                                else
                                {
                                        _e [i] *= e;
                                //      if (_e [i] == 0)
                                //              removepair (i);
                                }
                                return *this;
                        }
                }
        }
 
        // if the entire chain has to be multiplied by a non-zero number...
        else if (!(e == 0))
        {
                for (int_t i = 0; i < len; ++ i)
                {
                        _e [i] *= e;
                //      if (_e [i] == 0)
                //              removepair (i);
                }
        }
 
        // otherwise, if the chain has to be made zero, clean it
        else
        {
                if (len)
                {
                        delete [] _n;
                        delete [] _e;
                }
                len = 0;
        }
 
        return *this;
} /* chain<euclidom>::multiply */

◆ num()

template<class euclidom >

int_t chomp::homology::chain< euclidom >::num ( int_t i ) const

inline

Returns the number (identifier) of the i-th element in the chain.

Definition at line 339 of file chains.h.

{
        if (i >= len)
                throw "Wrong number requested from a chain.";
        return _n [i];
} /* chain<euclidom>::num */

◆ operator=()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::operator= ( const chain< euclidom > & c )

inline

The assignment operator.

Definition at line 235 of file chains.h.

{
        // protect against self-assignment
        if (&c == this)
                return *this;
 
        // make sure the lengths of the chains are the same
        if (len != c.len)
        {
                if (len)
                {
                        delete [] _n;
                        delete [] _e;
                }
                len = c.len;
                if (len)
                {
                        _n = new int_t [len];
                        _e = new euclidom [len];
                        if (!_n || !_e)
                                throw "Not enough memory to create a chain copy =.";
                }
        }
 
        // copy the data
        for (int_t i = 0; i < len; ++ i)
        {
                _n [i] = c. _n [i];
                _e [i] = c. _e [i];
        }
        return *this;
} /* chain<euclidom>::operator = */

References chomp::homology::chain< euclidom >::len.

◆ remove()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::remove ( int_t n )

Removes an element with the given identifier from the chain.

Definition at line 583 of file chains.h.

{
        // find the element of the chain to be removed
        int_t i = 0;
        while ((i < len) && (_n [i] < n))
                ++ i;
 
        // if found, then remove it
        if ((i < len) && (_n [i] == n))
                return removepair (i);
 
        return *this;
} /* chain<euclidom>::remove */

◆ removepair()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::removepair ( int_t i )

inlineprivate

Removes one chain element at the given position.

The correctness of the position is not verified.

Definition at line 451 of file chains.h.

{
        // make sure the chain is not empty
        if (!len)
                throw "Trying to remove an element from an empty chain.";
 
        // remember the addresses of the old tables
        int_t *old_n = _n;
        euclidom *old_e = _e;
 
        // allocate new tables if necessary
        if (len > 1)
        {
                _n = new int_t [len - 1];
                _e = new euclidom [len - 1];
                if (!_n || !_e)
                        throw "Cannot add an element to a chain.";
        }
 
        // decrease the length
        -- len;
 
        // copy the data form the previous tables
        for (int_t j = 0; j < i; ++ j)
        {
                _n [j] = old_n [j];
                _e [j] = old_e [j];
        }
        for (int_t j = i; j < len; ++ j)
        {
                _n [j] = old_n [j + 1];
                _e [j] = old_e [j + 1];
        }
 
        // release the previous tables
        delete [] old_n;
        delete [] old_e;
 
        return *this;
} /* chain<euclidom>::removepair */

◆ show() [1/2]

template<class euclidom >

outputstream & chomp::homology::chain< euclidom >::show	(	outputstream &	out,
		const char *	label = `NULL`
	)		const

inline

Shows the chain to the output stream.

Uses a given label for indicating identifiers of elements in the chain.

Definition at line 849 of file chains.h.

{
        if (len <= 0)
                out << "0";
        for (int_t i = 0; i < len; ++ i)
        {
                euclidom e = _e [i];
                int_t n = _n [i] + 1;
 
                if (e == 1)
                        out << (i ? " + " : "") <<
                                (label ? label : "") << n;
                else if (-e == 1)
                        out << (i ? " - " : "-") <<
                                (label ? label : "") << n;
                else
                        out << (i ? " + " : "") << e << " * " <<
                                (label ? label : "") << n;
        }
        return out;
} /* chain<euclidom>::show */

◆ show() [2/2]

template<class euclidom >

std::ostream & chomp::homology::chain< euclidom >::show	(	std::ostream &	out,
		const char *	label = `NULL`
	)		const

inline

Shows the chain to the standard output stream.

Uses a given label for indicating identifiers of elements in the chain.

Definition at line 873 of file chains.h.

{
        outputstream tout (out);
        show (tout, label);
        return out;
} /* chain<euclidom>::show */

◆ size()

template<class euclidom >

int_t chomp::homology::chain< euclidom >::size

inline

Returns the size of the chain, that is, the number of elements with non-zero coefficients.

Definition at line 281 of file chains.h.

{
        return len;
} /* chain<euclidom>::size */

◆ swap()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::swap	(	chain< euclidom > &	other,
		int_t	number = `-1`,
		int_t	othernumber = `-1`,
		chain< euclidom > *	table = `NULL`
	)

inline

Swaps one chain with another.

If the chain is a row of a matrix, then its number, the number of the other row and the table of columns must be given for proper modification; if this is a column, its number and rows(?) must be given

Definition at line 738 of file chains.h.

{
        // swap the data of the chains
        swapelements (_n, other. _n);
        swapelements (_e, other. _e);
        swapelements (len, other. len);
 
        if (!table)
                return *this;
 
        // change the numbers in every relevant entry of the table
        int_t i = 0;
        int_t j = 0;
        while ((i < len) || (j < other. len))
        {
                // determine which table entry should be modified
                int_t n;
                if (i >= len)
                        n = other. _n [j ++];
                else if (j >= other. len)
                        n = _n [i ++];
                else if (_n [i] < other. _n [j])
                        n = _n [i ++];
                else if (other. _n [j] < _n [i])
                        n = other. _n [j ++];
                else
                {
                        n = _n [i ++];
                        ++ j;
                //      ++ i;
                //      ++ j;
                //      continue;
                }
 
                // swap numbers in that table entry
                table [n]. swapnumbers (othernumber, number);
        }
 
        return *this;
} /* chain<euclidom>::swap */

References chomp::homology::swapelements().

◆ swapnumbers()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::swapnumbers	(	int_t	number1,
		int_t	number2
	)

inlineprivate

Swaps two numbers (identifiers) in the chain.

Definition at line 493 of file chains.h.

{
        // if the numbers are the same, do nothing
        if (number1 == number2)
                return *this;
 
        // force the first number be less than the second number
        if (number1 > number2)
                std::swap (number1, number2);
 
        // find both numbers or the positions they should be at
        int_t i1 = 0;
        while ((i1 < len) && (_n [i1] < number1))
                ++ i1;
        int_t i2 = i1;
        while ((i2 < len) && (_n [i2] < number2))
                ++ i2;
 
        // if the first number was found...
        if ((i1 < len) && (_n [i1] == number1))
        {
                // if both numbers were found, exchange their coefficients
                if ((i2 < len) && (_n [i2] == number2))
                        swapelements (_e [i1], _e [i2]);
                // if only the first was found, move it to the new position
                else
                {
                        euclidom temp = _e [i1];
                        for (int_t i = i1 + 1; i < i2; ++ i)
                        {
                                _n [i - 1] = _n [i];
                                _e [i - 1] = _e [i];
                        }
                        _n [i2 - 1] = number2;
                        _e [i2 - 1] = temp;
                }
        }
 
        // otherwise if the second number only was found, move it to its pos.
        else if ((i2 < len) && (_n [i2] == number2))
        {
                euclidom temp = _e [i2];
                for (int_t i = i2; i > i1; -- i)
                {
                        _n [i] = _n [i - 1];
                        _e [i] = _e [i - 1];
                }
                _n [i1] = number1;
                _e [i1] = temp;
        }
 
        return *this;
} /* chain<euclidom>::swapnumbers */

References chomp::multiwork::swap(), and chomp::homology::swapelements().

◆ take()

template<class euclidom >

chain< euclidom > & chomp::homology::chain< euclidom >::take ( chain< euclidom > & c )

inline

Takes data from another chain. Destroys the other chain.

Definition at line 781 of file chains.h.

{
        // release the current tables if they were allocated
        if (len)
        {
                delete [] _n;
                delete [] _e;
        }
 
        _n = c. _n;
        _e = c. _e;
 
        // copy the length and reset the other length
        len = c. len;
        c. len = 0;
 
        return *this;
} /* chain<euclidom>::take */

Member Data Documentation

◆ _e

template<class euclidom >

euclidom* chomp::homology::chain< euclidom >::_e

private

Coefficients of the elements of the chain.

Definition at line 189 of file chains.h.

◆ _n

template<class euclidom >

int_t* chomp::homology::chain< euclidom >::_n

private

Identifiers of the elements of the chain (sorted).

Definition at line 186 of file chains.h.

◆ len

template<class euclidom >

int_t chomp::homology::chain< euclidom >::len

private

The length of the list and the length of the table.

Definition at line 183 of file chains.h.

Referenced by chomp::homology::chain< euclidom >::operator=().

The documentation for this class was generated from the following file:

chomp/homology/chains.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ chain() [1/2]

◆ chain() [2/2]

◆ ~chain()

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ coef()

◆ contains_non_invertible()

◆ empty()

◆ findbest()

◆ findnumber()

◆ getcoefficient()

◆ insertpair()

◆ multiply()

◆ num()

◆ operator=()

◆ remove()

◆ removepair()

◆ show() [1/2]

◆ show() [2/2]

◆ size()

◆ swap()

◆ swapnumbers()

◆ take()

Member Data Documentation

◆ _e

◆ _n

◆ len