Firstov.com

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

Здесь чётко разграничены понятия список и элемент списка, хотя в свою очередь список может быть элементом другого списка. Понятию элемент списка соответсвует класс ShevItem, который содержит два указателя, виртуальный деструктор и переменную info. В первом варианте класса этой переменной не было, но затем возникли ситуации, когда нужно было объекты производных классов как-то пометить или передать с ними какую-то новую информацию. Для этих целей и появилась переменная info. Кроме того класс ShevItem стал представлять самостоятельный интерес, а не только, как базовый.

class ShevItem
{
ShevItem * prevPtr;
ShevItem * nextPtr;
protected:
virtual ~ShevItem ();
public:
int info; // дополнительная информация
// Конструктор по умолчанию
ShevItem () : prevPtr(0), nextPtr(0), info(-123456789) {}
friend class ShevList;
friend class ShowList;
friend void swapCurItems ( ShevList &, ShevList & );
};

class SLSorter
{
public:
virtual bool isOrder ( ShevItem *, ShevItem * ) const = 0;
virtual ~SLSorter();
};

class ShevList : public ShevItem
{
ShevItem * cPtr; // указатель на текущий элемент списка
ShevItem * fPtr; // указатель на первый элемент списка
ShevItem * lPtr; // указатель на последний элемент списка
int listSize; // количество элементов в списке
// Запрет конструктора копии и оператора присваивания:
ShevList ( ShevList & );
void operator = ( ShevList & );
public:
// Конструктор и деструктор:
ShevList () { cPtr = fPtr = lPtr = 0; listSize = 0; }
~ShevList ();
// Количество элементов в списке:
int size () const { return listSize; }
// Количество элементов у которых поле info равно i
int countEqual ( int i ) const;
// Текущий элемент первый?
bool curIsFir () const { return cPtr == fPtr; }
// Текущий элемент последний?
bool curIsLas () const { return cPtr == lPtr; }
// Имеется ли списке данный элемент?
bool has ( const ShevItem * ) const;
// Доступ к отдельному элементу списка:
const ShevItem * fir () const { return fPtr; }
const ShevItem * cur () const { return cPtr; }
const ShevItem * las () const { return lPtr; }
ShevItem * fir () { return fPtr; }
ShevItem * cur () { return cPtr; }
ShevItem * las () { return lPtr; }
// Сделать текущим первый элемент:
ShevItem * top () { return cPtr = fPtr; }
// Сделать текущим последний элемент:
ShevItem * end () { return cPtr = lPtr; }
// Сделать текущим предыдущий элемент:
ShevItem * prev () { return cPtr != fPtr ? cPtr = cPtr->prevPtr : 0; }
// Сделать текущим последующий элемент:
ShevItem * next () { return cPtr != lPtr ? cPtr = cPtr->nextPtr : 0; }
// Сделать текущим предыдущий элемент в цикле:
ShevItem * cprev () { return cPtr = (cPtr== fPtr) ? lPtr :cPtr->prevPtr; }
// Сделать текущим последующий элемент в цикле:
ShevItem * cnext () { return cPtr = (cPtr== lPtr) ? fPtr :cPtr->nextPtr; }
// Сделать текущим данный элемент:
void jump ( ShevItem * m ) { cPtr = m; }
// Добавить в список один элемент перед первым:
void addBefFir ( ShevItem * );
// Добавить в список один элемент перед текущим и сделать его текущим:
void addBefCur ( ShevItem * );
// Добавить в список один элемент после текущего и сделать его текущим:
void addAftCur ( ShevItem * );
// Добавить в список один элемент после последнего:
void addAftLas ( ShevItem * );
// Изменение порядка следования элементов в списке:
void invert ();
void makeCurFir ();
void makeCurLas ();
void swapCurAndFir ();
void swapCurAndLas ();
void swapFirAndLas ();
void sort123 ();
void sort321 ();
void sort ( const SLSorter & );
void sort ( bool (*f) ( ShevItem *, ShevItem * ) );
// Перемещение одного элемента из списка в список ( Эти действия двухактовые -
// вначале элемент выносится из первого списка, затем добавляется во второй.
// Это принципиально когда списки совпадают. ):
void movFirBefFir ( ShevList & list ) { list.addBefFir ( outFir() ); }
void movFirBefCur ( ShevList & list ) { list.addBefCur ( outFir() ); }
void movFirAftCur ( ShevList & list ) { list.addAftCur ( outFir() ); }
void movFirAftLas ( ShevList & list ) { list.addAftLas ( outFir() ); }
void movCurBefFir ( ShevList & list );
void movCurBefCur ( ShevList & list );
void movCurAftCur ( ShevList & list );
void movCurAftLas ( ShevList & list );
void movLasBefFir ( ShevList & list ) { list.addBefFir ( outLas() ); }
void movLasBefCur ( ShevList & list ) { list.addBefCur ( outLas() ); }
void movLasAftCur ( ShevList & list ) { list.addAftCur ( outLas() ); }
void movLasAftLas ( ShevList & list ) { list.addAftLas ( outLas() ); }
// Перемещение группы элементов из списка в список:
void movFirBefFir ( int, ShevList & );
void movLasAftLas ( int, ShevList & );
void movAllBefFir ( ShevList & );
void movAllBefCur ( ShevList & );
void movAllAftCur ( ShevList & );
void movAllAftLas ( ShevList & );
// Для всех элементов присвоить члену info значение i:
void setAllInfo ( int i );
// Заменить значения info равные iold на inew:
void setInfo ( int iold, int inew );
protected:
// Вынос элементов из списка:
ShevItem * outFir ();
ShevItem * outCur ();
ShevItem * outLas ();
void outAll () { cPtr = fPtr = lPtr = 0; listSize = 0; }
public:
// Удаление элементов из списка:
void delFir () { delete outFir (); }
void delCur () { delete outCur (); }
void delLas () { delete outLas (); }
void delAll ();
// Проверка на наличие ошибок ( возвращает указатель на строку с описанием ошибки или 0, если ошибок не обнаружено )
const char * test () const;
// Полный обмен элементами:
friend void swap ( ShevList &, ShevList & );
// Обмен текущими элементами:
friend void swapCurItems ( ShevList &, ShevList & );
// Класс просмотра константного списка
friend class ShowList;
};

