Dialogs

Dialogs are windows displayed by a program for the purpose of exchanging specific information with the user. There are two kinds of dialogs:

• Modal dialogs block all other interaction with the program until the dialog is closed.
• Non-modal dialogs allow the user to interact with the program in other ways while the dialog is open.

We will examine three classes provided by Microsoft® .NET 6, each of which implements a modal dialog. .NET provides various other classes, such as FolderBrowserDialog , FontDialog , and ColorDialog , that also implement specific kinds of dialogs. We conclude by discussing how custom dialogs may be built using Visual Studio®.

Simple Text File I/O

Many of the I/O tools provided by .NET are found in the System.IO namespace. One class that provides several general-purpose static methods related to file I/O is the File class. Two of the static methods provided by this class are:

• File.ReadAllText and
• File.WriteAllText

The File.ReadAllText method takes a string as its only parameter. This string should give the path to a text file. It will then attempt to read that entire file and return its contents as a string. For example, if fileName refers to a string containing the path to a text file, then

string contents = File.ReadAllText(fileName);

will read that entire file and place its contents into the string to which contents refers. We can then process the string contents however we need to.

The File.WriteAllText method takes two parameters:

• a string giving the path to a file; and
• a string? (i.e., a nullable string - a string that may be null) giving the text to be written.

It will then attempt to write the given text as the entire contents of the given file. If this text is null, an empty file will be written. Thus, if fileName refers to a string containing the path to a file and contents refers to some string, then

File.WriteAllText(fileName, contents);

will write to that file the string to which contents refers.

While these methods are quite easy to use, they are not always the best ways of doing text file I/O. One drawback is that files can be quite large - perhaps too large to fit in memory or within a single string. Even when it is possible to read the entire file into a single string, it may use enough memory that performance suffers. In the section, “Advanced Text File I/O” , we will present other techniques for reading and writing text files.

Exception Handling

As was mentioned in the previous section , various problems can occur when doing file I/O. Some of these problems include:

• Trying to write to a read-only file.
• Trying to access a file that is locked by another process.
• Accessing an external drive that becomes disconnected.

Note that some of these issues are beyond the programmer’s control, while others may be tedious for the programmer to check. When one of these problems prevents an I/O operation from completing successfully, an exception is thrown. This section discusses how to handle such exceptions gracefully, without terminating the program.

The mechanism used to handle exceptions is the try-catch construct. In its simplest form, it looks like:

try
{
    
    // Block of code that might throw an exception
    
}
catch
{
    
    // Code to handle the exception
    
}

If we are concerned about exceptions thrown while doing I/O, we would include the I/O and anything dependent on it within the try-block. If at any point within this block an exception is thrown, control immediately jumps to the catch-block. Here, we would place code to handle the exception - for example, displaying a message to the user.

Suppose, for example, that we want to count the number of upper-case letters in a file whose name is in the string referenced by fileName. We could use the following code:

try
{
    string contents = File.ReadAllText(fileName);
    int count = 0;
    foreach (char c in contents)
    {
        if (char.IsUpper(c))
        {
            count++;
        }
    }
    MessageBox.Show("The file contains " + count + " upper-case letters.");
}
catch
{
    MessageBox.Show("An exception occurred.");
}

We should always include within the try-block all of the code that depends on what we want to read. Consider what would happen, for example, if we tried to move the statement,

MessageBox.Show("The file contains " + count + " upper-case letters.");

outside the try-catch. First, we would have a syntax error because the variable count is declared within the try-block, and hence cannot be used outside of it. We could fix this error by declaring and initializing count prior to the try statement. The resulting code would compile and run, but consider what happens if an exception is thrown during the reading of the file. Control immediately jumps to the catch-block, where the message, “An exception occurred.”, is displayed. After that, assuming we have made these changes to the above code, control continues on past the catch-block to the code to display the results. Because the file was not successfully read, it really doesn’t make any sense to do this. The code given above, however, displays a result only if the result is successfully computed; otherwise, the exception message is displayed.

In the above example, the message, “An exception occurred.”, isn’t very helpful to the user. It gives no indication of what the problem is. In order to be able to provide more information to the user, we need more information regarding the nature of the exception. The way we do this is to use some additional code on the catch statement:

catch (Exception ex)

The word Exception above is a type. Every exception in C# is a subtype of the Exception class. In this form of the catch statement, we can include any subtype of Exception, including Exception itself, as the first word within the parentheses. The second word is a new variable name. One effect of this parenthesized part is to declare this variable to be of the given type; i.e., ex is of type Exception, and may be used within the catch block.

This form of the catch statement will catch any exception that can be treated as the given type. If we use the type, Exception, as above, the catch-block will still catch any exception. In addition, the variable defined within the parentheses will refer to that exception. Thus, the parenthesized part of this statement behaves much like a parameter list, giving us access to the exception that was thrown. Having the exception available to examine, we can now give more meaningful feedback to the user. One rather crude way of doing this is to use the exception’s ToString method to convert it to a string representation, which can then be displayed to the user; for example,

catch (Exception ex)
{
    MessageBox.Show(ex.ToString());
}

Replacing the catch-block in the earler example with this catch-block might result in the following message:

While this message is not something we would want to show to an end user, it does provide helpful debugging information, such as the exception thrown and the line that threw the exception.

A single try-block can have more than one catch-block. In such a case, whenever an exception occurs within the try-block, control is transferred to the first catch-block that can catch that particular exception. For example, we can set up the following construct:

try
{

    // Code that may throw an exception

}
catch (DirectoryNotFoundException ex)
{

    // Code to handle a DirectoryNotFoundException

}
catch (FileNotFoundException ex)
{

    // Code to handle a FileNotFoundException

}
catch (Exception ex)
{

    // Code to handle any other exception

}

If we don’t need access to the exception itself in order to handle it, but only need to know what kind of exception it is, we can leave off the variable name in the catch statement. For example, if we are trying to read from a file whose name is referenced by the string fileName, we might handle a FileNotFoundException as follows:

catch (FileNotFoundException)
{
    MessageBox.Show("Could not find the file " + fileName);
}

Advanced Text File I/O

Though the File.ReadAllText and File.WriteAllText methods provide simple mechanisms for reading and writing text files, they are not always the best choices. For one reason, files can be very large — too large to fit into memory, or possibly even larger than the maximum length of a string in C# (2,147,483,647 characters). Even when it is possible to store the entire contents of a file as a string, it may not be desirable, as the high memory usage may degrade the overall performance of the system.

For the purpose of handling a sequence of input or output data in more flexible ways, .NET provides streams. These streams are classes that provide uniform access to a wide variety of sequences of input or output data, such as files, network connections, other processes, or even blocks of memory. The StreamReader and StreamWriter classes (in the System.IO namespace) provide read and write, respectively, access to text streams, including text files.

Some of the more useful public members of the StreamReader class are:

• A constructor that takes a string giving a file name as its only parameter and constructs a StreamReader to read from that file.
• A Read method that takes no parameters. It reads the next character from the stream and returns it as an int. If it cannot read a character because it is already at the end of the stream, it returns -1 (it returns an int because -1 is outside the range of char values).
• A ReadLine method that takes no parameters. It reads the next line from the stream and returns it as a string?. If it cannot read a line because it is already at the end of the stream, it returns null.
• An EndOfStream property that gets a bool indicating whether the end of the stream has been reached.

With these members, we can read a text file either a character at a time or a line at a time until we reach the end of the file. The StreamWriter class has similar public members:

• A constructor that takes a string giving a file name as its only parameter and constructs a StreamWriter to write to this file. If the file already exists, it is replaced by what is written by the StreamWriter; otherwise, a new file is created.
• A Write method that takes a char as its only parameter. It writes this char to the end of the stream.
• Another Write method that takes a string? as its only parameter. It writes this string? to the end of the stream. If the given string? is null, nothing is written.
• A WriteLine method that takes no parameters. It writes a line terminator to the end of the stream (i.e., it ends the current line of text).
• Another WriteLine method that takes a char as its only parameter. It writes this char to the end of the stream, then terminates the current line of text.
• Yet another WriteLine method that takes a string? as its only parameter. It writes this string? to the end of the stream, then terminates the current line of text. If the string? is null, only the line terminator is written.

Thus, with a StreamWriter, we can build a text file a character at a time, a line at a time, or an arbitrary string at a time. In fact, a number of other Write and WriteLine methods exist, providing the ability to write various other types, such as int or double. In each case, the given value is first converted to a string, then written to the stream.

Streams are different from other classes, such as strings or arrays, in that they are unmanaged resources. When a managed resource, such as a string or an array, is no longer being used by the program, the garbage collector will reclaim the space that it occupies so that it can be allocated to new objects that may need to be constructed. However, after a stream is constructed, it remains under the control of the program until the program explicitly releases it. This has several practical ramifications. For example, the underlying file remains locked, restricting how other programs may use it. In fact, if an output stream is not properly closed by the program, some of the data written to it may not actually reach the underlying file. This is because output streams are typically buffered for efficiency — when bytes are written to the stream, they are first accumulated in an internal array, then written as a single block when the array is full. When the program is finished writing, it needs to make sure that this array is flushed to the underlying file.

Both the StreamReader and StreamWriter classes have Dispose methods to release them properly; however, because I/O typically requires exception handling, it can be tricky to ensure that this method is always called when the I/O is finished. Specifically, the try-catch may be located in a method that does not have access to the stream. In such a case, the catch-block cannot call the stream’s Dispose method.

To handle this difficulty, C# provides a using statement. A using statement is different from a using directive, such as

using System.IO;

A using statement occurs within a method definition, not at the top of a code file. Its recommended form is as follows:

using ( /* declaration and initialization of disposable variable(s) */ )
{

    /* Code that uses the disposable variables(s) */

}

Thus, if we want to read and process a text file whose name is given by the string variable fileName, we could use the following code structure:

using (StreamReader input = new StreamReader(fileName))
{

    /* Code that reads and process the file accessed by the
     * StreamReader input */

}

This declares the variable input to be of type StreamReader and initializes it to a new StreamReader to read the given file. This variable is only visible with the braces; furthermore, it is read-only — its value cannot be changed to refer to a different StreamReader. The using statement then ensures that whenever control exits the code within the braces, input’s Dispose method is called.

More than one variable of the same type may be declared and initialized within the parentheses of a using statement; for example:

using (StreamReader input1 = new StreamReader(fileName1),
    input2 = new StreamReader(fileName2))
{

    /* Code that reads from input1 and input2 */

}

The type of variable(s) declared must be a subtype of IDisposable . This ensures that the variables each have a Dispose method.

As a complete example of the use of a StreamReader and a StreamWriter, together with a using statement for each, suppose we want to write a method that takes as its parameters two strings giving the name of an input file and the name of an output file. The method is to reproduce the input file as the output file, but with each line prefixed by a line number and a tab. We will start numbering lines with 1. The following method accomplishes this:

/// <summary>
/// Copies the file at inFileName to outFileName with each line
/// prefixed by its line number followed by a tab.
/// </summary>
/// <param name="inFileName">The path name of the input file.</param>
/// <param name="outFileName">The path name of the output file.</param>
private void AddLineNumbers(string inFileName, string outFileName)
{
    using (StreamReader input = new StreamReader(inFileName))
    {
        using (StreamWriter output = new StreamWriter(outFileName))
        {
            int count = 0;
            while (!input.EndOfStream)
            {
                // Because input is not at the end of the stream, its ReadLine
                // method won't return null.
                string line = input.ReadLine()!;
                count++;
                output.Write(count);
                output.Write('\t');   // The tab character
                output.WriteLine(line);
            }
        }
    }
}

As noted above, a StreamReader’s ReadLine method has a return type of string? because it will return null if the end of the stream has already been reached. Furthermore, the compiler is unable to determine that the loop condition will prevent the call to ReadLine from returning null. Thus, in order to suppress the compiler warning when the returned string? is assigned to a string, we include a ! following the call to ReadLine, and document the reason with a comment above this line.

We can call the above method within a try-block to handle any exceptions that may be thrown during the I/O. The catch-block will not have access to either input or output, but it doesn’t need it. If an exception is thrown during the I/O, the two using statements will ensure that the Dispose methods of both the StreamReader and the StreamWriter are called.

Other File I/O

Not all files are plain text files — often we need to read and/or write binary data. .NET provides the FileStream class for this purpose.

The FileStream class provides constructors for creating a FileStream for reading, writing, or both. These constructors can be used to specify how the file is to be opened or created, the type of access to be allowed (i.e., reading/writing), and how the file is to be locked. In most cases, however, a simpler way to construct an appropriate FileStream is to use one of the following static methods provided by the the File class:

• File.OpenRead(string fn) : returns a FileStream for reading the file with the given path name. A FileNotFoundException is thrown if the file does not exist.
• File.OpenWrite(string fn) : returns a FileStream for writing to the file with the given path name. If the file exists, it will be replaced; otherwise, it will be created.

Two of the most commonly-used methods of a FileStream are ReadByte and WriteByte . The ReadByte method takes no parameters and returns an int. If there is at least one byte available to read, the next one is read and its value (a nonnegative integer less than 256) is returned; otherwise, the value returned is -1 (this is the only way to detect when the end of the stream has been reached). The WriteByte method takes a byte as its only parameter and writes it to the file. It returns nothing.

Because a FileStream has no EndOfStream property, we must code a loop to read to the end of the stream somewhat differently from what we have seen before. We can take advantage of the fact that in C#, an assignment statement can be used within an expression. When this is done, the value of the assignment statement is the value that it assigns. Thus, if input is a FileStream opened for input, we can set up a loop to read a byte at a time to the end of the stream as follows:

int k;
while ((k = input.ReadByte()) != -1)
{
    byte b = (byte)k;
    . . .
}

In the above code, the ReadByte method reads a byte from the file as long as there is one to read, and assigns it to the int variable k. If there is no byte to read, it assigns -1 to k. In either case, the value of the assignment statement is the value assigned to k. Thus, if the ReadByte method is at the end of the stream, it returns -1, which is assigned to k, and the loop terminates. Otherwise, the loop iterates, assigning k to b as a byte. The remainder of the iteration can then use the byte read, which is in b.

strings

Instances of the string class are immutable sequences of characters. Because string is a class, it is a reference type . Because instances are immutable, once they are constructed, their contents cannot change. Note that this does not mean that string variables cannot change - we can assign a string variable s the value “abc” and later assign it the value “xyz”. These assignments simply assign to s references to different instances of the string class. What immutability does mean is that there is no way to change any of the characters in either of these instances (i.e., in either “abc” or “xyz”). As a result, it is safe to copy a string by simply assigning the value of one string variable to another; for example, if s is a string variable, we can write:

string t = s;

Note that this is not safe when dealing with mutable reference types, such as arrays. For example, let a be an int[ ] with at least one element, and consider the following code sequence:

int[ ] b = a;
b[0]++;

Because a and b refer to the same array, a[0] is incremented as well. This danger is absent for strings because they are immutable.

We access individual characters in a string by indexing; i.e., if s is a string variable, then s[0] retrieves its first character, s[1] retrieves its second character, etc. For example, if s refers to the string, “abc”, then after executing

char c = s[1];

c will contain ‘b’. Note that a statement like

s[0] = 'x';

is prohibited in order to enforce immutability.

We obtain the number of characters in a string using its Length property; for example:

int len = s.Length;

We can concatenate two strings using the + operator. For example, if s refers to the string “abc” and t refers to the string “xyz”, then

string u = s + t;

will assign the string “abcxyz” to u.

Because strings are immutable, building long strings directly from many small pieces is very inefficient. Suppose, for example, that we want to convert all the lower-case characters in the string text to upper-case, and to convert all upper-case letters in text to lower-case. All other characters we will leave unchanged. We can do this with the following code:

string result = "";
for (int i = 0; i < text.Length; i++)
{
    char c = text[i];
    if (char.IsLower(c))
    {
        result += char.ToUpper(c);
    }
    else if (char.IsUpper(c))
    {
        result += char.ToLower(c);
    }
    else
    {
        result += c;
    }
}

Now suppose that text contains 100,000 characters. Each iteration of the loop executes one of the three branches of the if-statement, each of which concatenates one character to the string accumulated so far. Because strings are immutable, this concatenation must be done by copying all the characters in result, along with the concatenated character, to a new string. As a result, if we were to add up the total number of characters copied over the course of the entire loop, we would come up with 5,000,050,000 character copies done. This may take a while. In general, we say that this code runs in O(n²) time, where n is the length of text. This means that as n increases, the running time of the code is at worst proportional to n². In the next section , we will see how we can do this much more efficiently using another data structure.

strings have many other methods to allow various kinds of manipulation - see the documentation for the string class for details.

StringBuilders

In the previous section , we saw that building large strings from small pieces by concatenating them together is very inefficient. This inefficiency is due to the fact that strings are immutable. In order to overcome the inefficiency of concatenation, we need an alternative data structure that we can modify. The StringBuilder class fills this need.

Like strings, StringBuilders implement sequences of characters, but the contents of StringBuilders can be changed. The StringBuilder class has six constructors. The simplest StringBuilder constructor takes no parameters and constructs an empty StringBuilder — i.e., a StringBuilder containing no characters:

StringBuilder sb = new();

We can then modify a StringBuilder in various ways. First, we may append a char to the end using its Append method. This method not only changes the contents of the StringBuilder, but it also returns a reference to it. Thus if we have char variables, a, b, and c, and a StringBuilder variable sb, we can write code such as:

sb.Append(a).Append(b).Append(c);

The first call to Append appends the contents of a to sb, and returns sb. Thus, the second call to Append also applies to sb - it appends the contents of b. Likewise, the third call appends the contents of c.

Because this method changes a StringBuilder, rather than constructing a new one, its implementation is very efficient - in most cases, only the appended character needs to be copied (see “Implementation of StringBuilders ” for details). This class has other Append methods as well, including one that appends the contents of a given string . This method likewise only needs to copy the appended characters.

Let us now return to the problem of converting all lower-case letters in a string to upper-case, converting all upper-case letters to lower-case, and leaving all other characters unchanged. We can use a StringBuilder as an intermediate data structure to do this much more efficiently than the code presented in the previous section :

StringBuilder sb = new();
for (int i = 0; i < text.Length; i++)
{
    char c = text[i];
    if (char.IsLower(c))
    {
        sb.Append(char.ToUpper(c));
    }
    else if (char.IsUpper(c))
    {
        sb.Append(char.ToLower(c));
    }
    else
    {
        sb.Append(c);
    }
}
string result = sb.ToString();

On most iterations, the above loop only copies one character. In addition, the call to the StringBuilder’s ToString method copies each character in the result. If text is 100,000 characters long, this is a total of 200,000 character copies. Using the StringBuilder implementation described in the next section , there are some iterations that copy more than one character, but even if we account for this, it turns out that fewer than 400,000 characters are copied, as opposed to over five billion character copies when strings are used directly (see the previous section ). The .NET StringBuilder implementation performs even better. In either case, the above code runs in O(n) time, where n is the length of text; i.e., as n gets large, the running time is at worst proportional to n. Thus, its performance degrades much less rapidly than the O(n²) code that uses strings directly.

A program that runs the above code and the code given in the previous section on user-provided text files can be obtained by creating a Git repository (see “Git Repositories” ) using this URL . A noticeable performance difference can be seen on text files larger than 100K - for example, the full text of Lewis Carroll’s Through the Looking Glass .

StringBuilders have some features in common with strings. For example, we access individual characters in a StringBuilder by indexing; i.e., if sb is a StringBuilder variable, then sb[0] accesses its first character, sb[1] accesses its second character, etc. The main difference here is that with a StringBuilder, we may use indexing to change characters; e.g., we may do the following, provided sb contains at least 3 characters:

sb[2] = 'x';

A StringBuilder also has a Length property, which gets the number of characters contained. However, we may also set this property to any nonnegative value, provided there is enough memory available to provide this length. For example, we may write:

sb.Length = 10;

If the new length is shorter than the old, characters are removed from the end of the StringBuilder. If the new length is longer that the old, chars containing the Unicode NULL value (0 in decimal) are appended.

StringBuilders have many other methods to allow various kinds of manipulation - see the documentation for the StringBuilder class for details. There is also a StringBuilder constructor that takes a string as its only parameter and constructs a StringBuilder containing the contents of that string.

Implementation of StringBuilders

In this section, we will examine some of the implementation details of the StringBuilder class. There are several reasons for doing this. First, by examining these details, we can begin to understand why a StringBuilder is so much more efficient than a string when it comes to building long strings a character at a time. Second, by studying implementations of data structures, we can learn techniques that might be useful to us if we need to build our own data structures. Finally, a computing professional who better understands the underlying software will be better equipped to use that software effectively.

In what follows, we will develop an implementation of a simplified StringBuilder class. Specifically, we will only implement enough to support the program that flips the case of all characters in a string (see the previous section ). Most other features of a StringBuilder have a rather straightforward implementation once the basics are done (we will show how to implement an indexer in a later section ).

In order to illustrate more clearly the techniques used to implement a StringBuilder, we will present an implementation that uses only those types provided by the C# core language, rather than those found in a library such as .NET. One of the more useful data structures that the C# core language provides for building more advanced data structures is the array. We can represent the characters in a StringBuilder using a char[ ]. One difficulty in using an array, however, is that we don’t know how many characters our StringBuilder might need. We will return to this issue shortly, but for now, let’s just arbitrarily pick a size for our array, and define:

/// <summary>
/// The initial capacity of the underlying array.
/// </summary>
private const int _initialCapacity = 100;

/// <summary>
/// The character in this StringBuilder.
/// </summary>
private char[] _characters = new char[_initialCapacity];

An array with 100 elements will give us room enough to store up to 100 characters. In fact, initializing the array in this way actually gives us 100 characters, as each array element is initialized to a Unicode NULL character (a char with a decimal value of 0). Because char is a value type , each array element is going to store a char - it’s just a question of which char it is going to store. Therefore, if we want to be able to represent a sequence of fewer than 100 characters, we need an additional field to keep track of how many characters of the array actually represent characters in the StringBuilder. We therefore define:

/// <summary>
/// The number of characters in this StringBuilder.
/// </summary>
private int _length = 0;

Thus, for example, if _length is 25, the first 25 characters in _characters will be the characters in the StringBuilder.

Because both fields have initializers, the default constructor will initialize them both; hence, we don’t need to write a constructor. Let’s focus instead on the Append method. This method needs to take a char as its only parameter and return a StringBuilder (itself). Its effect needs to be to add the given char to the end of the sequence of characters in the StringBuilder.

In order to see how this can be done, consider how our fields together represent the sequence of characters:

Within the array referred to by _characters, the first _length locations (i.e., locations 0 through _length - 1) store the characters in the StringBuilder. This means that _characters[_length] is the next available location, provided this is a valid array location. In this case, we can simply place the char to be appended in _characters[_length], increment _length (because the number of characters in the StringBuilder has increased by 1), and return the StringBuilder.

However, what if we are already using all of the array locations for characters in the StringBuilder? In this case, _length is the length of the array, and therefore is not a valid array location. In order to handle this case, we need to make more room. The only way to do this to construct a new, larger array, and copy all of the characters into it. We will then make _characters refer to the new array. (.NET actually provides a method to do all this, but in order to show the details of what is happening, we will not use it.) Now that there is enough room, we can append the new character as above. The code is as follows:

/// <summary>
/// Appends the given character to the end of this StringBuilder.
/// </summary>
/// <param name="c">The character to append.</param>
/// <returns>This StringBuilder.</returns>
public StringBuilder Append(char c)
{
    if (_length == _characters.Length)
    {
        char[] chars = new char[2 * _length];
        _characters.CopyTo(chars, 0);
        _characters = chars;
    }
    _characters[_length] = c;
    _length++;
    return this;
}

A few comments on the above code are in order. First, when we need a new array, we allocate one of twice the size as the original array. We do this for a couple of reasons. First, notice that copying every character from one array to another is expensive if there are a lot of characters. For this reason, we don’t want to do it very often. By doubling the size of the array every time we run out of room, we increase the size by enough that it will be a while before we need to do it again. On the other hand, doubling the array doesn’t waste too much space if we don’t need to fill it entirely.

The CopyTo method used above copies all of the elements in the array to which this method belongs (in this case, _characters) to the array given by the first parameter (chars in this case), placing them beginning at the location given by the second parameter (0 in this case). Thus, we are copying all the elements of _characters to chars, placing them beginning at location 0.

The last statement within the if block assigns the reference stored in chars to _characters; i.e., it makes _characters refer to the same array as does chars. The last statement in the method returns the StringBuilder whose Append method was called.

To complete this simple implementation, we need to provide a ToString method. This method is already defined for every object; hence, StringBuilder inherits this definition by default. However, the ToString method defined for objects doesn’t give us the string we want. Fortunately, though, this method is a virtual method, meaning that we can re-define by overriding it. We do this by using the keyword, override, in its definition. Visual Studio®’s auto-complete feature is helpful here, as when we type the word override, it presents us with a list of the methods that can be overridden. Selecting ToString from this list will fill in a template for the method with a correct parameter list and return type.

We want this method to return the string formed from the first _length characters in _characters. We can form such a string using one of the string constructor s. This constructor takes three parameters:

• a char[ ] containing the characters to form the string;
• an int giving the index in this array of the first character to use; and
• an int giving the number of characters to use.

We can therefore define the ToString method as follows:

/// <summary>
/// Converts this StringBuilder to a string.
/// </summary>
/// <returns>The string equivalent of this StringBuilder.</returns>
public override string ToString()
{
    return new string(_characters, 0, _length);
}

You can obtain a program containing the complete class definition by creating a Git repository (see “Git Repositories” ) using this URL . This program is a modification of the program used in the previous section to compare the performance differences between using strings or StringBuilders when building strings a character at a time. Its only modification is to use this StringBuilder class, defined within a class library, instead of the class defined in .NET. By running the program on long strings, you can verify that the performance of this StringBuilder class is comparable to that of the StringBuilder in .NET.

Now that we have the details of a StringBuilder implementation, we can begin to see why it is so much more efficient to build a string a character at a time using a StringBuilder, as opposed to using a string. As we have noted, allocating a new array and copying all characters to it is expensive; however, we have tried to reduce the number of times this is done. To see how this is accomplished, suppose we are building a string of 100,000 characters. The first time we need a larger array, we will copy 100 characters to a 200-element array. The next time, we will copy 200 characters to a 400-element array. This will continue until we copy 51,200 characters to a 102,400-element array, which is large enough to hold all of the characters. If we add up all of the character copies we have done when allocating new arrays, we find that there are a total of 102,300 copies. In addition, each time we call Append, we copy the char parameter to the array. This is another 100,000 copies. Finally, the ToString method must copy all of the characters to the string it is constructing. This is another 100,000 character copies, for a total of 302,300 copies. In general, the number of character copies will always be less than 4n, where n is the length of the string being built.

Introduction to Stacks

A stack provides last-in-first-out (LIFO) access to data items. We usually think of a stack as arranging data items vertically, like a stack of trays in a cafeteria. Access is normally provided only at the top of the stack; hence, if we want to add an item, we push it onto the top, and if we want to remove an item, we pop it from the top. Because we only access the top of the stack, the item that we pop is always the remaining item that we had pushed the most recently.

.NET provides two kinds of stacks. One is the Stack class found in the System.Collections namespace. Because this namespace isn’t typically included in the list of namespaces searched by the compiler, but the namespace containing the other Stack definition (discussed a bit later below) is included, we need to refer to it in code as System.Collections.Stack. This class provides a stack of object?s. Because every type in C# is a subtype of object, we can push any data items we want onto a Stack. Because object? is a nullable type, we can even push null. The most commonly-used public members of this class are:

• A constructor that takes no parameters and constructs an empty stack.
• A Count property, which gets the number of elements on the Stack as an int.
• A Push method, which takes a single parameter of type object?, and pushes it onto the top of the Stack.
• A Peek method, which takes no parameters and returns the element at the top of the Stack (as an object?) without changing the Stack’s contents. If the Stack is empty, this method throws an InvalidOperationException.
• A Pop method, which takes no parameters, and removes and returns the element at the top of the Stack (as an object?). If the Stack is empty, this method throws an InvalidOperationException.

As we mentioned above, because the Push method takes an object? as its parameter, we can push any data elements we want, including null, onto a Stack. What this means, however, is that the compiler can’t determine the type of these elements when we retrieve them; i.e., both the Peek and Pop methods return object?s. Thus, for example, the following code will not compile:

System.Collections.Stack s = new();
s.Push(7);
int n = s.Pop() + 1;

The problem is that the Pop method returns an object?, and we can’t add an int to an object?. Although it’s pretty easy to see from this code that Pop will return 7, in many cases it’s impossible to know at compile time the exact type of the element returned (for example, the Stack may be a parameter to a public method, and that method may be called by code that has not yet been written). Consequently, the compiler simply uses the return type of Pop - it doesn’t even try to figure out the type any more precisely.

If you want to use the value returned by Pop or Peek as something other than an object?, you need to tell the compiler what its type actually is. You do this with a cast:

int n = (int)s.Pop() + 1;

This tells the compiler to assume that the value returned by Pop is an int. The type is still checked, but now it is checked at run time, rather than at compile time. If the runtime environment detects that the value is not, in fact, an int, it will throw an InvalidCastException.

While the above line of code will now compile, it generates a warning because Pop might return null, which cannot be cast to int. In order to avoid this warning, once we have determined that the call won’t return a null value, we need to use the ! operator:

// The element on the top of the stack is the int 7
int n = (int)s.Pop()! + 1;

Note that we include a comment explaining why Pop won’t return null here.

Often when we need a stack, the data items that we wish to store are all of the same type. In such a case, it is rather awkward to include a cast whenever we retrieve an item from the stack. In order to avoid this casting, .NET provides a generic stack, Stack<T> , found in the System.Collections.Generic namespace. The T within angle brackets is a type parameter - we may replace it with any type we want. This type tells what type of elements may be placed in this stack. For example, if we want a stack that will only contain ints, we can write:

Stack<int> s = new();

This class has members similar to those listed above for the non-generic Stack class, except that the Push method takes a parameter of type T (i.e., whatever type we placed within the angle brackets in the type declaration and constructor call), and the Peek and Pop methods each return a value of type T. As a result, the following is now legal code:

Stack<int> s = new();
s.Push(7);
int n = s.Pop() + 1;

We will show how you can define your own generic types in “Implementing a Stack ”. First, however, we want to work through two example applications of stacks. We will do that in the next two sections.

Implementing Undo and Redo for a TextBox

A TextBox has a rather crude Undo/Redo feature. By right-clicking on a TextBox, a popup menu containing an Undo entry is presented. This Undo will undo only one action, which may include several edits. An immediate subsequent Undo will undo the Undo - in essence, a Redo. The same behavior can be achieved using Ctrl+Z. A more powerful Undo/Redo feature would allow an arbitrary sequence of edits to be undone, with the option of redoing any of these Undo operations. This section outlines various ways of implementing such a feature.

We first observe that when we perform an Undo, we want to undo the most recent edit that has not been undone; i.e., we need LIFO access to the edits. Likewise, when we perform a Redo, we want to redo the most recent Undo that has not been redone. Again, we need LIFO access to the Undo operations. We will therefore use two stacks, one to keep the edit history, and one to keep the Undo history (i.e., the history of Undo operations that can be redone).

Before we can define these stacks, we need to determine what we will be storing in them; i.e., we need to determine how we will represent an edit. We will consider several ways of doing this, but the simplest way is to store the entire contents of the TextBox after each edit. Proceeding in this way, we really aren’t representing edits at all, but we certainly would have the information we need to undo the edits. Likewise, the Undo history would store the entire contents of the TextBox prior to each Undo. Because the contents of the TextBox form a string, we need two private fields, each referring to a stack of strings:

/// <summary>
/// The history of the contents of the TextBox.
/// </summary>
private Stack<string> _editingHistory = new();

/// <summary>
/// The history of TextBox contents that have been undone and can be redone.
/// </summary>
private Stack<string> _undoHistory = new();

Before we can proceed to implementing the Undo and Redo operations, we need to do a bit more initialization. Note that by the way we have defined _editingHistory, this stack needs to contain the initial contents of the TextBox. Therefore, assuming the TextBox field is named uxEditBuffer, we need to add the following line to the end of the constructor of our user interface:

_editingHistory.Push(uxEditBuffer.Text);

In order to support Undo and Redo, we need to be able to record the content of uxEditBuffer each time it is modified. We can do this via an event handler for the TextChanged event on the TextBox. Because this event is the default event for a TextBox, we can add such an event handler by double-clicking on the TextBox within the Visual Studio® Design window. This event handler will then be called every time the contents of the TextBox are changed.

We need to deal with one important issue before we can write the code for this event handler. Whenever we perform an Undo or Redo operation, we will change the contents of the TextBox. This will cause the TextChanged event handler to be called. However, we don’t want to treat an Undo or a Redo in the same way as an edit by the user. For example, if the user does an Undo, we don’t want that Undo to be considered an edit, or a subsequent Undo would just undo the Undo; i.e., it would perform a Redo rather than an Undo.

Fortunately, there is an easy way to distinguish between an edit made by the user and a change made by the program code. A TextBox has a Modified property, which is set to true when the user modifies the TextBox contents, and is set to false when the program modifies the contents. Thus, we only want to record the TextBox contents when this property is true. Assuming the TextBox is named uxEditBuffer, we can then set up the event handler as follows:

/// <summary>
/// Handles a TextChanged event on the edit buffer.
/// </summary>
/// <param name="sender">The object signaling the event.</param>
/// <param name="e">Information about the event.</param>
private void EditBufferTextChanged(object sender, EventArgs e)
{
    if (uxEditBuffer.Modified)
    {
        RecordEdit();
    }
}

Now let’s consider how to write the RecordEdit method. Suppose there are two GUI controls (e.g., menu items or buttons) called uxUndo and uxRedo, which invoke the Undo and Redo operations, respectively. These controls should be enabled only when there are operations to undo or redo. Thus, initially these controls will be disabled. Whenever the user modifies the contents of the TextBox, we need to do the following:

• Push the resulting text onto _editingHistory.
• Enable uxUndo, as there is now an edit that can be undone.
• Clear the contents of _undoHistory, as the last change to the TextBox contents was not an Undo. (A Stack<T> has a Clear method for this purpose.)
• Disable uxRedo.

We therefore have the following method:

/// <summary>
/// Records an edit made by the user.
/// </summary>
private void RecordEdit()
{
    _editingHistory.Push(uxEditBuffer.Text);
    uxUndo.Enabled = true;
    _undoHistory.Clear();
    uxRedo.Enabled = false;
}

Now that we have a mechanism for recording the user’s edits, we can implement the Undo operation. The contents of the TextBox following the last edit (i.e, the current contents of the TextBox) should always be at the top of _editingHistory. An Undo should change the current contents to the previous contents - i.e., to the next string on _editingHistory. However, we don’t want to lose the top string, as this is the string that would need to be restored by a subsequent Redo. Instead, we need to push this string onto _undoHistory. We then need to enable uxRedo. In order to determine whether uxUndo should be enabled, we need to know how many elements remain in _editingHistory. We know there is at least one string on this stack - the string that we placed in the TextBox. There is an edit to undo if there is at least one more element on this stack - i.e., if its Count is greater than 1. We therefore have the following event handler for a Click event on uxUndo:

/// <summary>
/// Handles a Click event on Undo.
/// </summary>
/// <param name="sender">The object signaling the event.</param>
/// <param name="e">Information about the event.</param>
private void UndoClick(object sender, EventArgs e)
{
    _undoHistory.Push(_editingHistory.Pop());
    uxRedo.Enabled = true;
    uxEditBuffer.Text = _editingHistory.Peek();
    uxUndo.Enabled = _editingHistory.Count > 1;
}

The implementation of Redo is similar, but now we need to transfer a string between the stacks in the opposite direction - we move the top string from _undoHistory to _editingHistory. Then uxRedo should be enabled if any more strings remain in _undoHistory. The string we removed from _undoHistory should be placed in the TextBox. Finally, uxUndo should be enabled. We therefore have the following event handler for a Click event on uxRedo:

/// <summary>
/// Handles a Click event on Redo.
/// </summary>
/// <param name="sender">The object signaling the event.</param>
/// <param name="e">Information about the event.</param>
private void RedoClick(object sender, EventArgs e)
{
    _editingHistory.Push(_undoHistory.Pop());
    uxRedo.Enabled = _undoHistory.Count > 0;
    uxEditBuffer.Text = _editingHistory.Peek();
    uxUndo.Enabled = true;
}

This solution will work, except that an Undo or Redo always brings the text caret to the beginning of the TextBox contents. Furthermore, if the TextBox contains a long string, each edit causes a long string to be placed onto _editingHistory. This can quickly eat up a lot of memory, and may eventually fill up all available storage. In what follows, we will outline two better approaches.

The idea for both of these approaches is that instead of recording the entire contents of the TextBox for each edit, we only record a description of each edit. A single edit will either be an insertion or a deletion of some text. The number of characters inserted/deleted may vary, as the edit may be a cut or a paste (if we select a block of text and do a paste, the TextChanged event handler is actually called twice - once for the deletion of the selected text, and once for the insertion of the pasted text). We can therefore describe the edit with the following three values:

• A bool indicating whether the edit was an insertion or a deletion.
• An int giving the index of the beginning of the edit.
• The string inserted or deleted.

We can maintain this information in stacks in one of two ways. One way is to use non-generic stacks and to push three items onto a stack for each edit. If we do this, we need to realize that when we pop elements from the stack, they will come out in reverse order from the way they were pushed onto it. Alternatively, we can define a class or a structure to represent an edit using the three values above as private fields. We can then use generic stacks storing instances of this type.

Whichever way we choose to represent the edits, we need to be able to compute each of the three pieces of information describing the edit. In order to compute this information, we need to compare the current contents of the TextBox with its prior contents in order to see how it changed. This means that, in addition to the two private fields we defined for the stacks, we will also need a private field to store the last string we saw in the TextBox. Rather than initializing _editingHistory within the constructor, we should now initialize this string in its place (because there will have been no edits initially, both stacks should initially be empty). If we keep this string field up to date, we will always have a “before” picture (the contents of this field) and an “after” picture (the current contents of the TextBox) for the edit we need to record.

To determine whether the edit was an insertion or a deletion, we can compare the lengths of the current TextBox contents and its previous contents. If the current content is longer, then the edit was an insertion; otherwise, the edit was a deletion. We therefore have the following method for this purpose:

/// <summary>
/// Returns whether text was deleted from the given string in order to
/// obtain the contents of the given TextBox.
/// </summary>
/// <param name="editor">The TextBox containing the result of the edit.</param>
/// <param name="lastContent">The string representing the text prior
/// to the edit.</param> 
/// <returns>Whether the edit was a deletion.</returns>
private bool IsDeletion(TextBox editor, string lastContent)
{
    return editor.TextLength < lastContent.Length;
}

Note that the above code uses the TextBox’s TextLength property. This is more efficient than finding the length of its Text property because evaluating the Text property requires all the characters to be copied to a new string.

Before getting either the location of the edit or the edit string itself, it is useful to compute the length of the edit string. This length is simply the absolute value of the difference in the lengths of the string currently in the TextBox and the last string we saw there. The Math class (in the System namespace) contains a static method Abs , which computes the absolute value of an int. We therefore have the following method:

/// <summary>
/// Gets the length of the text inserted or deleted.
/// </summary>
/// <param name="editor">The TextBox containing the result of the edit.</param>
/// <param name="lastContent">The string representing the text prior
/// to the edit.</param> 
/// <returns>The length of the edit.</returns>
private int GetEditLength(TextBox editor, string lastContent)
{
    return Math.Abs(editor.TextLength - lastContent.Length);
}

Now that we can determine whether an edit is a deletion or an insertion, and we can find the length of the edit string, it isn’t hard to find the beginning of the edit. First, suppose the edit is a deletion. The point at which the deletion occurred is the point at which the text caret now resides. We can find this point using the TextBox’s SelectionStart property. When there is no current selection - and there never will be immediately following an edit - this property gives the location of the text caret in the TextBox. Now consider the case in which the edit was an insertion. When text is inserted into a TextBox, the text caret ends up at the end of the inserted text. We need to find its beginning. We can do this by subtracting the length of the edit string from the text caret position. We therefore have the following method:

/// <summary>
/// Gets the location of the beginning of the edit.
/// </summary>
/// <param name="editor">The TextBox containing the result of the edit.</param>
/// <param name="isDeletion">Indicates whether the edit was a deletion.</param>
/// <param name="len">The length of the edit string.</param>
/// <returns>The location of the beginning of the edit.</returns>
private int GetEditLocation(TextBox editor, bool isDeletion, int len)
{
    if (isDeletion)
    {
        return editor.SelectionStart;
    }
    else
    {
        return editor.SelectionStart - len;
    }
}

The last piece of information we need is the string that was deleted or inserted. If the edit was a deletion, this string can be found in the previous TextBox contents. Its beginning is the point at which the edit occurred. We can therefore extract the deleted string from the previous contents using its Substring method. We pass this method the beginning index of the substring and its length, and it returns the substring, which is the deleted string. On the other hand, if the edit was an insertion, we can find the inserted string in the current TextBox contents by using its Substring in a similar way. We therefore have the following method:

/// <summary>
/// Gets the edit string.
/// </summary>
/// <param name="content">The current content of the TextBox.</param>
/// <param name="lastContent">The string representing the text prior
/// to the edit.</param> 
/// <param name="isDeletion">Indicates whether the edit was a deletion.</param>
/// <param name="editLocation">The location of the beginning of the edit.</param>
/// <param name="len">The length of the edit.</param>
/// <returns>The edit string.</returns>
private string GetEditString(string content, string lastContent, bool isDeletion, int editLocation, int len)
{
    if (isDeletion)
    {
        return lastContent.Substring(editLocation, len);
    }
    else
    {
        return content.Substring(editLocation, len);
    }
}

Using the methods above, we can modify the RecordEdit method to obtain the three values listed above to describe an edit. Once we have placed these three values onto the stack of editing history, we also need to update the string giving the previous TextBox contents. This should now be the current TextBox contents. We can then finish the method as shown above.

In order to implement Undo and Redo, we need to be able to insert and delete text in the TextBox. A string has two methods we can use to accomplish this:

• The Remove method takes as its parameters the beginning index and length of the portion to remove, and returns the result.
• The Insert method takes as its parameters the index at which the string should be inserted, and the string to insert. It returns the result.

Given the location of the edit along with the edit string itself, we can easily provide the parameters to the appropriate method above. Furthermore, it is not hard to set the location of the text caret using the TextBox’s SelectionStart property - we just need to be sure to add the length of the edit string if we are inserting text. The following method therefore performs a given edit, updating the string containing the last contents of the TextBox as well (we assume this string is called _lastText):

/// <summary>
/// Performs the given edit on the contents of the given TextBox.
/// </summary>
/// <param name="editor">The TextBox to edit.</param>
/// <param name="isDeletion">Indicates whether the edit is a deletion.</param>
/// <param name="loc">The location of the beginning of the edit.</param>
/// <param name="text">The text to insert or delete.</param>
private void DoEdit(TextBox editor, bool isDeletion, int loc, string text)
{
    if (isDeletion)
    {
        _lastText = editor.Text.Remove(loc, text.Length);
        editor.Text = _lastText;
        editor.SelectionStart = loc;
    }
    else
    {
        _lastText = editor.Text.Insert(loc, text);
        editor.Text = _lastText;
        editor.SelectionStart = loc + text.Length;
    }
}

We can now implement event handlers for Undo and Redo. We can obtain the description of the edit from the stack of editing history for an Undo, or from the stack of undo history for a Redo. This description gives us the type of edit (i.e., either insertion or deletion), the beginning position of the edit, and the inserted or deleted string. To implement a Redo, we simply do this edit, but to implement an Undo, we must do the opposite.

Parenthesis Matching

The problem of finding matching parentheses must be solved in many computing applications. For example, consider a C# compiler. Matching parentheses (( and )), brackets ([ and ]), and braces ({ and }) delimit various parts of the source code. In order for these parts to be interpreted correctly, the compiler must be able to determine how these different kinds of parentheses match up with each other. Another example is processing structured data stored in XML format. Different parts of such a data set are delimited by nested begin tags like <summary> and end tags like </summary> (documentation comments in C# code are in XML format). These tags are essentially different kinds of parentheses that need to be matched.

We will restrict our attention to parentheses, brackets, and braces. We will call all six of these characters “parentheses”, but will divide them into three types. Each type then has an opening parenthesis and a closing parenthesis. We will define a string restricted to these six characters to be matched (or balanced) if we can repeatedly remove an opening parenthesis and a closing parenthesis of the same type to its immediate right until there are no more parentheses.

For example, suppose we have the string, “([]{()[]})[{}]”. We can apply the matching-pair removal process described above as follows (blank space is inserted to make it easier to see which parentheses are removed):

    ([]{()[]})[{}]
    (  {()[]})[{}]
    (  {  []})[{}]
    (  {    })[{}]
    (        )[{}]
              [{}]
              [  ]

Hence, this string is matched. On the other hand, consider the string, “([]{()[])}[{}]”. When we apply the above process to this string, we obtain:

    ([]{()[])}[{}]
    (  {()[])}[{}]
    (  {  [])}[{}]
    (  {    )}[{}]
    (  {    )}[  ]
    (  {    )}

and we can go no further. Hence, this string is not matched.

We can extend the definition of a matched string to include other characters if we first remove all other characters before we begin the matching-pair removal process. In what follows, we will focus on the problem of determining whether a given string is matched.

The matching-pair removal process shown above gives us an algorithm for determining whether a string is matched. However, if implemented directly, it isn’t very efficient. Changes to a string are inefficient because the entire string must be reconstructed. We could use a StringBuilder, but even then, removing characters is inefficient, as all characters to the right of the removed character must be moved to take its place. Even if we simply change parentheses to blanks, as we did in the above example, searching for matching pairs is still rather expensive.

What we would like to do instead is to find a way to apply the matching-pair removal process while scanning the string once. As we are scanning the string, we don’t want to spend time searching for a matching pair. We can do this if, while scanning the string, we keep all unmatched opening parentheses in a stack. Then the parenthesis at the top of the stack will always be the rightmost unmatched opening parenthesis. Thus, starting with an empty stack, we do the following for each character in the string:

• If the character is a opening parenthesis, push it onto the stack.
• If the character is a closing parenthesis:
  • If the stack is nonempty, and the current character matches the character on top of the stack, remove the character from the top of the stack.
  • Otherwise, the string is not matched.
• Ignore all other characters.

If the stack is empty when the entire string has been processed, then the string is matched; otherwise, it is not.

For example, consider the string, “{a[b]([c]){de}}f[(g)]”. In what follows, we will simulate the above algorithm, showing the result of processing each character on a separate line. The portion of the line with an orange background will be the stack contents, with the top element shown at the right. We will insert blank space in the orange area for clarity, but the stack will only contain opening parentheses. The first character with a gray background is the character currently being processed.

{a[b]([c]){de}}f[(g)]    --- an opening parenthesis - push it onto the stack
{a[b]([c]){de}}f[(g)]    --- ignore
{ [b]([c]){de}}f[(g)]    --- push onto stack
{ [b]([c]){de}}f[(g)]    --- ignore
{ [ ]([c]){de}}f[(g)]    --- closing parenthesis that matches the top - remove top
{    ([c]){de}}f[(g)]    --- push onto stack
{    ([c]){de}}f[(g)]    --- push onto stack
{    ([c]){de}}f[(g)]    --- ignore
{    ([ ]){de}}f[(g)]    --- a match - remove top
{    (   ){de}}f[(g)]    --- a match - remove top
{         {de}}f[(g)]    --- push onto stack
{         {de}}f[(g)]    --- ignore
{         { e}}f[(g)]    --- ignore
{         {  }}f[(g)]    --- a match - remove top
{             }f[(g)]    --- a match - remove top
               f[(g)]    --- ignore
                [(g)]    --- push onto stack
                [(g)]    --- push onto stack
                [(g)]    --- ignore
                [( )]    --- a match - remove top
                [   ]    --- a match - remove top
                         --- end of string and stack empty - matched string

If at any time during the above process we had encountered a closing parenthesis while the stack was empty, this would have indicated that this closing parenthesis has no matching opening parenthesis. In this case, we would have stopped immediately, determining that the string is not matched. Likewise, if we had encountered a closing parenthesis that did not match the parenthesis at the top of the stack, this would have indicated a mismatched pair. Again, we would have stopped immediately. Finally, if we had reached the end of the string with a nonempty stack, this would have indicated that we had at least one opening parenthesis that was never matched. We would have again determined that the string is not matched.

Implementing a Stack

This section gives an overview of perhaps the most common way to implement a stack. For example, the implementations of both System.Collections.Stack and System.Collections.Generic.Stack<T> use this technique. This implementation uses an array to store the elements of the stack, and is quite similar to the StringBuilder implementation we described in the last chapter. We have discussed two kinds of stacks in this chapter - stacks of object?s and generic stacks. We will focus on implementing a generic stack in this section, as it is easy to modify such an implementation to be non-generic.

We first need to consider how to define a generic class. In the simplest case, we simply add a type parameter to the class statement, as follows:

public class Stack<T>
{
    . . .
}

Within this class definition, T is treated like any other type, except that the compiler knows nothing about it. We can declare fields, parameters, and local variables to be of type T. Even though the compiler knows nothing about T, it will still do type checking - you cannot assign an expression of any other type to a variable of type T, and you can only assign an expression of type T to variables of either type T or type object? (because any type is a subtype of object?). Assigning an expression of type T to an object variable may generate a compiler warning, but is permitted as well. In general, we can define generic data types with any number of type parameters if more that one generic type is needed by the data structure. To do this, we would list the type parameters, separated by commas, between the < and > symbols of the generic class definition. Each of the type parameters is then treated as a type within the class definition. We will show how the types passed as type parameters can be restricted in a later section .

For the class Stack<T>, only one type parameter is needed. The type parameter T denotes the type of the values that are stored in the stack. Therefore, the array in which we will store the elements will be of type T?[ ]. The ? is needed because if a reference type is used for T, when the array is constructed, all locations will initially store null, and will continue to store null until stack elements are placed into them.

As in the StringBuilder implementation , we will need a private field for this array. This field can be initialized in a manner similar to the StringBuilder implementation; hence, we don’t need to write a constructor.

A stack has a public read-only property, Count, which gets the number of elements in the stack (as an int). We can define this property to use the default implementation with a private set accessor, as outlined in the section, “Properties ”.

Before we can delve any further into the implementation, we need to decide how we are going to arrange the elements in the array. Because all of our accesses will be to the top of the stack, it makes sense to keep the bottom element of the stack at location 0, and as we go up the stack, keep each successive element in the next location:

This arrangement makes sense because unless all of the array locations are being used, there is room to push a new element on top of the stack without having to move any pre-existing elements out of its way.

Note the similarity of this arrangement to the implementation of a StringBuilder . Given this similarity, we can implement the Push method in a similar way to how we implemented the Append method for a StringBuilder. Instead of taking a char parameter, the Push method takes a T parameter, but this is the type that we can store in the array. The biggest difference in these two methods is that while Append returns a StringBuilder, Push returns nothing.

We now need to implement the public methods that retrieve elements from the stack. We will start with the Peek method, which takes no parameters and returns a T. This method needs to begin with some error checking: if there are no elements in the stack, it needs to throw an InvalidOperationException. We can do this by constructing such an exception and throwing it with the throw keyword:

throw new InvalidOperationException();

If there are elements in the stack, we need to return the one at the top. Note from the figure above that the top element is at the location preceding the location indexed by Count. However, note that this element is of type T?, whereas the return type of Peek is T. Thus, returning this element will generate a warning unless we use the ! operator. This operator is safe to use here because the location we are returning stores an element that was passed to Push as type T.

The other public method to retrieve an element is the Pop method. This method also takes no parameters and returns a T. Part of what it does we have already implemented in the Peek method. In order to avoid duplicating code, we can retrieve the top element using the Peek method, and save it in a local variable so that we can return it when we are finished with this method (avoiding code duplication improves maintainability, as there are fewer places that might need to be modified later). Note that by using the Peek method, we are taking advantage of the fact that it checks whether the stack is empty; hence, there is no need to do that here. Before we can return the value we retrieved, we need to update Count to reflect the fact that we are removing one element.

While what we have described in the preceding paragraph is sufficient for correct functioning, there is one issue we need to address. Note that we have done nothing to the array location that stored the value we popped - it still stores that value. This fact does not impact correctness, however, because after we update the number of elements, we are no longer considering that location to be storing a stack element - its contents are irrelevant. Nevertheless, there is a performance issue here. If T is a reference type , then the reference stored in this location may refer to a large data structure that is no longer needed by the program. Because this array location still stores a reference to it, the garbage collector cannot tell that it is no longer in use, and consequently, it cannot reclaim the storage.

It therefore makes sense to remove what is stored in this array location. However, we run into a difficulty when we try to do this. We can’t simply assign null to this location because T might be a value type; hence, the compiler will not allow such an assignment. In order to address this problem, C# has the keyword, default, which can be used to get the default value for a given type. Thus, if T is a reference type, default(T) will give us null, but if T is a value type, it will give us the value whose binary representation is all 0s. In order to free up any memory we might no longer need, it therefore makes sense to assign default(T) to an array location after we are no longer using it.

Finally, we can implement a public Clear method. This method takes no parameters and returns nothing. One way to implement it would be to pop all of the elements, one by one, from the stack. However, this could be very inefficient if the stack contains a lot of elements. A better way is simply to change Count to 0; however, this way prevents the garbage collector from reclaiming storage we no longer need. In order to allow this storage to be reclaimed, we should also replace our array with a new array of the size we used when we initialized this field (note that this is more efficient than replacing every element with the default element of the appropriate type). Because we are no longer using the old array, the garbage collector can reclaim it, along with any otherwise unused data it might refer to.

Due to the similarities between this implementation and the StringBuilder implementation , the two data structures have similar performance characteristics. In fact, it is possible to show that any sequence of n operations on an initially empty Stack<T> is done in O(n) time - i.e., in time proportional to n.

Introduction to Queues

Stacks provide LIFO access to data, but sometimes we need first-in-first-out, or FIFO, access. Consider, for example, the computation of capital gains from stock sales. Typically an investor will buy shares of a stock commodity at various times and for different prices. When shares are sold, the amount of money received doesn’t depend on which shares of a given commodity are sold, as each share is worth the same amount at that time. Likewise, the unsold shares of that commodity each have the same value. However, for accounting purposes, it does matter. Specifically, the capital gain for that sale is defined to be the amount received from the sale minus the amount originally paid for those shares, assuming the shares sold are the oldest shares of that commodity owned by the investor.

Suppose now that we want to compute the capital gains from sales of stock. As shares are purchased, we need to record the purchase price of each share, along with the order in which the shares were purchased. As shares are sold, we need to retrieve the original purchase price of the oldest shares of each commodity sold. We therefore need first-in-first-out access to the purchase prices of the shares of each commodity owned. To keep this relatively simple, in what follows we will assume that we only need to keep track of one stock commodity.

A queue provides FIFO access to data items. Like a stack, a queue is a sequence of data items. However, a queue behaves more like a line of people at a ticket counter. Each person who enters the queue enters at the back, and the next person who is served is the person at the front. Thus, the people in the queue are served in FIFO order. Likewise, new data items are added to the back of a queue, and data items are retrieved from the front.

.NET provides both a non-generic queue of object?s (System.Collections.Queue ) and a generic queue (System.Collections.Generic.Queue<T> ). For simplicity, we will focus on the generic version. The non-generic version is the same, except that wherever the type parameter T is used in the generic version, object? is used in the non-generic version.

Like Stack<T>, Queue<T> has a public constructor that takes no parameters and constructs an empty queue, along with a public Count property that gets the number of elements in the queue (as an int). It also has the following public methods:

• An Enqueue method that takes a single parameter of type T and places it at the back of the queue.
• A Peek method that takes no parameters and returns the element (of type T) at the front of the queue without changing the queue’s contents. If the queue is empty, this method throws an InvalidOperationException.
• A Dequeue method, which takes no parameters and removes and returns the element at the front of the queue. If the queue is empty, this method throws an InvalidOperationException.

To implement a capital gain calculator using a Queue<T>, we first need to determine what type to make the elements. We will need to store the purchase price of each share we buy in the queue. An appropriate type for storing monetary amounts is the decimal type. Therefore, we will use an initially empty Queue<decimal>. Each time we buy shares, we enqueue the purchase price of each share onto the queue. When we sell shares, we need to compute the sum of the capital gains for all of the shares we sold. To get the capital gain for a single share, we dequeue its original purchase price from the queue, and subtract that purchase price from the selling price. Using the queue in this way ensures that we sell the shares in FIFO order.

Implementing a Queue

We will approach the implementation of a queue much like we did the implementation of a stack - we will use part of an array to store the elements, and create a larger array as needed. However, efficiently implementing a stack is easier because we only need to access one end of a stack, but we need to access both ends of a queue. Suppose, for example, that we were to use the initial part of the array, as we did for a stack; i.e.:

This implementation works well as long as we are only enqueuing elements — each element is placed at the back, much like pushing an element onto a stack. However, consider what happens when we dequeue an element. The element is easy to locate, as it must be at index 0, but in order to maintain the above picture, we would need to move all of the remaining elements one location to the left. This becomes less efficient as the number of elements in the queue increases.

One alternative is to modify the picture somewhat:

We can maintain this picture more efficiently, as there is now no need to move the elements when we dequeue an element. It does mean that we need to keep track of a bit more information, namely, the location of either the front or the back, in addition to the Count (note that we can compute the other end from these two values). But a more serious problem remains. Notice that as we enqueue and dequeue elements, the portion of the array that we are using works its way to the right. Eventually, the back element will be the last element in the array. However, this doesn’t mean that we are using the entire array, as the front can be anywhere in the array.

To solve this problem, when we need to enqueue an element but the back element is in the last array location, we place the next element at index 0. It is as if we are imagining the array as being circular, as the next location after the last is back at the beginning. The following picture gives two views of such a “circular array” implementation:

With this implementation, we only need to construct a larger array if we completely fill the current array, and unless we need to do this, we don’t need to move elements around. We need the following class members in order to keep track of everything:

• a private T?[ ] field in which to store the elements;
• a public int Count property; and
• a private int field giving the index of the element at the front of the queue (if the queue is empty, this can be any valid index).

Let us now consider how we would implement Enqueue. We first need to determine whether the array is full by comparing the Count with the size of the array. If it is full, we need to construct a new array of twice the size, as we did for both the StringBuilder implementation and the stack implementation . However, we can’t simply copy the entire array to the beginning of the new array, as we did for these other two implementations. To do so would leave a gap in the middle of the queue, as shown in the following illustration:

While there are several ways of copying the elements correctly, it may be helpful to copy in such a way that the index of the front of the queue remains unchanged; i.e., we copy as follows:

In order to copy the elements like this, we can use the static method, Array.Copy . This method takes the following parameters:

• The array to copy from.
• An int giving the index of the first element to copy.
• The array to copy to.
• An int giving the index in which to place the first element.
• An int giving the number of elements to copy.

Just figuring out how to fill in these parameters takes some work. Let’s first consider the part that begins with the front of the queue. The index of the first element to copy is the index of the front of the queue, which we have in a private field. We want to place this element at the same index in the new array. In order to compute the number of elements to copy, first observe that we know the number of elements in the original array (we can use either the Count property or the length of this array, as these values are equal whenever we need a larger array). To get the number of elements we want to copy, we can subtract from this value the number of elements we are not copying — i.e., the number of elements preceding the index of the front of the queue. The number of elements preceding any index i is always i; hence, by subtracting the index of the front of the queue from the Count, we get the number of elements we are copying by this call.

Now let’s see if we can figure out the parameters for the other call. The first element we want to copy is at index 0. We want to place it immediately following the elements we have already copied. Because the last of these elements occupies the last index of the original array, whose size is currently the same as the Count, the next index is just the Count. The number of elements we want to copy, as we have already argued, is the index of the front of the queue.

Once we have the elements copied to the new array, the hardest part is done. After we do this, we just need to copy the reference to the new array into the array field.

Once we have ensured that there is room in the array to add a new element, we can complete the Enqueue method. We need to place the element at the back of the queue. We can obtain the proper location by adding the Count to the index of the front of the queue, provided this value is not beyond the end of the array. If it is, then we need to wrap it around by subtracting the length of the array. We can then increment the number of elements, and we are (finally) done.

The Peek method is straightforward — after verifying that the queue is nonempty, we simply return the element at the front. The Dequeue method isn’t much more difficult. We can obtain the element we want to return using the Peek method. We then need to place the default element of type T at the front, and update both the index of the front of the queue and the Count before returning the element we obtained ealier from Peek. The only slightly tricky part is making sure that when we update the index of the front of the queue, we don’t go outside of the array. If we do, we need to wrap it back around to 0.

Introduction to Linked Lists

To build a linked list, we first need to define a simple class, which we will call LinkedListCell<T>. Instances of this class will be the individual building blocks that we will chain together to form linked lists. T will be the type of the data item we will store in each cell - i.e., the type of the data items that we will store in the linked list.

A LinkedListCell<T> will contain two public properties, which can each be implemented using the default implementation:

• The Data property gets or sets the data item (of type T) stored in the cell.
• The Next property gets or sets the next LinkedListCell<T>? in the linked list. If there is no next cell, it gets null.

Because this is a class, it is a reference type ; hence, the Next property will store a reference to another LinkedListCell<T>.

The only other member of this class is a public constructor. Because we don’t want to make Data nullable unless the user code specifies a nullable type for T, we need to make sure it is initialized to an appropriate value. For this purpose, we use a public constructor that takes the following parameters:

• The initial Data value (of type T).
• The next cell in the list (of type LinkedListCell<T>?).

It simply sets the values of the two properties to the given parameters.

Although the LinkedListCell<T> class is simple, we can use its Next property to chain together long sequences of its instances:

In the above figure, p is a LinkedListCell<string> variable. Each box in the figure represents an instance of LinkedListCell<string>. The boxes are each divided into two regions to indicate the two public properties for each cell. Because string is a reference type, we have shown each Data property as a reference to a string. The rightmost arrow that is bent downward is used to represent null. The entire sequence of LinkedListCell<string>s is called a linked list. Given this linked list:

• p.Data is “Now”;
• p.Next.Data is “is”;
• p.Next.Next.Data is “the”;
• p.Next.Next.Next.Data is “time”; and
• p.Next.Next.Next.Next is null (if we try to get its Data property, we will get a NullReferenceException).

Suppose we want to insert the string “Notice:” at the beginning of this linked list. We use the LinkedListCell<T> constructor to initialize a new cell:

LinkedListCell<string> cell = new("Notice", p);

This yields the following:

This is what we want, unless we want p to refer to the beginning of the linked list. We can take care of this by copying the value of cell to p:

p = cell;

This yields the following (we are not showing cell because we are no longer interested in it, but it still refers to the same cell):

We can also undo the above statement by copying into p the reference in the Next property of the cell to which p refers:

p = p.Next;

(If this statement occurs in a context in which the compiler cannot determine that p is not null, an ! will need to be inserted prior to .Next.) This yields the following:

This has the effect of removing “Notice:” from the linked list to which p refers. Though we haven’t shown it, cell still refers to the cell containing “Notice:”; hence, we still have access to the linked list beginning with this cell. However, if the program had no references remaining to this cell, we would have no way to retrieve it, and it would be available for garbage collection. This illustrates how we must take care not to lose a part of a linked list (unless we are finished with it) when we are manipulating it.

With a little more work, cells can be inserted into or removed from arbitrary locations in a linked list. We will discuss how to do this in subsequent sections. For now let us simply observe that linked lists do not always continue until they reach a null - they can contain cycles, as follows:

This is occasionally what we want, but more often, this is a programming error that leads to an infinite loop.

Implementing Stacks and Queues with Linked Lists

Because linked lists store data elements in linear sequences, they can be used to give alternative implementations of stacks and queues. One advantage to using linked lists is that we don’t have to worry about filling up something like an array - we can just keep allocating cells as long as we need to (unless we run out of memory).

Implementing a stack using a linked list is particularly easy because all accesses to a stack are at the top. One end of a linked list, the beginning, is always directly accessible. We should therefore arrange the elements so that the top element of the stack is at the beginning of the linked list, and the bottom element of the stack is at the end of the linked list. We can represent an empty stack with null.

We therefore need a private LinkedListCell<T>? field to implement a generic stack Stack<T> using a linked list. This field will refer to the cell containing the data item at the top of the stack. If the stack is empty, this field will be null; hence, this field should be null initially. A public Count property will be used to keep track of the number of elements in the stack.

The public methods Push, Peek, and Pop are then fairly straightforward to implement. For Push we need to add the given element to a new cell at the beginning of the linked list, as shown in the previous section , and update the Count. To implement Peek, if the stack is nonempty, we simply return the Data property of the cell at the beginning of the linked list; otherwise, we throw an InvalidOperationException. Note that we can determine whether the stack is empty by examining either the LinkedListCell<T>? field or the Count property; however, examining the LinkedListCell<T>? field allows the compiler to determine that the Data property of the first cell can be accessed without throwing a NullReferenceException.

To implement Pop:

1. Using Peek, obtain the element to be returned.
2. Remove the first element from the linked list as shown in the previous section .
3. Update the Count.
4. Return the retrieved value.

Note that the call to Peek in step 1 ensures that the stack is nonempty before we remove the first element; however, the compiler won’t be able to determine this.

Implementing a queue is a little more involved because we need to operate at both ends of the linked list. For efficiency, we should keep a reference to the last cell in the linked list, as this will allow us to access both ends of the linked list directly. We will therefore have the following:

We now need to decide which end to make the front of the queue. As we saw in the previous section , both inserting and removing can be done efficiently at the beginning of a linked list. Likewise, it is easy to insert an element at the end if we have a reference to the last cell. Suppose, for example, that last refers to the last cell in a linked list, and that cell refers to a LinkedListCell<T> that we want to insert at the end. Suppose further that the linked list is not empty (that will be a special case that we’ll need to handle). Thus, we have the following:

To insert this cell at the end of the linked list, we just need to copy the reference in cell to the Next property of the cell to which last refers:

last.Next = cell;

On the other hand, removing the last cell is problematic, even if we have a reference to it. The problem is that in order to remove it from the linked list, we need to change the Next property of the preceding cell. Unfortunately, the only way to obtain that cell is to start at the beginning of the list and work our way through it. If the linked list is long, this could be quite inefficient.

Because we need to remove elements from the front of a queue, but not from the back, we conclude that it will work best to make the beginning of the linked list the front of the queue. We therefore need the following private fields to implement a generic queue Queue<T>:

• A LinkedListCell<T>? giving the element at the front of the queue. This will be the beginning of the linked list of queue elements.
• A LinkedListCell<T>? giving the element at the back of the queue. This will be the last cell in the linked list of queue elements.

As we mentioned earlier, adding an element to an empty queue is a special case that we will need to handle separately. For this reason, it doesn’t matter what values the two LinkedListCell<T>? fields contain when the queue is empty - we can always detect when the queue is empty by checking the Count. The initialization of the two LinkedListCell<T>? fields is therefore unimportant. It is easiest to just leave them null.

Let us now consider the implementation of the Enqueue method. We need to consider two cases. We’ll first consider the case in which the queue is empty. In this case, we need to build the following linked list:

We therefore need to:

1. Construct a new LinkedListCell<T> containing the element we want to enqueue and no next cell.
2. Assign it to the field denoting the front of the queue.
3. Assign it to the field denoting the back of the queue.
4. Update the Count.

If the queue is nonempty, the only step that changes is Step 2. Because the queue is nonempty, we don’t want to make the new cell the front of the queue; instead, we need to insert it at the end of the linked list, as outlined above.

The implementations of the Peek and Dequeue methods are essentially the same as the implementations of the Peek and Pop methods, respectively, for a stack.

The implementations described in this section are simpler than the implementations using arrays, mainly due to the fact that we don’t need to rebuild the structure when we fill up the space available. While these implementations are also pretty efficient, it turns out that the array-based implementations tend to out-perform the linked-list-based implementations. This might be counterintuitive at first because rebuilding the structures when the array is filled is expensive. However, due to the fact that we double the size of the array each time we need a new one, this rebuilding is done so rarely in practice that it ends up having minimal impact on performance. Due to hardware and low-level software issues, the overhead involved in using arrays usually ends up being less.

Finding Prime Numbers

An integer greater than $ 1 $ is said to be prime if it is not divisible by any positive integers other than itself and $ 1 $. Thus, $ 2 $, $ 3 $, and $ 5 $ are prime, but not $ 1 $ (it is not greater than $ 1 $) or $ 4 $ (it is divisible by $ 2 $). Because every integer is divisible by itself and $ 1 $, we will call any other positive factors nontrivial factors; thus, a prime number is an integer greater than $ 1 $ that has no nontrivial factors. The study of prime numbers dates back to at least the third century BC. One of the earliest known algorithms finds all prime numbers less than a given integer $ n $. This algorithm is known as the Sieve of Eratosthenes, and is attributed to the Greek mathematician Eratosthenes of Cyrene (c. 276 BC - c. 194 BC).

The most basic version of this algorithm operates as follows:

1. Place all integers greater than $ 1 $ and less than $ n $ in order in a list.
2. For each element $ k $ in the list, remove all subsequent elements that are divisible by $ k $.
3. The remaining values are the prime numbers less than $ n $.

For example, suppose $ n = 20 $. We then place the integers from $ 2 $ to $ 19 $ in a list: $$ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 14\ 15\ 16\ 17\ 18\ 19 $$ We then remove all numbers following $ 2 $ that are divisible by $ 2 $: $$ \require{cancel} 2\ 3\ \cancel{4}\ 5\ \cancel{6}\ 7\ \cancel{8}\ 9\ \cancel{10}\ 11\ \cancel{12}\ 13\ \cancel{14}\ 15\ \cancel{16}\ 17\ \cancel{18}\ 19 $$ We then remove all numbers following $ 3 $ that are divisible by $ 3 $: $$ 2\ 3\ \cancel{4}\ 5\ \cancel{6}\ 7\ \cancel{8}\ \cancel{9}\ \cancel{10}\ 11\ \cancel{12}\ 13\ \cancel{14}\ \cancel{15}\ \cancel{16}\ 17\ \cancel{18}\ 19 $$ The algorithm continues, but none of the succeeding iterations finds any values to remove. Therefore, $ 2, 3, 5, 7, 11, 13, 17 $, and $ 19 $ are the prime numbers less than $ 20 $.

To see why this algorithm gives us exactly the prime numbers less than $ n $, first note that because we only remove a number when we find a nontrivial factor, we only remove non-primes from the list. What may be a little less obvious is that we remove all non-primes from the list. To see this, suppose $ m $ is a non-prime less than $ n $, and let $ a $ be its smallest nontrivial factor. Then $ a $ must be prime because any nontrivial factor of $ a $ would be less than $ a $ and would also divide $ m $. $ a $ therefore will not be removed from the list. When $ k = a $ in Step 2, $ m $ will be removed.

There is actually a good reason why the first two iterations in the above example removed all of the non-primes — once the algorithm reaches a divisor $ k $ such that $ k^2 \geq n $ (in this example, $ 5^2 = 25 \geq 20 $), all of the non-primes will have been removed. To see why this is true, let $ m $ and $ a $ be as above. We can then write $$ m = ab $$ where $ a \leq b $, and $ m $ is removed from the list when $ k = a $. We can then multiply both sides of the above equation by $ a/b $, yielding: $$ \frac{am}{b} = a^2. $$ Finally, because $ a \leq b $, $ a/b \leq 1 $. Therefore, $$ m \geq a^2. $$ We conclude that if $ m $ is a non-prime greater than $ 1 $, it is removed when the algorithm reaches some value $ k $ with $ k^2 < n $. We can therefore optimize the algorithm by stopping when $ k^2 \geq n $.

We can implement this algorithm using a linked list. A linked list is an appropriate data structure for this algorithm because once the list is built, all of the processing involves iterating through it from beginning to end — the same direction the links go.

To implement Step 1, it is easier to build the list from back to front, as we don’t need to maintain a separate reference to the end of the list. This step then consists of a loop that iterates from $ n - 1 $ down to $ 2 $, with each iteration adding to the front of the list a cell containing the loop index.

In order to be able to implement Step 2, we will need to know how to remove a cell from a linked list. Suppose, for example, that we want to remove the cell referring to “the” from the following linked list:

To remove it, we need the cell that precedes it to be followed by the cell that follows it:

In order to change that reference, we need a reference to the cell that precedes the cell we want to remove:

We can then remove the cell following the cell referenced by q as follows:

q.Next = q.Next.Next;

Now that we know how to remove a cell from a linked list, let’s consider Step 2 of the algorithm. For one value of $ k $, we need to remove all subsequent values that are divisible by $ k $. In terms of the linked list, we need to start this process with the cell containing $ k $. For example, consider the second iteration from the example above — i.e., when $ k = 3 $:

We need to iterate p through the linked list, checking the next cell on each iteration to see whether its contents are divisible by $ k $. We can check for divisibility by $ k $ using the remainder operator — i.e., $ k $ divides $ m $ if $ m \mathbin{\texttt{%}} k $ is 0. Thus, the first iteration would see if $ 3 $ divides $ 5 $. It doesn’t, so we advance p to the next cell (containing $ 5 $). We then see if $ 3 $ divides $ 7 $. Again it doesn’t, so we advance p to the next cell (containing $ 7 $). At this point, $ 3 $ divides $ 9 $, so we remove the cell containing $ 9 $ as shown above. This gives us the following linked list:

Note that we have not yet advanced p, and indeed we don’t want to, as $ 11 $ is the next value we want to check. Thus, on each iteration, if $ k $ divides the value in the cell following p, we remove that cell; otherwise, we advance p to that cell. We iterate this loop as long as there is a cell following p.

The loop described above represents a single iteration of the loop described for Step 2. Thus, for Step 2, we need to iterate a variable through the list, performing the above on each iteration. We stop when we either have run off the end of the list or have reached a value of $ k $ such that $ k^2 \geq n $. Note that at the end of each iteration, we want to advance to the next cell.

The Dictionary<TKey, TValue> Class

In this section, we will discuss the use of the Dictionary<TKey, TValue> class, which implements a dictionary. In the next section , we will discuss how this data structure can be implemented using a linked list. In subsequent sections, we will consider alternative implementations.

Note that the Dictionary<TKey, TValue> type has two type parameters, TKey and TValue. TKey is the type of the keys, and TValue is the type of the values (i.e., the data elements associated with the keys). Keys must always be non-null — any attempt to use a null key will result in an ArgumentNullException. A Dictionary<TKey, TValue>’s most basic public methods are:

• void Add(TKey key, TValue value) : Associates the given value with the given key. If there is already a value associated with the given key, it throws an ArgumentException.
• bool Remove(TKey key) : Removes the given key and its associated value from the dictionary, and returns whether the key was found.
• bool TryGetValue(TKey key, out TValue? value) : Returns whether the given key is in the dictionary. If so, the out parameter value is assigned the value associated with key; otherwise, value is assigned the default value for its type.

The above methods can be used for building and updating a Dictionary, as well as for looking up values by their keys. It is also possible to do updates and lookups using indexing. Specifically, a key may be used as an index in a Dictionary, as if the Dictionary were an array. For example, suppose that dictionary is a Dictionary<TKey, TValue>, k is a TKey, and v is a TValue. We can then do the following:

dictionary[k] = v;

This will associate the value v with the key k, as the Add method does; however, its behavior is slightly different if k already has a value associated with it. Whereas the Add method would throw an exception in this case, using the indexer will simply replace the value previously associated with k by the new value v. Thus, we use the Add method when we expect the key to be a new key for the dictionary, but we use the indexer when we want to associate the value with the key, regardless of whether the key is already in the dictionary.

Likewise, we can use the indexer to look up a key:

v = dictionary[k];

Again, the behavior is similar to the TryGetValue method, but slightly different, as there is no bool in the above statement. When using the indexer, if the key is not in the dictionary, it will throw a KeyNotFoundException. Thus, we use the indexer when we expect the key to be in the dictionary, but we use the TryGetValue method when we don’t know if the key is in the dictionary.

Implementing a Dictionary with a Linked List

One way of implementing a dictionary is to store all the keys and values in a linked list. We want to do this in such a way that a key is stored together with its associated value. To facilitate this, .NET provides a structure KeyValuePair<TKey, TValue> in the System.Collections.Generic namespace. This structure is used simply for storing a key and a value. The type parameter TKey is used to define the type of the keys, and the other type parameter TValue is used to define the type of the values. It has two public properties:

• Key , which gets the key stored; and
• Value , which gets the value stored.

Note that neither of these properties can be set; i.e., the structure is immutable. In order to set the key and value, we need to construct a new instance using its 2-parameter constructor . The first parameter to this constructor is the key, and the second is the value.

Now that we have a way of storing keys and values together, we can implement a Dictionary<TKey, TValue> with a linked list comprised of instances of LinkedListCell<KeyValuePair<TKey, TValue>>. Thus, each cell of the list stores as its Data a KeyValuePair<TKey, TValue> containing a key and its associated value. To add a key and a value, we first need to search the list for a cell containing that key. If we find such a cell, we either replace the KeyValuePair in that cell with a new KeyValuePair containing the given key and value, or we throw an exception, depending on the specific behavior required. If we don’t find such a cell, we insert a new cell containing the given key and value. Because it doesn’t matter where we insert it, we might as well insert it at the beginning of the list, as that is the easiest way. We can remove a key using techniques described in “Finding Prime Numbers” .

The main disadvantage to this approach is that searching for a key is expensive. For example, to search for a key that is not in the dictionary, we need to examine every key in the dictionary. We would like to improve on this performance.

One way of improving the performance of searching is to store the keys in increasing order. Then as we search, if we see a key that is larger than the key we are looking for, we can stop. However, recall that keys can be of any type. For some types of keys, “increasing order” and “larger than” make no sense.

C# does provide a way to restrict the types that can be passed as type parameters to generic types. Specifically, we can restrict the type TKey by writing the class statement as follows:

public class Dictionary<TKey, TValue> where TKey : notnull, IComparable<TKey>   

The where clause in this statement constrains TKey in two ways:

• notnull constrains it to be a non-nullable type. The compiler doesn’t actually enforce this constraint, but will give a warning if a nullable type is used for TKey.

• IComparable<TKey> constrains it to be a subtype of IComparable<TKey> . Each subtype of IComparable<TKey> contains a method public int CompareTo(TKey? x) . If a and b are of type TKey, then a.CompareTo(b) returns:

  • A negative number if a is considered to be less than b;
  • 0 if a is considered to be equal to b; or
  • A positive number if a is considered to be greater than b or if b is null.

We can therefore use this CompareTo method to keep the list in increasing order.

Note that by constraining the key type in this way, we are making the Dictionary<TKey, TValue> less general, as we may sometimes want to use a key type that can’t be ordered. On the other hand, there are times when not only do we have a key type that can be ordered, but also we need to access the keys in increasing order (for example, to print an ordered list of keys with their values). In such cases, what we actually need is an ordered dictionary, which both restricts the keys in this way and provides a means of accessing them in increasing order. While we won’t consider the full implementation of an ordered dictionary here, it is worth considering how we can improve performance by keeping the keys in increasing order.

Let’s now consider how to add a key and value to a linked list storing keys in increasing order. We first need to find where the key belongs in the ordering. Specifically, the cell whose Next property needs to be changed (assuming the key is not already in the list) is the one that must precede the new cell. We therefore need to find the last cell whose key is less than the key we need to add. Note also that when we are removing a key, the cell whose Next property needs to be changed is the last cell whose key is less than the key we are removing. Furthermore, if we are looking up a key, we need to look in the cell that follows the last cell whose key is less than the key we are looking for. This suggests that we should provide a private method to find the last cell whose key is less than a given key, provided such a cell exists.

Before we can write such a method, however, we first need to address a problem that occurs if we are trying to add, remove, or look up a key that is smaller than all other keys in the list. In this case, there are no cells containing keys smaller than the given key.

We can avoid needing a special case to deal with this problem if we include a special header cell at the beginning of our linked list. This cell will not contain any meaningful data, but it will always be present. If we consider that its key is less than any other key (though we will never actually examine its key), then there will always be at least one key less than any given key. We can obtain this header cell by initializing the linked list to contain a new cell containing the default key-value pair, rather than to null. Note that because the linked list will always contain at least the header cell, the reference to it should not be nullable.

A method to find the last cell containing a key less than a given key is now straightforward. We initialize a variable to the first cell (i.e., the header cell), and set up a loop that iterates as long as the next cell is non-null and contains a key less than the given key. Each iteration advances to the next cell. When the loop terminates, we return the cell we have reached.

To look up a key, we use the above method to find the last cell containing a key less than the key we are looking for. If the next cell is non-null and contains the key we are looking for, then we have found it; otherwise, it cannot be in the list. To add a key and value, we first need to look up the key in the same way. If we don’t find it, we insert a new cell containing this key and value following the last cell containing a key less than this key. To remove a key, we proceed in a similar way, but if we find the key, we remove this cell from the list.

While keeping the keys in increasing order improves the performance of many searches, the overall performance is still unsatisfactory for even data sets of moderate size. In subsequent sections, we will explore ways of improving this performance using various data structures.

Implementing a Dictionary with an Array-Like Structure

In the previous section , we discussed how linked lists could be used to implement a dictionary. An alternative to a linked list would be an array. A couple of other alternatives are the non-generic System.Collections.ArrayList or the generic System.Collections.Generic.List<T> . These classes are similar to singly-dimensioned arrays, but they can grow as needed. In this respect, they are like a StringBuilder , but instead of storing chars, an ArrayList stores object?s and a List<T> stores instances of the type parameter T. Elements can be retrieved from instances of these classes using indexing, just like retrieving an element from an array.

Assuming we restrict the keys to be non-nullable sub-types of IComparable<TKey>, where TKey is the key type, we can store the keys in order in any of these data structures. We can then search for a key in the same way as we described for a linked list. However, such a search can be expensive - to search for a key that is larger than any key in the dictionary, we need to examine all of the keys. We say that the performance of this sequential search is in $ O(n) $, where $ n $ is the number of keys in the dictionary. This means that as $ n $ grows, the time required for the search is at worst proportional to $ n $.

We can improve this performance dramatically for an array or array-like structure such as an ArrayList or a List<T> using a technique called binary search (there isn’t much we can do to improve the performance of searching a linked list, as its structure restricts us to traversing it sequentially). The idea is similar to what humans do when looking for something in an ordered list such as a dictionary or an index of a book. Rather than looking sequentially through the sequence, we first look in the middle and narrow our search space depending on how what we are looking for compares with what we are looking at. For example, if we are looking for “Les Miserables”, we first look in the middle of the sequence, where we might see “Othello”. Because “Les Miserables” is alphabetically less than “Othello”, we can narrow the search space to those titles less than “Othello”. In the middle of this search space, we might find the title, “Great Expectations”. Because “Les Miserables” is alphabetically greater than “Great Expectations”, we narrow the search space to those titles greater than “Great Expectations” and less than “Othello”. We continue narrowing in this way until either we find “Les Miserables” or the search space becomes empty, implying that the data set does not contain this title.

In a binary search, each lookup is as nearly as possible in the center of the search space. This means that each time we look at an entry, we either find what we are looking for, or we decrease the size of the search space to at most half its previous size. For large data sets the search space therefore shrinks rapidly. For example, if we start with 1,000,000 elements and repeatedly reduce the search space to at most half its previous size, after 20 such reductions, we are left with nothing. Likewise, if we start with 1,000,000,000 elements, 30 such reductions in size lead to an empty search space.

To implement this algorithm, we need to keep track of the search space. We will use two int variables, start and end. start will keep track of the first index in the search space, while end will keep track of the first index past the search space, as follows:

The way we have defined end may seem unnatural at first, but because it simplifies various calculations, it is a common way of describing a search space. For example, the number of elements in such a search space is simply the difference between end and start, and to describe an entire array, we can initialize start to 0 and end to the array’s length.

We then need a loop to iterate as long as this search space is nonempty (we can return from inside this loop if we find what we are looking for). On each iteration, we need to find the midpoint of the search space. This midpoint is simply the average of start and end - i.e., their sum divided by 2. We need to be a bit careful here because we are doing integer division, which may involve truncation. As a result, we may not get exactly the average. In any case, we need to ensure that the index we compute is within the search space - otherwise, we may not reduce the search space, and an infinite loop will result. Because the search space is nonempty, start < end; hence, the true average is strictly between start and end. If this average is not an integer, the result will be rounded down to the next smaller integer. Because start is an integer, this result will be no less than start, but less than end; hence it will be in the search space.

Once we have computed this midpoint, we need to compare the key of the element at that location with the key we are looking for. Recall that we use the CompareTo method to do this comparison. Note that for large key types, the CompareTo method can be expensive. For this reason, it is best to call the CompareTo method only once for a given pair of keys, and if necessary, save the result it returns in order to make more than one comparison between this result and 0.

Thus, once we have obtained the result of the CompareTo method, we need to determine which of the three cases we have. If the keys are equal, we should be able to return. If the key we are looking for is less than the key at the midpoint, we need to adjust end. Otherwise, we need to adjust start. We are then ready for the next iteration of the loop.

If the loop finishes without returning, then the search space is empty; hence, the key we are looking for is not in the data set. However, start will end up at the point at which this key could be inserted; hence, the binary search can be used for both lookups and insertions.

Binary search is a very efficient way to search an ordered array-like structure. In particular, it always makes no more than $ O(\log n) $ comparisons, where $ n $ is the number of elements in the data set. The $ \log $ function grows very slowly - much more slowly than $ n $.

Introduction to Trees

A tree is a mathematical structure having a hierarchical nature. A tree may be empty, or it may consist of:

• a root, and
• zero or more children, each of which is also a tree.

Consider, for example, a folder (or directory) in a Windows file system. This folder and all its sub-folders form a tree — the root of the tree is the folder itself, and its children are the folders directly contained within it. Because a folder (with its sub-folders) forms a tree, each of the sub-folders directly contained within the folder are also trees. In this example, there are no empty trees — an empty folder is a nonempty tree containing a root but no children.

We have at least a couple of ways of presenting a tree graphically. One way is as done within Windows Explorer:

Here, children are shown in a vertically-aligned list, indented under the root. An alternative depiction is as follows:

Here, children are shown by drawing lines to them downward from the root.

Other examples of trees include various kinds of search spaces. For example, for a chess-playing program, the search for a move can be performed on a game tree whose root is a board position and whose children are the game trees formed from each board position reachable from the root position by a single move. Also, in the sections that follow, we will consider various data structures that form trees.

.NET provides access to the folders in a file system tree via the DirectoryInfo class, found in the System.IO namespace. This class has a constructor that takes as its only parameter a string giving the path to a folder (i.e., a directory) and constructs a DirectoryInfo describing that folder. We can obtain such a string from the user using a FolderBrowserDialog . This class is similar to a file dialog and can be added to a form in the Design window in the same way. If uxFolderBrowser is a FolderBrowserDialog, we can use it to obtain a DirectoryInfo for a user-selected folder as follows:

if (uxFolderBrowser.ShowDialog() == DialogResult.OK)
{
    DirectoryInfo folder = new(uxFolderBrowser.SelectedPath);
    
	// Process the folder
}

Various properties of a DirectoryInfo give information about the folder; for example:

• Name gets the name of the folder as a string.
• FullName gets the full path of the folder as a string.
• Parent gets the parent folder as a DirectoryInfo?. If the current folder is the root of its file system, this property is null.

In addition, its GetDirectories method takes no parameters and returns a DirectoryInfo[ ] whose elements describe the contained folders (i.e., the elements of the array are the children of the folder). For example, if d refers to a DirectoryInfo for the folder Ksu.Cis300.HelloWorld from the figures above, then d.GetDirectories() would return a 3-element array whose elements describe the folders bin, obj, and Properties. The following method illustrates how we can write the names of the folders contained within a given folder to a StreamWriter :

/// <summary>
/// Writes the names of the directories contained in the given directory 
/// (excluding their sub-directories) to the given StreamWriter.
/// </summary>
/// <param name="dir">The directory whose contained directories are to
/// be written.</param>
/// <param name="output">The output stream to write to.</param>
private void WriteSubDirectories(DirectoryInfo dir, StreamWriter output)
{
    foreach (DirectoryInfo d in dir.GetDirectories())
    {
        output.WriteLine(d.Name);
    }
}

For a more interesting problem, suppose we want to write to a StreamWriter the structure of an entire folder, as follows:

Ksu.Cis300.HelloWorld
  bin
    Debug
    Release
  obj
    Debug
      TempPE
  Properties

We can break this task into the following steps:

1. Write the name of the folder:

   Ksu.Cis300.HelloWorld

2. Write the structure of each child folder, indented one level (i.e., two spaces):

   • First child:

       bin
         Debug
         Release
     

   • Second child:

       obj
         Debug
           TempPE
     

   • Third child:

       Properties
     

Note that writing the structure of a child folder is an instance of the original problem that we want to solve - i.e., writing the structure of a folder. The only difference is that the folders are different and the amount of indentation is different. We can solve such a problem using a technique called recursion. Recursion involves a method calling itself. Because of the recursive nature of a tree (i.e., each child of a tree is also a tree), recursion is commonly used in processing trees.

In order to use recursion, we first must define precisely what we want our method to accomplish, wherever it might be called. For this problem, we want to write to a given StreamWriter a list of all the folders contained within a given folder, including the given folder itself and all sub-folders in the entire tree, where each folder is indented two spaces beyond its parent’s indentation. Furthermore, the entire tree below a given folder (i.e., excluding the folder itself) should be listed below that folder, but before any folders that are outside that folder. In order to write such a method, we need three parameters:

• a DirectoryInfo giving the root folder;
• a StreamWriter where the output is to be written; and
• an int giving the level of indentation for the root folder, where each level of indentation is two spaces.

Because the root folder must be written first, we begin there. We first must write two blanks for every level of indentation, then write the name of the root folder:

/// <summary>
/// Writes the directory structure for the given root directory to the
/// given StreamWriter, indenting all entries to the given indentation
/// level (incomplete). 
/// </summary>
/// <param name="root">The root directory.</param>
/// <param name="output">The output stream to which to write</param>
/// <param name="level">The current indentation level.</param>
private void WriteTree(DirectoryInfo root, StreamWriter output, int level)
{
    for (int i = 0; i < level; i++)
    {
        output.Write("  ");
    }
    output.WriteLine(root.Name);

    // We now need to write the sub-directories . . .

}

We can get the children using root.GetDirectories(). Each of the elements of the array this method returns will be a DirectoryInfo whose structure we want to write. Looking back at how we described what we want the WriteTree method to accomplish, we see that it is exactly what we want to do for each child. We can therefore make a recursive call for each child, specifying that the indentation level should be one deeper than the level for root:

/// <summary>
/// Writes the directory structure for the given root directory to the
/// given StreamWriter, indenting all entries to the given indentation
/// level (incomplete). 
/// </summary>
/// <param name="root">The root directory.</param>
/// <param name="output">The output stream to which to write</param>
/// <param name="level">The current indentation level.</param>
private void WriteTree(DirectoryInfo root, StreamWriter output, int level)
{
    for (int i = 0; i < level; i++)
    {
        output.Write("  ");
    }
    output.WriteLine(root.Name);
    foreach (DirectoryInfo d in root.GetDirectories())
    {
        WriteTree(d, output, level + 1);
    }
}

This method accomplishes the desired task, provided the directory tree does not contain symbolic links or anything similar that might be represented using a DirectoryInfo, but is not an actual folder. While it is possible to detect these and avoid following them, we will not consider that here.

There is something that may seem mysterious about what we have done. In order to convince ourselves that this method is written correctly, we need to know that the recursive calls work correctly; however, the recursive calls are to the same method. Our reasoning therefore seems circular. However, we are actually using a mathematical principle from the discipline of formally proving software correctness: in order to prove that a recursive method meets its specification we may assume that any recursive calls meet that same specification, provided that these recursive calls are all on smaller problem instances.

The restriction that recursive calls are on smaller problem instances is what avoids circular reasoning regarding recursion. We associate with each problem instance a nonnegative integer describing its size. For a problem involving a tree, this size is typically the number of nodes in the tree, where a node is a root of some subtree. Because every node in a child is also in the tree containing the child, but the root of the containing tree is not in the child, a child is always smaller, provided the tree is finite. (For directory trees, if the underlying file system is a Windows system, the tree will be finite; however if it is a non-Windows system, the trees may appear to Windows as being infinite - the above method actually will not work in such cases.)

The validity of this strategy is based on the fact that for any method, the following three statements cannot be simultaneously true:

1. All of the method’s recursive calls (if there are any) are on inputs of smaller size, where the size is defined to be a nonnegative integer.
2. When the method is given any input, if all of the method’s recursive calls produce correct results, then the method itself produces a correct result.
3. There is at least one input for which the method does not produce a correct result.

Thus, if we can ensure that Statements 1 and 2 are true, then Statement 3 must be false; i.e., the method will be correct. To ensure Statement 2, we only need to concern ourselves with cases in which all recursive calls produce correct results; hence, we simply assume that each recursive call produces correct results.

To see why the three statements above cannot be simultaneously true, let’s first suppose Statement 3 is true. Let S be the set of all inputs for which the method does not produce a correct result. Then because Statement 3 is true, this set is nonempty. Because each input in S has a nonnegative integer size, there is an input I in S with smallest size. Now suppose Statement 1 is true. Then when the method is run on input I, each of the recursive calls is given an input smaller than I; hence, because I is a smallest input in S, none of these inputs is in S. Therefore, each of the recursive calls produces a correct result. We therefore have an input, I on which all of the method’s recursive calls produce correct results, but the method itself does not produce a correct result. Statement 2 is therefore false.

Once we understand this strategy, recursion is as easy to use as calling a method written by someone else. In fact, we should treat recursive calls in exactly the same way — we need to understand what the recursive call is supposed to accomplish, but not necessarily how it accomplishes it. Furthermore, because processing trees typically involves solving the same problem for multiple nodes in the tree, recursion is the natural technique to use.

A recursive method for processing a tree will break down into cases, each fitting into one of the following categories:

• A base case is a case that is simple enough that a recursive call is not needed. Empty trees are always base cases, and sometimes other trees are as well.
• A recursive case is a case that requires one or more recursive calls to handle it.

A recursive method will always contain cases of both these types. If there were no base cases, the recursion would never terminate. If there were no recursive cases, the method wouldn’t be recursive. Most recursive methods are, in fact, structured as an if-statement, with some cases being base cases and some cases being recursive cases. However, for some recursive methods, such as WriteTree above, the base cases aren’t as obvious. Note that in that method, the recursive call appears in a loop; hence, if the loop doesn’t iterate (because the array returned is empty), no recursive calls are made. Furthermore, if the directory tree is finite, there must be some sub-directories that have no children. When the GetDirectories method is called for such a directory, it returns an empty array. These directories are therefore the base cases.

The WriteTree method above is actually an example of processing an entire tree using a preorder traversal. In a preorder traversal, the root of the tree is processed first, then each of the children is processed using a recursive call. This results in each node’s being processed prior to any node contained in any of its children. For the WriteTree method, this means that the name of any folder is written before any folders contained anywhere within it.

When debugging a recursive method, we should continue to think about it in the same way — that is, assume that all recursive calls work correctly. In order to isolate an error, we need to find an instance that causes an error, but whose recursive calls all work correctly. It will almost always be possible to find such a case that is small — in fact, small cases tend to be the most likely ones to fit this description. When debugging, it therefore makes sense to start with the smallest cases, and slowly increase their size until one is found that causes an error. When using the debugger to step through code, first delete all breakpoints from this method, then use Step Over to step over the recursive calls. If a recursive call doesn’t work correctly, you have found a smaller instance that causes an error — work on that instance instead. Otherwise, you can focus on the top-level code for the instance you are debugging. This is much easier to think about that trying to work through different levels of recursion.

There are times when it is useful to know exactly what happens when a recursive call (or any method call, for that matter) is made. Prior to transferring control to the top of the method being called, all local variables and the address of the current code location are pushed onto the call stack. This call stack is just like any other stack, except that it has a smaller amount of space available to it. You can, in fact, examine the call stack when debugging — from the “Debug” menu, select “Windows -> Call Stack”. This will open a window showing the contents of the call stack. The line on top shows the line of code currently ready for execution. Below it is the line that called the current method, and below that line is the line that called that method, etc. By double-clicking on an entry in the call stack, you can use the other debugging tools to examine the values of the local variables for the method containing that line of code. If this method is recursive, the values displayed for the local variables are their values at that level of recursion.

One consequence of method calls using a call stack with limited space available is that moderately deep recursion can fill up the call stack. If this happens, a StackOverflowException will be thrown. Thus, infinite recursion will always throw this exception, as will recursion that is nested too deeply. For this reason, it is usually a bad idea to use recursion on a linked list - if the list is very long, the recursion will be nested too deeply. We must also take care in using recursion with trees, as long paths in a tree can lead to a StackOverflowException. Due to the branching nature of trees, however, we can have very large trees with no long paths. In fact, there are many cases in which we can be sure that a tree doesn’t contain any long paths. In such cases, recursion is often a useful technique.

Binary Search Trees

