Click here to Skip to main content
Click here to Skip to main content

BitArray indexed List

, 4 Apr 2012
Rate this:
Please Sign up or sign in to vote.
List subclass for limited number of items and fast search.

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Pinx
Software Developer
Netherlands Netherlands
My first encounters with computers where Sinclair, TI99-4A, C64, Apple II. Have programmed ever since. Worked for a few logistic companies.
I have been a VB.NET programmer for quite some years. I work with a small firm, that specializes in supply chain planning for bulk products. We have our own application, Delivery+, that helps vehicle planners with their daily job.
I am married and I have two children. I am building an eco-friendly house and try to live green.

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 4 Apr 2012
Article Copyright 2012 by Pinx
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid