hashsets.h

Go to the documentation of this file.

 
 
 
// Copyright (C) 1997-2020 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 <https://www.gnu.org/licenses/>.
 
// Started in January 2002. Last revision: October 24, 2013.
 
 
#ifndef _CHOMP_STRUCT_HASHSETS_H_
#define _CHOMP_STRUCT_HASHSETS_H_
 
#include "chomp/system/config.h"
#include "chomp/system/textfile.h"
#include "chomp/struct/multitab.h"
#include "chomp/struct/inthash.h"
 
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
 
// make the chomp::homology hashkey methods global ones
//using chomp::homology::hashkey1;
//using chomp::homology::hashkey2;
 
namespace chomp {
namespace homology {
 
// import the global hashkey functions to the chomp::homology namespace
using ::hashkey1;
using ::hashkey2;
 
// class templates defined within this header file (in this order):
template <class element, class hashing>
class hashedset;
template <class domelement, class imgelement>
class mvmap;
 
 
// --------------------------------------------------
// ------------------- hash stat --------------------
// --------------------------------------------------
 
class hashstat
{
public:
        hashstat ();
 
        std::time_t creationtime;
 
        unsigned long hashhits;
 
        unsigned long hashmisses;
 
        unsigned long rehashcount;
 
}; /* class hashstat */
 
// --------------------------------------------------
 
inline hashstat::hashstat ()
{
        std::time (&creationtime);
        hashhits = 0;
        hashmisses = 0;
        rehashcount = 0;
        return;
} /* hashstat::hashstat */
 
// --------------------------------------------------
 
inline std::ostream &operator << (std::ostream &out, const hashstat &s)
{
        if (!s. hashhits)
                return out;
        out << "hashing: " << s. hashhits << " hits, avg " <<
                ((s. hashhits + s. hashmisses) / s. hashhits) << "." <<
                ((s. hashhits + s. hashmisses) * 10 / s. hashhits) % 10 <<
                " attempts (" << s. rehashcount << " times rehashed)";
        return out;
} /* operator << */
 
 
// --------------------------------------------------
// ------------- basic hashing methods --------------
// --------------------------------------------------
 
template <class element>
class HashingGlobal
{
public:
        static int_t hashkey1 (const element &x)
        {
                return chomp::homology::hashkey1 (x);
        }
 
        static int_t hashkey2 (const element &x)
        {
                return chomp::homology::hashkey2 (x);
        }
 
}; /* class HashingGlobal */
 
 
template <class element>
class HashingMember
{
public:
        static int_t hashkey1 (const element &x)
        {
                return x. hashkey1 ();
        }
 
        static int_t hashkey2 (const element &x)
        {
                return x. hashkey2 ();
        }
 
}; /* class HashingMember */
 
 
// --------------------------------------------------
// ------------------- hashed set -------------------
// --------------------------------------------------
 
template <class element, class hashkeys = HashingGlobal<element> >
class hashedset
{
public:
        typedef element value_type;
 
        typedef hashkeys hashing_method;
 
        explicit hashedset (int_t initialsize = 0, int bequiet = 1);
 
        hashedset (const hashedset<element,hashkeys> &s);
 
        hashedset &operator = (const hashedset<element,hashkeys> &s);
 
        ~hashedset (void);
 
        int_t getnumber (const element &e) const;
 
        bool checknum (int_t n) const;
 
        bool check (const element &e) const;
 
        const element &operator [] (int_t n) const;
 
        const element &get (int_t n) const;
 
        const element &front () const;
 
        const element &top () const;
 
        int_t add (const element &e);
 
        int_t push (const element &e);
 
        int_t push_back (const element &e);
 
        int remove (const element &e);
 
        int removenum (int_t n);
 
        int_t pop ();
 
        hashedset<element,hashkeys> &add
                (const hashedset<element,hashkeys> &s);
 
        hashedset<element,hashkeys> &remove
                (const hashedset<element,hashkeys> &s);
 
        int_t size () const;
 
        bool empty () const;
 
        void swap (hashedset<element,hashkeys> &other);
 
