juce_Array.h

/*
  ==============================================================================
 
   This file is part of the JUCE library.
   Copyright (c) 2022 - Raw Material Software Limited
 
   JUCE is an open source library subject to commercial or open-source
   licensing.
 
   The code included in this file is provided 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.
 
   JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
   EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
   DISCLAIMED.
 
  ==============================================================================
*/
 
namespace juce
{
 
//==============================================================================
template <typename ElementType,
          typename TypeOfCriticalSectionToUse = DummyCriticalSection,
          int minimumAllocatedSize = 0>
class Array
{
private:
    using ParameterType = typename TypeHelpers::ParameterType<ElementType>::type;
 
public:
    //==============================================================================
    Array() = default;
 
    Array (const Array& other)
    {
        const ScopedLockType lock (other.getLock());
        values.addArray (other.values.begin(), other.values.size());
    }
 
    Array (Array&& other) noexcept
        : values (std::move (other.values))
    {
    }
 
    template <typename TypeToCreateFrom>
    explicit Array (const TypeToCreateFrom* data)
    {
        while (*values != TypeToCreateFrom())
            add (*data++);
    }
 
    template <typename TypeToCreateFrom>
    Array (const TypeToCreateFrom* data, int numValues)
    {
        values.addArray (data, numValues);
    }
 
    Array (const ElementType& singleElementToAdd)
    {
        add (singleElementToAdd);
    }
 
    Array (ElementType&& singleElementToAdd)
    {
        add (std::move (singleElementToAdd));
    }
 
    template <typename... OtherElements>
    Array (const ElementType& firstNewElement, OtherElements&&... otherElements)
    {
        values.add (firstNewElement, std::forward<OtherElements> (otherElements)...);
    }
 
    template <typename... OtherElements>
    Array (ElementType&& firstNewElement, OtherElements&&... otherElements)
    {
        values.add (std::move (firstNewElement), std::forward<OtherElements> (otherElements)...);
    }
 
    template <typename TypeToCreateFrom>
    Array (const std::initializer_list<TypeToCreateFrom>& items)
    {
        addArray (items);
    }
 
    ~Array() = default;
 
    Array& operator= (const Array& other)
    {
        if (this != &other)
        {
            auto otherCopy (other);
            swapWith (otherCopy);
        }
 
        return *this;
    }
 
    Array& operator= (Array&& other) noexcept
    {
        const ScopedLockType lock (getLock());
        values = std::move (other.values);
        return *this;
    }
 
    //==============================================================================
    template <class OtherArrayType>
    bool operator== (const OtherArrayType& other) const
    {
        const ScopedLockType lock (getLock());
        const typename OtherArrayType::ScopedLockType lock2 (other.getLock());
        return values == other;
    }
 
    template <class OtherArrayType>
    bool operator!= (const OtherArrayType& other) const
    {
        return ! operator== (other);
    }
 
    //==============================================================================
    void clear()
    {
        const ScopedLockType lock (getLock());
        clearQuick();
        values.setAllocatedSize (0);
    }
 
    void clearQuick()
    {
        const ScopedLockType lock (getLock());
        values.clear();
    }
 
    void fill (const ParameterType& newValue) noexcept
    {
        const ScopedLockType lock (getLock());
 
        for (auto& e : *this)
            e = newValue;
    }
 
    //==============================================================================
    inline int size() const noexcept
    {
        const ScopedLockType lock (getLock());
        return values.size();
    }
 
    inline bool isEmpty() const noexcept
    {
        return size() == 0;
    }
 
    ElementType operator[] (int index) const
    {
        const ScopedLockType lock (getLock());
        return values.getValueWithDefault (index);
    }
 
    inline ElementType getUnchecked (int index) const
    {
        const ScopedLockType lock (getLock());
        return values[index];
    }
 
    inline ElementType& getReference (int index) noexcept
    {
        const ScopedLockType lock (getLock());
        return values[index];
    }
 
    inline const ElementType& getReference (int index) const noexcept
    {
        const ScopedLockType lock (getLock());
        return values[index];
    }
 
    inline ElementType getFirst() const noexcept
    {
        const ScopedLockType lock (getLock());
        return values.getFirst();
    }
 
