/*************************************************************************
                           intl_finder  -  description
                             -------------------
    début                : 5 oct. 2012
    copyright            : (C) 2012 par tcantenot
*************************************************************************/

//---------- Interface de la classe <intl_finder> (fichier intl_finder.h) ------
#ifndef __INTL_FINDER_H__
#define __INTL_FINDER_H__

//--------------------------------------------------- Interfaces utilisées

#include <iostream>

#include "rb_tree.h"
#include "list.h"

namespace tp_cpp_1 {
    //------------------------------------------------------------------ Types

    typedef unsigned long long int size_t;

    template<class T>
    struct free {
        void operator()(T * & __e) {
            delete __e;
        }
    };

    template<class T>
    struct show {
        void operator()(T const & __e) const {
            std::cout << __e;
        }
    };

    struct hash_char {
        size_t operator()(char __c) const {
            return static_cast<size_t>(__c + 128);
        }
    };

    struct inv_hash_char {
        char operator()(size_t __s) {
            return static_cast<char>(__s - 128);
        }
    };

    //------------------------------------------------------------------------
    // Rôle de la classe <intl_finder>
    //
    //
    //------------------------------------------------------------------------
    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End = T(0)>
    class intl_finder {
    //----------------------------------------------------------------- PUBLIC

    public:
    //----------------------------------------------------- Méthodes publiques
        void Display(size_t __source) const;
        // Mode d'emploi :
        //
        // Contrat :
        //

        bool Add(T const & __data, size_t __source);
        // Mode d'emploi :
        //      Ajoute un élément de communication (__data) pour une planète source (__source)
        //      Renvoie true si l'ajout a réussi, false sinon.
        //
        // Contrat :
        //      L'indice __source d'une planète est compris entre 1 et 128 (inclus).
        //

        bool Add(T const * __data, size_t __source);
        // Mode d'emploi :
        //      Ajoute un ensemble d'éléments de communication sous forme d'un tableau de caractères
        //      (__data) pour une planète source (__source)
        //      Renvoie true si l'ajout a réussi, false sinon.
        //
        // Contrat :
        //      L'indice __source d'une planète est compris entre 1 et 128 (inclus).
        //

        size_t Count(size_t __source) const;
        // Mode d'emploi :
        //      Renvoie le nombre d'éléments de communication de la planète d'indice __source
        //
        // Contrat :
        //      L'indice __source d'une planète est compris entre 1 et 128 (inclus).
        //

        size_t FindIntl(T const * __pattern, size_t __from_pos, size_t & __source) const;
        // Mode d'emploi :
        //      Retourne la première occurence du mot clé __pattern trouvée dans les données
        //      à partir de l'indice __from_pos
        //      Récupération de l'indice de la planète dont les données contiennent la première
        //      occurence via (la référence) __source.
        //
        // Contrat :
        //      __from_pos doit être compris entre 0 et (10 000 000 - longueur(__pattern)).


        T const & GetData(size_t __pos, int * __error = nullptr) const;
        T & GetData(size_t __pos, int * __error = nullptr);
        // Mode d'emploi :
        //      Retourne l'élément de communication à la position "__pos"
        //      __error vaut 0 si la chaine est trouvée, -1 sinon
        // Contrat :
        //


    //-------------------------------------------- Constructeurs - destructeur

        intl_finder(Hash __hash = Hash(), InvHash __inv_hash = InvHash());
        // Mode d'emploi (constructeur par défault): trivial
        //
        // Contrat : aucun
        //

        virtual ~intl_finder();
        // Mode d'emploi (destructeur) : trivial
        //
        // Contrat : aucun
        //


    //------------------------------------------------------------------ PRIVE

    private:
        struct source {
            source() : count(0), ls() {
                for(size_t i = 0 ; i < MAX_DATA ; ++i)
                    tree[i] = nullptr;
            }

            ~source() {
                for(size_t i = 0 ; i < MAX_DATA ; ++i) {
                    if(tree[i] != nullptr)
                        tree[i]->preorder_map(free<size_t>());

                    delete tree[i];
                }
            }

            size_t count;
            rb_tree<size_t> * tree[MAX_DATA];
            list<T> ls;

            private:
                source(source const & __other) = delete;
                source const & operator=(source const & __other) = delete;
        };

    //----------------------------------------------------- Méthodes protégées

        intl_finder(intl_finder const & __other) = delete;
        // Mode d'emploi (constructeur de copie) : trivial
        // Mis dans la partie private afin que l'on ne puisse pas l'utiliser.
        // Contrat : aucun
        //

        intl_finder const & operator=(intl_finder const & __other) = delete;
        // Mode d'emploi :
        // Surcharge l'opérateur d'affectation
        //
        // Contrat : aucun
        //