        bool operator == (const hashedset<element,hashkeys> &other) const;
 
        void intersection (const hashedset<element,hashkeys> &s1,
                const hashedset<element,hashkeys> &s2);
 
        hashstat *stat;
 
private:
        static const int_t InitHashSize;
 
        static const int_t InitTabSize;
 
        static const int_t StartHashingSize;
 
        int_t nelem;
 
        multitable<element> tab;
 
        int hashing;
 
        int_t hashsize;
 
        int_t hashcleared;
 
        multitable<int_t> hashtable;
 
        int_t hashfind (const element &e, int_t *addpos = NULL) const;
 
        void rehash (int_t newsize = 0);
 
        static bool numberisprime (const int_t &n);
 
        static int_t rounduptoprime (int_t n);
 
}; /* class hashedset */
 
// --------------------------------------------------
 
template <class element, class hashkeys>
const int_t hashedset<element,hashkeys>::InitHashSize (137);
 
template <class element, class hashkeys>
const int_t hashedset<element,hashkeys>::InitTabSize (30);
 
template <class element, class hashkeys>
const int_t hashedset<element,hashkeys>::StartHashingSize (30);
 
// --------------------------------------------------
 
template <class element, class hashkeys>
hashedset<element,hashkeys>::hashedset (int_t initialsize, int bequiet):
        nelem (0), tab ((initialsize > 0) ? initialsize :
                int_t (InitTabSize)),
        hashing (0),
        hashsize (initialsize + (initialsize >> 2) + InitHashSize),
        hashcleared (0), hashtable (hashsize)
{
        hashedset<element,hashkeys>::rounduptoprime (hashsize);
        if (bequiet)
                stat = NULL;
        else
                stat = new hashstat;
        return;
} /* hashedset<element,hashkeys>::hashedset */
 
template <class element, class hashkeys>
hashedset<element,hashkeys>::hashedset (const hashedset<element,hashkeys> &s):
        nelem (s. nelem), tab (s. tab),
        hashing (s. hashing), hashsize (s. hashsize),
        hashcleared (s. hashcleared), hashtable (s. hashtable)
{
        if (s. stat)
                stat = new hashstat;
        else
                stat = NULL;
        return;
} /* hashedset<element,hashkeys>::hashedset */
 
template <class element, class hashkeys>
hashedset<element,hashkeys> &hashedset<element,hashkeys>::operator =
        (const hashedset<element,hashkeys> &s)
{
        if (this == &s)
                return *this;
 
        if (s. stat)
                stat = new hashstat (*stat);
        nelem = s. nelem;
        tab = s. tab;
        hashing = s. hashing;
        hashsize = s. hashsize;
        hashcleared = s. hashcleared;
        hashtable = s. hashtable;
 
        return *this;
} /* multitable<element,hashkeys>::operator = */
 
template <class element, class hashkeys>
hashedset<element,hashkeys>::~hashedset ()
{
        if (!stat)
                return;
        sout << "  " << *stat << '\n';
        delete stat;
        stat = NULL;
        return;
} /* hashedset<element,hashkeys>::~hashedset */
 
template <class element, class hashkeys>
int_t hashedset<element,hashkeys>::getnumber (const element &e) const
{
        if (hashing)
        {
                int_t pos = hashfind (e);
                return (hashtable (pos));
        }
        else
        {
                for (int_t i = 0; i < nelem; ++ i)
                {
                        if (tab (i) == e)
                                return i;
                }
                return -1;
        }
} /* hashedset<element,hashkeys>::getnumber */
 
template <class element, class hashkeys>
inline bool hashedset<element,hashkeys>::checknum (int_t n) const
{
        return ((n >= 0) && (n < nelem));
} /* hashedset<element,hashkeys>::checknum */
 
template <class element, class hashkeys>
inline bool hashedset<element,hashkeys>::check (const element &e) const
{
        return (getnumber (e) >= 0);
} /* hashedset<element,hashkeys>::check */
 
template <class element, class hashkeys>
inline const element &hashedset<element,hashkeys>::get (int_t n) const
{
        if ((n < 0) || (n >= nelem))
                throw "Trying to get an element out of range.";
        return tab (n);
} /* hashedset<element,hashkeys>::get */
 
template <class element, class hashkeys>
inline const element &hashedset<element,hashkeys>::operator [] (int_t n) const
{
        return get (n);
} /* hashedset<element,hashkeys>::operator [] */
 
template <class element, class hashkeys>
inline const element &hashedset<element,hashkeys>::front () const
{
        return get (nelem - 1);
} /* hashedset<element,hashkeys>::front */
 
template <class element, class hashkeys>
inline const element &hashedset<element,hashkeys>::top () const
{
        return get (nelem - 1);
} /* hashedset<element,hashkeys>::top */
 
template <class element, class hashkeys>
int_t hashedset<element,hashkeys>::add (const element &e)
{
        if (!hashing)
        {
                for (int_t i = 0; i < nelem; ++ i)
                {
                        if (tab (i) == e)
                                return i;
                }
                tab [nelem ++] = e;
                if (nelem >= StartHashingSize)
                {
                        hashing = 1;
                        rehash ();
                }
                return (nelem - 1);
        }
 
        // rehash if there is very little free space in the hashing table
        if (hashsize - hashcleared < nelem + (nelem >> 1) + 19)
                rehash ();
 
        // find the position of the element's number in the hashing table
        int_t addpos = -1;
        int_t pos = hashfind (e, &addpos);
 
        // if it alread was in the set, then just return its number
        if (hashtable (pos) >= 0)
                return hashtable (pos);
 
        // add this element to the set and return its new number
        if (addpos >= 0)
                pos = addpos;
        hashtable [pos] = nelem;
        tab [nelem] = e;
        return nelem ++;
} /* hashedset<element,hashkeys>::add */
 
template <class element, class hashkeys>
inline int_t hashedset<element,hashkeys>::push (const element &e)
{
        return add (e);
} /* hashedset<element,hashkeys>::push */
 
template <class element, class hashkeys>
inline int_t hashedset<element,hashkeys>::push_back (const element &e)
{
        return add (e);
} /* hashedset<element,hashkeys>::push_back */
 
template <class element, class hashkeys>
int hashedset<element,hashkeys>::remove (const element &e)
{
        if (!hashing)
        {
                for (int_t i = 0; i < nelem; ++ i)
                {
                        if (tab (i) == e)
                        {
                                tab [i] = tab (-- nelem);
                                return 0;
                        }
                }
                return -1;
        }
 
        // find the position in the hashing table with this element's number
        int_t pos = hashfind (e);
 
        // if it was not there, then finish
        if (hashtable (pos) < 0)
                return -1;
        int_t n = hashtable (pos);
 
        // update the hashing table and the number of elements in the set
        hashtable [pos] = -2;
        -- nelem;
        ++ hashcleared;
 
        // if it was not the last element in the set, move the last one
        // to the vacated place
        if (n != nelem)
        {
                pos = hashfind (tab (nelem));
                hashtable [pos] = n;
                tab [n] = tab (nelem);
        }
 
        // if there are very few elements in the table, turn off hashing
        if (nelem < StartHashingSize / 2)
        {
                hashing = 0;
        }
 
        // if there are very many cleared entries, then rehash
        else if (hashcleared > nelem + 19)
                rehash ();
 
        return 0;
} /* hashedset<element,hashkeys>::remove */
 
template <class element, class hashkeys>
inline int hashedset<element,hashkeys>::removenum (int_t n)
{
        if ((n < 0) || (n >= nelem))
                return -1;
        if (!hashing)
        {
                -- nelem;
                if (n != nelem)
                        tab [n] = tab (nelem);
                return 0;
        }
        return remove (tab (n));
} /* hashedset<element,hashkeys>::removenum */
 
template <class element, class hashkeys>
inline int_t hashedset<element,hashkeys>::pop ()
{
        if (!nelem)
                throw "Trying to remove an element from an empty set.";
        return removenum (nelem - 1);
} /* hashedset<element,hashkeys>::pop */
 
template <class element, class hashkeys>
hashedset<element,hashkeys> &hashedset<element,hashkeys>::add (const hashedset<element,hashkeys> &s)
{
        int_t n = s. size ();
        for (int_t i = 0; i < n; ++ i)
                add (s [i]);
        return *this;
} /* hashedset<element,hashkeys>::add */
 
template <class element, class hashkeys>
hashedset<element,hashkeys> &hashedset<element,hashkeys>::remove (const hashedset<element,hashkeys> &s)
{
        if (this -> size () < s. size ())
        {
                for (int_t i = 0; i < this -> size (); ++ i)
                {
                        if (s. check ((*this) [i]))
                                this -> removenum (i --);
                }
        }
        else
        {
                int_t n = s. size ();
                for (int_t i = 0; i < n; ++ i)
                        remove (s [i]);
        }
        return *this;
} /* hashedset<element,hashkeys>::remove */
 
template <class element, class hashkeys>
inline bool hashedset<element,hashkeys>::empty () const
{
        return !nelem;
} /* hashedset<element,hashkeys>::empty */
 
template <class element, class hashkeys>
inline int_t hashedset<element,hashkeys>::size () const
{
        return nelem;
} /* hashedset<element,hashkeys>::size */
 
template <class element, class hashkeys>
inline void hashedset<element,hashkeys>::swap (hashedset<element,hashkeys> &other)
{
        std::swap (stat, other. stat);
        std::swap (nelem, other. nelem);
        tab. swap (other. tab);
        std::swap (hashing, other. hashing);
        std::swap (hashsize, other. hashsize);
        std::swap (hashcleared, other. hashcleared);
        hashtable. swap (other. hashtable);
        return;
} /* hashedset<element,hashkeys>::swap */
 
template <class element, class hashkeys>
inline bool hashedset<element,hashkeys>::operator ==
        (const hashedset<element,hashkeys> &other) const
{
        if (this -> nelem != other. nelem)
                return false;
        for (int_t i = 0; i < nelem; ++ i)
        {
                if (!other. check (this -> tab [i]))
                        return false;
        }
        return true;
} /* hashedset<element,hashkeys>::swap */
 
template <class element, class hashkeys>
inline void hashedset<element,hashkeys>::intersection (const hashedset<element,hashkeys> &s1,
        const hashedset<element,hashkeys> &s2)
{
        int_t size1 = s1. size ();
        int_t size2 = s2. size ();
 
        if (size1 <= size2)
        {
                for (int_t i = 0; i < size1; ++ i)
                {
                        const element &elem = s1. tab [i];
                        if (s2. check (elem))
                                this -> add (elem);
                }
        }
        else
        {
                for (int_t i = 0; i < size2; ++ i)
                {
                        const element &elem = s2. tab [i];
                        if (s1. check (elem))
                                this -> add (elem);
                }
        }
        return;
} /* hashedset<element,hashkeys>::intersection */
 
template <class element, class hashkeys>
int_t hashedset<element,hashkeys>::hashfind (const element &e, int_t *addpos) const
{
        if (!hashing)
                throw "Hashing is turned off.";
 
        int_t key = hashkey1 (e);
        if (key < 0)
                key = -(key + 1);
        int_t pos = key % hashsize;
        if (addpos)
                *addpos = -1;
 
        // start updating hashing statistics
        if (stat)
                ++ (stat -> hashhits);
 
        // find the position of the element in the hashing table
        int_t number;
        int_t add = 0;
        while ((number = hashtable (pos)) != -1)
        {
                if ((number >= 0) && (e == tab (number)))
                        return (pos);
                if (addpos && (*addpos < 0) && (number == -2))
                        *addpos = pos;
                if (!add)
                {
                        int_t key = hashkey2 (e);
                        if (key < 0)
                                key = -(key + 1);
                        add = key % (hashsize - 1) + 1;
                }
                pos += add;
                if (pos >= hashsize)
                        pos -= hashsize;
                if (stat)
                        ++ (stat -> hashmisses);
        }
 
        // return the position located in the hashing table
        return (pos);
 
} /* hashedset<element,hashkeys>::hashfind */
 
template <class element, class hashkeys>
void hashedset<element,hashkeys>::rehash (int_t newsize)
{
        if (stat)
                ++ (stat -> rehashcount);
 
        // adjust the new size of the hashing table
        if ((newsize < (nelem << 1) + InitHashSize) ||
                (newsize > (nelem << 2) + InitHashSize))
                newsize = (nelem << 1) + nelem + InitHashSize;
 
        // DEBUG
//      sbug << "(rehash: nelem=" << nelem <<
//              ", hashsize=" << hashsize << ", newsize=" << newsize << ")\n";
 
        // check if it is not too large for 16-bit programs
        int_t x = 0xFFFF;
        if ((x < 0) && (newsize >= 16384))
                throw "Set too large for this 16-bit program.";
 
        // free unused memory if desired
        if (newsize < hashsize)
        {
                multitable<int_t> empty;
                hashtable = empty;
        }
        
        // set the new value of the hashing table and re-buid it
        hashsize = hashedset<element,hashkeys>::rounduptoprime (newsize);
        hashcleared = 0;
 
        // build the entire hash table from the beginning
        hashtable. fill (-1, hashsize);
        for (int_t i = 0; i < nelem; ++ i)
        {
                int_t pos = hashfind (tab (i));
                if (hashtable (pos) != -1)
                        throw "A repeated element in a set!";
                hashtable [pos] = i;
        }
 
        return;
} /* hashedset<element,hashkeys>::rehash */
 
template <class element, class hashkeys>
inline bool hashedset<element,hashkeys>::numberisprime (const int_t &n)
{
        if (n < 2)
                return 0;
 
        int_t i = 2;
        while (i * i <= n)
        {
                if (!(n % i))
                        return false;
                ++ i;
        }
 
        return true;
} /* hashedset<element,hashkeys>::numberisprime */
 
template <class element, class hashkeys>
int_t hashedset<element,hashkeys>::rounduptoprime (int_t n)
{
        while (!hashedset<element,hashkeys>::numberisprime (n))
                ++ n;
 
        return n;
} /* hashedset<element,hashkeys>::rounduptoprime */
 
 
// --------------------------------------------------
 
#define SMALL_SIZE true
 
#define LARGE_SIZE false
 
template <class stream, class element, class hashkeys>
stream &write (stream &out, const hashedset<element,hashkeys> &s, bool size)
{
        if (size == SMALL_SIZE)
        {
                out << '{';
                int_t n = s. size ();
                for (int_t i = 0; i < n; ++ i)
                        out << (i ? " " : "") << s [i];
                out << '}';
        }
        else
        {
                int_t n = s. size ();
                if (!s. empty ())
                {
                        out << "; " << n << ((n == 1) ? " element." :
                                " elements.") << '\n';
                }
                if (s. stat && s. stat -> hashhits)
                        out << ';' << *(s. stat) << '\n';
                for (int_t i = 0; i < n; ++ i)
                        out << s [i] << '\n';
        }
        return out;
} /* write */
 
template <class element, class hashkeys>
std::ostream &operator << (std::ostream &out,
        const hashedset<element,hashkeys> &s)
{
        return write (out, s, LARGE_SIZE);
} /* operator << */
 
template <class stream, class element, class hashkeys>
stream &read (stream &in, hashedset<element,hashkeys> &s, bool size)
{
        // ignore all the comments at the beginning of the input stream
        ignorecomments (in);
 
        // determine the closing parenthesis
        // and read the opening one if applicable
        int closing = EOF;
        if (size == SMALL_SIZE)
        {
                closing = readparenthesis (in);
                if (closing == EOF)
                        throw "An opening parenthesis expected in a set.";
                ignorecomments (in);
        }
 
        // read the elements until the closing parenthesis is found
        while (in. peek () != closing)
        {
                element e;
                in >> e;
        //      if (!in)
        //              throw "Failed to read an element of a set.";
                s. add (e);
                ignorecomments (in);
 
                // read a comma between the elements if it is there
                if (in. peek () == ',')
                {
                        in. get ();
                        ignorecomments (in);
                }
        }
 
        // read the closing parenthesis if any
        if (closing != EOF)
                in. get ();
 
        return in;
} /* read */
 
template <class element, class hashkeys>
std::istream &operator >> (std::istream &in, hashedset<element,hashkeys> &s)
{
        return read (in, s, LARGE_SIZE);
} /* operator >> */
 
template <class element, class hashkeys>
inline hashedset<element,hashkeys> &operator += (hashedset<element,hashkeys> &s,
        const hashedset<element,hashkeys> &u)
{
        s. add (u);
        return s;
} /* operator += */
 
template <class element, class hashkeys>
inline hashedset<element,hashkeys> &operator -= (hashedset<element,hashkeys> &s,
        const hashedset<element,hashkeys> &u)
{
        s. remove (u);
        return s;
} /* operator -= */
 
 
// --------------------------------------------------
// ---------------- multivalued map -----------------
// --------------------------------------------------
 
template <class domelement, class imgelement>
class mvmap
{
public:
        explicit mvmap (int bequiet = 1);
 
