CODEWITHSUNDEEP
c#sortingdata-structures
DanielLC
DanielLC

Reputation: 7151

Multi-sorted data structure

I'm trying to implement A* and I ran into a problem. I have a set where I need to find the minimum value of a given function, but I also need to be able to check if a given cell is in that set. In order to do this efficiently, I need the set to be sorted by position and value. It doesn't seem too difficult to write such a data structure. I just need one sorted by position and one by value, and have each refer to the other. There are two problems with this. First, in order to do it well, the structures need to be able to refer to parts of each other. There's no point in searching through a tree in log time if I can just point to the particular element. In order to do this, I'd pretty much need to rewrite trees from scratch. Second, it doesn't seem like the sort of thing I should be writing. Data structures are supposed to be part of the libraries. What's the name of the sort of data structure I need, and where can I find a C# library for it?

Upvotes: 2

Views: 86

Answers (1)

Servy
Servy

Reputation: 203821

There is no need for the two data structures to interact at all. Just have two data structures side by side. Make sure that when you add/remove an item you add/remove it from both. You can then fetch the minimum value of either collection based on which property you're interested in.

The only real reason to create a new data structure would be to ensure that adding/removing items was kept in sync between the two collections. There would be no need to manipulate the actual trees explicitly.

Such a custom type would look something like this (other operations omitted; they all just delegate to first and/or second).

public class SetPair<T>
{
    private SortedSet<T> first;
    private SortedSet<T> second;

    public SetPair(IComparer<T> firstComparer, IComparer<T> secondComparer)
    {
        first = new SortedSet<T>(firstComparer ?? Comparer<T>.Default);
        second = new SortedSet<T>(secondComparer ?? Comparer<T>.Default);
    }

    public T FirstMin { get { return first.Min; } }
    public T SecondMin { get { return second.Min; } }

    public bool Add(T item)
    {
        return first.Add(item) &&
            second.Add(item);
    }

    public bool Remove(T item)
    {
        return first.Remove(item) &&
            second.Remove(item);
    }
}

Upvotes: 2

Related Questions