sortedvector.hpp

#ifndef SORTED_VECTOR_HPP
#define SORTED_VECTOR_HPP

#include <functional>
#include <memory>
#include <initializer_list>
#include <algorithm>
#include <iostream>

namespace homebrew {

struct out_of_range {}; //exceptions
struct elem_not_found {};
    
// SortedVector<type, sort_functor, allocator>    
template<typename T, typename S = std::less<T>, typename A = std::allocator<T>>
class SortedVector {
public:
    using size_type       = unsigned long;
    using value_type      = T;
    using iterator        = T*;
    using const_iterator  = const T*;
    using reference       = T&;
    using const_reference = const T&;
    using pointer         = T*;
    using const_pointer   = const T*;
    using difference_type = std::ptrdiff_t;
    using riterator       = std::reverse_iterator<iterator>;
    using const_riterator = std::reverse_iterator<const_iterator>;

private:
    size_type sz;
    size_type space;
    A alloc;
    T* elem;
    S functor;

public:
    explicit SortedVector(size_type s, T val = T())
        : sz{s}, elem{alloc.allocate(s)}, space(s)
        {
            for (size_type i=0; i<sz; ++i){
                alloc.construct(&elem[i], val);
            }
        }
    
    SortedVector() // default constructor
        : sz{0}, elem{nullptr}, space{0} {}       
    
    explicit SortedVector(const SortedVector& arg) // copy constructor (SortedVector v1 = v) -> need deep copy
        : sz{arg.sz}, elem{alloc.allocate(arg.sz)}, space{arg.sz}
    {
        for (size_type i=0; i<arg.sz; ++i) {
            alloc.construct(&elem[i], arg.elem[i]);
        }
    }
    
    template<typename I>
    SortedVector(I begin, I end)
        : space(std::distance(begin, end)), sz{0}, elem{alloc.allocate(space)}
    {
        for (auto i = begin; i != end; ++i) {
            insert(static_cast<T>(*i));
        }
    }    
        
    template<typename I>
    SortedVector(const std::initializer_list<I>& lst) // Initializer list constructor
        : SortedVector(std::begin(lst), std::end(lst)) {}
    
    /*
    SortedVector& operator=(const SortedVector& arg) //copy assignment -> need deep copy
    {              
        //1: Make a copy
        T* p = alloc.allocate(arg.sz);
        for (size_type i=0; i<arg.sz; ++i){
            alloc.construct(&p[i], arg.elem[i]);
        }
        size_type tsz = arg.sz;
        size_type tspace = arg.space;
        
        //2: Safely swap the state
        std::swap(elem,  p);
        std::swap(space, tspace);
        std::swap(sz,    tsz);
        
        // 3: Do the potentially dangerous deallocation
        for (size_type i=0; i<tsz; ++i) {
            alloc.destroy(&p[i]);
        }
        alloc.deallocate(p, tsz);                             
        
        return *this;
    }*/
    
    SortedVector& operator=(const SortedVector& copy)
    {  // copy assignment with copy and swap idiom
        SortedVector tmp (copy);
        tmp.swap(*this);
        return *this;
    }
    
    void swap(SortedVector& other) noexcept
    {
        std::swap(other.space, space);
        std::swap(other.sz, sz);
        std::swap(other.elem, elem);
    }
    
    explicit SortedVector(SortedVector&& arg) noexcept //move constructor
        : sz{arg.sz}, elem{arg.elem}, space{arg.sz}  // move elem to new owner
    {
        arg.sz = 0; //empty the source
        arg.elem = nullptr;
    }
    
    SortedVector& operator=(SortedVector&& arg) noexcept //move assignment (move arg to this vector)
    {
        this->swap(arg);  //just swap and let arg destructor do the cleanup
        
        return *this;        
    }
    
    ~SortedVector() noexcept //destructor
    {
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, sz);
    }
    
    // Checked access (cannot assign - if could would loose sort)
    const_reference at(size_type n) const
    {
        if (n<0 || n>=sz) throw out_of_range();
        return elem[n];
    }
    
    //unchecked access (only access, cannot assign)
    const_reference operator[](size_type n) const { return elem[n]; }
    
    size_type         size() const noexcept     { return sz; }
    size_type         capacity() const noexcept { return space; }
    pointer           data() noexcept           { return elem; }
    const_pointer     data() const noexcept     { return elem; }
    bool              empty() const noexcept    { return sz == 0; }
    
    iterator          begin() noexcept          { return elem; }
    riterator         rbegin() noexcept         { return riterator(end()); }
    const_iterator    begin() const noexcept    { return elem; }
    const_riterator   rbegin() const noexcept   { return const_riterator(end()); }
    iterator          end() noexcept            { return elem == nullptr ? nullptr: elem + sz;}
    riterator         rend() noexcept           { return riterator(begin()); }
    const_iterator    end() const noexcept      { return elem == nullptr ? nullptr: elem + sz;}
    const_riterator   rend() const noexcept     { return const_riterator(begin()); }
    const_iterator    cbegin() const noexcept   { return begin(); }
    const_iterator    cend() const noexcept     { return end(); }
    const_riterator   crbegin() const noexcept  { return rbegin(); }
    const_riterator   crend() const noexcept    { return rend(); }

    
    reference         back()                    { return elem[sz - 1];}
    const_reference   back() const              { return elem[sz - 1];}
    reference         front() noexcept          { return elem[0];}
    const_reference   front() const noexcept    { return elem[0];}
        
    void reserve(size_type newalloc) //change memory size (never decrease)
    {
        if (newalloc <= space) return;
        T* p = alloc.allocate(newalloc);
        for (size_type i=0; i<sz; ++i) alloc.construct(&p[i], elem[i]);
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, sz);
        elem = p;
        space = newalloc;
    }
    
    //You insert, but the position is determined by the functor sort
    void insert(const T& val)
    {
        if (size()==capacity())
            reserve(size()==0 ? 12: 2*size());
        
        auto lowerBound = std::lower_bound(elem, elem+sz, val, functor);
        
        //first copy last element into uninitialized space
        alloc.construct(elem+sz, back());
        ++sz;
        for (auto pos = end()-1; pos !=lowerBound; --pos) //shift
            *pos = *(pos - 1);
        alloc.construct(lowerBound, val); //insert the val
    }
       
    void insert_unique(const T& val)
    {
        if (!contain(val)) insert(val);
    }
    
  
    void erase(const T& val)
    {
        auto pp = std::upper_bound(elem, elem+sz, val, functor);
        if (pp == begin()) throw elem_not_found();
        else if (pp == end()) {
            if (val == *back()) {
                alloc.destroy(back());
                --sz;
                return;
            }else throw elem_not_found();
        }
        
        alloc.destroy(pp-1);
        for (auto pos = pp-1; pos != end()-1; ++pos)
            *pos = *(pos+1);

        --sz;
    }
        
    void erase(iterator position)
    {
        alloc.destroy(position);
        while (position != end()-1) {
            *position = *(position+1);
            ++position;
        }
        --sz;
    }
    
    void erase(iterator first, iterator last) //erase a range of elements
    {
        int shift = 0;
        for (iterator i = first; i != last; ++i) {
            alloc.destroy(i);
            ++shift;
        }
        
        for (iterator i = first; i != end()-shift; ++i) {
            *i = *(i + shift);
        }
        sz -= shift;
    }
    
    void clear()
    {
        for (size_type i=0; i<sz; ++i) alloc.destroy(&elem[i]); //destroy but keep memory allocated
        sz = 0;
    }
    
    bool contain(const T& arg)
    {
        return std::binary_search(elem, elem+sz, arg, functor);
    }
    
    size_type count(const T& arg)
    {
        size_type temp = 0;
        for (size_type i=0; i<sz; ++i) {
            if (arg == elem[i]) ++temp;
        }
        return temp;
    }
    
    void deduplicate()
    {
        //erase(std::unique(begin(), end()), end()); -> Faster??
        for (size_type i=0; i<sz; ++i) {
            while (count(elem[i]) > 1) {
                erase(elem[i]);
            }
        }
    }
    
    SortedVector<T, S, A>& operator+=(const SortedVector<T, S, A>& rhs)
    {
        for (auto& obj: rhs) this->insert(obj);
        return *this;
    }
    
    SortedVector<T, S, A>& operator-=(const SortedVector<T, S, A>& rhs)
    {
        for (auto& obj: rhs) this->erase(obj); //Beware it throws if you try to remove
        return *this;                          // a non-existent element
    }
    
    bool operator==(const SortedVector& rhs) const
    {
        return  (size() == rhs.size()) &&  std::equal(begin(), end(), rhs.begin());
    }
    
    bool operator!=(const SortedVector& rhs) const
    {
        return !(*this==rhs);
    }   

}; // class SortedVector

template<typename T, typename S, typename A>
inline SortedVector<T, S, A> operator+(SortedVector<T, S, A> lhs, const SortedVector<T, S, A>& rhs)
{
    lhs += rhs;
    return lhs;
}

template<typename T, typename S, typename A>
inline SortedVector<T, S, A> operator-(SortedVector<T, S, A> lhs, const SortedVector<T, S, A>& rhs)
{
    lhs -= rhs;
    return lhs;
}

template<typename T, typename S, typename A> // to cout and easy my debugging with std types
std::ostream& operator<<(std::ostream& os, const SortedVector<T, S, A>& vec)
{
    os << "[";
    for (auto i = vec.cbegin(); i != vec.cend(); ++i) {
        os << *i;
        if (i == vec.cend() - 1) { os << "]"; } else { os << ", "; } // x ? y:z operations didnt work. why?                                                       
    }
    os << "\n";
    return os;
}

} //namespace homebrew

#endif //SORTED_VECTOR_HPP