//////////////////////////////////////////////////////////////////////////////// /** \file \brief \ru Список. \en List. \~ */ //////////////////////////////////////////////////////////////////////////////// #ifndef __TEMPL_S_LIST_H #define __TEMPL_S_LIST_H #include #include #include #include //----------------------------------------------------------------------------- /** \brief \ru Элемент списка. \en The list element. \~ \details \ru Элемент списка. \n \en The list element. \n \~ \ingroup Base_Tools_Containers */ // --- template class ListItem { public: ListItem * next; ///< \ru Указатель на следующий элемент. \en A pointer to the next element. Type * data; ///< \ru Указатель на поле данных. \en A pointer to field of data. public: ListItem() : next( 0 ), data( 0 ) {} ListItem( Type *d ) : next( 0 ), data( d ) {} ListItem( Type *d, ListItem &prev ); // \ru добавить себя после заданного элемента \en add self after the given element private: ListItem ( const ListItem& ); // \ru запрещено \en forbidden void operator = ( const ListItem& ); // \ru запрещено \en forbidden }; //------------------------------------------------------------------------------ // \ru вставляет себя после item \en inserts itself after 'item' //--- template inline ListItem::ListItem( Type *d, ListItem &prev ) { next = prev.next; prev.next = this; data = d; } //------------------------------------------------------------------------------ // // --- FORVARD_DECL_TEMPLATE_TYPENAME( class LIterator ); FORVARD_DECL_TEMPLATE_TYPENAME( class List ); FORVARD_DECL_TEMPLATE_TYPENAME( void add_to_list ( List &, List & ) ); FORVARD_DECL_TEMPLATE_TYPENAME( void add_to_list ( List &, Type* data, const Type* after ) ); FORVARD_DECL_TEMPLATE_TYPENAME( void insert_to_list ( List &, List & ) ); FORVARD_DECL_TEMPLATE_TYPENAME( void remove_from_list ( List &, DelType shdl ) ); FORVARD_DECL_TEMPLATE_TYPENAME( void remove_from_list_release ( List & ) ); FORVARD_DECL_TEMPLATE_TYPENAME( size_t remove_from_list ( List &, List &, DelType shdl ) ); FORVARD_DECL_TEMPLATE_TYPENAME( bool detach_from_list ( List &, const Type * ) ); FORVARD_DECL_TEMPLATE_TYPENAME( size_t recalc_list ( List & ) ); FORVARD_DECL_TEMPLATE_TYPENAME( bool is_exist_in_list ( const List &, const Type * ) ); FORVARD_DECL_TEMPLATE_TYPENAME( ListItem * find_prev_in_list ( const List &, ListItem* now ) ); class reader; class writer; FORVARD_DECL_TEMPLATE_TYPENAME( reader& CALL_DECLARATION operator >> ( reader& in, List & ref ) ); FORVARD_DECL_TEMPLATE_TYPENAME( writer& CALL_DECLARATION operator << ( writer& out, const List & ref ) ); FORVARD_DECL_TEMPLATE_TYPENAME( reader& CALL_DECLARATION operator >> ( reader& in, List *& ptr ) ); FORVARD_DECL_TEMPLATE_TYPENAME( writer& CALL_DECLARATION operator << ( writer& out, const List * ptr ) ); //----------------------------------------------------------------------------- /** \brief \ru Cписок указателей на элементы. \en List of pointers to elements. \~ \details \ru Cписок указателей на элементы. \n \en List of pointers to elements. \n \~ \ingroup Base_Tools_Containers */ // --- template class List { protected: bool owns; ///< \ru Признак владения элементами. \en Attribute of ownership of elements. size_t count; ///< \ru Кол-во эл-тов в списке. \en The number of elements in the list. ListItem * first; ///< \ru Указатель на первый элемент в списке. \en A pointer to the first list element. ListItem * last; ///< \ru Указатель на последний элемент в списке. \en A pointer to the last list element. ListItem * nowDelItem; // \ru Bременно, для отладки \en Temporarily, for debugging Type * nowDelElem; // \ru Bременно, для отладки \en Temporarily, for debugging public: explicit List( bool ownsEl = true ) : owns( ownsEl ) , count( 0 ) , first( nullptr ) , last( nullptr ) , nowDelItem( nullptr ) , nowDelElem( nullptr ) {} virtual ~List(); bool OwnsElem() const { return owns; } void OwnsElem( bool ownsEl ) { owns = ownsEl; } void Add( Type * ); // \ru добавить элемент в конец списка \en add an element to the end of the list void Add( Type *, const Type *after ); // \ru добавить элемент после заданного элемента \en add an element after the given element void Add( Type *, bool check ); // \ru добавить элемент в конец списка с проверкой на существование \en add an element in the end of the list with existence validation. void Add ( ListItem & ); // \ru добавить элемент в конец списка \en add an element to the end of the list void Add ( List &l ) { add_to_list(*this, l); } // \ru добавить список list в конец данного списка \en add a list to the end of the given list void AddAndEat( List & ); // \ru съесть список list в конец данного списка \en destroy a list and add it to the end of the given list void Insert ( Type * ); // \ru вставить элемент в начало списка \en insert an element to the beginning of the list void Insert ( ListItem & ); // \ru вставить элемент в начало списка \en insert an element to the beginning of the list void Insert ( List &l ) { insert_to_list(*this, l); } // \ru вставить список в начало данного списка \en insert a list to the beginning of the given list void InsertAndEat( List & ); // \ru съесть список в начало данного списка \en destroy and add a list to the beginning of the given list void Flush ( DelType shdl=defDelete ) { Remove( shdl ); } // \ru удалить все элементы списка \en delete all elements of the list void Remove( DelType shdl=defDelete ) { remove_from_list(*this, shdl); } // \ru удалить все элементы списка \en delete all elements of the list void FlushRelease() { RemoveRelease(); } // \ru удалить все элементы списка \en delete all elements of the list void RemoveRelease() { remove_from_list_release(*this); } // \ru удалить все элементы списка \en delete all elements of the list bool Remove( Type *, DelType=defDelete ); // \ru удалить один элемент списка \en delete one element of the list size_t Remove( List &l, DelType shdl=defDelete ) { return remove_from_list(*this, l, shdl ); } // \ru удалить все элементы принадлежащие списку l \en delete all elements from the list l bool Detach( const Type *d ) { return detach_from_list(*this, d); } // \ru отсоединить один элемент списка \en detach one element from the list size_t Detach( List &l ) { return Remove(l, noDelete); } // \ru отсоединить от списка другой список элементов \en detach other list from the list void Close(); // \ru замкнуть список \en close the list void Split(); // \ru разомкнуть список \en split the list size_t Count() const { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); return count; } // \ru дать количество элементов в списке \en get the number of elements in the list size_t ReCalc() { return recalc_list(*this); }// \ru пересчитать количество элементов в списке \en count the number of elements in the list bool IsEmpty () const { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); return first == 0; } // \ru проверить, пустой ли список \en check whether the list is empty bool IsExist( const Type * d ) const { return is_exist_in_list(*this, d);} // \ru найти элемент по равенству указателей \en find an element by the equality of pointers Type * GetFirstData() const { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); PRECONDITION( first ); return first->data; } // \ru получить данные первого элемента списка \en get the data of the first element of the list Type * GetLastData() const { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); PRECONDITION( last ); return last->data; } // \ru получить данные последнего элемента списка \en get the data of the last element of the list protected: TEMPLATE_FRIEND class LIterator TEMPLATE_SUFFIX; private: ListItem * findPrev( ListItem *now ) { return find_prev_in_list(*this, now); } // \ru найти предыдущий \en find the previous List ( const List& ); // \ru запрещено \en forbidden void operator = ( const List& ); // \ru запрещено \en forbidden TEMPLATE_FRIEND void add_to_list TEMPLATE_SUFFIX ( List &, List & ); TEMPLATE_FRIEND void add_to_list TEMPLATE_SUFFIX ( List &, Type* data, const Type* after ); TEMPLATE_FRIEND void insert_to_list TEMPLATE_SUFFIX ( List &, List & ); TEMPLATE_FRIEND void remove_from_list TEMPLATE_SUFFIX ( List &, DelType shdl ); TEMPLATE_FRIEND void remove_from_list_release TEMPLATE_SUFFIX ( List & ); TEMPLATE_FRIEND size_t remove_from_list TEMPLATE_SUFFIX ( List &, List &, DelType shdl ); TEMPLATE_FRIEND bool detach_from_list TEMPLATE_SUFFIX ( List &, const Type * ); TEMPLATE_FRIEND size_t recalc_list TEMPLATE_SUFFIX ( List & ); TEMPLATE_FRIEND bool is_exist_in_list TEMPLATE_SUFFIX ( const List &, const Type * ); TEMPLATE_FRIEND ListItem * find_prev_in_list TEMPLATE_SUFFIX ( const List &, ListItem* now ); TEMPLATE_FRIEND reader& CALL_DECLARATION operator >> TEMPLATE_SUFFIX ( reader& in, List & ref ); TEMPLATE_FRIEND writer& CALL_DECLARATION operator << TEMPLATE_SUFFIX ( writer& out, const List & ref ); TEMPLATE_FRIEND reader& CALL_DECLARATION operator >> TEMPLATE_SUFFIX ( reader& in, List *& ptr ); TEMPLATE_FRIEND writer& CALL_DECLARATION operator << TEMPLATE_SUFFIX ( writer& out, const List * ptr ); #ifdef __DEBUG_MEMORY_ALLOCATE_FREE_ public: void * operator new ( size_t ); void operator delete ( void *, size_t ); #endif // __DEBUG_MEMORY_ALLOCATE_FREE_ }; #ifdef __DEBUG_MEMORY_ALLOCATE_FREE_ //------------------------------------------------------------------------------ // \ru Перегрузка оператора new. \en Overloading of the "new" operator. // --- template inline void * List::operator new( size_t size ) { return ::Allocate( size, typeid(List).name() ); } //------------------------------------------------------------------------------ // \ru Перегрузка оператора delete. \en Overloading of the "delete" operator. // --- template inline void List::operator delete( void * ptr, size_t size ) { ::Free( ptr, size, typeid(List).name() ); } #endif // __DEBUG_MEMORY_ALLOCATE_FREE_ //----------------------------------------------------------------------------- /** \brief \ru Итератор списка. \en Iterator of list. \~ \details \ru Итератор списка. \n \en Iterator of list. \n \~ \ingroup Base_Tools_Containers */ // --- template class LIterator { protected: List * list; ListItem * curr; ListItem * prev; public: LIterator() : list( nullptr ), curr( nullptr ), prev( nullptr ) {} LIterator( const List & l ) : list( nullptr ), curr( nullptr ), prev( nullptr ) { Set(l); } LIterator( const LIterator &i ) : list( i.list ), curr( i.curr ), prev( i.prev ) {} virtual ~LIterator() {} void Set( const List& l ) { list = (List*)&l; Restart(); } void Restart() { PRECONDITION(list); curr = list->first; prev = nullptr; } Type * GetData() const { return curr ? curr->data : nullptr; } Type * GetDataAndGo(); // \ru взять данные и продвинуть итератор \en take the data and move the iterator List * GetList() const { return list; } Type& operator* () const { PRECONDITION(curr && curr->data ); return *curr->data; } Type* operator () () const { return curr ? curr->data : nullptr; } operator ListItem* () const { return curr; } operator ListItem& () const { PRECONDITION(curr); return *curr; } Type* operator ++() { prev = curr; if (curr) {curr=curr->next; return curr ? curr->data : nullptr;} else return nullptr; } Type* operator ++(int) { prev = curr; if (curr) {Type* ret=curr->data; curr=curr->next; return ret;} else return nullptr; } Type* operator --() { PRECONDITION(list); curr=prev; prev=list->findPrev(prev); return curr ? curr->data : nullptr; } Type* operator --(int) { PRECONDITION(list); if (curr) {Type* ret=curr->data; curr=prev; prev=list->findPrev(prev); return ret;} else return nullptr; } Type* operator ->() { return curr ? curr->data : nullptr; } bool operator == ( const LIterator &o ) const { return list==o.list && curr==o.curr; } bool operator != ( const LIterator &o ) const { return ! operator == (o); } LIterator & operator = ( const List &l ) { Set(l); return* this; } LIterator & operator = ( const LIterator &o ) { list=o.list; curr = o.curr; prev = o.prev; return *this; } void Add ( Type * ); // \ru добавить элемент после заданного элемента \en add an element after the given element void AddAndEat( List & ); // \ru съесть list после текущего элемента \en destroy the list and add it after the current element void Insert ( Type * ); // \ru вставить элемент перед заданным элементом \en insert an element before the given element void InsertAndEat( List & ); // \ru съесть list перед заданным элементом \en destroy the list and add it before the given element void Remove( DelType = defDelete ); // \ru удалить элемент списка и продвинуть вперед \en delete an element from the list and move forward void Detach(); // \ru отсоединить элемент списка \en detach an element from the list bool IsOK() const { return curr != nullptr; } ListItem * Next() const { PRECONDITION(curr); return curr->next; } void Go() { prev = curr; if ( curr ) curr = curr->next; } void GoLast() { PRECONDITION(list); curr = list->last; prev = list->findPrev(curr); } bool IsFirst() const { PRECONDITION(list); return curr == list->first; } bool IsLast() const { PRECONDITION(list); return curr == list->last; } }; //////////////////////////////////////////////////////////////////////////////// // // \ru список указателей на элементы \en a list of pointers to the elements // //////////////////////////////////////////////////////////////////////////////// //------------------------------------------------------------------------------ // //--- template inline List::~List() { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); Remove(); } //------------------------------------------------------------------------------ // \ru добавить элемент в конец списка \en add an element to the end of the list //--- template inline void List::Add( Type* data ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( last ) last = new ListItem( data, *last ); else first = last = new ListItem( data ); count++; } //------------------------------------------------------------------------------ // \ru добавить элемент после заданного элемента \en add an element after the given element //--- template inline void List::Add( Type* data, const Type* after ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); add_to_list( *this, data, after ); } //------------------------------------------------------------------------------ // \ru добавить элемент в конец списка с проверкой на существование \en add an element in the end of the list with existence validation //--- template inline void List::Add( Type * data, bool /*check*/ ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( !IsExist(data) ) Add( data ); } //------------------------------------------------------------------------------ // \ru добавить элемент в конец списка \en add an element to the end of the list //--- template inline void List::Add( ListItem & item ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); item.next = nullptr; if ( last ) last->next = &item; else first = &item; last = &item; count++; } //------------------------------------------------------------------------------ // \ru добавить список list в конец данного списка \en add a list to the end of the given list // \ru list после добавления становится пустым! \en a list becomes empty after the adding of it! //--- template inline void List::AddAndEat( List & list ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( list.first ) { if ( last ) { last->next = list.first; last = list.last; } else { first = list.first; last = list.last; } count += list.count; list.count = 0; list.first = list.last = nullptr; } } //------------------------------------------------------------------------------ // \ru вставить элемент в начало списка \en insert an element to the beginning of the list //--- template inline void List::Insert( Type * data ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); Insert( *new ListItem(data) ); } //------------------------------------------------------------------------------ // \ru вставить элемент в начало списка \en insert an element to the beginning of the list //--- template inline void List::Insert( ListItem & item ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); ListItem* old = first; first = &item; first->next = old; if ( !last ) last = first; count++; } //------------------------------------------------------------------------------ // \ru съесть список list в начало данного списка \en destroy and add a list to the beginning of the given list //--- template inline void List::InsertAndEat( List & list ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( list.first ) { if ( first ) { PRECONDITION( list.last ); list.last->next = first; first = list.first; } else { first = list.first; last = list.last; } count += list.count; list.count = 0; list.first = list.last = nullptr; } } //------------------------------------------------------------------------------ // \ru удалить один элемент списка \en delete one element of the list //--- template inline bool List::Remove( Type * del, DelType shdl ) { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( Detach(del) ) { if ( shdl==Delete || (shdl==defDelete && owns) ) { nowDelElem = del; delete del; nowDelElem = nullptr; } return true; } return false; } //------------------------------------------------------------------------------ // \ru замкнуть список \en close the list //--- template inline void List::Close() { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( last ) last->next = first; } //------------------------------------------------------------------------------ // \ru разомкнуть список \en split the list //--- template inline void List::Split() { PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr ); if ( last ) last->next = nullptr; } //////////////////////////////////////////////////////////////////////////////// // // \ru итератор списка \en Iterator of list // //////////////////////////////////////////////////////////////////////////////// //------------------------------------------------------------------------------ // \ru взять данные и продвинуть итератор \en take the data and move the iterator. //--- template inline Type * LIterator::GetDataAndGo() { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( curr ) { Type * ret = curr->data; prev = curr; curr = curr->next; return ret; } return nullptr; } //------------------------------------------------------------------------------ // \ru добавить элемент после текущего элемента \en add an element after the current element //--- template inline void LIterator::Add( Type * data ) { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( list ) { if ( curr ) { ListItem * newItem = new ListItem( data, *curr ); // \ru поставит себя после curr \en inserts itself after 'curr' if ( list->last == curr ) list->last = newItem; list->count++; } else list->Add( data ); } } //------------------------------------------------------------------------------ // \ru съесть list после текущего элемента \en destroy a list and add it after the current element //--- template inline void LIterator::AddAndEat( List & l ) { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( list && l.first ) { if ( curr ) { PRECONDITION( l.last ); l.last->next = curr->next; curr->next = l.first; if ( list->last == curr ) list->last = l.last; list->count += l.count; l.count = 0; l.first = l.last = nullptr; } else list->AddAndEat( l ); // \ru съесть список l в конец данного списка \en destroy a list l and add it to the end of the given list } } //------------------------------------------------------------------------------ // \ru вставить элемент перед текущим \en insert an element before the specified one //--- template inline void LIterator::Insert( Type * data ) { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( list ) { if ( prev ) { ListItem * newItem = new ListItem( data, *prev ); // \ru ставит себя после prev \en inserts itself after 'prev' if ( list->last == prev ) list->last = newItem; prev = newItem; list->count++; } else list->Insert( data ); // \ru вставить элемент в начало списка \en insert an element to the beginning of the list } } //------------------------------------------------------------------------------ // \ru съесть list перед моим текущим элементом \en destroy a list and add it before mine current element //--- template inline void LIterator::InsertAndEat( List & l ) { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( list && l.first ) { if ( prev ) { PRECONDITION( l.last ); prev->next = l.first; l.last->next = curr; prev = l.last; list->count += l.count; l.count = 0; l.first = l.last = nullptr; } else list->InsertAndEat( l ); // \ru съесть список l в конец данного списка \en destroy a list l and add it to the end of the given list } } //------------------------------------------------------------------------------ // \ru удалить текущий элемент итератора \en delete the current element of the iterator //--- template inline void LIterator::Remove( DelType shdl ) { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( list && curr ) { if ( shdl==Delete || (shdl==defDelete && list->owns) ) { list->nowDelElem = curr->data; delete curr->data; list->nowDelElem = nullptr; } Detach(); } } //------------------------------------------------------------------------------ // \ru отсоединить элемент списка \en detach an element from the list //--- template inline void LIterator::Detach() { PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr ); if ( list && curr ) { ListItem* next = curr->next; if ( prev ) prev->next = next; else list->first = next; if ( !next ) list->last = prev; list->nowDelItem = curr; delete curr; list->nowDelItem = nullptr; curr = next; prev = list->findPrev( curr ); list->count--; } } //------------------------------------------------------------------------------ template void add_to_list( List & list, Type * data, const Type * after ) { PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); if ( after ) { ListItem *c = list.first; while ( c ) { if ( c->data == after ) { ListItem *newItem = new ListItem( data, *c ); // \ru поставит себя после c \en inserts itself after 'c' if ( list.last == c ) list.last = newItem; list.count++; return; } else c = c->next; } } list.Add( data ); } //------------------------------------------------------------------------------ template void add_to_list( List & to, List & from ) { PRECONDITION( to.nowDelItem == nullptr && to.nowDelElem == nullptr ); PRECONDITION( from.nowDelItem == nullptr && from.nowDelElem == nullptr ); ListItem *curr = from.first; while ( curr ) { to.Add( curr->data ); curr = curr->next; } if ( to.owns ) from.owns = false; } //------------------------------------------------------------------------------ template void insert_to_list( List & to, List & from ) { PRECONDITION( to.nowDelItem == nullptr && to.nowDelElem == nullptr ); PRECONDITION( from.nowDelItem == nullptr && from.nowDelElem == nullptr ); ListItem *curr = from.first; while ( curr ) { to.Insert( curr->data ); curr = curr->next; } if ( to.owns ) from.owns = false; } //------------------------------------------------------------------------------ // \ru Очистить лист с возможным удаленим данных \en Clear the list with data deletion // --- template void remove_from_list( List & list, DelType shdl ) { PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); bool del = shdl==Delete || (shdl==defDelete && list.owns); ListItem *first = list.first; list.first = nullptr; list.last = nullptr; list.count = 0; while ( first ) { ListItem *temp = first; first = first->next; if ( del ) { list.nowDelElem = temp->data; delete temp->data; list.nowDelElem = nullptr; } list.nowDelItem = temp; delete temp; list.nowDelItem = nullptr; } } //------------------------------------------------------------------------------ // \ru Очистить лист с возможным удаленим данных \en Clear the list with data deletion // --- template void remove_from_list_release( List & list ) { PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); ListItem *first = list.first; list.first = nullptr; list.last = nullptr; list.count = 0; while ( first ) { ListItem *temp = first; first = first->next; list.nowDelElem = temp->data; if ( temp->data ) temp->data->Release(); list.nowDelElem = nullptr; list.nowDelItem = temp; delete temp; list.nowDelItem = nullptr; } } //------------------------------------------------------------------------------ // \ru Отцепить один список от другого с возможным удалением данных \en Detach one list from another with data deletion // --- template size_t remove_from_list( List & list, List & deList, DelType shdl ) { PRECONDITION( &list != &deList ); PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); PRECONDITION( deList.nowDelItem == nullptr && deList.nowDelElem == nullptr ); if ( !list.first || !deList.first ) // \ru какой-то из списков пуст ! \en one of the lists is empty ! return 0; bool willDel = shdl==Delete || (shdl==defDelete && list.owns); list.last->next = list.first; // \ru закольцуем список \en close the list ListItem *curr = list.first; // \ru начнем сначала \en start from the beginning ListItem *prev = list.last; ListItem *del = deList.first; // \ru текущий удаляемый \en the current deleted ListItem *pdel = nullptr; // \ru предыдущий удаляемый \en the previous deleted size_t deleted = 0; // \ru отцепленных 0 \en there are 0 detached while( del && list.first ) { // \ru есть еще пока чего удалять и откуда \en there are elements to delete ListItem *from = curr; // \ru начинаем с текущего \en start from the current one bool found = false; do { if ( curr->data == del->data ) { // \ru поймался !! \en found !! ListItem *condemned = curr; // \ru его будем удалять \en it will be deleted found = true; if ( list.first == list.last ) { // \ru если всего один элемент, то ничего не останется \en if there is only one element then nothing will be left list.count = 0; list.first = nullptr; list.last = nullptr; // \ru curr продвигать не нужно - все равно заканчиваем \en 'curr' should not be moved } else { list.count--; // \ru скорректируем счетчик \en correct the counter if ( list.first == curr ) // \ru если вдруг в начале списка - \en if it is in the beginning of the list list.first = curr->next; // \ru начало сдвинуть \en then move the beginning if ( list.last == curr ) // \ru если вдруг в конце списка - \en if it is in the end of the list list.last = prev; // \ru конец сдвинуть \en then move the end prev->next = curr->next; // \ru отцепим найденный \en detach the found one curr = curr->next; // \ru продвинемся \en move } if ( willDel ) { // \ru если надо - удалим данные \en delete the data if it is necessary list.nowDelElem = condemned->data; delete condemned->data; list.nowDelElem = nullptr; } list.nowDelItem = condemned; delete condemned; // \ru удалим квартиру \en delete condemned list.nowDelItem = nullptr; deleted++; // \ru еще один удалили \en another one has been deleted break; } else { // \ru если не нашли - продвинемся на следующий \en if nothing is found then move to the next prev = curr; curr = curr->next; } } while( curr != from ); // \ru есть где поискать \en there is something to find ListItem *next = del->next; if ( found && willDel ) { // \ru удаляем квартиру в list'е задающем список удаляемых \en delete a condemned from the list which sets the list of deleted elements if ( pdel ) pdel->next = next; else deList.first = next; if ( !next ) deList.last = pdel; deList.nowDelItem = del; delete del; // \ru помним, что данные мы уже удалили \en remember that the data has already been deleted deList.nowDelItem = nullptr; deList.count--; } else pdel = del; del = next; } if ( list.last ) list.last->next = nullptr; // \ru разорвать список \en split the list return deleted; } //------------------------------------------------------------------------------ template bool detach_from_list( List & from, const Type * del ) { PRECONDITION( from.nowDelItem == nullptr && from.nowDelElem == nullptr ); ListItem* curr = from.first; ListItem* prev = nullptr; while( curr ) { if ( curr->data == del ) { // \ru нашли \en found ListItem *next = curr->next; if ( prev ) prev->next = next; else from.first = next; if ( !next ) from.last = prev; from.nowDelItem = curr; delete curr; from.nowDelItem = nullptr; from.count--; return true; } else { prev = curr; curr = curr->next; } } return false; } //------------------------------------------------------------------------------ template size_t recalc_list( List & list ) { PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); list.count = 0; ListItem *curr = list.first; while ( curr ) { list.count++; curr = curr->next; } return list.count; } //------------------------------------------------------------------------------ template bool is_exist_in_list( const List & list, const Type * what ) { PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); bool exist = false; ListItem * curr = list.first; while ( curr && !exist ) { exist = ( curr->data == what ); curr = curr->next; } return exist; } //------------------------------------------------------------------------------ template ListItem * find_prev_in_list( const List & list, ListItem * now ) { PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr ); if ( now ) { ListItem *tmp = list.first; while( tmp && tmp->next != now ) tmp = tmp->next; return tmp; } return nullptr; } #endif // __TEMPL_S_LIST_H