Overview:
So while I was trying to validate my List design I started thinking about other things I could do with a List. Obviously I could add selection but that just seemed boring. I happened to be watching some NASCAR at the time and an idea popped in my head. If I were writing an application with real time race information, I would really need to sort some data. Further, since this data would be highly dynamic it wouldn’t be viable to rely on the data source to sort this data either. Additionally, we may want to display two different views of the same data. For race information, one view might sort by current race position while another view might sort by current speed or time of the driver’s last lap. So I had my answer. How could I develop a Sorted List View on top of my current List infrastructure?
Simplifying our Use Case
With some thought on what would be involved to accomplish this goal, I immediately started trying to simplify my problem. First, how would I do my sorting? I think a tree would be most appropriate but I don’t need to be efficient on my first pass. I am not going to implement a binary tree, but I will make sure it will be straightforward replace my linear sort/search with a logarithmic algorithm at a later time. Secondly, will I support an observable list? This is actually a pretty interesting question. At first thought, it sounds like an important feature but note that I am not talking about listening for value changes I am talking about list changes. I will obviously want to watch for data changes in the list, but do I need to watch for list changes? After more thought I concluded that 1) it wasn’t needed for my use case (new drivers won’t enter the race) and 2) I’m not even sure it’s viable for the general scenario and 3) I already implemented binding to an observed list so the excitement was gone J. Ok, Again, I will not implement binding to an observed list, but I will make sure I know where to place this logic when I add it later. Finally, will I queue updates or handle them synchronously? Same decision – I will defer until later.
Design:
So I looked at the components I needed to develop and might develop in the future and came up with the following design.
Sorted List Class Diagram
SortedList
The SortedList class will inherit from my existing ListBase class. The ListBase class provides ItemType initialization without doing any binding. The SortedList defines the following properties.
1) ItemsSource – bound list of items
2) SortProperty – Property to sort by
3) SortOrder – Asc or Desc?
4) Top – How many items to display
The SortedList class will implement Top functionality as well as maintaining the displayed list items. In the future it will also implement binding to an observable collection. It will not do any sorting itself. This class will rely on a SortedListManager to maintain sorted items. I put Add and Remove methods on the SortedListManager. Currently, I just call Add, but when I implement an observed binding, I will have to utilize remove as well.
SortedListManager
The SortedListManager class maintains the sorted order of items in the source list. In the future, this class will also implement queuing before doing the re-sort. It will also be updated to a logarithmic algorithm. The SortedListManager will communicate updates to the sorted order of items via a ListUpdated event that the SortedList will listen to and handle. To monitor the individual list items, the SortedListManager will attach listeners to the individual objects INotifyPropertyChanged interfaces.
DataObjectWatcher
The DataObjectWatcher listens for updates to the individual data objects. It does this by binding to the objects INotifyPropertyChanged interface. When I first wrote this class it just had a SourceIndex property which was the index of the watched object in the source array. This way when I received the PropertyChanged event, I would know exactly which item changed. As I got further with development this object changed completely so I would like to spend some time discussing the important properties in detail.
KnownValue : I added the KnownValue attribute on this class to keep a local copy of the data objects sorted property value. This property isn’t so useful now but when I implement event queuing this will be an extremely important attribute. When we have multiple pending updates to re-sort, it will be an error to always sort against other data objects current values because those values may themselves be a pending update. Sorting against current values could lead to incorrectly ordering the items.
DataObject: I’ll be perfectly honest; I wasn’t thrilled about having this property here! While developing the SortedList I realized that it was going to be important to have the SortedList class “own” the original list. By this, I mean that the SortedList was going to monitor the source list for changes and then call appropriate Add/Remove methods on the SortedListManager. This way I simplified the SortedListManager class. It also occurred to me that this not only simplified the SortedListManager but it also added to the overall functionality by allowing for use cases which don’t actually include a source list! Now, at that time I could have asserted for non source list scenario’s that the SortedList class would create its own internal List but that would create unnecessary complexity in the SortedList class. I decided that having the DataObject Property here, not a ‘SourceIndex’ property into the original list, was the best solution.
Implementation (top down)
SortedList
Start with the skeleton including dependency properties:
public enum SortOrder { Asc, Desc };
public class SortedList<ItemType, DataObjectType> : ListBase<ItemType, DataObjectType>
where ItemType : FrameworkElement, new()
where DataObjectType : INotifyPropertyChanged
{
#region Members
private SortedListManager<DataObjectType> _manager;
#endregion
#region Dependency Properties
public static readonly DependencyProperty SortPropertyProperty;
public static readonly DependencyProperty SortOrderProperty;
public static readonly DependencyProperty ItemsSourceProperty;
public static readonly DependencyProperty TopProperty;
public SortOrder SortOrder
{
get { return (SortOrder)GetValue(SortOrderProperty); }
set { SetValue(SortOrderProperty, value); }
}
public string SortProperty
{
get { return (string)GetValue(SortPropertyProperty); }
set { SetValue(SortPropertyProperty, value); }
}
public int Top
{
get { return (int)GetValue(TopProperty); }
set { SetValue(TopProperty, value); }
}
public IList<DataObjectType> ItemsSource
{
get { return (IList<DataObjectType>)GetValue(ItemsSourceProperty); }
set { SetValue(ItemsSourceProperty, value); }
}
#endregion
#region Constructor
public SortedList()
{
}
static SortedList()
{
SortPropertyProperty = DependencyProperty.Register(
“SortProperty”, typeof(string),
typeof(SortedList<ItemType, DataObjectType>), null);
ItemsSourceProperty = DependencyProperty.Register(
“ItemsSource”, typeof(IList<DataObjectType>),
typeof(SortedList<ItemType, DataObjectType>), null);
SortOrderProperty = DependencyProperty.Register(
“SortOrderProperty”, typeof(SortOrder),
typeof(SortedList<ItemType, DataObjectType>), null)
TopProperty = DependencyProperty.Register(
“TopProperty”, typeof(int),
typeof(SortedList<ItemType, DataObjectType>),
new PropertyMetadata(-1));
}
#endregion
Then Include Some Initialization Logic:
public override void OnApplyTemplate()
{
base.OnApplyTemplate();
Initialize();
}
private void Initialize()
{
_manager = new SortedListManager<DataObjectType>(SortProperty, SortOrder);
_manager.ListUpdated += new ListEventHandler<DataObjectType>(_manager_ListUpdated);
if (null != base.Panel)
{
base.Clear();
for ( int i = 0; i < ItemsSource.Count; ++ i )
_manager.AddItem(ItemsSource[i]);
}
}
And finally logic to handle list changed events:
void _manager_ListUpdated(object sender, ListEventArgs<DataObjectType> args)
{
switch (args.EventType)
{
case ListEventType.Insert:
HandleInsert(args);
break;
case ListEventType.Move :
HandleMove(args);
break;
}
}
private void HandleInsert(ListEventArgs<DataObjectType> args)
{
if (Top < 0) // top not used
base.InsertItem(args.NewIndex, args.DataObject);
else
{
if (args.NewIndex < Top) // insert into top
{
base.InsertItem(args.NewIndex, args.DataObject);
if (Count > Top) // remove old top
RemoveAt(Top);
}
}
}
private void HandleMove(ListEventArgs<DataObjectType> args)
{
if (Top < 0) // Top not used
base.Move(args.OldIndex, args.NewIndex);
else
{
if (args.NewIndex < Top) // Moved into top
{
if (args.OldIndex < Top) // From within top
{
base.Move(args.OldIndex, args.NewIndex);
return;
}
else // From outside top
{
InsertItem(args.NewIndex, _manager[args.NewIndex]);
if (Count > Top)
RemoveAt(Top);
}
}
else if (args.OldIndex < Top) // Moved out of top
{
base.RemoveAt(args.OldIndex);
if (_manager.Count >= Top)
InsertItem(Top – 1, _manager[Top - 1]);
}
}
}
Sorted List Manager: ( a linear implementation)
public class SortedListManager<DataObjectType>
where DataObjectType : INotifyPropertyChanged
{
private delegate bool LessThanDelegate(IComparable a, IComparable b);
#region members
private PropertyInfo _propertyInfo;
private LessThanDelegate _comparer;
private List<DataObjectWatcher<DataObjectType>> _list;
#endregion
#region Events
public event ListEventHandler<DataObjectType> ListUpdated;
#endregion
#region Properties
public int Count
{
get { return _list.Count; }
}
public DataObjectType this[int index]
{
get { return _list[index].DataObject; }
}
#endregion
#region Constructor
public SortedListManager( string sortProperty, SortOrder order)
{
_propertyInfo = typeof(DataObjectType).GetProperty(sortProperty);
_list = new List<DataObjectWatcher<DataObjectType>>();
if (SortOrder.Asc.Equals ( order ))
_comparer = delegate(IComparable a, IComparable b)
{
return (a.CompareTo(b) <= 0);
};
else
_comparer = delegate(IComparable a, IComparable b)
{
return (a.CompareTo(b) >= 0);
};
}
#endregion
#region List Updates
public void AddItem(/*int index,*/ DataObjectType dataObject)
{
DataObjectWatcher<DataObjectType> watcher =
new DataObjectWatcher<DataObjectType>( _propertyInfo.Name,dataObject);
watcher.KnownValue = (IComparable)_propertyInfo.GetValue(dataObject,null);
watcher.DataObjectUpdated +=
new DataObjectChangeHandler(watcher_DataObjectUpdated);
DataObjectWatcherInserted(watcher);
}
public void RemoveItem(int sourceIndex)
{
}
#endregion
#region Data Object Updates
void watcher_DataObjectUpdated(object sender)
{
DataObjectWatcherUpdated (( DataObjectWatcher<DataObjectType>) sender);
}
private void DataObjectWatcherInserted(DataObjectWatcher<DataObjectType> watcher)
{
lock (this)
{
int index = FindIndex ( watcher.KnownValue);
_list.Insert(index, watcher);
ListUpdated(this,
new ListEventArgs<DataObjectType>(
ListEventType.Insert, watcher.DataObject, -1, index));
}
}
private int FindIndex(IComparable knownValue)
{
int index = 0;
for (index = 0; index < _list.Count; ++index)
{
if (_comparer(knownValue, _list[index].KnownValue))
break;
}
return index;
}
private void DataObjectWatcherUpdated(DataObjectWatcher<DataObjectType> watcher)
{
lock (this)
{
watcher.KnownValue =
(IComparable)_propertyInfo.GetValue( watcher.DataObject,null);
int sourceIndex = _list.IndexOf(watcher);
_list.RemoveAt(sourceIndex);
int destinationIndex = FindIndex(watcher.KnownValue);
_list.Insert(destinationIndex, watcher);
ListUpdated(this,
new ListEventArgs<DataObjectType>(
ListEventType.Move, watcher.DataObject, sourceIndex, destinationIndex));
}
}
#endregion
}
DataObjectWatcher
public delegate void DataObjectChangeHandler (object sender );
public class DataObjectWatcher<DataObjectType>
where DataObjectType : INotifyPropertyChanged
{
#region Members
private string _monitoredProperty;
#endregion
#region Properties
public IComparable KnownValue { get; set; }
public DataObjectType DataObject { get; set; }
#endregion
#region Events
public event DataObjectChangeHandler DataObjectUpdated;
#endregion
#region Constructors
public DataObjectWatcher( string monitoredProperty, DataObjectType dataObject)
{
DataObject = dataObject;
_monitoredProperty = monitoredProperty;
dataObject.PropertyChanged +=
new PropertyChangedEventHandler(dataObject_PropertyChanged);
}
#endregion
void dataObject_PropertyChanged(object sender, PropertyChangedEventArgs e)
{
if (e.PropertyName == _monitoredProperty)
{
if (null != DataObjectUpdated)
DataObjectUpdated(this);
}
}
}
And some miscellaneous classes
public enum ListEventType { Insert, Remove, Move };
public class ListEventArgs<DataObjectType>
{
public ListEventArgs()
{
}
public ListEventArgs(ListEventType eventType,
DataObjectType dataObject, int oldIndex, int newIndex)
{
EventType = eventType;
DataObject = dataObject;
OldIndex = oldIndex;
NewIndex = newIndex;
}
public ListEventType EventType { get; set; }
public int OldIndex { get; set; }
public int NewIndex { get; set; }
public DataObjectType DataObject{ get; set; }
}
public delegate void ListEventHandler<DataObjectType>(
object sender, ListEventArgs<DataObjectType> args);
