//////////////////////////////////////////////////////////////////////////////
// $Id: SmallList.h,v 1.1.1.3 2005/01/26 13:42:20 nthiery Exp $
// Name:	SmallList.h
// Purpose:	Class SmallList for efficient small lists of small objects
//		(User interface)
// Author:	Nicolas M. Thiéry <nthiery@mines.edu>
// Created:	2000/04
// Copyright:	LGPL
//////////////////////////////////////////////////////////////////////////////

// Specifications:
//  - Data structure for lists
//    - of small and fixed size (say 0..100)
//    - containing small objects of type T (sizeof(T) is typically 1)
//  - As compact and efficient as possible
//  - Value semantic with reference count

#ifndef GLIP_SMALLLIST_H
#define GLIP_SMALLLIST_H

#include <cstddef>
#include <stdexcept>
#include <iostream>
#include <string>
#include <list>
#include <iterator>
#include <functional>
#include <algorithm>

#include <GLIP/Byte.h>

namespace GLIP {

  using std::string;
  using std::reverse_iterator;
  using std::random_access_iterator_tag;
  using std::input_iterator_tag;
  using std::iterator_traits;
  using std::greater;
  using std::lexicographical_compare;

  template<class T=short int, class S=short int>
  class SmallList {

  public:

    // Standard container typedefs
    
    typedef	  T	      value_type;
    typedef	  S	      size_type;
    typedef	  value_type *pointer;
    typedef const value_type *const_pointer;
    class		      reference;
    // Note: reference is a class, for implementing copy-on-write with []
    typedef const value_type &const_reference;
    typedef       value_type *iterator;
    typedef const value_type *const_iterator;
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
    typedef reverse_iterator<iterator>	     reverse_iterator;

    // Constructors & destructor

    explicit SmallList(size_type len=0);// Constructor without initialization
    SmallList(size_type len, T value);	// Constructor with initialization
  
    template<class InputIterator>	// Constructors from iterator
    SmallList(InputIterator first, InputIterator last);
    template<class InputIterator>
    SmallList(InputIterator first, InputIterator last, size_type len);
  
    SmallList(const SmallList &);	// Copy constructor
    SmallList(const string &s);		// construct the list from s, using >>

    ~SmallList();

    // Assignment

    SmallList& operator= (const SmallList&);
    template<class InputIterator>
    SmallList& assign (InputIterator first, InputIterator last);
    template<class InputIterator>
    SmallList& assign (InputIterator first, InputIterator last, size_type len);
    SmallList& assign (std::istream& i);

    // Standard container accessors

    bool      empty    () const;
    size_type size     () const;
    size_type capacity () const;

    // Iterators & Reverse iterators
  
    iterator       	   begin  ();
    iterator       	   end    ();
    const_iterator 	   begin  () const;
    const_iterator 	   end    () const;

    reverse_iterator	   rbegin ();
    reverse_iterator	   rend   ();
    const_reverse_iterator rbegin () const;
    const_reverse_iterator rend   () const;
  
    // Standard random access operators

    value_type operator[] (size_type) const;
    reference  operator[] (size_type);
    value_type at	  (size_type) const;
    reference  at	  (size_type);

    // Other random access operators

    void       check       (size_type) const;
    // Throws an exception if the index is out of range
    value_type operator () (size_type) const;
    // View a SmallList as a function
    // For a non const SmallList, it is more efficient than [] because
    // it can be used for read-only access

    // Fine control of copy-on-write / miscellaneous
  
    SmallList& unique();
    // Ensure the representation is not shared. Logically const.
    bool is_clone (const SmallList& l) const;
    // Test if l shares the same internal representation
  
    size_t fullsizeof() const;
    // Same as sizeof(), but also measures the internal representation


    //////////////////////////////////////////////////////////////////////////
    // Private stuff
    //////////////////////////////////////////////////////////////////////////
    
  private:
    class Rep;				// Helper for sharing representation
    Rep *rep;
    value_type read (size_type) const;
    template<class T1>
    void       write(size_type, T1);
    friend class reference;

    std::list<value_type>* parse_stream(std::istream &i);

    template<class InputIterator>
    void init(InputIterator first, InputIterator last, size_type len);
    /* It might be nice to do as described in the C++ Annotations, in
       Chapter 6: Classes and memory allocation and implement two
       methods copy and destroy, and implement the constructors,
       assignment operators and destructors from them:
       
       void copy(SmallList<T,S>);
       void destroy(); */
  }; // End of class SmallList

  ////////////////////////////////////////////////////////////////////////////
  // Helper functions
  ////////////////////////////////////////////////////////////////////////////

  template <class T, class S>
  bool operator == (const SmallList<T,S> &, const SmallList<T,S> &);
  // Lexicographic comparison
  template <class T, class S>
  bool lex	   (const SmallList<T,S> &, const SmallList<T,S> &);
  // Reverse lexicographic comparison
  template <class T, class S>
  bool revlex	   (const SmallList<T,S> &, const SmallList<T,S> &);
  // Default comparison: lexicographic
  template <class T, class S>
  bool operator <  (const SmallList<T,S> &, const SmallList<T,S> &);

  // Input / Output

  template <class T, class S>
  std::ostream &operator << (std::ostream &o,      const SmallList<T,S> &p);
  template <class T, class S>
  std::istream &operator >> (std::istream &i,            SmallList<T,S> &p);

} // End of namespace GLIP

//////////////////////////////////////////////////////////////////////////////
//
//			 End of user interface
//
//////////////////////////////////////////////////////////////////////////////

// Below is the definition of what is inlined for efficiency.
// It ought to be considered implementation detail.

//////////////////////////////////////////////////////////////////////////////
// Helper class for the internal representation
//////////////////////////////////////////////////////////////////////////////

template<class T, class S>
class GLIP::SmallList<T,S>::Rep {
private:
  size_type len;
  size_type ref;
  T* data;
  
  Rep(size_type len_, T data_[]) :
    len(len_), ref(1), data((T*)malloc(len*sizeof(T))) {
    memcpy(data, data_, len*sizeof(T));
  };  // should use traits::copy and traits::malloc

public:
  // Returns uninitialized memory!
  Rep(size_type len_) :
    len(len_), ref(1), data((T*)malloc(len*sizeof(T))) { };

  ~Rep() { delete[] data; };

  void release() {
    //std::clog << ref << std::endl;
    if (--ref==0) delete this; }
  Rep *grab   () { ++ref; return this;   }
  
  Rep *unique() {
    // Returns a representation containing the same data as before.
    // Ensures this representation is not shared.
    // Don't break the representation of the other sharers.
    // Tries to reuse the former representation.
    if (ref==1) {
      return this;
    } else {
      ref--;
      return new Rep(len,data);
    }
  }

  Rep *recycle(size_type len_) {
    // Same as new Rep(len), but releases the former representation if
    // it's shared, and recycles it otherwise.
    if (ref==1) {
      if (len!=len_) {
	delete [] data;
	len=len_;
	data=new T[len];
      }
      return this;
    } else {
      ref--;
      return new Rep(len_);
    }
  }

  T*        begin() { return data;      }
  T*        end()   { return data+len;  }
  size_type size()  { return len;       }

};

//////////////////////////////////////////////////////////////////////////////
// Helper class for implementing copy-on-write with subscripting
//
// Overloading does not allow for making a difference between:
//  - cout << l[i]	// read-only access
//  - l[i] = 1		// write access
// We use the trick described in Stroustrup's Book, Ch. 11.12.
// A non const subscript returns an object of this class, which will
// trigger the copy only if there is actually an assignment.
//////////////////////////////////////////////////////////////////////////////

template<class T, class S>
class GLIP::SmallList<T,S>::reference {
private:
  SmallList<T,S> &s;
  size_type i;
public:

  reference(SmallList<T,S> &s_, size_type i_) : s(s_), i(i_) {};

  operator T() const { return s.read(i); };

  template<class T1>	// To allow for all assignments that T provides
  reference & operator=(T1 t) {
    s.unique();
    s.write(i,t);
    return *this;
  }

  reference & operator=(const reference& r) {
    s.unique();
    s.write(i,T(r));
    return *this;
  }
};


//////////////////////////////////////////////////////////////////////////////
// Inlined members

// Constructors

template<class T, class S> inline
GLIP::SmallList<T,S>::SmallList(size_type len)          : rep(new Rep(len)) {
}

template<class T, class S> inline
GLIP::SmallList<T,S>::SmallList(size_type len, T value) : rep(new Rep(len)) {
  std::uninitialized_fill(rep->begin(), rep->end(), value);
}

template<class T, class S> inline
GLIP::SmallList<T,S>::SmallList(const SmallList & l)    : rep(l.rep->grab()) {
}

// Destructor

template<class T, class S> inline
GLIP::SmallList<T,S>::~SmallList() {
  //  std::clog << "coucou" << *this << ":";
  rep->release();
}

// Utilities

template <class T, class S>
template<class InputIterator>
void GLIP::SmallList<T,S>::init(InputIterator first, InputIterator last,
				GLIP::SmallList<T,S>::size_type len)  {
  rep=new Rep(len);
  std::uninitialized_copy(first, last, rep->begin());
}

template<class T, class S> inline
GLIP::SmallList<T,S> &
GLIP::SmallList<T,S>::unique() {
  rep=rep->unique();
  return *this;
}
  
template<class T, class S> inline
GLIP::SmallList<T,S> &
GLIP::SmallList<T,S>::operator = (const SmallList& l) {
  if (&l!=this) {
    rep->release();
    rep=l.rep->grab();
  }
  return *this;
}

// Assignments

