source: branches/HeuristicLab.Problems.GrammaticalOptimization/DynamicDataDisplay/Common/Auxiliary/DataSearch/SortedXSearcher1d.cs @ 13757

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;

namespace Microsoft.Research.DynamicDataDisplay.Common.DataSearch
{
  internal class SortedXSearcher1d
  {
    private readonly IList<Point> collection;
    public SortedXSearcher1d(IList<Point> collection)
    {
      if (collection == null)
        throw new ArgumentNullException("collection");

      this.collection = collection;
    }

    public SearchResult1d SearchXBetween(double x)
    {
      return SearchXBetween(x, SearchResult1d.Empty);
    }

    public SearchResult1d SearchXBetween(double x, SearchResult1d result)
    {
      if (collection.Count == 0)
        return SearchResult1d.Empty;

      int lastIndex = collection.Count - 1;

      if (x < collection[0].X)
        return SearchResult1d.Empty;
      else if (collection[lastIndex].X < x)
        return SearchResult1d.Empty;

      int startIndex = !result.IsEmpty ? Math.Min(result.Index, lastIndex) : 0;

      // searching ascending
      if (collection[startIndex].X < x)
      {
        for (int i = startIndex + 1; i <= lastIndex; i++)
          if (collection[i].X >= x)
            return new SearchResult1d { Index = i - 1 };
      }
      else // searching descending
      {
        for (int i = startIndex - 1; i >= 0; i--)
          if (collection[i].X <= x)
            return new SearchResult1d { Index = i };
      }

      throw new InvalidOperationException("Should not appear here.");
    }
  }
}