Array.h

Go to the documentation of this file.

/*
  ==============================================================================
 
   This file is part of the Water library.
   Copyright (c) 2016 ROLI Ltd.
   Copyright (C) 2017-2019 Filipe Coelho <falktx@falktx.com>
 
   Permission is granted to use this software under the terms of the ISC license
   http://www.isc.org/downloads/software-support-policy/isc-license/
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
   copyright notice and this permission notice appear in all copies.
 
   THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH REGARD
   TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
   FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT,
   OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
   USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
   TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
   OF THIS SOFTWARE.
 
  ==============================================================================
*/
 
#ifndef WATER_ARRAY_H_INCLUDED
#define WATER_ARRAY_H_INCLUDED
 
#include "../containers/ArrayAllocationBase.h"
#include "../containers/ElementComparator.h"
 
namespace water {
 
//==============================================================================
template <typename ElementType, size_t minimumAllocatedSize = 0>
class Array
{
private:
    typedef PARAMETER_TYPE (ElementType) ParameterType;
 
public:
    //==============================================================================
    Array() noexcept
        : data(),
          numUsed(0)
    {
    }

    Array (const Array<ElementType>& other) noexcept
        : data(),
          numUsed(0)
    {
        CARLA_SAFE_ASSERT_RETURN(data.setAllocatedSize (other.numUsed),);
        numUsed = other.numUsed;
 
        for (int i = 0; i < numUsed; ++i)
            new (data.elements + i) ElementType (other.data.elements[i]);
    }

    template <typename TypeToCreateFrom>
    explicit Array (const TypeToCreateFrom* values) noexcept  : numUsed (0)
    {
        while (*values != TypeToCreateFrom())
        {
            CARLA_SAFE_ASSERT_BREAK(add (*values++));
        }
    }

    template <typename TypeToCreateFrom>
    Array (const TypeToCreateFrom* values, int numValues) noexcept  : numUsed (numValues)
    {
        CARLA_SAFE_ASSERT_RETURN(data.setAllocatedSize (numValues),);
 
        for (int i = 0; i < numValues; ++i)
            new (data.elements + i) ElementType (values[i]);
    }

    ~Array() noexcept
    {
        deleteAllElements();
    }

    Array& operator= (const Array& other) noexcept
    {
        if (this != &other)
        {
            Array<ElementType> otherCopy (other);
            swapWith (otherCopy);
        }
 
        return *this;
    }
 
    //==============================================================================
    template <class OtherArrayType>
    bool operator== (const OtherArrayType& other) const
    {
        if (numUsed != other.numUsed)
            return false;
 
        for (int i = numUsed; --i >= 0;)
            if (! (data.elements [i] == other.data.elements [i]))
                return false;
 
        return true;
    }

    template <class OtherArrayType>
    bool operator!= (const OtherArrayType& other) const
    {
        return ! operator== (other);
    }
 
    //==============================================================================
    void clear() noexcept
    {
        deleteAllElements();
        data.setAllocatedSize (0);
        numUsed = 0;
    }

    void clearQuick() noexcept
    {
        deleteAllElements();
        numUsed = 0;
    }
 
    //==============================================================================
    inline int size() const noexcept
    {
        return numUsed;
    }

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

    ElementType operator[] (const int index) const
    {
        if (isPositiveAndBelow (index, numUsed))
        {
            wassert (data.elements != nullptr);
            return data.elements [index];
        }
 
        return ElementType();
    }

    inline ElementType getUnchecked (const int index) const
    {
        wassert (isPositiveAndBelow (index, numUsed) && data.elements != nullptr);
        return data.elements [index];
    }

    inline ElementType& getReference (const int index) const noexcept
    {
        wassert (isPositiveAndBelow (index, numUsed) && data.elements != nullptr);
        return data.elements [index];
    }

    inline ElementType getFirst() const
    {
        if (numUsed > 0)
        {
            wassert (data.elements != nullptr);
            return data.elements[0];
        }
 
        return ElementType();
    }

    inline ElementType getLast() const
    {
        if (numUsed > 0)
        {
            wassert (data.elements != nullptr);
            return data.elements[numUsed - 1];
        }
 
        return ElementType();
    }

    inline ElementType* getRawDataPointer() noexcept
    {
        return data.elements;
    }
 
    //==============================================================================
    inline ElementType* begin() const noexcept
    {
        return data.elements;
    }

    inline ElementType* end() const noexcept
    {
       #ifdef DEBUG
        if (data.elements == nullptr || numUsed <= 0) // (to keep static analysers happy)
            return data.elements;
       #endif
 
        return data.elements + numUsed;
    }
 
    //==============================================================================
    int indexOf (ParameterType elementToLookFor) const
    {
        const ElementType* e = data.elements.getData();
        const ElementType* const end_ = e + numUsed;
 
        for (; e != end_; ++e)
            if (elementToLookFor == *e)
                return static_cast<int> (e - data.elements.getData());
 
        return -1;
    }

    bool contains (ParameterType elementToLookFor) const
    {
        const ElementType* e = data.elements.getData();
        const ElementType* const end_ = e + numUsed;
 
        for (; e != end_; ++e)
            if (elementToLookFor == *e)
                return true;
 
        return false;
    }
 
    //==============================================================================
    bool add (const ElementType& newElement) noexcept
    {
        if (! data.ensureAllocatedSize (static_cast<size_t>(numUsed + 1)))
            return false;
 
        new (data.elements + numUsed++) ElementType (newElement);
        return true;
    }

    bool insert (int indexToInsertAt, ParameterType newElement) noexcept
    {
        if (! data.ensureAllocatedSize (numUsed + 1))
            return false;
 
        if (isPositiveAndBelow (indexToInsertAt, numUsed))
        {
            ElementType* const insertPos = data.elements + indexToInsertAt;
            const int numberToMove = numUsed - indexToInsertAt;
 
            if (numberToMove > 0)
                data.moveMemory (insertPos + 1, insertPos, numberToMove);
 
            new (insertPos) ElementType (newElement);
            ++numUsed;
        }
        else
        {
            new (data.elements + numUsed++) ElementType (newElement);
        }
 
        return true;
    }

    bool insertMultiple (int indexToInsertAt, ParameterType newElement,
                         int numberOfTimesToInsertIt)
    {
        if (numberOfTimesToInsertIt > 0)
        {
            if (! data.ensureAllocatedSize (numUsed + numberOfTimesToInsertIt))
                return false;
 
            ElementType* insertPos;
 
            if (isPositiveAndBelow (indexToInsertAt, numUsed))
            {
                insertPos = data.elements + indexToInsertAt;
                const int numberToMove = numUsed - indexToInsertAt;
                data.moveMemory (insertPos + numberOfTimesToInsertIt, insertPos, numberToMove);
            }
            else
            {
                insertPos = data.elements + numUsed;
            }
 
            numUsed += numberOfTimesToInsertIt;
 
            while (--numberOfTimesToInsertIt >= 0)
            {
                new (insertPos) ElementType (newElement);
                ++insertPos; // NB: this increment is done separately from the
                             // new statement to avoid a compiler bug in VS2014
            }
        }
 
        return true;
    }
 
#if 0
    bool insertArray (int indexToInsertAt,
                      const ElementType* newElements,
                      int numberOfElements)
    {
        if (numberOfElements > 0)
        {
            if (! data.ensureAllocatedSize (numUsed + numberOfElements))
                return false;
 
            ElementType* insertPos = data.elements;
 
            if (isPositiveAndBelow (indexToInsertAt, numUsed))
            {
                insertPos += indexToInsertAt;
                const int numberToMove = numUsed - indexToInsertAt;
                std::memmove (insertPos + numberOfElements, insertPos, (size_t) numberToMove * sizeof (ElementType));
            }
            else
            {
                insertPos += numUsed;
            }
 
            numUsed += numberOfElements;
 
            while (--numberOfElements >= 0)
                new (insertPos++) ElementType (*newElements++);
        }
 
        return true;
    }
#endif

    bool addIfNotAlreadyThere (ParameterType newElement)
    {
        if (contains (newElement))
            return false;
 
        return add (newElement);
    }

    void set (const int indexToChange, ParameterType newValue)
    {
        wassert (indexToChange >= 0);
 
        if (isPositiveAndBelow (indexToChange, numUsed))
        {
            wassert (data.elements != nullptr);
            data.elements [indexToChange] = newValue;
        }
        else if (indexToChange >= 0)
        {
            data.ensureAllocatedSize (numUsed + 1);
            new (data.elements + numUsed++) ElementType (newValue);
        }
    }

    void setUnchecked (const int indexToChange, ParameterType newValue)
    {
        wassert (isPositiveAndBelow (indexToChange, numUsed));
        data.elements [indexToChange] = newValue;
    }

    template <typename Type>
    void addArray (const Type* elementsToAdd, int numElementsToAdd)
    {
        if (numElementsToAdd > 0)
        {
            data.ensureAllocatedSize (numUsed + numElementsToAdd);
 
            while (--numElementsToAdd >= 0)
            {
                new (data.elements + numUsed) ElementType (*elementsToAdd++);
                ++numUsed;
            }
        }
    }

    template <typename Type>
    void addNullTerminatedArray (const Type* const* elementsToAdd)
    {
        int num = 0;
        for (const Type* const* e = elementsToAdd; *e != nullptr; ++e)
            ++num;
 
        addArray (elementsToAdd, num);
    }

    template <class OtherArrayType>
    void swapWith (OtherArrayType& otherArray) noexcept
    {
        data.swapWith (otherArray.data);
        std::swap (numUsed, otherArray.numUsed);
    }

    template <class OtherArrayType>
    void addArray (const OtherArrayType& arrayToAddFrom,
                   int startIndex = 0,
                   int numElementsToAdd = -1)
    {
        if (startIndex < 0)
        {
            wassertfalse;
            startIndex = 0;
        }
 
        if (numElementsToAdd < 0 || startIndex + numElementsToAdd > arrayToAddFrom.size())
            numElementsToAdd = arrayToAddFrom.size() - startIndex;
 
        while (--numElementsToAdd >= 0)
            add (arrayToAddFrom.getUnchecked (startIndex++));
    }

    void resize (const int targetNumItems)
    {
        wassert (targetNumItems >= 0);
 
        const int numToAdd = targetNumItems - numUsed;
        if (numToAdd > 0)
            insertMultiple (numUsed, ElementType(), numToAdd);
        else if (numToAdd < 0)
            removeRange (targetNumItems, -numToAdd);
    }

    template <class ElementComparator>
    int addSorted (ElementComparator& comparator, ParameterType newElement)
    {
        const int index = findInsertIndexInSortedArray (comparator, data.elements.getData(), newElement, 0, numUsed);
        insert (index, newElement);
        return index;
    }

    void addUsingDefaultSort (ParameterType newElement)
    {
        DefaultElementComparator <ElementType> comparator;
        addSorted (comparator, newElement);
    }

    template <typename ElementComparator, typename TargetValueType>
    int indexOfSorted (ElementComparator& comparator, TargetValueType elementToLookFor) const
    {
        ignoreUnused (comparator); // if you pass in an object with a static compareElements() method, this
                                   // avoids getting warning messages about the parameter being unused
 
        for (int s = 0, e = numUsed;;)
        {
            if (s >= e)
                return -1;
 
            if (comparator.compareElements (elementToLookFor, data.elements [s]) == 0)
                return s;
 
            const int halfway = (s + e) / 2;
            if (halfway == s)
                return -1;
 
            if (comparator.compareElements (elementToLookFor, data.elements [halfway]) >= 0)
                s = halfway;
            else
                e = halfway;
        }
    }
 
    //==============================================================================
    void remove (int indexToRemove)
    {
        if (isPositiveAndBelow (indexToRemove, numUsed))
        {
            wassert (data.elements != nullptr);
            removeInternal (indexToRemove);
        }
    }

    ElementType removeAndReturn (const int indexToRemove)
    {
        if (isPositiveAndBelow (indexToRemove, numUsed))
        {
            wassert (data.elements != nullptr);
            ElementType removed (data.elements[indexToRemove]);
            removeInternal (indexToRemove);
            return removed;
        }
 
        return ElementType();
    }

    void remove (const ElementType* elementToRemove)
    {
        wassert (elementToRemove != nullptr);
        wassert (data.elements != nullptr);
        const int indexToRemove = int (elementToRemove - data.elements);
 
        if (! isPositiveAndBelow (indexToRemove, numUsed))
        {
            wassertfalse;
            return;
        }
 
        removeInternal (indexToRemove);
    }

    void removeFirstMatchingValue (ParameterType valueToRemove)
    {
        ElementType* const e = data.elements;
 
        for (int i = 0; i < numUsed; ++i)
        {
            if (valueToRemove == e[i])
            {
                removeInternal (i);
                break;
            }
        }
    }

    int removeAllInstancesOf (ParameterType valueToRemove)
    {
        int numRemoved = 0;
 
        for (int i = numUsed; --i >= 0;)
        {
            if (valueToRemove == data.elements[i])
            {
                removeInternal (i);
                ++numRemoved;
            }
        }
 
        return numRemoved;
    }

    template <typename PredicateType>
    int removeIf (PredicateType predicate)
    {
        int numRemoved = 0;
 
        for (int i = numUsed; --i >= 0;)
        {
            if (predicate (data.elements[i]) == true)
            {
                removeInternal (i);
                ++numRemoved;
            }
        }
 
        return numRemoved;
    }

    void removeRange (int startIndex, int numberToRemove)
    {
        const int endIndex = jlimit (0, numUsed, startIndex + numberToRemove);
        startIndex = jlimit (0, numUsed, startIndex);
        numberToRemove = endIndex - startIndex;
 
        if (numberToRemove > 0)
        {
#if 1
            ElementType* const e = data.elements + startIndex;
 
            const int numToShift = numUsed - endIndex;
            if (numToShift > 0)
                data.moveMemory (e, e + numberToRemove, numToShift);
 
            for (int i = 0; i < numberToRemove; ++i)
                e[numToShift + i].~ElementType();
#else
            ElementType* dst = data.elements + startIndex;
            ElementType* src = dst + numberToRemove;
 
            const int numToShift = numUsed - endIndex;
            for (int i = 0; i < numToShift; ++i)
                data.moveElement (dst++, std::move (*(src++)));
 
            for (int i = 0; i < numberToRemove; ++i)
                (dst++)->~ElementType();
#endif
 
            numUsed -= numberToRemove;
            minimiseStorageAfterRemoval();
        }
    }

    void removeLast (int howManyToRemove = 1)
    {
        if (howManyToRemove > numUsed)
            howManyToRemove = numUsed;
 
        for (int i = 1; i <= howManyToRemove; ++i)
            data.elements [numUsed - i].~ElementType();
 
        numUsed -= howManyToRemove;
        minimiseStorageAfterRemoval();
    }

    template <class OtherArrayType>
    void removeValuesIn (const OtherArrayType& otherArray)
    {
        if (this == &otherArray)
        {
            clear();
        }
        else
        {
            if (otherArray.size() > 0)
            {
                for (int i = numUsed; --i >= 0;)
                    if (otherArray.contains (data.elements [i]))
                        removeInternal (i);
            }
        }
    }

    template <class OtherArrayType>
    void removeValuesNotIn (const OtherArrayType& otherArray)
    {
        if (this != &otherArray)
        {
            if (otherArray.size() <= 0)
            {
                clear();
            }
            else
            {
                for (int i = numUsed; --i >= 0;)
                    if (! otherArray.contains (data.elements [i]))
                        removeInternal (i);
            }
        }
    }

    void swap (const int index1,
               const int index2)
    {
        if (isPositiveAndBelow (index1, numUsed)
             && isPositiveAndBelow (index2, numUsed))
        {
            std::swap (data.elements [index1],
                       data.elements [index2]);
        }
    }
 
    //==============================================================================
    bool minimiseStorageOverheads() noexcept
    {
        return data.shrinkToNoMoreThan (numUsed);
    }

    bool ensureStorageAllocated (const int minNumElements) noexcept
    {
        return data.ensureAllocatedSize (minNumElements);
    }
 
    //==============================================================================
    void sort()
    {
        DefaultElementComparator<ElementType> comparator;
        sort (comparator);
    }

    template <class ElementComparator>
    void sort (ElementComparator& comparator,
               const bool retainOrderOfEquivalentItems = false)
    {
        ignoreUnused (comparator); // if you pass in an object with a static compareElements() method, this
                                   // avoids getting warning messages about the parameter being unused
        sortArray (comparator, data.elements.getData(), 0, size() - 1, retainOrderOfEquivalentItems);
    }
 
private:
    //==============================================================================
    ArrayAllocationBase <ElementType> data;
    int numUsed;
 
    void removeInternal (const int indexToRemove)
    {
        --numUsed;
        ElementType* const e = data.elements + indexToRemove;
        e->~ElementType();
        const int numberToShift = numUsed - indexToRemove;
 
        if (numberToShift > 0)
            data.moveMemory (e, e + 1, static_cast<size_t>(numberToShift));
 
        minimiseStorageAfterRemoval();
    }
 
    inline void deleteAllElements() noexcept
    {
        for (int i = 0; i < numUsed; ++i)
            data.elements[i].~ElementType();
    }
 
    void minimiseStorageAfterRemoval()
    {
        CARLA_SAFE_ASSERT_RETURN(numUsed >= 0,);
 
        const size_t snumUsed = static_cast<size_t>(numUsed);
 
        if (data.numAllocated > jmax (minimumAllocatedSize, snumUsed * 2U))
            data.shrinkToNoMoreThan (jmax (snumUsed, jmax (minimumAllocatedSize, 64U / sizeof (ElementType))));
    }
};
 
}
 
#endif // WATER_ARRAY_H_INCLUDED