SharpShooter
LANGUAGES: C#
TECHNOLOGIES: Collections
Manage Object Collections
Explore the functionality of the CollectionBase and ArrayList classes.
By Dan Fergus
In programming, the term collection has the expectation of having a certain set of functionality. Before .NET, this functionality varied drastically from language to language. And even within a language, the implementation of a collection was not always the most straightforward programming paradigm. In .NET, the Framework Class Library provides a wide selection of collection classes through the System.Collections namespace. In effect, the Collections namespace provides two levels of classes - low-level classes that provide base functionality designed for you to inherit and customize, and higher-level classes designed to be used as is. The latter category contains six classes: ArrayList, BitArray, HashTable, Queue, SortedList, and Stack. The primitive classes are CollectionBase, DictionaryBase, and ReadOnlyCollectionBase.
The key-and-value pair collections inherit from IDictionary, and the object collections derive from IList. Both interfaces derive from the ICollection and IEnumerable interfaces. Of particular interest is the IList interface. Many framework classes inherit from IList, including ListView, DataView, DataGrid Columns, Arrays, Menus, and many more.
For this article, I will explore how to use the IList interface in the collection classes. In particular, I'll show you some of the basic implementations of CollectionBase and the more advanced usage of ArrayList, including using interfaces for advanced sorting. (I'll cover the key-and-value pair classes in a future column.)
The most important methods exposed by the CollectionBase class are Clear, Equals, GetEnumerator, RemoveAt, and ToString; the most important property this class exposes is Count. These are the bare essentials provided by the framework. If you need anything more, you'll need to provide it in a derived class.
The important methods of the IList interface are Add, Clear, Contains, IndexOf, Insert, Remove, and RemoveAt. This interface is the basis for collections and much more. When you look at the class methods you also should see how the interface is used in other classes in the framework, such as Menus, DataViews, and ListViews.
The CollectionBase Class
The CollectionBase class is little more than a simple shell over the IList interface. You can pass much of its functionality directly down to the methods of IList. The code in Figure 1 shows a simple class, BooksCB, that acts as a generic collection class, accepting only Book objects through the Add method.
public class BooksCB : CollectionBase
{
public void AddBook(Book b)
{ this.List.Add(b); }
public int BookCount()
{ return this.List.Count; }
public bool IsOnShelf(Book b)
{ return this.List.Contains(b); }
public void RemoveBook(Book b)
{ this.List.Remove(b); }
}
Figure 1. The BooksCB class inherits from CollectionBase to obtain collection functionality.
You can see in Figure 1 that the collection is maintained by the protected List property, which the IList interface provides. Although this class stores and supplies data to the user as a collection would, it comes up short in the functionality category.
If an item is added to the IList and there is no more room for it in the allocated space, the size of the internal data doubles. So if you have 1,000 elements stored already in a list whose capacity is 1,000, the next item added will cause the list to grow to a capacity of 2,000. Also, if you want to sort the list, there is no functionality built into either IList or CollectionBase classes to perform a sort (although I'll show you a trick later). So, if you are looking for a low-overhead, type-safe, and simple collection implementation, CollectionBase might be a valid option. But if you want more, you need to look at one of the higher-level classes provided by the framework.
Step Up to the ArrayList Class
The ArrayList class would be your best choice for a step up from CollectionBase. This class has all the basic functionality of CollectionBase, but it also implements new interfaces to allow sorting and gives you more flexibility in the memory management of the class. The ArrayList class adds a Capacity property. You can use Capacity to get or set the number of elements an ArrayList can contain. Setting Capacity to 0 causes the framework to allocate space for 16 elements by default. You can use this property to implement a custom memory resizer for your ArrayList. For example, instead of letting the framework double the size of the element capacity, you could do a check when you add a new element and increase the Capacity property in an increment more to your liking:
public void AddBook(Book book)
{
if( _bookList.Count == _bookList.Capacity )
_bookList.Capacity += 25;
_bookList.Add(book);
}
You must understand, however, that increasing the capacity in smaller increments at a more frequent occurrence rate might not be the best technique if you are planning to add many elements to the ArrayList. Perhaps the best technique would be to know the expected capacity before loading the list and set the Capacity property to that value once to avoid the dynamic allocation of new space. The counterpart of Capacity is the TrimToSize method. Calling TrimToSize causes Capacity to be set equal to Count, thereby removing any extra space allocated for element storage you have not used.
Sort the List
Another advanced feature of ArrayList is the Sort method. Although the method belongs to ArrayList, your class must implement the IComparable interface to make sorting work in the ArrayList (see Figure 2).
public class Book : IComparable {
public string Title;
public string Author;
public string ISBN;
public Book(string title, string author, string isbn) {
Title = title;
Author = author;
ISBN = isbn;
}
int IComparable.CompareTo(object obj)
{
Book b = (Book) obj;
return( this.Title.CompareTo(b.Title));
}
}
Figure 2. To sort an ArrayList, you must implement the IComparable interface. This interface provides a mechanism to sort the list by a single property. In this code, the list will be sorted by book title.
The IComparable interface has a single method, CompareTo, which returns -1 if the instance is less than obj, 0 if they are equal, and 1 if the instance is larger than obj. In Figure 2, the sort order is based on the book title, so a string's CompareTo method is used to do the actual comparison. Use caution about which object you use as the current instance and which you use as the comparand. Reversing the two will sort the list in the reverse order. The code in Figure 2 performs an ascending sort, but this code performs a sort in descending order:
int IComparable.CompareTo(object obj)
{
Book b = (Book) obj;
return( b.Title.CompareTo(this.Title));
}
If you want to define multiple sort orders, a bit more work is required on the Book class. You might be inclined to attempt this by adding the IComparer interface to the Book definition. This attempt would fail because only a single Comparer method can be defined on a class. To circumvent this limitation, define two new classes that each implement the IComparer interface. Each class, shown in Figure 3, does the comparison based on a different field in the Book class.
public class SortByISBN : IComparer
{
public int Compare(object o1, object o2)
{
string b1ISBN = ((Book)o1).ISBN;
string b2ISBN = ((Book)o2).ISBN;
return (((IComparable) b1ISBN).CompareTo(b2ISBN));
}
}
public class SortByAuthor : IComparer
{
public int Compare(object o1, object o2)
{
string b1Author = ((Book)o1).Author;
string b2Author = ((Book)o2).Author;
return (((IComparable) b1Author).CompareTo(b2Author));
}
}
Figure 3. The SortByISBN and SortByAuthor classes are defined to implement sorting by Author and ISBN.
The Compare method of the IComparer interface takes two objects. In the sort routines, you take each object, cast it to a Book instance, and get the element of the class you are interested in sorting. You then use the CompareTo method of the string object to do the comparison, which is passed back as an integer.
To call the sort classes from the Book class, you need to add these static properties, one for each IComparer class:
public static IComparer SortByISBN
{
get
{ return ((IComparer) new SortByISBN()); }
}
public static IComparer SortByAuthor
{
get
{ return ((IComparer) new SortByAuthor()); }
}
Then, to make the actual sort occur, you use an overloaded version of the ArrayList Sort method that takes an IComparer object as its parameter:
public void Sort(int sortByFlag)
{
if( sortByFlag == 0 )
bookList.Sort();
else if( sortByFlag == 1 )
bookList.Sort(Book.SortByAuthor);
else if( sortByFlag == 2 )
bookList.Sort(Book.SortByISBN);
}
Now you can sort the ArrayList collection on three different elements of the Book class: Title, Author, and ISBN.
Explore ArrayList Wrappers
The Collections namespace provides a series of static methods that let you copy or convert an ArrayList, changing its characteristics in the process. The FixedSize method returns a new ArrayList with editable elements, but to which you cannot add elements. The ReadOnly method returns a new ArrayList that is a read-only copy of the original:
public ArrayList CopyReadOnly()
{
return ArrayList.ReadOnly(_bookList);
}
When a new ArrayList is made using the FixedSize method, the resulting ArrayList can still be sorted or have its Reverse method called. If you make a copy using the ReadOnly method, however, attempting to sort the list will result in an exception.
Another static wrapper method, Repeat, lets you add multiple copies of the same element to a list:
public void AddMultipleCopies( Book b, int count)
{
_bookList = ArrayList.Repeat(b, count);
}
What if the ArrayList will be accessed by several threads or applications simultaneously? The Synchronize method returns a copy of the ArrayList that is guaranteed to be thread-safe for iteration of the list. If another thread changes some data in the list, however, an exception will be raised during the next iteration. You can use the methods discussed already to protect the data being changed during list iteration:
public ArrayList CopyReadOnly()
{
ArrayList t= ArrayList.ReadOnly(_bookList);
return ArrayList.Synchronized(t);
}
In your application, you can provide a synchronized, read-only version of the ArrayList for iteration while the original is still available for editing, thus eliminating the chances of an exception being raised.
I mentioned earlier that IList does not support sorting of its internal list. One workaround for this is to call the Adapter method of ArrayList. Like the other wrapper methods of ArrayList, this method creates a new ArrayList object. But unlike the previous static methods I discussed, the input parameter of this method is an IList, not an ArrayList. Also different is the fact that the IList data is not copied. The new ArrayList is a wrapper that works directly on the IList data. Any changes made to the IList while the wrapper is valid will be seen by the user of the ArrayList wrapper. Calling the Sort, Reverse, or BinarySearch methods on the ArrayList operate and change the order in the IList data.
Covering the entire Collections namespace in a single column is impossible. As I mentioned at the beginning of the article, there are two general types of collection classes - object collections, the subject of this column, and name-value pair collections, which I did not cover. If you are an old Visual Basic 6.0 programmer, ArrayList is the closest to what you had in the VB 6.0 Collection object. Once you get used to .NET's interface programming model, you really can make the collection objects perform to the level that you need.
The files referenced in this article are available for download.
Dan Fergus is the chief software architect at Forest Software Group, providing custom software and Web Services, and is a well-known lecturer who travels the world speaking at conferences on .NET technologies. Dan also is a trainer and consultant for Wintellect (http://www.wintellect.com) where he teaches Windows CE, debugging, and .NET Framework classes. E-mail him at mailto:[email protected].
Tell us what you think! Please send any comments about this article to [email protected]. Please include the article title and author.
