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

**

** 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 QtGui 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$

**

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

#ifndef QFRAGMENTMAP_P_H

#define QFRAGMENTMAP_P_H

//

//  W A R N I N G

//  -------------

//

// This file is not part of the Qt API.  It exists purely as an

// implementation detail.  This header file may change from version to

// version without notice, or even be removed.

//

// We mean it.

//

#include "QtCore/qglobal.h"

#include <stdlib.h>

#include <private/qtools_p.h>

QT_BEGIN_NAMESPACE

template <int N = 1>

class QFragment

{

public:

    quint32 parent;

    quint32 left;

    quint32 right;

    quint32 color;

    quint32 size_left_array[N];

    quint32 size_array[N];

    enum {size_array_max = N };

};

template <class Fragment>

class QFragmentMapData

{

    enum Color { Red, Black };

public:

    QFragmentMapData();

    ~QFragmentMapData();

    void init();

    class Header

    {

    public:

        quint32 root; // this relies on being at the same position as parent in the fragment struct

        quint32 tag;

        quint32 freelist;

        quint32 node_count;

        quint32 allocated;

    };

    enum {fragmentSize = sizeof(Fragment) };

    int length(uint field = 0) const;

    inline Fragment *fragment(uint index) {

        return (fragments + index);

    }

    inline const Fragment *fragment(uint index) const {

        return (fragments + index);

    }

    inline Fragment &F(uint index) { return fragments[index] ; }

    inline const Fragment &F(uint index) const { return fragments[index] ; }

    inline bool isRoot(uint index) const {

        return !fragment(index)->parent;

    }

    inline uint position(uint node, uint field = 0) const {

        Q_ASSERT(field < Fragment::size_array_max);

        const Fragment *f = fragment(node);

        uint offset = f->size_left_array[field];

        while (f->parent) {

            uint p = f->parent;

            f = fragment(p);

            if (f->right == node)

                offset += f->size_left_array[field] + f->size_array[field];

            node = p;

        }

        return offset;

    }

    inline uint sizeRight(uint node, uint field = 0) const {

        Q_ASSERT(field < Fragment::size_array_max);

        uint sr = 0;

        const Fragment *f = fragment(node);

        node = f->right;

        while (node) {

            f = fragment(node);

            sr += f->size_left_array[field] + f->size_array[field];

            node = f->right;

        }

        return sr;

    }

    inline uint sizeLeft(uint node, uint field = 0) const {

        Q_ASSERT(field < Fragment::size_array_max);

        return fragment(node)->size_left_array[field];

    }

    inline uint size(uint node, uint field = 0) const {

        Q_ASSERT(field < Fragment::size_array_max);

        return fragment(node)->size_array[field];

    }

    inline void setSize(uint node, int new_size, uint field = 0) {

        Q_ASSERT(field < Fragment::size_array_max);

        Fragment *f = fragment(node);

        int diff = new_size - f->size_array[field];

        f->size_array[field] = new_size;

        while (f->parent) {

            uint p = f->parent;

            f = fragment(p);

            if (f->left == node)

                f->size_left_array[field] += diff;

            node = p;

        }

    }

    uint findNode(int k, uint field = 0) const;

    uint insert_single(int key, uint length);

    uint erase_single(uint f);

    uint minimum(uint n) const {

        while (n && fragment(n)->left)

            n = fragment(n)->left;

        return n;

    }

    uint maximum(uint n) const {

        while (n && fragment(n)->right)

            n = fragment(n)->right;

        return n;

    }

    uint next(uint n) const;

    uint previous(uint n) const;

    inline uint root() const {

        Q_ASSERT(!head->root || !fragment(head->root)->parent);

        return head->root;

    }

    inline void setRoot(uint new_root) {

        Q_ASSERT(!head->root || !fragment(new_root)->parent);

        head->root = new_root;

    }

    union {

        Header *head;

        Fragment *fragments;

    };

private:

    void rotateLeft(uint x);

    void rotateRight(uint x);

