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 briefly 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 will start to write larger programs in which we may have our own uses for inheritance.
Suppose that we have a simple C# class that
implements a fixed-size stack of values of type double:
class Stack {
double[] a;
int count;
public Stack(int maxSize) {
a = new double[maxSize];
}
public void push(double d) {
a[count] = d;
count += 1;
}
public double pop() {
count -= 1;
return a[count];
}
public bool isEmpty => count == 0;
}
We'd now like to write a class AvgStack that is like
Stack, but has an additional method average()
that can report the average value of the numbers that are currently
on the stack. We would like average() to run in O(1). To
achieve that, AvgStack will keep track of the current
total of all numbers on the stack.
We can write
AvgStack using inheritance. Here is an
implementation:
class AvgStack : Stack {
double total;
public AvgStack(int maxSize) : base(maxSize) {
}
public override void push(double d) {
base.push(d);
total += d;
}
public override double pop() {
double d = base.pop();
total -= d;
return d;
}
public double average() => total / count;
}
The notation class
AvgStack : Stack means that the class AvgStack
inherits from Stack.
In this situation, we say that Stack 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 maxSize,
just like the parent class. The notation : base(maxSize)
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 maxSize that
it itself received. (We
previously saw similar syntax for chaining 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().)
The AvgStack constructor does not
need to initialize the total field
to 0.0, since 0.0 is the default value for fields of type
double.
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 total += d to update the running
total. pop() is similar.
Note that if you attempt to build
the Stack and
AvgStack classes
as written above, the code will
not compile!
We need to make two changes to the base class Stack:
1. We
must modify the push() and
pop() methods
to be virtual:
public virtual void push(double d) {
a[count] = d;
count += 1;
}
public virtual double pop() {
count -= 1;
return a[count];
}
In C#,
a subclass may only override base class methods if they are virtual.
2.
We must modify the count
field
in the base class to be protected:
protected int count; // in Stack class
That is because the
average() method
in AvgStack
accesses count:
public double average() => total / count; // 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.
We can create instances of each of the Stack
and AvgStack classes as follows:
Stack s = new Stack(100); // create a Stack AvgStack t = new AvgStack(100); // create an AvgStack
How about the following – will this work?
AvgStack t = new Stack(100); // does not compile
We are creating a Stack, 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 a
Stack is
not an AvgStack.
In general, an instance of a superclass (Stack)
is not an instance of a subclass (AvgStack)
because it doesn't have the extended capabilities that the subclass
provides.
On the other hand, consider this:
Stack s = new AvgStack(100); // works OK
This code will compile: a variable of type Stack can
hold an AvgStack, because an AvgStack is a
kind of Stack. 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?
Stack s = new AvgStack(100); for (double d = 0.0 ; d < 10.0 ; d += 1.0) s.push(d); // which push() will this call?
Which implementation of
push()
will be invoked by the code
above – the implementation in Stack,
or in the subclass AvgStack?
The code
will call the implementation in AvgStack.
Even though the object is held in a variable of type Stack,
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 Stack s = new AvgStack(100) works
because the type AvgStack is
implicitly
convertible to
Stack.
Because of this phenomenon, we may write a method that works
on Stack objects and may pass it instances of the
AvgStack subclass. For example:
static void empty(Stack s) {
while (!s.isEmpty)
Console.WriteLine(s.pop());
}
We may pass an AvgStack to this method:
AvgStack s = new AvgStack(100); for (double d = 0.0 ; d < 10.0 ; d += 1.0) s.push(d); 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:
Stack 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:
Stack s = new Stack(100); AvgStack t = (AvgStack) s; // compiles, but will throw an exception when run
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:
class LinkedStack : Stack { … }
…
Stack s = getStack();
if (s is LinkedStack)
WriteLine("it is a LinkedStack");
int? i = abc();
if (i is int) // true if i != null
WriteLine(i.Value);The as operator checks whether a
value belongs to a type. If so, it returns the value; otherwise it
returns null:
Stack s = getStack();
LinkedStack ls = s as LinkedStack; // if s was not a LinkedStack, ls will be nullSuppose that we'd like to write classes that implement several kinds of collections of integers:
Stack,
a LIFO stack
Queue,
a FIFO queue
PriorityQueue,
a priority queue
Furthemore we would like to use these classes somewhat interchangeably, so we'd like them all to provide a common set of members:
a constructor that creates an empty collection
a constructor
that takes an array of type int[] and uses it to
initialize the collection
a method void
add(int
val)
a method int
remove()
a property
count that returns the current number of items in the
collection
a property
isEmpty that is true if the collection is empty
The add() and remove()
methods will work differently in the different classes. For example,
in a Queue the remove() method will remove
the element that was added first, whereas in a PriorityQueue
it will remove the smallest value.
We could write all these classes independently. But since they share some common functionality, it might be nicer to use inheritance so that we can write the common code only once. However, none of these classes can reasonably inherit from each other. (Perhaps a priority queue sounds like a particular kind of queue, but the data structure for implementing a priority queue (e.g. a binary heap) will be completely different from the data structure for implementing a FIFO queue (e.g. a linked list).)
Instead, a better idea is to write a top-level
class Collection that can serve as a superclass for all
of these classes. Then we can implement the common functionality in
the Collection class. Of course, it would make no sense
to create an object of class Collection; the only
purpose of Collection is for other classes to derive
from this. So we will mark Collection as an abstract
class. An abstract class cannot
be instantiated – that
is to say, you cannot create an instance of it. Furthermore, an
abstract class can have abstract methods,
which have no implementation: a concrete derived class must provide
an implementation of these methods.
Here
is the base class Collection:
abstract class Collection {
protected int _count;
protected Collection() { }
protected Collection(int[] a) {
foreach (int val in a)
add(val);
}
public int count => _count;
public bool isEmpty => _count == 0;
protected abstract void _add(int val);
protected abstract int _remove();
public void add(int a) {
_add(a);
_count += 1;
}
public int remove() {
int val = _remove();
_count -= 1;
return val;
}
}
The field _count holds the number of elements in a
collection. Its name is preceded with an underscore to distinguish it
from the public read-only count property. The class has
two constructors: one creates an empty Collection and
another initializes a Collection with elements from an
array. The constructors are protected, not public, since they will
only be called by subclasses.
The public methods add() and remove()
call the abstract methods _add() and _remove()
to perform the actual work of adding and removing elements from a
collection. Notice that these methods have no implementation; they
will be implemented by each subclass.
Here is a subclass Queue that
implements a FIFO queue using a linked list:
class Node {
public int val;
public Node<int> next;
public Node(int val) { this.val = val; }
}
class Queue : Collection {
Node head, tail;
public Queue() { }
public Queue(int[] a) : base(a) { }
protected override void _add(int val) {
if (head == null)
head = tail = new Node<int>(val);
else {
tail.next = new Node<int>(val);
tail = tail.next;
}
}
protected override int _remove() {
int val = head.val;
head = head.next;
return val;
}
}
Notice that we must write override when implementing an
abstract method.
I will not provide implementations of the other
subclasses. Hopefully it is clear enough, however, that the
functionality in the top-level Collection class could
reasonably be shared by all subclasses.
All C# class automatically inherit from a
top-level class called Object which contains a modest
number of methods that are shared by all objects. One
of these methods is ToString:
virtual string ToString ();
C# automatically calls this method when it needs to convert any
object to a string. You can override ToString() in your
own classes if you'd like to change their printed representation.
(ToString() is like the __repr magic method
in Python, which you may remember.)
Write a static method int sqrt(int n) that computes the integer square root of an integer n, i.e. the non-negative integer i such that i * i = n. If no such integer exists, return -1.
static int sqrt(int n) {
int lo = 0, hi = n;
// Loop invariant: lo <= sqrt(n) <= hi
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (mid * mid == n)
return mid;
else if (mid * mid < n)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}Write a program that computes and prints the number 10100 mod 47.
static void Main(string[] args) {
int n = 1;
for (int i = 0 ; i < 100 ; ++i)
n = (n * 10) % 47;
WriteLine(n);
}A knight on a chessboard has a broken leg. On
odd
moves (including his first move), he moves like a knight. On even
moves, he may only move one square horizontally or vertically (not
diagonally). Write a method int
knight_path((int, int) start_pos,
(int, int) end_pos) that
returns
the
length
of the shortest
path that the knight can take between positions (start_pos) and
(end_pos) on a chessboard.
using static System.Console;
class Node {
public (int x, int y) pos;
public int dist;
public Node((int, int) pos, int dist) {
this.pos = pos; this.dist = dist;
}
}
class Queue {
Node[] a = new Node[100];
int head = 0, tail = 0;
public void enqueue(Node q) {
a[tail++] = q;
}
public Node dequeue() {
return a[head++];
}
public bool is_empty => head == tail;
}
class Program {
static (int, int)[] knight_moves = {
(2, 1), (2, -1), (-2, 1), (-2, -1),
(1, 2), (1, -2), (-1, 2), (-1, -2)
};
static (int, int)[] limp_moves = {
(1, 0), (-1, 0), (0, 1), (0, -1)
};
static bool valid(int x, int y) => 1 <= x && x <= 8 && 1 <= y && y <= 8;
static int knight_path((int, int) start, (int, int) goal) {
Queue q = new Queue();
q.enqueue(new Node(start, 0));
bool[,] visited = new bool[9, 9];
while (!q.is_empty) {
Node n = q.dequeue();
(int, int) [] moves = n.dist % 2 == 0 ? knight_moves : limp_moves;
foreach ((int dx, int dy) in moves) {
(int x, int y) = (n.pos.x + dx, n.pos.y + dy);
if ((x, y) == goal)
return n.dist + 1;
if (valid(x, y) && !visited[x, y]) {
visited[x, y] = true;
q.enqueue(new Node((x, y), n.dist + 1));
}
}
}
return -1;
}
static void Main(string[] args) {
WriteLine(knight_path((1, 1), (1, 2)));
}
}