CORE_ArrayList.hpp

Go to the documentation of this file.

#ifndef CORE_ArrayList_HPP
#define CORE_ArrayList_HPP

#include <CORE_ArrayList.h>

using namespace std;


template<class T>
template<class Q>
void CORE_ArrayList<T>::push_back(const Q& obj) {
    //new dimension of array
    const tUIndex& dim=CORE_Array<T>::getSize();

    //get the capacity
    const tUIndex& cap=CORE_Array<T>::getCapacity();
    const tFlag& capF=getCapacityFactor();
    if (dim>=cap) {//capacity too small
        if ( (capF==1) || (cap==0) ) CORE_Array<T>::reserve(dim+1);
        else CORE_Array<T>::reserve(cap*capF);
    }
    //set at the end
    (*this)[dim]=obj;
    
    //set the size
    CORE_Array<T>::setSize(dim+1);
}



template<class T>
tBoolean CORE_ArrayList<T>::remove(const T& obj) {
  
  
    //number of copied
    tUIndex k=0;
    //pointer to the element to replace
    T *pK=&(*this)[0];
    //pointer of the element to test
    const T *pI=&(*this)[0];

    //get the size
    tUIndex &s=CORE_Array<T>::getSize();
    for (tUIndex i=0;i<s;i++) {
        
        if (*pI!=obj) {
            //copy the element
            *pK=*pI;
            //set the number of copied elements
            k++;
            //next copied element
            pK++;
        }
        //next test element
        pI++;
    }

    if (s!=k) {
        s=k;
        return true;
    }
    return false;
}

template<class T>
void CORE_ArrayList<T>::removeAtIndex(const tUIndex& index) {

    tUIndex &s=CORE_Array<T>::getSize();
    //no element
    if (s==0) return;
    //index too big
    if (index>=s) return;

    
    //new size
    s--;

    //no element to transfert
    if (index==s) return;
    
    //copy from index to mSize -1
    T *pI=&(*this)[index];
    const T *pS=&(*this)[index+1];
    //copy the elemetnt at index i+1 to array at index i
    for (tUIndex i=index;i<s;i++) {
        *pI=*pS;
        pI++;
        pS++;
    }
  
}

template<class T>
void CORE_ArrayList<T>::contractToLastElements(const tUIndex& n) {

    tUIndex &s=CORE_Array<T>::getSize();
    //test if there is no change
    if (n>=s) return;
    //test if clear 
    if (n==0) {
        CORE_Array<T>::clear();
        CORE_Array<T>::fitToSize();
        return;
    }
    //copy the last element to the first elements
    const T *v=&(*this)[s-n];
    T *newV=&(*this)[0];
    for (tUIndex i=0;i<n;i++) {
        *newV=*v;
        v++;
        newV++;
    }
    //set the size
    s=n;

    //fit the array
    CORE_Array<T>::fitToSize();
}


template<class T>
void CORE_ArrayList<T>::insertAtIndex(const tUIndex& i,const T& v) {
    tUIndex &s=CORE_Array<T>::getSize();
    //add at the end
   
    if (i>=s) {
        push_back(v);
        return;
    }

    //reallocate the array if necessary
    tUIndex dim=s+1;
    
    //get the capacity
    const tUIndex& cap=CORE_Array<T>::getCapacity();
    const tFlag& capF=getCapacityFactor();
    if (dim>=cap) {//capacity too small
        if ( (capF==1) || (cap==0) ) CORE_Array<T>::reserve(dim+1);
        else CORE_Array<T>::reserve(cap*capF);
    }

    //move the element at index k to index k+1
    //k=mSize
    T* newV=&(*this)[s];
    const T* vs=&(*this)[s-1];
    for (tUIndex k=s;k>i;k--) {
        *newV=*vs;
        newV--;
        vs--;
        
    }
    //set the v
    (*newV)=v;
    
    //new size
    s=dim;
    
}