Понятию список соответсвует класс ShevList, который является производным от ShevItem. Дополнительно он содержит три указателя и целую переменную равную количеству элементов в списке. Три указателя намекают на то, что в любом списке три элемента являются особыми - это текущий, первый и последний элементы, которые иногда могут совпадать или вообще отсутствовать. Для этого класса не определены конструктор копии и оператор присваивания, поэтому они объявлены закрытыми (private). Для создания списка существует единственный конструктор, который создаёт пустой список. Деструктор предполагает, что все элементы списка были созданы оператором new и поэтому применяет к ним оператор delete. Если это не так, то его надо переопределить в производном классе.

Есть несколько константных методов: size() возвращает количество элементов в списке; countEqual ( int i ) возвращает количество элементов у которых поле info равно i; curIsFir() возвращает true, если текущий элемент является первым; curIsLas() возвращает true, если текущий элемент является последним; has ( ShevItem * ) возвращает true, если указанный элемент присутствует в списке и test() который будет описан ниже.

Методы fir(), cur() и las(), возвращающие соответственно указатели на первый, текущий и последний элементы списка, существуют, как в константной, так и в неконстантной форме. Хотя сами по себе они не изменяют объект типа ShevList, было бы странно иметь возможность изменять элементы у константного списка.

Следующая группа методов делает текущим некоторый элемент. Метод top() делает текущим первый элемент и возвращает указатель на него. Метод end() делает текущим последний элемент и возвращает указатель на него. Метод prev() делает текущим предыдущий элемент, если он есть и возвращает указатель на него, иначе возвращается 0. Метод next() делает текущим последующий элемент, если он есть и возвращает указатель на него, иначе возвращается 0. Метод cprev() делает текущим предыдущий элемент, если он есть, иначе последний элемент и возвращает указатель на него, т.е. это предыдущий в цикле. Метод cnext() делает текущим последующий элемент, если он есть, иначе первый элемент и возвращает указатель на него, т.е. это последующий в цикле. Метод jump ( ShevItem * m ) делает текущим данный элемент m. Это опасный метод, т.к. если m не принадлежит списку последствия будут не предсказуемые. В сомнительных случаях можно проверить наличие элемента в списке методом has.