    inline ElementType getLast() const noexcept
    {
        const ScopedLockType lock (getLock());
        return values.getLast();
    }
 
    inline ElementType* getRawDataPointer() noexcept
    {
        return values.begin();
    }
 
    inline const ElementType* getRawDataPointer() const noexcept
    {
        return values.begin();
    }
 
    //==============================================================================
    inline ElementType* begin() noexcept
    {
        return values.begin();
    }
 
    inline const ElementType* begin() const noexcept
    {
        return values.begin();
    }
 
    inline ElementType* end() noexcept
    {
        return values.end();
    }
 
    inline const ElementType* end() const noexcept
    {
        return values.end();
    }
 
    inline ElementType* data() noexcept
    {
        return begin();
    }
 
    inline const ElementType* data() const noexcept
    {
        return begin();
    }
 
    //==============================================================================
    int indexOf (ParameterType elementToLookFor) const
    {
        const ScopedLockType lock (getLock());
        auto e = values.begin();
        auto endPtr = values.end();
 
        for (; e != endPtr; ++e)
            if (exactlyEqual (elementToLookFor, *e))
                return static_cast<int> (e - values.begin());
 
        return -1;
    }
 
    bool contains (ParameterType elementToLookFor) const
    {
        const ScopedLockType lock (getLock());
        auto e = values.begin();
        auto endPtr = values.end();
 
        for (; e != endPtr; ++e)
            if (exactlyEqual (elementToLookFor, *e))
                return true;
 
        return false;
    }
 
    //==============================================================================
    void add (const ElementType& newElement)
    {
        const ScopedLockType lock (getLock());
        values.add (newElement);
    }
 
    void add (ElementType&& newElement)
    {
        const ScopedLockType lock (getLock());
        values.add (std::move (newElement));
    }
 
    template <typename... OtherElements>
    void add (const ElementType& firstNewElement, OtherElements&&... otherElements)
    {
        const ScopedLockType lock (getLock());
        values.add (firstNewElement, std::forward<OtherElements> (otherElements)...);
    }
 
    template <typename... OtherElements>
    void add (ElementType&& firstNewElement, OtherElements&&... otherElements)
    {
        const ScopedLockType lock (getLock());
        values.add (std::move (firstNewElement), std::forward<OtherElements> (otherElements)...);
    }
 
    void insert (int indexToInsertAt, ParameterType newElement)
    {
        const ScopedLockType lock (getLock());
        values.insert (indexToInsertAt, newElement, 1);
    }
 
    void insertMultiple (int indexToInsertAt, ParameterType newElement,
                         int numberOfTimesToInsertIt)
    {
        if (numberOfTimesToInsertIt > 0)
        {
            const ScopedLockType lock (getLock());
            values.insert (indexToInsertAt, newElement, numberOfTimesToInsertIt);
        }
    }
 
    void insertArray (int indexToInsertAt,
                      const ElementType* newElements,
                      int numberOfElements)
    {
        if (numberOfElements > 0)
        {
            const ScopedLockType lock (getLock());
            values.insertArray (indexToInsertAt, newElements, numberOfElements);
        }
    }
 
    bool addIfNotAlreadyThere (ParameterType newElement)
    {
        const ScopedLockType lock (getLock());
 
        if (contains (newElement))
            return false;
 
        add (newElement);
        return true;
    }
 
    void set (int indexToChange, ParameterType newValue)
    {
        if (indexToChange >= 0)
        {
            const ScopedLockType lock (getLock());
 
            if (indexToChange < values.size())
                values[indexToChange] = newValue;
            else
                values.add (newValue);
        }
        else
        {
            jassertfalse;
        }
    }
 
    void setUnchecked (int indexToChange, ParameterType newValue)
    {
        const ScopedLockType lock (getLock());
        jassert (isPositiveAndBelow (indexToChange, values.size()));
        values[indexToChange] = newValue;
    }
 
    template <typename Type>
    void addArray (const Type* elementsToAdd, int numElementsToAdd)
    {
        const ScopedLockType lock (getLock());
 
        if (numElementsToAdd > 0)
            values.addArray (elementsToAdd, numElementsToAdd);
    }
 
