Priority List implementation suggestions

[Trips]

Hi,
I need to implement an itterable priority list, preferably sorted on add. with all the standard functions for add / remove etc...
at the moment, the best I can come up with is a cached lazy sort on request method, which is alright but doesnt make for a consistent or efficient priority list.
Something like this:

<pre lang="x-c# class PriorityList<Pri, Val> where Pri : IComparable
{
List<PriorityListItem> Items;

public bool Sorted { get; set; }

public PriorityList()
{
Items = new List<PriorityListItem>();
Sorted = true;
}

public void Add(Pri priority, Val value)
{
Items.Add( new PriorityListItem( priority, value ) );
Sorted = false;
}

public Val this[int i]
{
get
{
if ( !Sorted )
{
Items.Sort(
( a, b ) => a.Priority.CompareTo( b.Priority )
);

Sorted = true;
}

return Items.Value;
}
}

class PriorityListItem
{
public Pri Priority { get; set; }
public Val Value { get; set; }

public PriorityListItem( Pri priority, Val value )
{
Priority = priority;
Value = value;
}
}
}[/code]

<div style="color:Black; background-color:White
<pre><span style="font-family:Verdana,Arial,Helvetica,sans-serif; white-space:normal The only alternative I can think of is a binary search tree, but then changing the priority of an element would involve collossal overhead. and the retrieves would only be efficient if the list is small.[/code]


Any suggestions?


View the full article