Списки

Понятию "элемент списка" соответсвует класс ShevItem. Он содержит два указателя и переменную info, которая предназначена для хранения какой-нибудь информации. Эту информацию можно указать в конструкторе:

class ShevItem
{
    ShevItem * prevPtr;
    ShevItem * nextPtr;
// Запрет конструктора копии и оператора присваивания:
    ShevItem ( ShevItem & );
    void operator = ( ShevItem & );
protected:
    virtual ~ShevItem ();
public:
    int info; // дополнительная информация
// Конструктор
    explicit ShevItem ( int i = -123456789 ) : prevPtr(0), nextPtr(0), info(i) {}

friend class ShevList;
friend class ShowList;
};

Класс Predicate1 и производные от него предназначены для того, чтобы показать обладает ли элемент списка заданным свойством или нет. При помощи операторов !, || и && предикаты можно комбинировать.

class Predicate1
{
public:
    virtual bool operator () ( const ShevItem * ) = 0;
};

class InfoEQ : public Predicate1
{
public:
    const int i;
    explicit InfoEQ ( int p ) : i(p) {}
    virtual bool operator () ( const ShevItem * p );
};

class InfoNE : public Predicate1
{
public:
    const int i;
    explicit InfoNE ( int p ) : i(p) {}
    virtual bool operator () ( const ShevItem * p );
};

class InfoLT : public Predicate1
{
public:
    const int i;
    explicit InfoLT ( int p ) : i(p) {}
    virtual bool operator () ( const ShevItem * p );
};

class InfoGT : public Predicate1
{
public:
    const int i;
    explicit InfoGT ( int p ) : i(p) {}
    virtual bool operator () ( const ShevItem * p );
};

class InfoLE : public Predicate1
{
public:
    const int i;
    explicit InfoLE ( int p ) : i(p) {}
    virtual bool operator () ( const ShevItem * p );
};

class InfoGE : public Predicate1
{
public:
    const int i;
    explicit InfoGE ( int p ) : i(p) {}
    virtual bool operator () ( const ShevItem * p );
};

class NotPredicate1 : public Predicate1
{
public:
    Predicate1 & pre;
    explicit NotPredicate1 ( Predicate1 & p ) : pre(p) {}
    virtual bool operator () ( const ShevItem * p );
};

inline NotPredicate1 operator ! ( Predicate1 & p ) { return NotPredicate1(p); }

class Or_Predicate1 : public Predicate1
{
public:
    Predicate1 & pre1;
    Predicate1 & pre2;
    Or_Predicate1 ( Predicate1 & p1, Predicate1 & p2 ) : pre1(p1), pre2(p2) {}
    virtual bool operator () ( const ShevItem * p );
};

inline Or_Predicate1 operator || ( Predicate1 & p1, Predicate1 & p2 ) { return Or_Predicate1(p1,p2); }

class AndPredicate1 : public Predicate1
{
public:
    Predicate1 & pre1;
    Predicate1 & pre2;
    AndPredicate1 ( Predicate1 & p1, Predicate1 & p2 ) : pre1(p1), pre2(p2) {}
    virtual bool operator () ( const ShevItem * p );
};

inline AndPredicate1 operator && ( Predicate1 & p1, Predicate1 & p2 ) { return AndPredicate1(p1,p2); }

Класс Predicate2 и производные от него предназначены для того, чтобы показать обладает ли заданным свойством пара элементов:

class Predicate2
{
public:
    virtual bool operator () ( const ShevItem *, const ShevItem * ) = 0;
};

class Double123Sorter : public Predicate2
{
    const double * array;
public:
    explicit Double123Sorter ( const double * p ) : array ( p ) {} 
    bool operator () ( const ShevItem *, const ShevItem * );
};

class Double321Sorter : public Predicate2
{
    const double * array;
public:
    explicit Double321Sorter ( const double * p ) : array ( p ) {} 
    bool operator () ( const ShevItem *, const ShevItem * );
};

Класс Alter и производные от него предназначены для того, чтобы делать манипуляции с элементом списка. Класс InfoAP заполняет поле info членами арифметической прогрессии. При помощи класса If можно сделать условный манипулятор из исходных.

class Alter
{
public:
    virtual void operator () ( ShevItem * );
};

extern Alter none;

