Self-renewing concurrency collection
I am trying to create a self-updating collection. Each item in the collection has a position (x, y). When the position changes, an event occurs and the collection will move the item.
A "jagged dictionary" is used within the collection. The external dictionary uses the x-coordinate key a, while the nested dictionary uses the y-coordinate key a. The nested dictionary then has a list of items as a value.
The collection also stores a dictionary for storing the position of the positions stored in nested dictionaries - an element for finding the stored location.
I am having problems with collection security, which is what I really need.
Source code for the collection:
public class PositionCollection<TItem, TCoordinate> : ICollection<TItem>
where TItem : IPositionable<TCoordinate>
where TCoordinate : struct, IConvertible
{
private readonly object itemsLock = new object();
private readonly Dictionary<TCoordinate, Dictionary<TCoordinate, List<TItem>>> items;
private readonly Dictionary<TItem, Vector<TCoordinate>> storedPositionLookup;
public PositionCollection()
{
this.items = new Dictionary<TCoordinate, Dictionary<TCoordinate, List<TItem>>>();
this.storedPositionLookup = new Dictionary<TItem, Vector<TCoordinate>>();
}
public void Add(TItem item)
{
if (item.Position == null)
{
throw new ArgumentException("Item must have a valid position.");
}
lock (this.itemsLock)
{
if (!this.items.ContainsKey(item.Position.X))
{
this.items.Add(item.Position.X, new Dictionary<TCoordinate, List<TItem>>());
}
Dictionary<TCoordinate, List<TItem>> xRow = this.items[item.Position.X];
if (!xRow.ContainsKey(item.Position.Y))
{
xRow.Add(item.Position.Y, new List<TItem>());
}
xRow[item.Position.Y].Add(item);
if (this.storedPositionLookup.ContainsKey(item))
{
this.storedPositionLookup[item] = new Vector<TCoordinate>(item.Position);
}
else
{
this.storedPositionLookup.Add(item, new Vector<TCoordinate>(item.Position)); // Store a copy of the original position
}
item.Position.PropertyChanged += (object sender, PropertyChangedEventArgs eventArgs) => this.UpdatePosition(item, eventArgs.PropertyName);
}
}
private void UpdatePosition(TItem item, string propertyName)
{
lock (this.itemsLock)
{
Vector<TCoordinate> storedPosition = this.storedPositionLookup[item];
this.RemoveAt(storedPosition, item);
this.storedPositionLookup.Remove(item);
}
this.Add(item);
}
}
I wrote a simple unit test to check for concurrency issues:
[TestMethod]
public void TestThreadedPositionChange()
{
PositionCollection<Crate, int> collection = new PositionCollection<Crate, int>();
Crate crate = new Crate(new Vector<int>(5, 5));
collection.Add(crate);
Parallel.For(0, 100, new Action<int>((i) => crate.Position.X += 1));
Crate same = collection[105, 5].First();
Assert.AreEqual(crate, same);
}
The actual stored position changes every time I run the test. I appreciate any feedback you may have.
a source to share
Perhaps you can keep the lock list per X coordinate to improve concurrency, otherwise you won't see much performance benefit.
Alternatively, you can switch to Quad-Tree or some other spatial indexing system to minimize data structure disturbance as items move. With Quad-Tree, you can minimize concurrency problems by holding independent locks at individual levels of the tree, rather than the width of the entire data structure.
Your data structure is very expensive to track moving objects as it needs to be updated almost constantly. Using the "bracketed" approach (if you have constraints on the X / Y coordinates), you can restrict updates only when the item has changed buckets.
private void UpdatePosition(TItem item)
{
// each bucket holds some MxN section of the X,Y grid
var nextBucket = CalculateBucket(item.Position);
if (nextBucket != item.Bucket)
{
lock (wholeCollectionLock)
{
this.buckets[nextBucket].Add(item);
this.buckets[item.Bucket].Remove(item);
item.Bucket = nextBucket;
}
}
}
public IEnumerable<TItem> ItemsAt(TPosition position)
{
var bucket = CalculateBucket(position);
lock (wholeCollectionLock)
{
// this will be efficient enough for cases where O(n) searches
// have small enough n's
// needs to be .ToArray for "snapshot"
return this.buckets[bucket].Where(xx => xx.Position == position).ToArray();
}
}
a source to share