array.h

Go to the documentation of this file.

// Evo C++ Library
/* Copyright 2019 Justin Crowell
Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
*/

#pragma once
#ifndef INCL_evo_array_h
#define INCL_evo_array_h

#include "type.h"
#include "impl/iter.h"

namespace evo {


// Internal implementation macros -- only used in this file
// Grows to add items, without initializing -- size_ must be updated after calling
#define EVO_IMPL_ARRAY_GROW_ADD(SIZE) { \
    if (size_ > 0) { \
        Size newsize = size_ + SIZE; \
        T* const old_data = data_; \
        data_ = (T*)::malloc((size_t)newsize*sizeof(T)); \
        memcpy(data_, old_data, (size_t)size_*sizeof(T)); \
        ::free(old_data); \
    } else \
        data_ = (T*)::malloc((size_t)SIZE*sizeof(T)); \
}
// Grows to insert items, without initializing -- updates size_
#define EVO_IMPL_ARRAY_GROW_INSERT(INDEX, SIZE) { \
    assert( size_ > 0 ); \
    Size newsize = size_ + SIZE; \
    T* const old_data = data_; \
    data_ = (T*)::malloc((size_t)newsize*sizeof(T)); \
    if (INDEX > 0) { \
        memcpy(data_, old_data, (size_t)INDEX*sizeof(T)); \
        Size tail = size_ - INDEX; \
        assert( tail > 0 ); \
        memcpy(data_+INDEX+SIZE, old_data+INDEX, (size_t)tail*sizeof(T)); \
    } else \
        memcpy(data_+SIZE, old_data, (size_t)size_*sizeof(T)); \
    ::free(old_data); \
    size_ = newsize; \
}


template<class T,class TSize=SizeT>
class Array {
public:
    EVO_CONTAINER_TYPE;                         
    typedef Array<T,TSize> ThisType;            
    typedef TSize          Size;                
    typedef Size           Key;                 
    typedef T              Value;               
    typedef T              Item;                

    // Iterator support types
    typedef Key IterKey;
    typedef T   IterItem;
    typedef typename IteratorRa<ThisType>::Const Iter;    
    typedef IteratorRa<ThisType>                 IterM;    

    Array() {
        data_ = NULL;
        size_ = 0;
    }

    explicit Array(const ValEmpty& val) {
        EVO_PARAM_UNUSED(val);
        data_ = EVO_PEMPTY;
        size_ = 0;
    }

    Array(const ThisType& src) {
        if (src.size_ > 0) {
            data_ = (T*)::malloc((size_t)src.size_*sizeof(T));
            DataInit<T>::init(data_, src.data_, src.size_);
        } else
            data_ = src.data_;
        size_ = src.size_;
    }

    Array(const T* data, Size size) {
        if (size > 0) {
            data_ = (T*)::malloc((size_t)size*sizeof(T));
            DataInit<T>::init(data_, data, size);
        } else if (data == NULL)
            data_ = NULL;
        else
            data_ = EVO_PEMPTY;
        size_ = size;
    }

    ~Array() {
        if (size_ > 0) {
            DataInit<T>::uninit(data_, size_);
            ::free(data_);
        }
    }

#if defined(EVO_CPP11)

    Array(std::initializer_list<T> init) : Array() {
        assert( init.size() < IntegerT<Size>::MAX );
        resize((Size)init.size());
        uint i = 0;
        for (const auto& item : init)
            data_[i++] = item;
    }

    Array(ThisType&& src) {
        ::memcpy(this, &src, sizeof(ThisType));
        ::memset(&src, 0, sizeof(ThisType));
    }

    ThisType& operator=(ThisType&& src) {
        resize(0);
        ::memcpy(this, &src, sizeof(ThisType));
        ::memset(&src, 0, sizeof(ThisType));
        return *this;
    }
#endif

    const ThisType& asconst() const {
        return *this;
    }

    // SET

    ThisType& operator=(const ThisType& src)
        { return set(src); }

    ThisType& operator=(const ValNull&)
        { return set(); }

    ThisType& operator=(const ValEmpty&)
        { return setempty(); }

