/* 
 * The contents of this file are subject to the Mozilla Public
 * License Version 1.1 (the "License"); you may not use this file
 * except in compliance with the License. You may obtain a copy of
 * the License at http://www.mozilla.org/MPL/
 * 
 * Software distributed under the License is distributed on an "AS
 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * rights and limitations under the License.
 * 
 * The Original Code is the Sablotron XSLT Processor.
 * 
 * The Initial Developer of the Original Code is Ginger Alliance Ltd.
 * Portions created by Ginger Alliance are Copyright (C) 2000 Ginger
 * Alliance Ltd. All Rights Reserved.
 * 
 * Contributor(s):
 * 
 * Alternatively, the contents of this file may be used under the
 * terms of the GNU General Public License Version 2 or later (the
 * "GPL"), in which case the provisions of the GPL are applicable 
 * instead of those above.  If you wish to allow use of your 
 * version of this file only under the terms of the GPL and not to
 * allow others to use your version of this file under the MPL,
 * indicate your decision by deleting the provisions above and
 * replace them with the notice and other provisions required by
 * the GPL.  If you do not delete the provisions above, a recipient
 * may use your version of this file under either the MPL or the
 * GPL.
 */

//
// datastr.h
//
// most constants (list sizes etc.) are in base.h

#ifndef DataStrHIncl
#define DataStrHIncl

// error.h will be included later:
#define BaseH_NoErrorH
#include "base.h"
#undef BaseH_NoErrorH
#include <ctype.h>

typedef unsigned long Phrase;
#define QSORT_THRESHOLD     10      // insertsort is used for smaller lists

// List is a basic structure for ordered lists. 
// If the T's are pointers, you may want to use PList instead, which
// allows you to delete the pointers (in List, they are just taken off the 
// list).

template <class T>
class List /* : public SabObj */
{
public:
    List(int logBlocksize_ = LIST_SIZE_SMALL);
        // append an element to the end of list
    void append(T x);
        // remove last element from list
    void deppend();
        // remove all elements (shrink list to size 0)
    void deppendall();
        // remove element with given index
    void rm(int);
        // test whether list is empty
    Bool isEmpty() const;
        // number of elements in list
    inline int number() const;
        // get element with given index
    T& operator[](int ndx) const;
        // get last element
    inline T& last() const;
        // swap two elements with given indices
    void swap(int,int);
    ~List(void);
protected:
    void grow();
    int nItems; 
    T *block;
    int blocksize, origBlocksize;
    virtual T* claimMemory( int nbytes ) const { return (T*) malloc(nbytes); }
    virtual T* reclaimMemory( T *p, int newbytes, int oldbytes ) const 
        { return (T*) realloc(p, newbytes); }
    virtual void returnMemory( T* &p ) const { if (p) free(p); p = NULL; }
};

// PList is for lists whose members are pointers. It adds the possibility
// to delete pointers when removing them from the list.
// The Bool parameters in its methods say whether delete[] or delete should
// be used (TRUE/FALSE, respectively).
//
template <class T>
class PList : public List<T>
{
public:
    PList(int logBlocksize_ = LIST_SIZE_SMALL);
        // free and remove the last pointer
    void freelast(Bool);
        // free and remove all pointers
    void freeall(Bool);
        // free and remove all pointers
    void freerm(int, Bool);
};


/*****************************************************************
DynBlock

  is a class for "dynamic memory blocks", i.e. blocks that can 
  grow in size.
*****************************************************************/

struct DynBlockItem
{
    char *data;
    int byteCount;
    DynBlockItem *next;
};

class DynBlock
{
    friend class DStr;
public:
    DynBlock();
    ~DynBlock();
    void nadd(const char *data, int bytes);
    Bool isEmpty() const;
    char *getPointer() const;
    char *compactToBuffer() const;
protected:
    int byteCount;
    DynBlockItem *first, *last;
    void remove();
    void compact() const;
    int compactToBuffer_(char* buf, Bool kill_);
};


#ifndef FAST_STRING

// block for the dynamic strings
class DynStrBlock : public DynBlock
{
public:
        // compact the string into one chunk,
        // prepending 'firstPart' and appending 0.
    char* compactString_(const char *firstPart, int firstLen);
};


/*****************************************************************

    Str
    static string

*****************************************************************/

class DStr;

class Str
{
public:
    friend class DStr;
        // constructors: default, copy, from char, char* and from
        // dynamic string
    Str();
    Str(const Str& string);
    Str(int num);
    Str(double num);
    Str(char c);
    Str(const char *chars);
    Str(const DStr &dstring);
    
        // assignment: from DStr, Str, char*, char, int, double
    Str& operator=(const DStr& string);
    Str& operator=(const Str& string);
    Str& operator=(const char *chars);
    Str& operator=(char c);
    Str& operator=(int number);
    Str& operator=(double dblnum);
    
        // set self to a string of length 'len' (non-NULL-terminated)
    void nset(const char* chars, int len);
    
        // set self to an empty string
    virtual void empty();
    
        // test whether the string is void
    Bool isEmpty() const;
    
        // get byte with the given index
        // NEEDS TO INCLUDE pack_()
    char operator[](int index) const;
    
        // convert to const char* (just return the internal pointer)
        // NEEDS TO INCLUDE pack_()
    virtual operator char*() const;
    
        // test for < / == / > against a Str, char*
        // NEEDS TO INCLUDE pack_()
    int compare(const Str &other) const;
    int compare(const char *otherChars) const;
    
        // test for being lex-smaller than other Str, char*
        // NEEDS TO INCLUDE pack_()
    Bool operator< (const Str &);
    Bool operator< (const char*);
    
        // test for equality: to a Str, char*
        // NEEDS TO INCLUDE pack_()
    Bool operator== (const Str& other) const;
    Bool operator== (const char* otherChars) const;
    
        // non-case-sensitive test for equality: to a Str, char*
        // NEEDS TO INCLUDE pack_()
    Bool eqNoCase(const Str& other) const;
    Bool eqNoCase(const char* otherChars) const;
    
        // get the byte length of the string
    virtual int length() const;
    
        // addition operator: with char*, Str and int
        // NEEDS TO INCLUDE pack_()
    DStr operator+ (const Str& other) const;
    DStr operator+ (const char *otherChars) const;
    DStr operator+ (int otherNum) const;
    
        // convert *this to double, return FALSE if OK
    Bool toDouble(double& retval) const;
    
    DStr& appendSelf(DStr& other);


    // THE FOLLOWING 3 FUNCTIONS WOULD BE BEST REMOVED
        // output *this to another string with whitespace trimmed
    void speakTerse(DStr &);
    static Bool namechar(char c);
    static Bool isdigit_(char c);

    virtual ~Str();
protected:
        // deallocate all memory used
    virtual void remove_() { returnMemory(text_); }
    
        // pack all parts (in derived classes) to form a valid Str
    virtual void pack_() const;

    // claimMemory and returnMemory are to facilitate allocating the character data in an arena
    virtual char* claimMemory( int nbytes ) const { return new char[nbytes]; }

    virtual void returnMemory( char *&p ) const { if (p) delete[] p; p = NULL; }
    
    char* text_;
    int byteLength_;
};


/*****************************************************************
    DStr
    dynamic string
*****************************************************************/

class DStr : public Str
{
public:
    DStr();
    DStr(char c);
    DStr(const char *chars);
    DStr(const Str& string);
    DStr(const DStr& dstring);
    
    DStr& operator=(const DStr& other);
    
        // append a string or whatever
    DStr& operator+= (const DStr& other);
    DStr& operator+= (const Str& other);
    DStr& operator+= (const char* otherChars);
    DStr& operator+= (char c);
    DStr& operator+= (int num);

    virtual DStr& appendSelf(DStr& other);
    
        // nadd adds a non-zero-terminated string
    DStr& nadd(const char *,int);
    
    virtual operator char*() const;
    virtual int length() const;

        // consume is just like += but it steals the char*'s from 'other'.
/*
    DStr& operator consume(Str &other);
    DStr& operator consume(DStr &other);
*/
    
    virtual ~DStr();
private:
        // deallocate all memory used
    virtual void remove_();    
        // pack all parts (in derived classes) to form a valid Str
    virtual void pack_() const;
    DynStrBlock blocks;
};

#else

