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

** 

**

** Implementation of QGDict and QGDictIterator classes

**

** Created : 920529

**

** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.

**

** This file is part of the tools module of the Qt GUI Toolkit.

**

** This file may be distributed under the terms of the Q Public License

** as defined by Trolltech AS of Norway and appearing in the file

** LICENSE.QPL included in the packaging of this file.

**

** This file may be distributed and/or modified under the terms of the

** GNU General Public License version 2 as published by the Free Software

** Foundation and appearing in the file LICENSE.GPL included in the

** packaging of this file.

**

** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition

** licenses may use this file in accordance with the Qt Commercial License

** Agreement provided with the Software.

**

** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE

** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

**

** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for

**   information about Qt Commercial License Agreements.

** See http://www.trolltech.com/qpl/ for QPL licensing information.

** See http://www.trolltech.com/gpl/ for GPL licensing information.

**

** Contact info@trolltech.com if any conditions of this licensing are

** not clear to you.

**

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

#include "qgdict.h"

#include "qlist.h"

#include "qstring.h"

#include "qdatastream.h"

#include <ctype.h>

// NOT REVISED

/*!

  \class QGDict qgdict.h

  \brief The QGDict class is an internal class for implementing QDict template classes.

  QGDict is a strictly internal class that acts as a base class for the

  \link collection.html collection classes\endlink QDict and QIntDict.

  QGDict has some virtual functions that can be reimplemented to customize

  the subclasses.

  <ul>

  <li> read() reads a collection/dictionary item from a QDataStream.

  <li> write() writes a collection/dictionary item to a QDataStream.

  </ul>

  Normally, you do not have to reimplement any of these functions.

*/

static const int op_find    = 0;

static const int op_insert  = 1;

static const int op_replace = 2;

class QGDItList : public QList<QGDictIterator>

{

public:

    QGDItList() : QList<QGDictIterator>() {}

    QGDItList( const QGDItList &list ) : QList<QGDictIterator>(list) {}

   ~QGDItList() { clear(); }

    QGDItList &operator=(const QGDItList &list)

	{ return (QGDItList&)QList<QGDictIterator>::operator=(list); }

};

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

  Default implementation of special and virtual functions

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

/*!

  \internal

  Returns the hash key for \e key, when key is a string.

*/

int QGDict::hashKeyString( const QString &key )

{

#if defined(CHECK_NULL)

    if ( key.isNull() ) 

	qWarning( "QGDict::hashStringKey: Invalid null key" ); 

#endif

    int i;

    register uint h=0;

    uint g;

    int len = key.length();

    const QChar *p = key.unicode();

    if ( cases ) {				// case sensitive

	for ( i=0; i<len; i++ ) {

	    h = (h<<4) + p[i].cell();

	    if ( (g = h & 0xf0000000) )

		h ^= g >> 24;

	    h &= ~g;

	}

    } else {					// case insensitive

	for ( i=0; i<len; i++ ) {

	    h = (h<<4) + p[i].lower().cell();

	    if ( (g = h & 0xf0000000) )

		h ^= g >> 24;

	    h &= ~g;

	}

    }

    int index = h;

    if ( index < 0 )				// adjust index to table size

	index = -index;

    return index;

}

/*!

  \internal

  Returns the hash key for \a key, which is a C string.

*/

int QGDict::hashKeyAscii( const char *key )

{

#if defined(CHECK_NULL)

    if ( key == 0 )

    {

	qWarning( "QGDict::hashAsciiKey: Invalid null key" );

        return 0;

    }

#endif

    register const char *k = key;

    register uint h=0;

    uint g;

    if ( cases ) {				// case sensitive

	while ( *k ) {

	    h = (h<<4) + *k++;

	    if ( (g = h & 0xf0000000) )

		h ^= g >> 24;

	    h &= ~g;

	}

    } else {					// case insensitive

	while ( *k ) {

	    h = (h<<4) + tolower(*k);

	    if ( (g = h & 0xf0000000) )

		h ^= g >> 24;

	    h &= ~g;

	    k++;

	}

    }

    int index = h;

    if ( index < 0 )				// adjust index to table size

	index = -index;

    return index;

}

#ifndef QT_NO_DATASTREAM

/*!

  Reads a collection/dictionary item from the stream \e s and returns a

  reference to the stream.

  The default implementation sets \e item to 0.

  \sa write()

*/

QDataStream& QGDict::read( QDataStream &s, QCollection::Item &item )

{

    item = 0;

    return s;

}

/*!

  Writes a collection/dictionary item to the stream \e s and returns a

  reference to the stream.

  \sa read()

*/

