Наследование и универсальность

Необходимость в универсализации возникает с первых шагов программирования. Одна из первых процедур, появляющихся при обучении программированию – это процедура свопинга:обмен значениями двух переменных одного типа. Выглядит она примерно так:

public void Swap(ref T x1, ref T x2)

{

T temp;

temp = x1; x1 = x2; x2 = temp;

}

Если тип T – это вполне определенный тип, например int, string или Person, то никаких проблем не существует, все совершенно прозрачно. Но как быть, если возникает необходимость обмена данными разного типа? Неужели нужно писать копии этой процедуры для каждого типа? Проблема легко решается в языках, где нет контроля типов – там достаточно иметь единственный экземпляр такой процедуры, прекрасно работающий, но лишь до тех пор, пока передаются аргументы одного типа. Когда же процедуре будут переданы фактические аргументы разного типа, то немедленно возникнет ошибка периода выполнения, и это слишком дорогая плата за универсальность.

В типизированных языках, не обладающих механизмом универсализации, выхода практически нет – приходится писать многочисленные копии Swap.

Для достижения универсальности процедуры Swap следует рассматривать тип T как ее параметр, такой же, как и сами аргументы x1 и x2. Суть универсальности в том, чтобы в момент вызова процедуры передавать ей не только фактические аргументы, но и их фактический тип.

Под универсальностью (genericity) понимается способность класса объявлять используемые им типы как параметры. Класс с параметрами, задающими типы, называется универсальным классом (generic class). Терминология не устоялась и синонимами термина “универсальный класс” являются термины: родовой класс, параметризованный класс, класс с родовыми параметрами. В языке С++ универсальные классы называются шаблонами (template).

Синтаксис универсального класса

Объявить класс C# универсальным просто: для этого достаточно указать в объявлении класса, какие из используемых им типов являются параметрами. Список типовых параметров класса, заключенный в угловые скобки, добавляется к имени класса:

class MyClass<T1, … Tn> {…}

Как и всякие формальные параметры, Ti являются именами (идентификаторами). В теле класса эти имена могут задавать типы некоторых полей класса, типы аргументов и возвращаемых значений методов класса. В некоторый момент (об этом скажем чуть позже) формальные имена типов будут заменены фактическими параметрами, представляющими уже конкретные типы – имена встроенных классов, классов библиотеки FCL, классов, определенных пользователем.

В C# универсальными могут быть как классы, так и все их частные случаи – интерфейсы, структуры, делегаты, события.

Класс с универсальными методами

Специальным частным случаем универсального класса является класс, не объявляющий сам параметров, но разрешающий делать это своим методам. Давайте начнем рассмотрение универсальности с этого частного случая. Вот как выглядит класс, содержащий универсальный метод swap:

class Change

{

static public void Swap<T>(ref T x1, ref T x2)

{

T temp;

temp = x1; x1 = x2; x2 = temp;

}

}

Как видите, сам класс в данном случае не имеет родовых параметров, но зато универсальным является статический метод класса swap, имеющий родовой параметр типа T. Этому типу принадлежат аргументы метода и локальная переменная temp. Всякий раз при вызове метода ему, наряду с фактическими аргументами, будет передаваться и фактический тип, заменяющий тип T в описании метода. О некоторых деталях технологии подстановки и выполнения метода поговорим в конце лекции, сейчас же лишь отмечу, что реализация вызова универсального метода в C# не приводит к существенным накладным расходам.

Рассмотрим тестирующую процедуру из традиционного для наших примеров класса Testing, в которой интенсивно используется вызов метода swap для различных типов переменных:

public void TestSwap()

{

int x1 = 5, x2 = 7;

Console.WriteLine(“до обмена: x1={0}, x2={1}”,x1, x2);

Change.Swap<int>(ref x1, ref x2);

Console.WriteLine(“после обмена: x1={0}, x2={1}”, x1, x2);

string s1 = “Савл”, s2 = “Павел”;

Console.WriteLine(“до обмена: s1={0}, s2={1}”, s1, s2);

Change.Swap<string>(ref s1, ref s2);

Console.WriteLine(“после обмена: s1={0}, s2={1}”, s1, s2);

Person pers1 = new Person(“Савлов”, 25, 1500);

Person pers2 = new Person(“Павлов”, 35, 2100);

Console.WriteLine(“до обмена: “);

pers1.PrintPerson(); pers2.PrintPerson();

Change.Swap<Person>(ref pers1, ref pers2);

Console.WriteLine(“после обмена:”);

pers1.PrintPerson(); pers2.PrintPerson();

}

Обратите внимание на строки, осуществляющие вызов метода:

Change.Swap<int>(ref x1, ref x2);

Change.Swap<string>(ref s1, ref s2);

Change.Swap<Person>(ref pers1, ref pers2);

В момент вызова метода передаются фактические аргументы и фактические типы. В данном примере в качестве фактических типов использовались встроенные типы int и string и тип Person, определенный пользователем. Общая ситуация такова: если в классе объявлен универсальный метод со списком параметров M<T1, …Tn> (…), то метод вызывается следующим образом: M<TYPE1, … TYPEn>(…), где TYPEi – это конкретные типы.

Еще раз напомню, что все эти примеры построены в Whidbey, и вот как выглядят внешний вид среды разработки и окно с результаты работы этой процедуры.

Рис. 22.1. Результаты работы универсальной процедуры swap

В этом примере использовался класс Person, и поскольку он появится и в следующих примерах, то приведу его текст:

class Person

{

public Person(string name, int age, double salary)

{

this.name = name; this.age = age; this.salary = salary;

}

public string name;

public int age;

public double salary;

public void PrintPerson()

{

Console.WriteLine(“name= {0}, age = {1}, salary ={2}”,

name, age, salary);

}

}

Два основных механизма объектной технологии

Наследование и универсальность являются двумя основными механизмами, обеспечивающими мощность объектной технологии разработки. Наследование позволяет специализировать операции класса, уточнить, как должны выполняться операции. Универсализация позволяет специализировать данные, уточнить, над какими данными выполняются операции.

Эти механизмы взаимно дополняют друг друга. Универсальность можно ограничить (об этом подробнее будет сказано ниже), указав, что тип, задаваемый родовым параметром, обязан быть наследником некоторого класса и/или ряда интерфейсов. С другой стороны, когда формальный тип T заменяется фактическим типом TFact, то там, где разрешено появляться объектам типа TFact, разрешены и объекты, принадлежащие классам-потомкам TFact.

Эти механизмы в совокупности обеспечивают бесшовный процесс разработки программных систем, начиная с этапов спецификации и проектирования системы и заканчивая этапами реализации и сопровождения. На этапе задания спецификаций появляются абстрактные, универсальные классы, которые в ходе разработки становятся вполне конкретными классами с конкретными типами данных. Механизмы наследования и универсализации позволяют существенно сократить объем кода, описывающего программную систему, поскольку потомки не повторяют наследуемый код своих родителей, а единый код универсального класса используется при каждой конкретизации типов данных. На рис. 22.2 показан схематически процесс разработки программной системы.

Рис. 22.2.1. 1: Этап проектирования: абстрактный класс с абстрактными типами

Рис. 22.2.2. 2: Наследование: уточняется представление данных; задается или уточняется реализация методов родителя

Рис. 22.2.3. 3: Родовое порождение: уточняются типы данных; порождается класс путем подстановки конкретных типов

На этапе спецификации, как правило, создается абстрактный, универсальный класс, где задана только сигнатура методов, но не их реализация; где определены имена типов, но не их конкретизация. Здесь же, используя возможности тегов класса, формально или неформально задаются спецификации, описывающие семантику методов класса. Далее в ходе разработки, благодаря механизму наследования, появляются потомки абстрактного класса, каждый из которых задает реализацию методов. На следующем этапе, благодаря механизму универсализации, появляются экземпляры универсального класса, каждый из которых выполняет операции класса над данными соответствующих типов.

Для наполнения этой схемы реальным содержанием давайте рассмотрим некоторый пример с прохождением всех трех этапов.

Стек. От абстрактного, универсального класса к конкретным версиям

Возьмем классическую задачу определения стека. Следуя схеме, определим абстрактный универсальный класс, описывающий всевозможные представления стеков:

/// <summary>

/// Абстрактный класс GenStack<T> задает контейнер с

/// доступом LIFO:

/// Функции:

/// конструктор new: -> GenStack<T>

/// запросы:

/// item: GenStack -> T

/// empty: GenStack -> Boolean

/// процедуры:

