Другие элементы меню 22 страница

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. Этапы процесса разработки программной системы>

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

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

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

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

/// <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. Работа со стеками>

Ограниченная универсальность

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

Если немного подумать, то это совершенно естественная ситуация. Если имеет место неограниченная универсальность, то над объектами типов можно выполнять только те операции, которые допускают все типы – в C#, что эквивалентно операциям, разрешенным над объектами типа object – прародителя всех типов. В нашем предыдущем примере, где речь шла о свопинге, над объектами выполнялась единственная операция присваивания. Поскольку присваивание внутри одного типа разрешено для всех типов, то неограниченная универсальность приемлема в такой ситуации. Но что произойдет, если попытаться выполнить сложение элементов, сравнение элементов, или даже простую проверку элементов на равенство? Немедленно возникнет ошибка еще на этапе компиляции. Эти операции не разрешены для всех типов, поэтому в случае компиляции такого проекта ошибка могла бы возникнуть на этапе выполнения, когда вместо формального типа появился бы конкретный тип, не допускающий подобную операцию. Нельзя ради универсальности пожертвовать одним из важнейших механизмов C# и Framework.Net – безопасностью типов, поддерживаемой статическим контролем типов. Именно поэтому неограниченная универсальность существенно ограничена. Ее ограничивает статический контроль типов. Чтобы снять в определенной мере эти ограничения, необходимо на типы наложить ограничения, позволяющие ослабить границы статического контроля. На практике универсальность почти всегда ограничивается, что, повторяю, дает большую свободу программисту.

В языке C# допускаются три вида ограничений накладываемых на родовые параметры:

Ограничение наследования. Это основный вид ограничений, указывающий, что тип T является наследником некоторого класса и ряда интерфейсов. Следовательно, над объектами типа T можно выполнять все операции, заданные базовым классом и интерфейсами. Эти операции статический контроль типов будет разрешать, обеспечивать для них интеллектуальную поддержку, показывая список разрешенных операций. Ограничение наследования позволяет выполнять над объектами больше операций, чем в случае неограниченной универсальности. Синтаксически ограничение выглядит так: where T: BaseClass, I1, …Ik.

Ограничение конструктора. Это ограничение указывает, что тип T имеет конструктор без аргументов и, следовательно, позволяет создавать объекты типа T. Синтаксически ограничение выглядит так: where T: new ().

Ограничение value/reference. Это ограничение указывает, к значимым или к ссылочным типам относится тип T. Для указания значимого типа задается слово struct, для ссылочных типов указывается – class. Так что синтаксически этот тип ограничений выглядит так: where T: struct.

Возникает законный вопрос, насколько полна предлагаемая система ограничений? Конечно, речь идет о практической полноте, а не о математически строгих определениях. С позиций практики систему хотелось бы дополнить, в первую очередь введением ограничением операций, указывающим допустимые знаки операций в выражениях над объектами соответствующего типа. Хотелось бы, например, указать, что к объектам типа T применима операция сложения + или операция сравнения <. Позже я покажу, как можно справиться с этой проблемой, но предлагаемое решение довольно сложно. Наличие ограничения операций намного элегантнее решало бы эту проблему.

Синтаксис ограничений

Уточним некоторые синтаксические правила записи ограничений. Если задан универсальный класс с типовыми параметрами T1, …Tn, то на каждый параметр могут быть наложены ограничения всех типов. Ограничения для каждого параметра задаются предложением where, начинающегося соответствующим ключевым словом, после которого следует имя параметра, а затем через двоеточие ограничения первого, второго или третьего типа, разделенные запятыми. Порядок их важен, если присутствует ограничение третьего типа, то оно записывается первым. Заметьте, предложения where для разных параметров отделяются лишь пробелами, как правило, они записываются на отдельных строчках. Предложения where записываются в конце заголовка класса после имени класса и списка его типовых параметров, после родительских классов и интерфейсов, если они заданы для универсального класса. Вот синтаксически корректные объявления классов с ограничением универсальности:

public class Father<T1, T2>

{ }

public class Base

{

public void M1() { }

public void M2() { }

}

public class Child<T1,T2>:Father<T1,T2>

where T1:Base,IEnumerable<T1>, new ()

where T2: struct,IComparable<T2>

{ }

