OwnedArray.h

Go to the documentation of this file.

/*
  ==============================================================================
 
   This file is part of the Water library.
   Copyright (c) 2016 ROLI Ltd.
   Copyright (C) 2017-2022 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_OWNEDARRAY_H_INCLUDED
#define WATER_OWNEDARRAY_H_INCLUDED
 
#include "ArrayAllocationBase.h"
 
#include "CarlaScopeUtils.hpp"
 
namespace water {
 
//==============================================================================
template <class ObjectClass>
 
class OwnedArray
{
public:
    //==============================================================================
    OwnedArray() noexcept
        : numUsed (0)
    {
    }

    ~OwnedArray()
    {
        deleteAllObjects();
    }
 
    //==============================================================================
    void clear (bool deleteObjects = true)
    {
        if (deleteObjects)
            deleteAllObjects();
 
        data.setAllocatedSize (0);
        numUsed = 0;
    }
 
    //==============================================================================
    void clearQuick (bool deleteObjects)
    {
        if (deleteObjects)
            deleteAllObjects();
 
        numUsed = 0;
    }
 
    //==============================================================================
    inline size_t size() const noexcept
    {
        return numUsed;
    }

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

    inline ObjectClass* operator[] (const size_t index) const noexcept
    {
        if (index < numUsed)
        {
            CARLA_SAFE_ASSERT_RETURN(data.elements != nullptr, nullptr);
            return data.elements [index];
        }
 
        return nullptr;
    }

    inline ObjectClass* getUnchecked (const int index) const noexcept
    {
        return data.elements [index];
    }

    inline ObjectClass* getFirst() const noexcept
    {
        if (numUsed > 0)
        {
            CARLA_SAFE_ASSERT_RETURN(data.elements != nullptr, nullptr);
            return data.elements [0];
        }
 
        return nullptr;
    }

    inline ObjectClass* getLast() const noexcept
    {
        if (numUsed > 0)
        {
            CARLA_SAFE_ASSERT_RETURN(data.elements != nullptr, nullptr);
            return data.elements [numUsed - 1];
        }
 
        return nullptr;
    }

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

    inline ObjectClass** 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 (const ObjectClass* objectToLookFor) const noexcept
    {
        ObjectClass* const* e = data.elements.getData();
        ObjectClass* const* const end_ = e + numUsed;
 
        for (; e != end_; ++e)
            if (objectToLookFor == *e)
                return static_cast<int> (e - data.elements.getData());
 
        return -1;
    }

    bool contains (const ObjectClass* objectToLookFor) const noexcept
    {
        ObjectClass* const* e = data.elements.getData();
        ObjectClass* const* const end_ = e + numUsed;
 
        for (; e != end_; ++e)
            if (objectToLookFor == *e)
                return true;
 
        return false;
    }
 
    //==============================================================================
    ObjectClass* add (ObjectClass* newObject) noexcept
    {
        if (! data.ensureAllocatedSize (numUsed + 1))
            return nullptr;
 
        data.elements [numUsed++] = newObject;
        return newObject;
    }

    ObjectClass* insert (int indexToInsertAt, ObjectClass* newObject) noexcept
    {
        if (indexToInsertAt < 0)
            return add (newObject);
 
        size_t uindexToInsertAt = static_cast<size_t>(indexToInsertAt);
 
        if (uindexToInsertAt > numUsed)
            uindexToInsertAt = numUsed;
 
        if (! data.ensureAllocatedSize (numUsed + 1))
            return nullptr;
 
        ObjectClass** const e = data.elements + uindexToInsertAt;
        const int numToMove = numUsed - uindexToInsertAt;
 
        if (numToMove > 0)
            std::memmove (e + 1, e, sizeof (ObjectClass*) * (size_t) numToMove);
 
        *e = newObject;
        ++numUsed;
        return newObject;
    }

    void insertArray (const size_t indexToInsertAt,
                      ObjectClass* const* newObjects,
                      const size_t numberOfElements)
    {
        if (numberOfElements > 0)
        {
            data.ensureAllocatedSize (numUsed + numberOfElements);
            ObjectClass** insertPos = data.elements;
 
            if (indexToInsertAt < numUsed)
            {
                insertPos += indexToInsertAt;
                const size_t numberToMove = numUsed - indexToInsertAt;
                std::memmove (insertPos + numberOfElements, insertPos, numberToMove * sizeof (ObjectClass*));
            }
            else
            {
                insertPos += numUsed;
            }
 
            numUsed += numberOfElements;
 
            for (size_t i=0; i < numberOfElements; ++i)
                *insertPos++ = *newObjects++;
        }
    }

    bool addIfNotAlreadyThere (ObjectClass* newObject) noexcept
    {
        if (contains (newObject))
            return false;
 
        return add (newObject) != nullptr;
    }

    ObjectClass* set (int indexToChange, ObjectClass* newObject, bool deleteOldElement = true)
    {
        if (indexToChange >= 0)
        {
            CarlaScopedPointer<ObjectClass> toDelete;
 
            {
                if (indexToChange < numUsed)
                {
                    if (deleteOldElement)
                    {
                        toDelete = data.elements [indexToChange];
 
                        if (toDelete == newObject)
                            toDelete.release();
                    }
 
                    data.elements [indexToChange] = newObject;
                }
                else
                {
                    data.ensureAllocatedSize (numUsed + 1);
                    data.elements [numUsed++] = newObject;
                }
            }
        }
        else
        {
            wassertfalse; // you're trying to set an object at a negative index, which doesn't have
                          // any effect - but since the object is not being added, it may be leaking..
        }
 
        return newObject;
    }

    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;
 
        data.ensureAllocatedSize (numUsed + numElementsToAdd);
        wassert (numElementsToAdd <= 0 || data.elements != nullptr);
 
        while (--numElementsToAdd >= 0)
        {
            data.elements [numUsed] = arrayToAddFrom.getUnchecked (startIndex++);
            ++numUsed;
        }
    }

    template <class OtherArrayType>
    void addCopiesOf (const OtherArrayType& arrayToAddFrom,
                      size_t startIndex = 0,
                      int numElementsToAdd = -1)
    {
        if (numElementsToAdd < 0 || startIndex + numElementsToAdd > arrayToAddFrom.size())
            numElementsToAdd = arrayToAddFrom.size() - startIndex;
 
        data.ensureAllocatedSize (numUsed + numElementsToAdd);
        wassert (numElementsToAdd <= 0 || data.elements != nullptr);
 
        while (--numElementsToAdd >= 0)
            data.elements [numUsed++] = createCopyIfNotNull (arrayToAddFrom.getUnchecked (startIndex++));
    }

    template <class ElementComparator>
    int addSorted (ElementComparator& comparator, ObjectClass* const newObject) noexcept
    {
        ignoreUnused (comparator); // if you pass in an object with a static compareElements() method, this
                                   // avoids getting warning messages about the parameter being unused
        const int index = findInsertIndexInSortedArray (comparator, data.elements.getData(), newObject, 0, numUsed);
        insert (index, newObject);
        return index;
    }

    template <typename ElementComparator>
    int indexOfSorted (ElementComparator& comparator, const ObjectClass* const objectToLookFor) const noexcept
    {
        ignoreUnused (comparator);
        int s = 0, e = numUsed;
 
        while (s < e)
        {
            if (comparator.compareElements (objectToLookFor, data.elements [s]) == 0)
                return s;
 
            const int halfway = (s + e) / 2;
            if (halfway == s)
                break;
 
            if (comparator.compareElements (objectToLookFor, data.elements [halfway]) >= 0)
                s = halfway;
            else
                e = halfway;
        }
 
        return -1;
    }
 
    //==============================================================================
    void remove (const size_t indexToRemove, bool deleteObject = true)
    {
        CarlaScopedPointer<ObjectClass> toDelete;
 
        if (indexToRemove < numUsed)
        {
            ObjectClass** const e = data.elements + indexToRemove;
 
            if (deleteObject)
                toDelete = *e;
 
            --numUsed;
            const size_t numToShift = numUsed - indexToRemove;
 
            if (numToShift > 0)
                std::memmove (e, e + 1, sizeof (ObjectClass*) * numToShift);
        }
 
        if ((numUsed << 1) < data.numAllocated)
            minimiseStorageOverheads();
    }

    ObjectClass* removeAndReturn (const size_t indexToRemove)
    {
        ObjectClass* removedItem = nullptr;
        if (indexToRemove < numUsed)
        {
            ObjectClass** const e = data.elements + indexToRemove;
            removedItem = *e;
 
            --numUsed;
            const size_t numToShift = numUsed - indexToRemove;
 
            if (numToShift > 0)
                std::memmove (e, e + 1, sizeof (ObjectClass*) * (size_t) numToShift);
 
            if ((numUsed << 1) < data.numAllocated)
                minimiseStorageOverheads();
        }
 
        return removedItem;
    }

    void removeObject (const ObjectClass* objectToRemove, bool deleteObject = true)
    {
        ObjectClass** const e = data.elements.getData();
 
        for (int i = 0; i < numUsed; ++i)
        {
            if (objectToRemove == e[i])
            {
                remove (i, deleteObject);
                break;
            }
        }
    }

    void removeRange (size_t startIndex, const size_t numberToRemove, bool deleteObjects = true)
    {
        const size_t endIndex = jlimit ((size_t)0U, numUsed, startIndex + numberToRemove);
        startIndex = jlimit ((size_t)0U, numUsed, startIndex);
 
        if (endIndex > startIndex)
        {
            if (deleteObjects)
            {
                for (int i = startIndex; i < endIndex; ++i)
                {
                    delete data.elements [i];
                    data.elements [i] = nullptr; // (in case one of the destructors accesses this array and hits a dangling pointer)
                }
            }
 
            const size_t rangeSize = endIndex - startIndex;
            ObjectClass** e = data.elements + startIndex;
            size_t numToShift = numUsed - endIndex;
            numUsed -= rangeSize;
 
            for (size_t i=0; i < numToShift; ++i)
            {
                *e = e [rangeSize];
                ++e;
            }
 
            if ((numUsed << 1) < data.numAllocated)
                minimiseStorageOverheads();
        }
    }

    void removeLast (int howManyToRemove = 1,
                     bool deleteObjects = true)
    {
        if (howManyToRemove >= numUsed)
            clear (deleteObjects);
        else
            removeRange (numUsed - howManyToRemove, howManyToRemove, deleteObjects);
    }

    void swap (const size_t index1,
               const size_t index2) noexcept
    {
        if (index1 < numUsed && index2 < numUsed)
        {
            std::swap (data.elements [index1],
                       data.elements [index2]);
        }
    }

    void move (const size_t currentIndex, size_t newIndex) noexcept
    {
        if (currentIndex != newIndex)
        {
            if (currentIndex < numUsed)
            {
                if (newIndex >=  numUsed)
                    newIndex = numUsed - 1;
 
                ObjectClass* const value = data.elements [currentIndex];
 
                if (newIndex > currentIndex)
                {
                    std::memmove (data.elements + currentIndex,
                                  data.elements + currentIndex + 1,
                                  sizeof (ObjectClass*) * (size_t) (newIndex - currentIndex));
                }
                else
                {
                    std::memmove (data.elements + newIndex + 1,
                                  data.elements + newIndex,
                                  sizeof (ObjectClass*) * (size_t) (currentIndex - newIndex));
                }
 
                data.elements [newIndex] = value;
            }
        }
    }

    template <class OtherArrayType>
    void swapWith (OtherArrayType& otherArray) noexcept
    {
        data.swapWith (otherArray.data);
        std::swap (numUsed, otherArray.numUsed);
    }
 
    //==============================================================================
    bool minimiseStorageOverheads() noexcept
    {
        return data.shrinkToNoMoreThan (numUsed);
    }

    bool ensureStorageAllocated (const int minNumElements) noexcept
    {
        return data.ensureAllocatedSize (minNumElements);
    }
 
    //==============================================================================
    template <class ElementComparator>
    void sort (ElementComparator& comparator,
               bool retainOrderOfEquivalentItems = false) const noexcept
    {
        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 <ObjectClass*> data;
    size_t numUsed;
 
    void deleteAllObjects()
    {
        while (numUsed > 0)
            delete data.elements [--numUsed];
    }
 
    CARLA_DECLARE_NON_COPYABLE (OwnedArray)
};
 
}
 
#endif // WATER_OWNEDARRAY_H_INCLUDED