Keeping a sorted list of elements, sorted by an attribute external to that element

Question

I have a "manager" class maintaining a list of objects. Each Object has a certain "position", but this is not known to them, only the manager knows about this. The manager must assign each Object a position and maintain its list of Objects sorted according to this "external attribute".

Note that an Object's position can change at any time. Ideally I should be able to immediately get either Element at position X or the position of Element X at any time.

This is C# code. I am wondering what would be a clean or idiomatic way of doing this.

I thought about making an internal class like this:

class SortedElement {
    public Element Elem { get; set; }
    public int Position { get; set; }
}

And then maintain a list of SortedElements. I don't know, it seems clumsy to me. Two SortedElements could have the same Position for instance. I feel like there's an obvious, clean solution which I'm missing. I could also make the Position a property of the Elements themselves, but it doesn't make sense semantically, meaning there's no reason for them to know about that except making my life easier.

Please make me go facepalm.

EDIT: Following Eric Lippert's advice of listing my requirements, and a good night's sleep, I realized I should opt for a LinkedList<Element> and use the index as position. Indeed, the most common operations here will be insertion at the beginning and removal anywhere within the container, which are expensive on an array-based container. Thanks for all replies.

Answer 1

You seem to be taking pains to avoid describing the collection as a simple sequence of elements, so I'll assume a List<T> and using the index as position is out of the question. What about a Dictionary<int, Element>? It enforces uniqueness and assuming this "position" you refer to is ordinal, maintains proper sorting.

Answer 2

You could maintain the list of elements internally to the "manager" class using a generic list (List<Element>). You could then sort the list however you wanted using the Sort() method of the List<T> class. For example:

myList.Sort((elem1, elem2) => elem1.Name.CompareTo(elem2.Name));

In this example the elements are sorted by the property "Name", but you could use anything in the comparison, including your "external attribute".

Answer 3

Let's list your requirements. I assume you want to have a data structure S which has the following operations:

• ContainsElement: takes an element, tells you whether the element is in S
• IsValidPosition: takes a Position, tells you whether that position is available in S
• GetElementAt: takes a valid Position, returns an Element
• GetPositionOf: takes an Element which is in S, returns a Position
• InsertElementAt: takes an Element not in S and a valid Position. Puts the element at that position; all elements after that position move "up by one".
• RemoveElementAt: takes a valid Position, removes the element at that position, all elements after that position move "down one".

Is that a correct summary of the operations you want? (Note that moving an element to a new position is the same as RemoveElementAt followed by InsertElementAt.)

If those are not a correct summary of the operations, then it would be helpful if you'd list exactly the set of operations you want your abstract data type to support.

Once we have a clear list of requirements for operations then the next question is "what are the asymptotic performance requirements?"

For example, you could use a List<T> as your data structure S; it supports all of those operations. However, if the list is very long then inserting and removing at the beginning of the list is very expensive, as is the "Contains" operation.

There are more exotic data structures you can use that are highly efficient at modeling insertions and removals; we use such data structures to model changes to the state of the editor in the C# IDE. Obviously each token, variable declaration, and so on, is an "element" that has a "position" and that position changes all the time as you type around it; handling those changes in an efficient manner is quite challenging, but if that's the sort of problem space you're in, then describe it more clearly and we can give you pointers on data structures you can do some research on.

Answer 4

I think you should really use a SortedDictionary.