/*
    ChemCon - molecular mechanics and molecular graphics
    Copyright (C) 1998-2002  Alexei Nikitin

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#ifndef LIST_H
#define LIST_H

#ifndef ARRAY_H
#include "Array.h"
#endif


#if defined WIN32
#pragma warning(disable : 4355)
#endif

namespace MM
{

template< class T > class list;
template< class T > class list_iterator;
template< class T > class list_node;

template< class T >
class list_node
  {
      friend class list< T >;
      friend class list_iterator< T >;

    public:
      list_node *                 next() const;
      list_node *                 prev() const;
      list_node *                 insert( list_node * );
      list_node *                 remove();
      void                        splice( list_node * );

      list_node();
      ~list_node();
      list_node( const T & val );

    private:

      int                         Number;
      list_node                   *Next;
      list_node                   *Prev;
      
      list_node                   *original_Next;
      list_node                   *original_Prev;

      T                           Value;

      list_node( const list_node & );
      const list_node & operator=( const list_node & );
  };

template< class T > 
class list
  {
    private:
      int                         Length;
      int                         iter_counter;
     
      list_node< T >              *Head;
      list_node< T >              *Current;

      mutable Array< T * >                Data;
      mutable Array< list_node< T > * >   Node;

      Array< list_node< T > * >   changed;

    public:
      list();
      ~list();

      T &                         insert( const T & );
      T &                         prepend( const T & );
      T &                         append( const T & );
      void                        append( list & );
      void                        remove();
      void                        remove_all();

      void                        set_value( const T & );
      T &                         get_value() const;
      int                         get_number();
      list_node< T > *            get_node( int i );
      void                        set_current( int i );
      T &                         next();
      T &                         prev();
//      void                        next();
//      void                        prev();
      T &                         first();
      T &                         last();

      void                        miss( int i );
      void                        miss_current();
      void                        restore();
      void                        hard_restore();
      void                        check_restoration();

      T &                         operator[]( int i );
      const T &                   operator[]( int i ) const;
//      T &                         dangerous_access( int n )         { return *Data[n]; }

      int                         length() const;
      int                         size  () const;
      bool                        is_first() const;
      bool                        is_last() const;
      bool                        is_head() const;
      bool                        is_not_head() const;
      bool                        is_valid() const {return is_not_head();}

      list( const list & );
      const list & operator=( const list & );

    private:
      list_node< T > *            get_physical_next_node( list_node< T > * );
      list_node< T > *            get_physical_prev_node( list_node< T > * );
      void                        set_random_access();

    friend class list_iterator< T >;
  };

template< class T > 
class  list_iterator
  {
    public: 
      T &                         operator[]( int n )  { return *data_ptr_[ n ]; }

      list_iterator( list< T > &List ); 
     ~list_iterator();                    

    private:
      Array< T * >                data_ptr_;
      list< T >                   &list_;
  };

//--------------------------------------------------------
template< class T > inline list_node< T > * list_node< T >::next() const  { return Next; }
template< class T > inline list_node< T > * list_node< T >::prev() const  { return Prev; }

template< class T > inline  list_node< T > * list_node< T >::
insert( list_node * b )
  {
    list_node *c = Next;
    b->Next = c;
    b->Prev = this;
    Next = b;
    c->Prev = b;
    return b;
  }

template< class T > inline  list_node< T > * list_node< T >::
remove()
  {
    Prev->Next = Next;
    Next->Prev = Prev;
    Next = Prev = this;
    return this;
  }

template< class T > inline  void list_node< T >::
splice( list_node *b )
  {
    list_node *a  = this;
    list_node *an = a->Next;
    list_node *bn = b->Next;
    a->Next  = bn;
    b->Next  = an;
    an->Prev = b;
    bn->Prev = a;
  }

template< class T > inline list_node< T >::list_node()   
  : Next( this ), Prev( this ), original_Next( NULL ), original_Prev( NULL ) {}
//template< class T > inline list_node< T >::list_node()   : Next( NULL ), Prev( NULL ) {}
template< class T > inline list_node< T >::~list_node()  
  { Next = NULL;  Prev = NULL;  original_Next = NULL;  original_Prev = NULL; }

template< class T > inline  list_node< T >::
list_node( const T & val )
  : Next( this ), Prev( this ), 
    original_Next( NULL ), original_Prev( NULL ), 
    Value( val )
  //: Next( NULL ), Prev( NULL ), Value( val )
  {
  }
/*
template< class T > inline  list_node< T >::
list_node( const list_node &  )
  :
  {
  }

template< class T > inline  list_node< T >::
const list_node & operator=( const list_node & )
*/