We motivated our discussion of trees by expressing a need for a linked data structure that supports a binary search or something similar. We will present such a data structure - a binary search tree - in this section. While it will support efficient lookups, insertions, and deletions for many applications, we will see that there are cases in which it performs no better than a linked list. In the next section , we will add some refinements that will guarantee good performance.

Before we can define a binary search tree, we need to define a more primitive structure, a binary tree. We will then use binary trees to define binary search trees, and show how to build them and search them. We will then show how to remove elements from them. We conclude this section by presenting the inorder traversal algorithm, which processes all the elements in a binary search tree in order.

AVL Trees

Up to this point, we haven’t addressed the performance of binary search trees. In considering this performance, let’s assume that the time needed to compare two keys is bounded by some fixed constant. The main reason we do this is that this cost doesn’t depend on the number of keys in the tree; however, it may depend on the sizes of the keys, as, for example, if keys are strings. However, we will ignore this complication for the purpose of this discussion.

Each of the methods we have described for finding a key, adding a key and a value, or removing a key and its associated value, follows a single path in the given tree. As a result, the time needed for each of these methods is at worst proportional to the height of the tree, where the height is defined to be the length of the longest path from the root to any node. (Thus, the height of a one-node tree is $ 0 $, because no steps are needed to get from the root to the only node - the root itself — and the height of a two-node tree is always $ 1 $.) In other words, we say that the worst-case running time of each of these methods is in $ O(h) $, where $ h $ is the height of the tree.

Depending on the shape of the tree, $ O(h) $ running time might be very good. For example, it is possible to show that if keys are randomly taken from a uniform distribution and successively added to an initially empty binary search tree, the expected height is in $ O(\log n) $, where $ n $ is the number of nodes. In this case, we would expect logarithmic performance for lookups, insertions, and deletions. In fact, there are many applications in which the height of a binary search tree remains fairly small in comparison to the number of nodes.

On the other hand, such a shape is by no means guaranteed. For example, suppose a binary search tree were built by adding the int keys 1 through $ n $ in increasing order. Then 1 would go at the root, and 2 would be its right child. Each successive key would then be larger than any key currently in the tree, and hence would be added as the right child of the last node on the path going to the right. As a result, the tree would have the following shape:

The height of this tree is $ n - 1 $; consequently, lookups will take time linear in $ n $, the number of elements, in the worst case. This performance is comparable with that of a linked list. In order to guaranteed good performance, we need a way to ensure that the height of a binary search tree does not grow too quickly.

One way to accomplish this is to require that each node always has children that differ in height by at most $ 1 $. In order for this restriction to make sense, we need to extend the definition of the height of a tree to apply to an empty tree. Because the height of a one-node tree is $ 0 $, we will define the height of an empty tree to be $ -1 $. We call this restricted form of a binary search tree an AVL tree (“AVL” stands for the names of the inventors, Adelson-Velskii and Landis).

This repository contains a Java application that displays an AVL tree of a given height using as few nodes as possible. For example, the following screen capture shows an AVL tree of height $ 7 $ having a minimum number of nodes:

As the above picture illustrates, a minimum of $ 54 $ nodes are required for an AVL tree to reach a height of $ 7 $. In general, it can be shown that the height of an AVL tree is at worst proportional to $ \log n $, where $ n $ is the number of nodes in the tree. Thus, if we can maintain the shape of an AVL tree efficiently, we should have efficient lookups and updates.

Regarding the AVL tree shown above, notice that the tree is not as well-balanced as it could be. For example, $ 0 $ is at depth $ 7 $, whereas $ 52 $, which also has two empty children, is only at depth $ 4 $. Furthermore, it is possible to arrange $ 54 $ nodes into a binary tree with height as small as $ 5 $. However, maintaining a more-balanced structure would likely require more work, and as a result, the overall performance might not be as good. As we will show in what follows, the balance criterion for an AVL tree can be maintained without a great deal of overhead.

The first thing we should consider is how we can efficiently determine the height of a binary tree. We don’t want to have to explore the entire tree to find the longest path from the root — this would be way too expensive. Instead, we store the height of a tree in its root. If our nodes are mutable, we should use a public property with both get and set accessors for this purpose. However, such a setup places the burden of maintaining the heights on the user of the binary tree node class. Using immutable nodes allows a much cleaner (albeit slightly less efficient) solution. In what follows, we will show how to modify the definition of an immutable binary tree node so that whenever a binary tree is created from such nodes, the resulting tree is guaranteed to satisfy the AVL tree balance criterion. As a result, user code will be able to form AVL trees as if they were ordinary binary search trees.

In order to allow convenient and efficient access to the height, even for empty trees, we can store the height of a tree in a private field in its root, and provide a static method to take a nullable binary tree node as its only parameter and return its height. Making this method static will allow us to handle empty (i.e., null) trees. If the tree is empty, this method will return $ -1 $; otherwise, it will return the height stored in the tree. This method can be public.

We then can modify the constructor so that it initializes the height field. Using the above method, it can find the heights of each child, and add $ 1 $ to the maximum of these values. This is the height of the node being constructed. It can initialize the height field to this value, and because the nodes are immutable, this field will store the correct height from that point on.

Now that we have a way to find the height of a tree efficiently, we can focus on how we maintain the balance property. Whenever an insertion or deletion would cause the balance property to be violated for a particular node, we perform a rotation at that node. Suppose, for example, that we have inserted an element into a node’s left child, and that this operation causes the height of the new left child to be $ 2 $ greater than the height of the right child (note that this same scenario could have occurred if we had removed an element from the right child). We can then rotate the tree using a single rotate right:

The tree on the left above represents the tree whose left child has a height $ 2 $ greater than its right child. The root and the lines to its children are drawn using dashes to indicate that the root node has not yet been constructed — we have at this point simply built a new left child, and the tree on the left shows the tree that would be formed if we were building an ordinary binary search tree. The circles in the picture indicate individual nodes, and the triangles indicate arbitrary trees (which may be empty). Note that the because the left child has a height $ 2 $ greater than the right child, we know that the left child cannot be empty; hence, we can safely depict it as a node with two children. The labels are chosen to indicate the order of the elements — e.g., as “a” $ \lt $ “b”, every key in tree a is less than the key in node b. The tree on the right shows the tree that would be built by performing this rotation. Note that the rotation preserves the order of the keys.

Suppose the name of our class implementing a binary tree node is BinaryTreeNode<T>, and suppose it has the following properties:

• Data: gets the data stored in the node.
• LeftChild: gets the left child of the node.
• RightChild: gets the right child of the node.

Then the following code can be used to perform a single rotate right:

/// <summary>
/// Builds the result of performing a single rotate right on the binary tree
/// described by the given root, left child, and right child.
/// </summary>
/// <param name="root">The data stored in the root of the original tree.</param>
/// <param name="left">The left child of the root of the original tree.</param>
/// <param name="right">The right child of the root of the original tree.</param>
/// <returns>The result of performing a single rotate right on the tree described
/// by the parameters.</returns>
private static BinaryTreeNode<T> SingleRotateRight(T root,
    BinaryTreeNode<T> left, BinaryTreeNode<T>? right)
{
    BinaryTreeNode<T> newRight = new(root, left.RightChild, right);
    return new BinaryTreeNode<T>(left.Data, left.LeftChild, newRight);
}

Relating this code to the tree on the left in the picture above, the parameter root refers to d, the parameter left refers to the tree rooted at node b, and the parameter right refers to the (possibly empty) tree e. The code first constructs the right child of the tree on the right and places it in the variable newRight. It then constructs the entire tree on the right and returns it.

Now that we have seen what a single rotate right does and how to code it, we need to consider whether it fixes the problem. Recall that we were assuming that the given left child (i.e., the tree rooted at b in the tree on the left above) has a height $ 2 $ greater than the given right child (i.e., the tree e in the tree on the left above). Let’s suppose the tree e has height $ h $. Then the tree rooted at b has height $ h + 2 $. By the definition of the height of a tree, either a or c (or both) must have height $ h + 1 $. Assuming that every tree we’ve built so far is an AVL tree, the children of b must differ in height by at most $ 1 $; hence, a and c must both have a height of at least $ h $ and at most $ h + 1 $.

Given these heights, let’s examine the tree on the right. We have assumed that every tree we’ve built up to this point is an AVL tree, so we don’t need to worry about any balances within a, c, or e. Because c has either height $ h $ or height $ h + 1 $ and e has height $ h $, the tree rooted at d satisfies the balance criterion. However, if c has height $ h + 1 $ and a has height $ h $, then the tree rooted at d has height $ h + 2 $, and the balance criterion is not satisfied. On the other hand, if a has height $ h + 1 $, the tree rooted at d will have a height of either $ h + 1 $ or $ h + 2 $, depending on the height of c. In these cases, the balance criterion is satisfied.

We therefore conclude that a single rotate right will restore the balance if:

• The height of the original left child (i.e., the tree rooted at b in the above figure) is $ 2 $ greater than the height of the original right child (tree e in the above figure); and
• The height of the left child of the original left child (tree a in the above figure) is greater than the height of the original right child (tree e).

For the case in which the height of the left child of the original left child (tree a) is not greater than the height of the original right child (tree e), we will need to use a different kind of rotation.

Before we consider the other kind of rotation, we can observe that if an insertion or deletion leaves the right child with a height $ 2 $ greater than the left child and the right child of the right child with a height greater than the left child, the mirror image of a single rotate right will restore the balance. This rotation is called a single rotate left:

Returning to the case in which the left child has a height $ 2 $ greater than the right child, but the left child of the left child has a height no greater than the right child, we can in this case do a double rotate right:

Note that we have drawn the trees a bit differently by showing more detail. Let’s now show that this rotation restores the balance in this case. Suppose that in the tree on the left, g has height $ h $. Then the tree rooted at b has height $ h + 2 $. Because the height of a is no greater than the height of g, assuming all trees we have built so far are AVL trees, a must have height $ h $, and the tree rooted at d must have height $ h + 1 $ (thus, it makes sense to draw it as having a root node). This means that c and e both must have heights of either $ h $ or $ h - 1 $. It is now not hard to verify that the balance criterion is satisfied at b, f, and d in the tree on the right.

The only remaining case is the mirror image of the above — i.e., that the right child has height $ 2 $ greater than the left child, but the height of the right child of the right child is no greater than the height of the left child. In this case, a double rotate left can be applied:

We have shown how to restore the balance whenever the balance criterion is violated. Now we just need to put it all together in a public static method that will replace the constructor as far as user code is concerned. In order to prevent the user from calling the constructor directly, we also need to make the constructor private. We want this static method to take the same parameters as the constructor:

• The data item that can be stored at the root, provided no rotation is required.
• The tree that can be used as the left child if no rotation is required.
• The tree that can be used as the right child if no rotation is required.

The purpose of this method is to build a tree including all the given nodes, with the given data item following all nodes in the left child and preceding all nodes in the right child, but satisfying the AVL tree balance criterion. Because this method will be the only way for user code to build a tree, we can assume that both of the given trees satisfy the AVL balance criterion. Suppose that the name of the static method to get the height of a tree is Height, and that the names of the methods to do the remaining rotations are SingleRotateLeft, DoubleRotateRight, and DoubleRotateLeft, respectively. Further suppose that the parameter lists for each of these last three methods are the same as for SingleRotateRight above, except that for the left rotations, left is nullable, not right. The following method can then be used to build AVL trees:

/// <summary>
/// Constructs an AVL Tree from the given data element and trees. The heights of 
/// the trees must differ by at most two. The tree built will have the same 
/// inorder traversal order as if the data were at the root, left were the left 
/// child, and right were the right child.
/// </summary>
/// <param name="data">A data item to be stored in the tree.</param>
/// <param name="left">An AVL Tree containing elements less than data.</param>
/// <param name="right">An AVL Tree containing elements greater than data.
/// </param>
/// <returns>The AVL Tree constructed.</returns>
public static BinaryTreeNode<T> GetAvlTree(T data, BinaryTreeNode<T>? left,
    BinaryTreeNode<T>? right)
{
    int diff = Height(left) - Height(right);
    if (Math.Abs(diff) > 2)
    {
        throw new ArgumentException();
    }
    else if (diff == 2)
    {
        // If the heights differ by 2, left's height is at least 1; hence, it isn't null.
        if (Height(left!.LeftChild) > Height(right))
        {
            return SingleRotateRight(data, left, right);
        }
        else
        {
            // If the heights differ by 2, but left.LeftChild's height is no more than
            // right's height, then left.RightChild's height must be greater than right's
            // height; hence, left.RightChild isn't null.
            return DoubleRotateRight(data, left, right);
        }
    }
    else if (diff == -2)
    {
        // If the heights differ by -2, right's height is at least 1; hence, it isn't null.
        if (Height(right!.RightChild) > Height(left))
        {
            return SingleRotateLeft(data, left, right);
        }
        else
        {
            // If the heights differ by -1, but right.RightChild's height is no more than 
            // left's height, then right.LeftChild's height must be greater than right's 
            // height; hence right.LeftChild isn't null.
            return DoubleRotateLeft(data, left, right);
        }
    }
    else
    {
        return new BinaryTreeNode<T>(data, left, right);
    }
}

In order to build and maintain an AVL tree, user code simply needs to call the above wherever it would have invoked the BinaryTreeNode<T> constructor in building and maintaining an ordinary binary search tree. The extra overhead is fairly minimal — each time a new node is constructed, we need to check a few heights (which are stored in fields), and if a rotation is needed, construct one or two extra nodes. As a result, because the height of an AVL tree is guaranteed to be logarithmic in the number of nodes, the worst-case running times of both lookups and updates are in $ O(\log n) $, where $ n $ is the number of nodes in the tree.

Tries

AVL trees give us an efficient mechanism for storage and retrieval, particularly if we need to be able to process the elements in order of their keys. However, there are special cases where we can achieve better performance. One of these special cases occurs when we need to store a list of words, as we might need in a word game, for example. For such applications, a trie provides for even more efficient storage and retrieval.

In this section, we first define a trie and give a rather straightforward implementation. We then show how to improve performance by implementing different nodes in different ways. We then examine the use of a preorder traversal to traverse a trie. We conclude by discussing an example of using a trie in a word game.

Priority Queues

Often we need a data structure that supports efficient storage of data items and their subsequent retrieval in order of some pre-determined priority. We have already seen two instances of such data structures: stacks and queues. With a stack, the later the item is stored, the higher its priority. With a queue, the earlier the item is stored, the higher its priority. More generally, we would like to be able to set priorities arbitrarily, in a way that may be unrelated to the order in which they were stored.

The general name for such a data structure is a priority queue. Priority queues typically support the following operations:

• Adding a data element, together with a priority.
• Obtaining the number of data elements currently in the structure.
• Obtaining the maximum of all priorities of elements in the structure.
• Removing a data element having maximum priority.

Obviously, the last two operations above can only be done when the structure is nonempty. A variation on the above focuses on minimum priority rather than maximum priority. This variation is called a min-priority queue. Because we will later cover applications of min-priority queues, we will focus on this variation in this section. In the sub-sections that follow, we will first consider a general structure that can be used in various ways to give efficient priority queue implementations. We will then look at one specific implementation. We will conclude by giving an example of how min-priority queues are used in file compression algorithms.

A Simple Hash Table Implementation

In this section, we will look at a simple hash table implementation using a fixed-length table. In subsequent sections, we will consider how to adjust the table size for better performance, as well as how to implement enumerators for iterating through the keys and/or values.

At the core of our implementation is the computation of the hash function. Recall that the implementation of the hash function computation is divided into two parts. The first part of the computation is implemented within the definition of the key type via its GetHashCode method. We will discuss this part of the computation in the section, “Hash Codes” . Here, we will focus on the second step, converting the int hash code returned by the key’s GetHashCode method to a table location.

One common technique, which is used in the .NET implementation of the Dictionary<TKey, TValue> class, is called the division method. This technique consists of the following:

1. Reset the sign bit of the hash code to 0.
2. Compute the remainder of dividing this value by the length of the table.

If p is a nonnegative int and q is a positive int, then p % q gives a nonnegative value less than q; hence, if q is the table length, p % q is a location within the table. Furthermore, this calculation often does a good job of distributing hash code values among the different table locations, but this depends on how the hash codes were computed and what the length of the table is.

For example, suppose we use a size $ 2^k $ for some positive integer $ k $. In this case, the above computation can be simplified, as the values formed by $ k $ bits are $ 0 $ through $ 2^k - 1 $, or all of the locations in the table. We can therefore simply use the low-order $ k $ bits of the hash code as the table location. However, it turns out that using the division method when the table size is a power of $ 2 $ can lead to poor key distribution for some common hash code schemes. To avoid these problems, a prime number should be used as the table length. When a prime number is used, the division method tends to result in a good distribution of the keys.

The reason we need to reset the sign bit of the hash code to 0 is to ensure that the first operand to the % operator is nonnegative, and hence that the result is nonnegative. Furthermore, simply taking the absolute value of the hash code won’t always work because $ -2^{31} $ can be stored in an int, but $ 2^{31} $ is too large. Resetting the sign bit to 0 is a quick way to ensure we have a nonnegative value without losing any additional information.

We can do this using a bitwise AND operator, denoted by a single ampersand (&). This operator operates on the individual bits of an integer type such as int. The logical AND of two 1 bits is 1; all other combinations result in 0. Thus, if we want to set a bit to 0, we AND it with 0, and ANDing a bit with 1 will leave it unchanged. The sign bit is the high-order bit; hence, we want to AND the hash code with an int whose first bit is 0 and whose remaining bits are 1. The easiest way to write this value is using hexadecimal notation, as each hex digit corresponds to exactly four bits. We begin writing a hexadecimal value with 0x. The first four bits need to be one 0, followed by three 1s. These three 1 are in the $ 1 $, $ 2 $, and $ 4 $ bit positions of the first hex digit; hence, the value of this hex digit should be 7. We then want seven more hex digits, each containing four 1s. An additional 1 in the $ 8 $ position gives us a sum of $ 15 $, which is denoted as either f or F in hex. We can therefore reset the sign bit of an int i as follows:

i = i & 0x7fffffff;

or:

i &= 0x7fffffff;

Now let’s consider how we would look up a key. First, we need to obtain the key’s hash code by calling its GetHashCode method. From the hash code, we use the division method to compute the table location where it belongs. We then search the linked list for that key.

Adding a key and a value is done similarly. We first look for the key as described above. If we find it, we either replace its KeyValuePair with a new one containing the new value, or we throw an exception, depending on how we want this method to behave. If we don’t find it, we add a new cell containing the given key and value to the beginning of the list we searched.

Note that looking up a key or adding a key and a value as described above can be implemented using either methods or indexers (.NET uses both). See the section, “Indexers” for details on how to implement an indexer.

Rehashing

In this section, we will show how to improve the performance of a hash table by adjusting the size of the array. In order to see how the array size impacts the performance, let’s suppose we are using an array with $ m $ locations, and that we are storing $ n $ keys in the hash table. In what follows, we will analyze the number of keys we will need to examine while searching for a particular key, k.

In the worst case, no matter how large the array is, it is possible that all of the keys map to the same array location, and therefore all end up in one long linked list. In such a case, we will need to examine all of the keys whenever we are looking for the last one in this list. However, the worst case is too pessimistic — if the hash function is implemented properly, it is reasonable to expect that something approaching a uniform random distribution will occur. We will therefore consider the number of keys we would expect to examine, assuming a uniform random distribution of keys throughout the table.

We’ll first consider the case in which k is not in the hash table. In this case, we will need to examine all of the keys in the linked list at the array location where k belongs. Because each of the $ n $ keys is equally likely to map to each of the $ m $ array locations, we would expect, on average, $ n / m $ keys to be mapped to the location where k belongs. Hence, in this case, we would expect to examine $ n / m $ keys, on average.

Now let’s consider the case in which k is in the hash table. In this case, we will examine the key k, plus all the keys that precede k in its linked list. The number of keys preceding k cannot be more than the total number of keys other than k in that linked list. Again, because each of the $ n - 1 $ keys other than k is equally likely to map to each of the $ m $ array locations, we would expect, on average, $ (n - 1) / m $ keys other than k to be in the same linked list as k. Thus, we can expect, on average, to examine no more than $ 1 +  (n - 1) / m $ keys when looking for a key that is present.

Notice that both of the values derived above decrease as $ m $ increases. Specifically, if $ m \geq n $, the expected number of examined keys on a failed lookup is no more than $ 1 $, and the expected number of examined keys on a successful lookup is less than $ 2 $. We can therefore expect to achieve very good performance if we keep the number of array locations at least as large as the number of keys.

We have already seen (e.g., in “Implementation of StringBuilders ”) how we can keep an array large enough by doubling its size whenever we need to. However, a hash table presents two unique challenges for this technique. First, as we observed in the previous section , we are most likely to get good performance from a hash table if the number of array locations is a prime number. However, doubling a prime number will never give us a prime number. The other challenge is due to the fact that when we change the size of the array, we consequently change the hash function, as the hash function uses the array size. As a result, the keys will need to go to different array locations in the new array.

In order to tackle the first challenge, recall that we presented an algorithm for finding all prime numbers less than a given n in “Finding Prime Numbers ”; however, this is a rather expensive way to find a prime number of an appropriate size. While there are more efficient algorithms, we really don’t need one. Suppose we start with an array size of $ 5 $ (there may be applications using many small hash tables — the .NET implementation starts with an array size of $ 3 $). $ 5 $ is larger than $ 2^2 = 4 $. If we double this value $ 28 $ times, we reach a value larger than $ 2^{30} $, which is larger than $ 1 $ billion. More importantly, this value is large enough that we can’t double it again, as an array in C# must contain fewer than $ 2^{31} $ locations. Hence, we need no more than $ 29 $ different array sizes. We can pre-compute these and hard-code them into our implementation; for example,

private int[] _tableSizes = 
{
    5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717,
    51437, 102877, 205759, 411527, 823117, 1646237, 3292489, 6584983,
    13169977, 26339969, 52679969, 105359939, 210719881, 421439783,
    842879579, 1685759167 
}; 

Each of the values in the above array is a prime number, and each one after the first is slightly more than twice its predecessor. In order to make use of these values, we need a private field to store the index at which the current table size is stored in this array. We also need to keep track of the number of keys currently stored. As this information is useful to the user, a public int Count property would be appropriate. It can use the default implementation with a get accessor and a private set accessor.

One important difference between the reason for rehashing and the reason for creating a larger array for an implementation of a StringBuilder , stack , or queue is that rehashing is done simply for performance reasons - there is always room to put a new key and value into a hash table unless we have run out of memory. For this reason, it makes sense to handle rehashing after we have added the new key and value. This results in one extra linked-list insertion (i.e., updating two references) each time we rehash, but it simplifies the coding somewhat. Because rehashing is rarely done, this overhead is minimal, and seems to be a reasonable price to pay for simpler code.

Once a new key and value have been added, we first need to update the Count. We then need to check to see whether this number exceeds the current array size. As we do this, we should also make sure that the array size we are using is not the last array size in _tableSizes, because if it is, we can’t rehash. If both of these conditions hold, we need to rehash.

To begin rehashing, we copy the reference to the table into a local variable and increment the field giving our current index into _tableSizes. We then construct for the table field a new array whose size is given by the value at the new current index into _tableSizes. Note that it is important that the local variable is used to refer to the old table, and that the field is used to refer to the new table, as the hash function uses the field to obtain the array size.

We then need to move all keys and values from the old table to the new one. As we do this, we will need to re-compute the hash function for each key, as the hash function has now changed. We therefore need two nested loops. The outer loop iterates through the locations in the old table, and the inner loop iterates through the linked list at that location. On each iteration of the inner loop:

1. Use a local variable to save another reference to the current cell in the linked list at the current table location.
2. Advance to the next cell in the list.
3. Using the hash function, compute the new array location of the key in the cell that was saved in step 1.
4. Insert this cell into the beginning of the linked list at the new array location in the new table.

Memoization

We we will now present an example of a common technique involving dictionaries. Consider the following variation of the 2-player game, Nim. The board consists of a number of stones arranged into several piles. Associated with each nonempty pile is a limit, which is a positive integer no greater than the number of stones on that pile (the limit for an empty pile is always 0). Players alternate taking stones according to the following rules:

• On each turn, the player must take some number of stones from a single pile.
• The number of stones taken must be at least 1, but no more than the current limit for that pile.
• Taking n stones from a pile changes the limit for that pile to 2n. (If this limit is more than the number of stones remaining on that pile, the new limit is the number of stones remaining.)