    void rebalance(uint x);

    void removeAndRebalance(uint z);

    uint createFragment();

    void freeFragment(uint f);

};

template <class Fragment>

QFragmentMapData<Fragment>::QFragmentMapData()

    : fragments(0)

{

    init();

}

template <class Fragment>

void QFragmentMapData<Fragment>::init()

{

    // the following code will realloc an existing fragment or create a new one.

    // it will also ignore errors when shrinking an existing fragment.

    Fragment *newFragments = (Fragment *)realloc(fragments, 64*fragmentSize);

    if (newFragments) {

        fragments = newFragments;

        head->allocated = 64;

    }

    Q_CHECK_PTR(fragments);

    head->tag = (((quint32)'p') << 24) | (((quint32)'m') << 16) | (((quint32)'a') << 8) | 'p'; //TAG('p', 'm', 'a', 'p');

    head->root = 0;

    head->freelist = 1;

    head->node_count = 0;

    // mark all items to the right as unused

    F(head->freelist).right = 0;

}

template <class Fragment>

QFragmentMapData<Fragment>::~QFragmentMapData()

{

    free(fragments);

}

template <class Fragment>

uint QFragmentMapData<Fragment>::createFragment()

{

    Q_ASSERT(head->freelist <= head->allocated);

    uint freePos = head->freelist;

    if (freePos == head->allocated) {

        // need to create some free space

        uint needed = qAllocMore((freePos+1)*fragmentSize, 0);

        Q_ASSERT(needed/fragmentSize > head->allocated);

        Fragment *newFragments = (Fragment *)realloc(fragments, needed);

        Q_CHECK_PTR(newFragments);

        fragments = newFragments;

        head->allocated = needed/fragmentSize;

        F(freePos).right = 0;

    }

    uint nextPos = F(freePos).right;

    if (!nextPos) {

        nextPos = freePos+1;

        if (nextPos < head->allocated)

            F(nextPos).right = 0;

    }

    head->freelist = nextPos;

    ++head->node_count;

    return freePos;

}

template <class Fragment>

void QFragmentMapData<Fragment>::freeFragment(uint i)

{

    F(i).right = head->freelist;

    head->freelist = i;

    --head->node_count;

}

template <class Fragment>

uint QFragmentMapData<Fragment>::next(uint n) const {

    Q_ASSERT(n);

    if (F(n).right) {

        n = F(n).right;

        while (F(n).left)

            n = F(n).left;

    } else {

        uint y = F(n).parent;

        while (F(n).parent && n == F(y).right) {

            n = y;

            y = F(y).parent;

        }

        n = y;

    }

    return n;

}

template <class Fragment>

uint QFragmentMapData<Fragment>::previous(uint n) const {

    if (!n)

        return maximum(root());

    if (F(n).left) {

        n = F(n).left;

        while (F(n).right)

            n = F(n).right;

    } else {

        uint y = F(n).parent;

        while (F(n).parent && n == F(y).left) {

            n = y;

            y = F(y).parent;

        }

        n = y;

    }

    return n;

}

/*

     x              y

      \            / \

       y    -->   x   b

      / \          \

     a   b          a

*/

template <class Fragment>

void QFragmentMapData<Fragment>::rotateLeft(uint x)

{

    uint p = F(x).parent;

    uint y = F(x).right;

    if (y) {

        F(x).right = F(y).left;

        if (F(y).left)

            F(F(y).left).parent = x;

        F(y).left = x;

        F(y).parent = p;

    } else {

        F(x).right = 0;

    }

    if (!p) {

        Q_ASSERT(head->root == x);

        head->root = y;

    }

    else if (x == F(p).left)

        F(p).left = y;

    else

        F(p).right = y;

    F(x).parent = y;

    for (uint field = 0; field < Fragment::size_array_max; ++field)

        F(y).size_left_array[field] += F(x).size_left_array[field] + F(x).size_array[field];

}

/*

         x          y

        /          / \

       y    -->   a   x

      / \            /

     a   b          b

*/

