patternstore.h

Go to the documentation of this file.

#ifndef COLIBRIPATTERNSTORE_H
#define COLIBRIPATTERNSTORE_H

#include <string>
#include <iostream>
#include <ostream>
#include <istream>
#include <unordered_map>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <unordered_set>
#include <iomanip> // contains setprecision()
#include <exception>
#include <algorithm>
#include "common.h"
#include "pattern.h"
#include "datatypes.h"
#include "classdecoder.h"
#include "classencoder.h"

/***********************************************************************************/

typedef std::pair<IndexReference,PatternPointer> IndexPattern;
class IndexedCorpus {
    protected:
        unsigned char * corpus;
        unsigned int corpussize; //in bytes
        PatternPointer * patternpointer; //pattern pointer covering the whole corpus
        unsigned int totaltokens;
        std::map<uint32_t,unsigned char*> sentenceindex; //sentence pointers
    public:
        IndexedCorpus() {
            corpus = NULL;
            corpussize = 0;
            totaltokens = 0; //will be computed when queried
            patternpointer = NULL;
        };

        /*
         * Low-level constructor
         */
        IndexedCorpus(unsigned char * corpus, unsigned int corpussize) {
            this->corpus = corpus;
            this->corpussize = 0;
            totaltokens = 0; //will be computed when queried
            patternpointer = new PatternPointer(corpus,corpussize);
        }

        /*
         * Read an indexed corpus from stream. The stream must correspond to an
         * encoded corpus (*.colibri.dat)
         */
        IndexedCorpus(std::istream *in, bool debug = false);
        /*
         * Read an indexed corpus from file. The filename must correspond to an
         * encoded corpus (*.colibri.dat)
         */
        IndexedCorpus(std::string filename, bool debug = false);

        ~IndexedCorpus() { 
            if (corpus != NULL) delete[] corpus; 
            if (patternpointer != NULL) delete patternpointer; 
        }
        
        /*
         * Read an indexed corpus from stream. The stream must correspond to an
         * encoded corpus (*.colibri.dat)
         */
        void load(std::istream *in, bool debug = false);

        /*
         * Read an indexed corpus from file. The filename must correspond to an
         * encoded corpus (*.colibri.dat)
         */
        void load(std::string filename, bool debug = false);



        unsigned char * getpointer(const IndexReference & begin) const;

        PatternPointer getpattern(const IndexReference & begin, int length=1) const;

        PatternPointer getpattern() const {
            return *patternpointer;
        }
        unsigned char * beginpointer() const {
            return corpus;
        }
        unsigned int bytesize() const {
            return corpussize;
        }

        PatternPointer getsentence(int sentence) const; //returns sentence as a pattern pointer
        PatternPointer getsentence(unsigned char * sentencedata) const; //returns sentence as a pattern pointer
         
        std::vector<IndexReference> findpattern(const Pattern & pattern, uint32_t sentence = 0, int maxmatches=0); 
        void findpattern(std::vector<IndexReference> & result, const Pattern & pattern,  uint32_t sentence, const PatternPointer & sentencedata, int maxmatches=0);

        int sentencelength(int sentence) const;  
        int sentencelength(unsigned char * sentencebegin) const;  

        unsigned int sentences() const { return sentenceindex.size(); }  //returns the number of sentences (1-indexed)


        class iterator {
            public:
                typedef iterator self_type;
                typedef IndexPattern value_type;
                typedef IndexPattern & reference;
                typedef IndexPattern * pointer;
                typedef std::forward_iterator_tag iterator_category;
                typedef int difference_type;
                iterator(const self_type & ref) { //copy constructor
                    pairpointer = new std::pair<IndexReference,PatternPointer>(*ref.pairpointer);
                }
                iterator(pointer ptr) { 
                    pairpointer = new std::pair<IndexReference,PatternPointer>(*ptr);
                }
                iterator(IndexReference iref, PatternPointer pp) { 
                    pairpointer = new std::pair<IndexReference,PatternPointer>(iref, pp);
                }
                iterator(reference ref) { 
                    pairpointer = new std::pair<IndexReference,PatternPointer>(ref.first, ref.second);
                }
                iterator() { //default constructor, required for cython
                    pairpointer = NULL;
                }
                ~iterator() {
                    if (pairpointer != NULL) delete pairpointer;
                }
                self_type operator++() { 
                    next();
                    return *this; 
                } //prefix

                void next() {
                    ++(pairpointer->second);
                    if (*(pairpointer->second.data) == ClassDecoder::delimiterclass) {
                        //we never stop at delimiterclasses, iterate again:
                        pairpointer->first.sentence++;
                        pairpointer->first.token = 0;
                        ++(pairpointer->second);
                    } else {
                        pairpointer->first.token++; 
                    }
                    //Note: At the end of the data, the patternpointer is out of bounds, checking against end() should work fine though
                }
                self_type operator++(int junk) { self_type tmpiter = *this; next(); return *tmpiter; } //postfix
                reference operator*() { return *pairpointer; }
                pointer operator->()  { return pairpointer; }
                bool operator==(self_type rhs) { return pairpointer->first == rhs->first; }
                bool operator!=(self_type rhs) { return pairpointer->first != rhs->first; }
                void debug() {
                    std::cerr << (size_t) pairpointer << std::endl;
                }
            protected:
                pointer pairpointer;
        };
    
        /*
         * Returns the begin iterator over the corpus
         */
        iterator begin() { 
            IndexReference iref = IndexReference(1,0);
            PatternPointer p = getpattern(iref,1);
            return iterator(iref,p); 
        }
        //const_iterator begin() const { return data.begin(); }

        /*
         * Returns the end iterator of the corpus
         */
        iterator end() { 
            IndexReference iref = IndexReference(sentences() + 1,0);
            PatternPointer p = PatternPointer(corpus,corpussize+1); //will be an invalid pointer, should never be used though
            return iterator(iref,p); 
        }
        //const_iterator end() const { return data.end(); }

        iterator find(const IndexReference & ref) {
            try {
                PatternPointer p = getpattern(ref);
                return iterator(ref,p);
            } catch (KeyError &e) {
                return end();
            }
        }
        /*const_iterator find(const IndexReference & ref) const {
            return std::lower_bound(this->begin(), this->end(), IndexPattern(ref) ); //does binary search
        }*/
        
        bool has(const IndexReference & ref) const {
            return (getpointer(ref) != NULL);
        }

        size_t size() {
            if (totaltokens > 0) return totaltokens;
            totaltokens =  patternpointer->n();
            return totaltokens;
        } 

        bool empty() const { return (corpussize <= 1); }


        unsigned int operator [](const IndexReference & ref) { 
            try {
                PatternPointer pp = getpattern(ref);
                return bytestoint(pp.data);
            } catch (KeyError &e) {
                throw e;
            }
        } 




};


/************* Base abstract container for pattern storage  ********************/

class PatternStoreInterface {
    public:
        virtual bool has(const Pattern &) const =0;
        virtual bool has(const PatternPointer &) const =0;
        virtual size_t size() const =0; 
};

template<class ContainerType,class ReadWriteSizeType = uint64_t,class PatternType = Pattern> 
class PatternStore: public PatternStoreInterface {
    protected:
        unsigned char * corpusstart; //used only when PatternType=PatternPointer
        unsigned int corpussize;
        unsigned char classencodingversion;
        int patterntype;
    public:
        PatternStore<ContainerType,ReadWriteSizeType,PatternType>() {corpusstart = NULL; corpussize = 0; classencodingversion = 2; patterntype = PatternType::patterntype; };
        virtual ~PatternStore<ContainerType,ReadWriteSizeType,PatternType>() {};
    
        virtual void attachcorpus(unsigned char * corpusstart, unsigned int corpussize) {
            this->corpusstart = corpusstart;
            this->corpussize = corpussize;
        }
        virtual void attachcorpus(const IndexedCorpus & corpus) {
            this->corpusstart = corpus.beginpointer();
            this->corpussize = corpus.bytesize();
        }
        virtual void detachcorpus() {
            this->corpusstart = NULL;
            this->corpussize = 0;
        }
        unsigned char * getcorpus() const {
            return corpusstart;
        }
        unsigned int getcorpussize() const {
            return corpussize;
        }
        

        virtual void use_v1_format() { this->classencodingversion = 1; }

        virtual void insert(const PatternType & pattern)=0; //might be a noop in some implementations that require a value

        virtual bool has(const Pattern &) const =0;
        virtual bool has(const PatternPointer &) const =0;

        virtual bool erase(const PatternType &) =0;
        
        virtual size_t size() const =0; 
        virtual void reserve(size_t) =0; //might be a noop in some implementations
        
        
        typedef typename ContainerType::iterator iterator;
        typedef typename ContainerType::const_iterator const_iterator;

        virtual typename ContainerType::iterator begin()=0;
        virtual typename ContainerType::iterator end()=0;
        virtual typename ContainerType::iterator find(const Pattern & pattern)=0;
        virtual typename ContainerType::iterator find(const PatternPointer & pattern)=0;
        