The player taking the last stone wins. Note that by the rules of the game, there will always be a winner — a draw is impossible.

For example, suppose we start a game with three piles, each containing 10 stones with a limit of 9. We will denote this board position as (10/9; 10/9; 10/9). If Player 1 removes two stones from Pile 1, the resulting position is (8/4; 10/9; 10/9). Note that because 2 stones were removed from Pile 1, its new limit is 2 x 2 = 4. If Player 2 now removes 4 stones from Pile 2, the resulting position is (8/4; 6/6; 10/9). Note that because 4 stones were removed, the new limit for Pile 2 would become 2 x 4 = 8; however, because only 6 stones remain, the new limit is 6. Play then continues until a player wins by taking all remaining stones.

Let us define a winning play as any play giving a position from which there is no winning play. Thus, if we make a winning play, there are two possible cases. In the first case, there are no winning plays from the resulting position because there are no legal plays. This means we just took the last stone and won the game. In the other case, there are legal plays, but none is a winning play. Our opponent must make one of these plays. Because it isn’t a winning play, there must be a winning play from the resulting position. Therefore, an optimal strategy is to make a winning play whenever one exists. Because of the way a winning play is defined, if a winning play exists, following this strategy will enable us to continue to make winning plays until we eventually win the game. If no winning play exists, we just have to make some play and hope that our opponent blunders by making a play that is not a winning play. If that happens, a winning play will be available, and our strategy leads us to a win.

Consider the following examples:

• Example 1: (1/1; 0/0). Taking one stone from Pile 1 is a winning play because there is no legal play from the resulting position; hence, there can be no winning play from it.
• Example 2: (1/1; 1/1). There is no winning play from this position because both legal plays give essentially the position from Example 1, from which there is a winning play.
• Example 3: (2/2; 1/1). Taking one stone from Pile 1 is a winning play because it leads to (1/1; 1/1), from which there is no winning play, as shown in Example 2.

Given enough stones and piles, finding a winning play or determining that there is none is challenging. In order to develop a search algorithm somewhat similar to the one described in “Tries in Word Games” , we can define the following tree:

• The root is the current board position.
• The children of a node are all the positions that can be reached by making legal plays.

Thus, the tree defined by (2/2; 2/2) is as follows:

The winning plays have each been marked with a ‘W’ in the above tree. As in “Tries in Word Games” , this tree is not a data structure, but simply a mental guide to building a search algorithm. Specifically, we can find a winning play (or determine whether there is none) by traversing the tree in the following way:

• For each legal play p from the given position:
  • Form the board position that results from making this play (this position is a child).
  • Recursively find a winning play from this new position.
  • If there was no winning play returned (i.e., it was null), return p, as it’s a winning play.
• If we get to this point we’ve examined all the plays, and none of them is winning; hence we return null.

Note that the above algorithm may not examine all the nodes in the tree because once it finds a winning play, it returns it immediately without needing to examine any more children. For example, when processing the children of the node (1/1; 2/2), it finds that from its second child, (1/1; 1/1), there is no winning play; hence, it immediately returns the play that removes one stone from Pile 2 without even looking at the third child, (1/1; 0/0). Even so, because the size of the tree grows exponentially as the number of stones increases, once the number of stones reaches about 25, the time needed for the algorithm becomes unacceptable.

Notice that several of the nodes in the tree occur multiple times. For example, (1/1; 1/1) occurs twice and (1/1; 0/0) occurs five times. For a large tree, the number of duplicate nodes in the tree increases dramatically. The only thing that determines the presence of a winning move is the board position; hence, once we have a winning move (or know that none exists) for a given position, it will be the same wherever this position may occur in the tree. We can therefore save a great deal of time by saving the winning move for any position we examine. Then whenever we need to examine a position, we first check to see if we’ve already processed it — if so, we just use the result we obtained earlier rather than processing it again. Because processing it again may involve searching a large tree, the savings in time might be huge.

The technique outlined in the above paragraph is known as memoization (not to be confused with memorization) — we make a memo of the results we compute so that we can look them up again later if we need them. A dictionary whose keys are board positions and whose values are plays is an ideal data structure for augmenting the above search with memoization. As the first step, before we look at any plays from the given board position, we look up the position in the dictionary. If we find it, we immediately return the play associated with it. Otherwise, we continue the algorithm as before, but prior to returning a play (even if it is null), we save that play in the dictionary with the given board position as its key. This memoization will allow us to analyze board positions containing many more stones.

To implement the above strategy, we need to define two types - one to represent a board position and one to represent a play. The type representing a play needs to be a class so that we can use null to indicate that there is no winning play. The type representing a board position can be either a class or a structure. Because the dictionary needs to be able to compare instances of this type for equality in order be able to find keys, its definition will need to re-define the equality comparisons. Consequently, we need to redefine the hash code computation to be consistent with the equality comparison. The next two sections will examine these topics.

Equality in C#

Continuing our discussion from the previous section , we want to define a type that represents a Nim board. Furthermore, we need to be able to compare instances of this type for equality. Before we can address how this can be done, we first need to take a careful look at how C# handles equality. In what follows, we will discuss how C# handles the == operator, the non-static Equals method, and two static methods for determining equality. We will then show how the comparison can be defined so that all of these mechanisms behave in a consistent way.

We first consider the == operator. The behavior of this operator is determined by the compile-time types of its operands. This is determined by the declared types of variables, the declared return types of methods or properties, and the rules for evaluating expressions. Thus, for example, if we have a statement

object x = "abc";

the compile-time type of x is object, even though it actually refers to a string.

For pre-defined value types , == evaluates to true if its operands contain the same values. Because enumerations are represented as numeric types such as int or byte, this rule applies to them as well. For user-defined structures, == is undefined unless the structure definition explicitly defines the == and != operators. We will show how this can be done below.

By default, when == is applied to reference types, it evaluates to true when the two operands refer to the same object (i.e., they refer to the same memory location). A class may override this behavior by explicitly defining the == and != operators. For example, the string class defines the == operator to evaluate to true if the given strings are the same length and contain the same sequence of characters.

Let’s consider an example that illustrates the rules for reference types:

string a = "abc";
string b = "0abc".Substring(1);
object x = a;
object y = b;
bool comp1 = a == b;
bool comp2 = x == y;

The first two lines assign to a and b the same sequence of characters; however, because the strings are computed differently, they are different objects. The next two lines copy the reference in a to x and the reference in b to y. Thus, at this point, all four variables refer to a string “abc”; however, a and x refer to a different object than do b and y. The fifth line compares a and b for equality using ==. The compile-time types of a and b are both string; hence, these variables are compared using the rules for comparing strings. Because they refer to strings of the same length and containing the same sequence of characters, comp1 is assigned true. The behavior of the last line is determined by the compile-time types of x and y. These types are both object, which defines the default behavior of this operator for reference types. Thus, the comparison determines whether the two variables refer to the same object. Because they do not, comp2 is assigned false.

Now let’s consider the non-static Equals method. The biggest difference between this method and the == operator is that the behavior of x.Equals(y) is determined by the run-time type of x. This is determined by the actual type of the object, independent of how any variables or return types are declared.

By default, if x is a value type and y can be treated as having the same type, then x.Equals(y) returns true if x and y have the same value (if y can’t be treated as having the same type as x, then this method returns false). Thus, for pre-defined value types, the behavior is the same as for == once the types are determined (provided the types are consistent). However, the Equals method is always defined, whereas the == operator may not be. Furthermore, structures may override this method to change this behavior — we will show how to do this below.

By default, if x is a reference type, x.Equals(y) returns true if x and y refer to the same object. Hence, this behavior is the same as for == once the types are determined (except that if x is null, x.Equals(y) will throw a NullReferenceException, whereas x == y will not). However, classes may override this method to change this behavior. For example, the string class overrides this method to return true if y is a string of the same length and contains the same sequence of characters as x.

Let’s now continue the above example by adding the following lines:

bool comp3 = a.Equals(b);
bool comp4 = a.Equals(x);
bool comp5 = x.Equals(a);
bool comp6 = x.Equals(y);

These all evaluate to true for one simple reason — the behavior is determined by the run-time type of a in the case of the first two lines, or of x in the case of the last two lines. Because these types are both string, the objects are compared as strings.

The object class defines, in addition to the Equals method described above, two public static methods, which are in turn inherited by every type in C#:

• bool Equals(object x, object y): The main purpose of this method is to avoid the NullReferenceException that is thrown by x.Equals(y) when x is null. If neither x nor y is null, this method simply returns the value of x.Equals(y). Otherwise, it will return true if both x and y are null, or false if only one is null. User-defined types cannot override this method, but because it calls the non-static Equals method, which they can override, they can affect its behavior indirectly.
• bool ReferenceEquals(object x, object y): This method returns true if x and y refer to the same object or are both null. If either x or y is a value type, it will return false. User-defined types cannot override this method.

Finally, there is nothing to prevent user-defined types from including their own Equals methods with different parameter lists. In fact, the string class includes definitions of the following public methods:

• bool Equals(string s): This method actually does the same thing as the non-static Equals method defined in the object class, but is slightly more efficient because less run-time type checking needs to be done. This is the method that is called in the computation of comp3 in the above example.
• static bool Equals(string x, string y): This method does the same thing as the static Equals method defined in the object class, but again is slightly more efficient because less run-time type checking needs to be done.

All of this can be rather daunting at first. Fortunately, in most cases these comparisons end up working the way we expect them to. The main thing we want to focus on here is how to define equality properly in a user-defined type.

Let’s start with the == operator. This is one of several operators that may be defined within class and structure definitions. If we are defining a class called SomeType, we can include a definition of the == operator as follows:

public static bool operator ==(SomeType? x, SomeType? y)
{
    // Definition of the behavior of ==
}

If SomeType is a structure, the definition is similar, but we wouldn’t define the parameters to be nullable. Note the resemblance to the definition of a static method. Even though we define it using the syntax for a method definition, we still use it as we typically use the == operator; e.g.,

if (a == b)
{
    . . .
}

If SomeType is a class and a and b are both of either type SomeType or type SomeType?, the above definition will be called using a as the parameter x and b as the parameter y.

Within the operator definition, if it is within a class definition, the first thing we need to do is to handle the cases in which one or both parameters are null. We don’t need to do this for a structure definition because value types can’t be null, but if we omit this part for a reference type, comparing a variable or expression of this type to null will most likely result in a NullReferenceException. We need to be a bit careful here, because if we use == to compare one of the parameters to null it will be a recursive call — infinite recursion, in fact. Furthermore, using x.Equals(null) is always a bad idea, as if x does, in fact, equal null, this will throw a NullReferenceException. We therefore need to use one of the static methods, Equals or ReferenceEquals:

public static bool operator ==(SomeType? x, SomeType? y)
{
    if (Equals(x, null))
    {
         return (Equals(y, null));
    }
    else if (Equals(y, null))
    {
        return false;
    }
    else
    {
        // Code to determine if x == y
    }
}

Note that because all three calls to Equals have null as a parameter, these calls won’t result in calling the Equals method that we will override below.

Whenever we define the == operator, C# requires that we also define the != operator. In virtually all cases, what we want this operator to do is to return the negation of what the == operator does; thus, if SomeType is a class, we define:

public static bool operator !=(SomeType? x, SomeType? y)
{
    return !(x == y);
}

If SomeType is a structure, we use the same definition, without making the parameters nullable.

We now turn to the (non-static) Equals method. This is defined in the object class to be a virtual method, meaning that sub-types are allowed to override its behavior. Because every type in C# is a subtype of object, this method is present in every type, and it can be overridden by any class or structure.

We override this method as follows:

public override bool Equals(object? obj)
{
    // Definition of the behavior of Equals
}

For the body of the method, we first need to take care of the fact that the parameter is of type object; hence, it may not even have the same type as what we want to compare it to. If this is the case, we need to return false. Otherwise, in order to ensure consistency between this method and the == operator, we can do the actual comparison using the == operator. If we are defining a class SomeType, we can accomplish all of this as follows:

public override bool Equals(object? obj)
{
    return obj as SomeType == this;
}

The as keyword casts obj to SomeType if possible; however, if obj cannot be cast to SomeType, the as expression evaluates to null (or in general, the default value for SomeType). Because this cannot be null, false will always be returned if obj cannot be cast to SomeType.

If SomeType is a structure, the above won’t work because this may be the default value for SomeType. In this case, we need somewhat more complicated code:

public override bool Equals(object? obj)
{
    if (obj is SomeType x)
    {
        return this == x;
    }
    else
    {
        return false;
    }
}

This code uses the is keyword, which is similar to as in that it tries to cast obj to SomeType. However, if the cast is allowed, it places the result in the SomeType variable x and evaluates to true; otherwise, it assigns to x the default value of SomeType and evaluates to false.

The above definitions give a template for defining the == and != operators and the non-static Equals method for most types that we would want to compare for equality. All we need to do to complete the definitions is to replace the name SomeType, wherever it occurs, with the name of the type we are defining, and to fill in the hole left in the definition of the == operator. It is here where we actually define how the comparison is to be made.

Suppose, for example, that we want to define a class to represent a Nim board position (see the previous section ). This class will need to have two private fields: an int[ ] storing the number of stones on each pile and an int[ ] storing the limit for each pile. These two arrays should be non-null and have the same length, but this should be enforced by the constructor. By default, two instances of a class are considered to be equal (by either the == operator or the non-static Equals method) if they are the same object. This is too strong for our purposes; instead, two instances x and y of the board position class should be considered equal if

• Their arrays giving the number of stones on each pile have the same length; and
• For each index i into the arrays giving the number of stones on each pile, the elements at location i of these arrays have the same value, and the elements at location i of the arrays giving the limit for each pile have the same value.

Code to make this determination and return the result can be inserted into the above template defining of the == operator, and the other two templates can be customized to refer to this type.

Any class that redefines equality should also redefine the hash code computation to be consistent with the equality definition. We will show how to do this in the next section.

Hash Codes

Whenever equality is redefined for a type, the hash code computation for that type needs to be redefined in a consistent way. This is done by overriding that type’s GetHashCode method. In order for hashing to be implemented correctly and efficiently, this method should satisfy the following goals:

• Equal keys must have the same hash code. This is necessary in order for the Dictionary<TKey, TValue> class to be able to find a given key that it has stored. On the other hand, because the number of possible keys is usually larger than the number of possible hash codes, unequal keys are also allowed to have the same hash code.
• The computation should be done quickly.
• Hash codes should be uniformly distributed even if the keys are not.

The last goal above may seem rather daunting, particularly in light of our desire for a quick computation. In fact, it is impossible to guarantee in general — provided there are more than $ 2^{32}(k - 1) $ possible keys from which to choose, no matter how the hash code computation is implemented, we can always find at least $ k $ keys with the same hash code. However, this is a problem that has been studied a great deal, and several techniques have been developed that are effective in practice. We will caution, however, that not every technique that looks like it should be effective actually is in practice. It is best to use techniques that have been demonstrated to be effective in a wide variety of applications. We will examine one of these techniques in what follows.

A guiding principle in developing hashing techniques is to use all information available in the key. By using all the information, we will be sure to use the information that distinguishes this key from other keys. This information includes not just the values of the individual parts of the the key, but also the order in which they occur, provided this order is significant in distinguishing unequal keys. For example, the strings, “being” and “begin” contain the same letters, but are different because the letters occur in a different order.

One specific technique initializes the hash code to 0, then processes the key one component at a time. These components may be bytes, characters, or other parts no larger than 32 bits each. For example, for the Nim board positions discussed in “Memoization” , the components would be the number of stones on each pile, the limit for each pile, and the total number of piles (to distinguish between a board ending with empty piles and a board with fewer piles). For each component, it does the following:

• Multiply the hash code by some fixed odd integer.
• Add the current component to the hash code.

Due to the repeated multiplications, the above computation will often overflow an int. This is not a problem — the remaining bits are sufficient for the hash code.

In order to understand this computation a little better, let’s first ignore the effect of this overflow. We’ll denote the fixed odd integer by $ x $, and the components of the key as $ k_1, \dots, k_n $. Then this is the result of the computation:

Because the above is a polynomial, this hashing scheme is called polynomial hashing. While the computation itself is efficient, performing just a couple of arithmetic operations on each component, the result is to multiply each component by a unique value ( $ x^i $ for some $ i $) depending on its position within the key.

Now let’s consider the effect of overflow on the above polynomial. What this does is to keep only the low-order 32 bits of the value of the polynomial. Looking at it another way, we end up multiplying $ k_i $ by only the low-order 32 bits of $ x^{n-i} $. This helps to explain why $ x $ is an odd number — raising an even number to the $ i $th power forms a number ending in $ i $ 0s in binary. Thus, if there are more than 32 components in the key, all but the last 32 will be multiplied by $ 0 $, and hence, ignored.

There are other potential problems with using certain odd numbers for $ x $. For example, we wouldn’t want to use $ 1 $, because that would result in simply adding all the components together, and we would lose any information regarding their positions within the key. Using $ -1 $ would be almost as bad, as we would multiply all components in odd positions by $ -1 $ and all components in even positions by $ 1 $. The effect of overflow can cause similar behavior; for example, if we place $ 2^{31} - 1 $ in an int variable and square it, the overflow causes the result to be 1. Successive powers will then alternate between $ 2^{31} - 1 $ and $ 1 $.

It turns out that this cyclic behavior occurs no matter what odd number we use for $ x $. However, in most cases the cycle is long enough that keys of a reasonable size will have each component multiplied by a unique value. The only odd numbers that result in short cycles are those that are adjacent to a multiple of a large power of $ 2 $ (note that $ 0 $ is a multiple of any integer).

The other potential problem occurs when we are hashing fairly short keys. In such cases, if $ x $ is also small enough, the values computed will all be much smaller than the maximum possible integer value $ (2^{31} - 1) $. As a result, we will not have a uniform distribution of values. We therefore want to avoid making $ x $ too small.

Putting all this together, choosing $ x $ to be an odd number between $ 30 $ and $ 40 $ works pretty well. These values are large enough so that seven key components will usually overflow an int. Furthermore, they all have a cycle length greater than $ 100 $ million.

We should always save the hash code in a private field after we compute it so that subsequent requests for the same hash code don’t result in repeating the computation. This can be done in either of two ways. One way is to compute it in an eager fashion by doing it in the constructor. When doing it this way, the GetHashCode method simply needs to return the value of the private field. While this is often the easiest way, it sometimes results in computing a hash code that we end up not using. The alternative is to compute it in a lazy fashion. This requires an extra private field of type bool. This field is used to indicate whether the hash code has been computed yet or not. With this approach, the GetHashCode method first checks this field to see if the hash code has been computed. If not, it computes the hash code and saves it in its field. In either case, it then returns the value of the hash code field.

Introduction to Graphs

There are two kinds of graphs: undirected and directed. An undirected graph consists of:

• a finite set of nodes; and
• a finite set of edges, which are 2-element subsets of the nodes.

The fact that edges are 2-element sets means that the nodes that comprise an edge must be distinct. Furthermore, within a set, there is no notion of a “first” element or a “second” element — there are just two elements. Thus, an edge expresses some symmetric relationship between two nodes; i.e., if $ \{u, v\} $ is an edge then node $ u $ is adjacent to node $ v $, and node $ v $ is adjacent to node $ u $. We also might associate some data, such as a label or a length, with an edge.

We can think of an edge as “connecting” the two nodes that comprise it. We can then draw an undirected graph using circles for the nodes and lines connecting two distinct nodes for the edges. Following is an example of an undirected graph with numeric values associated with the edges:

A directed graph is similar to an undirected graph, but the edges are ordered pairs of distinct nodes rather than 2-element sets. Within an ordered pair, there is a first element and a second element. We call the first node of an edge its source and the second node its destination. Thus, an edge in a directed graph expresses an asymmetric relationship between two nodes; i.e., if $ (u, v) $ is an edge, then $ v $ is adjacent to $ u $, but $ u $ is not adjacent to $ v $ unless $ (v, u) $ is also an edge in the graph. As with undirected graphs, we might associate data with an edge in a directed graph.

We can draw directed graphs like we draw undirected graphs, except that we use an arrow to distinguish between the source and the destination of an edge. Specifically, the arrows point from the source to the destination. If we have edges $ (u, v) $ and $ (v, u) $, and if these edges have the same data associated with them, we might simplify the drawing by using a single line with arrows in both directions. Following is an example of a directed graph with numeric values associated with the edges:

This DLL contains the definition of a namespace Ksu.Cis300.Graphs containing a class DirectedGraph<TNode, TEdgeData> and a readonly structure Edge<TNode, TEdgeData>. It requires a DLL for Ksu.Cis300.LinkedListLibrary within the same directory. The class DirectedGraph<TNode, TEdgeData> implements a directed graph whose nodes are of type TNode, which must be non-nullable. The edges each store a data item of type TEdgeData, which may be any type. These edges can be represented using instances of the Edge<TNode, TEdgeData> structure. We also can use the DirectedGraph<TNode, TEdgeData> class to represent undirected graphs — we simply make sure that whenever there is an edge $ (u, v) $, there is also an edge $ (v, u) $ containing the same data.

The Edge<TNode, TEdgeData> structure contains the following public members:

• Edge(TNode source, TNode dest, TEdgeData data): This constructor constructs an edge leading from source to dest and having data as its data item.
• TNode Source: This property gets the source node for the edge.
• TNode Destination: This property gets the destination node for the edge.
• TEdgeData Data: This property gets the data associated with the edge.

The DirectedGraph<TNode, TEdgeData> class contains the following public members:

• DirectedGraph(): This constructor constructs a directed graph with no nodes or edges.
• void AddNode(TNode node): This method adds the given node to the graph. If this node already is in the graph, it throws an ArgumentException. If node is null, it throws an ArgumentNullException.
• void AddEdge(TNode source, TNode dest, TEdgeData value): This method adds a new edge from source to dest, with value as its associated value. If either source or dest is not already in the graph, it is automatically added. If source and dest are the same node, or if there is already an edge from source to dest, it throws an ArgumentException. If either source or dest is null, it throws an ArgumentNullException.
• bool TryGetEdge(TNode source, TNode dest, out TEdgeData? value): This method tries to get the value associated with the edge from source to dest. If this edge exists, it sets value to the value associated with this edge and returns true; otherwise, it sets value to the default value for the TEdge type and returns false.
• int NodeCount: This property gets the number of nodes in the graph.
• int EdgeCount: This property gets the number of edges in the graph.
• bool ContainsNode(TNode node): This method returns whether the graph contains the given node. If node is null, it throws an ArgumentNullException.
• bool ContainsEdge(TNode source, TNode dest): This method returns whether the graph contains an edge from source to dest.
• IEnumerable<TNode> Nodes: This property gets an enumerable collection of the nodes in the graph.
• IEnumerable<Edge<TNode, TEdgeData>> OutgoingEdges(TNode source): This method gets an enumerable collection of the outgoing edges from the given node. If source is not a node in the graph, it throws an ArgumentException. If source is null, it throws an ArgumentNullException. Otherwise, each edge in the collection returned is represented by an Edge<TNode, TEdgeData>

This implementation is somewhat limited in its utility, as nodes or edges cannot be removed, and values associated with edges cannot be changed. However, it will be sufficient for our purposes. We will examine its implementation details in a later section . For now, we will examine how it can be used.

Building a graph is straightforward using the constructor and the AddNode and/or AddEdge methods. Note that because the AddEdge method will automatically add given nodes that are not already in the graph, the AddNode method is only needed when we need to add a node that may have no incoming or outgoing edges.

For many graph algorithms, we need to process all of the edges in some way. Often the order in which we process them is important, but not in all cases. If we simply need to process all of the edges in some order we can use foreach loops with the last two members listed above to accomplish this:

• For each node in the graph:
  • For each outgoing edge from that node:
    • Process this edge.

Shortest Paths

In this section, we will consider a common graph problem — that of finding a shortest path from a node u to a node v in a directed graph. We will assume that each edge contains as its data a nonnegative number. This number may represent a physical distance or some other cost, but for simplicity, we will refer to this value as the length of the edge. We can then define the length of a path to be the sum of the lengths of all the edges along that path. A shortest path from u to v is then a path from u to v with minimum length. Thus, for example, the shortest path from a to h in the graph below is a-c-g-f-h, and its length is 4.8 + 6.4 + 4.9 + 3.2 = 19.3.

The biggest challenge in finding an algorithm for this problem is that the number of paths in a graph can be huge, even for relatively small graphs. For example, a directed graph with 15 nodes might contain almost 17 billion paths from a node u to a node v. Clearly, an algorithm that simply checks all paths would be impractical for solving a problem such as finding the shortest route between two given locations in North America. In what follows, we will present a much more efficient algorithm due to Edsger W. Dijkstra.

