CODEWITHSUNDEEP
c#mathcollectionsrelation
Mat
Mat

Reputation: 274

C# Data Structure for a set of (x,y) points

I'm not familiar with all the collections available in C# but I'd like to implement a class to store a mathematical relation or function, i.e. a set of pairs (x,y). Presumably it would include a list of tuples or some other built collection from .NET, but I'm not sure what's best. Some potentially relevant facts:

  1. up a million pairs
  2. frequently would want to lookup which y goes with a particular x
  3. x would be a double type for all cases I know of now
  4. may want to interpolate y's to nonexistant x's
  5. will want to extract a subset of the relation including all pairs with x in a certain range
  6. will want to iterate through pairs in order of xs sometimes seems like it should be sorted by xs based on above things?

Upvotes: 2

Views: 5209

Answers (2)

Timothy Shields
Timothy Shields

Reputation: 79581

The SortedSet<T> seems like the right tool for this task.

We can define an IComparable element type as follows.

struct FunctionPoint : IComparable<FunctionPoint>
{
    public double X, Y;
    public FunctionPoint(double x)
    {
        this.X = x;
        this.Y = 0;
    }
    public FunctionPoint(double x, double y)
    {
        this.X = x;
        this.Y = y;
    }
    public int CompareTo(FunctionPoint other)
    {
        return X.CompareTo(other.X);
    }
}

And then use it in a SortedSet<FunctionPoint> as follows.

var function = new SortedSet<FunctionPoint>();
  1. up a million pairs
for (int i = 0; i < 100000; i++)
{
    var x = 2 * Math.PI * i / 1000000;
    var y = Math.Sin(x);
    function.Add(new FunctionPoint { X = x, Y = y });
}
  1. frequently would want to lookup which y goes with a particular x
var view = function.GetViewBetween(new FunctionPoint(x), new FunctionPoint(x));
if (view.Count > 0)
{
    var y = view.Min;
}
  1. may want to interpolate y's to nonexistant x's
var left = function.GetViewBetween(new FunctionPoint(double.NegativeInfinity), new FunctionPoint(x)).Max;
var right = function.GetViewBetween(new FunctionPoint(x), new FunctionPoint(double.PositiveInfinity)).Min;
var y = LinearInterpolate(left, right, x);
  1. will want to extract a subset of the relation including all pairs with x in a certain range
var view = function.GetViewBetween(new FunctionPoint(a), new FunctionPoint(b));
  1. will want to iterate through pairs in order of xs sometimes seems like it should be sorted by xs based on above things?
foreach (var point in function)
{
}

Upvotes: 4

Dennis_E
Dennis_E

Reputation: 8904

Maybe a System.Collections.Generic.SortedList<double, double> is what you need?
SortedList

If you constantly remove and add items, a SortedDictionary might perform better.

Upvotes: 0

Related Questions