Introduction
Every so often a class comes along that will truly change your life as a programmer. It will fit in like glue everywhere; binding together all your unfinished code, resolving your past issues, and literally simplifying everything. It might even make your friends like you more.
This, dear reader, is not one of those classes.
It
is a helpful class, however. But I'm getting ahead of myself, first let me explain the problem I was facing, and how this class developed. With that perspective I will demonstrate how it works and, if you are still with me, some of the nuts and bolts of its (very quick) implementation. Finally, I'll just provide the class.
The problem was this: I was working on a GUI that contained a spinner control whose databinding would change on the selection of another control. The spinner control's integer value could be selected, or not selected, but if it were selected I wanted that value to be unavailable to the other data references that were using it. In other words, when a value, say "1," was selected and then the reference changed, "1" would be skipped and only 2 through
n would be available.
In the land of metaphors, this would be analogous to a number waiting system at the Department of Motor Vehicles (or insert your favorite government agency here). If you are old enough, you'll remember that this used to be accomplished by a little red machine that had a ticket you would pull, subsequently followed by a decent into madness as you stared at a little "Now Serving Number" sign. But I digress. In this example, the building represents the control. The tickets or numbers are the values in the list, and the people are the data references. Once a person has a number it is unavailable to others. Although it is very much possible for a person to need to leave (maybe their lunch hour is up) and return their number to the pool.
Ok, so the goal was to move this "availability" logic out of the GUI's code and into a container class that would:
- Take a shared SortedSet amongst instances.
- Provide accessor functions to move up and down the list.
- Provide a "neutral" value. That is, a value that is not in the list so a reference could not be holding on to anything.
- And, what the heck, since we're doing this... let's do this. Make it a generic so the container will take any type.
- Support the increment (++) and decrement (--) operators for those types that support it.
So now that you have the background, let's see it in use.
Usage
Let's start with a caveat. This class was coded towards my convenience and not performance, so it is entirely possible that ListLimitedItem might not scale to your needs (I am using a SortedSet, after all). That being said, for a reasonable number of references and a list measuring less than 1e6, you should be ok. No promises, of course.
Ok let's look at instantiation and use of an
int based
ListLimitedItem object.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ListLimitedItem;
namespace ListLimitedItemExample
{
class Program
{
static void Main(string[] args)
{
//
// ListLimitedItem with an integer set
//
//create a set of ints numbering between 1 and 20
SortedSet<int> available_nums = new SortedSet<int>(Enumerable.Range(1, 20));
//lets get rid of 11 - 14 to simulate that these numbers are in use by other
//instances of ListLimitedItem
available_nums = new SortedSet<int>(available_nums.Where(x => x <= 10 || x >= 14));
//we pass in the SortedSet<t> as well as what value is a "neutral" number. If set to the
//neutral, any existing value is returned to the list and the ListLimitedItem no longer
//occupies any values. Here we pass in the default for int, which is zero.
ListLimitedItem<int> testItemInt = new ListLimitedItem<int>(ref available_nums, default(int));
//testItemInt starts with the neutral value of zero.
Console.WriteLine("testItemInt Currrent Value: {0}", testItemInt.Value);
testItemInt.moveUpTo(10); //moves and occupies 10, 10 is removed from the list
testItemInt.moveUpTo(11); //There isn't an 11, so 14 is occupied. 10 is returned to the list.
testItemInt.moveUpTo(12); //There isn't a 12, but 14 is already occupied. Since moving up, stay at 14.
testItemInt.moveUpTo(13); //There isn't a 13, but 14 is already occupied. Since moving up, stay at 14.
testItemInt.moveUpTo(14); //14 is already occupied. Since moving up, stay at 14.
testItemInt.moveUpTo(15); //moves and occupies 15, 14 is returned to the list.
testItemInt.moveUpTo(16); //moves and occupies 16, 15 is returned to the list.
testItemInt.moveUpTo(20); //moves and occupies 20, 16 is returned to the list.
testItemInt.moveUpTo(21); //20 is the highest value, and it is already occupied. Since moving up, stay at 20.
testItemInt.moveUpTo(22); //20 is the highest value, and it is already occupied. Since moving up, stay at 20.
//testItemInt.moveDownTo(...) follows the same pattern of rules, but in the opposite direction
//for those classes that implement the increment/decrement operator, the appropriate unary operators can be used.
//If the object doesn't, nothing happens.
//move back to the neutral position
testItemInt.moveDownTo(testItemInt.AllowedNeutralItem);
testItemInt++; //moves and occupies 1, 1 is removed from the list
testItemInt--; //1 is the lowest value, and it is already occupied. Since moving down, stay at 1.
}
}
}
Alright, so the above example pretty much demonstrates all the class features. The
SortedSet stuff is just to create a list from 1 to 20 and remove some values to demonstrate what the class would do when those integers are missing (presumably being held by other references). I didn't want to include other references to keep things simple.
The instantiation just has you passing in the
SortedSet, and setting what the neutral item is going to be. The default value of an
int is 0.
Next, the
moveUpTo(...) method is shown and since it is explained step by step in the comments I'll let it stand at that. Just know that the argument that you are "moving up to" is a request. If that value is not available, the next highest value will be taken. If there are no values greater than the current position, the value stays put. This might mean that the instance remains on the neutral item (not getting any values from the list). The
moveDownTo(...) method has the same behavior but, predictably, in the opposite direction of the list. Finally, an example of moving to the neutral item is displayed, followed by an example of using the decrement/increment operators as an alternative for the accessor functions (that is, since
int supports them).
NOTE: Only use the decrement/increment operators if you know the type supports them. If it isn't supported, nothing will happen in your code though a costly InvalidOperationException is being swallowed at each attempt (See below).
"But what of a type that isn't a number?" you ask. Let's answer that by looking at a
DateTime SortedSet.
//
//ListLimitedItem test with a non-numeric
//
SortedSet<DateTime> available_dates = new SortedSet<DateTime>();
//Base after now. When..? Just now. We're at now now.
DateTime dtime1 = DateTime.Now;
//As before, let's make a gap and start the next datetime as 4 days from dtime1
DateTime dtime2 = dtime1.AddDays(4);
DateTime dtime3 = dtime1.AddDays(5);
DateTime dtime4 = dtime1.AddDays(6);
//Just to show that the SortedSet will automatically sort
available_dates.Add(dtime4);
available_dates.Add(dtime1);
available_dates.Add(dtime3);
available_dates.Add(dtime2);
//Here let's set the neutral position as the DateTime's MinValue
ListLimitedItem<DateTime> testItemDateTime = new ListLimitedItem<DateTime>(ref available_dates, DateTime.MinValue);
testItemDateTime.moveUpTo(dtime1); //move to first position of dtime1. It is removed from the list
DateTime dtime_target = dtime1.AddDays(3); //let's purposely create a date that falls in the hole
//between dtime1 and dtime2... again to simulate that this time
//is occupied.
testItemDateTime.moveUpTo(dtime_target); //There isn't a dtime_target value, so dtime2 is occupied. dtime1 is returned to the list.
testItemDateTime++; //increment/decrement is not implemented by DateTime. So nothing happens here. Except an invisible InvalidOperationException.
No surprises here. It functions in the same way as an
int based set. That is, of course, with the exception of the decrement/increment not being supported and the neutral item is the minimum
DateTime value.
"But what if I want to use my own custom type?", you ask. Ok now you are just being difficult. Fine. Here's an example with a class that implements IComparable.
public class dumbTest : IComparable
{
public string Name { get; set; }
public int Ordinal { get; set; }
public int NextOrdinal { get; set; }
public int CompareTo(object obj)
{
dumbTest dt = obj as dumbTest;
if (dt == null)
throw new InvalidOperationException("The type'" + obj.GetType().Name + "' compare is not supported.");
if (this.Ordinal > dt.Ordinal)
return 1;
else if (this.Ordinal < dt.Ordinal)
return -1;
else
return 0;
}
}
And here is the custom type in action:
SortedSet<dumbTest> available_nums3 = new SortedSet<dumbTest>();
dumbTest a = new dumbTest();
a.Name = "a";
a.Ordinal = 1;
available_nums3.Add(a);
dumbTest b = new dumbTest();
b.Name = "b";
b.Ordinal = 2;
available_nums3.Add(b);
ListLimitedItem<dumbTest> dumblist = new ListLimitedItem<dumbTest>(ref available_nums3, null);
ListLimitedItem<dumbTest> dumblist2 = new ListLimitedItem<dumbTest>(ref available_nums3, null);
dumblist.moveUpTo(b); //move to b
dumblist2.moveUpTo(a); //move to a
And that should be all you need to use it! Next, let's look at a couple of interesting points in the implementation of
ListLimitedItem.
Inspection
Since you will have the entire class to look through at your leisure (and since this is already a long post), I'll focus only on a couple of interesting points in the code.
First, let's look at the LINQ used to find the next value. All roads lead to getItem(...), so it is not a surprise that it lives there.
T next_item = allowed_neutral_item;
lock (available_items)
{
try
{
//If the set has the item, we're done. Otherwise, use LINQ to find the closest
//item.
if (available_items.Contains(requested_item))
next_item = requested_item;
else
next_item = (isForward) ? available_items.Where(n => n.CompareTo(requested_item) >= 0).First() : available_items.Where(n => n.CompareTo(requested_item) <= 0).Last();
}
catch (Exception err)
{
//This should never happen, but in case it does throw a ListLimiteItemException.
string base_message = "An exception occured seeking the next list position.";
if (err is NullReferenceException)
{
if (available_items == null)
base_message += " The available items internal list is null.";
if (requested_item == null)
base_message += " The requested item is null.";
}
throw new ListLimitedItemException(base_message, err);
}
available_items.Remove(next_item);
addBackItem(next_item);
}
selected_item = next_item;
This is the heart of the class, I'd say. Most of the other stuff is either gating to here, or list handling (
addBackitem(...), for example), but this is what does the actual "finding." When you really look at it, it is pretty straight forward. The next_item variable is set to the neutral value, after which me make an attempt to find their requested value in the list. If it's there, the search is over. If not, we need to find the next nearest so LINQ is used. The ternary operator just divides the direction of the LINQ search: we will find either the last or first item, depending on traversal direction. If something fails unexpectedly in the seek, a
ListLimitedItemException is thrown. So your client code should be prepared to handle that.
After the next candidate is found, the item is removed from the availability list, and the previous item (the item the class is giving up for the move) is added back.
The second part of the code I wanted to draw attention to was not my idea, which is of course why I found it interesting. I was trying to think of a way to be able to add an overload for the increment operator on a generic type but wasn't getting there. I found this little
gem by Marc Gravell showing how to do so using LINQ Expressions (Note the aforementioned
InvalidOperationException that may be caught and swallowed).
/// <summary>
/// The overloaded increment operator. If not supported by the underlying type, the
/// item is unchanged.
/// SOURCE: The expression technique, for me at least, can be attributed to Marc Gravell from here: http://www.yoda.arachsys.com/csharp/genericoperators.html
/// </summary>
/// <param name="li">Current ListLimitedItem</param>
/// <returns>The incremented ListLimitedItem</returns>
public static ListLimitedItem<T> operator ++(ListLimitedItem<T> li)
{
if (li.selected_item != null && li.available_items.Count > 0 && li.selected_item.CompareTo(li.available_items.Last()) < 0 && HasIncrementOperator(typeof(T)))
{
try
{
if (increment == null)
{
ParameterExpression paramA = Expression.Parameter(typeof(T), "a");
UnaryExpression body = Expression.Increment(paramA);
increment = Expression.Lambda<Func<T, T>>(body, paramA).Compile();
}
li.moveUpTo(increment(li.selected_item));
}
catch (InvalidOperationException) { }
}
return li;
}
We basically do a check (to the best of our ability) to see if the increment operator is there. If it is, we create the
UnaryExpression for the object and compile it. Spiffy. The check looks like this:
///
/// This helper function determines if the passed in type has an increment operator.
///
/// The type to verify it supports an increment operation.
/// True if the increment is supported, false if not.
public static bool HasIncrementOperator(Type t)
{
if (t.IsPrimitive)
return true;
var op_MI = t.GetMethod("op_Increment");
return op_MI != null && op_MI.IsSpecialName;
}
The decrement of course works in similar fashion.
But is there a performance cost? Yes. Yes there is. But it is much more pronounced on the first call. Once the expression is compiled, albeit slower, the increment works at an acceptable performance compared to the method call (for my purposes, at least).
 |
| Comparison of seek time increment/decrement (++/--) vs method call (UP/DOWN). All times are in milliseconds. |
In the interest of brevity, I'll leave it there.
Last Thoughts and the Code
"But I use method x and it works fantastic. Why would you do
this?" you ask. Oh, great. You again. Well I'm sure method x is awesome and I'd love to hear about it. But as the expression goes, there are many ways to skin an algorithm. This just happens to be what I wanted to do. I'm not suggesting this is the only way to do it. I'm not even suggesting this is the
best way. It's just the route I went. If it strikes your fancy, by all means use it. If offends your sensibilities, my deepest apologies to said sensibilities.
On to the "using" portion. There is a license attribution at the top of the code (which the biggest part is you shouldn't remove that bit), but I'll paraphrase it here. You may use it however you like in any endeavor you pursue. All I ask is that you leave the notice on the top of the file and consider coming back here and commenting on how (or if) it helped you. Also this is a completely as-is offering. By using this code you indemnify me of anything that may happen (or not happen) . If your program won't compile, your company fails, your lucky number becomes unlucky... whatever... you absolve me of any responsibility. I also am not making any promise to support it at all. Things are busy, so don't be offended if I don't answer your questions regarding it.
Thanks for reading this long article. And if you just skipped to here: Yes, I am shaming you. For doing what I probably would have done. :o)
ListLimitedItem and ListLimitedItemException
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace ListLimitedItem
{
/// <summary>
/// This class is used with a shared finite list of items between its instances
/// to which a item can only be possessed by one instance.
///
/// AUTHOR: Scott Myers January, 2014
/// SITE: http://neuralcorrelates.blogspot.com/2014/01/any-list-will-do-sharing-set-between-csharp-instances.html
/// LICENSE: For all purposes as long as this attributation stays intact and you agree to use as is and disavow
/// the author, Scott Myers, of any
/// and all damages, real or preceived from its use.
/// </summary>
/// <exception cref="ListLimitedItemException"/>
public class ListLimitedItem<T> where T : IComparable
{
#region Fields
private SortedSet<T> available_items;
private T selected_item;
private readonly T allowed_neutral_item;
static private Func<T, T> increment;
static private Func<T, T> decrement;
#endregion
#region Constructor
/// <summary>
/// Neutral item constructor.
/// </summary>
/// <param name="available_items">The list to use as limited list</param>
/// <param name="allowed_neutral_item">A item that, if used, will not be removed from the list.</param>
public ListLimitedItem(ref SortedSet<T> available_items, T allowed_neutral_item)
{
//make sure the neutral number wasn't added to the list by mistake
if (allowed_neutral_item != null && available_items.Contains(allowed_neutral_item))
throw new Exception("The neutral item must not be contained in the available items set.");
this.allowed_neutral_item = allowed_neutral_item;
this.available_items = available_items;
if (allowed_neutral_item != null)
selected_item = allowed_neutral_item;
}
#endregion
#region Properties
/// <summary>
/// The number of items still up for grabs.
/// </summary>
public int RemainingCount
{
get
{
return available_items.Count;
}
}
/// <summary>
/// The current selected value. This might be the AllowedNeutralItem.
/// </summary>
public T Value
{
get
{
return selected_item;
}
}
/// <summary>
/// A value that, if the Value is set to, represents the instance
/// currently has no claims on an item in the set.
/// </summary>
public T AllowedNeutralItem
{
get
{
return allowed_neutral_item;
}
}
#endregion
#region Internal Methods
/// <summary>
/// Accessor to move down the list.
/// </summary>
/// <param name="requested_item">The item to move down to. If not available, the next lowest will be attempted. If none are available
/// the current position will be retained (which might be no position if the current is the AllowedNeturalItem).</param>
/// <returns></returns>
public T moveDownTo(T requested_item)
{
return getItem(requested_item, false);
}
/// <summary>
/// Accessor to move up the list.
/// </summary>
/// <param name="requested_item">The item to move up to. If not available, the next highest will be attempted. If none are available
/// the current position will be retained (which might be no position if the current is the AllowedNeturalItem).</param>
/// <returns></returns>
public T moveUpTo(T requested_item)
{
return getItem(requested_item, true);
}
/// <summary>
/// Main internal accessor to traverse the list.
/// </summary>
/// <param name="requested_item">The item to move to. If not available, the next closest will be attempted (according to direction). If none are available
/// the current position will be retained (which might be no position if the current is the AllowedNeturalItem).</param>
/// <param name="isForward">A boolean of whether the list direction is forward. True if so, false if not.</param>
/// <returns>Next Item (T)</returns>
/// <exception cref="ListLimitedItemException">If soemthing goes wrong in seeking the next item, the exception is thrown.</exception>
private T getItem(T requested_item, bool isForward)
{
//if we are changing to neutral item, return our item back into the list
//set to the value and return
if (allowed_neutral_item != null && allowed_neutral_item.Equals(requested_item))
{
lock (available_items)
addBackItem(requested_item);
selected_item = requested_item;
return selected_item;
}
if (available_items.Count > 0)
{
if (selected_item != null && !selected_item.Equals(allowed_neutral_item))
{
//This stops movement if the request is to move up yet the current number is greater (or vice versa for moving down the list)
if ((((selected_item != null) && (requested_item.Equals(selected_item))) ||
(isForward && ((requested_item.CompareTo(selected_item) <= 0) || requested_item.CompareTo(available_items.Last()) > 0)) ||
(!isForward && ((requested_item.CompareTo(selected_item) >= 0) || requested_item.CompareTo(available_items.First()) < 0))))
return selected_item;
}
//if the request overshoots or undershoots the list give the max/min
//available respectively
if (isForward && requested_item.CompareTo(available_items.Last()) >= 0)
requested_item = available_items.Last();
else if (!isForward && requested_item.CompareTo(available_items.Last()) <= 0)
requested_item = available_items.First();
}
else if ((allowed_neutral_item == null && selected_item != null) || (selected_item.CompareTo(allowed_neutral_item) >= 0))
return selected_item; //if we have a spot, but their no other spots available, stay put.
T next_item = allowed_neutral_item;
lock (available_items)
{
try
{
//If the set has the item, we're done. Otherwise, use LINQ to find the closest
//item.
if (available_items.Contains(requested_item))
next_item = requested_item;
else
next_item = (isForward) ? available_items.Where(n => n.CompareTo(requested_item) >= 0).First() : available_items.Where(n => n.CompareTo(requested_item) <= 0).Last();
}
catch (Exception err)
{
//This should never happen, but in case it does throw a ListLimiteItemException.
string base_message = "An exception occured seeking the next list position.";
if (err is NullReferenceException)
{
if (available_items == null)
base_message += " The available items internal list is null.";
if (requested_item == null)
base_message += " The requested item is null.";
}
throw new ListLimitedItemException(base_message, err);
}
available_items.Remove(next_item);
addBackItem(next_item);
}
selected_item = next_item;
return next_item;
}
/// <summary>
/// When the instance leaves a position, this method returns it to the list.
/// </summary>
/// <param name="next_item">The next item. If it is equal to the current value, nothing is returned to the set.</param>
private void addBackItem(T next_item)
{
if (selected_item != null && next_item != null && !selected_item.Equals(next_item))
{
if (!available_items.Contains(selected_item))
{
if (allowed_neutral_item == null || !selected_item.Equals(allowed_neutral_item))
available_items.Add(selected_item);
}
}
}
#endregion
#region Operator Overloading
/// <summary>
/// The overloaded increment operator. If not supported by the underlying type, the
/// item is unchanged.
/// SOURCE: The expression technique, for me at least, can be attributed to Marc Gravell from here: http://www.yoda.arachsys.com/csharp/genericoperators.html
/// </summary>
/// <param name="li">Current ListLimitedItem</param>
/// <returns>The incremented ListLimitedItem</returns>
public static ListLimitedItem<T> operator ++(ListLimitedItem<T> li)
{
if (li.selected_item != null && li.available_items.Count > 0 && li.selected_item.CompareTo(li.available_items.Last()) < 0 && HasIncrementOperator(typeof(T)))
{
try
{
if (increment == null)
{
ParameterExpression paramA = Expression.Parameter(typeof(T), "a");
UnaryExpression body = Expression.Increment(paramA);
increment = Expression.Lambda<Func<T, T>>(body, paramA).Compile();
}
li.moveUpTo(increment(li.selected_item));
}
catch (InvalidOperationException) { }
}
return li;
}
/// <summary>
/// The overloaded decrement operator. If not supported by the underlying type, the
/// item is unchanged.
/// SOURCE: The expression technique, for me at least, can be attributed to Marc Gravell from here: http://www.yoda.arachsys.com/csharp/genericoperators.html
/// </summary>
/// <param name="li">Current ListLimitedItem</param>
/// <returns>The decremented ListLimitedItem</returns>
public static ListLimitedItem<T> operator --(ListLimitedItem<T> li)
{
if (li.selected_item != null && li.available_items.Count > 0 && li.selected_item.CompareTo(li.available_items.First()) > 0 && HasDecrementOperator(typeof(T)))
{
try
{
if (decrement == null)
{
ParameterExpression paramA = Expression.Parameter(typeof(T), "a");
UnaryExpression body = Expression.Decrement(paramA);
decrement = Expression.Lambda<Func<T, T>>(body, paramA).Compile();
}
li.moveDownTo(decrement(li.selected_item));
}
catch (InvalidOperationException) { }
}
return li;
}
/// <summary>
/// This helper function determines if the passed in type has an increment operator.
/// </summary>
/// <param name="t">The type to verify it supports an increment operation.</param>
/// <returns>True if the increment is supported, false if not.</returns>
public static bool HasIncrementOperator(Type t)
{
if (t.IsPrimitive)
return true;
var op_MI = t.GetMethod("op_Increment");
return op_MI != null && op_MI.IsSpecialName;
}
/// <summary>
/// This helper function determines if the passed in type has an decrement operator.
/// </summary>
/// <param name="t">The type to verify it supports a decrement operation.</param>
/// <returns>True if the decrement is supported, false if not.</returns>
public static bool HasDecrementOperator(Type t)
{
if (t.IsPrimitive)
return true;
var op_MI = t.GetMethod("op_Decrement");
return op_MI != null && op_MI.IsSpecialName;
}
#endregion
}
/// <summary>
/// This is the general exception that is thrown if something goes very, very wrong.
/// </summary>
public class ListLimitedItemException : Exception
{
public ListLimitedItemException(string message)
: base(message)
{
}
public ListLimitedItemException(string message, Exception innerException)
: base(message, innerException)
{
}
}
}