        virtual void write(std::ostream * out)=0;
        //virtual void read(std::istream * in, int MINTOKENS)=0;

        virtual PatternStoreInterface * getstoreinterface() {
            return (PatternStoreInterface*) this;
        }
};


/************* Abstract datatype for all kinds of maps ********************/


template<class ContainerType, class ValueType, class ValueHandler,class ReadWriteSizeType = uint32_t,class PatternType=Pattern>
class PatternMapStore: public PatternStore<ContainerType,ReadWriteSizeType,PatternType> { 
     protected:
        ValueHandler valuehandler;
     public:
        PatternMapStore<ContainerType,ValueType,ValueHandler,ReadWriteSizeType,PatternType>(): PatternStore<ContainerType,ReadWriteSizeType,PatternType>() { };
        virtual ~PatternMapStore<ContainerType,ValueType,ValueHandler,ReadWriteSizeType,PatternType>() {};


        virtual void insert(const PatternType & pattern, ValueType & value)=0;

        virtual bool has(const Pattern &) const =0;
        virtual bool has(const PatternPointer &) const =0;

        virtual bool erase(const PatternType &) =0;

        
        virtual size_t size() const =0; 
        virtual void reserve(size_t) =0;
        
        
        virtual ValueType & operator [](const Pattern & pattern)=0;
        virtual ValueType & operator [](const PatternPointer & pattern)=0;
        
        typedef typename ContainerType::iterator iterator;
        typedef typename ContainerType::const_iterator const_iterator;

        virtual typename ContainerType::iterator begin()=0;
        virtual typename ContainerType::iterator end()=0;
        virtual typename ContainerType::iterator find(const Pattern & pattern)=0;
        virtual typename ContainerType::iterator find(const PatternPointer & pattern)=0;

        virtual void write(std::ostream * out) {
            ReadWriteSizeType s = (ReadWriteSizeType) size();
            out->write( (char*) &s, sizeof(ReadWriteSizeType));
            for (iterator iter = this->begin(); iter != this->end(); iter++) {
                PatternType p = iter->first;
                p.write(out, this->corpusstart);
                this->valuehandler.write(out, iter->second);
            }
        }
        
        virtual void write(std::string filename) {
            std::ofstream * out = new std::ofstream(filename.c_str());
            this->write(out);
            out->close();
            delete out;
        }


        template<class ReadValueType=ValueType, class ReadValueHandler=ValueHandler,class ReadPatternType=PatternType>
        void read(std::istream * in, int MINTOKENS=0, int MINLENGTH=0, int MAXLENGTH=999999, PatternStoreInterface * constrainstore = NULL, bool DONGRAMS=true, bool DOSKIPGRAMS=true, bool DOFLEXGRAMS=true, bool DORESET=false,  bool DEBUG=false) {
            ReadValueHandler readvaluehandler = ReadValueHandler();
            ReadWriteSizeType s; //read size:
            ReadPatternType p;
            in->read( (char*) &s, sizeof(ReadWriteSizeType));
            reserve(s);
            if (DEBUG) std::cerr << "Reading " << s << " patterns, classencodingversion=" << (int) this->classencodingversion << ", @corpusstart=" << (size_t) this->corpusstart << std::endl;
            if (MINTOKENS == -1) MINTOKENS = 0;
            for (ReadWriteSizeType i = 0; i < s; i++) {
                try {
                    p = ReadPatternType(in, false, this->classencodingversion, this->corpusstart, DEBUG);
                } catch (std::exception &e) {
                    std::cerr << "ERROR: Exception occurred at pattern " << (i+1) << " of " << s << std::endl;
                    throw InternalError();
                }
                if (!DONGRAMS || !DOSKIPGRAMS || !DOFLEXGRAMS) {
                    const PatternCategory c = p.category();
                    if ((!DONGRAMS && c == NGRAM) || (!DOSKIPGRAMS && c == SKIPGRAM) || (!DOFLEXGRAMS && c == FLEXGRAM)) continue;
                }
                const int n = p.size();
                if (DEBUG) std::cerr << "Read pattern #" << (i+1) << ", size=" << n << ", valuehandler=" << readvaluehandler.id() << ", classencodingversion="<<(int)this->classencodingversion;
                ReadValueType readvalue;
                readvaluehandler.read(in, readvalue);
                if (n >= MINLENGTH && n <= MAXLENGTH)  {
                    if ((readvaluehandler.count(readvalue) >= (unsigned int) MINTOKENS) && ((constrainstore == NULL) || (constrainstore->has(p)))) {
                            ValueType * convertedvalue = NULL;
                            if (DORESET) {
                                convertedvalue = new ValueType();
                            } else {
                                readvaluehandler.convertto(&readvalue, convertedvalue); 
                                if (DEBUG) std::cerr << "...converted";
                                if (convertedvalue == NULL) {
                                    if (DEBUG) std::cerr << std::endl;
                                    std::cerr << "ERROR: Converted value yielded NULL at pattern #" << (i+1) << ", size=" << n << ", valuehandler=" << readvaluehandler.id() <<std::endl;
                                    throw InternalError();
                                }
                            }
                            if (DEBUG) std::cerr << "...adding";
                            this->insert(p,*convertedvalue);
                            if ((convertedvalue != NULL) && ((void*) convertedvalue != (void*) &readvalue)) delete convertedvalue;
                    } else if (DEBUG) {
                        if (readvaluehandler.count(readvalue) < (unsigned int) MINTOKENS) {
                            std::cerr << "...skipping because of occurrence (" << readvaluehandler.count(readvalue) << " below " << MINTOKENS;    
                        } else {
                            std::cerr << "...skipping because of constraints";    
                        }
                    }
                } else if (DEBUG) {
                  std::cerr << "...skipping because of length";
                }
                if (DEBUG) std::cerr << std::endl;
            }
        }

