Week 5: Notes

inheritance

C# supports inheritance, a mechanism that allows a class to extend another class and to change its behavior. We have already seen inheritance in Programming 1, where we discussed inheritance between classes in Python. However we will emphasize inheritance more in Programming 2. Inheritance plays a major role in the C# collection class library and in other popular class libraries such as graphical interface toolkits. Furthermore, in Programming 2 we'll start to write larger programs in which we may have our own uses for inheritance.

Consider a simple C# class that implements a fixed-size stack of values of type int:

class IntStack {
    int[] a;
    int n;

    public IntStack(int limit) {
        a = new int[limit];
    }

    public int count => n;

    public void push(int i) {
        a[n++] = i;
    }

    public int pop() => a[--n];

    public int this[int i] => a[n - 1 - i];

    public static bool operator ! (IntStack s) =>
        s.count == 0;
}

Notice that our class contains

• a property count that returns the number of items currently on the stack

• an indexer that returns an item by index, where s[0] is the top item on the stack, s[1] is the second item from the top, and so on

• a unary overloaded operator !, where !s is true if the stack s is empty

We'd now like to write a class AvgStack that is like IntStack, but has an additional property avg that can report the average value of the numbers that are currently on the stack. We'd like avg to run in O(1). To achieve that, AvgStack will keep track of the current total of all numbers on the stack. (As you may recall, we saw a similar example in Python in Programming 1.)

We can write AvgStack using inheritance. Here's an implementation:

class AvgStack : IntStack {
    int sum;

    public AvgStack(int limit) : base(limit) { }

    public AvgStack() : this(20) { }

    public override void push(int i) {
        base.push(i);
        sum += i;
    }

    public override int pop() {
        int i = base.pop();
        sum -= i;
        return i;
    }

    public double avg => (double) sum / n;
}

The notation class AvgStack : IntStack means that the class AvgStack inherits from IntStack. In this situation, we say that IntStack is the superclass (or parent class or base class), and AvgStack is a subclass (or derived class).

AvgStack has a public constructor that takes a single argument limit, just like the parent class. The notation : base(limit) means that the AvgStack constructor chains to the base class constructor – in other words, it calls the base class constructor, passing it the same value of limit that it itself received.

The AvgStack constructor does not need to initialize the sum field to 0, since 0 is the default value for fields of type int.

The second AvgStack constructor takes no arguments and chains to a different constructor in the same class. When chaining to a constructor in the same class, we write : this(); when chaining to a constructor in the base class, we write : base().

AvgStack overrides the push and pop methods from its parent class. That means that AvgStack provides its own implementation of these methods. In the push() method, AvgStack calls base.push(d) to call the same-named method in the base class. It then runs sum += i to update the running total. pop() is similar.

Note that if you attempt to build the IntStack and AvgStack classes as written above, the code will not compile! We need to make two changes to the base class IntStack:

1. We must modify the push() and pop() methods to be virtual:

    public virtual void push(int i) {
        a[n++] = i;
    }

    public virtual int pop() => a[--n];

In C#, a subclass may only override base class methods if they are virtual.

2. We must modify the field n in the base class to be protected:

    protected int n;    // in IntStack class

That is because the avg property in AvgStack accesses n:

    public double avg => (double) sum / n;   // in AvgStack class

In C#, the default access level for any member (e.g. field, method) is private. So if we use the simple declaration "int count;", then count will be private, which means that it will accessible only within its own class. A protected member, by constract, is accessible within its own class and within any subclasses. Finally, as we have seen before, a member marked as public is accessible from anywhere.

using base and derived types

We can create instances of each of the IntStack and AvgStack classes as follows:

IntStack s = new IntStack(100);   // create an IntStack
AvgStack t = new AvgStack(100);   // create an AvgStack

How about the following – will this work?

AvgStack t = new IntStack(100);    // does not compile

We are creating a IntStack, and attempting to store it in a variable of type AvgStack. The code will not compile. If t has type AvgStack, then it cannot hold this object because an IntStack is not an AvgStack. In general, an instance of a superclass (e.g. IntStack) is not an instance of a subclass (e.g. AvgStack) because it doesn't have the extended capabilities that the subclass provides.

On the other hand, consider this:

IntStack s = new AvgStack(100);   // works OK