Следующая группа методов добавляет в список один элемент. Метод addBefFir добавляет один элемент перед первым. Метод addBefCur добавляет один элемент перед текущим и делает его текущим. Метод addAftCur добавляет один элемент после текущего и делает его текущим. Метод addAftLas добавляет один элемент после последнего. Здесь действует следующее правило: если элемент добавляется относительно текущего, то текущим становится добавляемый элемент, в других случаях текущий остаётся прежним.

Следующая группа методов изменяет порядок следования элементов в списке. Метод invert меняет порядок следования на обратный. При этом первый и последний элементы меняются местами. Метод makeCurFir делает текущий элемент первым, а элемент перед ним - последним. Метод makeCurLas делает текущий элемент последним, а элемент после него - первым. Метод swapCurAndFir меняет местами текущий и первый элементы. Метод swapCurAndLas меняет местами текущий и последний элементы. Метод swapFirAndLas меняет местами первый и последний элементы. Метод sort123 упорядочивает элементы списка по возрастанию значения члена info. Метод sort321 упорядочивает элементы списка по убыванию значения члена info. Метод sort ( const SLSorter & ) упорядочивает элементы списка с помощью класса SLSorter, который определяет порядок следования. Метод sort ( bool (*f) ( ShevItem *, ShevItem * ) ) упорядочивает элементы списка с помощью функции f, которая возращает true, если данная пара элементов упорядочена и false в противным случае. Во всех этих сортировках используется один метод - сортировка слиянием.

Следующая группа методов перемещяет один элемент из списка в список. Эти действия двухактовые - вначале элемент выносится из первого списка, затем добавляется во второй. Это принципиально, когда списки совпадают. Здесь, как и в остальных методах применяются следующие сокращения: Fir - первый элемент, Cur - текущий, Las - последний, Bef - перед, Aft - после.

Следующая группа методов перемещяет несколько элементов из списка в список. Метод movFirBefFir перемещяет n первых элементов в начало второго списка. Метод movLasAftLas перемещяет n последних элементов в конец второго списка. Метод movAllBefFir перемещяет все элементы первого списка в начало второго списка. Метод movAllBefCur перемещяет все элементы первого списка перед текущим элементом второго списка. Метод movAllAftCur перемещяет все элементы первого списка после текущего элемента второго списка. Метод movAllAftLas перемещяет все элементы первого списка в конец второго списка. Здесь тоже действует правило - если элементы добавляются относительно текущего элемента, то текущим становится текущий элемент из первого списка, иначе текущий элемент остаётся прежним.

Метод setAllInfo ( int i ) для всех элементов списка присваивает члену info значение i, а метод setInfo ( int iold, int inew ) заменяет значения info равные iold на inew.

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

Следующая группа методов удаляет элементы из списка. Здесь предполагается, что элементы были созданы оператором new. Если это не так, то эти методы надо переопределить в производном классе. Если есть желание уменьшить количество вызовов операторов new/delete, можно поступить следующим образом: завести список в который складывать ненужные элементы и брать их оттуда по мере надобности.

