SaraP
957 lines
37 KiB
C++
957 lines
37 KiB
C++
////////////////////////////////////////////////////////////////////////////////
|
|
/**
|
|
\file
|
|
\brief \ru Список.
|
|
\en List. \~
|
|
|
|
*/
|
|
////////////////////////////////////////////////////////////////////////////////
|
|
|
|
#ifndef __TEMPL_S_LIST_H
|
|
#define __TEMPL_S_LIST_H
|
|
|
|
|
|
#include <system_types.h>
|
|
#include <templ_delete_define.h>
|
|
#include <io_define.h>
|
|
#include <tool_err_handling.h>
|
|
|
|
|
|
|
|
//-----------------------------------------------------------------------------
|
|
/** \brief \ru Элемент списка.
|
|
\en The list element. \~
|
|
\details \ru Элемент списка. \n
|
|
\en The list element. \n \~
|
|
\ingroup Base_Tools_Containers
|
|
*/
|
|
// ---
|
|
template <class Type>
|
|
class ListItem {
|
|
public:
|
|
ListItem<Type> * 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<Type> &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 <class Type>
|
|
inline ListItem<Type>::ListItem( Type *d, ListItem<Type> &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<Type> &, List<Type> & ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( void add_to_list ( List<Type> &, Type* data, const Type* after ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( void insert_to_list ( List<Type> &, List<Type> & ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( void remove_from_list ( List<Type> &, DelType shdl ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( void remove_from_list_release ( List<Type> & ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( size_t remove_from_list ( List<Type> &, List<Type> &, DelType shdl ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( bool detach_from_list ( List<Type> &, const Type * ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( size_t recalc_list ( List<Type> & ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( bool is_exist_in_list ( const List<Type> &, const Type * ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( ListItem<Type> * find_prev_in_list ( const List<Type> &, ListItem<Type>* now ) );
|
|
|
|
class reader;
|
|
class writer;
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( reader& CALL_DECLARATION operator >> ( reader& in, List<Type> & ref ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( writer& CALL_DECLARATION operator << ( writer& out, const List<Type> & ref ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( reader& CALL_DECLARATION operator >> ( reader& in, List<Type> *& ptr ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( writer& CALL_DECLARATION operator << ( writer& out, const List<Type> * 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 Type>
|
|
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<Type> * first; ///< \ru Указатель на первый элемент в списке. \en A pointer to the first list element.
|
|
ListItem<Type> * last; ///< \ru Указатель на последний элемент в списке. \en A pointer to the last list element.
|
|
|
|
ListItem<Type> * 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<Type> & ); // \ru добавить элемент в конец списка \en add an element to the end of the list
|
|
void Add ( List<Type> &l ) { add_to_list(*this, l); } // \ru добавить список list в конец данного списка \en add a list to the end of the given list
|
|
void AddAndEat( List<Type> & ); // \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<Type> & ); // \ru вставить элемент в начало списка \en insert an element to the beginning of the list
|
|
void Insert ( List<Type> &l ) { insert_to_list(*this, l); } // \ru вставить список в начало данного списка \en insert a list to the beginning of the given list
|
|
void InsertAndEat( List<Type> & ); // \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<Type> &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<Type> &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<Type> * findPrev( ListItem<Type> *now ) { return find_prev_in_list(*this, now); } // \ru найти предыдущий \en find the previous
|
|
|
|
List ( const List<Type>& ); // \ru запрещено \en forbidden
|
|
void operator = ( const List<Type>& ); // \ru запрещено \en forbidden
|
|
|
|
TEMPLATE_FRIEND void add_to_list TEMPLATE_SUFFIX ( List<Type> &, List<Type> & );
|
|
TEMPLATE_FRIEND void add_to_list TEMPLATE_SUFFIX ( List<Type> &, Type* data, const Type* after );
|
|
TEMPLATE_FRIEND void insert_to_list TEMPLATE_SUFFIX ( List<Type> &, List<Type> & );
|
|
TEMPLATE_FRIEND void remove_from_list TEMPLATE_SUFFIX ( List<Type> &, DelType shdl );
|
|
TEMPLATE_FRIEND void remove_from_list_release TEMPLATE_SUFFIX ( List<Type> & );
|
|
TEMPLATE_FRIEND size_t remove_from_list TEMPLATE_SUFFIX ( List<Type> &, List<Type> &, DelType shdl );
|
|
TEMPLATE_FRIEND bool detach_from_list TEMPLATE_SUFFIX ( List<Type> &, const Type * );
|
|
TEMPLATE_FRIEND size_t recalc_list TEMPLATE_SUFFIX ( List<Type> & );
|
|
TEMPLATE_FRIEND bool is_exist_in_list TEMPLATE_SUFFIX ( const List<Type> &, const Type * );
|
|
TEMPLATE_FRIEND ListItem<Type> * find_prev_in_list TEMPLATE_SUFFIX ( const List<Type> &, ListItem<Type>* now );
|
|
|
|
TEMPLATE_FRIEND reader& CALL_DECLARATION operator >> TEMPLATE_SUFFIX ( reader& in, List<Type> & ref );
|
|
TEMPLATE_FRIEND writer& CALL_DECLARATION operator << TEMPLATE_SUFFIX ( writer& out, const List<Type> & ref );
|
|
TEMPLATE_FRIEND reader& CALL_DECLARATION operator >> TEMPLATE_SUFFIX ( reader& in, List<Type> *& ptr );
|
|
TEMPLATE_FRIEND writer& CALL_DECLARATION operator << TEMPLATE_SUFFIX ( writer& out, const List<Type> * 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 <class Type>
|
|
inline void * List<Type>::operator new( size_t size ) {
|
|
return ::Allocate( size, typeid(List<Type>).name() );
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru Перегрузка оператора delete. \en Overloading of the "delete" operator.
|
|
// ---
|
|
template <class Type>
|
|
inline void List<Type>::operator delete( void * ptr, size_t size ) {
|
|
::Free( ptr, size, typeid(List<Type>).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 Type>
|
|
class LIterator {
|
|
protected:
|
|
List<Type> * list;
|
|
ListItem<Type> * curr;
|
|
ListItem<Type> * prev;
|
|
|
|
public:
|
|
LIterator() : list( nullptr ), curr( nullptr ), prev( nullptr ) {}
|
|
LIterator( const List<Type> & l ) : list( nullptr ), curr( nullptr ), prev( nullptr ) { Set(l); }
|
|
LIterator( const LIterator<Type> &i ) : list( i.list ), curr( i.curr ), prev( i.prev ) {}
|
|
virtual ~LIterator() {}
|
|
|
|
void Set( const List<Type>& l ) { list = (List<Type>*)&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<Type> * GetList() const { return list; }
|
|
|
|
Type& operator* () const { PRECONDITION(curr && curr->data ); return *curr->data; }
|
|
Type* operator () () const { return curr ? curr->data : nullptr; }
|
|
operator ListItem<Type>* () const { return curr; }
|
|
operator ListItem<Type>& () 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<Type> &o ) const { return list==o.list && curr==o.curr; }
|
|
bool operator != ( const LIterator<Type> &o ) const { return ! operator == (o); }
|
|
LIterator<Type> & operator = ( const List<Type> &l ) { Set(l); return* this; }
|
|
LIterator<Type> & operator = ( const LIterator<Type> &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<Type> & ); // \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<Type> & ); // \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<Type> * 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 <class Type>
|
|
inline List<Type>::~List() {
|
|
PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr );
|
|
|
|
Remove();
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru добавить элемент в конец списка \en add an element to the end of the list
|
|
//---
|
|
template <class Type>
|
|
inline void List<Type>::Add( Type* data ) {
|
|
PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr );
|
|
|
|
if ( last )
|
|
last = new ListItem<Type>( data, *last );
|
|
else
|
|
first = last = new ListItem<Type>( data );
|
|
|
|
count++;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru добавить элемент после заданного элемента \en add an element after the given element
|
|
//---
|
|
template <class Type>
|
|
inline void List<Type>::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 <class Type>
|
|
inline void List<Type>::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 <class Type>
|
|
inline void List<Type>::Add( ListItem<Type> & 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 <class Type>
|
|
inline void List<Type>::AddAndEat( List<Type> & 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 <class Type>
|
|
inline void List<Type>::Insert( Type * data )
|
|
{
|
|
PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr );
|
|
Insert( *new ListItem<Type>(data) );
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru вставить элемент в начало списка \en insert an element to the beginning of the list
|
|
//---
|
|
template <class Type>
|
|
inline void List<Type>::Insert( ListItem<Type> & item )
|
|
{
|
|
PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr );
|
|
|
|
ListItem<Type>* 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 <class Type>
|
|
inline void List<Type>::InsertAndEat( List<Type> & 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 <class Type>
|
|
inline bool List<Type>::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 <class Type>
|
|
inline void List<Type>::Close()
|
|
{
|
|
PRECONDITION( nowDelItem == nullptr && nowDelElem == nullptr );
|
|
if ( last )
|
|
last->next = first;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru разомкнуть список \en split the list
|
|
//---
|
|
template <class Type>
|
|
inline void List<Type>::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 <class Type>
|
|
inline Type * LIterator<Type>::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 <class Type>
|
|
inline void LIterator<Type>::Add( Type * data )
|
|
{
|
|
PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr );
|
|
|
|
if ( list ) {
|
|
if ( curr ) {
|
|
ListItem<Type> * newItem = new ListItem<Type>( 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 <class Type>
|
|
inline void LIterator<Type>::AddAndEat( List<Type> & 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 <class Type>
|
|
inline void LIterator<Type>::Insert( Type * data )
|
|
{
|
|
PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr );
|
|
|
|
if ( list ) {
|
|
if ( prev ) {
|
|
ListItem<Type> * newItem = new ListItem<Type>( 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 <class Type>
|
|
inline void LIterator<Type>::InsertAndEat( List<Type> & 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 <class Type>
|
|
inline void LIterator<Type>::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 <class Type>
|
|
inline void LIterator<Type>::Detach()
|
|
{
|
|
PRECONDITION( list && list->nowDelItem == nullptr && list->nowDelElem == nullptr );
|
|
|
|
if ( list && curr ) {
|
|
ListItem<Type>* 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 <class Type>
|
|
void add_to_list( List<Type> & list, Type * data, const Type * after )
|
|
{
|
|
PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr );
|
|
|
|
if ( after ) {
|
|
ListItem<Type> *c = list.first;
|
|
|
|
while ( c ) {
|
|
if ( c->data == after ) {
|
|
ListItem<Type> *newItem = new ListItem<Type>( 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 <class Type>
|
|
void add_to_list( List<Type> & to, List<Type> & from )
|
|
{
|
|
PRECONDITION( to.nowDelItem == nullptr && to.nowDelElem == nullptr );
|
|
PRECONDITION( from.nowDelItem == nullptr && from.nowDelElem == nullptr );
|
|
|
|
ListItem<Type> *curr = from.first;
|
|
while ( curr ) {
|
|
to.Add( curr->data );
|
|
curr = curr->next;
|
|
}
|
|
|
|
if ( to.owns )
|
|
from.owns = false;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
template <class Type>
|
|
void insert_to_list( List<Type> & to, List<Type> & from )
|
|
{
|
|
PRECONDITION( to.nowDelItem == nullptr && to.nowDelElem == nullptr );
|
|
PRECONDITION( from.nowDelItem == nullptr && from.nowDelElem == nullptr );
|
|
|
|
ListItem<Type> *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 <class Type>
|
|
void remove_from_list( List<Type> & list, DelType shdl )
|
|
{
|
|
PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr );
|
|
|
|
bool del = shdl==Delete || (shdl==defDelete && list.owns);
|
|
|
|
ListItem<Type> *first = list.first;
|
|
list.first = nullptr;
|
|
list.last = nullptr;
|
|
list.count = 0;
|
|
while ( first ) {
|
|
ListItem<Type> *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 <class Type>
|
|
void remove_from_list_release( List<Type> & list )
|
|
{
|
|
PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr );
|
|
|
|
ListItem<Type> *first = list.first;
|
|
list.first = nullptr;
|
|
list.last = nullptr;
|
|
list.count = 0;
|
|
while ( first ) {
|
|
ListItem<Type> *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 <class Type>
|
|
size_t remove_from_list( List<Type> & list, List<Type> & 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<Type> *curr = list.first; // \ru начнем сначала \en start from the beginning
|
|
ListItem<Type> *prev = list.last;
|
|
ListItem<Type> *del = deList.first; // \ru текущий удаляемый \en the current deleted
|
|
ListItem<Type> *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<Type> *from = curr; // \ru начинаем с текущего \en start from the current one
|
|
bool found = false;
|
|
do {
|
|
if ( curr->data == del->data ) { // \ru поймался !! \en found !!
|
|
ListItem<Type> *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<Type> *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 <class Type>
|
|
bool detach_from_list( List<Type> & from, const Type * del )
|
|
{
|
|
PRECONDITION( from.nowDelItem == nullptr && from.nowDelElem == nullptr );
|
|
|
|
ListItem<Type>* curr = from.first;
|
|
ListItem<Type>* prev = nullptr;
|
|
|
|
while( curr ) {
|
|
if ( curr->data == del ) { // \ru нашли \en found
|
|
ListItem<Type> *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 <class Type>
|
|
size_t recalc_list( List<Type> & list )
|
|
{
|
|
PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr );
|
|
|
|
list.count = 0;
|
|
ListItem<Type> *curr = list.first;
|
|
while ( curr ) {
|
|
list.count++;
|
|
curr = curr->next;
|
|
}
|
|
return list.count;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
template <class Type>
|
|
bool is_exist_in_list( const List<Type> & list, const Type * what )
|
|
{
|
|
PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr );
|
|
bool exist = false;
|
|
|
|
ListItem<Type> * curr = list.first;
|
|
while ( curr && !exist ) {
|
|
exist = ( curr->data == what );
|
|
curr = curr->next;
|
|
}
|
|
|
|
return exist;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
template <class Type>
|
|
ListItem<Type> * find_prev_in_list( const List<Type> & list, ListItem<Type> * now )
|
|
{
|
|
PRECONDITION( list.nowDelItem == nullptr && list.nowDelElem == nullptr );
|
|
|
|
if ( now ) {
|
|
ListItem<Type> *tmp = list.first;
|
|
while( tmp && tmp->next != now )
|
|
tmp = tmp->next;
|
|
return tmp;
|
|
}
|
|
|
|
return nullptr;
|
|
}
|
|
|
|
|
|
#endif // __TEMPL_S_LIST_H
|