#ifndef LINKED_PTR_HPP
#define LINKED_PTR_HPP
#include <algorithm>

//  Copyright Mark Borgerding, 2000. Permission to copy,
//  use, modify, sell and distribute this software is granted provided this
//  copyright notice appears in all copies. This software is provided "as is"
//  without express or implied warranty, and with no claim as to its
//  suitability for any purpose.


/*********************************************
Class                :  linked_ptr_base
______________________________________________
Responsibilities     :  - serve as a list node for specializations of 
linked_ptr<>
                         - maintain connections with left and right 
node, regardless of the type of ptr
______________________________________________
Collaborates With    :  linked_ptr<T>, which maintains the type 
safety, typed operations, and public interface
______________________________________________
Notes                :  - linked_ptr_base exists only to be the base 
class for linked_ptr<T>
                         Without it, handling polymorphism would be 
very difficult
                         (i.e. How would pointers to left and right 
neighbors be portably kept?)

                         - Re: synchronization -- linked_ptr_base was 
designed so that it alone would
                         change the values of left and right, these 
members can also be changed by
                         neighbors in another thread.  So any 
synchronization should take place
                         in linked_ptr_base (perhaps a static 
mutex/critical section?)
**********************************************/

class linked_ptr_base
{
protected:
    linked_ptr_base(void * p) throw() :ptr(p),left(this),right(this) { 
}// easy as pie

    void copy(const linked_ptr_base & other) throw () {
       const linked_ptr_base * pNewLeft = &other;
       // we place *this between other and *other.right
       ptr = pNewLeft->ptr;
       sync_lock sl;
       left = pNewLeft;
       right = left->right;
       left->right = this;
       right->left = this;
       //debugcheck();
    }

    linked_ptr_base(const linked_ptr_base & other) throw () 
:ptr(0),left(this),right(this)  {
       copy(other);
    }

    void leave_list() throw () {
       if (left != this || right != this)
       {
          sync_lock sl;
          // Take ourselves out of the list
          // and join the left and right neighbors.
          left->right = right;
          right->left = left;
          right = left = this;
       }
       //debugcheck();
    }

//   void debugcheck()  {
//      ASSERT(left && left->right == this); }
//      ASSERT(right && right->left == this); }
//   }

    bool isunique() const throw ()  { return left == this && right == this; }

    void baseswap(linked_ptr_base & other) throw ()
    {
       if (other.ptr != ptr) {
          linked_ptr_base tmp(other);// tmp shares other's ptr
          other = *this;// other shares *this's ptr
          *this = tmp;// *this shares other's original ptr
       }
    }

    void * ptr;// neighbors cannot change ptr, but subclass can
private:
    struct sync_lock // stub for now, replace this with a synchronizer
    {
       sync_lock() throw () {} // grab an exclusive lock
       ~sync_lock() throw () {}   // release lock
    };

    // neighbors can change the values of left & right, but not ptr
    mutable const linked_ptr_base * left;
    mutable const linked_ptr_base * right;
};


/*********************************************
Class                :  linked_ptr<>
______________________________________________
Responsibilities     :  - maintain a reference counted pointer to a heap object
                         - delete said heap object when the last smart 
pointer is released
                         - allow implicit conversions of polymorphic objects
                            (i.e. make a linked_ptr<foo> from 
linked_ptr<foochild> )
                         - use no heap allocations internally
______________________________________________
Collaborates With    :  - linked_ptr_base : base class that maintains 
a raw void ptr and left
                            and right node relationships
______________________________________________
Notes                :  holding the typed ptr as a void* is safe iff 
it can only be
                         set through typed means (i.e. check 
conversions at every entry point)
______________________________________________
**********************************************/

template <class T>
class linked_ptr : public linked_ptr_base
{
public:
    typedef T element_type;
    typedef linked_ptr<T> this_type;

    // default & dumb pointer construction
    explicit linked_ptr(T * p = 0)   throw ()  :linked_ptr_base(p) { }

    // copy construction
    template <class other_type>
    linked_ptr(linked_ptr<other_type> & other)   throw () 
:linked_ptr_base(other)  {
       element_type * do_nothing_ptr = other.get();// Do NOT take this 
do-nothing code out.
       // Compiling this makes sure the conversion from other_type to 
element_type is allowed.
    }
    linked_ptr(this_type & other)    throw () :  linked_ptr_base(other) {  }

    // assignment
    template <class other_type>
    this_type & operator=(linked_ptr<other_type> & other) {
       if (this != static_cast<const void *>(&other)) { // check for 
assignment to self
          // Do NOT take this do-nothing code out.
          // Compiling this makes sure the conversion from other_type 
to element_type is allowed.
          element_type * do_nothing_ptr = other.get();
          reset();
          copy(other);
       }
       return *this;
    }
    this_type & operator=(this_type & other) {
       if (this != &other){ // check for assignment to self
          reset();
          copy(other);
       }
       return *this;
    }

    void swap(this_type & other)  throw () {  baseswap(other);  }

    // destruction
    ~linked_ptr()  throw () {  try{reset();}catch(...){} }

    // access
    element_type * get() const throw () {
       return static_cast<element_type*>(ptr);
       // This is safe since there is no access to ptr
       // except through this class, and we checked its type on the way in.
    }

    element_type & operator*()const throw () {return *get();}
    element_type * operator->()const throw () {return get();}

    void reset(element_type * p=0) {
       bool lastref = isunique();
       element_type * myPtr = get();
       leave_list();
       ptr = p;
       if (lastref && myPtr)
       {
          try {delete myPtr;}catch(...){}
       }
    }

    bool unique() const throw () {  return isunique(); }
};

template <class T>
class linked_array : public linked_ptr_base
{
public:
    typedef T element_type;
    typedef linked_array<T> this_type;

    // default & dumb pointer construction
    explicit linked_array(T * p = 0)   throw ()  :linked_ptr_base(p) { }

    // copy construction
    template <class other_type>
    linked_array(linked_array<other_type> & other)   throw () 
:linked_ptr_base(other)  {
       element_type * do_nothing_ptr = other.get();// Do NOT take this 
do-nothing code out.
       // Compiling this makes sure the conversion from other_type to 
element_type is allowed.
    }
    linked_array(this_type & other)    throw () :  linked_ptr_base(other) {  }

    // assignment
    template <class other_type>
    this_type & operator=(linked_array<other_type> & other) {
       if (this != static_cast<const void *>(&other)) { // check for 
assignment to self
          // Do NOT take this do-nothing code out.
          // Compiling this makes sure the conversion from other_type 
to element_type is allowed.
          element_type * do_nothing_ptr = other.get();
          reset();
          copy(other);
       }
       return *this;
    }
    this_type & operator=(this_type & other) {
       if (this != &other){ // check for assignment to self
          reset();
          copy(other);
       }
       return *this;
    }

    void swap(this_type & other)  throw () {  baseswap(other);  }

    // destruction
    ~linked_array()  throw () {  try{reset();}catch(...){} }

    // access
    element_type * get() const throw () {
       return static_cast<element_type*>(ptr);
       // This is safe since there is no access to ptr
       // except through this class, and we checked its type on the way in.
    }

    element_type & operator[](int i) const throw() { return get()[i]; }

    void reset(element_type * p=0) {
       bool lastref = isunique();
       element_type * myPtr = get();
       leave_list();
       ptr = p;
       if (lastref && myPtr)
       {
          try {delete [] myPtr;}catch(...){}
       }
    }

    bool unique() const throw () {  return isunique(); }
};

#endif // LINKED_PTR_HPP