Maintaining proper order of a collection of ordinals

I have a simple domain object:

class FavoriteFood
{
    public string Name;
    public int Ordinal;
 }

I want to have a collection of this domain object that maintains the correct ordinal. For example, given 4 favorite foods:

Name: Banana, Ordinal: 1
Name: Orange, Ordinal: 2
Name: Pear, Ordinal: 3
Name: Watermelon, Ordinal: 4

If I change Pear's ordinal to 4 it should shift Watermelon's ordinal down to 3.

If I add a new favorite food (Strawberry) with ordinal 3 it should shift Pear up to 4 and Watermelon up to 5.

If I change Pear's ordinal to 2 it should shift Orange up to 3.

If I change Watermelon's ordinal to 1, Banana would bump up to 2, Orange would bump up to 3, and Pear would bump up to 4.

What's the best way to accomplish this?

UPDATE: The name property of the domain object is dynamic and based on user input. The object has to have this Ordinal property because a user can change the order in which their favorite foods are displayed. This ordinal value is saved in a database and when populating the structure I cannot guarantee the items are added in order of their ordinals.

The trouble I am running into is when the underlying domain object is changed, there isn't a good way of updating the rest of the items in the list. For example:

var favoriteFoods = new List<FavoriteFood>();
var banana = new FavoriteFood { Name = "Banana", Ordinal = 1};
favoriteFoods.Add(banana);
favoriteFoods.Add(new FavoriteFood { Name = "Orange", Ordinal = 2 });
banana.Ordinal = 2;
// at this point both Banana and Orange have the same ordinal in the list. How can we make sure that Orange's ordinal gets updated too?

So far I have tried doing the following which works :

class FavoriteFood : INotifyPropertyChanging
{
    public string Name;
    public int Ordinal
    {
        get { return this.ordinal; }
        set
        {
            var oldValue = this.ordinal;
            if (oldValue != value && this.PropertyChanging != null)
            {
                this.PropertyChanging(new FavoriteFoodChangingObject { NewOrdinal = value, OldOrdinal = oldValue }, new PropertyChangingEventArgs("Ordinal"));
            }
            this.ordinal = value;
        }
    }

    internal struct FavoriteFoodChangingObject
    {
开发者_如何学Python        internal int NewOrdinal;
        internal int OldOrdinal;
    }

    // THIS IS A TEMPORARY WORKAROUND
    internal int ordinal;

    public event PropertyChangingEventHandler PropertyChanging;
 }

 public class FavoriteFoodCollection : IEnumerable<FavoriteFood>
 {
    private class FavoriteFoodOrdinalComparer : IComparer<FavoriteFood>
    {
        public int Compare(FavoriteFood x, FavoriteFood y)
        {
            return x.Ordinal.CompareTo(y.Ordinal);
        }
    }

    private readonly SortedSet<FavoriteFood> underlyingList = new SortedSet<FavoriteFood>(new FavoriteFoodOrdinalComparer());

    public IEnumerator<FavoriteFood> GetEnumerator()
    {
        return this.underlyingList.GetEnumerator();
    }

    public void AddRange(IEnumerable<FavoriteFood> items)
    {
        foreach (var i in items)
        {
            this.underlyingList.Add(i);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private void UpdateOrdinalsDueToRemoving(FavoriteFood item)
    {

        foreach (var i in this.underlyingList.Where(x => x.Ordinal > item.Ordinal))
        {
            i.ordinal--;
        }
    }

    public void Remove(FavoriteFood item)
    {
        this.underlyingList.Remove(item);
        this.UpdateOrdinalsDueToRemoving(item);
    }

    public void Add(FavoriteFood item)
    {
        this.UpdateOrdinalsDueToAdding(item);
        this.underlyingList.Add(item);
        item.PropertyChanging += this.item_PropertyChanging;
    }

    private void item_PropertyChanging(object sender, PropertyChangingEventArgs e)
    {
        if (e.PropertyName.Equals("Ordinal"))
        {
            var ordinalsChanging = (FavoriteFood.FavoriteFoodChangingObject)sender;
            this.UpdateOrdinalsDueToEditing(ordinalsChanging.NewOrdinal, ordinalsChanging.OldOrdinal);
        }
    }

    private void UpdateOrdinalsDueToEditing(int newOrdinal, int oldOrdinal)
    {

        if (newOrdinal > oldOrdinal)
        {

            foreach (var i in this.underlyingList.Where(x => x.Ordinal <= newOrdinal && x.Ordinal > oldOrdinal))
            {
                //i.Ordinal = i.Ordinal - 1;
                i.ordinal--;
            }

        }
        else if (newOrdinal < oldOrdinal)
        {

            foreach (var i in this.underlyingList.Where(x => x.Ordinal >= newOrdinal && x.Ordinal < oldOrdinal))
            {
                //i.Ordinal = i.Ordinal + 1;
                i.ordinal++;
            }
        }
    }

    private void UpdateOrdinalsDueToAdding(FavoriteFood item)
    {

        foreach (var i in this.underlyingList.Where(x => x.Ordinal >= item.Ordinal))
        {
            i.ordinal++;
        }
    }
}

This works alright, but the use of the internal Ordinal field is a strange workaround. It's needed so that the PropertyChangingEvent wont be infinitely raised.

Just use a List<string>:

List<string> foods = new List<string> { "Banana", "Orange", "Pear" };
int ordinalOfOrange = foods.IndexOf("Orange");

It's not a good idea to 'store' that ordinal if it has to change the way you describe.

Sounds like you want a SortedList. Add each item using it's Ordinal as the key.

I'd do something like the following:

public class FavoriteFoods
{
  StringComparer comparer ;
  List<string> list ;

  public FavoriteFoods()
  {
    this.list = new List<string>() ;
    this.comparer = StringComparer.InvariantCultureIgnoreCase ;
    return ;
  }

  public void Add( string food , int rank )
  {
    if ( this.list.Contains(food,comparer ) ) throw new ArgumentException("food") ;
    this.list.Insert(rank,food) ;
    return ;
  }

  public void Remove( string food )
  {
    this.list.Remove( food ) ;
    return ;
  }

  public void ChangeRank( string food , int newRank )
  {
    int currentRank = this.list.IndexOf(food) ;

    if ( currentRank < 0 ) throw new ArgumentOutOfRangeException("food") ;
    if ( newRank     <  0               ) throw new ArgumentOutOfRangeException("newRank") ;
    if ( newRank     >= this.list.Count ) throw new ArgumentOutOfRangeException("newRank") ;

    if ( newRank != currentRank )
    {
      this.Remove(food) ;
      this.Add( food , newRank ) ;
    }
    return ;
  }

  public int GetRank( string food )
  {
    int rank = this.list.IndexOf(food) ;
    if ( rank < 0 ) throw new ArgumentOutOfRangeException("food");
    return rank ;
  }

  public IEnumerable<string> InRankOrder()
  {
    foreach ( string food in this.list )
    {
      yield return food ;
    }
  }

}

Let me restate your problem.

You have a collection of strings. You have a collection of ordinals.

You want to be able to quickly look up the ordinal of a string. And the string of an ordinal. You'd also like to be able to insert a string with a given ordinal. And change the ordinal of a string.

There are two ways to go. The first, simple, approach is to store a collection of the strings in order, with knowledge of their ordinal. You can scan the list in time O(n). You can also lookup, insert, move, and delete in time O(n) each. If you don't actually care about performance then I would strongly suggest going this way.

If you do care about performance, then you'll need to build a custom data structure. The simplest idea is to have two trees. One tree stores the strings in alphabetical order, and tells you where in the other tree the string is. The other tree stores the strings in order of the ordinals, and stores counts of how much stuff is in various subtrees.

Now here are your basic operations.

• Insert. Insert in the second tree at the correct position (if you choose to move anything else in the process, updating those things in the first tree), then insert the string in the first tree.
• Lookup by string. Search the first tree, find where it is in the second tree, walk back in the second tree to find its ordinal.
• Lookup by ordinal. Search the second tree, find the string.
• Delete. Delete from both trees.
• Move ordinal. Remove from the second tree in the old position. Insert into the second tree in the new position. Update all appropriate nodes in the first tree.

For the simple version you can just use trees. If you want to get fancy, you can look up B-Trees, Red-Black trees and other types of self-balancing trees, then pick one of those.

If you program this correctly you can guarantee that all operations take time O(log(n)). However there will be a lot of constant overhead, and for small collections the effort to be clever may be a loss relative to the simple approach.