/home/andref/projetos/epos--/include/ep_cvec.h

#ifndef EP_CVEC_H_
#define EP_CVEC_H_

#include <utility/malloc.h>
#include "algorithm.h"
//#include "utility/ostream.h"

__BEGIN_SYS

const unsigned int CVEC_ADAPTION_RATE = 16;

template<class Contained>
class CircularVector {
public:
        template<class ItTp>
        struct Incrementor {
                inline Incrementor(int current, CircularVector& vec) :
                                current(current), vec(vec) {}

                inline Incrementor operator+(int i) {
                        vec.inc(current, i);
                        return Incrementor(*this);
                }

                inline Incrementor operator++(int) {
                        Incrementor result(*this);
                        vec.inc(current, 1);
                        return result;
                }

                inline void operator++() {
                        vec.inc(current, 1);
                }

                inline void operator--() {
                        vec.inc(current, -1);
                }

                inline Incrementor operator--(int) {
                        Incrementor result(*this);
                        vec.inc(current, -1);
                        return result;
                }

                inline ItTp& operator*() const {
                        return (vec._elements[current]);
                }

                inline bool operator==(const Incrementor& comparable) const {
                        return ((comparable.current     == current));
                }

                inline bool operator!=(const Incrementor& comparable) const {
                        return !operator==(comparable);
                }

                int current;
                CircularVector& vec;
        };

        typedef Incrementor<Contained> Iterator;
        typedef Incrementor<const Contained> ConstIterator;

        friend struct Incrementor<Contained>;
        friend struct Incrementor<const Contained>;

        inline void print(Iterator begin, Iterator end) {
                /*
                kout << "elements[";
                for (Iterator it = begin; it != end; ++it)
                        kout << *it << " ";
                kout << "]\n";*/
        }

        CircularVector() : _size(0), _capacity(1), _begin(0), _end(0) {
                _elements = (Contained*) malloc(sizeof(Contained) * capacity());
        }

        virtual ~CircularVector() {
                free(_elements);
        }

        Iterator begin() {
                return Iterator(_begin, *this);
        }

        ConstIterator begin() const {
                return ConstIterator(_begin, *this);
        }

        Iterator end() {
                return Iterator(_end, *this);
        }

        ConstIterator end() const {
                return ConstIterator(_end, *this);
        }

        inline void pushFront(const Contained& contained) {
                //extra member for iterating correctly (-1)
                if (size() >= (capacity() - 1)) enlarge();
                ++_size;
                //increments first and writes after for having no shared memory with the end pointer
                inc(_begin, -1);
                _elements[_begin] = contained;
        }

        inline void pushBack(const Contained& contained) {
                //extra member for iterating correctly (-1)
                if (size() >= (capacity() - 1)) enlarge();
                ++_size;
                _elements[_end] = contained;
                inc(_end, +1);

        }

        inline Contained& operator[](unsigned int i) {
                return *(begin() + i);
        }

        inline void popBack() {
                --_size;
                inc(_end, -1);
                //extra member for iterating correctly (+1)
                //if ((size() + 1) < (capacity() / CVEC_ADAPTION_RATE)) minimize();
        }

        inline void popFront() {
                --_size;
                inc(_begin, +1);
                //extra member for iterating correctly (+1)
                //if ((size() + 1) < (capacity() / CVEC_ADAPTION_RATE)) minimize();
        }

        inline Contained& front() const {
                return _elements[_begin];
        }

        inline Contained& back() const {
                return _elements[_end - 1];
        }

        inline unsigned int size() const {
                return _size;
        }

        inline unsigned int capacity() const {
                return _capacity;
        }

        inline bool isEmpty() const {
                return (size() == 0);
        }

        void remove(const Contained& contained) {
                for (Iterator it = begin(); it != end(); ++it) {
                        if (*it == contained) {
                                ++it;
                                shift(it, end(), -1);
                                break;
                        }
                }
        }

protected:
        Contained* _elements;
        unsigned int _size, _capacity;
        int _begin, _end;

        inline void inc(int& toIncrement, int n) {
                toIncrement += n + _capacity;
                toIncrement %= _capacity;
        }

        void enlarge() {
                Contained* newElements = (Contained*) malloc(sizeof(Contained)
                                * capacity() * CVEC_ADAPTION_RATE);

                copy(begin(), end(), newElements);

                free(_elements);

                _begin = 0;
                _end = size();
                _elements = newElements;
                _capacity *= CVEC_ADAPTION_RATE;
        }

        void minimize() {
                Contained* newElements = (Contained*) malloc(sizeof(Contained)
                                * (capacity() / CVEC_ADAPTION_RATE));

                copy(begin(), end(), newElements);

                free(_elements);

                _begin = 0;
                _end = size();
                _elements = newElements;
                _capacity /= CVEC_ADAPTION_RATE;
        }

};

template<class Contained>
class OrderedCVector : public CircularVector<Contained> {
public:
        OrderedCVector() : CircularVector<Contained>() {}

        typedef typename CircularVector<Contained>::Iterator Iterator;

        template<typename Comparator>
        inline void pushBack(const Contained& contained, const Comparator& comparator) {
                /*kout << "Contained " << contained << "\n";*/

                //extra member for iterating correctly (-1)
                if (CircularVector<Contained>::size() >=
                                (CircularVector<Contained>::capacity() - 1)) {

                        CircularVector<Contained>::enlarge();
                }

                int i = 0, j = CircularVector<Contained>::size() - 1;

                int index = (i + j)/2;

                if (j == -1) {// if is empty
                        CircularVector<Contained>::pushBack(contained);
                        return;
                }

                int comparison = comparator(contained, (*this)[index]);
                int pi = -1, pj = -1;
                while ((i < j)) {
                        pi = i;
                        pj = j;
                        if (comparison == 1) i = index + 1;
                        else j = index + 1;
                        if (pi == i &&  pj == j) {
                                ++index;
                                break;
                        }
                        comparison = comparator(contained, (*this)[index]);
                        /*kout << "Loop: " << i << " " << j << "\n";*/
                }

                for (unsigned int i = CircularVector<Contained>::size(); i > (unsigned int)index; --i)
                        (*this)[i] = (*this)[i - 1];


                /*kout << "Inserted at index " << index << "\n";*/


                ++CircularVector<Contained>::_size;
                (*this)[index] = contained;
                CircularVector<Contained>::inc(
                                CircularVector<Contained>::_end, +1);
/*
                kout << "After ";
                CircularVector<Contained>::print(
                                CircularVector<Contained>::begin(),
                                CircularVector<Contained>::end());
*/

        }

};

__END_SYS

#endif 

---