1

I have a list of panels, sorted by their y-values. You can see my question from earlier about the specifics of why this is structured this way. Long story short, this List has the highest panel at position 0, the one below it at position 1, etc, down to the last one at the last position. I am accessing the y-coordinate of each panel using this line of code adapted from my linked question:

Panel p = panelList[someIndex];
int panelHeight = p.Top + p.Parent.Top - p.Parent.Margin.Top;
//The above line guarantees that the first panel (index 0) has y-coordinate 0 when scrolled all the way up,
//and becomes negative as the user scrolls down.
//the second panel starts with a positive y-coordinate, but grows negative after the user scrolls past the top of that page
//and so on...

I need to find the index of the panel closest to height 0, so I know which panels are currently on, or very near being on, the page. Therefore, I am trying to use the List.BinarySearch() method, which is where I'm stuck. I'm hoping to take advantage of the BinarySearch's property of returning the index that the value would be at if it did exist in the list. That way I can just search for the panel at height 0 (which I don't expect to find), but find the element nearest it (say at y=24 or y=-5 something), and know that that is the panel being rendered at the moment.

Binary Search lets you specify an IComparer to define the < and > operations, so I wrote this class:

class PanelLocationComparer : IComparer<Panel>
{
    public int Compare(Panel x, Panel y)
    {
        //start by checking all the cases for invalid input
        if      (x == null && y == null) { return  0; }
        else if (x == null && y != null) { return -1; }
        else if (x != null && y == null) { return  1; }
        else//both values are defined, compare their y values
        {
            int xHeight = x.Top + x.Parent.Top - x.Parent.Margin.Top;
            int yHeight = y.Top + y.Parent.Top - y.Parent.Margin.Top;
            if (xHeight > yHeight)
            {
                return 1;
            }
            else if (xHeight < yHeight)
            {
                return -1;
            }
            else
            {
                return 0;
            }
        }
    }
}

That doesn't work, and I'm realizing now that it is because comparing two panels for greater than or less than doesn't actually care about what value I'm searching for, in this case y value = 0. Is there a way to implement this in a IComparer, or is there a way to even do this type of search using the built-in BinarySearch?

I considered just making a new List of the same length as my Panel list every time, copying the y-values into it, and then searching through this list of ints for 0, but creating, searching, and destroying that list every time they scroll will hurt performance so much that it defeats the point of the binary search.

My question is also related to this one, but I couldn't figure out how to adapt it because they ultimately use a built-in comparison method, which I don't have access to in this situation.

Community
  • 1
  • 1
Cody
  • 2,643
  • 2
  • 10
  • 24

1 Answers1

1

Unfortunately the built-in BinarySearch methods cannot handle such scenario. All they can do is to search for list item or something that can be extracted from the list item. Someimes they can be used with a fake item and appropriate comparer, but this is not applicable here.

From the other side, binary search is quite simple algorithm, so you can easily create one for your specific case, or better, create a custom extension method in order to not repeat yourself the next time you need something like this:

public static class Algorithms
{
    public static int BinarySearch<TSource, TValue>(this IReadOnlyList<TSource> source, TValue value, Func<TSource, TValue> valueSelector, IComparer<TValue> valueComparer = null)
    {
        return source.BinarySearch(0, source.Count, value, valueSelector, valueComparer);
    }
    public static int BinarySearch<TSource, TValue>(this IReadOnlyList<TSource> source, int start, int count, TValue value, Func<TSource, TValue> valueSelector, IComparer<TValue> valueComparer = null)
    {
        if (valueComparer == null) valueComparer = Comparer<TValue>.Default;
        int lo = start, hi = lo + count - 1;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            int compare = valueComparer.Compare(value, valueSelector(source[mid]));
            if (compare < 0) hi = mid - 1;
            else if (compare > 0) lo = mid + 1;
            else return mid;
        }
        return ~lo; // Same behavior as the built-in methods
    }
}

and then use simply:

int index = panelList.BinarySearch(0,  p => p.Top + p.Parent.Top - p.Parent.Margin.Top);
Ivan Stoev
  • 195,425
  • 15
  • 312
  • 343