QDataStream& QGDict::write( QDataStream &s, QCollection::Item ) const

{

    return s;

}

#endif //QT_NO_DATASTREAM

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

  QGDict member functions

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

/*!

  \internal

  Constructs a dictionary.

*/

QGDict::QGDict( uint len, KeyType kt, bool caseSensitive, bool copyKeys )

{

    init( len, kt, caseSensitive, copyKeys );

}

void QGDict::init( uint len, KeyType kt, bool caseSensitive, bool copyKeys )

{

    vec = new QBaseBucket *[vlen = len];		// allocate hash table

    CHECK_PTR( vec );

    memset( (char*)vec, 0, vlen*sizeof(QBaseBucket*) );

    numItems  = 0;

    iterators = 0;

    // The caseSensitive and copyKey options don't make sense for

    // all dict types.

    switch ( (keytype = (uint)kt) ) {

	case StringKey:

	    cases = caseSensitive;

	    copyk = FALSE;

	    break;

	case AsciiKey:

	    cases = caseSensitive;

	    copyk = copyKeys;

	    break;

	default:

	    cases = FALSE;

	    copyk = FALSE;

	    break;

    }

}

/*!

  \internal

  Constructs a copy of \e dict.

*/

QGDict::QGDict( const QGDict & dict )

    : QCollection( dict )

{

    init( dict.vlen, (KeyType)dict.keytype, dict.cases, dict.copyk );

    QGDictIterator it( dict );

    while ( it.get() ) {			// copy from other dict

	switch ( keytype ) {

	    case StringKey:

		look_string( it.getKeyString(), it.get(), op_insert );

		break;

	    case AsciiKey:

		look_ascii( it.getKeyAscii(), it.get(), op_insert );

		break;

	    case IntKey:

		look_int( it.getKeyInt(), it.get(), op_insert );

		break;

	    case PtrKey:

		look_ptr( it.getKeyPtr(), it.get(), op_insert );

		break;

	}

	++it;

    }

}

/*!

  \internal

  Removes all items from the dictionary and destroys it.

*/

QGDict::~QGDict()

{

    clear();					// delete everything

    delete [] vec;

    if ( !iterators )				// no iterators for this dict

	return;

    QGDictIterator *i = iterators->first();

    while ( i ) {				// notify all iterators that

	i->dict = 0;				// this dict is deleted

	i = iterators->next();

    }

    delete iterators;

}

/*!

  \internal

  Assigns \e dict to this dictionary.

*/

QGDict &QGDict::operator=( const QGDict &dict )

{

    clear();

    QGDictIterator it( dict );

    while ( it.get() ) {			// copy from other dict

	switch ( keytype ) {

	    case StringKey:

		look_string( it.getKeyString(), it.get(), op_insert );

		break;

	    case AsciiKey:

		look_ascii( it.getKeyAscii(), it.get(), op_insert );

		break;

	    case IntKey:

		look_int( it.getKeyInt(), it.get(), op_insert );

		break;

	    case PtrKey:

		look_ptr( it.getKeyPtr(), it.get(), op_insert );

		break;

	}

	++it;

    }

    return *this;

}

/*! \fn QCollection::Item QGDictIterator::get() const

  \internal

*/

/*! \fn QString QGDictIterator::getKeyString() const

  \internal

*/

/*! \fn const char * QGDictIterator::getKeyAscii() const

  \internal

*/

/*! \fn void * QGDictIterator::getKeyPtr() const

  \internal

*/

/*! \fn long QGDictIterator::getKeyInt() const

  \internal

*/

/*!

  \fn uint QGDict::count() const

  \internal

  Returns the number of items in the dictionary.

*/

/*!

  \fn uint QGDict::size() const

  \internal

  Returns the size of the hash array.

*/

/*!

  \internal

  The do-it-all function; op is one of op_find, op_insert, op_replace

*/

QCollection::Item QGDict::look_string( const QString &key, QCollection::Item d, int op )