    template <typename TypeToCreateFrom>
    void addArray (const std::initializer_list<TypeToCreateFrom>& items)
    {
        const ScopedLockType lock (getLock());
        values.addArray (items);
    }
 
    template <typename Type>
    void addNullTerminatedArray (const Type* const* elementsToAdd)
    {
        int num = 0;
 
        for (auto 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());
        values.swapWith (otherArray.values);
    }
 
    template <class OtherArrayType>
    void addArray (const OtherArrayType& arrayToAddFrom)
    {
        const typename OtherArrayType::ScopedLockType lock1 (arrayToAddFrom.getLock());
        const ScopedLockType lock2 (getLock());
 
        values.addArray (arrayToAddFrom);
    }
 
    template <class OtherArrayType>
    std::enable_if_t<! std::is_pointer_v<OtherArrayType>, void>
    addArray (const OtherArrayType& arrayToAddFrom,
              int startIndex,
              int numElementsToAdd = -1)
    {
        const typename OtherArrayType::ScopedLockType lock1 (arrayToAddFrom.getLock());
        const ScopedLockType lock2 (getLock());
 
        values.addArray (arrayToAddFrom, startIndex, numElementsToAdd);
    }
 
    void resize (int targetNumItems)
    {
        jassert (targetNumItems >= 0);
        auto numToAdd = targetNumItems - values.size();
 
        if (numToAdd > 0)
            insertMultiple (values.size(), ElementType(), numToAdd);
        else if (numToAdd < 0)
            removeRange (targetNumItems, -numToAdd);
    }
 