        void read(std::string filename,int MINTOKENS=0, int MINLENGTH=0, int MAXLENGTH=999999, PatternStoreInterface * constrainstore = NULL, bool DONGRAMS=true, bool DOSKIPGRAMS=true, bool DOFLEXGRAMS=true, bool DORESET = false, bool DEBUG=false) { //no templates for this one, easier on python/cython
            std::ifstream * in = new std::ifstream(filename.c_str());
            this->read<ValueType,ValueHandler>(in,MINTOKENS,MINLENGTH,MAXLENGTH,constrainstore,DONGRAMS,DOSKIPGRAMS,DOFLEXGRAMS, DORESET, DEBUG);
            in->close();
            delete in;
        }

};


/************* Specific STL-like containers for patterns ********************/



typedef std::unordered_set<Pattern> t_patternset;

template<class ReadWriteSizeType = uint32_t>
class PatternSet: public PatternStore<t_patternset,ReadWriteSizeType,Pattern> {
    protected:
        t_patternset data;
    public:

        PatternSet<ReadWriteSizeType>(): PatternStore<t_patternset,ReadWriteSizeType>() {};


        PatternSet<ReadWriteSizeType>(const ClassDecoder & classdecoder): PatternStore<t_patternset,ReadWriteSizeType>() {
            for (ClassDecoder::const_iterator iter = classdecoder.begin(); iter != classdecoder.end(); iter++) {
                const int cls = iter->first;
                int length; //will be set by inttobytes
                unsigned char * buffer = inttobytes(cls, length);
                data.insert( Pattern(buffer, length) );
                delete buffer;
            }
        }

        PatternSet<ReadWriteSizeType>(const ClassEncoder & classencoder): PatternStore<t_patternset,ReadWriteSizeType>() {
            for (ClassEncoder::const_iterator iter = classencoder.begin(); iter != classencoder.end(); iter++) {
                const int cls = iter->second;
                int length; //will be set by inttobytes
                unsigned char * buffer = inttobytes(cls, length);
                data.insert( Pattern(buffer, length) );
                delete buffer;
            }
        }

        virtual ~PatternSet<ReadWriteSizeType>() {};

        void insert(const Pattern & pattern) {
            data.insert(pattern);
        }

        bool has(const Pattern & pattern) const { return data.count(pattern); }

        bool has(const PatternPointer & pattern) const { return data.count(pattern); }

        size_t size() const { return data.size(); } 
        void reserve(size_t s) { data.reserve(s); }

        typedef t_patternset::iterator iterator;
        typedef t_patternset::const_iterator const_iterator;
        
        iterator begin() { return data.begin(); }
        const_iterator begin() const { return data.begin(); }

        iterator end() { return data.end(); }
        const_iterator end() const { return data.end(); }

        iterator find(const Pattern & pattern) { return data.find(pattern); }
        const_iterator find(const Pattern & pattern) const { return data.find(pattern); }

        iterator find(const PatternPointer & pattern) { return data.find(pattern); }
        const_iterator find(const PatternPointer & pattern) const { return data.find(pattern); }

        bool erase(const Pattern & pattern) { return data.erase(pattern); }
        iterator erase(const_iterator position) { return data.erase(position); }