//========================================================
//                 list< T >
//========================================================

template< class T > inline list< T >::
list()
  : Length(0), iter_counter( 0 )
  {
    Current = Head = new list_node< T >;
    if( Current == NULL )
        throw "list< T >::list():\n"
              "Can not allocate memory";
  }

template< class T > inline list< T >::
~list()
  { 
    remove_all();
    delete Head;
  }

template< class T > inline T &  list< T >::
insert( const T & val )
  {
    if( iter_counter )
        throw "list< T >::insert( const T & val ):\n"
              "Not allowed use insert in presence of iterators";
    Data.clear();
    Node.clear();

    list_node< T > *tmp = new list_node< T > ( val );
    if( tmp == NULL )
        throw "list< T >::insert( const T & val ):\n"
              "Can not allocate memory";
    Current->insert( tmp );
    Length++;
    return tmp->Value;
  }

template< class T > inline T &  list< T >::
prepend( const T & val )
  {
    if( iter_counter )
        throw "list< T >::insert( const T & val ):\n"
              "Not allowed use prepend in presence of iterators";
    Data.clear();
    Node.clear();

    list_node< T > *tmp = new list_node< T > ( val );
    if( tmp == NULL )
        throw "list< T >::prepend( const T & val ):\n"
              "Can not allocate memory";
    Head->insert( tmp );
    Length++;
    return tmp->Value;
  }

template< class T > inline T &  list< T >::
append( const T & val )
  {
    if( iter_counter )
        throw "list< T >::insert( const T & val ):\n"
              "Not allowed use append in presence of iterators";
    Data.clear();
    Node.clear();

    list_node< T > *tmp = new list_node< T > ( val );
    if( tmp == NULL )
        throw "list< T >::append( const T & val ):\n"
              "Can not allocate memory";
    //Head->prev()->insert( tmp );
    Head->Prev->insert( tmp );
    Length++;
    return tmp->Value;
  }

template< class T > inline void list< T >::
append( list & l )
  {
    if( iter_counter )
        throw "list< T >::insert( const T & val ):\n"
              "Not allowed use append in presence of iterators";
    Data.clear();
    Node.clear();

    list_node< T >  *a = Head->prev();
    a->splice( l.Head );
    Length += l.Length;
    l.Head->remove();
    l.Length = 0;
    l.Current = Head;
  }

template< class T > inline void list< T >::
remove()
  {
    if( iter_counter )
        throw "list< T >::insert( const T & val ):\n"
              "Not allowed use remove in presence of iterators";
    Data.clear();
    Node.clear();

    if( Current == Head )   return;
    //fixT &val = Current->Value;
    Current = Current->prev();
    delete Current->next()->remove();
    Length--;
  }

template< class T > inline void list< T >::
remove_all()
  {
    if( iter_counter )
        throw "list< T >::insert( const T & val ):\n"
              "Not allowed use remove_all in presence of iterators";
    Data.clear();
    Node.clear();

    while( Length > 0 )
      {
        first();
        remove();
      }
  }

template< class T > inline void list< T >::
set_value( const T & val )
  {
    #if NDEBUG
    #else
    if( Current == Head )  throw "list< T >::set_value( const T & val )";
    #endif
    Current->Value = val;
  }