        ~mvmap ();
 
        const domelement &get (int_t n) const;
 
        const hashedset<domelement> &getdomain () const;
 
        const hashedset<imgelement> &operator () (int_t n) const;
 
        const hashedset<imgelement> &operator ()
                (const domelement &x) const;
 
        hashedset<imgelement> &operator [] (int_t n);
 
        hashedset<imgelement> &operator [] (const domelement &x);
 
        int_t size () const;
 
        bool remove (const domelement &x);
 
        bool removenum (int_t n);
 
        void remove (const hashedset<domelement> &x);
 
        void swap (mvmap<domelement,imgelement> &other);
 
        int quiet;
 
private:
        hashedset<domelement> domain;
 
        multitable<hashedset<imgelement> > images;
 
}; /* class mvmap */
 
// --------------------------------------------------
 
template <class domelement, class imgelement>
inline mvmap<domelement,imgelement>::mvmap (int bequiet):
        domain (0, bequiet), images ()
{
        return;
} /* mvmap::mvmap */
 
template <class domelement, class imgelement>
inline mvmap<domelement,imgelement>::~mvmap ()
{
        return;
} /* mvmap::~mvmap */
 
template <class domelement, class imgelement>
inline const domelement &mvmap<domelement,imgelement>::get (int_t n) const
{
        if ((n < 0) || (n >= domain. size ()))
                throw "Domain element number out of range.";
        return domain [n];
} /* mvmap::get */
 
template <class domelement, class imgelement>
inline const hashedset<domelement> &
        mvmap<domelement,imgelement>::getdomain () const
{
        return domain;
} /* mvmap::getdomain */
 
template <class domelement, class imgelement>
inline const hashedset<imgelement>
        &mvmap<domelement,imgelement>::operator () (int_t n) const
{
        if ((n < 0) || (n >= domain. size ()))
                throw "Domain element number out of range.";
        return images (n);
} /* mvmap::operator () */
 
template <class domelement, class imgelement>
inline const hashedset<imgelement>
        &mvmap<domelement,imgelement>::operator ()
        (const domelement &q) const
{
        int_t n = domain. getnumber (q);
        if (n < 0)
                throw "Element not in the domain.";
        return images (n);
} /* mvmap::operator () */
 
template <class domelement, class imgelement>
inline hashedset<imgelement>
        &mvmap<domelement,imgelement>::operator [] (int_t n)
{
        if ((n < 0) || (n >= domain. size ()))
                throw "Domain element number out of range.";
        return images [n];
} /* mvmap::operator [] */
 
template <class domelement, class imgelement>
inline hashedset<imgelement>
        &mvmap<domelement,imgelement>::operator []
        (const domelement &q)
{
        int_t n = domain. add (q);
        return images [n];
} /* mvmap::operator [] */
 
template <class domelement, class imgelement>
inline int_t mvmap<domelement,imgelement>::size () const
{
        return domain. size ();
} /* mvmap::size */
 
template <class domelement, class imgelement>
inline bool mvmap<domelement,imgelement>::removenum (int_t n)
// WARNING: This procedure uses the specific way elements are removed from
// a hashed set. If that way is changed, this procedure may not work anymore.
{
        if ((n < 0) || (n >= domain. size ()))
                return false;
        domain. removenum (n);
        if (n != domain. size ())
                images [n] = images [domain. size ()];
        hashedset<imgelement> empty;
        images [domain. size ()] = empty;
        return true;
} /* mvmap::removenum */
 
template <class domelement, class imgelement>
inline bool mvmap<domelement,imgelement>::remove (const domelement &x)
{
        return removenum (domain. getnumber (x));
} /* mvmap::remove */
 
template <class domelement, class imgelement>
inline void mvmap<domelement,imgelement>::remove
        (const hashedset<domelement> &x)
{
        int_t n = x. size ();
        for (int_t i = 0; i < n; ++ i)
                remove (x [i]);
        return;
} /* mvmap::remove */
 
template <class domelement, class imgelement>
inline void mvmap<domelement,imgelement>::swap
        (mvmap<domelement,imgelement> &other)
{
        domain. swap (other. domain);
        images. swap (other. images);
        return;
} /* mvmap::swap */
 
// --------------------------------------------------
 
template <class domelement, class imgelement>
hashedset<imgelement> &retrieveimage (const mvmap<domelement,imgelement> &m,
        hashedset<imgelement> &img)
{
        int_t n = m. getdomain (). size ();
        for (int_t i = 0; i < n; ++ i)
                img. add (m (i));
        return img;
} /* retrieveimage */
 
template <class domelement, class imgelement>
hashedset<imgelement> &creategraph (const mvmap<domelement,imgelement> &m,
        hashedset<imgelement> &graph)
{
        for (int_t i = 0; i < m. getdomain (). size (); ++ i)
        {
                const domelement &e = m. get (i);
                const hashedset<imgelement> &f = m (i);
                int_t n = f. size ();
                for (int_t j = 0; j < n; ++ j)
                        graph. add (e * f [j]);
        }
        return graph;
} /* creategraph */
 
// --------------------------------------------------
 
template <class domelement, class imgelement>
std::istream &readdomain (std::istream &in, hashedset<domelement> &dom,
        const mvmap<domelement,imgelement> &)
{
        ignorecomments (in);
        while (in. peek () != EOF)
        {
                domelement e;
                in >> e;
        //      if (!in)
        //              throw "Failed to read a domain element of a map.";
                dom. add (e);
 
                // read the map's arrow
                ignorecomments (in);
                while (in. peek () == '-')
                        in. get ();
                if (in. peek () == '>')
                        in. get ();
 
                ignorecomments (in);
                int closing = readparenthesis (in);
 
                ignorecomments (in);
                while (in. peek () != closing)
                {
                        imgelement junk;
                        in >> junk;
                //      if (!in)
                //              throw "Failed to read an image element.";
                        ignorecomments (in);
                        if (in. peek () == ',')
                        {
                                in. get ();
                                ignorecomments (in);
                        }
                }
 
                if (closing != EOF)
                        in. get ();
                ignorecomments (in);
        }
        return in;
} /* readdomain */
 
template <class domelement, class imgelement>
std::istream &readimage (std::istream &in, hashedset<imgelement> &img,
        const mvmap<domelement,imgelement> &)
{
        ignorecomments (in);
        while (in. peek () != EOF)
        {
                domelement e;
                in >> e;
        //      if (!in)
        //              throw "Failed to read a domain element of a map.";
 
                // read the map's arrow
                ignorecomments (in);
                while (in. peek () == '-')
                        in. get ();
                if (in. peek () == '>')
                        in. get ();
 
                ignorecomments (in);
                read (in, img, SMALL_SIZE);
 
                ignorecomments (in);
        }
        return in;
} /* readimage */
 
template <class domelement, class imgelement>
std::istream &readselective (std::istream &in, mvmap<domelement,imgelement> &m,
        const hashedset<domelement> &dom1, const hashedset<domelement> &dom2)
{
        if (dom1. empty () && dom2. empty ())
        {
                sout << "Warning: The domain of the map is empty.\n";
                return in;
        }
 
        ignorecomments (in);
        while (in. peek () != EOF)
        {
                domelement e;
                in >> e;
        //      if (!in)
        //              throw "Failed to read a domain element of a map.";
 
                // read the map's arrow
                ignorecomments (in);
                while (in. peek () == '-')
                        in. get ();
                if (in. peek () == '>')
                        in. get ();
 
                ignorecomments (in);
                if (dom1. check (e) || dom2. check (e))
                        read (in, m [e], SMALL_SIZE);
                else
                {
                        int closing = readparenthesis (in);
        
                        ignorecomments (in);
                        while (in. peek () != closing)
                        {
                                imgelement junk;
                                in >> junk;
                        //      if (!in)
                        //              throw "Failed to read an img elem.";
                                ignorecomments (in);
                                if (in. peek () == ',')
                                {
                                        in. get ();
                                        ignorecomments (in);
                                }
                        }
        
                        if (closing != EOF)
                                in. get ();
                }
                ignorecomments (in);
        }
        return in;
} /* readselective */
 
template <class domelement, class imgelement>
std::istream &readrestriction (std::istream &in,
        mvmap<domelement,imgelement> &m, const hashedset<domelement> &dom,
        const hashedset<imgelement> &img)
{
        if (dom. empty ())
        {
                sout << "Warning: The domain of the map is empty.\n";
                return in;
        }
 
        ignorecomments (in);
        while (in. peek () != EOF)
        {
                domelement e;
                in >> e;
        //      if (!in)
        //              throw "Failed to read a domain element of a map.";
 
                // read the map's arrow
                ignorecomments (in);
                while (in. peek () == '-')
                        in. get ();
                if (in. peek () == '>')
                        in. get ();
 
                ignorecomments (in);
                if (dom. check (e))
                {
                        hashedset<imgelement> &y = m [e];
                        hashedset<domelement> x;
                        read (in, x, SMALL_SIZE);
                        int_t n = x. size ();
                        for (int_t i = 0; i < n; ++ i)
                        {
                                if (img. check (x [i]))
                                        y. add (x [i]);
                        }
                }
                else
                {
                        int closing = readparenthesis (in);
        
                        ignorecomments (in);
                        while (in. peek () != closing)
                        {
                                imgelement junk;
                                in >> junk;
                        //      if (!in)
                        //              throw "Failed to read an img elem.";
                                ignorecomments (in);
                                if (in. peek () == ',')
                                {
                                        in. get ();
                                        ignorecomments (in);
                                }
                        }
        
                        if (closing != EOF)
                                in. get ();
                }
                ignorecomments (in);
        }
        return in;
} /* readrestriction */
 
template <class domelement, class imgelement>
inline std::istream &readselective (std::istream &in,
        mvmap<domelement,imgelement> &m, const hashedset<domelement> &dom)
{
        hashedset<domelement> empty;
        return readselective (in, m, dom, empty);
} /* readselective */
 
 
// --------------------------------------------------
 
template <class domelement, class imgelement>
std::ostream &operator << (std::ostream &out,
        const mvmap<domelement,imgelement> &m)
{
        int_t n = m. getdomain (). size ();
        for (int_t i = 0; i < n; ++ i)
        {
                out << m. get (i) << " -> ";
                write (out, m (i), SMALL_SIZE) << '\n';
        }
        return out;
} /* operator << */
 
template <class domelement, class imgelement>
std::istream &operator >> (std::istream &in, mvmap<domelement,imgelement> &m)
{
        ignorecomments (in);
        while (in. peek () != EOF)
        {
                domelement e;
                in >> e;
        //      if (!in)
        //              throw "Failed to read a domain element of a map.";
 
                // read the map's arrow
                ignorecomments (in);
                while (in. peek () == '-')
                        in. get ();
                if (in. peek () == '>')
                        in. get ();
 
                ignorecomments (in);
                read (in, m [e], SMALL_SIZE);
 
                ignorecomments (in);
        }
        return in;
} /* operator >> */
 
 
} // namespace homology
} // namespace chomp
 
#endif // _CHOMP_STRUCT_HASHSETS_H_