First, it helps to realize that when we are looking for a shortest path from u to v, we are likely to find other shortest paths along the way. Specifically, if node w is on the shortest path from u to v, then taking that same path but stopping at w gives us a shortest path from u to w. Returning to the above example, the shortest path from a to h also gives us shortest paths from a to each of the nodes c, g, and f. For this reason, we will generalize the problem to that of finding the shortest paths from a given node u to each of the nodes in the graph. This problem is known as the single-source shortest paths problem. This problem is a bit easier to think about because we can use shortest path information that we have already computed to find additional shortest path information. Then once we have an algorithm for this problem, we can easily modify it so that as soon as it finds the shortest path to our actual goal node v, we terminate it.

Dijkstra’s algorithm progresses by finding a shortest path to one node at a time. Let S denote the set of nodes to which it has found a shortest path. Initially, S will contain only u, as the shortest path from u to u is the empty path. At each step, it finds a shortest path that begins at u and ends at a node outside of S. Let’s call the last node in this path x. Certainly, if this path to x is the shortest to any node outside of S, it is also the shortest to x. The algorithm therefore adds x to S, and continues to the next step.

What makes Dijkstra’s algorithm efficient is the way in which it finds each of the paths described above. Recall that each edge has a nonnegative length. Hence, once a given path reaches some node outside of S, we cannot make the path any shorter by extending it further. We therefore only need to consider paths that remain in S until the last edge, which goes from a node in S to a node outside of S. We will refer to such edges as eligible. We are therefore looking for a shortest path whose last edge is eligible.

Suppose (w, x) is an eligible edge; i.e., w is in S, but x is not. Because w is in S, we know the length of the shortest path to w. The length of a shortest path ending in (w, x) is simply the length of the shortest path to w, plus the length of (w, x).

Let us therefore assign to each eligible edge (w, x) a priority equal to the length of the shortest path to w, plus the length of (w, x). A shortest path ending in an eligible edge therefore has a length equal to the minimum priority of any eligible edge. Furthermore, if the eligible edge with minimum priority is (w, x), then the shortest path to x is the shortest path to w, followed by (w, x).

We can efficiently find an eligible edge with minimum priority if we store all eligible edges in a MinPriorityQueue<TEdgeData, Edge<TNode, TEdgeData>>. Note however, that when we include x in S as a result of removing (w, x) from the queue, it will cause any other eligible edges leading to x to become ineligible, as x will no longer be outside of S. Because removing these edges from the min-priority queue is difficult, we will simply leave them in the queue, and discard them whenever they have minimum priority. This min-priority queue will therefore contain all eligible edges, plus some edges whose endpoints are both in S.

We also need a data structure to keep track of the shortest paths we have found. A convenient way to do this is, for each node to which we have found a shortest path, to keep track of this node’s predecessor on this path. This will allow us to retrieve a shortest path to a node v by starting at v and tracing the path backwards using the predecessor of each node until we reach u. A Dictionary<TNode, TNode> is an ideal choice for this data structure. The keys in the dictionary will be the nodes in S, and the value associated with a key will be that key’s predecessor on a shortest path. For node u, which is in S but has no predecessor on its shortest path, we can associate a value of u itself.

The algorithm begins by adding the key u with the value u to a new dictionary. Because all of the outgoing edges from u are now eligible, it then places each of these edges into the min-priority queue. Because u is the source node of each of these edges, and the shortest path from u to u has length 0, the priority of each of these edges will simply be its length.

Once the above initialization is done, the algorithm enters a loop that iterates as long as the min-priority queue is nonempty. An iteration begins by obtaining the minimum priority p from the min-priority queue, then removing an edge (w, x) with minimum priority. If x is a key in the dictionary, we can ignore this edge and go on to the next iteration. Otherwise, we add to the dictionary the key x with a value of w. Because we now have a shortest path to x, there may be more eligible edges that we need to add to the min-priority queue. These edges will be edges from x that lead to nodes that are not keys in the dictionary; however, because the min-priority queue can contain edges to nodes that are already keys, we can simply add all outgoing edges from x. Because the length of the shortest path to x is p, the priority of each of these outgoing edges is p plus the length of the outgoing edge.

Note that an edge is added to the min-priority queue only when its source is added as a key to the dictionary. Because we can only add a key once, each edge is added to the min-priority queue at most once. Because each iteration removes an edge from the min-priority queue, the min-priority queue must eventually become empty, causing the loop to terminate. When the min-priority queue becomes empty, there can be no eligible edges; hence, when the loop terminates, the algorithm has found a shortest path to every reachable node.

We can now modify the above algorithm so that it finds a shortest path from u to a given node v. Each time we add a new key to the dictionary, we check to see if this key is v; if so, we return the dictionary immediately. We might also want to return this path’s length, which is the priority of the edge leading to v. In this case, we could return the dictionary as an out parameter. Doing this would allow us to return a special value (e.g., a negative number) if we get through the loop without adding v, as this would indicate that v is unreachable. This modified algorithm is therefore as follows:

• Construct a new dictionary and a new min-priority queue.
• Add to the dictionary the key u with value u.
• If u = v, return 0.
• For each outgoing edge (u, w) from u:
  • Add (u, w) to the min-priority queue with a priority of the length of this edge.
• While the min-priority queue is nonempty:
  • Get the minimum priority p from the min-priority queue.
  • Remove an edge (w, x) with minimum priority from the min-priority queue.
  • If x is not a key in the dictionary:
    • Add to the dictionary the key x with a value of w.
    • If x = v, return p.
    • For each outgoing edge (x, y) from x:
      • Add (x, y) to the min-priority queue with priority p plus the length of (x, y).
• Return a negative value.

The above algorithm computes all of the path information we need, but we still need to extract from the dictionary the shortest path from u to v. Because the value for each key is that key’s predecessor, we can walk backward through this path, starting with v. To get the path in the proper order, we can push the nodes onto a stack; then we can remove them in the proper order. Thus, we can extract the shortest path as follows:

• Construct a new stack.
• Set the current node to v.
• While the current node is not u:
  • Push the current node onto the stack.
  • Set the current node to its value in the dictionary.
• Process u.
• While the stack is not empty:
  • Pop the top node from the stack and process it.

Unweighted Shortest Paths

In some shortest path problems, all edges have the same length. For example, we may be trying to find the shortest path out of a maze. Each cell in the maze is a node, and an edge connects two nodes if we can move between them in a single step. In this problem, we simply want to minimize the number of edges in a path to an exit. We therefore say that the edges are unweighted — they contain no explicit length information, and the length of each edge is considered to be $ 1 $.

We could of course apply Dijkstra’s algorithm to this problem, using $ 1 $ as the length of each edge. However, if analyze what this algorithm does in this case, we find that we can optimize it to achieve significantly better performance.

The optimization revolves around the use of the min-priority queue. Note that Dijkstra’s algorithm first adds all outgoing edges from the start node u to the min-priority queue, using their lengths as their priorities. For unweighted edges, each of these priorities will be $ 1 $. As the algorithm progresses it retrieves the minimum priority and removes an edge having this priority. If it adds any new edges before removing the next edge, they will all have a priority $ 1 $ greater than the priority of the edge just removed.

We claim that this behavior causes the priorities in the min-priority queue to differ by no more than $ 1 $. To see this, we will show that we can never reach a point where we change the maximum difference in priorities from at most $ 1 $ to more than $ 1 $. First observe that when the outgoing edges from u are added, the priorities all differ by $ 0 \leq 1 $. Removing an edge can’t increase the difference in the priorities stored. Suppose the edge we remove has priority $ p $. Assuming we have not yet achieved a priority difference greater than $ 1 $, any priorities remaining in the min-priority queue must be either $ p $ or $ p + 1 $. Any edges we add before removing the next edge have priority $ p + 1 $. Hence, the priority difference remains no more than $ 1 $. Because we have covered all changes to the priority queue, we can never cause the priority difference to exceed $ 1 $.

Based on the above claim, we can now claim that whenever an edge is added, its priority is the largest of any in the min-priority queue. This is certainly true when we add the outgoing edges from u, as all these edges have the same priority. Furthermore, whenever we remove an edge with priority $ p $, any edges we subsequently add have priority $ p + 1 $, which must be the maximum priority in the min-priority queue.

As a result of this behavior, we can replace the min-priority queue with an ordinary FIFO queue , ignoring any priorities. For a graph with unweighted edges, the behavior of the algorithm will be the same. Because accessing a FIFO queue is more efficient than accessing a min-priority queue, the resulting algorithm, known as breadth-first search, is also more efficient.

Implementing a Graph

Traditionally, there are two main techniques for implementing a graph. Each of these techniques has advantages and disadvantages, depending on the characteristics of the graph. In this section, we describe the implementation of the DirectedGraph<TNode, TEdgeData> class from Ksu.Cis300.Graphs.dll . This implementation borrows from both traditional techniques to obtain an implementation that provides good performance for any graph. In what follows, we will first describe the two traditional techniques and discuss the strengths and weaknesses of each. We will then outline the implementation of DirectedGraph<TNode, TEdgeData>.

The first traditional technique is to use what we call an adjacency matrix. This matrix is an $ n \times n $ boolean array, where $ n $ is the number of nodes in the graph. In this implementation, each node is represented by an int value $ i $, where $ 0 \leq i \lt n $. The value at row $ i $ and column $ j $ will be true if there is an edge from node $ i $ to node $ j $.

The main advantage to this technique is that we can very quickly determine whether an edge exists — we only need to look up one element in an array. There are several disadvantages, however. First, we are forced to use a specific range of int values as the nodes. If we wish to have a generic node type, we need an additional data structure (such as a Dictionary<TNode, int>) to map each node to its int representation. It also fails to provide a way to associate a value with an edge; hence, we would need an additional data structure (such as a TEdgeData[int, int]) to store this information.

Perhaps the most serious shortcoming for the adjacency matrix, however, is that if the graph contains a large number of nodes, but relatively few edges, it wastes a huge amount of space. Suppose, for example, that we have a graph representing street information, and suppose there are about one million nodes in this graph. We might expect the graph to contain around three million edges. However, an adjacency matrix would require one trillion entries, almost all of which will be false. Similarly, finding the edges from a given node would require examining an entire row of a million elements to find the three or four outgoing edges from that node.

The other traditional technique involves using what we call adjacency lists. An adjacency list is simply a linked list containing descriptions of the outgoing edges from a single node. These lists are traditionally grouped together in an array of size $ n $, where $ n $ is again the number of nodes in the graph. As with the adjacency matrix technique, the nodes must be nonnegative ints less than $ n $. The linked list at location $ i $ of the array then contains the descriptions of the outgoing edges from node $ i $.

One advantage to this technique is that the amount of space it uses is proportional to the size of the graph (i.e., the number of nodes plus the number of edges). Furthermore, obtaining the outgoing edges from a given node simply requires traversing the linked list containing the descriptions of these edges. Note also that we can store the data associated with an edge within the linked list cell describing that edge. However, this technique still requires some modification if we wish to use a generic node type. A more serious weakness, though, is that in order to determine if a given edge exists, we must search through potentially all of the outgoing edges from a given node. If the number of edges is large in comparison to the number of nodes, this search can be expensive.

As we mentioned above, our implementation of DirectedGraph<TNode, TEdgeData> borrows from both of these traditional techniques. We start by modifying the adjacency lists technique to use a Dictionary<TNode, LinkedListCell<TNode>?> instead of an array of linked lists. Thus, we can accommodate a generic node type while maintaining efficient access to the adjacency lists. While a dictionary lookup is not quite as efficient as an array lookup, a dictionary would provide the most efficient way of mapping nodes of a generic type to int array indices. Using a dictionary instead of an array eliminates the need to do a subsequent array lookup. The linked list associated with a given node in this dictionary will then contain the destination node of each outgoing edge from the given node.

In addition to this dictionary, we use a Dictionary<(TNode, TNode), TEdgeData> to facilitate efficient edge lookups. The notation (T1, T2) defines a tuple, which is an ordered pair of elements, the first of type T1, and the second of type T2. Elements of this type are described with similar notation, (x, y), where x is of type T1 and y is of type T2. These elements can be accessed using the public properties Item1 and Item2. In general, longer tuples can be defined similarly.

This second dictionary essentially fills the role of an adjacency matrix, while accommodating a generic node type and using space more efficiently. Specifically, a tuple whose Item1 is u and whose Item2 is v will be a key in this dictionary if there is an edge from node u to node v. The value associated with this key will be the data associated with this edge. Thus, looking up an edge consists of a single dictionary lookup.

The two dictionaries described above are the only private fields our implementation needs. We will refer to them as _adjacencyLists and _edges, respectively. Because we can initialize both fields to new dictionaries, there is no need to define a constructor. Furthermore, given these two dictionaries, most of the public methods and properties (see “Introduction to Graphs” ) can be implemented using a single call to one of the members of one of these dictionaries:

• void AddNode(TNode node): We can implement this method using the Add method of _adjacencyLists. We associate an empty linked list with this node.
• void AddEdge(TNode source, TNode dest, TEdgeData value): See below.
• bool TryGetEdge(TNode source, TNode dest, out TEdgeData? value): We can implement this method using the TryGetValue method of _edges.
• int NodeCount: Because _adjacencyLists contains all of the nodes as keys, we can implement this property using this dictionary’s Count property.
• int EdgeCount: We can implement this property using the Count property of _edges.
• bool ContainsNode(TNode node): We can implement this method using the ContainsKey method of _adjacencyLists.
• bool ContainsEdge(TNode source, TNode dest): We can implement this method using the ContainsKey method of _edges.
• IEnumerable<TNode> Nodes: We can implement this property using the Keys property of _adjacencyLists.
• IEnumerable<Edge<TNode, TEdgeData>> OutgoingEdges(TNode source): See below.

Let’s now consider the implementation of the AddEdge method. Recall from “Introduction to Graphs” that this method adds an edge from source to dest with data item value. If either source or dest is not already in the graph, it will be added. If either source or dest is null, it will throw an ArgumentNullException. If source and dest are the same, or if the edge already exists in the graph, it will throw an ArgumentException.

In order to avoid changing the graph if the parameters are bad, we should do the error checking first. However, there is no need to check whether the edge already exists, provided we update _edges using its Add method, and that we do this before making any other changes to the graph. Because a dictionary’s Add method will throw an ArgumentException if the given key is already in the dictionary, it takes care of this error checking for us. The key that we need to add will be a (TNode, TNode) containing the two nodes, and the value will be the value.

After we have updated _edges, we need to update _adjacencyLists. To do this, we first need to obtain the linked list associated with the key source in _adjacencyLists; however, because source may not exist as a key in this dictionary, we should use the TryGetValue method to do this lookup (note that if source is not a key in this dictionary, the out parameter will be set to null, which we can interpret as an empty list). We then construct a new linked list cell containing dest as its data and insert it at the beginning of the linked list we retrieved. We then set this linked list as the new value associated with source in _adjacencyLists. Finally, if _adjacencyLists doesn’t already contain dest as a key, we need to add it with null as its associated value.

Finally, we need to implement the OutgoingEdges method. Because this method returns an IEnumerable<Edge<TNode, TEdgeData>>, it needs to iterate through the cells of the linked list associated with the given node in _adjacencyLists. For each of these cells, it will need to yield return (see “Enumerators ”) an Edge<TNode, TEdgeData> describing the edge represented by that cell. The source node for this edge will be the node given to this method. The destination node will be the node stored in the cell. The edge data can be obtained from the dictionary _edges.

Select Sorts

A select sort operates by repeatedly selecting the smallest data element of an unsorted portion of the array and moving it to the end of a sorted portion. Thus, at each step, the data items will be arranged into two parts:

1. A sorted part; and
2. An unsorted part in which each element is at least as large as all elements in the sorted part.

The following figure illustrates this arrangement.

Initially, the sorted part will be empty. At each step, the unsorted part is rearranged so that its smallest element comes first. As a result, the sorted part can now contain one more element, and the unsorted part one fewer element. After $ n - 1 $ steps, where $ n $ is the number of elements in the array, the sorted part will have all but one of the elements. Because the one element in the unsorted part must be at least as large as all elements in the sorted part, the entire array will be sorted at this point.

The approach outlined above can be implemented in various ways. The main difference in these implementations is in how we rearrange the unsorted part to bring its smallest element to the beginning of that part. The most straightforward way to do this is to find the smallest element in this part, then swap it with the first element in this part. The resulting algorithm is called selection sort. It requires nested loops. The outer loop index keeps track of how many elements are in the sorted part. The unsorted part then begins at this index. The inner loop is responsible for finding the smallest element in the unsorted part. Once the inner loop has finished, the smallest element is swapped with the first element in the unsorted part.

Note that the inner loop in selection sort iterates once for every element in the unsorted part. On the first iteration of the outer loop, the unsorted part contains all $ n $ elements. On each successive iteration, the unsorted part is one element smaller, until on the last iteration, it has only $ 2 $ elements. If we add up all these values, we find that the inner loop iterates a total of exactly $ (n - 1)(n + 2)/2 $ times. This value is proportional to $ n^2 $ as $ n $ increases; hence, the running time of the algorithm is in $ O(n^2) $. Furthermore, this performance occurs no matter how the data items are initially arranged.

As we will see in what follows, $ O(n^2) $ performance is not very good if we want to sort a moderately large data set. For example, sorting $ 100,000 $ elements will require about $ 5 $ billion iterations of the inner loop. On the positive side, the only time data items are moved is when a swap is made at the end of the outer loop; hence, this number is proportional to $ n $. This could be advantageous if we are sorting large value types, as we would not need to write these large data elements very many times. However, for general performance reasons, large data types shouldn’t be value types — they should be reference types to avoid unnecessary copying of the values. For this reason, selection sort isn’t a particularly good sorting algorithm.

Performance issues aside, however, there is one positive aspect to selection sort. This aspect has to do with sorting by keys. Consider, for example, the rows of a spreadsheet. We often want to sort these rows by the values in a specific column. These values are the sort keys of the elements. In such a scenario, it is possible that two data elements are different, but their sort keys are the same. A sorting algorithm might reverse the order of these elements, or it might leave their order the unchanged. In some cases, it is advantageous for a sorting algorithm to leave the order of these elements unchanged. For example, if we sort first by a secondary key, then by a primary key, we would like for elements whose primary keys are equal to remain sorted by their secondary key. Therefore, a sorting algorithm that always maintains the original order of equal keys is said to be stable. If we are careful how we implement the inner loop of selection sort so that we always select the first instance of the smallest key, then this algorithm is stable.

Another implementation of a select sort is bubble sort. It rearranges the unsorted part by swapping adjacent elements that are out of order. It starts with the last two elements (i.e., the elements at locations $ n - 1 $ and $ n - 2 $), then the elements at locations $ n - 2 $ and $ n - 3 $, etc. Proceeding in this way, the smallest element in the unsorted part will end up at the beginning of the unsorted part. While the inner loop is doing this, it keeps track of whether it has made any swaps. If the loop completes without having made any swaps, then the array is sorted, and the algorithm therefore stops.

Like selection sort, bubble sort is stable. In the worst case, however, the performance of bubble sort is even worse than that of selection sort. It is still in $ O(n^2) $, but in the worst case, its inner loop performs the same number of iterations, but does a lot more swaps. Bubble sort does outperform selection sort on some inputs, but describing when this will occur isn’t easy. For example, in an array in which the largest element occurs in the first location, and the remaining locations are sorted, the performance ends up being about the same as selection sort — even though this array is nearly sorted. Like selection sort, it is best to avoid bubble sort.

A select sort that significantly outperforms selection sort is known as heap sort. This algorithm is based on the idea that a priority queue can be used to sort data — we first place all items in a priority queue, using the values themselves as priorities (if we are sorting by keys, then we use the keys as priorities). We then repeatedly remove the element with largest priority, filling the array from back to front with these elements.

We can optimize the above algorithm by using a priority queue implementation called a binary heap, whose implementation details we will only sketch. The basic idea is that we can form a binary tree from the elements of an array by using their locations in the array. The first element is the root, its children are the next two elements, their children are the next four elements, etc. Given an array location, we can then compute the locations of its parent and both of its children. The priorities are arranged so that the root of each subtree contains the maximum priority in that subtree. It is possible to arrange the elements of an array into a binary heap in $ O(n) $ time, and to remove an element with maximum priority in $ O(\lg n) $ time.

Heap sort then works by pre-processing the array to arrange it into a binary heap. The binary heap then forms the unsorted part, and it is followed by the sorted part, whose elements are all no smaller than any element in the unsorted part. While this arrangement is slightly different from the arrangement for the first two select sorts, the idea is the same. To rearrange the unsorted part, it:

1. Copies the first (i.e., highest-priority) element to a temporary variable.
2. Removes the element with maximum priority (i.e., the first element).
3. Places the copy of the first element into the space vacated by its removal at the beginning of the sorted part.

Heap sort runs in $ O(n \lg n) $ time in the worst case. Information theory can be used to prove that any sorting algorithm that sorts by comparing elements must make at least $ \lg(n!) $ comparisons on some arrays of size $ n $. Because $ \lg(n!) $ is proportional to $ n \lg n $, we cannot hope to do any better than $ O(n \lg n) $ in the worst case. While this performance is a significant improvement over selection sort and bubble sort, we will see in later that there is are algorithms that do even better in practice. Furthermore, heap sort is not stable.

On the other hand, we will also see that heap sort is an important component of an efficient hybrid algorithm. This algorithm is one of the best general-purpose sorting algorithms; in fact, it is used by .NET’s Array.Sort method. We will examine this approach in “Hybrid Sorts ”.

Insert Sorts

An insert sort operates by repeatedly inserting an element into a sorted portion of the array. Thus, as for select sorts, at each step the data items will be arranged into a sorted part, followed by an unsorted part; however, for insert sorts, there is no restriction on how elements in the unsorted part compare to elements in the sorted part. The following figure illustrates this arrangement.

Initially, the sorted part will contain the first element, as a single element is always sorted. At each step, the first element in the unsorted part is inserted into its proper location in the sorted part. As a result, the sorted part now contains one more element, and the unsorted part one fewer element. After $ n - 1 $ steps, where $ n $ is the number of elements in the array, the sorted part will contain all the elements, and the algorithm will be done.

Again, this approach can be implemented in various ways. The main difference in these implementations is in how we insert an element. The most straightforward way is as follows:

1. Copy the first element of the unsorted part to a temporary variable.
2. Iterate from the location of the first element of the unsorted part toward the front of the array as long as we are at an index greater than 0 and the element to the left of the current index is greater than the element in the temporary variable. On each iteration:
   • Copy the element to the left of the current index to the current index.
3. Place the value in the temporary variable into the location at which the above loop stopped.

The algorithm that uses the above insertion technique is known as insertion sort. Like selection sort, it requires an outer loop to keep track of the number of elements in the sorted part. Each iteration of this outer loop performs the above insertion algorithm. It is not hard to see that this algorithm is stable .

The main advantage insertion sort has over selection sort is that the inner loop only iterates as long as necessary to find the insertion point. In the worst case, it will iterate over the entire sorted part. In this case, the number of iterations is the same as for selection sort; hence, the worst-case running time is in $ O(n^2) $ — the same as selection sort and bubble sort . At the other extreme, however, if the array is already sorted, the inner loop won’t need to iterate at all. In this case, the running time is in $ O(n) $, which is the same as the running time of bubble sort on an array that is already sorted.

Unlike bubble sort, however, insertion sort has a clean characterization of its performance based on how sorted the array is. This characterization is based on the notion of an inversion, which is a pair of array locations $ i \lt j $ such that the value at location $ i $ is greater than the value at location $ j $; i.e., these two values are out of order with respect to each other. A sorted array has no inversions, whereas in an array of distinct elements in reverse order, every pair of locations is an inversion, for a total of $ n(n - 1)/2 $ inversions. In general, we can say that the fewer inversions an array has, the more sorted it is.

The reason why inversions are important to understanding the performance of insertion sort is that each iteration of the inner loop (i.e., step 2 of the insertion algorithm above) removes exactly one inversion. Consequently, if an array initially has $ k $ inversions, the inner loop will iterate a total of $ k $ times. If we combine this with the $ n - 1 $ iterations of the outer loop, we can conclude that the running time of insertion sort is in $ O(n + k) $. Thus, if the number of inversions is relatively small in comparison to $ n $ (i.e., the array is nearly sorted), insertion sort runs in $ O(n) $ time. (By contrast, $ n - 2 $ inversions can be enough to cause the inner loop of bubble sort to iterate its worst-case number of times.) For this reason, insertion sort is the algorithm of choice when we expect the data to be nearly sorted — a scenario that occurs frequently in practice. This fact is exploited by an efficient hybrid algorithm that combines insertion sort with two other sorting algorithms - see “Hybrid Sorting Algorithms ” for more details.