template <class Fragment>

void QFragmentMapData<Fragment>::rotateRight(uint x)

{

    uint y = F(x).left;

    uint p = F(x).parent;

    if (y) {

        F(x).left = F(y).right;

        if (F(y).right)

            F(F(y).right).parent = x;

        F(y).right = x;

        F(y).parent = p;

    } else {

        F(x).left = 0;

    }

    if (!p) {

        Q_ASSERT(head->root == x);

        head->root = y;

    }

    else if (x == F(p).right)

        F(p).right = y;

    else

        F(p).left = y;

    F(x).parent = y;

    for (uint field = 0; field < Fragment::size_array_max; ++field)

        F(x).size_left_array[field] -= F(y).size_left_array[field] + F(y).size_array[field];

}

template <class Fragment>

void QFragmentMapData<Fragment>::rebalance(uint x)

{

    F(x).color = Red;

    while (F(x).parent && F(F(x).parent).color == Red) {

        uint p = F(x).parent;

        uint pp = F(p).parent;

        Q_ASSERT(pp);

        if (p == F(pp).left) {

            uint y = F(pp).right;

            if (y && F(y).color == Red) {

                F(p).color = Black;

                F(y).color = Black;

                F(pp).color = Red;

                x = pp;

            } else {

                if (x == F(p).right) {

                    x = p;

                    rotateLeft(x);

                    p = F(x).parent;

                    pp = F(p).parent;

                }

                F(p).color = Black;

                if (pp) {

                    F(pp).color = Red;

                    rotateRight(pp);

                }

            }

        } else {

            uint y = F(pp).left;

            if (y && F(y).color == Red) {

                F(p).color = Black;

                F(y).color = Black;

                F(pp).color = Red;

                x = pp;

            } else {

                if (x == F(p).left) {

                    x = p;

                    rotateRight(x);

                    p = F(x).parent;

                    pp = F(p).parent;

                }

                F(p).color = Black;

                if (pp) {

                    F(pp).color = Red;

                    rotateLeft(pp);

                }

            }

        }

    }

    F(root()).color = Black;

}

template <class Fragment>

uint QFragmentMapData<Fragment>::erase_single(uint z)

{

    uint w = previous(z);

    uint y = z;

    uint x;

    uint p;

    if (!F(y).left) {

        x = F(y).right;

    } else if (!F(y).right) {

        x = F(y).left;

    } else {

        y = F(y).right;

        while (F(y).left)

            y = F(y).left;

        x = F(y).right;

    }

    if (y != z) {

        F(F(z).left).parent = y;

        F(y).left = F(z).left;

        for (uint field = 0; field < Fragment::size_array_max; ++field)

            F(y).size_left_array[field] = F(z).size_left_array[field];

        if (y != F(z).right) {

            /*

                     z                y

                    / \              / \

                   a   b            a   b

                      /                /

                    ...     -->      ...

                    /                /

                   y                x

                  / \

                 0   x

             */

            p = F(y).parent;

            if (x)

                F(x).parent = p;

            F(p).left = x;

            F(y).right = F(z).right;

            F(F(z).right).parent = y;

            uint n = p;

            while (n != y) {

                for (uint field = 0; field < Fragment::size_array_max; ++field)

                    F(n).size_left_array[field] -= F(y).size_array[field];

                n = F(n).parent;

            }

        } else {

            /*

                     z                y

                    / \              / \

                   a   y     -->    a   x

                      / \

                     0   x

             */

            p = y;

        }

        uint zp = F(z).parent;

        if (!zp) {

            Q_ASSERT(head->root == z);

            head->root = y;

        } else if (F(zp).left == z) {

            F(zp).left = y;

            for (uint field = 0; field < Fragment::size_array_max; ++field)

                F(zp).size_left_array[field] -= F(z).size_array[field];

        } else {

            F(zp).right = y;

        }

        F(y).parent = zp;

        // Swap the colors

        uint c = F(y).color;

        F(y).color = F(z).color;