    ThisType& clear() {
        if (size_ > 0) {
            DataInit<T>::uninit(data_, size_);
            ::free(data_);
            data_ = EVO_PEMPTY;
            size_ = 0;
        }
        return *this;
    }

    ThisType& set() {
        if (size_ > 0) {
            DataInit<T>::uninit(data_, size_);
            ::free(data_);
            size_ = 0;
        }
        data_ = NULL;
        return *this;
    }

    ThisType& set(const ThisType& src) {
        if (this != &src) {
            if (src.size_ > 0) {
                if (size_ == src.size_) {
                    // Same positive size
                    DataInit<T>::uninit(data_, size_);
                    DataInit<T>::init(data_, src.data_, src.size_);
                } else {
                    // New positive size
                    if (size_ > 0) {
                        DataInit<T>::uninit(data_, size_);
                        ::free(data_);
                    }
                    size_ = src.size_;
                    data_ = (T*)::malloc((size_t)src.size_*sizeof(T));
                    DataInit<T>::init(data_, src.data_, src.size_);
                }
            } else {
                // Null/Empty
                if (size_ > 0) {
                    DataInit<T>::uninit(data_, size_);
                    ::free(data_);
                    size_ = 0;
                }
                data_ = (src.data_ == NULL ? NULL : EVO_PEMPTY);
            }
        }
        return *this;
    }

    ThisType& set(const T* data, Size size) {
        if (size == size_) {
            if (size_ > 0)
                DataInit<T>::uninit(data_, size_);
            if (size > 0)
                DataInit<T>::init(data_, data, size);
            else if (data == NULL)
                data_ = NULL;
            else
                data_ = EVO_PEMPTY;
        } else {
            if (size_ > 0) {
                DataInit<T>::uninit(data_, size_);
                ::free(data_);
            }
            if (size > 0) {
                data_ = (T*)::malloc((size_t)size*sizeof(T));
                DataInit<T>::init(data_, data, size);
            } else if (data == NULL)
                data_ = NULL;
            else
                data_ = EVO_PEMPTY;
            size_ = size;
        }
        return *this;
    }

    ThisType& setempty() {
        if (size_ > 0) {
            DataInit<T>::uninit(data_, size_);
            ::free(data_);
            size_ = 0;
        }
        data_ = EVO_PEMPTY;
        return *this;
    }

    // INFO

    bool null() const
        { return (data_ == NULL); }

    bool empty() const
        { return (size_ == 0); }

    Size size() const
        { return size_; }

    bool shared() const
        { return false; }

    const T* data() const
        { return data_; }

    const T& operator[](Key index) const
        { assert( index < size_ ); return data_[index]; }

    const T& item(Key index) const
        { assert( index < size_ ); return data_[index]; }

    const T& ring(Key index) const
        { return data_[index % size_]; }

    const T* first() const
        { return (size_ > 0 ? data_ : NULL); }

    const T* last() const
        { return (size_ > 0 ? data_+size_-1 : NULL); }

    Key iend(Size offset=0) const
        { return (offset < size_ ? size_-1-offset : END); }

    ulong hash(ulong seed=0) const
        { return DataHash<T>::hash(data_, size_, seed); }

    // COMPARE

    int compare(const ThisType& data) const {
        int result;
        if (this == &data)
            result = 0;
        else if (data_ == NULL)
            result = (data.data_ == NULL ? 0 : -1);
        else if (data.data_ == NULL)
            result = 1;
        else
            result = DataCompare<T>::compare(data_, size_, data.data_, data.size_);
        return result;
    }

    bool operator==(const ThisType& data) const {
        bool result;
        if (this == &data)
            result = true;
        else if (data_ == NULL)
            result = (data.data_ == NULL);
        else if (data.data_ == NULL || size_ != data.size_)
            result = false;
        else
            result = DataEqual<T>::equal(data_, data.data_, data.size_);
        return result;
    }

    bool operator!=(const ThisType& data) const {
        bool result;
        if (this == &data)
            result = false;
        else if (data_ == NULL)
            result = (data.data_ != NULL);
        else if (data.data_ == NULL || size_ != data.size_)
            result = true;
        else
            result = !DataEqual<T>::equal(data_, data.data_, data.size_);
        return result;
    }

    bool starts(const T& item) const
        { return (size_ > 0 && data_[0] == item); }

    bool starts(const T* items, Size size) const
        { return (size_ >= size && DataEqual<T>::equal(data_, items, size)); }

    bool ends(const T& item) const
        { return (size_ > 0 && data_[size_-1] == item); }

    bool ends(const T* items, Size size) const
        { return (size_ >= size && DataEqual<T>::equal(data_+(size_-size), items, size)); }

    // FIND

    Iter cbegin() const
        { return Iter(*this); }

    Iter cend() const
        { return Iter(); }

    IterM begin()
        { return IterM(*this); }

    Iter begin() const
        { return Iter(*this); }

    IterM end()
        { return IterM(); }

    Iter end() const
        { return Iter(); }

    // INFO_SET

    T* data()
        { return data_; }

    T& operator[](Key index)
        { assert( index < size_ ); return data_[index]; }

    T& item(Key index)
        { assert( index < size_ ); return data_[index]; }

    T& ring(Key index)
        { return data_[index % size_]; }

    T* first()
        { return (size_ > 0 ? data_ : NULL); }

    T* last()
        { return (size_ > 0 ? data_+size_-1 : NULL); }

    ThisType& unshare()
        { return *this; }

    ThisType& resize(Size size) {
        if (size == 0) {
            // Null/Empty
            if (size_ > 0) {
                DataInit<T>::uninit(data_, size_);
                ::free(data_);
                data_ = EVO_PEMPTY;
                size_ = 0;
            }
        } else if (size_ != size) {
            // New positive size
            assert( size > 0 );
            if (size_ > 0) {
                // Preserve existing items
                T* const   old_data  = data_;
                const Size save_size = (size_ < size ? size_ : size);
                data_ = (T*)::malloc((size_t)size*sizeof(T));
                memcpy(data_, old_data, (size_t)save_size*sizeof(T));
                DataInit<T>::init_tail_safe(data_, save_size, size);

                size_ -= save_size;
                if (size_ > 0)
                    DataInit<T>::uninit(old_data+save_size, size_);
                ::free(old_data);
            } else {
                // New array
                data_ = (T*)::malloc((size_t)size*sizeof(T));
                DataInit<T>::init_safe(data_, size);
            }
            size_ = size;
        }
        return *this;
    }

    ThisType& resize2(Size size) {
        if (size > 0) {
            Size size2 = (size >= 256 ? 256 : 1);
            while (size2 < size)
                size2 *= 2;
            size = size2;
        }
        resize(size);
        return *this;
    }

    // ADD

    ThisType& addnew(Size size=1) {
        if (size > 0) {
            EVO_IMPL_ARRAY_GROW_ADD(size);
            DataInit<T>::init_safe(data_+size_, size);
            size_ += size;
        }
        return *this;
    }

    ThisType& add(const Item& item) {
        EVO_IMPL_ARRAY_GROW_ADD(1);
        DataInit<T>::init(data_+size_, &item, 1);
        ++size_;
        return *this;
    }

    // INSERT

    Size insertnew(Key index, Size size=1) {
        if (size > 0) {
            if (index < size_) {
                EVO_IMPL_ARRAY_GROW_INSERT(index, size);
            } else {
                index = size_;
                EVO_IMPL_ARRAY_GROW_ADD(size);
                size_ += size;
            }
            DataInit<T>::init_safe(data_+index, size);
        }
        return index;
    }

    Size insert(Key index, const Item& item) {
        if (index < size_) {
            EVO_IMPL_ARRAY_GROW_INSERT(index, 1);
        } else {
            index = size_;
            EVO_IMPL_ARRAY_GROW_ADD(1);
            ++size_;
        }
        DataInit<T>::init(data_+index, &item, 1);
        return index;
    }

    // REMOVE

    Size remove(Key index, Size size=1) {
        if (index < size_ && size > 0) {
            Size tempsize = size_ - index;
            if (size > tempsize)
                size = tempsize;
            if (size < size_) {
                // Preserve existing items
                tempsize = size_ - size;
                T* const old_data  = data_;
                data_ = (T*)::malloc((size_t)tempsize*sizeof(T));
                if (index > 0)
                    memcpy(data_, old_data, (size_t)index*sizeof(T));
                Size tail = size_ - index - size;
                if (tail > 0)
                    memcpy(data_+index, old_data+index+size, (size_t)tail*sizeof(T));

                DataInit<T>::uninit(old_data+index, size);
                ::free(old_data);
                size_ = tempsize;
            } else {
                // Remove all
                size = size_;
                DataInit<T>::uninit(data_, size_);
                ::free(data_);
                data_ = EVO_PEMPTY;
                size_ = 0;
            }
        } else
            size = 0;
        return size;
    }

    // FILL

    ThisType& fill(const T& item, Key index=0, Size size=ALL) {
        if (index == END)
            index = size_;
        if (size == ALL)
            size = (index < size_ ? size_ - index : 0);
        if (size > 0) {
            const Size newsize = index + size;
            if (newsize > size_)
                advResize(newsize);
            DataFill<T>::fill(data_+index, size, item);
        }
        return *this;
    }

    // MOVE / SWAP

    void swap(ThisType& array)
        { EVO_IMPL_CONTAINER_SWAP(this, &array, ThisType); }

    // ADVANCED

    const T& advRing(Key index) const {
        assert( is_pow2(size_) );
        return data_[index & (size_ - 1)];
    }

    T& advRing(Key index) {
        assert( is_pow2(size_) );
        return data_[index & (size_ - 1)];
    }

    ThisType& advResize(Size size) {
        if (size == 0) {
            // Null/Empty
            if (size_ > 0) {
                DataInit<T>::uninit(data_, size_);
                ::free(data_);
                data_ = EVO_PEMPTY;
                size_ = 0;
            }
        } else if (size_ != size) {
            // New positive size
            assert( size > 0 );
            if (size_ > 0) {
                // Preserve existing items
                T* const   old_data  = data_;
                const Size save_size = (size_ < size ? size_ : size);
                data_ = (T*)::malloc((size_t)size*sizeof(T));
                memcpy(data_, old_data, (size_t)save_size*sizeof(T));
                DataInit<T>::init_tail_fast(data_, save_size, size);

                size_ -= save_size;
                if (size_ > 0)
                    DataInit<T>::uninit(old_data+save_size, size_);
                ::free(old_data);
            } else {
                // New array
                data_ = (T*)::malloc((size_t)size*sizeof(T));
                DataInit<T>::init(data_, size);
            }
            size_ = size;
        }
        return *this;
    }

    // INTERNAL

    // Iterator support methods
    void iterInitMutable()
        { }
    const IterItem* iterFirst(IterKey& key) const
        { key = 0; return data_; }
    const IterItem* iterNext(IterKey& key) const {
        const IterItem* result = NULL;
        if (key != END) {
            if (++key < size_)
                result = &(data_[key]);
            else
                key = END;
        }
        return result;
    }
    const IterItem* iterNext(Size count, IterKey& key) const {
        const T* result = NULL;
        if (key != END) {
            if ( (key+=count) < size_ )
                result = &(data_[key]);
            else
                key = END;
        }
        return result;
    }
    const IterItem* iterLast(IterKey& key) const {
        const IterItem* result = NULL;
        if (size_ > 0) {
            key    = size_ - 1;
            result = &(data_[key]);
        } else
            key = END;
        return result;
    }
    const IterItem* iterPrev(IterKey& key) const {
        const IterItem* result = NULL;
        if (key != END) {
            if (key > 0)
                result = &(data_[--key]);
            else
                key = END;
        }
        return result;
    }
    const IterItem* iterPrev(Size count, IterKey& key) const {
        const IterItem* result = NULL;
        if (key != END) {
            if (key > 0 && count <= key)
                result = &(data_[(key-=count)]);
            else
                key = END;
        }
        return result;
    }
    Size iterCount() const
        { return size_; }
    const IterItem* iterSet(IterKey key) const {
        const IterItem* result = NULL;
        if (key < size_)
            result = &(data_[key]);
        return result;
    }
protected:
    T*   data_;
    Size size_;
};


// Remove implementation macros
#undef EVO_IMPL_ARRAY_GROW_ADD
#undef EVO_IMPL_ARRAY_GROW_INSERT


}
#endif