Before we consider another insert sort, there is one other advantage to insertion sort that we need to consider. Because the algorithm is simple (like selection sort and bubble sort), it performs well on small arrays. More complex algorithms like heap sort , while providing much better worst-case performance for larger arrays, don’t tend to perform as well on small arrays. In many cases, the performance difference on small arrays isn’t enough to matter, as pretty much any algorithm will perform reasonably well on a small array. However, this performance difference can become significant if we need to sort many small arrays (in a later section, we will see an application in which this scenario occurs). Because insertion sort tends to out-perform both selection sort and bubble sort, it is usually the best choice when sorting small arrays.

Another way to implement an insert sort is to use a balanced binary search tree, such as an AVL tree , to store the sorted part. In order to do this, we need to modify the definition of a binary search tree to allow multiple instances of the same key. In order to achieve stability, if we are inserting a key that is equal to a key already in the tree, we would treat the new key as being greater than the pre-existing key - i.e., we would recursively insert it into the right child. Once all the data items are inserted, we would then copy them back into the array in sorted order using an inorder traversal . We call this algorithm tree sort.

This algorithm doesn’t exactly match the above description of an insert sort, but it is not hard to see that it follows the same general principles. While the sorted portion is not a part of the array, but instead is a separate data structure, it does hold an initial part of the array in sorted order, and successive elements from the unsorted portion are inserted into it.

Because insertions into an AVL tree containing $ k $ elements can be done in $ O(\lg k) $ time in the worst case, and because an inorder traversal can be done in $ O(k) $ time, it follows that tree sort runs in $O(n \lg n)$ time in the worst case, where $ n $ is the number of elements in the array. However, because maintaining an AVL tree requires more overhead than maintaining a binary heap, heap sort tends to give better performance in practice. For this reason, tree sort is rarely used.

Merge Sorts

A merge sort works by merging together two sorted parts of an array. Thus, we should focus our attention on an array that is partitioned into two sorted parts, as shown in the following figure.

The different ways of implementing a merge sort depend both on how the above arrangement is achieved, and also on how the two parts are merged together. The simplest implementation is an algorithm simply called merge sort.

Merge sort uses recursion to arrange the array into two sorted parts. In order to use recursion, we need to express our algorithm, not in terms of sorting an array, but instead in terms of sorting a part of an array. If the part we are sorting has more than one element, then we can split it into two smaller parts of roughly equal size (if it doesn’t have more than one element, it is already sorted). Because both parts are smaller, we can recursively sort them to achieve the arrangement shown above.

The more complicated step in merge sort is merging the two sorted parts into one. While it is possible to do this without using another array (or other data structure), doing so is quite complicated. Merge sort takes a much simpler approach that uses a temporary array whose size is the sum of the sizes of the two sorted parts combined. It first accumulates the data items into the new array in sorted order, then copies them back into the original array.

In order to understand how the merging works, let’s consider a snapshot of an arbitrary step of the algorithm. If we’ve accumulated an initial portion of the result, these elements will be the smallest ones. Because both of the parts we are merging are sorted, these smallest elements must come from initial portions of these two parts, as shown below.

Initially, the three shaded areas above are all empty. In order to proceed, we need local variables to keep track of the first index in each of the three unshaded areas. We then iterate as long as both of the unshaded areas are nonempty. On each iteration, we want to place the next element into the temporary array. This element needs to be the smallest of the unmerged elements. Because both parts of the given array are sorted, the smallest unmerged element will be the first element from one of the two unshaded parts of this array — whichever one is smaller (for stability, we use the first if they are equal). We copy that element to the beginning of the unshaded portion of the temporary array, then update the local variables to reflect that we have another merged item.

The above loop will terminate as soon as we have merged all the data items from one of the two sorted parts; however, the other sorted part will still contain unmerged items. To finish merging to the temporary array, we just need to copy the remaining items to the temporary array. We can do this by first copying all remaining items from the first sorted part, then copying all remaining items from the second sorted part (one of these two copies will copy nothing because there will be no remaining items in one of the two sorted parts). Once all items have been merged into the temporary array, we copy all items back to the original array to complete the merge.

We won’t do a running time analysis here, but merge sort runs in $ O(n \lg n) $ time in the worst case. Furthermore, unlike heap sort , it is stable. Because it tends to perform better in practice than tree sort , it is a better choice when we need a stable sorting algorithm. In fact, it is the basis (along with insertion sort ) of a stable hybrid sorting algorithm that performs very well in practice. This algorithm, called Tim sort, is rather complicated; hence, we won’t describe it here. If we don’t need a stable sorting algorithm, though, there are other alternatives, as we shall see in the next two sections.

Another scenario in which a merge sort is appropriate occurs when we have a huge data set that will not fit into an array. In order to sort such a data set, we need to keep most of the data in files while keeping a relatively small amount within internal data structures at any given time. Because merging processes data items sequentially, it works well with files. There are several variations on how we might do this, but the basic algorithm is called external merge sort.

External merge sort uses four temporary files in addition to an input file and an output file. Each of these files will alternate between being used for input and being used for output. Furthermore, at any given time, one of the two files being used for input will be designated as the first input file, and the other will designated as the second input file. Similarly, at any given time, one of the two files being used for output will be designated as the current output file, and the other will be designated as the alternate output file.

The algorithm begins with an initialization step that uses the given unsorted data file as its input, and two of the temporary files as its output. We will need two variables storing references to the current output file and the alternate output file, respectively. At this point we begin a loop that iterates until we reach the end of the input. Each iteration of this loop does the following:

1. Fill a large array with data items from the input (if there aren’t enough items to fill this array, we just use part of it).
2. Sort this array using whatever sorting algorithm is appropriate.
3. Write each element of the sorted array to the current output file.
4. Write a special end marker to the output file.
5. Swap the contents of the variables referring to the current output file and the alternate output file.

After the above loop terminates, the two output files are closed. Thus, the initialization writes several sorted sequences, each terminated by end markers, to the two output files. Furthermore, either the two output files will contain the same number of sorted sequences or the one that was written to first will contain one more sorted sequence than the other. The following figure illustrates these two files.

The algorithm then enters the main loop. Initially the output file first written in the initialization is designated as the first input file, and the other file written in the initialization is designated as the second input file. The other two temporary files are arbitrarily designated as the current output file and the alternate output file. The loop then iterates as long as the second input file is nonempty. Each iteration does the following:

1. While there is data remaining in the second input file:
   1. Merge the next sorted sequence in the first input file with the next sorted sequence in the second input file, writing the result to the current output file (see below for details).
   2. Write an end marker to the current output file.
   3. Swap the current output file and the alternate output file.
2. If there is data remaining in the first input file:
   1. Copy the remaining data from the first input file to the current output file
   2. Write an end marker to the current output file.
   3. Swap the current output file and the alternate output file.
3. Close all four temporary files.
4. Swap the first input file with the alternate output file.
5. Swap the second input file with the current output file.

Each iteration therefore combines pairs of sorted sequences from the two input files, thus reducing the number of sorted sequences by about half. Because it alternates between the two output files, as was done in the initialization, either the two output files will end up with the same number of sequences, or the last one written (which will be the alternate output file following step 2) will have one more than the other. The last two steps therefore ensure that to begin the next iteration, if the the number of sequences in the two input files is different, the first input file has the extra sequence.

The loop described above finishes when the second input file is empty. Because the first input file will have no more than one more sorted sequence than the second input file, at the conclusion of the loop, it will contain a single sorted sequence followed by an end marker. The algorithm therefore concludes by copying the data from this file, minus the end marker, to the output file.

Let’s now consider more carefully the merge done in step 1a above. This merge is done in essentially the same way that the merge is done in the original merge sort; however, we don’t need to read in the entire sorted sequences to do it. Instead, all we need is the next item from each sequence. At each step, we write the smaller of the two, then read the next item from the appropriate input file. Because we only need these two data items at any time, this merge can handle arbitrarily long sequences.

For an external sorting algorithm, the most important measure of performance is the number of file I/O operations it requires, as these operations are often much more expensive than any other (depending, of course, on the storage medium). Suppose the initial input file has $ n $ data items, and suppose the array we use in the initialization step can hold $ m $ data items. Then the number of sorted sequences written by the initialization is $ n/m $, with any fractional part rounded up. Each iteration of the main loop then reduces the number of sorted sequences by half, with any fractional part again rounded up. The total number of iterations of the main loop is therefore $ \lg (n/m) $, rounding upward again. Each iteration of this loop makes one pass through the entire data set. In addition, the initialization makes one pass, and the final copying makes one pass. The total number of passes through the data is therefore $ \lg (n/m) + 2 $. For example, if we are sorting $ 10 $ billion data items using an array of size $ 1 $ million, we need $ \lg 10,000 + 2 $ passes, rounded up; i.e., we need $ 16 $ passes through the data.

Various improvements can be made to reduce the number of passes through the data. For example, we can avoid the final file copy if we use another mechanism for denoting the end of a sorted sequence. One alternative is to keep track of the length of each sequence in each file in a List<long>. If the temporary files are within the same directory as the output file, we can finish the sort by simply renaming the first input file, rather than copying it.

A more substantial improvement involves using more temporary files. $ k $-way external merge sort uses $ k $ input and $ k $ output files. Each merge then merges $ k $ sorted sequences into $ 1 $. This reduces the number of iterations of the main loop to $ \log_k (n/m) $. Using the fact that $ \log_{k^2} n = (\log_k n)/2 $, we can conclude that squaring $ k $ will reduce the number of passes through the data by about half. Thus, $ 4 $-way external merge sort will make about half as many passes through the data as $ 2 $-way external merge sort. The gain diminishes quickly after that, however, as we must increase $ k $ to $ 16 $ to cut the number of passes in half again.

Split Sorts

A split sort operates by splitting the array into three parts:

• An unsorted part containing elements less than or equal to some pivot element p.
• A nonempty part containing elements equal to p.
• An unsorted part containing elements greater than or equal to p.

This arrangement is illustrated in the following figure.

To complete the sort, it then sorts the two unsorted parts. Note that because the second part is nonempty, each of the two unsorted parts is smaller than the original data set; hence, the algorithm will always make progress.

The various implementations of a split sort are collectively known as quick sort. They differ in how many elements are placed in the middle part (only one element or all elements equal to the pivot), how the pivot is chosen, how the elements are partitioned into three parts, and how the two sub-problems are sorted. We will examine only two variations, which differ in how the pivot element is chosen.

Let’s start with how we do the partitioning. Let p denote the pivot element. Because most of the split sort implementations use recursion to complete the sort, we’ll assume that we are sorting a portion of an array. At each stage of the partitioning, the array portion we are sorting will be arranged into the following four segments:

1. Segment L: Elements less than p.
2. Segment U: Elements we haven’t yet examined (i.e., unknown elements).
3. Segment E: Elements equal to p.
4. Segment G: Elements greater than p.

Initially, segments L, E, and G will be empty, and each iteration will reduce the size of segment U. The partitioning will be finished when segment U is empty. We will need three local variables to keep track of where one segment ends and another segment begins, as shown in the following figure:

We have worded the descriptions of the three local variables so that they make sense even if some of the segments are empty. Thus, because all segments except U are initially empty, the location following segment L will initially be the first location in the array portion that we are sorting, and the other two variables will initially be the last location in this portion. We then need a loop that iterates as long as segment U is nonempty — i.e., as long as the location following segment L is no greater than the location preceding segment E. Each iteration of this loop will compare the last element in segment U (i.e., the element at the location preceding segment E) with p. We will swap this element with another depending on how it compares with p:

• If it is less than p, we swap it with the element following segment L, and adjust the end of segment L to include it.
• If it is equal to p, we leave it where it is, and adjust the beginning of segment E to include it.
• If it is greater than p, we swap it with the element preceding segment G, adjust the beginning of segment G to include it, and adjust the beginning of segment E to account for the fact that we are shifting this segment to the left by 1.

Once this loop completes, the partitioning will be done. Furthermore, we can determine the two parts that need to be sorted from the final values of the local variables.

The first split sort implementation we will consider is fairly straightforward, given the above partitioning scheme. If we are sorting more than one element (otherwise, there is nothing to do), we will use as the pivot element the first element of the array portion to be sorted. After partitioning, we then sort the elements less than the pivot using a recursive call, and sort the elements greater than the pivot with another.

Though we won’t give an analysis here, the above algorithm runs in $ O(n^2) $ time in the worst case, where $ n $ is the number of elements being sorted. However, as we saw with insertion sort , the worst-case running time doesn’t always tell the whole story. Specifically, the expected running time of quick sort (this implementation and others) on random arrays is in $ O(n \lg n) $.

However, we don’t often need to sort random data. Let’s therefore take a closer look at what makes the worst case bad. In some ways this algorithm is like merge sort — it does two recursive calls, and the additional work is proportional to the number of elements being sorted. The difference is that the recursive calls in merge sort are both on array portions that are about half the size of the portion being sorted. With this quick sort implementation, on the other hand, the sizes of the recursive calls depend on how the first element (i.e., the pivot element) compares to the other elements. The more elements that end up in one recursive call, the slower the algorithm becomes. Consequently, the worst case occurs when the array is already sorted, and is still bad if the array is nearly sorted. For this reason, this is a particularly bad implementation.

Before we look at how we can improve the performance, we need to consider one other aspect of this implementation’s performance. For a recursive method, the amount of data pushed on the runtime stack is proportional to the depth of the recursion. In the worst cases (i.e., on a sorted array), the recursion depth is $ n $. Thus, for large $ n $, if the array is sorted or nearly sorted, a StackOverflowException is likely.

The most important thing we can do to improve the performance, in terms of both running time and stack usage, is to be more careful about how we choose the pivot element. We want to choose an element that partitions the data elements roughly in half. The median element (i.e., the element that belongs in the middle after the array is sorted) will therefore give us the optimal split. It is possible to design an $ O(n \lg n) $ algorithm that uses the median as the pivot; however, the time it takes to find the median makes this algorithm slower than merge sort in practice. It works much better to find a quick approximation for the median.

The main technique for obtaining such an approximation is to examine only a few of the elements. For example, we can use median-of-three partitioning, which uses as its pivot element the median of the first, middle, and last elements of the array portion we are sorting. An easy way to implement this strategy is to place these three elements in an array of size 3, then sort this array using insertion sort . The element that ends up at location 1 is then the used as the pivot.

We can improve on the above strategy by doing a case analysis of the three values. If we do this, we don’t need a separate array — we just find the median of three values, $ a $, $ b $, and $ c $, as follows:

• If $ a \lt b $:
  • If $ b \lt c $, then $ b $ is the median.
  • Otherwise, because $ b $ is the largest:
    • If $ a \lt c $, then $ c $ is the median.
    • Otherwise, $ a $ is the median.
• Otherwise, because $ b \leq a $:
  • If $ a \lt c $, then $ a $ is the median.
  • Otherwise, because $ a $ is the largest:
    • If $ b \lt c $, then $ c $ is the median.
    • Otherwise, $ b $ is the median.

The above algorithm is quite efficient, using at most three comparisons and requiring no values to be copied other than the result if we implement it in-line, rather than as a separate method (normally an optimizing compiler can do this method inlining for us). It also improves the sorting algorithm by tending to make the bad cases less likely.

This version of quick sort gives good performance most of the time, typically outperforming either heap sort or merge sort . However, it still has a worst-case running time in $ O(n^2) $ and a worst-case stack usage in $ O(n) $. Furthermore, it is unstable and does not perform as well as insertion sort on small or nearly sorted data sets. In the next section , we will show how quick sort can be combined with some of the other sorting algorithms to address some of these issues, including the bad worst-case performance.

Hybrid Sorting Algorithms

The best versions of quick sort are competitive with both heap sort and merge sort on the vast majority of inputs. However, quick sort has a very bad worst case — $ O(n^2) $ running time and $ O(n) $ stack usage. By comparison, both heap sort and merge sort have $ O(n \lg n) $ worst-case running time, together with a stack usage of $ O(1) $ for heap sort or $ O(\lg n) $ for merge sort. Furthermore, insertion sort performs better than any of these algorithms on small data sets. In this section, we look at ways to combine some of these algorithms to obtain a sorting algorithm that has the advantages of each of them.

We will start with quick sort, which gives the best performance for most inputs. One way of improving its performance is to make use of the fact that insertion sort is more efficient for small data sets. Improving the performance on small portions can lead to significant performance improvements for large arrays because quick sort breaks large arrays into many small portions. Hence, when the portion we are sorting becomes small enough, rather than finding a pivot and splitting, we instead call insertion sort.

An alternative to the above improvement is to use the fact that insertion sort runs in $ O(n) $ time when the number of inversions is linear in the number of array elements. To accomplish this, we modify quick sort slightly so that instead of sorting the array, it brings each element near where it belongs. We will refer to this modified algorithm as a partial sort. After we have done the partial sort, we then sort the array using insertion sort. The modification we make to quick sort to obtain the partial sort is simply to change when we stop sorting. We only sort portions that are larger than some threshold — we leave other portions unsorted.

Suppose, for example, that we choose a threshold of $ 10 $. Once the partial sort reaches an array portion with nine or fewer elements, we do nothing with it. Note, however, that these elements are all larger than the elements that precede this portion, and they are all smaller than the elements that follow this portion; hence, each element can form an inversion with at most eight other elements — the other elements in the same portion. Because each inversion contains two elements, this means that there can be no more than $ 4n $ inversions in the entire array once the partial sort finishes. The subsequent call to insertion sort will therefore finish the sorting in linear time.

Both of the above techniques yield performance improvements over quick sort alone. In fact, for many years, such combinations of an optimized version of quick sort with insertion sort were so efficient for most inputs that they were the most commonly-used algorithms for general-purpose sorting. On modern hardware architectures, the first approach above tends to give the better performance.

Nevertheless, neither of the above approaches can guarantee $ O(n \lg n) $ performance — in the worst case, they are all still in $ O(n^2) $. Furthermore, the bad cases still use linear stack space. To overcome these shortfalls, we can put a limit on the depth of recursion. Once this limit is reached, we can finish sorting this portion with an $ O(n \lg n) $ algorithm such as heap sort . The idea is to pick a limit that is large enough that it is rarely reached, but still small enough that bad cases will cause the alternative sort to be invoked before too much time is spent. A limit of about $ 2 \lg n $, where $ n $ is the size of the entire array, has been suggested. Because arrays in C# must have fewer than $ 2^{31} $ elements, this value is always less than $ 62 $; hence, it is also safe to use a constant for the limit. The resulting algorithm has a worst-case running time in $ O(n \lg n) $ and a worst-case stack usage of $ O(\lg n) $. This logarithmic bound on the stack usage is sufficient to avoid a StackOverflowException.

The combination of quick sort using median-of-three partitioning with insertion sort for small portions and heap sort when the recursion depth limit is reached is known as introsort (short for introspective sort). Other improvements exist, but we will not discuss them here. The best versions of introsort are among the best sorting algorithms available, unless the array is nearly sorted. Of course, if the data won’t fit in an array, we can’t use introsort — we should use external merge sort instead. Furthermore, like quick sort and heap sort, introsort is not stable. When a stable sort is not needed, however, and when none of the above special cases applies, introsort is one of the best choices available.

Sorting Strings

We conclude our discussion of sorting with a look at a sorting algorithm designed specifically for sorting multi-keyed data. In such data there is a primary key, a secondary key, and so on. We want to sort the data so that element a precedes element b if:

• the primary key of a is less than the primary key of b;
• or their primary keys are equal, but the secondary key of a is less than the secondary key of b;
• etc.

An example of multi-keyed data is strings. The first character of a string is its primary key, its second character is its secondary key, and so on. The only caveat is that the strings may not all have the same length; hence, they may not all have the same number of keys. We therefore stipulate that a string that does not have a particular key must precede all strings that have that key.

One algorithm to sort multi-keyed data is known as multi-key quick sort. In this section, we will describe multi-key quick sort as it applies specifically to sorting strings; however, it can be applied to other multi-keyed data as well.

One problem with sorting strings using a version of quick sort described in “Split Sorts ” is that string comparisons can be expensive. Specifically, they must compare the strings a character at a time until they reach either a mismatch or the end of a string. Thus, comparing strings that have a long prefix in common is expensive. Now observe that quick sort operates by splitting the array into smaller and smaller pieces whose elements belong near each other in the sorted result. It is therefore common to have some pieces whose elements all begin with the same long prefix.

Multi-key quick sort improves the performance by trying to avoid comparing prefixes after they have already been found to be the same (though the suffixes may differ). In order to accomplish this, it uses an extra int parameter k such that all the strings being sorted match in their first k positions (and by implication, all strings have length at least k). We can safely use a value of 0 in the initial call, but this value can increase as recursive calls are made.

Because all strings begin with the same prefix of length k, we can focus on the character at location k (i.e., following the first k characters) of each string. We need to be careful, however, because some of the strings may not have a character at location k. We will therefore use an int to store the value of the character at location k of a string, letting $ -1 $ denote the absence of a character at that location. We can also let $ -2 $ denote a null element, so that these elements are placed before all non-null elements in the sorted result.

The algorithm then proceeds a lot like those described in “Split Sorts ”. If the number of elements being sorted is greater than $ 1 $, a pivot element p is found. Note that p is not a string, but an int representing a character at location k, as described above. The elements are then partitioned into groups of strings whose character at location k is less than p, equal to p, or greater than p, respectively.

After these three groups are formed, the first and third group are sorted recursively using the same value for k. Furthermore, the second group may not be completely sorted yet — all we know is that all strings in this group agree on the first k + 1 characters. Thus, unless p is negative (indicating that either these strings are all null or they all have length k, and are therefore all equal), we need to recursively sort this group as well. However, because we know that the strings in this group all agree on the first k + 1 characters, we pass k + 1 as the last parameter.

One aspect of this algorithm that we need to address is whether the recursion is valid. Recall that when we introduced recursion , we stated that in order to guarantee termination, all recursive calls must be on smaller problem instances, where the size of a problem instance is given by a nonnegative integer. In the algorithm described above, we might reach a point at which all of the strings being sorted match in location k. In such a case, the second recursive call will contain all of the strings.

By being careful how we define the size of the problem instance, however, we can show that this recursion is, in fact, valid. Specifically, we define the size of the problem instance to be the number of strings being sorted, plus the total number of characters beginning at location k in all strings being sorted. Because there is at least one string containing p at location k, the number of strings in both the first and the third recursive call must be smaller, while the total number of characters beginning at location k can be no larger. Because k increases by $ 1 $ in the second recursive call, the total number of characters past this location must be smaller, while the number of strings can be no larger. Hence, the size decreases in all recursive calls.

The fact that we are doing recursion on the length of strings, however, can potentially cause the runtime stack to overflow when we are sorting very long strings. For this reason, it is best to convert the recursive call on the second group to a loop. We can do this by changing the if-statement that controls whether the splitting will be done into a while-loop that iterates as long as the portion being sorted is large enough to split. Then at the bottom of the loop, after doing recursive calls on the first and third parts, we check to see if p is $ -1 $ — if so, we exit the loop. Otherwise, we do the following:

• increment k;
• change the index giving the start of the portion we are sorting to the beginning of the second part; and
• change the length of the portion we are sorting to the length of the second part.

The next iteration will then sort the second part.

This algorithm can be combined with insertion sort and heap sort , as was done for introsort in the previous section . However, we should also modify insertion sort and heap sort to use the information we already have about equal prefixes when we are comparing elements. Specifically, rather than comparing entire strings, we should begin comparing after the equal prefix. Because of the way multi-key quick sort does comparisons, the result tends to perform better than the single-key versions, assuming similar optimizations are made; however, cutoffs for running insertion sort and/or heap sort may need to be adjusted.

C# Syntax

This chapter discusses various C# features that are either unavailable in Java or are unlikely to have been covered in an introductory Java programming class. No attempt has been made to be exhaustive. Instead, we focus mainly on those features that are likely to be needed in CIS 300. In addition, the following topics are covered in the main text, rather than in this appendix:

• Generic Types
• Interfaces
• Overriding virtual Methods
• Operator Overloading
• The using Statement
• Equality
• Type Casting