Ordered queue with two indices

Question

Hi

I need an ordered queue where objects would be ordered by primary and secondary value.

class Object
{
  int PrimaryValue;
  int SecondaryValue;
}

The position of an Object in the queue must be determined by PrimaryValue. Object with higher PrimaryValue must preceed object with lower PrimaryValue. However for two objects with the same PrimaryValue a SecondaryValue must be used to determine precedence. Also I need two functions to get forward iterator GetFirst() and backward iterator GetLast() that would return respective iterators.

Answer 1

class Obj : IComparable<Obj>
{
    int PrimaryValue;
    int SecondaryValue;

    public int CompareTo(Obj other)
    {
        if (other == null) throw new ArgumentNullException("other");
        int diff = PrimaryValue - other.PrimaryValue;
        return diff != 0 ? diff : SecondaryValue - other.SecondaryValue;
    }
}

I'm not sure quite what you mean by forward and reverse iterators, which is C++ jargon for concepts that don't really exist in C#. You can always iterate over a collection in the forward direction simply by using foreach (var e in coll) ..., and in reverse by using System.Linq: foreach (var e in coll.Reverse()) ....

Answer 2

Sounds like what you want is either a PriorityQueue with the priority being a Pair or simply a SortedList with a custom Comparer. Here's an implementation of a PriorityQueue that could be adapted to your needs. Since GetEnumerator() returns an IEnumerable you can use the Reverse() extension method to iterate over it from back to front.

Similarly with the SortedList -- you need only supply a suitable IComparer that performs the comparison you need and use Reverse() for back to front iteration.

Answer 3

Do you know how to implement a priority queue with one key? If so, using two keys doesn't change anything as you just use the dictionary ordering on the keys. That is, implement a priority queue with keys being pairs of integers (x1, y1). You say that (x2, y2) is less than (x1, y1) if x2 < x1 or if x1 = x2 and y2 < y1. Now you can just use your previous knowledge of priority queues to solve this problem. You could do this, for example, using a SortedList with a custom IComparer.

class Pair<T> {
    public T First { get; private set; }
    public T Second { get; private set; }

    public Pair(T first, T second) {
        First = first;
        Second = second;
    }

    public override int GetHashCode() {
        return First.GetHashCode() ^ Second.GetHashCode();
    }

    public override bool Equals(object other) {
        Pair<T> pair = other as Pair<T>;
        if(pair == null) {
            return false;
        }
        return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second));
    }
}

class PairComparer<T> : IComparer<Pair<T>> {
    public int Compare(Pair<T> x, Pair<T> y) {
        if (x.First.CompareTo(y.First) < 0) {
            return -1;
        }
        else if (x.First.CompareTo(y.First) > 0) {
            return 1;
        }
        else {
            return x.Second.CompareTo(y.Second);
        }
    }   
}

Then:

SortedList<Pair<int>, MyClass> list = new SortedList<Pair<int>, MyClass>(new PairComparer<int>());

So that, for example,

SortedList<Pair<int>, string> list = new SortedList<Pair<int>, string>(new PairComparer<int>());
list.Add(new Pair<int>(-1, 1), "l1");
list.Add(new Pair<int>(-2, 1), "e");
list.Add(new Pair<int>(-7, 1), "h");
list.Add(new Pair<int>(-1, 3), "l2");
list.Add(new Pair<int>(0, 5), "o");
foreach (var value in list) {
     Console.WriteLine(value.Value);
}

will output

h
e
l1
l2
o

as expected and

foreach(var value in list.Reverse()) {
    Console.WriteLine(value.Value);
}

will output

o
l2
l1
e
h

showing that we can iterate from the end too.

Answer 4

you just need a SortedList.... and to give it your own copareing thingy...

http://msdn.microsoft.com/en-us/library/ms132323.aspx

Answer 5

You can just use a List<T>, and call Sort(), however, to do so, instead implement IComparable<T> on your class. Finally, if you want to enumerate in reverse, just call Reverse() on the List<T>.

public class MyObject : IComparable<MyObject>
{
public int First;
public int Second;

public int CompareTo(MyObject other)
{
  if (Equals(this, other))
  {
    return 0;
  }
  if (ReferenceEquals(other, null))
  {
    return 1;
  }
  int first = this.First.CompareTo(other.First);
  if (first != 0)
  {
    return first;
  }
  return this.Second.CompareTo(other.Second);
}
}