juce_Array.h

Go to the documentation of this file.

/*
  ==============================================================================
 
   This file is part of the juce_core module of the JUCE library.
   Copyright (c) 2015 - ROLI Ltd.
 
   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 THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD
   TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN
   NO EVENT SHALL THE AUTHOR 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.
 
   ------------------------------------------------------------------------------
 
   NOTE! This permissive ISC license applies ONLY to files within the juce_core module!
   All other JUCE modules are covered by a dual GPL/commercial license, so if you are
   using any other modules, be sure to check that you also comply with their license.
 
   For more details, visit www.juce.com
 
  ==============================================================================
*/
 
#ifndef JUCE_ARRAY_H_INCLUDED
#define JUCE_ARRAY_H_INCLUDED
 
 
//==============================================================================
template <typename ElementType,
          typename TypeOfCriticalSectionToUse = DummyCriticalSection,
          int minimumAllocatedSize = 0>
class Array
{
private:
    typedef PARAMETER_TYPE (ElementType) ParameterType;
 
public:
    //==============================================================================
    Array() noexcept   : numUsed (0)
    {
    }
 
    Array (const Array<ElementType, TypeOfCriticalSectionToUse>& other)
    {
        const ScopedLockType lock (other.getLock());
        numUsed = other.numUsed;
        data.setAllocatedSize (other.numUsed);
 
        for (int i = 0; i < numUsed; ++i)
            new (data.elements + i) ElementType (other.data.elements[i]);
    }
 
   #if JUCE_COMPILER_SUPPORTS_MOVE_SEMANTICS
    Array (Array<ElementType, TypeOfCriticalSectionToUse>&& other) noexcept
        : data (static_cast<ArrayAllocationBase<ElementType, TypeOfCriticalSectionToUse>&&> (other.data)),
          numUsed (other.numUsed)
    {
        other.numUsed = 0;
    }
   #endif
 
    template <typename TypeToCreateFrom>
    explicit Array (const TypeToCreateFrom* values)  : numUsed (0)
    {
        while (*values != TypeToCreateFrom())
            add (*values++);
    }
 
    template <typename TypeToCreateFrom>
    Array (const TypeToCreateFrom* values, int numValues)  : numUsed (numValues)
    {
        data.setAllocatedSize (numValues);
 
        for (int i = 0; i < numValues; ++i)
            new (data.elements + i) ElementType (values[i]);
    }
 
   #if JUCE_COMPILER_SUPPORTS_INITIALIZER_LISTS
    template <typename TypeToCreateFrom>
    Array (const std::initializer_list<TypeToCreateFrom>& items)  : numUsed (0)
    {
        addArray (items);
    }
   #endif
 
    ~Array()
    {
        deleteAllElements();
    }
 
    Array& operator= (const Array& other)
    {
        if (this != &other)
        {
            Array<ElementType, TypeOfCriticalSectionToUse> otherCopy (other);
            swapWith (otherCopy);
        }
 
        return *this;
    }
 
   #if JUCE_COMPILER_SUPPORTS_MOVE_SEMANTICS
    Array& operator= (Array&& other) noexcept
    {
        const ScopedLockType lock (getLock());
        deleteAllElements();
        data = static_cast<ArrayAllocationBase<ElementType, TypeOfCriticalSectionToUse>&&> (other.data);
        numUsed = other.numUsed;
        other.numUsed = 0;
        return *this;
    }
   #endif
 
    //==============================================================================
    template <class OtherArrayType>
    bool operator== (const OtherArrayType& other) const
    {
        const ScopedLockType lock (getLock());
        const typename OtherArrayType::ScopedLockType lock2 (other.getLock());
 
        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()
    {
        const ScopedLockType lock (getLock());
        deleteAllElements();
        data.setAllocatedSize (0);
        numUsed = 0;
    }
 
    void clearQuick()
    {
        const ScopedLockType lock (getLock());
        deleteAllElements();
        numUsed = 0;
    }
 
    //==============================================================================
    inline int size() const noexcept
    {
        return numUsed;
    }
 
    ElementType operator[] (const int index) const
    {
        const ScopedLockType lock (getLock());
 
        if (isPositiveAndBelow (index, numUsed))
        {
            jassert (data.elements != nullptr);
            return data.elements [index];
        }
 
        return ElementType();
    }
 
    inline ElementType getUnchecked (const int index) const
    {
        const ScopedLockType lock (getLock());
        jassert (isPositiveAndBelow (index, numUsed) && data.elements != nullptr);
        return data.elements [index];
    }
 
    inline ElementType& getReference (const int index) const noexcept
    {
        const ScopedLockType lock (getLock());
        jassert (isPositiveAndBelow (index, numUsed) && data.elements != nullptr);
        return data.elements [index];
    }
 
    inline ElementType getFirst() const
    {
        const ScopedLockType lock (getLock());
 
        if (numUsed > 0)
        {
            jassert (data.elements != nullptr);
            return data.elements[0];
        }
 
        return ElementType();
    }
 
    inline ElementType getLast() const
    {
        const ScopedLockType lock (getLock());
 
        if (numUsed > 0)
        {
            jassert (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
    {
       #if JUCE_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 ScopedLockType lock (getLock());
        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 ScopedLockType lock (getLock());
        const ElementType* e = data.elements.getData();
        const ElementType* const end_ = e + numUsed;
 
        for (; e != end_; ++e)
            if (elementToLookFor == *e)
                return true;
 
        return false;
    }
 
    //==============================================================================
    void add (const ElementType& newElement)
    {
        const ScopedLockType lock (getLock());
        data.ensureAllocatedSize (numUsed + 1);
        new (data.elements + numUsed++) ElementType (newElement);
    }
 
   #if JUCE_COMPILER_SUPPORTS_MOVE_SEMANTICS
 
    void add (ElementType&& newElement)
    {
        const ScopedLockType lock (getLock());
        data.ensureAllocatedSize (numUsed + 1);
        new (data.elements + numUsed++) ElementType (static_cast<ElementType&&> (newElement));
    }
   #endif
 
    void insert (int indexToInsertAt, ParameterType newElement)
    {
        const ScopedLockType lock (getLock());
        data.ensureAllocatedSize (numUsed + 1);
        jassert (data.elements != nullptr);
 
        if (isPositiveAndBelow (indexToInsertAt, numUsed))
        {
            ElementType* const insertPos = data.elements + indexToInsertAt;
            const int numberToMove = numUsed - indexToInsertAt;
 
            if (numberToMove > 0)
                memmove (insertPos + 1, insertPos, ((size_t) numberToMove) * sizeof (ElementType));
 
            new (insertPos) ElementType (newElement);
            ++numUsed;
        }
        else
        {
            new (data.elements + numUsed++) ElementType (newElement);
        }
    }
 
    void insertMultiple (int indexToInsertAt, ParameterType newElement,
                         int numberOfTimesToInsertIt)
    {
        if (numberOfTimesToInsertIt > 0)
        {
            const ScopedLockType lock (getLock());
            data.ensureAllocatedSize (numUsed + numberOfTimesToInsertIt);
            ElementType* insertPos;
 
            if (isPositiveAndBelow (indexToInsertAt, numUsed))
            {
                insertPos = data.elements + indexToInsertAt;
                const int numberToMove = numUsed - indexToInsertAt;
                memmove (insertPos + numberOfTimesToInsertIt, insertPos, ((size_t) numberToMove) * sizeof (ElementType));
            }
            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
            }
        }
    }
 
    void insertArray (int indexToInsertAt,
                      const ElementType* newElements,
                      int numberOfElements)
    {
        if (numberOfElements > 0)
        {
            const ScopedLockType lock (getLock());
            data.ensureAllocatedSize (numUsed + numberOfElements);
            ElementType* insertPos = data.elements;
 
            if (isPositiveAndBelow (indexToInsertAt, numUsed))
            {
                insertPos += indexToInsertAt;
                const int numberToMove = numUsed - indexToInsertAt;
                memmove (insertPos + numberOfElements, insertPos, numberToMove * sizeof (ElementType));
            }
            else
            {
                insertPos += numUsed;
            }
 
            numUsed += numberOfElements;
 
            while (--numberOfElements >= 0)
                new (insertPos++) ElementType (*newElements++);
        }
    }
 
    void addIfNotAlreadyThere (ParameterType newElement)
    {
        const ScopedLockType lock (getLock());
 
        if (! contains (newElement))
            add (newElement);
    }
 
    void set (const int indexToChange, ParameterType newValue)
    {
        jassert (indexToChange >= 0);
        const ScopedLockType lock (getLock());
 
        if (isPositiveAndBelow (indexToChange, numUsed))
        {
            jassert (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)
    {
        const ScopedLockType lock (getLock());
        jassert (isPositiveAndBelow (indexToChange, numUsed));
        data.elements [indexToChange] = newValue;
    }
 
    template <typename Type>
    void addArray (const Type* elementsToAdd, int numElementsToAdd)
    {
        const ScopedLockType lock (getLock());
 
        if (numElementsToAdd > 0)
        {
            data.ensureAllocatedSize (numUsed + numElementsToAdd);
 
            while (--numElementsToAdd >= 0)
            {
                new (data.elements + numUsed) ElementType (*elementsToAdd++);
                ++numUsed;
            }
        }
    }
 
   #if JUCE_COMPILER_SUPPORTS_INITIALIZER_LISTS
    template <typename TypeToCreateFrom>
    void addArray (const std::initializer_list<TypeToCreateFrom>& items)
    {
        const ScopedLockType lock (getLock());
        data.ensureAllocatedSize (numUsed + (int) items.size());
 
        for (auto& item : items)
        {
            new (data.elements + numUsed) ElementType (item);
            ++numUsed;
        }
    }
   #endif
 
    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
    {
        const ScopedLockType lock1 (getLock());
        const typename OtherArrayType::ScopedLockType lock2 (otherArray.getLock());
        data.swapWith (otherArray.data);
        std::swap (numUsed, otherArray.numUsed);
    }
 
    template <class OtherArrayType>
    void addArray (const OtherArrayType& arrayToAddFrom,
                   int startIndex = 0,
                   int numElementsToAdd = -1)
    {
        const typename OtherArrayType::ScopedLockType lock1 (arrayToAddFrom.getLock());
 
        {
            const ScopedLockType lock2 (getLock());
 
            if (startIndex < 0)
            {
                jassertfalse;
                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)
    {
        jassert (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 ScopedLockType lock (getLock());
        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
    {
        (void) comparator;  // if you pass in an object with a static compareElements() method, this
                            // avoids getting warning messages about the parameter being unused
 
        const ScopedLockType lock (getLock());
 
        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;
        }
    }
 
    //==============================================================================
    ElementType remove (const int indexToRemove)
    {
        const ScopedLockType lock (getLock());
 
        if (isPositiveAndBelow (indexToRemove, numUsed))
        {
            jassert (data.elements != nullptr);
            ElementType removed (data.elements[indexToRemove]);
            removeInternal (indexToRemove);
            return removed;
        }
 
        return ElementType();
    }
 
    void removeFirstMatchingValue (ParameterType valueToRemove)
    {
        const ScopedLockType lock (getLock());
        ElementType* const e = data.elements;
 
        for (int i = 0; i < numUsed; ++i)
        {
            if (valueToRemove == e[i])
            {
                removeInternal (i);
                break;
            }
        }
    }
 
    void removeAllInstancesOf (ParameterType valueToRemove)
    {
        const ScopedLockType lock (getLock());
 
        for (int i = numUsed; --i >= 0;)
            if (valueToRemove == data.elements[i])
                removeInternal (i);
    }
 
    void removeRange (int startIndex, int numberToRemove)
    {
        const ScopedLockType lock (getLock());
        const int endIndex = jlimit (0, numUsed, startIndex + numberToRemove);
        startIndex = jlimit (0, numUsed, startIndex);
 
        if (endIndex > startIndex)
        {
            ElementType* const e = data.elements + startIndex;
 
            numberToRemove = endIndex - startIndex;
            for (int i = 0; i < numberToRemove; ++i)
                e[i].~ElementType();
 
            const int numToShift = numUsed - endIndex;
            if (numToShift > 0)
                memmove (e, e + numberToRemove, ((size_t) numToShift) * sizeof (ElementType));
 
            numUsed -= numberToRemove;
            minimiseStorageAfterRemoval();
        }
    }
 
    void removeLast (int howManyToRemove = 1)
    {
        const ScopedLockType lock (getLock());
 
        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)
    {
        const typename OtherArrayType::ScopedLockType lock1 (otherArray.getLock());
        const ScopedLockType lock2 (getLock());
 
        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)
    {
        const typename OtherArrayType::ScopedLockType lock1 (otherArray.getLock());
        const ScopedLockType lock2 (getLock());
 
        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)
    {
        const ScopedLockType lock (getLock());
 
        if (isPositiveAndBelow (index1, numUsed)
             && isPositiveAndBelow (index2, numUsed))
        {
            std::swap (data.elements [index1],
                       data.elements [index2]);
        }
    }
 
    void move (const int currentIndex, int newIndex) noexcept
    {
        if (currentIndex != newIndex)
        {
            const ScopedLockType lock (getLock());
 
            if (isPositiveAndBelow (currentIndex, numUsed))
            {
                if (! isPositiveAndBelow (newIndex, numUsed))
                    newIndex = numUsed - 1;
 
                char tempCopy [sizeof (ElementType)];
                memcpy (tempCopy, data.elements + currentIndex, sizeof (ElementType));
 
                if (newIndex > currentIndex)
                {
                    memmove (data.elements + currentIndex,
                             data.elements + currentIndex + 1,
                             sizeof (ElementType) * (size_t) (newIndex - currentIndex));
                }
                else
                {
                    memmove (data.elements + newIndex + 1,
                             data.elements + newIndex,
                             sizeof (ElementType) * (size_t) (currentIndex - newIndex));
                }
 
                memcpy (data.elements + newIndex, tempCopy, sizeof (ElementType));
            }
        }
    }
 
    //==============================================================================
    void minimiseStorageOverheads()
    {
        const ScopedLockType lock (getLock());
        data.shrinkToNoMoreThan (numUsed);
    }
 
    void ensureStorageAllocated (const int minNumElements)
    {
        const ScopedLockType lock (getLock());
        data.ensureAllocatedSize (minNumElements);
    }
 
    //==============================================================================
    template <class ElementComparator>
    void sort (ElementComparator& comparator,
               const bool retainOrderOfEquivalentItems = false) const
    {
        const ScopedLockType lock (getLock());
        (void) 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);
    }
 
    //==============================================================================
    inline const TypeOfCriticalSectionToUse& getLock() const noexcept      { return data; }
 
    typedef typename TypeOfCriticalSectionToUse::ScopedLockType ScopedLockType;
 
 
    //==============================================================================
   #ifndef DOXYGEN
    // Note that the swapWithArray method has been replaced by a more flexible templated version,
    // and renamed "swapWith" to be more consistent with the names used in other classes.
    JUCE_DEPRECATED_WITH_BODY (void swapWithArray (Array& other) noexcept, { swapWith (other); })
   #endif
 
private:
    //==============================================================================
    ArrayAllocationBase <ElementType, TypeOfCriticalSectionToUse> 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)
            memmove (e, e + 1, ((size_t) numberToShift) * sizeof (ElementType));
 
        minimiseStorageAfterRemoval();
    }
 
    inline void deleteAllElements() noexcept
    {
        for (int i = 0; i < numUsed; ++i)
            data.elements[i].~ElementType();
    }
 
    void minimiseStorageAfterRemoval()
    {
        if (data.numAllocated > jmax (minimumAllocatedSize, numUsed * 2))
            data.shrinkToNoMoreThan (jmax (numUsed, jmax (minimumAllocatedSize, 64 / (int) sizeof (ElementType))));
    }
};
 
 
#endif   // JUCE_ARRAY_H_INCLUDED