template< class T > inline T & list< T >::
get_value() const
  {
    return  Current->Value;
  }

template< class T > inline int list< T >::
get_number()
  {
    set_random_access();
    return Current->Number;
  }

template< class T > inline list_node< T > * list< T >::
get_node( int i )
  {
    set_random_access();
    return Node[i];
  }

template< class T > inline void list< T >::
set_current( int i )                        // 0 - Head
  {
    set_random_access();
    Current = Node[i];
  }

template< class T > inline T & list< T >::
next()
  {
    Current = Current->Next;
    return  Current->Value;
  }

template< class T > inline T & list< T >::
prev()
  {
    Current = Current->Prev;
    return  Current->Value;
  }
//*/
/*template< class T > inline void list< T >::
next()
  {
    Current = Current->Next;
  }

template< class T > inline void list< T >::
prev()
  {
    Current = Current->Prev;
  }
//*/
template< class T > inline T & list< T >::
first()
  {
    Current = Head->Next;
    return  Current->Value;
  }

template< class T > inline T & list< T >::
last()
  {
    Current = Head->Prev;
    return  Current->Value;
  }

template< class T > inline void list< T >::
miss( int i )
  {
    set_random_access();
    set_current( i );
    miss_current();
  }

template< class T > inline void list< T >::
miss_current()
  {
    if( get_physical_next_node( Current )->Prev != Current )  return;   // already missed
    if( !Current->Prev->original_Next )
      {
        Current->Prev->original_Next = Current->Prev->Next;
        changed.push_back( Current->Prev );
      }
    if( !Current->Next->original_Prev )
      {
        Current->Next->original_Prev = Current->Next->Prev;
        changed.push_back( Current->Next );
      }

    Current->Prev->Next = Current->Next;
    Current->Next->Prev = Current->Prev;
  }

template< class T > inline void list< T >::
restore()
  {
    //hard_restore();
    int i;
    list_node< T > *ptr;
    for( i=0;  i<changed.size();  i++ )
      {
        ptr = changed[i];
        if( ptr->original_Next )
          {
            ptr->Next = ptr->original_Next;
            ptr->original_Next = NULL;
          }
        if( ptr->original_Prev )
          {
            ptr->Prev = ptr->original_Prev;
            ptr->original_Prev = NULL;
          }
       }
    changed.clear();
  }

template< class T > inline void list< T >::
hard_restore()
  {
    int i;
    list_node< T > *ptr = Head;

    for( i=0;  i<length();  i++ )
      {
        ptr = get_physical_next_node( ptr );
        if( ptr->original_Next )
          {
            ptr->Next = ptr->original_Next;
            ptr->original_Next = NULL;
          }
        if( ptr->original_Prev )
          {
            ptr->Prev = ptr->original_Prev;
            ptr->original_Prev = NULL;
          }
      }
    changed.clear();
  }

template< class T > inline void list< T >::
check_restoration()
  {
    int i;
    list_node< T > *ptr = Head;
    for( i=0;  i<length();  i++ )
      {
        if( ptr->Next->Prev != ptr ) throw "list< T >::check_restoration()";
        ptr = ptr->Next;
      }
  }

template< class T > inline T & list< T >::
operator[]( int n )
  {
    //set_random_access();
    if( Data.size() )      return *Data[n];
    else    
      {
        int size = length() + 1;
        //Data.add_by_default( size );
        //Node.add_by_default( size );
        Data.reserve( size );
        Node.reserve( size );
        for( int k=0;  k<size;  ++k ) //fix  reinterpret_cast???
        {
            Data.push_back( 0 );
            Node.push_back( 0 );
        }

        list_node< T > *ptr = Head; 
        for( int i=0;  i<size;  i++ )
          {
            Data[i] = &ptr->Value;
            Node[i] = ptr;
            ptr->Number = i;
            ptr = ptr->Next;
          }
      }
    return *Data[n];
  }

template< class T > inline const T & list< T >::
operator[]( int n ) const
  {
    //set_random_access();
    if( Data.size() )      return *Data[n];
    else    
      {
        int size = length() + 1;
        //Data.add_by_default( size );
        //Node.add_by_default( size );
        Data.reserve( size );
        Node.reserve( size );
        for( int k=0;  k<size;  ++k ) //fix  reinterpret_cast???
        {
            Data.push_back( 0 );
            Node.push_back( 0 );
        }

        list_node< T > *ptr = Head; 
        for( int i=0;  i<size;  i++ )
          {
            Data[i] = &ptr->Value;
            Node[i] = ptr;
            ptr->Number = i;
            ptr = ptr->Next;
          }
      }
    return *Data[n];
  }

template< class T > inline int  list< T >::                       
length() const
  {
    return  Length;
  }

template< class T > inline int  list< T >::                       
size() const
  {
    return  Length;
  }

template< class T > inline bool   list< T >::                        
is_first() const
  {
    return  ( Current == Head->next() ) && ( Length > 0 );
  }

template< class T > inline bool   list< T >::                        
is_last() const
  {
    return  ( Current == Head->prev() ) && ( Length > 0 );
  }

template< class T > inline bool  list< T >::                        
is_head() const
  {
    return Current == Head;
  }

template< class T > inline bool  list< T >::                        
is_not_head() const
  {
    return Current != Head;
  }

template< class T > inline  list< T >::
list( const list< T > &r )
  : Length( 0 ), iter_counter( 0 )
  {
    Current = Head = new list_node< T >;
    if( Current == NULL )
        throw "list< T >::list( list< T > &r ):\n"
              "Can not allocate memory";

    list_node< T > *ptr = r.Head;
    for( int i=0; i<r.length();  i++ )
      {
        ptr = ptr->Next;
        append( ptr->Value );
      }
//    for( r.first();  !r.is_head();  r.next() )  append( *r.get_value() );
  }

template< class T >
inline  const list< T > & list< T >::
operator=( const list< T > & r )
  {
    if( this != &r )
      {
        remove_all();

        iter_counter = 0;
        list_node< T > *ptr = r.Head;
        for( int i=0; i<r.length();  i++ )
          {
            ptr = ptr->Next;
            append( ptr->Value );
          }
//        for( r.first();  !r.is_head();  r.next() )  append( *r.get_value() );
      }
    return *this;
  }

template< class T > inline list_node< T > * list< T >::
get_physical_next_node( list_node< T > *ptr )
  {
    return  ptr->original_Next ? ptr->original_Next : ptr->Next;
  }

template< class T > inline list_node< T > * list< T >::
get_physical_prev_node( list_node< T > *ptr )
  {
    return  ptr->original_Prev ? ptr->original_Prev : ptr->Prev;
  }

template< class T > inline void list< T >::
set_random_access()
  {
    if( Data.size() == 0 )
      {
        int size = length() + 1;
        //fix Data.add_by_default( size );
        //fix Node.add_by_default( size );
        for( int k=0;  k<size;  ++k )       //fix
        {
            Data.push_back( 0 );
            Node.push_back( 0 );
        }

        list_node< T > *ptr = Head;
        for( int i=0;  i<size;  i++ )
          {
            Data[i] = &ptr->Value;
            Node[i] = ptr;
            ptr->Number = i;
            //ptr = ptr->Next;
            ptr = get_physical_next_node( ptr );
          }
      }
  }

//--------------------------------------------------------

template< class T >
list_iterator< T >::list_iterator( list< T > &List )
  : list_( List )
    {
      list_.iter_counter++;

      int size = list_.length() + 1;
      data_ptr_.add_by_default( size );
      list_node< T > *ptr = list_.Head; 
      for( int i=1;  i<size;  i++ )
        {
          ptr = ptr->Next;
          data_ptr_[i] = &ptr->Value;
        }
    }

template< class T > 
list_iterator< T >::~list_iterator()                        
  { 
    list_.iter_counter--; 
  }

}//MM

#endif//LIST_H