{

    QStringBucket *n;

    int	index = hashKeyString(key) % vlen;

    if ( op == op_find ) {			// find

	if ( cases ) {

	    for ( n=(QStringBucket*)vec[index]; n;

		  n=(QStringBucket*)n->getNext() ) {

		if ( key == n->getKey() )

		    return n->getData();	// item found

	    }

	} else {

	    QString k = key.lower();

	    for ( n=(QStringBucket*)vec[index]; n;

		  n=(QStringBucket*)n->getNext() ) {

		if ( k == n->getKey().lower() )

		    return n->getData();	// item found

	    }

	}

	return 0;				// not found

    }

    if ( op == op_replace ) {			// replace

	if ( vec[index] != 0 )			// maybe something there

	    remove_string( key );

    }

    // op_insert or op_replace

    n = new QStringBucket(key,newItem(d),vec[index]);

    CHECK_PTR( n );

#if defined(CHECK_NULL)

    if ( n->getData() == 0 )

	qWarning( "QDict: Cannot insert null item" );

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

/*!  \internal */

QCollection::Item QGDict::look_ascii( const char *key, QCollection::Item d, int op )

{

    QAsciiBucket *n;

    int	index = hashKeyAscii(key) % vlen;

    if ( op == op_find ) {			// find

	if ( cases ) {

	    for ( n=(QAsciiBucket*)vec[index]; n;

		  n=(QAsciiBucket*)n->getNext() ) {

		if ( qstrcmp(n->getKey(),key) == 0 )

		    return n->getData();	// item found

	    }

	} else {

	    for ( n=(QAsciiBucket*)vec[index]; n;

		  n=(QAsciiBucket*)n->getNext() ) {

		if ( qstricmp(n->getKey(),key) == 0 )

		    return n->getData();	// item found

	    }

	}

	return 0;				// not found

    }

    if ( op == op_replace ) {			// replace

	if ( vec[index] != 0 )			// maybe something there

	    remove_ascii( key );

    }

    // op_insert or op_replace

    n = new QAsciiBucket(copyk ? qstrdup(key) : key,newItem(d),vec[index]);

    CHECK_PTR( n );

#if defined(CHECK_NULL)

    if ( n->getData() == 0 )

	qWarning( "QAsciiDict: Cannot insert null item" );

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

/*!  \internal */

QCollection::Item QGDict::look_int( long key, QCollection::Item d, int op )

{

    QIntBucket *n;

    int index = (int)((ulong)key % vlen);	// simple hash

    if ( op == op_find ) {			// find

	for ( n=(QIntBucket*)vec[index]; n;

	      n=(QIntBucket*)n->getNext() ) {

	    if ( n->getKey() == key )

		return n->getData();		// item found

	}

	return 0;				// not found

    }

    if ( op == op_replace ) {			// replace

	if ( vec[index] != 0 )			// maybe something there

	    remove_int( key );

    }

    // op_insert or op_replace

    n = new QIntBucket(key,newItem(d),vec[index]);

    CHECK_PTR( n );

#if defined(CHECK_NULL)

    if ( n->getData() == 0 )

	qWarning( "QIntDict: Cannot insert null item" );

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

/*!  \internal */

QCollection::Item QGDict::look_ptr( void *key, QCollection::Item d, int op )

{

    QPtrBucket *n;

    int index = (int)((ulong)key % vlen);	// simple hash

    if ( op == op_find ) {			// find

	for ( n=(QPtrBucket*)vec[index]; n;

	      n=(QPtrBucket*)n->getNext() ) {

	    if ( n->getKey() == key )

		return n->getData();		// item found

	}

	return 0;				// not found

    }

    if ( op == op_replace ) {			// replace

	if ( vec[index] != 0 )			// maybe something there

	    remove_ptr( key );

    }

    // op_insert or op_replace

    n = new QPtrBucket(key,newItem(d),vec[index]);

    CHECK_PTR( n );

#if defined(CHECK_NULL)

    if ( n->getData() == 0 )

	qWarning( "QPtrDict: Cannot insert null item" );

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

/*!

  \internal

  Changes the size of the hashtable.

  The contents of the dictionary are preserved,

  but all iterators on the dictionary become invalid.

*/

void QGDict::resize( uint newsize )

{

    // Save old information

    QBaseBucket **old_vec = vec;

    uint old_vlen  = vlen;

    bool old_copyk = copyk;

    vec = new QBaseBucket *[vlen = newsize];

    CHECK_PTR( vec );

    memset( (char*)vec, 0, vlen*sizeof(QBaseBucket*) );

    numItems = 0;

    copyk = FALSE;

    // Reinsert every item from vec, deleting vec as we go

    for ( uint index = 0; index < old_vlen; index++ ) {

	switch ( keytype ) {

	    case StringKey:

		{

		    QStringBucket *n=(QStringBucket *)old_vec[index];

		    while ( n ) {

			look_string( n->getKey(), n->getData(), op_insert );

			QStringBucket *t=(QStringBucket *)n->getNext();

			delete n;

			n = t;

		    }

		}

		break;

	    case AsciiKey: