/* 
 * 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_);
};


// 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;
};

*/

#define StrInitialSize 1024
#define StrIncrementSize(x) ( ( ( x >> 12 ) + 1 ) << 12 )

class Str
{
public:
	Str()
	{
		ptr_ = NULL;
		lCurSize = 0;
		lCurMaxSize = StrInitialSize;
		text_[0] = '\0';
	}
	virtual ~Str()
	{
		if( ptr_ ) free( ptr_ );
	}

	Str( char c )
	{
		ptr_ = NULL;
		lCurSize = 1;
		lCurMaxSize = StrInitialSize;
		text_[0] = c;
		text_[1] = '\0';
	}
	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 );
	Str( const Str& String );

	Str& operator = ( char c )
	{
		lCurSize = 1;
		text_[0] = c;
		text_[1] = '\0';
		// Keep the ptr and lCurMaxSize unchange, need for memory cleanup.
		return *this;
	}
	Str& operator = ( int num )
	{
		sprintf( text_, "%d", num );
		lCurSize = strlen( text_ );
		// Keep the ptr and lCurMaxSize unchange, need for memory cleanup.
		return *this;
	}
	Str& operator = ( double num )
	{
		sprintf( text_, "%g", num );
		lCurSize = strlen( text_ );
		// Keep the ptr and lCurMaxSize unchange, need for memory cleanup.
		return *this;
	}
	Str& operator = ( const char * chars )
	{
		if( chars ) {
			nset( chars, strlen( chars ) );
		}
		else {
			text_[0] = '\0';
			lCurSize = 1;
		}
		return *this;
	}
	Str& operator = ( const Str& other )
	{
		return( operator = ( other.lCurSize < StrInitialSize ? other.text_ : other.ptr_ ) );
	}

	void nset( const char * chars, int len );
	Str& nadd( const char * chars, int len );

	Str& operator += ( char c );
	Str& operator += ( int num )
	{
		char sNum[20];
		sprintf( sNum, "%d", num );
		return( operator += (sNum) );
	}
	Str& operator += ( double num )
	{
		char sNum[20];
		sprintf( sNum, "%g", num );
		return( operator += (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_ ) );
	}

	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;
	}

	virtual Str& appendSelf( Str& other )
	{
		other += *this;
		return other;
	}

	virtual void empty()
	{
		lCurSize = 0;
		text_[0] = '\0';
	}
	Bool isEmpty() const
	{
		return( lCurSize ? FALSE : TRUE );
	}

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

	virtual int length() const
	{
		return lCurSize;
	}
	Bool toDouble( double& retval ) const
	{
		char * stopper;
		retval = strtod( operator char * () , &stopper );
		return( !!*stopper );
	}

	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 );
	}

	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


//
//  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(((logBlocksize_ > LIST_SIZE_LARGE) ? logBlocksize_ << 1 : 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