BitArray indexed List

• Download source code - 12.2 KB

Introduction

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:

• Contains
• Intersect
• Union
• Overlaps

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, AFAIK, is.

Background

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 implement the 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
    Implements IIndexable
    Private _Index As Short

    Public Property Index() As Short Implements IIndexable.Index
        Get
            Return Me._Index
        End Get
        Set(ByVal value As Short)
            Me._Index = value
        End Set
    End Property
End Class

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
            Me.Orders.Add(NewOrder)
        Next
    End Sub
    Public Sub UseOrders()
        Dim OrderList1 As New IndexedList(Of Order)
        Dim OrderList2 As New IndexedList(Of Order)
        OrderList1.Add(Me.Orders(0))
        OrderList1.Add(Me.Orders(1))
        If OrderList1.Contains(Me.Orders(0)) Then
            OrderList2.Add(Me.Orders(0))
            OrderList2.Add(Me.Orders(2))
        End If
        OrderList1.UnionWith(OrderList2) 'Order 2 will be added to OrderList1
        OrderList1.IntersectWith(OrderList2) 'OrderList1 will contain order 0 and 2 now
    End Sub
End Class

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.

History

• 29 February 2012: Initial version.