/// put: GenStack*T -> GenStack

/// remove: GenStack -> GenStack

/// Аксиомы:

/// remove(put(s,x)) = s

/// item(put(s,x)) = x

/// empty(new)= true

/// empty(put(s,x)) = false

/// </summary>

abstract public class GenStack<T>

{

/// <summary>

/// require: not empty();

/// </summary>

/// <returns>элемент вершины(последний пришедший)</returns>

abstract public T item();

/// <summary>

/// require: not empty();

/// ensure: удален элемент вершины(последний пришедший)

/// </summary>

abstract public void remove();

/// <summary>

/// require: true; ensure: elem находится в вершине стека

/// </summary>

/// <param name=”elem”></param>

abstract public void put(T t);

/// <summary>

/// require: true;

/// </summary>

/// <returns>true если стек пуст, иначе false </returns>

abstract public bool empty();

}// class GenStack

В приведенном примере программного текста чуть-чуть. Это объявление абстрактного универсального класса:

abstract public class GenStack<T>

и четыре строки с объявлением сигнатуры его методов. Основной текст задает описание спецификации класса и его методов. Заметьте, здесь спецификации заданы достаточно формально с использованием аксиом, характеризующих смысл операций, которые выполняются над стеком.

Не хочется вдаваться в математические подробности, отмечу лишь, что, если задать последовательность операций над стеком, то аксиомы позволяют точно определить состояние стека в результате выполнения этих операций. Как неоднократно отмечалось с первых лекций курса, XML-отчет, построенный по этому проекту, будет содержать в читаемой форме все спецификации нашего класса. Отмечу еще, что все потомки класса должны удовлетворять этим спецификациям, хотя могут добавлять и собственные ограничения.

Наш класс является универсальным – стек может хранить элементы любого типа, и конкретизация типа будет производиться в момент создания экземпляра стека.

Наш класс является абстрактным – не задана ни реализация методов, ни то, как стек будет представлен. Эти вопросы будут решать потомки класса.

Перейдем теперь ко второму этапу и построим потомков класса, каждый из которых задает некоторое представление стека и соответствующую этому представлению реализацию методов. Из всех возможных представлений ограничимся двумя. В первом из них стек будет представлен линейной односвязной списковой структурой. Во втором – он строится на массиве фиксированного размера, задавая стек ограниченной емкости. Вот как выглядит первый потомок абстрактного класса:

/// <summary>

/// Стек, построенный на односвязных элементах списка GenLinkable<T>

/// </summary>

public class OneLinkStack<T> : GenStack<T>

{

public OneLinkStack()

{

last = null;

}

GenLinkable<T> last; //ссылка на стек (вершину стека)

public override T item()

{

return (last.Item);

}//item

public override bool empty()

{

return (last == null);

}//empty

public override void put(T elem)

{

GenLinkable<T> newitem = new GenLinkable<T>();

newitem.Item = elem; newitem.Next = last;

last = newitem;

}//put

public override void remove()

{

last = last.Next;

}//remove

}//class OneLinkStack

Посмотрите, что происходит при наследовании от универсального класса. Во-первых, сам потомок также является универсальным классом:

public class OneLinkStack<T> : GenStack<T>

Во-вторых, если потомок является клиентом некоторого класса, то и этот класс, возможно, также должен быть универсальным, как в нашем случае происходит с классом GenLinkable<T>:

GenLinkable<T> last; //ссылка на стек (элемент стека)

В-третьих, тип T встречается в тексте потомка всюду, где речь идет о типе элементов, добавляемых в стек, как, например:

public override void put(T elem)

По ходу дела нам понадобился класс, задающий представление элементов стека в списковом представлении. Объявим его:

public class GenLinkable<T>

{

public T Item;

public GenLinkable<T> Next;

public GenLinkable()

{ Item = default(T); Next = null; }

}

Класс устроен достаточно просто, у него два поля: одно для хранения элементов, помещаемых в стек и имеющее тип T, другое – указатель на следующий элемент. Обратите внимание на конструктор класса, в котором для инициализации элемента используется новая конструкция default(T), которая возвращает значение, устанавливаемое по умолчанию для типа T.