class InfoAsn : public Alter
{
public:
    const int i;
    explicit InfoAsn ( int p ) : i(p) {}
    virtual void operator () ( ShevItem * p );
};

class InfoAdd : public Alter
{
public:
    const int i;
    explicit InfoAdd ( int p ) : i(p) {}
    virtual void operator () ( ShevItem * p );
};

class InfoSub : public Alter
{
public:
    const int i;
    explicit InfoSub ( int p ) : i(p) {}
    virtual void operator () ( ShevItem * p );
};

class InfoMul : public Alter
{
public:
    const int i;
    explicit InfoMul ( int p ) : i(p) {}
    virtual void operator () ( ShevItem * p );
};

class InfoDiv : public Alter
{
public:
    const int i;
    explicit InfoDiv ( int p ) : i(p) {}
    virtual void operator () ( ShevItem * p );
};

class InfoAP : public Alter
{
public:
    int start, step;
    InfoAP ( int p1, int p2 ) : start(p1), step(p2) {}
    virtual void operator () ( ShevItem * p );
};

class If : public Alter
{
public:
    Predicate1 & pre;
    Alter & alt1, & alt2;
    If ( Predicate1 & p, Alter & a1, Alter & a2 ) : pre(p), alt1(a1), alt2(a2) {}
    virtual void operator () ( ShevItem * p );
};
Класс InfoActGen преднаначен для автоматического создания предикатов и манипуляторов. При этом запись Info < 5 является более наглядной, чем InfoLT ( 5 ).
class InfoActGen
{
public:
    InfoEQ operator == ( int i ) { return InfoEQ ( i ); }
    InfoNE operator != ( int i ) { return InfoNE ( i ); }
    InfoLT operator <  ( int i ) { return InfoLT ( i ); }
    InfoGT operator >  ( int i ) { return InfoGT ( i ); }
    InfoLE operator <= ( int i ) { return InfoLE ( i ); }
    InfoGE operator >= ( int i ) { return InfoGE ( i ); }

    InfoAsn operator  = ( int i ) { return InfoAsn ( i ); }
    InfoAdd operator += ( int i ) { return InfoAdd ( i ); }
    InfoSub operator -= ( int i ) { return InfoSub ( i ); }
    InfoMul operator *= ( int i ) { return InfoMul ( i ); }
    InfoDiv operator /= ( int i ) { return InfoDiv ( i ); }
};

extern InfoActGen Info;

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

class ShevList
{
    ShevItem * cPtr; // указатель на текущий элемент списка
    ShevItem * fPtr; // указатель на первый элемент списка
    ShevItem * lPtr; // указатель на последний элемент списка
    nat listSize; // количество элементов в списке
// Запрет конструктора копии и оператора присваивания:
    ShevList ( ShevList & );
    void operator = ( ShevList & );
public:
// Конструктор и деструктор:
    ShevList () { cPtr = fPtr = lPtr = 0; listSize = 0; }
    ~ShevList ();
// Количество элементов в списке:
    nat size () const { return listSize; }
// Количество элементов с заданным свойством:
    nat count ( Predicate1 & ) const;
// Первый элемент с заданным свойством:
          ShevItem * fir ( Predicate1 & );
    const ShevItem * fir ( Predicate1 & ) const;
// Последний элемент с заданным свойством:
          ShevItem * las ( Predicate1 & );
    const ShevItem * las ( Predicate1 & ) const;
// Первый элемент с минимальным info:
    const ShevItem * firMinInfo () const;
// Первый элемент с максимальным info:
    const ShevItem * firMaxInfo () 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; }
// Сделать текущим первый элемент с заданным свойством:
    bool findFir ( Predicate1 & );
// Сделать текущим последний элемент с заданным свойством:
    bool findLas ( Predicate1 & );
// Добавить один элемент
    ShevList & addBefFir ( ShevItem * ); // перед первым
    ShevList & addBefCur ( ShevItem * ); // перед текущим и сделать его текущим
    ShevList & addAftCur ( ShevItem * ); // после текущего и сделать его текущим
    ShevList & addAftLas ( ShevItem * ); // после последнего элемента
// Добавить из другого списка
    ShevList & addAllBefFir ( ShevList & ); // все элементы в начало
    ShevList & addAllBefCur ( ShevList & ); // все элементы перед текущим
    ShevList & addAllAftCur ( ShevList & ); // все элементы после текущего
    ShevList & addAllAftLas ( ShevList & ); // все элементы в конец