This code will compile: a variable of type IntStack can hold an AvgStack, because an AvgStack is a kind of IntStack. In general, an instance of a subclass counts as an instance of its superclass (or of any ancestor class).

What happens if we invoke a method through a variable whose type is the superclass? In other words, how will the following code behave?

IntStack s = new AvgStack(100);
for (int i = 0 ; i < 10 ; ++i)
    s.push(i);   // which push() will this call?

Which implementation of push() will be invoked by the code above – the implementation in IntStack, or in the subclass AvgStack?

The code will call the implementation in AvgStack. Even though the object is held in a variable of type IntStack, it is actually an AvgStack. A call to a virtual method is resolved based on an object's actual class – the type of the variable holding the object is irrelevant.

The assigment IntStack s = new AvgStack(100) works because the type AvgStack is implicitly convertible to IntStack. Because of this phenomenon, we may write a method that works on IntStack objects and may pass it instances of the AvgStack subclass. For example:

static void empty(IntStack s) {
    while (!s.isEmpty)
        Console.WriteLine(s.pop());
}

We may pass an AvgStack to this method:

AvgStack s = new AvgStack(100);
for (int i = 0 ; i < 10 ; ++i)
    s.push(i);
empty(s);

We have seen that C# will implicitly convert from a subclass to a superclass type. In the other direction, C# provides an explicit conversion that we can access via a type cast. For example:

IntStack s = new AvgStack(100);
AvgStack t = (AvgStack) s;    // explicit conversion

We can use an explicit conversion to a subclass type when we are sure that a variable holds a object of that subclass. On the other hand, if the object does not actually belong to the subclass then the program will exit with an exception:

IntStack s = new IntStack(100);
AvgStack t = (AvgStack) s;  // compiles, but will throw an exception when run

is

The is operator returns true if a value is not null and belongs to a given type. It works with both reference types and nullable types:

IntStack s = getStack();
if (s is AvgStack) {
    AvgStack a = (AvgStack) s;
    WriteLine($"average = {a.avg}");
}

It's also possible to declare a local variable inside an is expression. The lines above may be rewritten as follows:

IntStack s = getStack();
if (s is AvgStack a)
    WriteLine($"average = {a.avg}");

Note that is works even with value types such as int:

int? i = abc();
if (i is int)  // true if i != null
    WriteLine(i);

As we saw in a previous lecture, you can conveniently use is in a while loop to capture all input lines. For example, the following loop will read all lines from standard input and echo them back out to standard output:

while (ReadLine() is string line)
    WriteLine(line);

as

The as operator checks whether a value belongs to a type. If so, it returns the value; otherwise it returns null:

IntStack s = getStack();
AvgStack ls = s as AvgStack;  // if s was not an AvgStack, ls will be null

abstract classes and methods

In Introduction to Algorithms we learned how to store an arithmetic expression using a tree. Here is a set of classes we might use to store expression trees in C#:

class Expr {
}

class OpExpr : Expr {
    char op;
    Expr left, right;

    public OpExpr(char op, Expr left, Expr right) {
        this.op = op; this.left = left; this.right = right;
    }
}

class IntExpr : Expr {
    int i;

    public IntExpr(int i) {
        this.i = i;
    }
}

An interior node of the tree is an OpExpr, which contains an operator (such as '+' or '-') plus pointers to children. Each child may be either another interior node, or a leaf node stored in the IntExpr class.

For example, the expression 2 + (3 * 4) could be stored as follows:

    // 2 + (3 * 4)
    Expr e = new OpExpr('+',
        new IntExpr(2),
        new OpExpr('*', new IntExpr(3), new IntExpr(4)));

(Of course, really it would be nice to write a parser function that can parse any arithmetic expression and generate a tree for it.)

Now suppose that we'd like to add an eval() method that will evaluate an expression. For example, e.eval() should return 14. We will have implementations of eval() in the OpExpr and IntExpr classes. Because these are implementations of the same method, it will need to be defined in the base class Expr as well. In theory we could define eval() there with a dummy implementation that will never be called:

    public virtual int eval() => 0;

However there is a better alternative. We can define the base class Expr as abstract, and define eval() as an abstract method in that class. An abstract class can never be instantiated directly – it exists only so that subclasses can extend it. Similarly, an abstract method can exist only in an abstract class, and has no implementation – it exists only so that subclasses can implement it.

