Sparse sorted numeric sequence class for .NET

Question

Hello everyone. I'm in need of very specific class, I would really like to know if there is existing one, so I don't have to re-implement it. I have a set of items. Each item has a numeric value associated whit it - weight. Weight of each item is unique within set. Items must be sorted by weight. Weight can be modified for each item, but the operation to change weight is extremely expensive. There is an operation, which executes on set frequently - move range of items within set, by modifying item's weight. So I need a List kind class, but with built-in logic to manage items weights. Weight sequence must be sparse to minimize weight collisions on move operations and improve performance by minimizing weight change operations. Class interface should look like that:

public abstract class SparsedSequence<T> : IList<T>
{
    // Weight increment for new items.
    private int WeightIncrement = 10000;

    protected abstract void OnWeightChanged(int weight, T item);

    public void MoveRange(int offset, int count, int amount)
    {
        // There must be fancy weight management logic.
    }

    public void MoveRange(T[] range, int amount)
    {
        // Cut T[] to set of calls to MoveRange(int, int, int)
    }

    public int ConstraintAmount(int offset, int count, int amount)
    {
        // Returns amount constrainded by sequence size and 0, 
        // so that moved block will remain within proper range.
        // If returns 0 - block unmovable in that direcion.
    }

    public int ConstraintAmount(T[] range, int amount)
    {
        // ----- " -----
    }

    public void Add(T newItem)
    {
        // Add to sequnce end.
        // Defines new weight and calls OnWeightChanged.
        // NewWeight = Weights[Count - 1] + WeightIncrement.
    }

    public void Add(T item, int weight)
    {
        // Adds item with forced weight.
    }

    public T this[int index]
    {
        // Get item
        get { ... }
    }

    public IList<int> Weights
    {
        // Get items weights
        get { ... }
    }

    public KeyValuePair<int, T> this[int index]
    {
        // Get item and weight
        get { ... }
    }

    // Remove, clear, insert, indexof etc.
}

Haven't found anything similar in framework or PowerCollections. I guess you already figured out that I intend to use this class to manage database ordered record set operations :) Thanks.

Answer 1

You could internally use a SortedList<int, T>. It doesn't allow you to modify the keys, but when you want to modify an item's weight, you could remove the item at the old weight and insert it again at the new weight. I'm not sure if that would cause too much of a performance hit though.