Поддержание правильного порядка коллекции ординалов - PullRequest
1 голос
/ 04 июня 2011

У меня есть простой объект домена:

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

Я хочу иметь коллекцию этого объекта домена, которая поддерживает правильный порядковый номер. Например, дано 4 любимых блюда:

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

Если я изменю порядковый номер Пиры на 4, это должно сместить порядковый номер Арбуза до 3.

Если я добавлю новое любимое блюдо (клубника) с порядковым номером 3, то должно сместиться Груша до 4, а Арбуз до 5.

Если я изменю порядковый номер Пиры на 2, это должно сместить Оранжевый до 3.

Если я изменю порядковый номер арбуза на 1, у Banana увеличится до 2, у Orange - до 3, а у Pear - до 4.

Какой лучший способ сделать это?

ОБНОВЛЕНИЕ : Свойство name объекта домена является динамическим и основано на пользовательском вводе. У объекта должно быть это свойство Ordinal, поскольку пользователь может изменить порядок отображения своих любимых блюд. Это порядковое значение сохраняется в базе данных, и при заполнении структуры я не могу гарантировать, что элементы добавляются в порядке их порядков.

Проблема, с которой я сталкиваюсь, заключается в том, что при изменении базового объекта домена не существует хорошего способа обновления остальных элементов в списке. Например:

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?

До сих пор я пытался сделать следующее, что работает:

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
    {
        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++;
        }
    }
}

Это работает нормально, но использование внутреннего поля Ordinal - странный обходной путь. Это необходимо для того, чтобы PropertyChangingEvent не поднимался бесконечно.

Ответы [ 4 ]

3 голосов
/ 04 июня 2011

Просто используйте List<string>:

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

Не стоит «хранить» этот порядковый номер, если он должен изменить то, как вы описываете.

0 голосов
/ 04 июня 2011

Позвольте мне повторить вашу проблему.

У вас есть коллекция строк.У вас есть коллекция ординалов.

Вы хотите, чтобы можно было быстро найти порядковый номер строки.И строка ординала.Вы также хотели бы иметь возможность вставить строку с заданным порядковым номером.И измените порядковый номер строки.

Есть два пути.Первый, простой, подход заключается в том, чтобы хранить последовательность строк по порядку со знанием их порядкового номера.Вы можете отсканировать список за время O(n).Вы также можете искать, вставлять, перемещать и удалять по времени O(n) каждый.Если вы на самом деле не заботитесь о производительности, я бы настоятельно рекомендовал пойти по этому пути.

Если вам не безразлична производительность, вам нужно будет создать собственную структуру данных.Самая простая идея - иметь два дерева.Одно дерево хранит строки в алфавитном порядке и сообщает вам, где в другом дереве находится строка.Другое дерево хранит строки в порядке порядковых номеров и хранит счет того, сколько вещей содержится в различных поддеревьях.

Теперь приведем основные операции.

  • Вставка.Вставьте второе дерево в правильную позицию (если вы решите переместить что-либо еще в процессе, обновляя эти элементы в первом дереве), затем вставьте строку в первое дерево.
  • Поиск по строке.Найдите первое дерево, найдите его во втором дереве, вернитесь во второе дерево, чтобы найти его порядковый номер.
  • Поиск по порядковому номеру.Найдите второе дерево, найдите строку.
  • Удалить.Удалить из обоих деревьев.
  • Переместить порядковый номер.Удалить из второго дерева в старом положении.Вставьте во второе дерево в новой позиции.Обновите все соответствующие узлы в первом дереве.

Для простой версии вы можете просто использовать деревья.Если вы хотите получить фантазию, вы можете найти B-деревья, красно-черные деревья и другие типы самобалансирующихся деревьев, а затем выбрать одно из них.

Если вы запрограммируете это правильно, вы можете гарантировать, что всеОперации занимают время O(log(n)).Однако будет много постоянных накладных расходов, и для небольших коллекций усилие быть умным может оказаться потерей относительно простого подхода.

0 голосов
/ 04 июня 2011

Я бы сделал что-то вроде следующего:

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 ;
    }
  }

}
0 голосов
/ 04 июня 2011

Похоже, вы хотите SortedList Добавьте каждый элемент, используя его Ordinal в качестве ключа.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...