        void write(std::ostream * out) {
            ReadWriteSizeType s = (ReadWriteSizeType) size();
            out->write( (char*) &s, sizeof(ReadWriteSizeType));
            for (iterator iter = begin(); iter != end(); iter++) {
                Pattern p = *iter;
                p.write(out, this->corpusstart);
            }
        }

        void read(std::istream * in, int MINLENGTH=0, int MAXLENGTH=999999, PatternStoreInterface * constrainstore = NULL, bool DONGRAMS=true, bool DOSKIPGRAMS=true, bool DOFLEXGRAMS=true) {
            ReadWriteSizeType s; //read size:
            in->read( (char*) &s, sizeof(ReadWriteSizeType));
            reserve(s);
            for (unsigned int i = 0; i < s; i++) {
                Pattern p = Pattern(in, false, this->classencodingversion);
                if (!DONGRAMS || !DOSKIPGRAMS || !DOFLEXGRAMS) {
                    const PatternCategory c = p.category();
                    if ((!DONGRAMS && c == NGRAM) || (!DOSKIPGRAMS && c == SKIPGRAM) || (!DOFLEXGRAMS && c == FLEXGRAM)) continue;
                }
                const int n = p.size();
                if ((n >= MINLENGTH && n <= MAXLENGTH) && ((constrainstore == NULL) || (constrainstore->has(p)))) {
                    insert(p);
                }
            }
        }

        template<class ReadValueType, class ReadValueHandler=BaseValueHandler<ReadValueType>>
        void readmap(std::istream * in, int MINTOKENS=0, int MINLENGTH=0, int MAXLENGTH=999999, PatternStoreInterface * constrainstore = NULL, bool DONGRAMS=true, bool DOSKIPGRAMS=true, bool DOFLEXGRAMS=true) {
            ReadValueHandler readvaluehandler = ReadValueHandler();
            ReadWriteSizeType s; //read size:
            in->read( (char*) &s, sizeof(ReadWriteSizeType));
            reserve(s);
            //std::cerr << "Reading " << (int) s << " patterns" << std::endl;
            for (ReadWriteSizeType i = 0; i < s; i++) {
                Pattern p;
                try {
                    p = Pattern(in, false, this->classencodingversion);
                } catch (std::exception &e) {
                    std::cerr << "ERROR: Exception occurred at pattern " << (i+1) << " of " << s << std::endl;
                    throw InternalError();
                }
                if (!DONGRAMS || !DOSKIPGRAMS || !DOFLEXGRAMS) {
                    const PatternCategory c = p.category();
                    if ((!DONGRAMS && c == NGRAM) || (!DOSKIPGRAMS && c == SKIPGRAM) || (!DOFLEXGRAMS && c == FLEXGRAM)) continue;
                }
                const int n = p.size();
                ReadValueType readvalue;
                //std::cerr << "Read pattern: " << std::endl;
                readvaluehandler.read(in, readvalue);
                if (n >= MINLENGTH && n <= MAXLENGTH)  {
                    if ((readvaluehandler.count(readvalue) >= (unsigned int) MINTOKENS) && ((constrainstore == NULL) || (constrainstore->has(p)))) {
                        this->insert(p);
                    }
                }
            }
        }
};


typedef std::set<Pattern> t_hashorderedpatternset;


template<class ReadWriteSizeType = uint64_t>
class HashOrderedPatternSet: public PatternStore<t_hashorderedpatternset,ReadWriteSizeType> {
    protected:
        t_hashorderedpatternset data;
    public:

        HashOrderedPatternSet<ReadWriteSizeType>(): PatternStore<t_hashorderedpatternset,ReadWriteSizeType>() {};
        virtual ~HashOrderedPatternSet<ReadWriteSizeType>();

        void insert(const Pattern pattern) {
            data.insert(pattern);
        }

        bool has(const Pattern & pattern) const { return data.count(pattern); }
        bool has(const PatternPointer & pattern) const { return data.count(pattern); }
        size_t size() const { return data.size(); } 
        void reserve(size_t s) {} //noop

        typedef t_hashorderedpatternset::iterator iterator;
        typedef t_hashorderedpatternset::const_iterator const_iterator;
        
        iterator begin() { return data.begin(); }
        const_iterator begin() const { return data.begin(); }

        iterator end() { return data.end(); }
        const_iterator end() const { return data.end(); }

        iterator find(const Pattern & pattern) { return data.find(pattern); }
        const_iterator find(const Pattern & pattern) const { return data.find(pattern); }
        iterator find(const PatternPointer & pattern) { return data.find(pattern); }
        const_iterator find(const PatternPointer & pattern) const { return data.find(pattern); }

