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

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the Qt3Support module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

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

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

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

#include "q3gdict.h"

#include "q3ptrlist.h"

#include "qstring.h"

#include "qdatastream.h"

#include <ctype.h>

QT_BEGIN_NAMESPACE

/*!

  \class Q3GDict

  \reentrant

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

  \internal

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

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

  Q3GDict has some virtual functions that can be reimplemented to customize

  the subclasses.

  \list

  \i read() reads a collection/dictionary item from a QDataStream.

  \i write() writes a collection/dictionary item to a QDataStream.

  \endlist

  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 Q3GDItList : public Q3PtrList<Q3GDictIterator>

{

public:

    Q3GDItList() : Q3PtrList<Q3GDictIterator>() {}

    Q3GDItList(const Q3GDItList &list) : Q3PtrList<Q3GDictIterator>(list) {}

    ~Q3GDItList() { clear(); }

    Q3GDItList &operator=(const Q3GDItList &list)

        { return (Q3GDItList&)Q3PtrList<Q3GDictIterator>::operator=(list); }

};

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

  Default implementation of special and virtual functions

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

/*!

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

*/

int Q3GDict::hashKeyString(const QString &key)

{

#if defined(QT_CHECK_NULL)

    if (key.isNull())

        qWarning("Q3GDict::hashKeyString: Invalid null key");

#endif

    int i;

    register uint h=0;

    uint g;

    const QChar *p = key.unicode();

    if (cases) {                                // case sensitive

        for (i=0; i<(int)key.length(); i++) {

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

            if ((g = h & 0xf0000000))

                h ^= g >> 24;

            h &= ~g;

        }

    } else {                                    // case insensitive

        for (i=0; i<(int)key.length(); 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;

}

/*!

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

*/

int Q3GDict::hashKeyAscii(const char *key)

{

#if defined(QT_CHECK_NULL)

    if (key == 0)

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

#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((uchar) *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

/*!

    \overload

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

  reference to the stream.

  The default implementation sets \a item to 0.

  \sa write()

*/

QDataStream& Q3GDict::read(QDataStream &s, Q3PtrCollection::Item &item)

{

    item = 0;

    return s;

}

/*!

    \overload

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

  reference to the stream.

  \sa read()

*/

QDataStream& Q3GDict::write(QDataStream &s, Q3PtrCollection::Item) const

{

    return s;

}

#endif //QT_NO_DATASTREAM

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

  Q3GDict member functions

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

/*!

  Constructs a dictionary.

  \a len is the initial size of the dictionary.

  The key type is \a kt which may be \c StringKey, \c AsciiKey,

  \c IntKey or \c PtrKey. The case-sensitivity of lookups is set with

  \a caseSensitive. Keys are copied if \a copyKeys is true.

*/

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

{

    init(len, kt, caseSensitive, copyKeys);

}

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

{

    vlen = len ? len : 17;

    vec = new Q3BaseBucket *[ vlen ];

    Q_CHECK_PTR(vec);

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

    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;

    }

}

/*!

  Constructs a copy of \a dict.

*/

Q3GDict::Q3GDict(const Q3GDict & dict)

    : Q3PtrCollection(dict)

{

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

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

    }

}

/*!

  Removes all items from the dictionary and destroys it.

*/

Q3GDict::~Q3GDict()

{

    clear();                                    // delete everything

    delete [] vec;

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

        return;

    Q3GDictIterator *i = iterators->first();

    while (i) {                         // notify all iterators that

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

        i = iterators->next();

    }

    delete iterators;

}

/*!

  Assigns \a dict to this dictionary.

*/

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

{

    if (&dict == this)

        return *this;

    clear();

    Q3GDictIterator 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 uint Q3GDict::count() const

  Returns the number of items in the dictionary.

*/

/*!

  \fn uint Q3GDict::size() const

  Returns the size of the hash array.

*/

/*!

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

  The key is \a key and the item is \a d.

*/

Q3PtrCollection::Item Q3GDict::look_string(const QString &key, Q3PtrCollection::Item d,

                                       int op)

{

    Q3StringBucket *n = 0;

    int index = hashKeyString(key) % vlen;

    if (op == op_find) {                        // find

        if (cases) {

            n = (Q3StringBucket*)vec[index];

            while(n != 0) {

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

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

                n = (Q3StringBucket*)n->getNext();

            }

        } else {

            QString k = key.lower();

            n = (Q3StringBucket*)vec[index];

            while(n != 0) {

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

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

                n = (Q3StringBucket*)n->getNext();

            }

        }

        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 Q3StringBucket(key,newItem(d),vec[index]);

    Q_CHECK_PTR(n);

#if defined(QT_CHECK_NULL)

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

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

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

Q3PtrCollection::Item Q3GDict::look_ascii(const char *key, Q3PtrCollection::Item d, int op)

{

    Q3AsciiBucket *n;

    int index = hashKeyAscii(key) % vlen;

    if (op == op_find) {                        // find

        if (cases) {

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

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

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

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

            }

        } else {

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

                  n=(Q3AsciiBucket*)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 Q3AsciiBucket(copyk ? qstrdup(key) : key,newItem(d),vec[index]);

    Q_CHECK_PTR(n);

#if defined(QT_CHECK_NULL)

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

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

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

Q3PtrCollection::Item Q3GDict::look_int(long key, Q3PtrCollection::Item d, int op)

{

    Q3IntBucket *n;

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

    if (op == op_find) {                        // find

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

              n=(Q3IntBucket*)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 Q3IntBucket(key,newItem(d),vec[index]);

    Q_CHECK_PTR(n);

#if defined(QT_CHECK_NULL)

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

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

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

Q3PtrCollection::Item Q3GDict::look_ptr(void *key, Q3PtrCollection::Item d, int op)

{

    Q3PtrBucket *n;

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

    if (op == op_find) {                        // find

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

              n=(Q3PtrBucket*)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 Q3PtrBucket(key,newItem(d),vec[index]);

    Q_CHECK_PTR(n);

#if defined(QT_CHECK_NULL)

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

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

#endif

    vec[index] = n;

    numItems++;

    return n->getData();

}

/*!

  Changes the size of the hashtable to \a newsize.

  The contents of the dictionary are preserved,

  but all iterators on the dictionary become invalid.

*/

void Q3GDict::resize(uint newsize)

{

    // Save old information

    Q3BaseBucket **old_vec = vec;

    uint old_vlen  = vlen;

    bool old_copyk = copyk;

    vec = new Q3BaseBucket *[vlen = newsize];

    Q_CHECK_PTR(vec);

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

    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:

                {

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

                    while (n) {

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

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

                        delete n;

                        n = t;

                    }

                }

                break;

            case AsciiKey:

                {

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

                    while (n) {

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

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

                        delete n;

                        n = t;

                    }

                }

                break;

            case IntKey:

                {

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

                    while (n) {

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

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

                        delete n;

                        n = t;

                    }

                }

                break;

            case PtrKey:

                {

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

                    while (n) {

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

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

                        delete n;

                        n = t;

                    }