/***************************************************************************
                          List.h  -  description
                             -------------------
    begin                : Sat, 10 Apr 2004 15:58:51 +0100
    copyright            : (C) 2004 by Tomas Oberhuber
    email                : tomas.oberhuber@fjfi.cvut.cz
 ***************************************************************************/

/* See Copyright Notice in tnl/Copyright */

#pragma once

#include <iostream>

#include <TNL/Assert.h>
#include <TNL/File.h>
#include <TNL/String.h>
#include <TNL/param-types.h>

namespace TNL {
namespace Containers {

template< class T > class ListDataElement;

/// \brief Template for double linked lists
/*! To acces elements in the list one can use method getSize() and
    operator[](). To add elements there are methods Append(),
    Prepend() and Insert() to insert an element at given
    position. To erase particular element there is method
    Erase() taking the element position. To erase all elements
    there is method reset(). There are also alternatives DeepErase()
    and DeepEraseAll() to free dynamicaly allocated data inside the
    data elements.
    The list stores pointer to last accesed element so if one goes
    seqeuntialy through the list there is no inefficiency. The
    accesing algorithm is also able to deside whether to start from
    the last accesed position or from the begining resp. from the end
    of the list. So with common use one does not need to worry about
    efficiency :-)
 */
template< class T > class List
{
   public:
      typedef T ValueType;

      /// \brief Basic constructor.
      ///
      /// Constructs an empty list.
      List();

      /// \brief Copy constructor.
      ///
      /// Construct a copy of \e list.
      /// \param list Name of another list.
      List( const List& list );

      /// \brief Destructor.
      ///
      /// Destroys the list. References to the values in the list become invalid.
      ~List();

      /// Returns the type of list.
      static String getType();

      /// Returns \e true if the list contains no items, otherwise returns \e false.
      bool isEmpty() const;

      /// Returns number of items in the list.
      int getSize() const;

      /// Indexing operator.
      T& operator[] ( const int& ind );

      /// Indexing operator for constant instances.
      const T& operator[] ( const int& ind ) const;

      const List& operator = ( const List& lst );

      bool operator == ( const List& lst ) const;

      bool operator != ( const List& lst ) const;

      /// \brief Appends new data element.
      ///
      /// Inserts \e data at the end of the list.
      bool Append( const T& data );

      /// \brief Prepends new data element.
      ///
      /// Inserts \e data at the beginning of the list.
      bool Prepend( const T& data );

      /// \brief Inserts new data element at given position.
      ///
      /// Inserts \e data at index position \e ind in the list.
      bool Insert( const T& data, const int& ind );

      /// Appends copy of another list.
      ///
      /// \param lst Name of another list.
      bool AppendList( const List< T >& lst );

      /// Prepends copy of another list.
      ///
      /// \param lst Name of another list.
      bool PrependList( const List< T >& lst );

      /// Transforms list to an \e array.
      template< typename Array >
      void toArray( Array& array );

      /***
       * \brief Checks if there is an element with value \e v in given array.
       *
       * \param v Reference to a value.
       */
      bool containsValue( const T& v ) const;

      /// Erases data element at given position.
      ///
      /// \param ind Index of the data element one chooses to remove.
      void Erase( const int& ind );

      /// Erases data element with contained data at given position.
      ///
      /// \param ind Index of the data element one chooses to remove.
      void DeepErase( const int& ind );

      /// Erases all data elements.
      void reset();

      /// \brief Erases all data elements with contained data.
      ///
      /// Frees dynamicaly allocated data inside the data elements
      void DeepEraseAll();

      /// Saves the list in binary format.
      ///
      /// \param file Name of file.
      bool Save( File& file ) const;

      /// Saves the list in binary format using method save of type T.
      ///
      /// \param file Name of file.
      bool DeepSave( File& file ) const;

      /// Loads the list from file.
      ///
      /// \param file Name of file.
      bool Load( File& file );

      /// Loads the list from file using method Load of the type T.
      ///
      /// \param file Name of file.
      bool DeepLoad( File& file );

   protected:
      /// Pointer to the first element.
      ListDataElement< T >* first;

      /// Pointer to the last element.
      /*! We use pointer to last element while adding new element to keep order of elements
       */
      ListDataElement< T >* last;

      /// List size.
      int size;

      /// Iterator.
      mutable ListDataElement< T >* iterator;

      /// Iterator index.
      mutable int index;
};

template< typename T > std::ostream& operator << ( std::ostream& str, const List< T >& list );

//! Data element for List and mStack
template< class T > class ListDataElement
{
   //! Main data
   T data;

   //! Pointer to the next element
   ListDataElement< T >* next;

   //! Pointer to the previous element
   ListDataElement< T >* previous;

   public:
   //! Basic constructor
   ListDataElement()
      : next( 0 ),
        previous( 0 ){};

   //! Constructor with given data and possibly pointer to next element
   ListDataElement( const T& dt,
                    ListDataElement< T >* prv = 0,
                    ListDataElement< T >* nxt = 0 )
      : data( dt ),
        next( nxt ),
        previous( prv ){};

   //! Destructor
   ~ListDataElement(){};

   //! Return data for non-const instances
   T& Data() { return data; };

   //! Return data for const instances
   const T& Data() const { return data; };

   //! Return pointer to the next element for non-const instances
   ListDataElement< T >*& Next() { return next; };

   //! Return pointer to the next element for const instances
   const ListDataElement< T >* Next() const { return next; };

   //! Return pointer to the previous element for non-const instances
   ListDataElement< T >*& Previous() { return previous; };

   //! Return pointer to the previous element for const instances
   const ListDataElement< T >* Previous() const { return previous; };
};

} // namespace Containers
} // namespace TNL

#include <TNL/Containers/List_impl.h>
