Click here to Skip to main content
15,881,757 members
Please Sign up or sign in to vote.
4.93/5 (14 votes)
See more:
hi everybody,

does anybody know of a way to remove an item from a .NET sortedset when it falls out of order?

Before you jump to tell me that a sorted set cannot fall out of order, all that needs to happen is for an object in the sorted set to have a parameter (by which the set is sorted) altered.

For example, imagine if we have a Person class with a modifiable 'Name' field, and a sortedset<person> that contains many people, and is sorted by Name.
[0]"April"
[1]"Bob"
[2]"Mary"
[3]"Zelda"

If we change the name of item 0 (April) to "Zoe", it will remain at position 0:
[0]"Zoe"
[1]"Bob"
[2]"Mary"
[3]"Zelda"

What I have tried:
I tried to get the items to fire an event so that when these fields changed ( e.g. Name), the sortedset would find the item, remove it, and then reinsert it, So it should be in the right order. This doesn't work, though, because the sortedset cannot find/remove items when it is out of order: presumably its binary search method stops working. I can't find a method which lets you remove items from a specific index.
I have also tried the RemoveWhere() method like so, but it still doesn't find the items:
C#
public void RemoveSafe(T removeMe)
{
    //removes an item, even if it is out of sort order
    RemoveWhere(a => a == removeMe);
}

an alternate solution, of course, is to remove an item, modify it, then add it back in. Unfortunately my program & sorting criteria is a bazillion times more complex than the Person example above, and this solution would make it very messy indeed...

So, to reiterate:
does anybody know of a way to remove an item from a sorted set when it falls out of order?

Other ideas also welcome :)
Thanks!
Posted
Updated 2-Apr-11 23:32pm
v3
Comments
Keith Barrow 3-Apr-11 7:49am    
Excellent Question! I have raised this in the lounge, hopefully wiser heads than mine will give you a better solution.

The problem arises from the fact that the Person has a value changed that is involved with the comparison, but the SortedSet is unaware the value has changed. I couldn't find a way to fix this.
I tried the following code (to clarify for others what the problem is :

class Person:  IComparable
{
    public string Name { get; set; }

    public int CompareTo(object obj)
    {
        //Not robust code!
        Person objPerson = obj as Person;
        return this.Name.CompareTo(objPerson.Name);
    }

    public Person(string name)
    {
        Name = name;
    }      
}

class Program
{
    static SortedSet<person> sortedSet = new SortedSet<person>();

    static void WriteElements()
    {
        foreach (Person foo in sortedSet)
            Console.WriteLine(foo.Name);
    }

    static void Main(string[] args)
    {
        Person alice = new Person("Alice"); 
        sortedSet.Add(new Person("Zelda"));
        sortedSet.Add(new Person("Bob"));
        sortedSet.Add(new Person("Mary"));
        sortedSet.Add(alice);
        alice.Name = "Zoe";
        WriteElements();
        Console.ReadKey();
    }
}


Sadly, it looks like Microsoft have not given us a way to force the set to re-sort which would fix it.
There is nothing in the documentation telling you shouldn't change the properties in this way and it seems a very reasonable thing to do. You could raise this with them as it looks like a genuine bug!

My solution is to remove the item from the list, update it then re-insert for now. I hope someone has a better answer!

[Edit]
Mike Hankey[^] has found a work around you can look at. It looks an option, if you don't mind the INotify... and IObservable... stuff
 
Share this answer
 
v3
Comments
Nagy Vilmos 3-Apr-11 8:36am    
You should be able to re-apply the sort after changing the key value, I beleive there's a method sort() to do this.
Keith Barrow 3-Apr-11 8:41am    
There isn't one in the SortedSet, you'd expect there to be, but I think the devs at MS are working under the assumption the set is always intrisically sorted. There is an OrderBy, but it returns the usual IOrderedEnumerable it doesn't sort the set itself.
Lee Reid 3-Apr-11 18:27pm    
Thanks for your help Keith. Given that noone can see a simple solution, I might point this one out to Microsoft. It's certainly a limitation of the sortedset I didn't expect to come across!
This was an interesting finding. Also played with the SortedSet for a while and encountered the same problem.

The only thing I found was that the documentation was quite confusing what comes to the IComparer interface. The comparer property is said to give the IEqualityComparer interface, but seems that it's the IEquality instead. I tried implementing both interfaces for the comparer, but no change.

Guess that currently this leads to either recreating and replacing the whole set or making the ordering outside a collection, for example using LINQ over HashSet.

Also I find this statement in BOL likely to be an overstatement "A SortedSet <T> maintains a sorted order as elements are inserted and deleted without affecting performance" :)
 
Share this answer
 
Comments
Lee Reid 3-Apr-11 18:21pm    
haha yeah I read that "without affecting performance" bit too and raised an eyebrow. Thanks for looking into it for me :)
I don't think there is any alegant and simple solution. SortedSet uses a binary tree internally and a binary search tree simply doesn't work when its structure is broken.

My best advice is: do never, ever make SortedSet fall out of order. You may have to change your application logic a bit, use a different collection or even implement your own SortedSomething class...
 
Share this answer
 
Sacha Barber wrote a great article A Chained Property Observer[^] that might very well find an application in this scenario. This is all the more true when the object comparison for the sorted set also takes child objects into account. The notification mechanism could be used to remove and reinsert the modified object which would effectively keep the sorted set in order.

I'll drop him a note to see if this is really applicable here.

Regards,

Manfred
 
Share this answer
 
v3
Comments
Lee Reid 3-Apr-11 18:50pm    
I'll give it a read. Thanks!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900