Comparing with null?

[galmok]

I have implemented my own IComparer to be used with the priority queue, but I am wondering if it is a bug that my comparer occasionally gets called with null reference instead of a valid object?

I am actually not certain how I should handle null values here as I only expected to have objects from the queue passed.

The null to the comparer happens when I call Remove on the queue (with a non-null value).

The item I try to remove is NOT on the queue. Should this result in null-values being passed to the comparer?

[galmok]

I created a test setup showing this:

  public class Foo
  {
    public string MyStr;
    public DateTime MyDate;
  }

  public class FooComparer : IComparer<Foo>, IEqualityComparer<Foo>
  {
    public int Compare(Foo x, Foo y)
    {
      //if (x == null && y == null)
      //  return 0;
      //if (x == null)
      //  return 1;
      //if (y == null)
      //  return -1;
      if (x.MyDate > y.MyDate)
        return -1;
      if (x.MyDate < y.MyDate)
        return 1;
      return 0;
    }

    public bool Equals(Foo x, Foo y)
    {
      if (x == null && y == null)
        return true;
      if (x == null || y == null)
        return false;
      if (x.MyStr.Equals(y.MyStr))
        return true;
      return false;
    }

    public int GetHashCode(Foo obj)
    {
      return obj.MyStr.GetHashCode();
    }
  }

    public void TestFoo()
    {
      var x = new ConcurrentPriorityQueue<Foo>(new FooComparer());
      var f1 = new Foo{ MyStr = @"C:\temp\test3.tmp", MyDate = DateTime.Parse("2018-01-03 13:48:21") };
      x.Add(f1);
      var f2 = new Foo{ MyStr = @"C:\temp\test3.tmp", MyDate = DateTime.Parse("2018-01-03 13:48:21") };
      x.Remove(f2);
      x.Add(f2);
      var f3 = new Foo{ MyStr = @"C:\temp\test1.tmp", MyDate = DateTime.Parse("2018-01-03 13:46:21") };
      x.Remove(f3);
      x.Add(f3);
      var f4 = new Foo{ MyStr = @"C:\temp\test1.tmp", MyDate = DateTime.Parse("2018-01-03 13:46:21") };
      x.Remove(f4);
      x.Add(f4);
      var f5 = new Foo{ MyStr = @"C:\temp\test2.tmp", MyDate = DateTime.Parse("2018-01-03 13:47:21") };
      x.Remove(f5);
      x.Add(f5);
      Console.WriteLine($"{x.Count} {x.Peek()}");
      var f6 = new Foo{ MyStr = @"C:\temp\test2.tmp", MyDate = DateTime.Parse("2018-01-03 13:47:21") };
      x.Remove(f6);
      Console.WriteLine($"{x.Count} {x.Peek()}");
      x.Add(f6);
      Console.WriteLine($"{x.Count} {x.Peek()}");
    }

The comparer orders files according to MyDate. The x.Add(f5); makes the comparer be called with null object.

I am a little bit uncertain if the Remove

[galmok]

For reference, the above gives this exception:

System.NullReferenceException: Object reference not set to an instance of an object.

At his line in FooComparer:

if (x.MyDate > y.MyDate)

where x is null.

[dshulepov]

Hello Your comparer needs to handle the comparison with null. The situation arises because of the way basic heap operations are implemented: https://github.com/dshulepov/DataStructures/blob/master/DataStructures/PriorityQueue.cs#L261

[galmok]

If I enable the commented lines in the comparer that handle the null values, I get null value instead of Foo objects when calling Peek. Is my comparer faulty with the commented lines uncommented?

[dshulepov]

Your comparer seems fine. Peek should not return nulls, so seems like you found a bug. Unfortunately, I don't have much time to look into it. Are you familiar with heap based priority queue? Would you be able to debug and contribute the fix?

[galmok]

I am not familiar with a heap based priority queue. I won't be able to help debug and fix it, sorry.

I checked the internal _heap and saw that element 0 was null while element 1 and 2 were Foo objects. The null was placed there upon the Remove that triggered the null exception in FooCompare. So I would guess the Remove method to have the flaw.

[dshulepov]

It seems so. I'm transferring this repository to a friend, since I don't have time to work on it. Hopefully, he'll fix the issue asap.

[heinrich-ulbricht]

Hi, I'm searching for a concurrent priority queue implementation as well. This transferral of the repo to a friend - has this happened? Is this bug @galmok found still present in the code base? @galmok did you solve this?

[galmok]

@heinrich-ulbricht I think I went another way. I don't know the state of this issue.