Список с курсором. Динамические структуры данных
Добавим в проект классы, задающие динамические структуры данных. Конечно, можно было бы воспользоваться стандартными... Но для обучения крайне полезно уметь создавать собственные классы, задающие такие структуры данных. Список с курсором - один из важнейших образцов подобных классов:
using System; namespace Shapes { /// <summary> /// Класс TwoWayList(G) описывает двусвязный список с /// курсором. Элементами списка являются объекты /// TwoLinkable, хранящие, помимо указателей на двух /// преемников, объекты типа G.Курсор будет определять /// текущий (активный) элемент списка. Класс будет /// определять симметричные операции по отношению к /// курсору. /// Конструкторы: /// Конструктор без параметров будет создавать пустой /// список /// Запросы: /// empty: require: true; возвращает true для пустого списка /// item: require: not empty(); возвращает активный элемент типа G; /// require: true; возвращает число элементов списка; /// count: count in[0,n] (count == 0) eqviv empty(); /// index: require: not empty(); возвращает индекс активного элемента. /// search_res: require: true; возвращает true, если последний поиск был успешным. /// Команды: /// put_left(elem): require: true; /// ensure: добавить новый элемент (elem) слева от курсора; /// put_right(elem): require: true; /// ensure: добавить новый элемент (elem) справа от курсора; /// remove: require: not empty(); /// ensure: удалить активный элемент; /// особо обрабатывается удаление последнего и единственного элементов /// операции с курсором: /// start: require: true; /// ensure: сделать активным первый элемент; /// finish: require: true; /// ensure: сделать активным последний элемент; /// go_prev: require: not (index = 1); /// ensure: сделать активным предыдущий элемент; /// go_next: require: not (index = count); /// ensure: сделать активным последующий элемент; /// go_i(i): require: (i in [1, count]); /// ensure: сделать активным элемент с индексом i; /// операции поиска: /// search_prev(elem): require: not (index = 1); /// ensure: сделать активным первый элемент elem слева от курсора; /// Успех или неуспех поиска сохранять в булевской /// переменной search_res /// search_next: require: not (index = count); /// ensure: сделать активным первый элемент elem справа от курсора; /// успех или неуспех поиска сохранять в булевской переменной search_res /// </summary> public class TwoWayList { public TwoWayList() { first = cursor = last = null; count = index = 0; search_res = false; }//конструктор /// <summary> /// first, cursor, last - ссылки на первый, /// активный и последний элементы списка /// Запросы count, index search_res также /// реализуются атрибутами. /// Запросы empty, item реализуются функциями /// </summary> protected TwoLinkable first, cursor, last; protected int count, index; protected bool search_res; //доступ на чтение к закрытым свойствам; public int Count { get { return(count); } } public int Index { get { return(index); } } public bool Search_res { get { return(search_res); } } /// <summary> /// require: true; возвращает true для непустого списка /// </summary> /// <returns></returns> public bool empty() { return(first == null); }//empty /// <summary> /// require: not empty(); возвращает активный /// элемент типа G; /// </summary> /// <returns></returns> public Figure item() { return(cursor.Item); }//item /// <summary> /// require: true; /// ensure: добавить новый элемент (elem) слева /// от курсора; /// </summary> /// <param name="elem">Тип Figure играет роль /// родового типа G /// хранимого элемента elem</param> public void put_left(Figure elem) { TwoLinkable newitem = new TwoLinkable(); newitem.Item = elem; newitem.Next = cursor; if (empty()) //список пуст { first = cursor = last = newitem; index =1; count = 1; } else { if (index == 1) first =newitem; else cursor.Prev.Next = newitem; newitem.Prev = cursor.Prev; cursor.Prev = newitem; count++; index++; } }//put_right /// <summary> /// require: true; /// ensure: добавить новый элемент (elem) справа /// от курсора; /// </summary> /// <param name="elem">Тип Figure играет роль /// родового типа G /// хранимого элемента elem</param> public void put_right(Figure elem) { TwoLinkable newitem = new TwoLinkable(); newitem.Item = elem; newitem.Prev = cursor; if (empty()) //список пуст { first = cursor = last = newitem; index =1; count = 1; } else { if (index == count) last =newitem; else cursor.Next.Prev = newitem;
newitem.Next = cursor.Next; cursor.Next = newitem; count++; } }//put_right public void remove() { if(count == 1) { first = last = cursor = null; index=0; } else if(index==1) { first = cursor.Next; cursor.Prev = null; cursor = cursor.Next; } else if(index == count) { last = cursor.Prev; cursor.Next = null; cursor = cursor.Prev; index--; } else { cursor.Prev.Next = cursor.Next; cursor.Next.Prev = cursor.Prev; cursor = cursor.Next; } count--; }//remove /// операции с курсором: /// <summary> /// start: require: true; /// ensure: сделать активным первый элемент; /// </summary> public void start() { cursor = first; index = 1; }//start /// <summary> /// finish: require: true; /// ensure: сделать активным последний элемент; /// </summary> public void finish() { cursor = last; index = count; }//finish /// <summary> /// go_prev: require: not (index = 1); /// ensure: сделать активным предыдущий элемент; /// </summary> public void go_prev() { cursor = cursor.Prev; index--; }// go_prev /// <summary> /// go_next: require: not (index = count); /// ensure: сделать активным последующий элемент; /// </summary> public void go_next() { cursor = cursor.Next; index++; }// go_next /// <summary> /// go_i(i): require: (i in [1, count]); /// ensure: сделать активным элемент с индексом i; /// </summary> /// <param name="i"></param> public void go_i(int i) { if(i >index) while (i>index) { cursor = cursor.Next; index++; } else if(i<index) while (i<index) { cursor = cursor.Prev; index--; } }// go_i /// операции поиска: /// <summary> /// search_prev(elem): require: not (index = 1); /// ensure: сделать активным первый элемент elem /// слева от курсора; /// </summary> /// <param name="elem">искомый элемент</param> public virtual void search_prev(Figure elem) { bool found = false; while (!found && (index !=1)) { cursor = cursor.Prev; index--; found = (elem == item()); } search_res = found; }// search_prev /// <summary> /// успех или неуспех поиска сохранять в булевской /// переменной search_res /// search_next: require: not (index = count); /// ensure: сделать активным первый элемент elem /// справа от курсора; /// успех или неуспех поиска сохранять в булевской /// переменной search_res /// </summary> /// <param name="elem"></param> public virtual void search_next(Figure elem) { bool found = false; while (!found && (index !=count)) { cursor = cursor.Next; index++; found = (elem == item()); } search_res = found; }//search_next } }
Заметьте, класс подробно документирован. Для методов класса указываются предусловия и постусловия. Обратите внимание, в соответствии с принципами контрактного программирования клиент класса, прежде чем вызвать метод, должен проверить выполнимость предусловия, что повышает корректность работы системы в целом. Именно так и будет реализован вызов этих методов в классе формы, где осуществляется работа со списком.