        bool erase(const Pattern & pattern) { return data.erase(pattern); }
        iterator erase(const_iterator position) { return data.erase(position); }

        
        void write(std::ostream * out) {
            ReadWriteSizeType s = (ReadWriteSizeType) size();
            out->write( (char*) &s, sizeof(ReadWriteSizeType));
            for (iterator iter = begin(); iter != end(); iter++) {
                Pattern p = *iter;
                p.write(out, this->corpusstart);
            }
        }

        void read(std::istream * in, int MINLENGTH=0, int MAXLENGTH=999999, bool DONGRAMS=true, bool DOSKIPGRAMS=true, bool DOFLEXGRAMS=true) {
            ReadWriteSizeType s; //read size:
            in->read( (char*) &s, sizeof(ReadWriteSizeType));
            reserve(s);
            for (unsigned int i = 0; i < s; i++) {
                Pattern p = Pattern(in, false, this->classencodingversion);
                if (!DONGRAMS || !DOSKIPGRAMS || !DOFLEXGRAMS) {
                    const PatternCategory c = p.category();
                    if ((!DONGRAMS && c == NGRAM) || (!DOSKIPGRAMS && c == SKIPGRAM) || (!DOFLEXGRAMS && c == FLEXGRAM)) continue;
                }
                const int n = p.size();
                if (n >= MINLENGTH && n <= MAXLENGTH)  {
                    insert(p);
                }
            }
        }

};


template<class ValueType, class ValueHandler = BaseValueHandler<ValueType>, class ReadWriteSizeType = uint64_t>
class PatternMap: public PatternMapStore<std::unordered_map<Pattern,ValueType>,ValueType,ValueHandler,ReadWriteSizeType,Pattern> {
    protected:
        std::unordered_map<Pattern, ValueType> data;
    public:
        //PatternMap(): PatternMapStore<std::unordered_map<const Pattern, ValueType>,ValueType,ValueHandler,ReadWriteSizeType>() {};
        PatternMap<ValueType,ValueHandler,ReadWriteSizeType>() {};

        void insert(const Pattern & pattern, ValueType & value) { 
            data[pattern] = value;
        }

        void insert(const Pattern & pattern) {  data[pattern] = ValueType(); } //singular insert required by PatternStore, implies 'default' ValueType, usually 0
        
        bool has(const Pattern & pattern) const { 
            return data.count(pattern);
        }
        bool has(const PatternPointer & pattern) const { return data.count(pattern); }

        size_t size() const { return data.size(); } 
        void reserve(size_t s) { data.reserve(s); }


        ValueType& operator [](const Pattern & pattern) { return data[pattern]; } 
        ValueType& operator [](const PatternPointer & pattern) { return data[pattern]; } 
        
        typedef typename std::unordered_map<Pattern,ValueType>::iterator iterator;
        typedef typename std::unordered_map<Pattern,ValueType>::const_iterator const_iterator;
        
        iterator begin() { return data.begin(); }
        const_iterator begin() const { return data.begin(); }

        iterator end() { return data.end(); }
        const_iterator end() const { return data.end(); }

        iterator find(const Pattern & pattern) { return data.find(pattern); }
        const_iterator find(const Pattern & pattern) const { return data.find(pattern); }
        iterator find(const PatternPointer & pattern) { return data.find(pattern); }
        const_iterator find(const PatternPointer & pattern) const { return data.find(pattern); }
        
        bool erase(const Pattern & pattern) { return data.erase(pattern); }
        iterator erase(const_iterator position) { return data.erase(position); }

};


template<class ValueType, class ValueHandler = BaseValueHandler<ValueType>, class ReadWriteSizeType = uint64_t>
class PatternPointerMap: public PatternMapStore<std::unordered_map<PatternPointer,ValueType>,ValueType,ValueHandler,ReadWriteSizeType,PatternPointer> {
    protected:
        std::unordered_map<PatternPointer, ValueType> data;
    public:
        IndexedCorpus * corpus;
        //PatternMap(): PatternMapStore<std::unordered_map<const Pattern, ValueType>,ValueType,ValueHandler,ReadWriteSizeType>() {};
        PatternPointerMap<ValueType,ValueHandler,ReadWriteSizeType>(IndexedCorpus * corpus) {
            this->corpus = corpus;
        };

        PatternPointerMap<ValueType,ValueHandler,ReadWriteSizeType>() { corpus = NULL; }