/*****************************************************************

  String Classes: Str and DStr

  To improve the performance, each Str object is now holding a
  pre-allocated buffer of size "StrInitialSize". All string
  assignment and concatenation will be done within this pre-allocated
  buffer if possible. When overflow occurs, a dynamic allocated buffer
  will be used. The size of the dynamic allocated buffer is initially
  set to 2 times the original size, and will be redouble everytime
  an overflow occurs.

  Note: To optimize the speed, "realloc" is used for memory reallocation
        to avoid additional new, memcpy and delete. Because of this,
		memory will be allocated and deallocated using "malloc" and
		"free" internally. External allocation routines still use
		"new" and "free" for backward compatibility.

*****************************************************************/

// Pre-allocated buffer size. Currently set at 32 bytes.
#define StrInitialSize 32

class Str
{
public:
	// Default constructor.
	// Note: lCurMaxSize MUST be set to "StrInitialSize"
	//       for pre-allocated buffer.
	Str()
	{
		ptr_ = NULL;
		lCurSize = 0;
		lCurMaxSize = StrInitialSize;
		text_[0] = '\0';
	}

	// Destructor
	virtual ~Str()
	{
		if( ptr_ ) free( ptr_ );
	}

	// Basic routine to handle string assignment, size must be specified.
	void nset( const char * chars, int len );

	// Copy Constructors
	Str( char c )
	{
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		text_[0] = c;
		text_[1] = '\0';
		lCurSize = 1;
	}
	Str( int num )
	{
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		sprintf( text_, "%d", num );
		lCurSize = strlen( text_ );
	}
	Str( double num )
	{
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		sprintf( text_, "%g", num );
		lCurSize = strlen( text_ );
	}
	Str( const char * chars )
	{
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		text_[0] = '\0';
		lCurSize = 0;
		if( chars ) {
			nset( chars, strlen( chars ) );
		}
	}
	Str( const Str& String );

	// Assignment operators
	Str& operator = ( char c )
	{
		if( ptr_ ) free( ptr_ );
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		text_[0] = c;
		text_[1] = '\0';
		lCurSize = 1;
		return *this;
	}
	Str& operator = ( int num )
	{
		if( ptr_ ) free( ptr_ );
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		sprintf( text_, "%d", num );
		lCurSize = strlen( text_ );
		return *this;
	}
	Str& operator = ( double num )
	{
		if( ptr_ ) free( ptr_ );
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		sprintf( text_, "%g", num );
		lCurSize = strlen( text_ );
		return *this;
	}
	Str& operator = ( const char * chars )
	{
		if( ptr_ ) free( ptr_ );
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		text_[0] = '\0';
		lCurSize = 0;
		if( chars ) {
			nset( chars, strlen( chars ) );
		}
		return *this;
	}
	Str& operator = ( const Str& other )
	{
		return( operator = ( other.lCurSize < StrInitialSize ? other.text_ : other.ptr_ ) );
	}

	// Basic routine to handle string concatenation, size must be specified.
	Str& nadd( const char * chars, int len );

	// Append routines
	Str& operator += ( char c )
	{
		return( nadd( &c, 1 ) );
	}
	Str& operator += ( int num )
	{
		char sNum[20];
		sprintf( sNum, "%d", num );
		return( nadd( sNum, strlen( sNum ) ) );
	}
	Str& operator += ( double num )
	{
		char sNum[20];
		sprintf( sNum, "%g", num );
		return( nadd( sNum, strlen( sNum ) ) );
	}
	Str& operator += ( const char * otherChars )
	{
		return( nadd( otherChars, strlen( otherChars ) ) );
	}
	Str& operator += ( const Str& other )
	{
		return( operator += ( other.lCurSize < StrInitialSize ? other.text_ : other.ptr_ ) );
	}

	// String operations
	Str operator + ( char c ) const
	{
		Str temp( * this );
		temp += c;
		return temp;
	}
	Str operator + ( int num ) const
	{
		char sNum[20];
		sprintf( sNum, "%d", num );

		Str temp( * this );
		temp += sNum;
		return temp;
	}
	Str operator + ( double num ) const
	{
		char sNum[20];
		sprintf( sNum, "%g", num );

		Str temp( * this );
		temp += sNum;
		return temp;
	}
	Str operator + ( const char * otherChars ) const
	{
		Str temp( * this );
		temp += otherChars;
		return temp;
	}
	Str operator + ( const Str& other ) const
	{
		Str temp( * this );
		temp += ( other.lCurSize < StrInitialSize ? other.text_ : other.ptr_ );
		return temp;
	}

