#ifndef PATRON_H
#define PATRON_H

template <typename T1>
void insertiontri(T1* objet1, T1** tab, int poscourante){
    for(;poscourante>0;poscourante--){
        if(*objet1 < *tab[poscourante-1])
            tab[poscourante] = tab[poscourante-1];
        else break;
    }
    tab[poscourante] = objet1;
}

template <typename T1> inline void echange(T1 &objet1, T1 &objet2){
    T1 a = objet1;
    objet1 = objet2;
    objet2 = a;
}

template <class B>
B carre(B const&b){
    return b*b;
}

template <typename T1>
inline T1 max(T1 const&a, T1 const&b){return (a>b)?a:b;}
template <typename T1>
inline T1 min(T1 const&a, T1 const&b){return (a<b)?a:b;}



template <class T>
class dynamictab{
private:
    int nmax;
    int n;
    T *ptr;
public:
    dynamictab(){n=0;nmax=0;ptr=NULL;}
    dynamictab(int nombre_max){nmax = nombre_max; n=0; ptr=new T[nombre_max];}
    ~dynamictab(){delete[] ptr;}
    dynamictab(dynamictab<T> const&i){nmax = i.nmax; n=i.n; ptr=new T[nmax];
        int k;for(k=0;k<n;k++)ptr[k]=i.ptr[k];}
    void operator=(dynamictab<T> const&i){nmax = i.nmax; n=i.n; delete ptr;ptr=new T[nmax];
        int k;for(k=0;k<n;k++)ptr[k]=i.ptr[k];}

    inline T& operator()(int i){
        //if(i>=n){printf("ecriture du type %ld, n :%d, i: %d ",sizeof(T),n,i);exit(96);}
        return ptr[i];}
    inline T const& operator()(int i)const{
        //if(i>=n){printf("lecture du type %ld, n :%d, i: %d ",sizeof(T),n,i);exit(96);}
        return ptr[i];}
    inline T& last(){return ptr[n-1];}
    inline T const& last()const{return ptr[n-1];}
    inline T& first(){return ptr[0];}
    inline T const& first()const{return ptr[0];}

    inline int end()const{return n;}
    inline int endalloc()const{return nmax;}
    inline bool isempty()const{return n==0;}
    //*
    void seek_suppr(const T& a_supprimer){
        T* p;
        for(p=ptr;p<ptr+n && *p!=a_supprimer;p++);
        if(p==ptr+n);else{
            *p = ptr[n-1];//on place le dernier indice à la place de celui qu'on supprime
            n--;
        }
    }
    int seek(const T& a_trouver){
        int k;for(k=0;k<n && a_trouver!=ptr[k];k++);
        if(k==n)return -1;
        return k;
    }
    bool appartient(const T& a_trouver){
        int k;for(k=0;k<n && a_trouver!=ptr[k];k++);
        if(k<n)return true;
        else return false;
    }
    //*/

    void indice_suppr(int indice){
        ptr[indice] = ptr[n-1];//on place le dernier élément à la place de celui qu'on supprime
        n--;
    }
    void add(T a_ajouter){//ajoute un élément à la fin
        if(n==nmax){
            T *tab=new T[nmax*2+1];
            int k;
            for(k=0;k<n;k++)tab[k]=ptr[k];
            delete[] ptr;
            ptr=tab;
            nmax=nmax*2+1;
        }
        ptr[n]=a_ajouter;n++;
    }

    void empty(){n=0;}
    void desalloc(){n=0;nmax=0;delete[] ptr;ptr=NULL;}
    void full(){n=nmax;}

};

typedef dynamictab<int> Indicestab;


#endif