template<class T, class S>
template <class InputIterator> inline
GLIP::SmallList<T,S> &
GLIP::SmallList<T,S>::assign (InputIterator first, InputIterator last,
			      size_type len)  {
  rep=rep->recycle(len);
  uninitialized_copy(first, last, rep->begin());
  return *this;
}

template<class T, class S>
template <class InputIterator> inline
GLIP::SmallList<T,S> &
GLIP::SmallList<T,S>::assign (InputIterator first, InputIterator last) {
  return assign(first, last, distance(first,last));
}

template<class T, class S>
inline
GLIP::SmallList<T,S> &
GLIP::SmallList<T,S>::assign (std::istream& i) {
  std::list<T>* v = parse_stream(i);
  if (v==0) { throw "Parse error: SmallList expected"; };
  assign(v->begin(),v->end());
  delete(v);
  return *this;
}

// Utilities

template<class T, class S> inline
bool
GLIP::SmallList<T,S>::is_clone (const SmallList& l) const {
  return rep==l.rep;
}

template<class T, class S> inline
size_t
GLIP::SmallList<T,S>::fullsizeof() const {
  return(sizeof(rep)+sizeof(Rep)+size()*sizeof(value_type));
}

// Standard container utilities

template<class T, class S> inline
bool
GLIP::SmallList<T,S>::empty    () const { return rep->size()==0; }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::size_type
GLIP::SmallList<T,S>::size     () const { return rep->size();	 }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::size_type
GLIP::SmallList<T,S>::capacity () const { return rep->size();	 }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::iterator
GLIP::SmallList<T,S>::begin ()       { unique(); return(rep->begin());  }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::iterator
GLIP::SmallList<T,S>::end   ()       { unique(); return(rep->end  ());  }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::const_iterator
GLIP::SmallList<T,S>::begin () const {           return rep->begin();   }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::const_iterator
GLIP::SmallList<T,S>::end   () const {           return rep->end();     }

template<class T, class S> inline
typename GLIP::SmallList<T,S>::reverse_iterator
GLIP::SmallList<T,S>::rbegin()       { return reverse_iterator      (end  ());}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::reverse_iterator
GLIP::SmallList<T,S>::rend  ()       { return reverse_iterator      (begin());}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::const_reverse_iterator
GLIP::SmallList<T,S>::rbegin() const { return const_reverse_iterator(end  ());}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::const_reverse_iterator
GLIP::SmallList<T,S>:: rend () const { return const_reverse_iterator(begin());}

template<class T, class S> inline
void
GLIP::SmallList<T,S>::check	 (size_type i) const {
  if (! (i>=0 && i<rep->size()) ) throw std::out_of_range("GLIP::SmallList");
}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::value_type
GLIP::SmallList<T,S>::read	 (size_type i) const {
  return rep->begin()[i];
}

template<class T, class S>
template<class T1> inline
void
GLIP::SmallList<T,S>::write	 (size_type i, T1 t)  {
  // Defined as a template, to allow for all assignments that T
  // provides. See class reference.
  unique();
  rep->begin()[i]=t;
}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::value_type
GLIP::SmallList<T,S>::operator[] (size_type i) const {
  return read(i);
}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::reference
GLIP::SmallList<T,S>::operator[] (size_type i)       {
  return reference(*this, i);
}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::value_type
GLIP::SmallList<T,S>::at         (size_type i) const {
  check(i);
  return read(i);
}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::reference
GLIP::SmallList<T,S>::at	 (size_type i)       {
  check(i);
  return reference(*this, i);
}

template<class T, class S> inline
typename GLIP::SmallList<T,S>::value_type
GLIP::SmallList<T,S>::operator () (size_type i) const {
  return read(i);
}

// Inline helper functions

template<class T, class S> inline
bool
GLIP::operator == (const GLIP::SmallList<T,S> &p1,
		   const GLIP::SmallList<T,S> &p2) {
  if (p1.is_clone(p2)) return true;
  if (p1.size()!=p2.size()) return false;
  return(std::equal(p1.begin(), p1.end(),
		    p2.begin()));
}

template<class T, class S> inline
bool
GLIP::revlex      (const GLIP::SmallList<T,S> &p1,
		   const GLIP::SmallList<T,S> &p2) {
  if (p1.is_clone(p2)) return false;
  return(lexicographical_compare(p1.rbegin(), p1.rend(),
				 p2.rbegin(), p2.rend(),
				 greater<T>()));
}

template<class T, class S>
inline bool
GLIP::lex	   (const GLIP::SmallList<T,S> &p1,
		    const GLIP::SmallList<T,S> &p2) {
  if (p1.is_clone(p2)) return false;
  return(lexicographical_compare(p1.begin(), p1.end(),
				 p2.begin(), p2.end()));
}

template<class T, class S>
inline bool
GLIP::operator <    (const GLIP::SmallList<T,S> &p1,
		     const GLIP::SmallList<T,S> &p2) {
  return lex(p1,p2);
}

#endif	/* GLIP_SMALLLIST_H */

// Local Variables: 
// mode: c++
// End: 