	// appendSelf: Append itself to the given string.
	virtual Str& appendSelf( Str& other )
	{
		other += *this;
		return other;
	}

	// empty: reset the content to an empty string.
	virtual void empty()
	{
		// Do not free the ptr_ nor reset the lCurMaxSize. Keep the ptr_
		// as it is, which may be reused in the future.
		if( ptr_ ) free( ptr_ );
		ptr_ = NULL;
		lCurMaxSize = StrInitialSize;
		text_[0] = '\0';
		lCurSize = 0;
	}
	// isEmpty: return TRUE if the content is empty.
	Bool isEmpty() const
	{
		return( lCurSize ? FALSE : TRUE );
	}

	// Type casting routines
	virtual operator char * () const
	{
		return( (char *)( lCurSize < StrInitialSize ? text_ : ptr_ ) );
	}
	Bool toDouble( double& retval ) const
	{
		char * stopper;
		retval = strtod( operator char * () , &stopper );
		return( !!*stopper );
	}

	// Comparison routines.
	int compare( const Str& other ) const
	{
		return( strcmp( lCurSize < StrInitialSize ? text_ : ptr_,
			other.lCurSize < StrInitialSize ? other.text_ : other.ptr_ ) );
	}
	int compare( const char * otherChars ) const
	{
		return( strcmp( lCurSize < StrInitialSize ? text_ : ptr_, otherChars ) );
	}
	Bool operator == ( const Str& other ) const
	{
		return( compare( other ) ? FALSE : TRUE );
	}
	Bool operator == (const char * otherChars ) const
	{
		return( compare( otherChars ) ? FALSE : TRUE );
	}
	Bool eqNoCase( const Str& other ) const
	{
		return( strEqNoCase( lCurSize < StrInitialSize ? text_ : ptr_,
			other.lCurSize < StrInitialSize ? other.text_ : other.ptr_ ) );
	}
	Bool eqNoCase( const char * otherChars ) const
	{
		return( strEqNoCase( lCurSize < StrInitialSize ? text_ : ptr_, otherChars) );
	}
	Bool operator < ( const Str& other )
	{
		return( compare( other ) < 0 ? TRUE : FALSE );
	}
	Bool operator < ( const char * otherChars )
	{
		return( compare( otherChars ) < 0 ? TRUE : FALSE );
	}

	virtual char operator [] ( int index ) const
	{
		if( lCurSize < (unsigned)index ) return '\0';
		return( lCurSize < StrInitialSize ? text_[index] : ptr_[index] );
	}

	virtual int length() const
	{
		return lCurSize;
	}

	void speakTerse( Str& ret );
	static Bool namechar( char c )
	{
		return( isalnum( c ) ? TRUE : FALSE );
	}
	static Bool isdigit_( char c )
	{
		return( isdigit( c ) ? TRUE : FALSE );
	}
	
	// The following are to facilitate allocating and
	// deallocating character data in an arena
	virtual void remove_() {}
	virtual char * claimMemory( int nbytes ) const
		{ return (char *)malloc( nbytes ); }
	virtual void returnMemory( char *&p ) const
		{ if (p) free( p ); p = NULL; }

private:
	char text_[StrInitialSize];
	char * ptr_;
	unsigned long lCurSize;
	unsigned long lCurMaxSize;
};

#define DStr Str

#endif
//
//
//  string constants and functions
//
//

void escapeChars(DStr& result, const Str& what, 
                 const char* toEscape, const char** substitutes);

extern const Str theEmptyString;

/*****************************************************************
NamespaceStack
*****************************************************************/

class NamespaceStackObj /* : public SabObj */
{
public:
   Str prefix, uri;
   Bool hide;
};

class NamespaceStack : public PList<NamespaceStackObj*>
{
public:
        // find the index of the element with the given key
    int findNum(const Str &_key) const;
        // find the value of the element with the given key
    Str* getUri(const Str &) const;
    Bool isHidden(const Str &) const;
    void appendConstruct(const Str &prefix, const Str& uri, Bool hide = false);
};

/****************************************
Q N a m e
****************************************/
// container for a QName (e.g. "books:isbn") consisting
// of the "namespace prefix", "namespace URI" and the "local part"

class NSList;
class Processor;

class QName /* : public SabObj */
{
    friend class TreeConstructer;
public:
    QName(Processor *proc_);
    QName(const QName &other);
        // set the QName from the string received from expat (using NS_SEP)
    Bool isEmpty() const;
    void empty();