        void insert(const PatternPointer & pattern, ValueType & value) { 
            data[pattern] = value;
        }

        void insert(const PatternPointer & pattern) {  data[pattern] = ValueType(); } //singular insert required by PatternStore, implies 'default' ValueType, usually 0
        
        bool has(const Pattern & pattern) const { 
            return data.count(pattern);
        }
        bool has(const PatternPointer & pattern) const { return data.count(pattern); }

        size_t size() const { return data.size(); } 
        void reserve(size_t s) { data.reserve(s); }


        ValueType& operator [](const Pattern & pattern) { return data[pattern]; } 
        ValueType& operator [](const PatternPointer & pattern) { return data[pattern]; } 
        
        typedef typename std::unordered_map<PatternPointer,ValueType>::iterator iterator;
        typedef typename std::unordered_map<PatternPointer,ValueType>::const_iterator const_iterator;
        
        iterator begin() { return data.begin(); }
        const_iterator begin() const { return data.begin(); }

        iterator end() { return data.end(); }
        const_iterator end() const { return data.end(); }

        iterator find(const Pattern & pattern) { 
            PatternPointer pp = pattern.getpointer();
            return data.find(pp);
        }
        //const_iterator find(const Pattern & pattern) const { return data.find(pattern); }

        iterator find(const PatternPointer & pattern) { return data.find(pattern); }
        const_iterator find(const PatternPointer & pattern) const { return data.find(pattern); }
        
        bool erase(const PatternPointer & pattern) { return data.erase(pattern); }
        iterator erase(const_iterator position) { return data.erase(position); }
};

template<class ValueType, class ValueHandler = BaseValueHandler<ValueType>, class ReadWriteSizeType = uint64_t>
class OrderedPatternPointerMap: public PatternMapStore<std::map<PatternPointer,ValueType>,ValueType,ValueHandler,ReadWriteSizeType,PatternPointer> {
    protected:
        std::map<PatternPointer, ValueType> data;
    public:
        IndexedCorpus * corpus;
        //PatternMap(): PatternMapStore<std::unordered_map<const Pattern, ValueType>,ValueType,ValueHandler,ReadWriteSizeType>() {};
        OrderedPatternPointerMap<ValueType,ValueHandler,ReadWriteSizeType>(IndexedCorpus * corpus) {
            this->corpus = corpus;
        };

        OrderedPatternPointerMap<ValueType,ValueHandler,ReadWriteSizeType>() { corpus = NULL; }


        void insert(const PatternPointer & pattern, ValueType & value) { 
            data[pattern] = value;
        }

        void insert(const PatternPointer & pattern) {  data[pattern] = ValueType(); } //singular insert required by PatternStore, implies 'default' ValueType, usually 0
        
        bool has(const Pattern & pattern) const { 
            return data.count(pattern);
        }
        bool has(const PatternPointer & pattern) const { return data.count(pattern); }

        size_t size() const { return data.size(); } 
        void reserve(size_t s) { } //noop


        ValueType& operator [](const Pattern & pattern) { return data[pattern]; } 
        ValueType& operator [](const PatternPointer & pattern) { return data[pattern]; } 
        
        typedef typename std::map<PatternPointer,ValueType>::iterator iterator;
        typedef typename std::map<PatternPointer,ValueType>::const_iterator const_iterator;
        
        iterator begin() { return data.begin(); }
        const_iterator begin() const { return data.begin(); }

        iterator end() { return data.end(); }
        const_iterator end() const { return data.end(); }

        iterator find(const Pattern & pattern) { 
            PatternPointer pp = pattern.getpointer();
            return data.find(pp);
        }
        //const_iterator find(const Pattern & pattern) const { return data.find(pattern); }

        iterator find(const PatternPointer & pattern) { return data.find(pattern); }
        const_iterator find(const PatternPointer & pattern) const { return data.find(pattern); }
        
        bool erase(const PatternPointer & pattern) { return data.erase(pattern); }
        iterator erase(const_iterator position) { return data.erase(position); }
};

template<class ValueType,class ValueHandler = BaseValueHandler<ValueType>,class ReadWriteSizeType = uint64_t>
class HashOrderedPatternMap: public PatternMapStore<std::map<const Pattern,ValueType>,ValueType,ValueHandler,ReadWriteSizeType,Pattern> {
    protected:
        std::map<const Pattern, ValueType> data;
    public:
        HashOrderedPatternMap<ValueType,ValueHandler,ReadWriteSizeType>(): PatternMapStore<std::map<const Pattern, ValueType>,ValueType,ValueHandler,ReadWriteSizeType>() {};
        virtual ~HashOrderedPatternMap<ValueType,ValueHandler,ReadWriteSizeType>() {};

