Проблема, очевидно, в этом коде:
if (x != y)
{
return 1;
}
Дело в том, что компаратор обязан быть антисиметричным. (То есть если Compare(x, y) == 1
, то обязательно Compare(y, x) == -1
.) Ваш компаратор не антисиметричен. Вы нарушили контракт, поведение непредсказуемо.
Уберите проблемный код, должно работать. Или скажите, для чего он нужен, попробуем решить проблему по-другому.
Давайте разберёмся, как работает RemoveWhere. Если верить декомпиляции с ILSpy (.NET 4.0), код такой:
public int RemoveWhere(Predicate<T> match)
{
if (match == null)
throw new ArgumentNullException("match");
List<T> matches = new List<T>(this.Count);
// получаем список всех элементовпроходящих через предикат
BreadthFirstTreeWalk(delegate(SortedSet<T>.Node n)
{
if (match(n.Item)) { matches.Add(n.Item); }
return true;
});
int num = 0;
for (int i = matches.Count - 1; i >= 0; i--)
{
if (Remove(matches[i])) num++;
}
return num;
}
Тут вроде ничего подозрительного.
Функция BreadthFirstTreeWalk
для TreeWalkPredicate
, возвращающего только true, обходит всё дерево:
internal virtual bool BreadthFirstTreeWalk(TreeWalkPredicate<T> action)
{
if (this.root == null) return true;
List<SortedSet<T>.Node> list = new List<SortedSet<T>.Node>();
list.Add(this.root);
while (list.Count != 0)
{
SortedSet<T>.Node node = list[0];
list.RemoveAt(0);
if (!action(node)) // тут у нас всегда true
return false;
if (node.Left != null) list.Add(node.Left);
if (node.Right != null) list.Add(node.Right);
}
return true;
}
Так мы должны получить список всех элементов, если, конечно, добавление в дерево не зафейлилось из-за компаратора. Так что проблема должна быть в функции Remove
. (Ну или Add
.)
Код функции DoRemove (к которой сводится функция Remove) слишком большой, положил тут: http://pastebin.com/MQ87EtQv. Интересен вот этот фрагмент:
int num = flag ? -1 : this.comparer.Compare(item, node.Item);
if (num == 0)
{
flag = true;
node4 = node;
parentOfMatch = node2;
}
node3 = node2;
node2 = node;
if (num < 0)
node = node.Left;
else
node = node.Right;
Здесь видно, что результат сравнения управляет тем, куда пойдёт алгоритм искать дальше узел, если он не совпадает с node
. В нашем случае будет всегда num > 0
, поэтому алгоритм всегда пойдёт вправо, несмотря на то, что искомый узел может находится и слева.