Приключения с LINQ-ом.
Вот такая задача.
Дан список отрезков на прямой, inputRanges. И дан другой список, privateRanges. Задача состоит в том, чтобы исключить из списка inputRanges все такие отрезки, которые лежат внутри каких либо отрезков списка privateRanges (вершины включаются). Все элементы privateRanges имеют попарно пустое пересечение.
T.е. если есть отрезок iR = [2, 5] в inputRanges и отрезок pR = [1, 6], iR нужно выбросить из списка.
Дан класс MyRange:
public class MyRange
{
public int lower;
public int upper;
public MyRange(int lower, int upper)
{
this.lower = lower;
this.upper = upper;
}
public override string ToString()
{
return string.Format("({0}, {1})", this.lower, this.upper);
}
}
Задача простая (казалось бы!) Пользуемся оператором Except имеющиься в LINQe.
static void Main(string[] args)
{
MyRange [] privateRanges = {new MyRange(1, 10),
new MyRange (25, 30),
new MyRange ( 40, 50 ),
new MyRange ( 61, 63 ) };
MyRange[] inputRanges = { new MyRange(2, 8),
new MyRange(31, 39),
new MyRange(26, 28),
new MyRange(41, 49),
new MyRange(62, 62),
new MyRange(70, 80) };
RangeCompare rc = new RangeCompare();
IEnumerable<MyRange> cleanedRanges = inputRanges.Except(privateRanges, rc);
foreach (MyRange r in cleanedRanges)
{
Console.WriteLine(r);
}
Console.ReadKey();
}
Единственное что осталось - это имплементация RangeCompare, наследующего IEqualityComparer<MyRange>, как написано в документации.
class RangeCompare : IEqualityComparer<MyRange>
{
#region
IEqualityComparer<MyRange> Members
bool IEqualityComparer<MyRange>.Equals(MyRange x, MyRange y)
{
return (y.lower >= x.lower && y.upper <= x.upper);
}
int IEqualityComparer<MyRange>.GetHashCode(MyRange obj)
{
return obj.ToString().GetHashCode();
}
#endregion
}
Здесь функция Equals несколько неортодоксальна. Но ничто не мешает нам вложить свой смысл в функцию Equals(). (Один важный момент: наша функция не симметрична, поэтому нужно знать как работает оператор Except и что именно означают x и у. В этом недостаток решения).
Компилируем, запускаем и ожидаем на выводе:
(31, 39)
(70, 80).
Но не тут-то было! На выводе получаем весь массив inputRanges! В чем же дело? Тут замечаем, что если добавить в inputRanges элемент, который содержится в privateRanges (например (1, 10)). Он будет выброшен совершенно правильно. Т.е. наша имплементация IEqualityComparer работает, но как-то странно. Что-то еще кроме функции Equals() заранее решает, что наши объекты не "равны". Вот это "что-то" нужно исключить и тогда все видимо заработает. Кандидат очевидный. Это - функция GetHashCode() имплементируя которую мы явно перестарались. Т.е., как и положено, мы стараемся вернуть разный хэш код для разных объектов. Проблема в том, что "разность" наших объектов совсем не подразумевает равенство. Если замысел создателей LINQa понят правильно, то в случае когда GetHashCode() для объектов x и y возвращает одно и то же значение, "коллизия" разрешается вызовом функции Equals(). Поэтому переписываем функцию GetHashCode() таким образом, чтобы она убралась с дороги. Т.е. всегда возвращала одно значение.
int IEqualityComparer<MyRange>.GetHashCode(MyRange obj)
{
return 0;
}
Ура! Заработало.