        bool contains(T const * __pattern, size_t & ___from_pos, size_t __pos, size_t __source) const;
        // Mode d'emploi :
        // Indique si la suite de caractères existe à partir de la position donnée
        // parmi les éléments de communication de l'ensemble des planètes
        //
        // Contrat :
        // Le numéro de la source doit être entre 1 et 128
        //

    //----------------------------------------------------- Attributs protégés

        size_t _pos;
        source * _sources[MAX_SOURCE];
        Hash const & _hash;
        InvHash const & _inv_hash;
    };

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::intl_finder(Hash __hash, InvHash __inv_hash) : _pos(0), _hash(__hash), _inv_hash(__inv_hash) {
        for(unsigned int i = 0 ; i < MAX_SOURCE ; ++i) {
            _sources[i] = nullptr;
        }
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::~intl_finder() {
        for(unsigned int i = 0 ; i < MAX_SOURCE ; ++i)
            delete _sources[i];
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    void intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::Display(size_t __source) const {
        if(__source == 0) {
            for(size_t i = 1 ; i < MAX_SOURCE ; i++) {
                if(_sources[i] != nullptr) {
                    std::cout << "Planete " << i << " : ";
                    Display(i);
                    std::cout << std::endl;
                }
            }
            return;
        }

        if(__source > MAX_SOURCE)
            return;
        if(_sources[__source] == nullptr)
            return;

        _sources[__source]->ls.map(show<T>());
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    bool intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::Add(T const & __data, size_t __source) {
        size_t c = _hash(__data);

        if(_sources[__source - 1] == nullptr)
            _sources[__source - 1] = new source();

        if(_sources[__source - 1]->tree[c] == nullptr)
            _sources[__source - 1]->tree[c] = new rb_tree<size_t>();

        _sources[__source - 1]->ls.push_back(__data);
        _sources[__source - 1]->tree[c]->insert(new size_t(_pos));
        _sources[__source - 1]->count++;
        _pos++;

        return true;
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    bool intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::Add(T const * __data, size_t __source) {
        for(size_t i = 0 ; __data[i] != End && Add(__data[i], __source) ; ++i);
        return true;
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    size_t intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::Count(size_t __source) const {
        if(__source > MAX_SOURCE)
            return 0;

        if(__source == 0)
            return _pos;

        if(_sources[__source - 1] == nullptr)
            return 0;

        return _sources[__source - 1]->count;
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    T & intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::GetData(size_t __pos, int * __error) {
        if(__error != nullptr)
            *__error = 0;

        for(size_t i = 0; i < MAX_SOURCE ; ++i)
            for(size_t j = 0; j < MAX_DATA; ++j)
                if(_sources[i] != nullptr && _sources[i]->tree[j] != nullptr && _sources[i]->tree[j]->search(__pos) != nullptr)
                    return _inv_hash(j);

        if(__error != nullptr)
            *__error = -1;

        return 0;
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    T const & intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::GetData(size_t __pos, int * __error) const {
        if(__error != nullptr)
            *__error = 0;

        for(size_t i = 0; i < MAX_SOURCE ; ++i)
            for(size_t j = 0; j < MAX_DATA; ++j)
                if(_sources[i] != nullptr && _sources[i]->tree[j] != nullptr && _sources[i]->tree[j]->search(__pos) != nullptr)
                    return _inv_hash(j);

        if(__error != nullptr)
            *__error = -1;

        return 0;
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    size_t intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::FindIntl(T const * __pattern, size_t __from_pos, size_t & __source) const {
        size_t min_end = 0;
        size_t min_source = 0;

        for(size_t i = 0 ; i < MAX_SOURCE ; ++i) {
            size_t from = __from_pos;
            if(contains(__pattern, from, 0, i + 1)) {
                if(min_end == 0 || from <= min_end) {
                    min_end = from;
                    min_source = i + 1;
                }
            }
        }

        if(min_source != 0) {
            __source = min_source;
            return *_sources[min_source - 1]->tree[_hash(__pattern[0])]->search_min_ranged(__from_pos);
        }

        __source = 0;
        return 0;
    }

    template<class T, class Hash, class InvHash, const size_t MAX_SOURCE, const size_t MAX_DATA, const T End>
    bool intl_finder<T, Hash, InvHash, MAX_SOURCE, MAX_DATA, End>::contains(T const * __pattern, size_t & __from_pos, size_t __pos, size_t __source) const {
        if(_sources[__source - 1] == nullptr)   return false;
        if(__pattern[__pos] == End) return true;

        size_t c = _hash(__pattern[__pos]);
        if(_sources[__source - 1]->tree[c] == nullptr)  return false;

        size_t * new_from = _sources[__source - 1]->tree[c]->search_min_ranged(__from_pos);
        if(new_from == nullptr) return false;

        __from_pos = *new_from + 1;
        return contains(__pattern, __from_pos, __pos + 1, __source);
    }
}

//--------------------------- Autres définitions dépendantes de <intl_finder>

#endif // INTLFINDER_H_