Here is the complete implementation:

abstract class Expr {
    public abstract int eval();
}

class OpExpr : Expr {
    char op;
    Expr left, right;

    public OpExpr(char op, Expr left, Expr right) {
        this.op = op; this.left = left; this.right = right;
    }

    public override int eval() {
        int l = left.eval();
        int r = right.eval();
        switch (op) {
            case '+': return l + r;
            case '-': return l - r;
            // ... other operator here ...
            default: throw new Exception("unknown operator");
        }
    }
}

class IntExpr : Expr {
    int i;

    public IntExpr(int i) {
        this.i = i;
    }

    public override int eval() => i;
}

Note that an abstract class may even contain fields and non-abstract methods, though we don't have any such members in this simple example.

interfaces

In Introduction to Algorithms we learned about various abstract data types, such as stacks and queues. For each abstract data type, we described the methods that it provides. For example, a stack has methods push(), pop() and isEmpty(). We saw that we can implement each abstract data type in various ways. For example, we can implement a stack either using a linked list, or an array. Different implementations of an abstract data type will have equivalent functionality, though they might have different performance characteristics.

C# interfaces formalize this concept. An interface defines a set of methods or other members in an abstract data type. For example, here is an interface for a stack of integers:

interface IStack {
    bool isEmpty();
    void push(int i);
    int pop();
}

There is no implementation yet - just a set of methods to be implemented. We can write a concrete class LinkedStack that implements a stack using a linked list. It might begin like this:

class LinkedStack : IStack {
    Node? head;

    public bool isEmpty() => head == null;
  
    public void push(int i) {
        head = new Node(i, head);
    }
  
    public int pop() { … }
}

Above, "class LinkedStack : IStack" means that we are defining a class LinkedStack that implements the IStack interface. The compiler will check that our class provides an implementation of every method that was declared in the interface. If any implementations are missing, we will get a compiler error.

We might then write a second class ArrayStack that implements a stack using a fixed-size array. It could begin like this:

class ArrayStack : IStack {
    int[] a;
    int num;  // number of elements currently on the stack

    public ArrayStack(int limit) {
        a = new int[limit];
    }

    public bool isEmpty() { return num == 0; }

    …
}
  

We now have two different concrete implementations of an IStack. We might create two IStack objects as follows:

IStack s = new LinkedStack();
IStack t = new ArrayStack(100);

Notice that a variable can have an interface type, such as the variables s and t above. A variable with an interface type can hold any object that implements that interface.

Method parameters can also have an interface type. For example, here is a method that will empty a Stack, printing all values as it does so:

static void empty(IStack s) {
    while (!s.isEmpty()) {
        int i = s.pop();
        WriteLine(i);
    }
}

We may pass either a LinkedStack or an ArrayStack to this method. For example:

ArrayStack as = new ArrayStack(100);
for (int i = 0 ; i < 5 ; ++i)
    as.push(i);
empty(as);

Notice that an interface may not contain a constructor. Any class that implements an interface may have its own constructor(s), but those are not part of the interface.

An interface may, however, contain properties and indexers. For example, let's modify the IStack interface so that isEmpty is a read-only property, not a method:

interface IStack {
    bool isEmpty { get; }
    void push(int i);
    int pop();
}

All members in an interface are implicitly public, so you should not write the keyword public in an interface declaration. However, when you write a class that implements an interface, all implementations of the interface's members must be declared public (as you can see in the examples above).

Note that a class may implement more than one interface. For example, let's write an interface ICountable for any type that has a current element count:

interface ICountable {
    int count { get; }
}

Now we can modify our ArrayStack class so that it implements both IStack and ICountable:

class ArrayStack : IStack, ICountable {
    int[] a;
    int num;  // number of elements currently on the stack

    public ArrayStack(int limit) {
        a = new int[limit];
    }

    public bool isEmpty => num == 0;  // implementation of property from Stack

    public int count => num;  // implementation of property from Countable

    …

}

interface inheritance

Up to now we have only discussed inheritance between classes. C# also allows an interface to inherit from another interface. An inheriting interface has all the members of its parent interface, and can add additional members of its own. Here is a somewhat abstract example:

interface IShape {
    double perimeter();
    double area();
}

interface IPolygon : IShape {
    int num_vertices { get; }
}