        void insert(const Pattern & pattern, ValueType & value) { 
            data[pattern] = value;
        }

        void insert(const Pattern & pattern) {  data[pattern] = ValueType(); } //singular insert required by PatternStore, implies 'default' ValueType

        bool has(const Pattern & pattern) const { return data.count(pattern); }
        bool has(const PatternPointer & pattern) const { return data.count(pattern); }

        size_t size() const { return data.size(); } 
        void reserve(size_t s) {} //noop

        ValueType& operator [](const Pattern & pattern) { return data[pattern]; } 
        ValueType& operator [](const PatternPointer & pattern) { return data[pattern]; } 
        
        typedef typename std::map<const Pattern,ValueType>::iterator iterator;
        typedef typename std::map<const Pattern,ValueType>::const_iterator const_iterator;
        
        iterator begin() { return data.begin(); }
        const_iterator begin() const { return data.begin(); }

        iterator end() { return data.end(); }
        const_iterator end() const { return data.end(); }

        iterator find(const Pattern & pattern) { return data.find(pattern); }
        const_iterator find(const Pattern & pattern) const { return data.find(pattern); }
        iterator find(const PatternPointer & pattern) { return data.find(pattern); }
        const_iterator find(const PatternPointer & pattern) const { return data.find(pattern); }

        bool erase(const Pattern & pattern) { return data.erase(pattern); }
        iterator erase(const_iterator position) { return data.erase(position); }
        

};


template<class T,size_t N,int countindex = 0>
class ArrayValueHandler: public AbstractValueHandler<T> {
   public:
    const static bool indexed = false;
    virtual std::string id() { return "ArrayValueHandler"; }
    void read(std::istream * in, std::array<T,N> & a) {
        for (int i = 0; i < N; i++) {
            T v;
            in->read( (char*) &v, sizeof(T)); 
            a[i] = v;
        }
    }
    void write(std::ostream * out, std::array<T,N> & a) {
        for (int i = 0; i < N; i++) {
            T v = a[i];
            out->write( (char*) &v, sizeof(T)); 
        }
    }
    std::string tostring(std::array<T,N> & a) {
        std::string s;
        for (int i = 0; i < N; i++) {
            T v = a[i];
            if (!s.empty()) s += " ";
            s += " " + tostring(a[i]);
        }
        return s;
    }
    unsigned int count(std::array<T,N> & a) const {
        return (int) a[countindex];
    }
    void add(std::array<T,N> * value, const IndexReference & ref ) const {
        (*value)[countindex] += 1;
    }
};


template<class PatternStoreType>
class PatternStoreValueHandler: public AbstractValueHandler<PatternStoreType> {
  public:
    const static bool indexed = false;
    virtual std::string id() { return "PatternStoreValueHandler"; }
    void read(std::istream * in,  PatternStoreType & value) {
        value.read(in);
    }
    void write(std::ostream * out,  PatternStoreType & value) {
        value.write(out);
    }
    virtual std::string tostring(  PatternStoreType & value) {
        std::cerr << "PatternStoreValueHandler::tostring() is not supported" << std::endl;
        throw InternalError();
    }
    unsigned int count( PatternStoreType & value) const {
        return value.size();
    }
    void add( PatternStoreType * value, const IndexReference & ref ) const {
        std::cerr << "PatternStoreValueHandler::add() is not supported" << std::endl;
        throw InternalError();
    }
};

template<class ValueType,class ValueHandler=BaseValueHandler<ValueType>, class NestedSizeType = uint16_t >
class AlignedPatternMap: public PatternMap< PatternMap<ValueType,ValueHandler,NestedSizeType>,PatternStoreValueHandler<PatternMap<ValueType,ValueHandler,NestedSizeType>>, uint64_t > {
    public:
        typedef PatternMap<ValueType,ValueHandler,NestedSizeType> valuetype;
        typedef typename PatternMap< PatternMap<ValueType,ValueHandler,NestedSizeType>,PatternStoreValueHandler<PatternMap<ValueType,ValueHandler,NestedSizeType>>, uint64_t >::iterator iterator;
        typedef typename PatternMap< PatternMap<ValueType,ValueHandler,NestedSizeType>,PatternStoreValueHandler<PatternMap<ValueType,ValueHandler,NestedSizeType>>, uint64_t >::const_iterator const_iterator;

};


//TODO: Implement a real Trie, conserving more memory
#endif