hashsets.h

Go to the documentation of this file.

// Copyright (C) 1997-2010 by Pawel Pilarczyk.
//
// This file is part of the Homology Library.  This library 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 2 of the License, or (at your option) any later version.
//
// This library 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, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// Started in January 2002. Last revision: May 24, 2010.


#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 <cstdlib>
#include <ctime>
#include <iostream>

namespace chomp {
namespace homology {


// class templates defined within this header file (in this order):
template <class element>
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 << */


// --------------------------------------------------
// ------------------- hashed set -------------------
// --------------------------------------------------

template <class element>
class hashedset
{
public:
        typedef element value_type;

        explicit hashedset (int_t initialsize = 0, int bequiet = 1);

        hashedset (const hashedset<element> &s);

        hashedset &operator = (const hashedset<element> &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> &add (const hashedset<element> &s);

        hashedset<element> &remove (const hashedset<element> &s);

        int_t size () const;

        bool empty () const;

        void swap (hashedset<element> &other);

        bool operator == (const hashedset<element> &other) const;

        void intersection (const hashedset<element> &s1,
                const hashedset<element> &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>
const int_t hashedset<element>::InitHashSize (137);

template <class element>
const int_t hashedset<element>::InitTabSize (30);

template <class element>
const int_t hashedset<element>::StartHashingSize (30);

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

template <class element>
hashedset<element>::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>::rounduptoprime (hashsize);
        if (bequiet)
                stat = NULL;
        else
                stat = new hashstat;
        return;
} /* hashedset<element>::hashedset */

template <class element>
hashedset<element>::hashedset (const hashedset<element> &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>::hashedset */

template <class element>
hashedset<element> &hashedset<element>::operator =
        (const hashedset<element> &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>::operator = */

template <class element>
hashedset<element>::~hashedset ()
{
        if (!stat)
                return;
        sout << "  " << *stat << '\n';
        delete stat;
        stat = NULL;
        return;
} /* hashedset<element>::~hashedset */

template <class element>
int_t hashedset<element>::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>::getnumber */

template <class element>
inline bool hashedset<element>::checknum (int_t n) const
{
        return ((n >= 0) && (n < nelem));
} /* hashedset<element>::checknum */

template <class element>
inline bool hashedset<element>::check (const element &e) const
{
        return (getnumber (e) >= 0);
} /* hashedset<element>::check */


template <class element>
inline const element &hashedset<element>::get (int_t n) const
{
        if ((n < 0) || (n >= nelem))
                throw "Trying to get an element out of range.";
        return tab (n);
} /* hashedset<element>::get */

template <class element>
inline const element &hashedset<element>::operator [] (int_t n) const
{
        return get (n);
} /* hashedset<element>::operator [] */

template <class element>
inline const element &hashedset<element>::front () const
{
        return get (nelem - 1);
} /* hashedset<element>::front */

template <class element>
inline const element &hashedset<element>::top () const
{
        return get (nelem - 1);
} /* hashedset<element>::top */

template <class element>
int_t hashedset<element>::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>::add */

template <class element>
inline int_t hashedset<element>::push (const element &e)
{
        return add (e);
} /* hashedset<element>::push */

template <class element>
inline int_t hashedset<element>::push_back (const element &e)
{
        return add (e);
} /* hashedset<element>::push_back */

template <class element>
int hashedset<element>::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>::remove */

template <class element>
inline int hashedset<element>::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>::removenum */

template <class element>
inline int_t hashedset<element>::pop ()
{
        if (!nelem)
                throw "Trying to remove an element from an empty set.";
        return removenum (nelem - 1);
} /* hashedset<element>::pop */

template <class element>
hashedset<element> &hashedset<element>::add (const hashedset<element> &s)
{
        int_t n = s. size ();
        for (int_t i = 0; i < n; ++ i)
                add (s [i]);
        return *this;
} /* hashedset<element>::add */

template <class element>
hashedset<element> &hashedset<element>::remove (const hashedset<element> &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>::remove */

template <class element>
inline bool hashedset<element>::empty () const
{
        return !nelem;
} /* hashedset<element>::empty */

template <class element>
inline int_t hashedset<element>::size () const
{
        return nelem;
} /* hashedset<element>::size */

template <class element>
inline void hashedset<element>::swap (hashedset<element> &other)
{
        my_swap (stat, other. stat);
        my_swap (nelem, other. nelem);
        tab. swap (other. tab);
        my_swap (hashing, other. hashing);
        my_swap (hashsize, other. hashsize);
        my_swap (hashcleared, other. hashcleared);
        hashtable. swap (other. hashtable);
        return;
} /* hashedset<element>::swap */

template <class element>
inline bool hashedset<element>::operator ==
        (const hashedset<element> &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>::swap */

template <class element>
inline void hashedset<element>::intersection (const hashedset<element> &s1,
        const hashedset<element> &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>::intersection */

template <class element>
int_t hashedset<element>::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>::hashfind */

template <class element>
void hashedset<element>::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>::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>::rehash */

template <class element>
inline bool hashedset<element>::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>::numberisprime */

template <class element>
int_t hashedset<element>::rounduptoprime (int_t n)
{
        while (!hashedset<element>::numberisprime (n))
                ++ n;

        return n;
} /* hashedset<element>::rounduptoprime */


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

#define SMALL_SIZE true

#define LARGE_SIZE false

template <class stream, class element>
stream &write (stream &out, const hashedset<element> &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>
std::ostream &operator << (std::ostream &out, const hashedset<element> &s)
{
        return write (out, s, LARGE_SIZE);
} /* operator << */

template <class stream, class element>
stream &read (stream &in, hashedset<element> &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>
std::istream &operator >> (std::istream &in, hashedset<element> &s)
{
        return read (in, s, LARGE_SIZE);
} /* operator >> */

template <class element>
inline hashedset<element> &operator += (hashedset<element> &s,
        const hashedset<element> &u)
{
        s. add (u);
        return s;
} /* operator += */

template <class element>
inline hashedset<element> &operator -= (hashedset<element> &s,
        const hashedset<element> &u)
{
        s. remove (u);
        return s;
} /* operator -= */

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

inline int_t hashkey1 (const unsigned long &number)
{
        return static_cast<int_t> (number);
} /* hashkey1 */

inline int_t hashkey2 (const unsigned long &number)
{
        return static_cast<int_t> (number ^ 0xFA5A75A7ul) << 8;
} /* hashkey2 */

#define DEFHASHKEYS(type) \
inline int_t hashkey1 (const type &number) \
{ return hashkey1 (static_cast<const unsigned long> (number)); } \
inline int_t hashkey2 (const type &number) \
{ return hashkey2 (static_cast<const unsigned long> (number)); }

DEFHASHKEYS(unsigned int)
DEFHASHKEYS(signed int)
//DEFHASHKEYS(unsigned long)
DEFHASHKEYS(signed long)
DEFHASHKEYS(unsigned short)
DEFHASHKEYS(signed short)
DEFHASHKEYS(unsigned char)
DEFHASHKEYS(signed char)

#undef DEFHASHKEYS

template <class T>
inline int_t hashkey1 (const T &x)
{
        return x. hashkey1 ();
}

template <class T>
inline int_t hashkey2 (const T &x)
{
        return x. hashkey2 ();
}


// --------------------------------------------------
// ---------------- 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_