    template <class ElementComparator>
    int addSorted (ElementComparator& comparator, ParameterType newElement)
    {
        const ScopedLockType lock (getLock());
        auto index = findInsertIndexInSortedArray (comparator, values.begin(), newElement, 0, values.size());
        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 remove (int indexToRemove)
    {
        const ScopedLockType lock (getLock());
 
        if (isPositiveAndBelow (indexToRemove, values.size()))
            removeInternal (indexToRemove);
    }
 
    ElementType removeAndReturn (int indexToRemove)
    {
        const ScopedLockType lock (getLock());
 
        if (isPositiveAndBelow (indexToRemove, values.size()))
        {
            ElementType removed (values[indexToRemove]);
            removeInternal (indexToRemove);
            return removed;
        }
 
        return ElementType();
    }
 
    void remove (const ElementType* elementToRemove)
    {
        jassert (elementToRemove != nullptr);
        const ScopedLockType lock (getLock());
 
        jassert (values.begin() != nullptr);
        auto indexToRemove = (int) (elementToRemove - values.begin());
 
        if (! isPositiveAndBelow (indexToRemove, values.size()))
        {
            jassertfalse;
            return;
        }
 
        removeInternal (indexToRemove);
    }
 
    int removeFirstMatchingValue (ParameterType valueToRemove)
    {
        const ScopedLockType lock (getLock());
        auto* e = values.begin();
 
        for (int i = 0; i < values.size(); ++i)
        {
            if (valueToRemove == e[i])
            {
                removeInternal (i);
                return i;
            }
        }
 
        return -1;
    }
 
    int removeAllInstancesOf (ParameterType valueToRemove)
    {
        int numRemoved = 0;
        const ScopedLockType lock (getLock());
 
        for (int i = values.size(); --i >= 0;)
        {
            if (valueToRemove == values[i])
            {
                removeInternal (i);
                ++numRemoved;
            }
        }
 
        return numRemoved;
    }
 
    template <typename PredicateType>
    int removeIf (PredicateType&& predicate)
    {
        int numRemoved = 0;
        const ScopedLockType lock (getLock());
 
        for (int i = values.size(); --i >= 0;)
        {
            if (predicate (values[i]))
            {
                removeInternal (i);
                ++numRemoved;
            }
        }
 
        return numRemoved;
    }
 
    void removeRange (int startIndex, int numberToRemove)
    {
        const ScopedLockType lock (getLock());
 
        auto endIndex = jlimit (0, values.size(), startIndex + numberToRemove);
        startIndex    = jlimit (0, values.size(), startIndex);
        numberToRemove = endIndex - startIndex;
 
        if (numberToRemove > 0)
        {
            values.removeElements (startIndex, numberToRemove);
            minimiseStorageAfterRemoval();
        }
    }
 
    void removeLast (int howManyToRemove = 1)
    {
        jassert (howManyToRemove >= 0);
 
        if (howManyToRemove > 0)
        {
            const ScopedLockType lock (getLock());
 
            if (howManyToRemove > values.size())
                howManyToRemove = values.size();
 
            values.removeElements (values.size() - howManyToRemove, 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 = values.size(); --i >= 0;)
                    if (otherArray.contains (values[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 = values.size(); --i >= 0;)
                    if (! otherArray.contains (values[i]))
                        removeInternal (i);
            }
        }
    }
 
    void swap (int index1, int index2)
    {
        const ScopedLockType lock (getLock());
        values.swap (index1, index2);
    }
 
    void move (int currentIndex, int newIndex) noexcept
    {
        if (currentIndex != newIndex)
        {
            const ScopedLockType lock (getLock());
            values.move (currentIndex, newIndex);
        }
    }
 
    //==============================================================================
    void minimiseStorageOverheads()
    {
        const ScopedLockType lock (getLock());
        values.shrinkToNoMoreThan (values.size());
    }
 
    void ensureStorageAllocated (int minNumElements)
    {
        const ScopedLockType lock (getLock());
        values.ensureAllocatedSize (minNumElements);
    }
 
    //==============================================================================
    void sort()
    {
        DefaultElementComparator<ElementType> comparator;
        sort (comparator);
    }
 
    template <class ElementComparator>
    void sort (ElementComparator& comparator, bool retainOrderOfEquivalentItems = false);
 
    //==============================================================================
    inline const TypeOfCriticalSectionToUse& getLock() const noexcept      { return values; }
 
    using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
 
 
    //==============================================================================
   #ifndef DOXYGEN
    [[deprecated ("This method has been replaced by a more flexible templated version and renamed "
                 "to swapWith to be more consistent with the names used in other classes.")]]
    void swapWithArray (Array& other) noexcept { swapWith (other); }
   #endif
 
private:
    //==============================================================================
    ArrayBase<ElementType, TypeOfCriticalSectionToUse> values;
 
    void removeInternal (int indexToRemove)
    {
        values.removeElements (indexToRemove, 1);
        minimiseStorageAfterRemoval();
    }
 
    void minimiseStorageAfterRemoval()
    {
        if (values.capacity() > jmax (minimumAllocatedSize, values.size() * 2))
            values.shrinkToNoMoreThan (jmax (values.size(), jmax (minimumAllocatedSize, 64 / (int) sizeof (ElementType))));
    }
};
 
//==============================================================================
template <typename ElementType, typename TypeOfCriticalSectionToUse, int minimumAllocatedSize>
template <typename ElementComparator, typename TargetValueType>
int Array<ElementType, TypeOfCriticalSectionToUse, minimumAllocatedSize>::indexOfSorted (
    [[maybe_unused]] ElementComparator& comparator,
    TargetValueType elementToLookFor) const
{
    const ScopedLockType lock (getLock());
 
    for (int s = 0, e = values.size();;)
    {
        if (s >= e)
            return -1;
 
        if (comparator.compareElements (elementToLookFor, values[s]) == 0)
            return s;
 
        auto halfway = (s + e) / 2;
 
        if (halfway == s)
            return -1;
 
        if (comparator.compareElements (elementToLookFor, values[halfway]) >= 0)
            s = halfway;
        else
            e = halfway;
    }
}
 
template <typename ElementType, typename TypeOfCriticalSectionToUse, int minimumAllocatedSize>
template <class ElementComparator>
void Array<ElementType, TypeOfCriticalSectionToUse, minimumAllocatedSize>::sort (
    [[maybe_unused]] ElementComparator& comparator,
    bool retainOrderOfEquivalentItems)
{
    const ScopedLockType lock (getLock());
    sortArray (comparator, values.begin(), 0, size() - 1, retainOrderOfEquivalentItems);
}
 
} // namespace juce