Класс Child с ограниченной универсальностью к данным типа T1 имеет право применять методы M1 и M2 базового класса Base, также как и методы интерфейса IEnumerable<T1>, он может создавать объекты типа T1, используя конструктор по умолчанию. Фактический тип, подставляемый вместо формального типа T2 должен быть значимым типом и объекты этого типа разрешается сравнивать между собой.

Список с возможностью поиска элементов по ключу

Ключевые идеи ограниченной универсальности, надеюсь, понятны. Давайте теперь рассмотрим пример построения подобного класса, где можно будет увидеть все детали. Рассмотрим саму по себе интересную и классическую задачу построения списка с курсором. Как и всякий контейнер данных, список следует сделать универсальным, допускающим хранение данных разного типа. С другой стороны мы не хотим, чтобы в одном списке происходило смешение типов, уж если там хранятся персоны, то чисел int в нем не должно быть. По этим причинам класс должен быть универсальным, имея в качестве параметра тип T, задающий тип хранимых данных. Мы потребуем также, чтобы данные хранились с их ключами. И поскольку не хочется заранее накладывать ограничений на тип ключей – они могут быть строковыми или числовыми, то тип хранимых ключей будет еще одним параметром нашего класса. Поскольку мы хотим определить над списком операцию поиска по ключу, то нам придется выполнять проверку ключей на равенство, поэтому универсальность типа ключей должна быть ограниченной, проще всего сделать этот тип наследником стандартного интерфейса IComparable.

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

class Node<K, T> where K:IComparable<K>

{

public Node()

{

next = null; key = default (K);

item = default (T);

}

public K key;

public T item;

public Node<K, T> next;

}

Класс Node имеет два родовых параметра, задающих тип ключей и тип элементов. Ограничение на тип ключей позволяет выполнять сравнение ключей. В конструкторе класса поля инициализируются значениями по умолчанию соответствующего типа.

Рассмотрим теперь организацию односвязного списка. Начнем с того, как устроены его данные:

public class OneLinkList<K, T> where K: IComparable<K>

{

Node<K, T> first, cursor;

}

Являясь клиентом универсального класса Node, наш класс сохраняет родовые параметры клиента и ограничения, накладываемые на них. Два поля класса – first и cursor – задают указатели на первый и текущий элементы списка. Операции над списком связываются с курсором, позволяя перемещать курсор по списку. Рассмотрим вначале набор операций, перемещающих курсор:

public void start()

{ cursor = first; }

public void finish()

{

while (cursor.next!= null)

cursor = cursor.next;

}

public void forth()

{ if (cursor.next!= null) cursor = cursor.next; }

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

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

public void add(K key, T item)

{

Node<K, T> newnode = new Node<K, T>();

if (first == null)

{

first = newnode; cursor = newnode;

newnode.key = key; newnode.item = item;

}

{

newnode.next = cursor.next; cursor.next = newnode;

newnode.key = key; newnode.item = item;

}

}

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

Рассмотрим теперь операцию поиска элемента по ключу, реализация которой потребовала ограничения универсальности типа ключа K:

public bool findstart(K key)

{

Node<K, T> temp = first;

while (temp!= null)

{

if (temp.key.CompareTo(key) == 0) {cursor=temp; return (true);}

temp= temp.next;

}

return (false);

}

Искомые элементы ищутся во всем списке. Если элемент найден, то курсор устанавливается на найденном элементе и метод возвращает значение true. Если элемента с заданным ключом нет в списке, то позиция курсора не меняется, а метод возвращает значение false. В процессе поиска для каждого очередного элемента списка вызывается допускаемый ограничением метод CompareTo интерфейса IComparable. При отсутствии ограничений универсальности вызов этого метода или операции эквивалентности == приводил бы к ошибке, обнаруживаемой на этапе компиляции.

Два метода класса являются запросами, позволяющими извлечь ключ и элемент списка, отмеченный курсором:

public K Key()

{

return (cursor.key);

}

public T Item()

{

return (cursor.item);

}

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

public void TestConstraint()

{

OneLinkList< int, string > list1 = new OneLinkList< int, string >();

list1.add(33, "thirty three"); list1.add(22, "twenty two");

if (list1.findstart(33)) Console.WriteLine("33 - найдено!");

else Console.WriteLine("33 - не найдено!");

if (list1.findstart(22)) Console.WriteLine("22 - найдено!");

else Console.WriteLine("22 - не найдено!");

if (list1.findstart(44)) Console.WriteLine("44 - найдено!");

else Console.WriteLine("44 - не найдено!");

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

Дата добавления: 2014-12-25