        // set the name to "prefix:local". Params give ns decls and
        // say whether to expand the default namespace
    eFlag setLogical(const Str&, const NSList *, Bool);
        // set just the prefix
    void setPrefix(const Str&);
    void setLocal(const Str&);
    void setUri(const Str&);

        // return the full name
    Str getname() const;
        // return the local part
    const Str& getLocal() const;
        // return the URI
    const Str& getUri() const;
        // return the prefix
    const Str& getPrefix() const;
        // return true if a prefix is defined
    const Bool QName::hasPrefix() const;

        // check for equality to another qname
    Bool operator==(const QName &) const;

        // output to a string
    void speak(DStr&, SpeakMode) const;
        // check if our own prefix is bound to the given namespace
    Bool prefixIsNS(const Str &s) const;
        // find a prefix for this URI in the list of ns decls
    void findPrefix(const NSList&);

    Phrase
        prefix,
        uri,
        local;
private:
    Processor *proc;

};

/*****************************************************************
    S t r S t r L i s t
*****************************************************************/

class StrStr /* : public SabObj */
{
public:
    Str 
        key,
        value;
};

class StrStrList : public PList<StrStr*>
{
public:
        // find the index of the element with the given key
    int findNum(const Str &_key) const;
        // find the value of the element with the given key
    Str* find(const Str &) const;
    void appendConstruct(const Str &key, const Str& value);
};

/*****************************************************************
    P 2 L i s t
*****************************************************************/

struct PhrasePhrase
{
    Phrase key, value;
};

class P2List : public PList<PhrasePhrase*>
{
public:
        // find the index of the element with the given key
    int findNum(Phrase) const;
        // find the value of the element with the given key
    Phrase find(Phrase) const;
    void appendConstruct(Phrase key, Phrase value);
};



/*****************************************************************
    Q N a m e L i s t
*****************************************************************/

class QNameList : public PList<QName *>
{
public:
    const QName* find(const QName &what) const;
};

/*****************************************************************
    Q N a m e S t r L i s t
*****************************************************************/
class SituationObj;

struct QNameStr
{
    QNameStr ( Processor *proc_ ): key ( proc_ )
    {
    }
    QName key;
    Str value;
};

class QNameStrList : public PList<QNameStr *>
{
public:
    QNameStrList (Processor *proc_) : proc(proc_)
    {
    }
    const Str* find(const QName &what) const;
    void appendConstruct(const QName &key, const Str& value);
protected:
    Processor *proc;
};

/*****************************************************************

    S L i s t

*****************************************************************/

template <class T>
class SList: public PList<T>
{
public:
    SList(int logBlocksize_);
        // comparison of two elements
    virtual int compare(T, T)
    { assert(!"abstract compare"); return 0; }
        // insertion of an element
    void insert(T);
    void sort();
private:
    void quicksort(int bottom, int top);
    void qsPartition(int& i, int& j);
    void insertsort(int bottom, int top);
};

/*****************************************************************

t e m p l a t e   m e t h o d s

*****************************************************************/

#include "situa.h"
//#include "error.h"


/*================================================================
List methods
================================================================*/

template <class T>
List<T>::List(int logBlocksize_) 
:
origBlocksize(TWO_TO(logBlocksize_))
{
    nItems = 0;
    blocksize = 0;
    block = NULL;
};


template <class T>
void List<T>::append(T what)
{
    if (nItems >= blocksize)
    {
        if (block)
            grow();
        else
        {
            blocksize = origBlocksize;
            block = (T*) claimMemory(blocksize * sizeof(T));
            // FIXME: asserting memory request ok
            assert(block);
        }
    }
    block[nItems++] = what;
};

template <class T>
void List<T>::deppend()
{
    assert (nItems > 0);
    --nItems;
    if (!(nItems & (nItems - 1)) && (nItems >= origBlocksize))   // realloc at powers of 2
    {
        int oldblocksize = blocksize;
        blocksize = nItems;
        if (blocksize)
        {
            block = (T*) reclaimMemory(block, blocksize * sizeof(T),
                oldblocksize * sizeof(T));
            // FIXME: asserting memory request ok
            assert(block);
        }
        else
            returnMemory(block);
    }
};

// double the block size