Метод test проверяет список на наличие ошибок и возвращает указатель на строку с описанием ошибки, если ошибка есть, или 0, если ошибок нет.

Кроме методов класса есть ещё две дружественые функции. Функция swap осуществляет полный обмен элементами между двумя списками, а функция swapCurItems осуществляет обмен текущими элементами между двумя списками.

Эти два класса предназначены для использования как базовые классы, хотя в простейших случаях можно обойтись без наследования, используя член info. В большинстве случаев можно применить шаблоны, которые представлены ниже.

namespace Shev
{

template class Item : public ShevItem
{
public:
T d;
Item () {}
Item ( const T & t ) : d(t) {}
};

template class List : public ShevList
{
// Запрет конструктора копии и оператора присваивания:
List ( List & );
void operator = ( List & );
public:
List() {}
const T * fir() const { return (const T *) ShevList::fir(); }
const T * cur() const { return (const T *) ShevList::cur(); }
const T * las() const { return (const T *) ShevList::las(); }

T * fir () { return (T *) ShevList::fir (); }
T * cur () { return (T *) ShevList::cur (); }
T * las () { return (T *) ShevList::las (); }
T * top () { return (T *) ShevList::top (); }
T * end () { return (T *) ShevList::end (); }
T * prev() { return (T *) ShevList::prev(); }
T * next() { return (T *) ShevList::next(); }
T * cprev() { return (T *) ShevList::cprev(); }
T * cnext() { return (T *) ShevList::cnext(); }

void jump ( T * i ) { ShevList::jump (i); }
void addBefFir ( T * i ) { ShevList::addBefFir(i); }
void addBefCur ( T * i ) { ShevList::addBefCur(i); }
void addAftCur ( T * i ) { ShevList::addAftCur(i); }
void addAftLas ( T * i ) { ShevList::addAftLas(i); }

void movFirBefFir ( List & list ) { ShevList::movFirBefFir ( list ); }
void movFirBefCur ( List & list ) { ShevList::movFirBefCur ( list ); }
void movFirAftCur ( List & list ) { ShevList::movFirAftCur ( list ); }
void movFirAftLas ( List & list ) { ShevList::movFirAftLas ( list ); }
void movCurBefFir ( List & list ) { ShevList::movCurBefFir ( list ); }
void movCurBefCur ( List & list ) { ShevList::movCurBefCur ( list ); }
void movCurAftCur ( List & list ) { ShevList::movCurAftCur ( list ); }
void movCurAftLas ( List & list ) { ShevList::movCurAftLas ( list ); }
void movLasBefFir ( List & list ) { ShevList::movLasBefFir ( list ); }
void movLasBefCur ( List & list ) { ShevList::movLasBefCur ( list ); }
void movLasAftCur ( List & list ) { ShevList::movLasAftCur ( list ); }
void movLasAftLas ( List & list ) { ShevList::movLasAftLas ( list ); }

void movFirBefFir ( int n, List & list ) { ShevList::movFirBefFir ( n, list ); }
void movLasAftLas ( int n, List & list ) { ShevList::movLasAftLas ( n, list ); }

void movAllBefFir ( List & list ) { ShevList::movAllBefFir ( list ); }
void movAllBefCur ( List & list ) { ShevList::movAllBefCur ( list ); }
void movAllAftCur ( List & list ) { ShevList::movAllAftCur ( list ); }
void movAllAftLas ( List & list ) { ShevList::movAllAftLas ( list ); }
};

} // namespace Shev;

using namespace Shev;

Шаблон Item делает производные классы от ShevItem. В качестве параметра для него можно задавать массивы. Например:

Item * item1f;
Item * item2i;
Item * item3d;

Шаблон List делает производные классы от ShevList. В качестве параметра для него нужно задавать класс производный от ShevItem. Если есть желание сократить имя полученного класса можно воспользоваться typedef или наследованием. Например:

typedef Item Item1f;
typedef List Lis1f;
class ListList1f : public List {};