Второй потомок абстрактного класса реализует стек по-другому, используя представление в виде массива. Потомок задает стек ограниченной емкости. Емкостью стека можно управлять в момент его создания. В ряде ситуаций использование такого стека предпочтительнее по соображениям эффективности, поскольку не требует динамического создания элементов. Приведу текст этого класса уже без дополнительных комментариев:

public class ArrayUpStack<T> : GenStack<T>

{

int SizeOfStack;

T[] stack;

int top;

/// <summary>

/// конструктор

/// </summary>

/// <param name=”size”>размер стека</param>

public ArrayUpStack(int size)

{ SizeOfStack = size; stack = new T[SizeOfStack]; top = 0; }

/// <summary>

/// require: (top < SizeOfStack)

/// </summary>

/// <param name=”x”> элемент, помещаемый в стек</param>

public override void put(T x)

{ stack[top] = x; top++; }

public override void remove()

{ top–; }

public override T item()

{ return (stack[top-1]); }

public override bool empty()

{ return (top == 0); }

}//class ArrayUpStack

Созданные в результате наследования классы-потомки перестали быть абстрактными, но все еще остаются универсальными. На третьем этапе порождаются конкретные экземпляры потомков – универсальных классов, в этот момент и происходит конкретизация типов, и два экземпляра одного универсального класса могут работать с данными различных типов. Этот процесс создания экземпляров с подстановкой конкретных типов называют родовым порождением экземпляров. Вот как в тестирующей процедуре создаются экземпляры созданных нами классов:

public void TestStacks()

{

OneLinkStack<int> stack1 = new OneLinkStack<int>();

OneLinkStack<string> stack2 = new OneLinkStack<string>();

ArrayUpStack<double> stack3 = new ArrayUpStack

<double>(10);

stack1.put(11); stack1.put(22);

int x1 = stack1.item(), x2 = stack1.item();

if ((x1 == x2) && (x1 == 22)) Console.WriteLine(“OK!”);

stack1.remove(); x2 = stack1.item();

if ((x1 != x2) && (x2 == 11)) Console.WriteLine(“OK!”);

stack1.remove(); x2 = (stack1.empty())? 77 : stack1.item();

if ((x1 != x2) && (x2 == 77)) Console.WriteLine(“OK!”);

stack2.put(“first”); stack2.put(“second”);

stack2.remove(); string s = stack2.item();

if (!stack2.empty()) Console.WriteLine(s);

stack3.put(3.33); stack3.put(Math.Sqrt(Math.PI));

double res = stack3.item();

stack3.remove(); res += stack3.item();

Console.WriteLine(“res= {0}”, res);

}

В трех первых строках этой процедуры порождаются три экземпляра стеков. Все они имеют общего родителя – абстрактный универсальный класс GenStack, но каждый из них работает с данными своего типа и по-разному реализует методы родителя. На рис. 22.3 показаны результаты работы этой процедуры.

Рис. 22.3. Три разных стека, порожденных абстрактным универсальным классом

Дополним наше рассмотрение еще одним примером работы с вариацией стеков, в том числе хранящим объекты класса Person:

public void TestPerson()

{

OneLinkStack<int> stack1 = new OneLinkStack<int>();

OneLinkStack<string> stack2 = new OneLinkStack<string>();

ArrayUpStack<double> stack3 = new ArrayUpStack

<double>(10);

ArrayUpStack<Person> stack4 = new ArrayUpStack<Person>(7);

stack2.put(“Петров”); stack2.put(“Васильев”);

stack2.put(“Шустов”);

stack1.put(27); stack1.put(45); stack1.put(53);

stack3.put(21550.5); stack3.put(12345.7);

stack3.put(32458.8);

stack4.put(new Person(stack2.item(), stack1.item(),

stack3.item()));

stack1.remove(); stack2.remove(); stack3.remove();

stack4.put(new Person(stack2.item(), stack1.item(),

stack3.item()));

stack1.remove(); stack2.remove(); stack3.remove();

stack4.put(new Person(stack2.item(), stack1.item(),

stack3.item()));

Person pers = stack4.item(); pers.PrintPerson();

stack4.remove(); pers = stack4.item(); pers.PrintPerson();

stack4.remove(); pers = stack4.item(); pers.PrintPerson();

stack4.remove(); if (stack4.empty()) Console.WriteLine(“OK!”);

}

Результаты работы этой процедуры приведены на рис. 22.4.

Рис. 22.4. Работа со стеками