DataStructures
DataStructures copied to clipboard
Comparing with null?
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?
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
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.
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
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?
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?
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.
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.
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?
@heinrich-ulbricht I think I went another way. I don't know the state of this issue.