// Изменение порядка следования элементов в списке:
    ShevList & invert ();
    ShevList & makeFir ( ShevItem * );
    ShevList & makeLas ( ShevItem * );
    ShevList & makeCurFir () { return makeFir ( cPtr ); }
    ShevList & makeCurLas () { return makeLas ( cPtr ); }
    void sort123 ();
    void sort321 ();
// Перемещение одного элемента из списка в список ( Эти действия двухактовые -
// вначале элемент выносится из первого списка, затем добавляется во второй.
// Это принципиально когда списки совпадают. ):
    ShevList & movFirBefFir ( ShevList & list ) { list.addBefFir ( outFir() ); return *this; }
    ShevList & movFirBefCur ( ShevList & list ) { list.addBefCur ( outFir() ); return *this; }
    ShevList & movFirAftCur ( ShevList & list ) { list.addAftCur ( outFir() ); return *this; }
    ShevList & movFirAftLas ( ShevList & list ) { list.addAftLas ( outFir() ); return *this; }
    ShevList & movCurBefFir ( ShevList & list );
    ShevList & movCurBefCur ( ShevList & list );
    ShevList & movCurAftCur ( ShevList & list );
    ShevList & movCurAftLas ( ShevList & list );
    ShevList & movLasBefFir ( ShevList & list ) { list.addBefFir ( outLas() ); return *this; }
    ShevList & movLasBefCur ( ShevList & list ) { list.addBefCur ( outLas() ); return *this; }
    ShevList & movLasAftCur ( ShevList & list ) { list.addAftCur ( outLas() ); return *this; }
    ShevList & movLasAftLas ( ShevList & list ) { list.addAftLas ( outLas() ); return *this; }
// Перемещение группы элементов из списка в список:
    ShevList & movBefCurBefCur ( ShevList & );
    ShevList & movAftCurAftCur ( ShevList & );
    ShevList & movFirBefFir ( nat, ShevList & );
    ShevList & movLasAftLas ( nat, ShevList & );
    ShevList & movAllBefFir ( ShevList & ); 
    ShevList & movAllBefCur ( ShevList & ); 
    ShevList & movAllAftCur ( ShevList & ); 
    ShevList & movAllAftLas ( ShevList & ); 
    ShevList & mov123BefFir ( Predicate1 &, ShevList & );
    ShevList & mov123AftLas ( Predicate1 &, ShevList & );
    ShevList & mov321BefFir ( Predicate1 &, ShevList & );
    ShevList & mov321AftLas ( Predicate1 &, ShevList & );
    ShevList & movAftCurAftLas ( ShevList & );
// Обмен элементами внутри списка:
    ShevList & swapCurAndFir ();
    ShevList & swapCurAndLas ();
    ShevList & swapFirAndLas ();
// Обмен элементами между двумя списками:
    ShevList & swapCurAndCur ( ShevList & ); // Обмен текущими элементами
    ShevList & swapAllAndAll ( ShevList & ); // Обмен всеми элементами
// Для всех элементов присвоить члену info значение i:
    ShevList & setAllInfo ( int i );
// Обработать все элементы списка:
    ShevList & for_each123 ( Alter & );
    ShevList & for_each321 ( Alter & );
// Обработать некоторые элементы списка:
    ShevList & for_some123 ( Predicate1 &, Alter & );
    ShevList & for_some321 ( Predicate1 &, Alter & );
protected:
// Вынос элементов из списка:
    ShevItem * outFir ();
    ShevItem * outCur ();
    ShevItem * outLas ();
    ShevList & outAll () { cPtr = fPtr = lPtr = 0; listSize = 0; return *this; }
public:
// Удаление данного элемента из списка ( небезопасная функция ):
    ShevList & del ( ShevItem * m ) { cPtr = m; delete outCur (); return *this; }
// Удаление элементов из списка:
    ShevList & delFir () { delete outFir (); return *this; }
    ShevList & delCur () { delete outCur (); return *this; }
    ShevList & delLas () { delete outLas (); return *this; }
    ShevList & delAll ();
// Операции с сигналом о последнем элементе:
    bool delCur_ () { bool res = cPtr == lPtr; delete outCur(); return res; }
    bool movCurAftLas_ ( ShevList & list ) { bool res = cPtr == lPtr; movCurAftLas ( list ); return res; }