template<class T>
tUIndex CORE_ArrayList<T>::insert(const T& obj) {

    tUIndex s=CORE_Array<T>::getSize();
    
    //start index
    tUIndex si=0;
    //end index
    tUIndex sf=CORE_Array<T>::getSize();

    //empty array case
    if (sf==0) {
        push_back(obj);
        return 0;
    }

    //set the end included index
    sf--;

  
    if (CORE_List::compare(obj,(*this)[0],mOrder)) {//obj is before mValues[0] with respect to order
        //insert at O
        insertAtIndex(0,obj);
        return 0;
    }
    
    if (CORE_List::compare((*this)[sf],obj,mOrder)) {//values[sf] is before values[sf] with respect to order
        //add at the end
        push_back(obj);
        return s;
    }
    
    tUIndex  i=0;
    while (sf-si>1) {
        i=(si+sf)/2;
        //values[i] is before obj
        if (CORE_List::compare((*this)[i],obj,mOrder)) si=i;
        else sf=i;
    }

    //sf=si
    insertAtIndex(sf,obj);
    return sf;
}



template<class T>
void CORE_ArrayList<T>::sort(T* items,
                             const tUIndex& N,
                             const tFlag& order) {
    
    tUIndex h=1;
    tUIndex i,j;
    T v;
    do h=3*h+1; 
    while (h<=N);
    do {
        h/=3;
        for (i=h;i<N;++i) {
            if (CORE_List::compare(items[i],
                                   items[i-h],
                                   order)) {
                v=items[i];
                j=i;
                do {
                    items[j]=items[j-h];
                    j=j-h;
                } 
                while ((j>=h) && (!CORE_List::compare(items[j-h],
                                                      v,
                                                      order)));
                items[j]=v;
            }
        }
    } 
    while (h>1); 
}


template<class T>
void CORE_ArrayList<T>::reverse() {

    const tUIndex& n=CORE_Array<T>::getSize();
    if (n==0) return;

    //mid index
    tUIndex i,mid=n/2;

    //end element
    T *e=&(*this)[n-1];
    //first element
    T *s=&(*this)[0];
    
    for (i=0;i<mid;i++) {
        std::swap(*e,*s);
        e--;
        s++;
    }

    //reverse the order
    CORE_List::reverse(mOrder);
}


template<class T>
tBoolean CORE_ArrayList<T>::search(const T* values, const tUIndex& n,const tFlag& order,
                                   const T& obj,
                                   tUIndex& index) {

    tIndex si=0;
    tIndex sf=n;
    index=0;
    
    if (sf==0) {
        return false;
    }
    sf--;
  
    // min
    if (compare(obj,values[0],order))  {
        return false;
    }

    // max
    if (compare(values[sf],obj,order)) {
        return false;
    }
 
    //eq
    if (compare(values[0],obj,CORE_List::EQ))  {
        return true;
    }
    if (compare(values[sf],obj,CORE_List::EQ)) {
        index=sf;
        return true;
    }
  
 
  
    int i=0;
    while (sf-si>1) {
        i=(si+sf)/2;
        if (compare(values[i],obj,CORE_List::EQ)) {
            index=i;
            return true;
        } else if (compare(values[i],obj,order)) {//values[i] is before obj with respect of order
            si=i;
        } else sf=i;
    }
    if (compare(obj,values[sf],CORE_List::EQ)) {
        index=sf;
        return true;
    }
    if (compare(obj,values[si],CORE_List::EQ)) {
        index=si;
        return true;
    }
    return false;
}
template<class T>
void CORE_ArrayList<T>::append(const CORE_ArrayList<T>& array) {
    // size of array to merge
    const tUIndex& p=array.getSize();

    tUIndex i,n=CORE_Array<T>::getSize();

    //set the  size
    tUIndex dim=n+p;

    //get the capacity
    const tUIndex& cap=CORE_Array<T>::getCapacity();
    const tFlag& capF=getCapacityFactor();
    if (dim>=cap) {//capacity too small
        if ( (capF==1) || (cap==0) ) CORE_Array<T>::reserve(dim+1);
        else CORE_Array<T>::reserve(cap*capF);
    }
    
    //copy the values
    T * vs=&CORE_Array<T>::getValues()[n];
    const T* as=&array[0];
    for (i=n;i<p;i++) {
        *vs=*as;
        as++;
        vs++;
    }
    
    
}

#endif