In the application I work on, we want to combine orders and put them on trucks: a typical truck scheduling problem. Characteristics of this problem,
for the purpose of the specialized
List class I want to present, are here:
- Limited number of items (orders, trucks, depots)
- Lots of small lists, where you want to check if they contain the same items
The speed of a few list operations is crucial. Therefore, the
List has super fast:
I searched wikis and articles to find a good description for this kind of collection. It might be called BitArray,
or a List with a BitArray index. The idea is probably not unique, but the implementation in .NET,
In our case, we have three fixed lists: orders, trucks, depots. For each order, we create lists of other orders they could be combined with,
trucks they might fit on, and depots that have the necessary products.
During all the shuffling that comes with scheduling, we constantly have to compare lists. E.g., if two orders do not share a truck in their truck lists,
they cannot be combined. If we do combine two orders, the trucks they can be scheduled on, is the intersection of the truck lists of the two orders.
Using the Code
The code consists of a simple interface that the items in the lists have to implement, and the
List class itself.
To use the
List, you have to make sure that the items you want to put in them
IIndexable interface. Also, each item has to have a unique value for Index.
A minimal example that shows the prerequisites and the main methods:
Public Class Order
Private _Index As Short
Public Property Index() As Short Implements IIndexable.Index
Set(ByVal value As Short)
Me._Index = value
Public Class OrderManager
Private Orders As New List(Of Order)
Public Sub InitOrders()
Dim NewOrder As Order
For Index As Integer = 0 To 10
NewOrder = New Order
NewOrder.Index = Index
Public Sub UseOrders()
Dim OrderList1 As New IndexedList(Of Order)
Dim OrderList2 As New IndexedList(Of Order)
If OrderList1.Contains(Me.Orders(0)) Then
I wrote everything in VB.NET, but all the code can be translated to C# with an online tool.
Points of Interest
I learned a few things myself: to turn on specific bits in an unsigned integer, you can use bitwise shift and bitwise OR. This is much faster than the "two to the power of x"
I had before. The tests in the class are modeled after an idea I learned on CP. To make it work, you have to add a
ProjectTypeGuids tag in vbproj, using a text editor.
- 29 February 2012: Initial version.