[Pull request] Array::indexOfSortedLowerBound()


#1

I had an [url=http://learn.juce.com/doc/classArray.php]Array[/url] and I wanted to find a range of elements in that [url=http://learn.juce.com/doc/classArray.php]Array[/url], which were greater than a and less than b, where a and b were not necessarily part of the [url=http://learn.juce.com/doc/classArray.php]Array[/url].

So I delved into the documentation and the code of the Array class, but I did not find methods to realize this.

This resolved into 2 things:

  1. Correct me if I am wrong, but I think in the method [url=http://learn.juce.com/doc/classArray.php#ad3faadfb7b8eb05350afb1c9dd951ff5]Array::indexOfSorted()[/url] exist two unnecessary lines:
    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;
    }

    In the line if (halfway == s) return -1; the condition never gets true. Because if halfway equals s, s equals e and then the method would return at the first if-statement. In between the values of s and e do not change.

    This is a really small unimportant change, but why not.

  2. I implemented a version of
    int Array<ElementType, TypeOfCriticalSectionToUse, minimumAllocatedSize>::indexOfSortedLowerBound(ElementComparator& comparator, TargetValueType elementToFindLowerBoundFor) const

    Do you think it would be a useful addition to the JUCE library? Or do you think it would just bloat the class?
    If this method exists, has to exist a method for upperBound as well? And should these two methods strictly relate to the definitions of lower- and upperBound in the STL?


#2

No.. halfway can be equal to s if e == s + 1. If the line's not there, it'd get into an infinite loop (...or am I missing something?)

TBH I don't really want to add very specific methods like that to the Array class, it's unnecessary bloat.. The general drift nowadays is towards using STL algorithms, which should mostly with Array, so there's probably a way to implement the same thing using them, or with a free function.


#3
  1. Yes, you are absolutely right! Forgot about the flooring! Sorry!
  2. I knew about the STL algorithm, but I never got the fact that you can use it with JUCE . But it is obious since they only use iterators as inputs. I feel so stupid now because there are of course functions for exactly my purpose: lower_bound and upper_bound. Thank you very much for pointing that out.