Professional ASP.NET 1.1 [Electronic resources] نسخه متنی

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); 

} 

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 .

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"); 

} 

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"); 

} 

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 

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 .

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 

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 

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); 

} 

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);
}

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(); 

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) 

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 (
0 ). 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

0 (

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

0 ,

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

0 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: