Better indexOfSorted() in OwnedArray


#1

I have an OwnedArray of objects that expose a getName() method. I want to keep it sorted, so I’ve created the obligatory Comparator object which implements compareElements. The question is, how do I determine if an object with a particular name (using the Comparator) already exists, without actually creating one of the objects?

I think this could be easily added to OwnedArray, by simply changing the signature of indexOfSorted:

juce_OwnedArray.cpp

template <class ElementComparator, class ObjectType>
int indexOfSorted (ElementComparator& comparator,
                   ObjectType objectToLookFor) const noexcept

Now it is possible to declare Comparator::compareElements with different types:

int compareElements (String const stringToLookFor, Object const* const objectToCompare);

This idiom could be used everywhere a Comparator is used.

Thoughts?


#2

Good idea! I actually just hit a similar problem myself. I’ll tweak that.


#3

Array needs it too (I’m using both). Or anywhere there’s a Comparator.


#4

I see you rolled back the change. So, the proposed change breaks places that pass a ScopedPointer where successful resolution depends on the conversion to a pointer type? That makes sense…TargetValueType ends up being ScopedPointer instead of ObjectType const* const.

Here’s a fix, just bring back the improved version of indexToSorted and then add this function below it:

template <typename ElementComparator, class ObjectType>
int indexOfSorted (ElementComparator& comparator, ObjectType const* const objectToLookFor) const noexcept
{
  return indexOfSorted <ElementComparator, ObjectType const* const> (comparator, objectToLookFor);
}

I haven’t actually tried it, but JUCE compiles correctly with it (juce_audio_processors.cpp will go through this new function now).


#5

Well, I suppose that’d be safe, though it’s not quite as neat as the original idea.


#6

Will it break anything else?


#7

Will it break anything else?[/quote]

Not sure, but this has made me nervous about changing it now!


#8

I have another approach. Rewrite OwnedArray::indexOfSorted to take a functor and no extra argument, and then make the 2 parameter version call the 1 parameter version with a local class:

Functor declaration looks like this:

struct Comparator
{
  int operator () (ObjectClass const* objectToCompare);
};

New, 1-argument version of indexOfSorted:

template <typename ComparatorFunctor>
int indexOfSorted (ComparatorFunctor comparator) const
{
...
        while (s < e)
        {
            if (comparator (data.elements [s]) == 0)
...
            if (comparator (data.elements [halfway]) >= 0)
...
}

Rewrite 2-argument version to call the first one:

template <typename ElementComparator>
int indexOfSorted (
  ElementComparator comparator, const ObjectClass* const objectToLookFor) const
{
  struct ComparatorFunctor {
    ElementComparator& comparator;
    ObjectClass const* const objectToLookFor;
    ComparatorFunctor (
      ElementComparator& comparator_,
      const ObjectClass* const objectToLookFor_) : comparator (comparator_)
                                          , objectToLookFor_ (objectToLookFor) { }
    int operator () (ObjectClass const* objectToCompare)
    {
      return comparator.compareElements (objectToLookFor, objectToCompare);
    }
  };

  return indexOfSorted (ComparatorFunctor (comparator, objectToLookFor));
}

Existing code should work as normal, and if you want to get the new functionality you just provide a real functor, store the “key” in the functor and call the 1-argument version.

This will eliminate any possible ambiguity since the number of arguments differ.


#9

Come to think of it, this could be hacked to work without changing the existing code, just stuff ElementComparator with the key, ignore the first parameter passed to compareElements, and call indexOfSorted with a dummy value / nullptr for objectToLookFor.