class Circle : IShape { … }

class Rectangle : IPolygon { … }

class Triangle : IPolygon { … }

In this example, an IShape represents a shape in two dimensions and a Polygon is an IShape that has a finite number of vertices. Because the Triangle class implements Polygon, it must provide an implementation of num_vertices as well as of the perimeter() and area() methods.

single and multiple inheritance

C# provides

• single class inheritance: a class may inherit from only one other class

• multiple interface inheritance: a class may implement multiple interfaces; an interface may inherit from multiple interfaces

This particular combination was popularized by Java. Some object-oriented languages (including Python) have a more general mechanism: they have multiple class inheritance, so that one class may have several immediate superclasses. That is more powerful, but creates various complexities that C# avoids through its simpler model.

You have have noticed that an interface is somewhat similar to an abstract class, since it defines functionality that must be implemented by another class. Here are some important differences:

• An abstract class may contain fields, but an interface may not.

• A class may implement multiple interfaces, but may inherit from only one abstract class.

The C# collection classes

LIke many object-oriented languages, C# contains a set of collection classes in its standard library. These classes implement common data structures such as stacks, queues and hash tables.

Here is a picture of the class hierarchy of some of the major collection classes and interfaces:

All of these classes and interfaces live in the namespace System.Collections.Generic.

In the picture, an arrow from A to B means that B implements or inherits from A.

All entities above whose names begin with the letter I (e..g ICollection, IDictionary) are interfaces. This is a standard naming convention in the C# standard library.

The classes and interfaces above are generic, which means that you can instantiate them with any type. For example, List<T> is a generic type with type parameter T. You can create a List<int> to hold ints, or a List<string> to hold strings, for example:

List<int> l = new();
l.Add(4);

List<string> m = new();
m.Add("hi");

In the next lecture we'll learn how to write our own generic classes and interfaces.

The picture above includes the following classes:

• List<T> is a dynamic array, similar to a list in Python. (Actually we first discussed this class a few weeks ago.) List<T> contains an Add() method for appending an element to the end of a List. It also contains an indexer so that you can get or set elements by index.

• Stack<T> implements a stack using a dynamic array. It includes methods Push() and Pop().

• Queue<T> implements a queue using a dynamic array, and includes methods Enqueue() and Dequeue().

• The classes HashSet<T> and SortedSet<T> implement sets, with methods Add(), Contains() and Remove(). They differ in their underlying data structure: HashSet<> uses a hash table and SortedSet<T> uses a balanced binary tree.

• Finally, the classes Dictionary<K, V> and SortedDictionary<K, V> implement dictionaries, with an indexer that can get/set values as well as a ContainsKey method. They differ in their underlying data structure: Dictionary<K, V> uses a hash table and SortedDictionary<K, V> uses a balanced binary tree.

You can read more details about these classes and interfaces in our Quick Library Reference. Note that you will need to follow the class hierarchy in order to find all the members available in each of these classes. For example, the methods available in List<T> include not only the ones listed under List<T> in the library reference, but also those listed under IList<T> and ICollection<T>, since List<T> implements those interfaces.

You can read even more details about the collection classes (including various classes not depicted above) in the official .NET API documentation.

Notice that all collection classes ultimately inherit from an interface IEnumerable<T>. This interface contains various methods that allow the foreach statement to iterate over a collection's values. We will not discuss these methods at this point, but you should know that you can use foreach to iterate over any collection.

You will want to become fluent in using these collection classes. With them, you finally have easy access to useful data structures that we often used in Python, i.e. lists, sets and dictionaries.

Dictionaries in particular are quite useful, so let's look at the Dictionary<K, V> class a bit more. As you can see in the documentation, Dictionary<K, V> implements the interface IDictionary<K, V>, which in turn implements the interface ICollection<KeyValuePair<K, V>>. This means that a dictionary is a collection of key-value pairs. You can use foreach to iterate over a dictionary, and each element you get back will be a KeyValuePair<K, V>. Each KeyValuePair in turn has properties Key and Value. For example:

    Dictionary<string, int> d = new Dictionary<string, int>();
    d["yellow"] = 10;
    d["red"] = 15;
    d["blue"] = 20;
    
    foreach (KeyValuePair<string, int> p in d)
        WriteLine($"key = {p.Key}, value = {p.Value}");