The System.Collections Core Interfaces

The core collection interfaces defined in the System.Collections are:

IEnumerable .
IEnumerator and IDictionaryEnumerator .
ICollection .
IList .
IDictionary .

An interface is a specification that defines the members that a type must implement but does not define how the actual functionality of these members will be implemented. Chapter 3 contains more information on interfaces.

The IEnumerable and IEnumerator Interfaces

A type that implements the IEnumerable interface indicates to consumers that this type supports the notion of forward-only access to its items, using an enumerator object. An enumerator object provides a forward-only read-only cursor for a set of items.

The IEnumerable interface has one method, GetEnumerator :

  public interface IEnumerable   {   IEnumerator GetEnumerator();   }

This method returns a new instance of an enumerator object each time it is called. The returned object implements the IEnumerator interface, which has methods that can be used to sequentially access the set of System.Object types exposed by an enumerable type. The enumerator object supports retrieving the item at the current cursor position, or resetting the cursor back to the beginning of the item set.

The built-in Array type supports the IEnumerable interface. The following code shows how to declare a simple string array (although any type of array could be used), call the GetEnumerator method to create an enumerator object, and use the methods of returned IEnumerator interface to sequentially access each item in the array.

Using VB.NET, you would write:

  Dim authors As String()   authors = New String() {"Richard","Alex","Dave","Rob","Brian","Karli"}   Dim e As IEnumerator   e = authors.GetEnumerator()   Do While e.MoveNext() = True   Response.Write("<p />" & e.Current)   Loop

Using C#, you would write:

  string[] authors = new string[6]   {"Richard","Alex","Dave","Rob","Brian","Karli"};   IEnumerator e;   e = authors.GetEnumerator();   while( e.MoveNext() == true )   {   Response.Write("<p />" + e.Current);   }

Note	An example page named simple-authorlist.aspx is provided in the samples that are available for download from http://www.daveandal.net/books/8900/ in both VB.NET and C#. It demonstrates the code shown here.

In this code, a string array called authors was declared that contains the names of six authors. To get an enumerator object for the array, the authors.GetEnumerator method is called. All arrays implement the IEnumerable interface, so calling GetEnumerator is possible. Once the enumerator object is created, the MoveNext method is called in a while loop. This method moves the cursor forward by one logical record. The cursor is always positioned before the first record (think of this as position -1 ) when an enumerator object is created. This means you must always call MoveNext before retrieving the first item using the Current property. When the enumerator object is positioned past the last record in a collection, it returns false . You can therefore safely loop through all items in the collection by calling MoveNext while it returns true , exiting when it returns false .

The .NET Framework guidelines state that once an enumerator object is created, it takes a snapshot of the items contained within an enumerable object at that point in time. If the original object is changed, the enumerator becomes invalid, and the enumerator object should throw an InvalidOperationException the next time one of its methods is called. All .NET Framework classes follow these guidelines, as should the enumerable types that you write. For reasons of performance, the enumerators implemented in the .NET Framework class library don't actually copy all the items when an enumerable object is created. Instead, they just maintain a reference to the enumerable object, and provide a logical snapshot. It's much cheaper to maintain a reference and an index to the original enumerable object “ copying each and every item would be an expensive process for a large collection.

A simple versioning scheme is used to implement the actual semantics of a logical snapshot. Each time an enumerable object is changed (for example, an author is added or removed from the array), it increments a version number (think of this as a change counter). When an enumerator object is created, it copies the current version number of the enumerable object. Then, each time an enumerator object method is called, the enumerator compares its stored version number to the enumerable object's current version number. If these version numbers are different, the enumerator throws an InvalidOperationException .

The Current property of the IEnumerator interface is defined as the System.Object type. In the earlier code, you didn't have to cast the returned object from Current before using it, since Response.Write will call the ToString method for you. However, to store the underlying string type in the example, you would typically cast it.

For example, using VB.NET, you would write:

  Dim author As String   author = CType(e.Current, string)

Using C#, you would write:

  string author   author = (string) e.Current;

All of the collection interfaces in the System.Collections namespace use the System.Object type, which gives them great flexibility because they can be used with any type. However, this generic approach does mean that the CLR must perform type-conversion checking for most calls, which imposes a small performance overhead.

The for...each Statement

VB.NET and C# both have a statement that calls the enumerator directly. C# has the foreach statement and VB.NET has the For Each..Next statement (we'll refer to these as for..each statements). Both these languages implement their for..each functionality using the IEnumerable and IEnumerator interfaces. This means that you could change the earlier author example to use a for..each rather than a while statement. Using VB.NET, you would write:

  Dim author As string   For Each author In authors   Response.Write("<p />" & author)   Next

Using C#, you would write:

  foreach( string author in authors )   {   Response.Write("<p />" + author );   }

Using the for..each statement requires less code than using the IEnumerable and IEnumerator interfaces directly, but there will be times when it is not advisable (or even possible) to use the for..each statement.

To create some generic functionality that doesn't deal with concrete types, it would be better to not use the for..each statement, and if you had a loop that must be performed across several method invocations, it would not even be possible to use the for..each statement.

Provided that a type has a GetEnumerator method that returns a type derived from IEnumerable , it does not have to implement the IEnumerable interface for the for..each statement to work with it in C# or VB.NET. However, unless you have a very good reason for not doing so, your enumerable types should implement IEnumerable “ that way they will be in accordance with the guidelines that the rest of the framework follows .

All other enumerable types in the .NET Framework class library derive from the IEnumerable interface. This means that although other enumerable types provide additional members for accessing the items they contain, all of them also support the forward-only cursor approach using enumerator objects. The same is true for the IEnumerator interface. Thus, all other enumerator interfaces derive from IEnumerator . Figure 15-1 shows the interface inheritance for the core interfaces:

Figure 15-1:

This UML class diagram can be read as follows:

The IList and IDictionary interfaces derive from the ICollection interface, which in turn derives from IEnumerable .
The IEnumerable interface is associated with IEnumerator .

The IDictionaryEnumerator interface derives from IEnumerator .

Note	Types that implement the IEnumerable interface can be enumerated in VB 6 and other COM-aware languages using COM interop, since the GetEnumerator method will be exposed with a DISPID of -4 . Refer to MSDN for more information.

The ICollection and IList Interfaces

Enumerating through a collection sequentially is a common task, and it's also useful to be able to directly access items using a key or an index. For example, to check if a specific author exists in your array of authors from earlier, you could use the static Array.IndexOf method.

Using VB.NET, you would write:

  Dim index As Integer   index = Array.IndexOf(authors, "Richard")   If index <> -1 Then   Response.Write("<p />" & authors(index) & " is in the author list")   End If

Using C# you would write:

  int index;   index = Array.IndexOf(authors, "Richard");   if (index != -1)   {   Response.Write("<p />" + authors[index] + " is in the author list");   }

Note	The check-authorlist.aspx example page demonstrates the code shown here.

Here the Array.IndexOf method is used to retrieve and store the index of a specific author in index . If the value of index is not -1 (which would mean that the author was not found), use the index to display the value held at that offset within the array. Under the hood, this method searches the array item by item, performing a comparison against each one. When a match is found, the index is returned.

The IList interface defines methods and properties that allow you to work with arrays of System.Object items, such as the string array of authors. The IList interface defines methods and properties that allow you to:

Add an item to the end of the list (using the Add method).
Insert an item at a specified offset in the list (using the Insert method).
Determine if an item is contained within a list (using the Contains methods).
Determine the index of an item within a list (using the IndexOf method).
Retrieve or add an item by index (using the Item property, although in C# you have to use an indexer).
Remove an item by reference, or by its index (using the Remove or RemoveAt methods).
Remove all items (using the Clear method).
Determine if a list is read-only (using the IsReadOnly property).
Determine if a list is of a fixed size (using the IsFixedSize property).

The IList interface inherits the members of both ICollection and IEnumerable , as IList derives from ICollection , which in turn derives from IEnumerable .

The Array and the IList Interface

The built-in Array type implements the IList interface, but it only implements the IndexOf , Clear , and Contains methods and the Item property of the interface. If you try to call any of the other IList members, a NotSupportedException will be thrown. The other IList members are defined as explicit interface member implementations , and you have to access these using an IList interface reference.

As you saw in Chapter 3, the author of a type that implements an interface can control whether the members of an interface can be used implicitly (as if they were just part of the type), or if an interface reference has to be used to access them. Typically, the first approach is used, but for types in which specific members of the interface will not be commonly used (or are only required for internal use) the second approach is appropriate, as it keeps the publicly seen members fewer in number and more intuitive to use.

To see IList in action rewrite the last example (in which you determined if a specific author existed in an array) to use the IList.Contains method to determine if the item is present in the array, the IList.IndexOf method to determine the index of the item, and the IList.Item property to retrieve the value.

Using VB.NET, you would write:

  Dim list As IList   list = CType(authors, IList)   If list.Contains("Richard") Then   index = list.IndexOf("Richard")   Response.Write("<p />" & list(index) & " is in the author list")   End If

Using C#, you would write:

  IList list = (IList) authors;   if (list.Contains("Richard") == true)   {   index = list.IndexOf("Richard");   Response.Write("<p />" + list[index] + " is in the author list");   }

Note	The check-authorlist.aspx example page demonstrates the code shown here.

As the Item property is actually an indexer, in C# you can just use the array-style notation to access items in the list. Using the IList interface is pretty simple and the code is certainly no more complex than before. Take a look at the System.Collections.ArrayList type to see more of the IList methods in use.

The ArrayList Class

An ArrayList is capable of holding zero to n System.Object objects in a dynamically sized array. The total number of objects that can be held in the array is available from the Capacity property. The used space (the number of items in the array) is available via the Count property. As you add or remove items from the list, the ArrayList is automatically resized as required. The key difference between the built-in Array type and ArrayList is this automatic size management. Internally, the ArrayList still uses the Array type to implement most of its functionality.

The following code shows how to create an ArrayList and populate it with a few items using the Add method. This time movie names are used, rather than authors. Using C#, you would write:

  ArrayList movieList;   movieList = new ArrayList();   movieList.Add("Pulp Fiction");   movieList.Add("Aliens");   movieList.Add("The Good, the Bad and the Ugly");

Since ArrayList supports any type derived from System.Object , you could actually add many different item types to it. For example, using VB.NET, you would write:

  Dim movieList As ArrayList = New ArrayList()   variedItems.Add("Pulp Fiction")    ' add a string   variedItems.Add(1234)              ' add an integer   variedItems.Add(new ArrayList())   ' add another array list

The ArrayList class implements the IList interface, so all the other IList members covered so far are implemented and available to use. The IList interface members are implemented implicitly as public members by the ArrayList type, so there is no need to use an IList reference to call them. Most of the types in the .NET Framework do this to make using them simpler. Of course, there's nothing stopping you from using an interface if you want to. Doing so could have advantages if, for example, you are trying to write generic code that works with any implementation of IList .

In the following VB.NET code, the IList interface of the ArrayList is used:

  Dim movieList As IList   movieList = New ArrayList()   movieList.Add("Pulp Fiction")   movieList.Add("Aliens")   movieList.Add("The Good, the Bad and the Ugly")

Using C#, you would write:

  IList movieList;   movieList = new ArrayList();   movieList.Add("Pulp Fiction");   movieList.Add("Aliens");   movieList.Add("The Good, the Bad and the Ugly");

Here a movieList variable of type IList is declared, and then assigned a newly created ArrayList object. You will only be able to use the members defined in the IList interface. To use the other ArrayList members, you must cast movieList to an ArrayList (or to some other supported interface).

When you assign a newly instantiated type to a variable in this way, you don't need to specify any casting as the compiler will interrogate the meta data of the type at compile time, and ensure that the interface is supported. If the interface isn't supported, a compile error will occur. However, if you do specify an explicit cast on an assignment such as new , this will override the checks performed by the compiler. If the cast then turns out to be invalid at runtime, the CLR will throw an InvalidCastException .

Let's write a simple web page that allows a user to enter a list of their favorite movies to demonstrate how to use the various members of ArrayList . The page will have options to add and delete movies to a list, as well as to sort the list. Only the important elements of the code for this application are reviewed here. The result is shown in Figure 15-2 “ it automatically adds three movies. Notice that there is a [view source] link at the bottom of the page you can use to see the complete source code.

Figure 15-2:

The code responsible for creating the visible output in the page (excluding the server-side code for events) is shown next in VB.NET. It is a separate routine named ShowList , which can be called when required from anywhere in the page code. The HTML section of the page contains a <div runat ="server"> element with the outList ID, into which the list of movies is inserted:

  Sub ShowList()   If movieList.Count > 0 Then   For Each Movie As String In movieList   outList.InnerHtml &= Movie & "<br />"   Next   Else   outList.InnerHtml = "There are no movies in the list."   End If   End Sub

If there are no movies in the list, the code displays the message There are no movies in the list. If there are movies in the list (the Count property of movieList is greater than zero), the code renders a list of the titles of the movies. The For Each statement is used to enumerate the ArrayList that contains the movies. You can do this as ArrayList implements IEnumerable .

The movieList variable is created in the Page _ Load event handler. You'll see two ways of creating and maintaining state during postbacks, as well as the advantages and disadvantages of each. The first approach creates the list the first time the page is rendered, and places the instantiated object into the ViewState of the page using a movies key. On subsequent postbacks, the list is retrieved using this key from the ViewState .

Whether a page is being rendered for the first time or not, the instantiated ArrayList is held in a page- level member variable called movieList . We've used a variable in this way to make the subsequent page code more readable, since no casting is needed after it has been retrieved. Using VB.NET, you would write:

  Dim movieList As ArrayList     Sub Page_Load(Sender As Object, Args As EventArgs)   If Page.IsPostBack Then   movieList = CType(ViewState("movies"), ArrayList)   Else   movieList = New ArrayList()   movieList.Add("Pulp Fiction")   movieList.Add("Aliens")   movieList.Add("The Good, the Bad and the Ugly")   ViewState("movies") = movieList   ShowList()   End If   End Sub

Important

Collection classes are reference types, not value types. Therefore, when a reference to a collection type is assigned to multiple variables, all those variables will reference the same object on the managed heap.

There are no COM-type threading issues associated with storing objects in the ASP intrinsic objects such as ViewState or Session . It's perfectly safe, and in general you don't have to worry about threading models at all. However, storing an ArrayList in the Session object like this means that, by default, the ArrayList objects reside in memory on a specific web server. This means you cannot load-balance requests to such a page across multiple web servers. There are two solutions to this problem. You could tell ASP.NET to use an external state store (this was discussed in Chapter 13) or you can store the list in the ViewState as in this example, instead of the intrinsic Session object.

The following C# code shows how you can implement the Page _ Load event handler using the Session object:

 protected void Page_Load (object sender, EventArgs e) {    if (IsPostBack == true)    {  movieList = (ArrayList) Session["movies"];  }    else    {       movieList = new ArrayList();  Session["movies"] = movieList;  } }

Now, the ASP.NET page framework will persist the state held in the ArrayList in the user's Session , rather that as part of the HTML page returned to the client. When the next postback occurs, ASP.NET will automatically recreate the ArrayList , restore its state, and make it available to your page.

The ViewState approach allows you to load-balance your application, but it does mean that pages sent back to the client will be slightly larger, and that the web server will have to perform a few more CPU cycles in order to create and destroy the objects held in ViewState .

Note	When you store types in ViewState , you should enable tracing to keep an eye on the total ViewState size. You can find more details on this in Chapter 4.

The choice of whether to use Session or ViewState to hold state should be made on a per-application basis as both have advantages:

The problems associated with Session state in ASP 3 are gone, thanks to new external state stores such as SQL Server. A key benefit of using the Session object to hold the state is that the contents can survive across multiple pages; they are destroyed only when an ASP.NET session ends or the Session variable is deleted. For applications that require features like shopping carts, Session state combined with an external state store provides a fine solution.
Unlike Session state, ViewState cannot be used beyond the scope of a single page. This means that it can't be used to pass data between pages, so any important data must be persisted elsewhere before the user navigates away from a page. However, the advantage of using ViewState is that fewer server resources “ such as memory “ are consumed, which increases the scalability of an application.

You've seen how the page is rendered, and how you can store the list of movies in either Session or ViewState . Next, let's look at the event handlers that manipulate the list in response to the user's actions.

The MovieList Event Handlers

Users can input a movie name and then select an action to perform using the following HTML form:

  <form runat=server>     <h3>Movies in List</h3>   <div id="outList" runat="server" EnableViewState="False" /><p />   <b>Movie Name:</b> <asp:TextBox id="MovieName" runat="server" /><p />   <asp:Button OnClick="OnAddMovie" Text="Add Movie" runat="server" />   <asp:Button OnClick="OnDeleteMovie" Text="Delete Movie" runat="server" />   <asp:Button OnClick="OnSortList" Text="Sort List" runat="server" />   <asp:Button OnClick="OnCustomSortList"   Text="Sort List (custom)" runat="server"/>   </form>

Six server controls are used in this form, one for the <div> into which the list of movies is inserted, one for the movie name textbox, ( id="MovieName" ), and one for each of the four buttons . Each button is associated with a server-side event handler via the OnClick attribute.

When the user hits the Add button, the following event handler is invoked (shown here in VB.NET). This event handler retrieves the value of the Text property of the MovieName server control and adds it to movieList (our ArrayList ). Then it displays the list with the new movie added by calling the ShowList routine you saw earlier:

  Sub OnAddMovie(Sender As Object, Args As EventArgs)   movieList.Add(MovieName.Text)   ShowList()   End Sub

When the user hits the Delete button, the following event handler is invoked (shown here in VB.NET). This event handler checks if the movie exists in the list by using the IndexOf method. If the movie is found in the list, the Remove method of the ArrayList is called to delete the movie:

  Sub OnDeleteMovie(Sender As Object, Args As EventArgs)   If movieList.IndexOf(MovieName.Text) = -1 Then   status.InnerHtml = "Movie not found in list"   Else   movieList.Remove(MovieName.Text)   End If   ShowList()   End Sub

If the movie is not found, an error message is displayed by setting the InnerHtml property of a <div> element with the ID of status . This element is represented by a HtmlGenericControl control underneath the main form:

  <div style="color:red" id="status" EnableViewState="False" runat="server" />

The Remove method doesn't throw any exception if it's called with an argument that's not in the list, and so you wouldn't have to validate the arguments (as done here), unless you wanted to give some type of feedback to the user. The Remove method of ArrayList actually calls the IndexOf method to determine the index of the passed item, and then calls the RemoveAt method, which actually removes the item at a specific position from the array. This means that this event handler could be more efficiently written as:

 Sub OnDeleteMovie(Sender As Object, Args As EventArgs)  Dim index As Integer = movieList.IndexOf(MovieName.Text)   If index = -1 Then  status.InnerHtml = "Movie not found in list"    Else  movieList.RemoveAt(index)  End If    ShowList() End Sub

Now check for an item's index, store it in the index variable, and then use it to delete the item. Small optimizations like this may seem minor, but are well worth doing as the ArrayList type isn't particularly efficient. It will sequentially search an array, item by item, until a match is found, which means that for a list with a several hundred items, the scan time can be significant.

When the user hits the Sort List button the following event handler is invoked (shown here in VB.NET):

  Sub OnSortList(Sender As Object, Args As EventArgs)   movieList.Sort()   ShowList()   End Sub

This event handler calls the Sort method of the ArrayList . This method sorts the items in the list by using a QuickSort algorithm (this cannot be changed), which results in the list being efficiently sorted alphabetically “ the default for string types. Figure 15-3 shows the result:

Figure 15-3:

The QuickSort algorithm works by dividing a list of items into two partitions based upon a pivot item. Items less than the pivot item end up in the left partition, items greater than the pivot item end up in the right partition, and the pivot item ends up in the middle. By recursively applying this algorithm to each of the left and right partitions that are created until each partition only contains a single item, a list can be sorted with a minimum number of comparisons and exchanges.

Performance and Memory Optimizations

When items are added to an ArrayList , the size of its internal array is automatically increased as required. The default capacity of an ArrayList is sixteen. If a seventeenth item is added to the list, a new internal array is created which is twice the size of the current one, and the original items are copied to the array. It's worth optimizing the initial capacity of a list if you know how many items will be in it, as otherwise the repeated memory allocation and copying of items as the list grows in size could prove expensive.

Most of the framework collection classes can have their initial capacity and size set, and ArrayList is no exception. The capacity for an ArrayList can be set using the Capacity property, which accepts an integer value. For example (in C#):

  ArrayList list = new ArrayList();   list.Capacity = 128;

Alternatively, you can set the capacity when the ArrayList is created by using one of the overloaded constructors. For example (in C#):

  ArrayList list = new ArrayList(128);

Once a list is populated with items, you can release any unused slots by calling the TrimToSize method. However, calling this method will require a new array to be allocated, and all of the existing items will be copied from the old array to the new one. Accordingly, this method should only be called if a list is likely to remain static in size for a reasonable length of time, or if there are a large number of unused slots that should be freed.

Sorting the List “ IComparer and IComparable

Collection classes such as ArrayList and Array use the System.Collections.IComparer interface to determine equality when they are sorting collections. This interface is used to establish if a type instance is less than, equal to, or greater than another type instance and has a single method called Compare :

  public int Compare(object x, object y)

Classes that implement this interface should check for equality between the objects passed in, and return one of the following:

A negative value if object x is less than object y .
A positive value is object x is greater than object y .
Zero if the objects are equal.

The default implementation of IComparer , which is used by the ArrayList and other types, is the System.Collections.Comparer class. This class implements its comparison of two objects by using the System.IComparable interface of the first object ( x ) passed in to the IComparer.Compare method.

The IComparable interface has a single method called CompareTo , which has the same return values as the IComparer.Compare method:

  public int CompareTo(object x);

Most value types such as string and integer implement the IComparable interface, which means that you can compare most types as follows (using VB.NET):

  Dim s1 As String = "This One"   Dim s2 As String = "That One"   Dim c1 As IComparable   c1 = CType(s1, IComparable)   If c1.CompareTo(s2) <> 0 Then   outResult.InnerHtml = "'" & s1 & "' is different to '" & s2 & "'"   End If   If c1.CompareTo(s2) < 0 Then   outResult.InnerHtml = "'" & s1 & "' is less than '" & s2 & "'"   End If   If c1.CompareTo(s2) > 0 Then   outResult.InnerHtml = "'" & s1 & "' is greater than '" & s2 & "'"   End If

Note	The simple-compare.aspx example page demonstrates the code shown here.

Unless there's a good reason, custom types should implement the IComparable interface, so that the type can be sorted easily. However, there is a limitation as to what can be sorted. The ArrayList class uses the System.Collections.Comparer implementation of IComparer to sort its list, which in turn uses the IComparable interface of the types within the list. This means that you can only sort an array that contains items that can do equality checks on each other. Most types can only do equality checks against their own type, so by default you can't sort an ArrayList that contains different types. For example, the following VB.NET code that tries to compare a string and integer will throw an ArgumentException :

  Dim s1 As String = "richard"   Dim i1 As Integer = 1234   Dim c1 As IComparable   c1 = CType(s1, IComparable)   If c1.CompareTo(i1) <> 0   outResult.InnerHtml = "You'll never see this line because of the exception."   End If

Note	The error-compare.aspx example page demonstrates the code shown here.

When the CompareTo method is called, the string type checks the type of the argument passed. If the argument is not a string type, it throws an exception. This exception must be caught at runtime. The code will compile without error, as type checking is not possible at design time. While this restriction will not be a problem in most applications, it is possible to sort arrays that contain different types. You can gain complete control over how an array is sorted by using an overload of the Sort method that accepts an IComparer interface that will be used when equality checks are performed.

This technique is used in the movie list application. Clicking the Sort List (custom) button results in the list of movies being displayed in reverse alphabetical order, as shown in Figure 15-4:

Figure 15-4:

The event handler for the Sort List (custom) button invokes the custom sort:

  Sub OnCustomSortList(Sender As Object, Args As EventArgs)   Dim custom As IComparer = New MyComparer()   movieList.Sort(custom)   ShowList()   End Sub

The MyComparer comparer class follows. This class uses the IComparable interface of object x to compare it with object y . The result from the call to CompareTo is then checked, and the sign of the number is inverted if the objects are not equal. By making negative values positive and positive values negative, the list is effectively reverse-sorted. An implementation of IComparer should always treat non- null values as being greater than a null value:

  Class MyComparer Implements IComparer   Overridable Function Compare(x As Object, y As Object) As Integer _   Implements IComparer.Compare   Dim ic As IComparable   Dim compareResult As Integer   ic = CType(x, IComparable)   compareResult = ic.CompareTo(y)   If compareResult <> 0   compareResult = compareResult * -1   End If   Return compareResult   End Function   End Class

The ArrayList type actually has a Reverse method, which would normally be used to reverse- sort a list.

Efficient Searching “ Using Binary Searching

Searching an ArrayList using methods like IndexOf means that every item in the list is compared with the value being searched for, until a match is found. This 'brute force' approach to searching means that as the number of items in a list increases, so does the number of comparisons that have to be performed to locate an item, particularly when the item being searched for is located towards the end of the list. The result is (pretty much) a linear increase in search times as a list grows. This isn't a problem for small lists, but large lists need a more efficient solution.

You can use a binary search to efficiently search lists. If a list is sorted (which is a prerequisite of performing a binary search), a binary search can locate an item using significantly fewer comparisons, which results in search times that are significantly less than for a regular linear search. The following code shows how you can perform a binary search on an ArrayList :

  ArrayList someList;   int ItemIndex;   someList = new ArrayList();   // code here to add lots of items to the list...   someList.Sort();   ItemIndex = someList.BinarySearch("Some item");

Binary searches do not work on an unsorted list. You won't receive an error if you call the BinarySearch method on an unsorted list, but you will get unpredictable results “ for example, items that are in the list may not be found. There are two main reasons why the BinarySearch method doesn't just sort the list anyway:

Performance :The list may already be sorted, and re-sorting would thus be wasteful .
Custom sorts :Sorting the list might require a custom IComparer implementation, which means that the BinarySearch method cannot make any assumptions on how to sort the list.

If you do sort a list using a custom IComparer interface, use the overloaded version of the BinarySearch method that accepts the comparer interface. If you don't use this overload, the search results will be unpredictable.

Indexers and Bounds Checking

When working with an ArrayList , you can treat it just like an array by using an integer index to retrieve a specific item. For example, using VB.NET, you would write:

  BestMovieOfAllTime = CType(movieList[2], string)

Using C#, you would write:

  BestMovieOfAllTime = (string) movieList[2];

You can treat the ArrayList like an array because it implements an indexer . Indexers allow a type to be programmatically treated like an array, but under the hood methods are called to set or retrieve values. Indexers can be declared to accept different types, which means that an indexer value could be an integer, a string, or another supported type. For example, the ASP.NET Session object supports both integer and string indexers. Using VB.NET, you would write:

  Dim SomeValue As String   SomeValue = CType(Session(0), String)   SomeValue = CType(Session("NamedValue"), String)

Using C#, you would write:

  string SomeValue;   SomeValue = (string) Session[0];   SomeValue = (string) Session["NamedValue"];

This code shows how you can retrieve the first session variable using either an integer index value (in this case zero), or a named session variable.

Types that support indexers typically throw exceptions when confronted with invalid index values. If you don't know in advance whether an index is valid, always write code that deals with exceptions. For example, using C#, you would write:

  try   {   BestMovieOfAllTime = (string) movieList[6];   }   catch( ArgumentOutOfRangeException rangeException )   {   BestMovieOfAllTime = "index too big";   }

Since types such as the ArrayList will throw an ArgumentOutOfRangeException if an index is invalid, you should declare an exception handler to catch an error and give the user some basic feedback. You should also handle the general exception case, since types could throw other unexpected exceptions:

  try   {   BestMovieOfAllTime = (string) movieList[6];   }   catch( ArgumentOutOfRangeException rangeException )   {   BestMovieOfAllTime = "index too big";   }   catch( Exception e )   {   // do something useful here   }

The ICollection Interface

The ArrayList class supports three collection interfaces: IList , IEnumerable , and ICollection . We've covered the first two. Turn your attention to ICollection . The ICollection interface defines methods and properties that allow you to:

Determine how many items are in a collection (using the Count property).
Copy the contents of a collection into a specified array at a given offset (using the CopyTo method).
Determine if the collection is synchronized and therefore thread-safe.
Determine the synchronization root object for the collection (using the SyncRoot property). The synchronization root object is the object that is locked and unlocked as collection operations are performed on a synchronized collection.

The ICollection interface derives from the IEnumerable interface so it inherits the GetEnumerator method.

The ICollection.Count Property

The following code shows how to use the ICollection.Count property to display the number of items in the movieList ArrayList :

  <p>There are <%=movieList.Count%> in the list.</p>

For those types in the class library, the implementation of the Count property returns a cached field. It doesn't cause the size of a collection to be recalculated, so it isn't expensive to call, which means that you don't need to worry about caching the Count property in an effort to get efficiency.

The ICollection.CopyTo Method

The ICollection.CopyTo method allows the contents of a collection to be inserted into an array at a specified offset. If the array to which the contents are copied does not have sufficient capacity for the insertion, an ArgumentException will be thrown. The following VB.NET code shows how to copy the contents of the ArrayList into a string array (at the beginning) using the CopyTo method:

  Dim Animals As ArrayList = New ArrayList()   Dim ArrayOfAnimals() As String   Animals.Add("Cat")   Animals.Add("Dog")   Dim a As Array   ArrayOfAnimals = Array.CreateInstance(GetType(String), 2)   Animals.CopyTo(ArrayOfAnimals, 0)   Dim Animal As String   For Each Animal In ArrayOfAnimals   Response.Write("<p />" & Animal)   Next

Using C#, you would write:

  ArrayList Animals = new ArrayList();   string[] ArrayOfAnimals;   Animals.Add("Cat");   Animals.Add("Dog");   ArrayOfAnimals = (string[]) Array.CreateInstance(typeof(string), 2);   Animals.CopyTo(ArrayOfAnimals, 0);   foreach( string Animal in ArrayOfAnimals )   {   Response.Write("<p />" + Animal);   }

Note	The array-copyto.aspx example page demonstrates the code shown here.

Here, you create an ArrayList that contains a couple of animals, dynamically create a string array, and then use the CopyTo method of the ArrayList to populate the created array with the contents of the ArrayList .

The ArrayList supports two additional overloads of CopyTo . The first overload doesn't require an index to be specified when the contents of the ArrayList are copied and inserted at the start of an array. The second overload allows a specified number of items, starting from a specified position, to be copied from the ArrayList to a given index within another array.

As the ArrayList class does not expose its internal array, you have to use either its AddRange or InsertRange method when copying data from an array into an ArrayList . The AddRange method accepts an ICollection interface and adds all items within the collection to the end of the array. In the following example, the contents of two arrays are copied into an ArrayList . The code would result in the names being listed in this order: Tom , Mark , Paul , Jon . Using C#, you would write:

  string[] Friends = {"Tom","Mark"};   string[] CoWorkers = {"Paul","Jon"};   ArrayList MergedList = new ArrayList();   MergedList.AddRange(Friends);   MergedList.AddRange(CoWorkers);   foreach (string Name in MergedList)   {   Response.Write("<p />" + Name );   }

The InsertRange method accepts an ICollection interface as its second parameter, but expects the first parameter to be the index to which the new items will be copied. To make the names Paul and Jon appear at the front of the list, you could insert the second array using InsertRange with an index value of zero. This code would result in the names being listed in this order: Paul , Jon , Tom , Mark :

 string[] Friends = {"Tom","Mark"}; string[] CoWorkers = {"Paul","Jon"}; ArrayList MergedList = new ArrayList(); MergedList.AddRange(Friends);  MergedList.InsertRange(0, CoWorkers);  foreach( string Name in MergedList ) {    Response.Write("<p />" + Name); }

Note	The merging-lists.aspx example page demonstrates the code shown here.

The ICollection.IsSynchronized Property

ASP.NET enables Web applications to share objects by using the Application and Cache intrinsic objects. If an object reference is shared this way, it's possible for multiple pages to work simultaneously with the same object instance. If this happens, any changes to the object must be synchronized. If two pages try to modify an object at the same time without synchronization, there is a high probability that the object's state will become corrupted. Objects that can safely be manipulated simultaneously are thread-safe. A thread-safe object takes on the responsibility of guarding itself from concurrent access, providing the necessary synchronization.

The ICollection.IsSynchronized property can be used to determine if an object is thread-safe. For performance reasons, most objects (including ArrayList ) are not thread-safe by default. Thus, you should not share types like ArrayList in a Web application without performing some form of synchronization. In classic ASP, you could use the Application.Lock and Application.Unlock methods for synchronization and while they are available in ASP.NET, they're not suitable for this particular task. They provide a coarse-grained lock (which is application-wide) that simply isn't suitable for scalable applications.

To safely share a collection object such as an ArrayList between multiple Web pages, you need to use a synchronization helper object. Such a helper object provides the same public interface as a non-thread- safe type, but adds a synchronization wrapper around the methods and properties that would otherwise not be thread-safe. Since this is such a common requirement, the collection types (and many other framework classes) follow a common pattern.

Types that need to work in a thread-safe way provide a public, static, method called Synchronized that takes a non-thread-safe object reference and creates and returns a thread-safe wrapper that can be used to synchronize calls. Both objects manipulate the same underlying state, so changes made by either the thread-safe or non-thread-safe object will be seen by any other code that holds a reference to either object.

The following VB.NET code shows how a non-thread-safe ArrayList adds an item before creating a thread-safe wrapper:

  Dim NotThreadSafeArrayList As ArrayList   NotThreadSafeArrayList = New ArrayList()   NotThreadSafeArrayList.Add("Hello")   Dim ThreadSafeArrayList As ArrayList   ThreadSafeArrayList = ArrayList.Synchronized(NotThreadSafeArrayList)   If ThreadSafeArrayList.IsSynchronized = True Then   Response.Write("<p />It's synchronized")   End If

Figure 15-5 illustrates how this ThreadSafeArrayList works by protecting calls, and then delegating the calls to the non-thread-safe object:

Figure 15-5:

The ICollection.SyncRoot Property

When writing thread-safe code, it's common to have a handle or object that's used by all the possible code paths in different threads (web pages) in order to synchronize access to the shared state. The CLR automatically allows any .NET type instance to be a synchronization root (SyncRoot) that can be locked and unlocked to ensure that one or more code statements are only ever executed by a single thread at a time.

In VB.NET, you can use an object reference in conjunction with the SyncLock statement to make code thread-safe:

  Sub DoSomethingWithAList( list as ArrayList )   SyncLock list   list.Add("abc")   End SyncLock   End Sub

In C#, you can achieve the same result using the lock statement:

  void DoSomethingWithAList( ArrayList list )   {   lock(list)   {   list.Add("abc");   }   }

Under the hood, both C# and VB.NET use the System.Threading.Monitor object to perform their synchronization. Both the C# and VB.NET compilers add exception handling around the statements being executed, to ensure that any exceptions that are not handled in the code do not result in synchronization locks not being released.

Using SyncLock (or lock ) you can achieve a fine-grained level of locking inside ASP.NET pages. Rather than having one global lock, which is effectively what Application.Lock and Application.Unlock provide, you can have many smaller locks, which reduces lock contention .

The disadvantage to this approach is that it requires that page developers really understand multi- threading. Since the writing of multi-threaded applications is not simple (and something ASP.NET does its best to protect you from), using the Synchronized method to automatically make a type thread-safe is often the preferred approach to take.

When acquiring or releasing a SyncLock , you need to know what SyncRoot object to use. This is the function of the ICollection.SyncRoot property. As you cannot assume any implementation knowledge about the type providing an interface, you cannot make any assumptions about which SyncRoot object to use either.

Consider this VB.NET code:

  Dim NotThreadSafeArrayList As ArrayList   NotThreadSafeArrayList = New ArrayList()   NotThreadSafeArrayList.Add("Hello")   Dim ThreadSafeArrayList1 As ArrayList   Dim ThreadSafeArrayList2 As ArrayList   Dim ThreadSafeArrayList3 As ArrayList   ThreadSafeArrayList1 = ArrayList.Synchronized(NotThreadSafeArrayList)   ThreadSafeArrayList2 = ArrayList.Synchronized(NotThreadSafeArrayList)   ThreadSafeArrayList3 = ArrayList.Synchronized(NotThreadSafeArrayList)

Here you create an ArrayList and then create three synchronization wrapper objects, each of which exposes the ICollection interface. Since each of the wrapper objects actually manipulates the same underlying array, the SyncRoot object used by each of the wrappers is the non-thread-safe ArrayList , as depicted in Figure 15-6:

Figure 15-6:

To synchronize access to the array in a Web page so that you could perform an atomic operation like adding the contents of the array to a database and clearing it, you'd need to lock out all other threads from using the ArrayList . If you only had a reference to an ArrayList object or an ICollection interface, and didn't know whether or not that type was thread-safe, how could you achieve this?

If you had a thread-safe wrapper, and wrote your code as follows, it would fail miserably:

  SyncLock ThreadSafeArrayList1   ' copy list to db and clear list (as an example)   End SyncLock

All this code does is acquire a lock on the thread-safe wrapper, not on the underlying list. Anybody using one of the other thread-safe wrappers would still be able to modify the list. The ICollection.SyncRoot property solves this problem. The implementation of this property should always return the appropriate SyncRoot object. You should therefore rewrite the code as follows:

  SyncLock ThreadSafeArrayList1.SyncRoot   ' copy list to db and clear list (as an example)   End SyncLock

Working with Dictionary Objects

In ASP.NET, state is managed by the Session or Application intrinsic objects. The value type stored is of type System.Object (rather than Variant , as was the case in ASP 3.0). Since all types in .NET derive from System.Object , any built-in or custom type can be held in session or application state.

The following code shows a simple example of storing and retrieving state using the Session intrinsic object. Using VB.NET, you would write:

  Session("value1") = "Wrox"   Session("value2") = "Wiley"   Dim value As String   value = CType(Session("value1"), string)   value = CType(Session("value2"), string)

Using C#, you would write:

  Session["value1"] = "Wrox";   Session["value2"] = "Wiley";   string value;   value = (string) Session["value1"];   value = (string) Session["value2"];

Here two values are being set using the keys value1 and value2 . The values associated with these keys are then retrieved.

The Hashtable Class

The Hashtable class represents a dictionary of associated keys and values, implemented as a hash table . A hash table is a proven way of efficiently storing and retrieving values using the hash of a key value.

Internally, the ASP intrinsic objects such as Session use the System.Collections.Hashtable class to implement key-based lookup functionality. This class is very similar to the scripting runtime Dictionary object used in classic ASP pages, and provides all those methods expected from a dictionary type object.

Using the Hashtable class is straightforward. You can create an instance of the Hashtable class and use a text indexer to set and retrieve associated keys and values. For example, using C#, you would write:

  Hashtable ourSession;   ourSession = new Hashtable();   ourSession["value1"] = "Wrox";   ourSession["value2"] = "Wiley";   string value;   value = (string) ourSession["value1"];   value = (string) ourSession["value2"];

You can determine if a key is contained within the hash table using the ContainsKey method. Using VB.NET, you would write:

  If ourSession.ContainsKey("value1") = True Then   Response.Write("The key value1 is in the Hashtable")   End If

You could of course use the Contains method to determine if a key is present, but since all that does is call the ContainsKey method, there is no point. You can determine if a specified value is held within the Hashtable using the ContainsValue method. Using VB.NET, you would write:

  If ourSession.ContainsValue("Wrox") = True Then   Response.Write("The value Wrox is in the Hashtable")   End If

Figure 15-7 demonstrates the creation of a Hashtable , and the use of the ContainsKey and ContainsValue methods:

Figure 15-7:

Although the Hashtable allows any object type to be used as a key, only those types that override System.Object.GetHashCode and System.Object.Equals should actually be used. All of the primitive types in .NET, such as integer and string, override these methods and are safe to use as keys.

A hash table depends on hash codes to uniquely identify keys. Hash codes are numbers that, where possible, uniquely identify a single object instance of a specific type. A perfect hash code algorithm will always return a hash code that is unique to a single instance of a specific type. A good candidate for a hash code is something along the lines of the identity field for a row within a database. The Hashtable class uses hash codes to provide efficient and fast lookups. When creating custom types, you also have to implement a good hash code algorithm.

As any type can be used with most of the collections in the .NET Framework class library, the System.Object class has a method called GetHashCode that returns a hash code for any object instance. The system-provided implementation of this method returns a hash code that uniquely identifies an object instance, but the hash code is not specific to a given type. The returned value is simply an index held internally by the CLR to identify an object. Thus, if the system-provided implementation of GetHashCode is not overridden by a type, then by default, two equal hash code values will imply that it's the same object instance, as demonstrated in this C# code:

  class SomeType {};   SomeType variable1 = new SomeType();   SomeType variable2;   variable2 = variable1;   if ( variable1.GetHashCode() == variable2.GetHashCode() )   {   Response.Write("The two variables reference the same object");   }

Hash codes enable classes like Hashtable to efficiently store and retrieve values. When an item is added to a Hashtable , the hash code of its associated key is used to determine a slot in which an item can be held. If a key with the same hash code doesn't already exist at the slot located using the hash code, the value can be saved. If the slot is already full, System.Object.Equals is called to determine if the key already in the slot is in fact equal to the one used to locate the slot. If both keys are equal, an exception is thrown. If the keys are different, a new key and value is added to the hash table in a different slot.

For these reasons, any type used as a key within a hash table must:

Implement an efficient hash code algorithm that (where possible) uniquely identifies an object of a specific type. This means that you must override System.Object.GetHashCode .
Override the System.Object.Equals method and provide an efficient comparison of two object instances. Typically, you would implement this by comparing the hash codes (if you can be sure that the hash code is always unique), or key fields that are held within a type as fields.

You can enumerate all of the keys and values in a hash table using the Keys or Values properties. Both these properties are defined as the ICollection type, and so they can be accessed in numerous ways. The following code uses the C# foreach statement to enumerate the keys. This code will actually result in a call to table.Keys.GetEnumerator (recall that ICollection inherits this from IEnumerable ). This method will return an enumerator object that implements IEnumerator , which can then be used to walk through each key value:

  Hashtable table = new Hashtable();   table["name"] = "Richard";   table["age"] = "Old enough";   foreach (string key in table.Keys)   {   Response.Write("<br />" + key );   }

In VB.NET, you can do the same thing using the For Each..Next statement:

  Dim table As Hashtable = New Hashtable()   Dim value As String   table("name") = "Richard"   table("age") = "Old enough"   For Each value As String In table.Values   Response.Write("<br />" & value)   Next

The Hashtable class implements the interface IEnumerable , so you can enumerate all its contained keys and items. The enumerator object returned by the Hashtable's implementation of IEnumerable.GetEnumerator exposes contained items using the value type System.Collections.DictionaryEntry . This value type has properties that allow you to access the associated Key and Value properties. To list all of the keys and current values held in a Hashtable , you could write the following C# code:

  foreach (DictionaryEntry entry in table)   {   Response.Write("<br />Key: " + entry.Key + " Value: " + entry.Value);   }

The public GetEnumerator method of the Hashtable object returns the IDictionaryEnumerator interface. This enumerator interface has all the methods and properties of IEnumerator , in addition to three properties that expose the Key , Value , and DictionaryEntry of the current item. Returning a custom enumerator with these additional properties reduces casting when the foreach statement cannot be used. This in turn improves performance of an application, as the CLR must check that a cast is type-safe.

The following C# code shows how you could use the IDictionaryEnumerator interface:

  IDictionaryEnumerator e;   e = table.GetEnumerator();   while (e.MoveNext())   {   Response.Write("<br />Key: " + e.Key + " Value: " + e.Value );   }

When the type implements the IEnumerable interface, it still has to implement a version of the GetEnumerator method, which returns an IEnumerator interface. The following C# code shows how to implement an enumerable type that supports both the standard IEnumerable.GetEnumerator method using an explicit interface method definition, and a public GetEnumerator method that reduces the need for casting:

  public class MyCollection : IEnumerable   {   public MyCustomEnumerator GetEnumerator()   {   return new MyCustomEnumerator();   }   IEnumerator IEnumerable.GetEnumerator()   {   return new MyCustomEnumerator();   }   }

Comparing Hashtable with the Intrinsic ASP.NET Objects

There are a number of differences between using the Hashtable class and the ASP.NET intrinsic objects:

The key values for a Hashtable are not restricted to strings. Any type can be used, so long as the type used as a key overrides the System.Object.Equals and System.Object.GetHashCode methods.
String keys are case-sensitive whereas those of the ASP.NET intrinsic objects are not.
When enumerating over an ASP.NET intrinsic object, you enumerate over the keys associated with each contained item value. The Hashtable returns both the key and value using the DictionaryEntry class.
When enumerating over an ASP.NET intrinsic object, the Current property returns a System.String object (the key value) and not a System.Collections.DictionaryEntry entry.

The IDictionary Interface

The IDictionary interface defines methods and properties that allow you to work with an unordered collection of keys and their associated values. Keys and values are both defined in this interface as type System.Object , which means any type can be used as a key, and any type can be used as a value. The IDictionary interface defines methods and properties that allow you to:

Add items to the collection (by passing in the key and value to the Add method).
Delete items from the collection (by passing the key of the value to delete to the Remove method)
Determine if a specified key exists and is associated with an item (using the Contains method).
Empty the collection (by calling the Clear method).
Enumerate all of the keys in the collection (using the Keys property, which is defined as an ICollection )
Enumerate all of the values in the collection (using the Values property, which is defined as an ICollection ).
Enumerate key-value pairs (by using the GetEnumerator method, which returns an IDictionaryEnumerator interface that is discussed shortly)
Determine if the collection is read-only (using the IsReadOnly property).
Determine if the collection is of a fixed size (using the IsFixedSize property).

The IDictionary interface derives from the ICollection interface so it inherits all of its methods and properties, as well as those of the basic interface IEnumerable .

Case Sensitivity of Keys

With the ASP.NET intrinsic objects, key values are case-insensitive. This means that the following C# code, which uses the intrinsic Session object, will happily set and retrieve the value correctly, even though the case in the key is different:

  Session["key"] = "value";   Response.Write("<p />value is " + Session["KEY"]);

The following VB.NET code shows the hash codes for two objects that contain the same string value, but with differing case:

  Dim name1, name2 As String   name1 = "Richard"   name2 = "RICHARD"   outResult1.InnerHtml &= "Hash code for '" & name1 & "' is " & _   name1.GetHashCode()   outResult1.InnerHtml &= "Hash code for '" & name2 & "' is " & _   name2.GetHashCode()   ...

Since the .NET Framework is case-sensitive by default, the hash codes for these strings are unique. If you want two strings that differ only by case to be considered the same, you have to implement a hash code provider class that determines hash codes for other types, and can therefore use a different algorithm to create a hash code, one which is not based on case-sensitive letters . Since it's common to have case- insensitive keys, the .NET Framework has a built-in hash code provider that is case-insensitive:

  ...   Dim hcp As IHashCodeProvider   hcp = CaseInsensitiveHashCodeProvider.Default   Response.Write("Hash code for '" & name1 & "' is " & hcp.GetHashCode(name1))   Response.Write("<br />");   Response.Write("Hash code for '" & name2 & "' is " & hcp.GetHashCode(name2))

Figure 15-8 demonstrates case-sensitive and case-insensitive hash code generation, using the example code you've just seen, in the display-hashcodes.aspx page:

Figure 15-8:

Classes such as Hashtable can use hash code providers to override their behavior. The following C# code shows how you can create a hash table that is not case-sensitive (when string keys are used) by using the standard framework classes System.Collections.CaseInsensitiveHashCodeProvider and System.Collections.CaseInsensitiveComparer :

  Hashtable ourSession;   ourSession = new Hashtable(CaseInsensitiveHashCodeProvider.Default,   CaseInsensitiveComparer.Default);   Session["key"] = "value";   Response.Write("value is " + Session["KEY"]);

With this code, the value will be correctly displayed in the browser “ the value will be found, even though the casing of the key is different.

The CaseInsensitiveHashCodeProvider class provides an implementation of the IHashCodeProvider interface that creates a case-insensitive hash code of string types. For non-string types, the objects default hash code is returned, which means that such types may still be case-sensitive (this depends on the algorithm used to create the hash).

The CaseInsensitiveComparer class provides an implementation of the IComparer interface that will perform a case-insensitive comparison for two string values. If either of the objects being compared is not a string, it uses the default Comparer.Default comparer object, encountered earlier.

Both CaseInsensitiveHashCodeProvider and CaseInsensitiveComparer have a static property called Default , which returns an instance of the class that is shared and always available.

Creating a case-insensitive hash table is a common requirement, and so a helper class, System.Collections.Specialized.CollectionsUtil , is provided to assist. For example:

  Hashtable names;   names = CollectionsUtil.CreateCaseInsensitiveHashtable();

Important

The System.Collections.Specialized namespace is imported by default into a ASP.NET page so you do not need to use fully qualified names or an import directive.

The Stack Class

The Stack class provides a Last-In First-Out (LIFO) collection of System.Object types. The last item pushed onto the stack is always the first item retrieved from the stack. The Stack class can be extremely useful when you need to perform recursive operations, where you often need to save and restore values in order (such as the context within an XSLT processor) but in which the number of values saved and restored is not necessarily known in advance.

A Stack class can also be useful if you simply need to save the values of some variables while performing a temporary calculation, after which you need to recall their original values.

The Stack class implements the ICollection and IEnumerable collection interfaces, and so can be enumerated using the For Each and foreach statements of VB.NET and C#, have its size determined, have specific items accessed using an indexer, and so on.

The following VB.NET code shows how you can push several items on to a stack and then pop (retrieve) them:

  Dim s As Stack = New Stack()     s.Push("Alex")   s.Push("Dave")   s.Push("Rich")   s.Push("Brian")   s.Push("Karli")     While s.Count > 0   Response.Write(s.Pop() & "<br />")   End While

Here, you keep retrieving and displaying items from the stack until the Count property tells you that there are no more items. As shown in Figure 15-9, the items are listed in reverse order in the browser, since the last item ( "Karli" ) is retrieved first:

Figure 15-9:

If you want to look at an item on the stack without actually removing it, use the Peek method:

  Response.Write(s.Peek())

The Stack class has a static Synchronized method that returns a thread-safe wrapper for a stack, which allows it to be called concurrently from different threads:

 Dim s As Stack = New Stack()  Dim s2 As Stack   s2 = Stack.Synchronized(s)

Important

Unless you provide your own synchronization, you should always use a thread-safe wrapper if multiple ASP.NET pages are going to access a shared object using application state.

The Queue Class

The Queue class provides a First-In First-Out (FIFO) collection. This is useful when you need to process items in order, such as a list of in-memory work to do. The following VB.NET code shows how to add items to a Queue before retrieving and displaying them, checking the Count property to ensure there are still items to be processed :

  Dim q As Queue = New Queue()   q.Enqueue("Wake up")   q.Enqueue("Have a shower")   q.Enqueue("Get dressed")   q.Enqueue("Go to work")   q.Enqueue("Do a great job")   q.Enqueue("Come home and relax")   While q.Count > 0   Response.Write(q.Dequeue() & "<br />")   End While

The output from this example, shown in Figure 15-10, demonstrates that the items are always retrieved in the order they are added:

Figure 15-10:

Like the Stack class the Queue class implements the ICollection and IEnumerable collection interfaces, and so can be enumerated using the foreach statements of VB.NET and C#, have its size determined, have specific items accessed using an indexer, and so on.

The Queue class has a Synchronized method that can return a thread-safe wrapper for a queue, which enables it to be called concurrently from different threads:

 Dim q As Queue = New Queue()  Dim q2 As Queue   q2 = Queue.Synchronized(q)

Again, a thread-safe wrapper should always be used if multiple ASP.NET pages are going to access a shared object using application state.

The SortedList Class

The SortedList class is an interesting collection class, as it's a cross between a Hashtable and an ArrayList . It implements the IDictionary interface and maintains key-value pairs like the Hashtable , but internally holds items in two sorted arrays. The following VB.NET code shows how to create and use a SortedList :

  Dim alphabet As New SortedList()     alphabet = CollectionsUtil.CreateCaseInsensitiveSortedList()     alphabet.Add("Z", "The Letter Z")   alphabet.Add("A", "The Letter A")   alphabet.Add("S", "The Letter S")     For Each letter As DictionaryEntry In alphabet   outResult.InnerHtml &= "Key:" & letter.Key & " - Value:" _   & letter.Value & "<br />"   Next

This code creates an instance of the SortedList class, adds three items that represent some letters of the alphabet, and then uses the For Each statement to display the items. The result can be seen in Figure 15-11:

Figure 15-11:

A SortedList always maintains a sorted collection of items. When an item is inserted, a binary search is performed to see if the specified key already exists. If the key is already in use, an ArgumentException is thrown since keys must be unique. If the key is not in use, the return code from the binary search (from the Array.BinarySearch method) is used to determine the insert point of the new item.

The sort order for a SortedList is determined by the implementation of IComparer that is used. The default comparer is System.Collections.Comparer . As discussed earlier, this implementation uses the IComparable interface of the left object passed into the IComparer.Compare method. In this example, the key is a string type, so the result is that the list is sorted alphabetically in ascending order (it will also be case-sensitive), as that's how the string type implementation of IComparable works.

An overloaded constructor of SortedList allows you to specify a custom IComparer interface if you need to override the sort order for a list of items. For example:

  IComparer ic = new SomeCustomTypeThatImplementsIComparer();   SortedList alphabet = new SortedList(ic);

If you need to create a case-insensitive sorted list, you could use the System.Collections.Comparer with this overload, or you could use the CreateCaseInsensitiveSortedList static method of the CollectionsUtil class (which basically just saves some typing):

 SortedList alphabet;  alphabet = CollectionsUtil.CreateCaseInsensitiveSortedList();

The SortedList class implements the IDictionary and IEnumerable interfaces. The IEnumerable.GetEnumerator method returns an IDictionaryEnumerator type.

Accessing items using an indexer or searching for an item is performed very quickly but adding items to a sorted list can be slower than adding them to unsorted lists, since the SortedList class holds keys and values in two different arrays. Arrays are held contiguously in memory, so when an item is inserted between two existing items, the items to the right of the insertion point have to be moved to make room.

This copying can be relatively slow for large lists, so it might be necessary to consider an alternative approach.

Creating an Indexed or Sorted View of an Existing Collection

The SortedList class has a constructor that accepts an IDictionary parameter. This constructor will copy the contents of the specified collection. This provides a great way of indexing and sorting existing collections of items, without having to change the source collection. The following C# code creates an unordered list of names using a Hashtable , and then creates a sorted list using the SortedList class:

  Dim names As New Hashtable()   names.Add("RA", "Richard Anderson")   names.Add("DS", "David Sussman")   names.Add("RH", "Rob Howard")   names.Add("AH", "Alex Homer")   names.Add("KW", "Karli Watson")   names.Add("BF", "Brian Francis")   For Each name As DictionaryEntry In names   outResult1.InnerHtml &= "Key:" & name.Key & " - Value:" _   & name.Value & "<br />"   Next     Dim sortedNameList As New SortedList(names)   For Each name As DictionaryEntry In sortedNameList   outResult2.InnerHtml &= "Key:" & name.Key & " - Value:" _   & name.Value & "<br />"   Next

The output of this code is shown in Figure 15-12:

Figure 15-12:

When a SortedList copies the contents of a source collection using the IDictionary interface, the list capacity is automatically resized to match the source. Once copied, no link between the collections is maintained . Changes made to one of the collections do not affect the other. Like the Stack and Queue classes, the SortedList class has a Synchronized method that can return a thread-safe wrapper for a given SortedList .

The BitArray Class

The BitArray class provides an efficient way of creating and manipulating a compact array of bit values. The bit array can be any size, and individual bits are represented as Boolean values, where True equals bit set ( 1 ), and False equals bit not set ( ). The following C# code shows how you can create a bit array that contains eight bits:

  BitArray b = new BitArray(8);

By default all bits are set to False . However, you can use an overloaded constructor to set the default value to True :

  BitArray b = new BitArray(8, true);

The BitArray class implements the IEnumerable and ICollection interfaces, so by using the IEnumerable interface, you can display the values of the bit array. This VB.NET code creates a new BitArray with all the values set to False :

  Dim b As BitArray = new BitArray(8, False)   Dim index As Integer   outResult.InnerHtml = "Count property is " & b.Count & "<br />"   index = 0   For Each value As Boolean in b   index += 1   outResult.InnerHtml &= "Bit " & index & " - value is " & value & "<br />"   Next

Figure 15-13 shows the BitArray with all the values set to False , as shown in the preceding code:

Figure 15-13:

To set a bit, you can use an indexer or the Set method. Following VB.NET code sets bit 2 and bit 7 using both approaches:

 Dim b As BitArray = new BitArray(8, False) Dim index As Integer outResult.InnerHtml = "Count property is " & b.Count & "<br />" index = 0  b(2) = True   b.Set(7,True)  For Each value As Boolean in b    index += 1    outResult.InnerHtml &= "Bit " & index & " - value is " & value & "<br />" Next

Figure 15-14 shows the BitArray after this code runs, with bits 2 and 7 set as expected:

Figure 15-14:

Note that the code displays the Bit numbers starting from 1, whereas (like all .NET collections) the values are actually indexed starting from zero.

The BitArray class provides several methods that allow logical bit operations to be performed against a BitArray . These include:

And : Performs a bitwise AND operation on the elements in the current BitArray against the corresponding elements in another BitArray .
Not : Inverts all bits in the array such that any 1 's ( True ) become ( False ) and vice versa.
Or : Performs a bitwise OR operation on the elements in the current BitArray against the corresponding elements in another BitArray .
Xor : Performs a bitwise Exclusive OR ( XOR ) operation on the elements in the current BitArray against the corresponding elements in another BitArray

All of these logical operations work in the same way. The following C# code extends the previous example by creating a second bit array, setting bits , 1 , and 6 , and then performing an Xor operation:

 Dim b As BitArray = new BitArray(8, False)  Dim b2 As BitArray = new BitArray(8, False)  Dim index As Integer outResult.InnerHtml = "Count property is " & b.Count & "<br />" index = 0 b(2) = True b.Set(7,True)  b2(0) = True   b2(1) = True   b2(6) = True   b.Xor(b2)  For Each value As Boolean in b    index += 1    outResult.InnerHtml &= "Bit " & index & " - value is " & value & "<br />" Next

The expected result of an Xor is that a given bit is set to 1 if only one of the input bits is 1 . If both bits are or 1 , the value should be zero. Figure 15-15 shows the BitArray from the previous example after the Xor operation has taken place:

Figure 15-15: