#ifndef DSL_H_
        #define DSL_H_

        #include "dsexceptions.h"
        #include <iostream.h>       // For NULL

        // Deterministic skip list class class
        //
        // CONSTRUCTION: with INFINITY object that is
        //               also used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x )       --> Insert x
        // void remove( x )       --> Remove x (unimplemented)
        // Comparable find( x )   --> Return item that matches x
        // Comparable findMin( )  --> Return smallest item
        // Comparable findMax( )  --> Return largest item
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printList( )      --> Print items in sorted order


          // Node and forward declaration because g++ does
          // not understand nested classes.
        template <class Comparable>
        class DSL;

        template <class Comparable>
        class SkipNode
        {
            Comparable element;
            SkipNode  *right;
            SkipNode  *down;

            SkipNode( const Comparable & theElement = Comparable( ),
                               SkipNode *rt = NULL, SkipNode *dt = NULL )
              : element( theElement ), right( rt ), down( dt ) { }

            friend class DSL<Comparable>;
        };


        template <class Comparable>
        class DSL
        {
          public:
            explicit DSL( const Comparable & inf );
            DSL( const DSL & rhs );
            ~DSL( );

            const Comparable & findMin( ) const;
            const Comparable & findMax( ) const;
            const Comparable & find( const Comparable & x ) const;
            bool isEmpty( ) const;
            void printList( ) const;

            void makeEmpty( );
            void insert( const Comparable & x );
            void remove( const Comparable & x );

            const DSL & operator=( const DSL & rhs );
          private:
            const Comparable INFINITY;
            SkipNode<Comparable> *header;  // The list
            SkipNode<Comparable> *bottom;
            SkipNode<Comparable> *tail;

            const Comparable & elementAt( SkipNode<Comparable> * t ) const;

                // Usual recursive stuff
            void reclaimMemory( SkipNode<Comparable> *t ) const;
        };

        #include "DSL.cpp"
        #endif