template <class T>
void List<T>::grow()
{
    if (!block) return;
    blocksize = blocksize << 1;
    int nbytes = blocksize * sizeof(T);
    block = (T*) reclaimMemory(block, nbytes, nbytes >> 1);
    // FIXME: asserting memory request ok
    assert(block);
}

template <class T>
void List<T>::rm(int n)
{
    assert((n >= 0) && (n < nItems));
    memmove(block + n, block + n + 1, (nItems - n - 1) * sizeof(T));
    deppend();
}

template <class T>
void List<T>::swap(int i, int j)
{
    assert((i >= 0) && (i < nItems));
    assert((j >= 0) && (j < nItems));
    T temp = block[i];
    block[i] = block[j];
    block[j] = temp;
}

template <class T>
void List<T>::deppendall() 
{
    nItems = 0;
    blocksize = 0;
    returnMemory(block);
/*    if (block)
        free(block);
        */
//    block = NULL;
}

template <class T>
inline int List<T>::number() const 
{
    return nItems;
}

template <class T>
List<T>::~List()
{
    deppendall();
};

template <class T>
inline T& List<T>::operator[](int ndx) const
{
    assert((ndx < nItems) && (ndx >= 0));
    return block[ndx];
};

template <class T>
inline T& List<T>::last() const
{
    assert(nItems);
    return block[nItems - 1];
}

template <class T>
Bool List<T>::isEmpty() const
{
    return (Bool) (!nItems);
}

/*================================================================
PList methods
================================================================*/

#define deleteScalarOrVector(PTR, VECT) \
    {if (VECT) delete[] PTR; else delete PTR;}

template <class T>
PList<T>::PList(int logBlocksize_)
: List<T>(logBlocksize_)
{
}

template <class T>
void PList<T>::freelast(Bool asArray)
{
    deleteScalarOrVector(last(), asArray);
    deppend();
}

template <class T>
void PList<T>::freeall(Bool asArray)
{
    for (int i = 0; i < nItems; i++)
        deleteScalarOrVector(block[i], asArray);
    deppendall();
}

template <class T>
void PList<T>::freerm(int n, Bool asArray)
{
    assert((n >= 0) && (n < nItems));
    deleteScalarOrVector(block[n], asArray);
    rm(n);
}

/*================================================================
SList methods    
================================================================*/

template <class T>
SList<T>::SList(int logBlocksize_) 
    : PList<T>(logBlocksize_)
{
};

template <class T>
void SList<T>::insert(T what)
{
    append(what);
    int whatndx = number() - 1;
    int i, j;
    for (i=0; i < whatndx; i++)
        if (compare((*this)[whatndx],(*this)[i]) == -1) break;
    if (i < whatndx)
    {
        for (j = whatndx; j > i; j--)
            operator[](j) = operator[](j-1);
        operator[](i) = what;
    };
};

template <class T>
void SList<T>::insertsort(int bottom, int top)
{
    int ceiling, k;
    T curr;
    for (ceiling = bottom + 1; ceiling <= top; ceiling++)
    {
        curr = block[ceiling];
        for (k = ceiling - 1; k >= bottom && compare(block[k], curr) > 0; k--)
            block[k+1] = block[k];
        block[k+1] = curr;
    }
}

template <class T>
void SList<T>::qsPartition(int& bottom, int& top)
{
    int middle = (bottom + top) >> 1;
    if (compare(block[bottom], block[top]) > 0) swap(bottom, top);
    if (compare(block[middle], block[top]) > 0) swap(middle, top);
    if (compare(block[bottom], block[middle]) > 0) swap(bottom, middle);
    T pivot = block[middle];
    while (bottom <= top)
    {
        while (compare(block[++bottom], pivot) <= 0);
        while (compare(block[--top], pivot) >= 0);
        if (bottom < top) swap(bottom, top);
    };
}

template <class T>
void SList<T>::quicksort(int bottom, int top)
{
    assert(QSORT_THRESHOLD >= 3);
    int i = bottom, j = top;
    if (top - bottom < QSORT_THRESHOLD)
        insertsort(bottom, top);
    else
    {
        qsPartition(i, j);
        quicksort(bottom, j);
        quicksort(i, top);
    }
}

template <class T>
void SList<T>::sort()
{
    if (nItems < 2)
        return;
    quicksort(0, nItems - 1);
}

#endif //ifndef DataStrHIncl