juce_SortedSet.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
{
 
JUCE_BEGIN_IGNORE_WARNINGS_MSVC (4512)
 
//==============================================================================
template <class ElementType, class TypeOfCriticalSectionToUse = DummyCriticalSection>
class SortedSet
{
public:
    //==============================================================================
    SortedSet() = default;
 
    SortedSet (const SortedSet&) = default;
 
    SortedSet (SortedSet&&) noexcept = default;
 
    SortedSet& operator= (const SortedSet&) = default;
 
    SortedSet& operator= (SortedSet&&) noexcept = default;
 
    ~SortedSet() = default;
 
    //==============================================================================
    bool operator== (const SortedSet<ElementType>& other) const noexcept
    {
        return data == other.data;
    }
 
    bool operator!= (const SortedSet<ElementType>& other) const noexcept
    {
        return ! operator== (other);
    }
 
    //==============================================================================
    void clear() noexcept
    {
        data.clear();
    }
 
    void clearQuick() noexcept
    {
        data.clearQuick();
    }
 
    //==============================================================================
    inline int size() const noexcept
    {
        return data.size();
    }
 
    inline bool isEmpty() const noexcept
    {
        return size() == 0;
    }
 
    inline ElementType operator[] (const int index) const noexcept
    {
        return data [index];
    }
 
    inline ElementType getUnchecked (const int index) const noexcept
    {
        return data.getUnchecked (index);
    }
 
    inline ElementType& getReference (const int index) noexcept
    {
        return data.getReference (index);
    }
 
    inline const ElementType& getReference (const int index) const noexcept
    {
        return data.getReference (index);
    }
 
    inline ElementType getFirst() const noexcept
    {
        return data.getFirst();
    }
 
    inline ElementType getLast() const noexcept
    {
        return data.getLast();
    }
 
    //==============================================================================
    inline const ElementType* begin() const noexcept
    {
        return data.begin();
    }
 
    inline const ElementType* end() const noexcept
    {
        return data.end();
    }
 
    //==============================================================================
    int indexOf (const ElementType& elementToLookFor) const noexcept
    {
        const ScopedLockType lock (data.getLock());
 
        int s = 0;
        int e = data.size();
 
        for (;;)
        {
            if (s >= e)
                return -1;
 
            if (elementToLookFor == data.getReference (s))
                return s;
 
            auto halfway = (s + e) / 2;
 
            if (halfway == s)
                return -1;
 
            if (elementToLookFor < data.getReference (halfway))
                e = halfway;
            else
                s = halfway;
        }
    }
 
    bool contains (const ElementType& elementToLookFor) const noexcept
    {
        return indexOf (elementToLookFor) >= 0;
    }
 
    //==============================================================================
    bool add (const ElementType& newElement) noexcept
    {
        const ScopedLockType lock (getLock());
 
        int s = 0;
        int e = data.size();
 
        while (s < e)
        {
            auto& elem = data.getReference (s);
 
            if (newElement == elem)
            {
                elem = newElement; // force an update in case operator== permits differences.
                return false;
            }
 
            auto halfway = (s + e) / 2;
            bool isBeforeHalfway = (newElement < data.getReference (halfway));
 
            if (halfway == s)
            {
                if (! isBeforeHalfway)
                    ++s;
 
                break;
            }
 
            if (isBeforeHalfway)
                e = halfway;
            else
                s = halfway;
        }
 
        data.insert (s, newElement);
        return true;
    }
 
    void addArray (const ElementType* elementsToAdd,
                   int numElementsToAdd) noexcept
    {
        const ScopedLockType lock (getLock());
 
        while (--numElementsToAdd >= 0)
            add (*elementsToAdd++);
    }
 
    template <class OtherSetType>
    void addSet (const OtherSetType& setToAddFrom,
                 int startIndex = 0,
                 int numElementsToAdd = -1) noexcept
    {
        const typename OtherSetType::ScopedLockType lock1 (setToAddFrom.getLock());
        const ScopedLockType lock2 (getLock());
        jassert (this != &setToAddFrom);
 
        if (this != &setToAddFrom)
        {
            if (startIndex < 0)
            {
                jassertfalse;
                startIndex = 0;
            }
 
            if (numElementsToAdd < 0 || startIndex + numElementsToAdd > setToAddFrom.size())
                numElementsToAdd = setToAddFrom.size() - startIndex;
 
            if (numElementsToAdd > 0)
                addArray (&setToAddFrom.data.getReference (startIndex), numElementsToAdd);
        }
    }
 
    //==============================================================================
    ElementType remove (const int indexToRemove) noexcept
    {
        return data.removeAndReturn (indexToRemove);
    }
 
    void removeValue (const ElementType& valueToRemove) noexcept
    {
        const ScopedLockType lock (getLock());
        data.remove (indexOf (valueToRemove));
    }
 
    template <class OtherSetType>
    void removeValuesIn (const OtherSetType& otherSet) noexcept
    {
        const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
        const ScopedLockType lock2 (getLock());
 
        if (this == &otherSet)
        {
            clear();
        }
        else if (! otherSet.isEmpty())
        {
            for (int i = data.size(); --i >= 0;)
                if (otherSet.contains (data.getReference (i)))
                    remove (i);
        }
    }
 
    template <class OtherSetType>
    void removeValuesNotIn (const OtherSetType& otherSet) noexcept
    {
        const typename OtherSetType::ScopedLockType lock1 (otherSet.getLock());
        const ScopedLockType lock2 (getLock());
 
        if (this != &otherSet)
        {
            if (otherSet.isEmpty())
            {
                clear();
            }
            else
            {
                for (int i = data.size(); --i >= 0;)
                    if (! otherSet.contains (data.getReference (i)))
                        remove (i);
            }
        }
    }
 
    template <class OtherSetType>
    void swapWith (OtherSetType& otherSet) noexcept
    {
        data.swapWith (otherSet.data);
    }
 
    //==============================================================================
    void minimiseStorageOverheads() noexcept
    {
        data.minimiseStorageOverheads();
    }
 
    void ensureStorageAllocated (const int minNumElements)
    {
        data.ensureStorageAllocated (minNumElements);
    }
 
    //==============================================================================
    inline const TypeOfCriticalSectionToUse& getLock() const noexcept      { return data.getLock(); }
 
    using ScopedLockType = typename TypeOfCriticalSectionToUse::ScopedLockType;
 
 
private:
    //==============================================================================
    Array<ElementType, TypeOfCriticalSectionToUse> data;
};
 
JUCE_END_IGNORE_WARNINGS_MSVC
 
} // namespace juce