// Проверка на наличие ошибок ( возвращает указатель на строку с описанием ошибки или 0, если ошибок не обнаружено )
    const char * test () const;
// Класс просмотра константного списка
    friend class ShowList;
};

inline void swap ( ShevList & a, ShevList & b ) { a.swapAllAndAll ( b ); }

Класс ShevList имеет несколько константных методов: size() возвращает количество элементов в списке; count ( Predicate1 & ) возвращает количество элементов с заданным свойством; fir ( Predicate1 & ) возвращает указатель на первый элемент с заданным свойством; las ( Predicate1 & ) возвращает указатель на последний элемент с заданным свойством; firMinInfo () возвращает указатель на первый элемент с минимальным info; firMaxInfo () возвращает указатель на первый элемент с максимальным info; 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. Метод findFir ( Predicate1 & ) делает текущим первый элемент с заданным свойством, если он есть. Метод findLas ( Predicate1 & ) делает текущим последний элемент с заданным свойством, если он есть.

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

Следующая группа методов добавляет в список элементы из другого списка. Метод addAllBefFir добавляет все элементы в начало. Метод addAllBefCur добавляет все элементы перед текущим элементом. Метод addAllAftCur добавляет все элементы после текущего элемента. Метод addAllAftLas добавляет все элементы в конец.

Следующая группа методов изменяет порядок следования элементов в списке. Метод invert меняет порядок следования на обратный. При этом первый и последний элементы меняются местами. Метод makeFir делает заданный элемент первым, а элемент перед ним - последним. Метод makeLas делает заданный элемент последним, а элемент после него - первым. Метод makeCurFir делает текущий элемент первым, а элемент перед ним - последним. Метод makeCurLas делает текущий элемент последним, а элемент после него - первым. Метод sort123 упорядочивает элементы списка по возрастанию значения члена info. Метод sort321 упорядочивает элементы списка по убыванию значения члена info. Во всех этих сортировках используется один метод - сортировка слиянием.

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

Следующая группа методов перемещает несколько элементов из списка в список. Метод movBefCurBefCur перемещает все элементы перед текущим из одного списка в другой список перед текущим. Метод movAftCurAftCur перемещает все элементы после текущего из одного списка в другой список после текущего. Метод movFirBefFir перемещает n первых элементов в начало второго списка. Метод movLasAftLas перемещает n последних элементов в конец второго списка. Метод movAllBefFir перемещает все элементы списка в начало другого списка. Метод movAllBefCur перемещает все элементы списка перед текущим элементом другого списка. Метод movAllAftCur перемещает все элементы списка после текущего элемента другого списка. Метод movAllAftLas перемещает все элементы списка в конец другого списка. Метод mov123BefFir перемещает элементы с заданным свойством начиная с первого в начало второго списка. Метод mov123AftLas перемещает элементы с заданным свойством начиная с первого в конец второго списка. Метод mov321BefFir перемещает элементы с заданным свойством начиная с последнего в начало второго списка. Метод mov321AftLas перемещает элементы с заданным свойством начиная с последнего в конец второго списка. Метод movAftCurAftLas перемещает все элементы после текущего из одного списка в конец другого списка.

Следующая группа методов меняет местами два элемента в списке. Метод swapCurAndFir меняет текущий и первый элементы. Метод swapCurAndLas меняет текущий и последний элементы. Метод swapFirAndLas меняет первый и последний элементы.

Следующая группа методов меняет местами элементы в двух списках. Метод swapCurAndCur меняет текущие элементы. Метод swapAllAndAll меняет все элементы.

Метод setAllInfo ( int i ) для всех элементов списка присваивает члену info значение i. Методы for_each123 и for_each321 последовательно обрабатывают все элементы списка, соответственно с начала и с конца. Методы for_some123 и for_some321 последовательно обрабатывают только те элементы списка, для которых предикат имеет истинное значение.

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

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

Следующая группа методов ( delCur_, movCurAftLas_ ) выполняет операцию над текущим элементом, а потом возвращает значение true в случае, если текущий элемент был последним. Эти методы упрощают организацию некоторых циклов над списком.

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

Функция swap осуществляет полный обмен элементами между двумя списками.

Продолжение

Наверх