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

**

** 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 "q3glist.h"

#include "q3gvector.h"

#include "qdatastream.h"

#include "q3valuelist.h"

QT_BEGIN_NAMESPACE

/*!

  \class Q3LNode

  \reentrant

  \brief The Q3LNode class is an internal class for the Q3PtrList template collection.

  \internal

  Q3LNode is a doubly-linked list node. It has three pointers:

  \list 1

  \i Pointer to the previous node.

  \i Pointer to the next node.

  \i Pointer to the actual data.

  \endlist

  It might sometimes be practical to have direct access to the list nodes

  in a Q3PtrList, but it is seldom required.

  Be very careful if you want to access the list nodes. The heap can

  easily get corrupted if you make a mistake.

  \sa Q3PtrList::currentNode(), Q3PtrList::removeNode(), Q3PtrList::takeNode()

*/

/*!

  \fn Q3PtrCollection::Item Q3LNode::getData()

  Returns a pointer (\c void*) to the actual data in the list node.

*/

/*!

  \class Q3GList

  \reentrant

  \brief The Q3GList class is an internal class for implementing Qt collection classes.

  \internal

  Q3GList is a strictly internal class that acts as a base class for

  several collection classes; Q3PtrList, Q3PtrQueue and Q3PtrStack.

  Q3GList has some virtual functions that can be reimplemented to

  customize the subclasses, namely compareItems(), read() and

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

  functions.  If you still want to reimplement them, see the QStrList

  class (qstrlist.h) for an example.

*/

/* Internal helper class for Q3GList. Contains some optimization for

   the typically case where only one iterators is activre on the list.

 */

class Q3GListIteratorList

{

public:

    Q3GListIteratorList()

	: list(0), iterator(0) {

    }

    ~Q3GListIteratorList() {

	notifyClear( true );

	delete list;

    }

    void add( Q3GListIterator* i ) {

	if ( !iterator ) {

	    iterator = i;

	} else if ( list ) {

	    list->push_front( i );

	} else {

	    list = new Q3ValueList<Q3GListIterator*>;

	    list->push_front( i );

	}

    }

    void remove( Q3GListIterator* i ) {

	if ( iterator == i ) {

	    iterator = 0;

	} else if ( list ) {

	    list->remove( i );

	    if ( list->isEmpty() ) {

		delete list;

		list = 0;

	    }

	}

    }

    void notifyClear( bool zeroList ) {

	if ( iterator ) {

	    if ( zeroList )

		iterator->list = 0;

	    iterator->curNode = 0;

	}

	if ( list ) {

	    for ( Q3ValueList<Q3GListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) {

		if ( zeroList )

		    (*i)->list = 0;

		(*i)->curNode = 0;

	    }

	}

    }

    void notifyRemove( Q3LNode* n, Q3LNode* curNode ) {

	if ( iterator ) {

	    if ( iterator->curNode == n )

		iterator->curNode = curNode;

	}

	if ( list ) {

	    for ( Q3ValueList<Q3GListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) {

		if ( (*i)->curNode == n )

		    (*i)->curNode = curNode;

	    }

	}

    }

private:

    Q3ValueList<Q3GListIterator*>* list;

    Q3GListIterator* iterator;

};

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

  Default implementation of virtual functions

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

/*!

  Documented as Q3PtrList::compareItems().

  Compares \a item1 with \a item2.

*/

int Q3GList::compareItems( Q3PtrCollection::Item item1, Q3PtrCollection::Item item2 )

{

    return item1 != item2;			// compare pointers

}

#ifndef QT_NO_DATASTREAM

/*!

    \overload

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

  to the stream.

  The default implementation sets \a item to 0.

  \sa write()

*/

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

{

    item = 0;

    return s;

}

/*!

    \overload

  Writes a collection/list item to the stream \a s and

  returns a reference to the stream.

  The default implementation does nothing.

  \sa read()

*/

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

{

    return s;

}

#endif // QT_NO_DATASTREAM

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

  Q3GList member functions

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

/*!

  Constructs an empty list.

*/

Q3GList::Q3GList()

{

    firstNode = lastNode = curNode = 0;		// initialize list

    numNodes  = 0;

    curIndex  = -1;

    iterators = 0;				// initialize iterator list

}

/*!

  Constructs a copy of \a list.

*/

Q3GList::Q3GList( const Q3GList & list )

    : Q3PtrCollection( list )

{

    firstNode = lastNode = curNode = 0;		// initialize list

    numNodes  = 0;

    curIndex  = -1;

    iterators = 0;				// initialize iterator list

    Q3LNode *n = list.firstNode;

    while ( n ) {				// copy all items from list

	append( n->data );

	n = n->next;

    }

}

/*!

  Removes all items from the list and destroys the list.

*/

Q3GList::~Q3GList()

{

    clear();

    delete iterators;

    // Workaround for GCC 2.7.* bug. Compiler constructs 'static' Q3GList

    // instances twice on the same address and therefore tries to destruct

    // twice on the same address! This is insane but let's try not to crash

    // here.

    iterators = 0;

}

/*!

  Assigns \a list to this list.

*/

Q3GList& Q3GList::operator=( const Q3GList &list )

{

    if ( &list == this )

	return *this;

    clear();

    if ( list.count() > 0 ) {

	Q3LNode *n = list.firstNode;

	while ( n ) {				// copy all items from list

	    append( n->data );

	    n = n->next;

	}

	curNode	 = firstNode;

	curIndex = 0;

    }

    return *this;

}

/*!

  Compares this list with \a list. Returns true if the lists

  contain the same data, otherwise false.

*/

bool Q3GList::operator==( const Q3GList &list ) const

{

    if ( count() != list.count() )

	return false;

    if ( count() == 0 )

	return true;

    Q3LNode *n1 = firstNode;

    Q3LNode *n2 = list.firstNode;

    while ( n1 && n2 ) {

	// should be mutable

	if ( ( (Q3GList*)this )->compareItems( n1->data, n2->data ) != 0 )

	    return false;

	n1 = n1->next;

	n2 = n2->next;

    }

    return true;

}

/*!

  \fn uint Q3GList::count() const

  Returns the number of items in the list.

*/

/*!

  Returns the node at position \a index.  Sets this node to current.

*/

Q3LNode *Q3GList::locate( uint index )

{

    if ( index == (uint)curIndex )		// current node ?

	return curNode;

    if ( !curNode && firstNode ) {		// set current node

	curNode	 = firstNode;

	curIndex = 0;

    }

    register Q3LNode *node;

    int	 distance = index - curIndex;		// node distance to cur node

    bool forward;				// direction to traverse

    if ( index >= numNodes )

	return 0;

    if ( distance < 0 )

	distance = -distance;

    if ( (uint)distance < index && (uint)distance < numNodes - index ) {

	node =	curNode;			// start from current node

	forward = index > (uint)curIndex;

    } else if ( index < numNodes - index ) {	// start from first node

	node = firstNode;

	distance = index;

	forward = true;

    } else {					// start from last node

	node = lastNode;

	distance = numNodes - index - 1;

	if ( distance < 0 )

	    distance = 0;

	forward = false;

    }

    if ( forward ) {				// now run through nodes

	while ( distance-- )

	    node = node->next;

    } else {

	while ( distance-- )

	    node = node->prev;

    }

    curIndex = index;				// must update index

    return curNode = node;

}

/*!

  Inserts item \a d at its sorted position in the list.

*/

void Q3GList::inSort( Q3PtrCollection::Item d )

{

    int index = 0;

    register Q3LNode *n = firstNode;

    while ( n && compareItems(n->data,d) < 0 ){ // find position in list

	n = n->next;

	index++;

    }

    insertAt( index, d );

}

/*!

  Inserts item \a d at the start of the list.

*/

void Q3GList::prepend( Q3PtrCollection::Item d )

{

    register Q3LNode *n = new Q3LNode( newItem(d) );

    Q_CHECK_PTR( n );

    n->prev = 0;

    if ( (n->next = firstNode) )		// list is not empty

	firstNode->prev = n;

    else					// initialize list

	lastNode = n;

    firstNode = curNode = n;			// curNode affected

    numNodes++;

    curIndex = 0;

}

/*!

  Inserts item \a d at the end of the list.

*/

void Q3GList::append( Q3PtrCollection::Item d )

{

    register Q3LNode *n = new Q3LNode( newItem(d) );

    Q_CHECK_PTR( n );

    n->next = 0;

    if ( (n->prev = lastNode) )			// list is not empty

	lastNode->next = n;

    else					// initialize list

	firstNode = n;

    lastNode = curNode = n;			// curNode affected

    curIndex = numNodes;

    numNodes++;

}

/*!

  Inserts item \a d at position \a index in the list.

*/

bool Q3GList::insertAt( uint index, Q3PtrCollection::Item d )

{

    if ( index == 0 ) {

	prepend( d );

	return true;

    } else if ( index == numNodes ) {

	append( d );

	return true;

    }

    Q3LNode *nextNode = locate( index );

    if ( !nextNode )

	return false;

    Q3LNode *prevNode = nextNode->prev;

    register Q3LNode *n = new Q3LNode( newItem(d) );

    Q_CHECK_PTR( n );

    nextNode->prev = n;

    prevNode->next = n;

    n->prev = prevNode;				// link new node into list

    n->next = nextNode;

    curNode = n;				// curIndex set by locate()

    numNodes++;

    return true;

}

/*!

  Relinks node \a n and makes it the first node in the list.

*/

void Q3GList::relinkNode( Q3LNode *n )

{

    if ( n == firstNode )			// already first

	return;

    curNode = n;

    unlink();

    n->prev = 0;

    if ( (n->next = firstNode) )		// list is not empty

	firstNode->prev = n;

    else					// initialize list

	lastNode = n;

    firstNode = curNode = n;			// curNode affected

    numNodes++;

    curIndex = 0;

}

/*!

  Unlinks the current list node and returns a pointer to this node.

*/

Q3LNode *Q3GList::unlink()

{

    if ( curNode == 0 )				// null current node

	return 0;

    register Q3LNode *n = curNode;		// unlink this node

    if ( n == firstNode ) {			// removing first node ?

	if ( (firstNode = n->next) ) {

	    firstNode->prev = 0;

	} else {

	    lastNode = curNode = 0;		// list becomes empty

	    curIndex = -1;

	}

    } else {

	if ( n == lastNode ) {			// removing last node ?

	    lastNode = n->prev;

	    lastNode->next = 0;

	} else {				// neither last nor first node

	    n->prev->next = n->next;

	    n->next->prev = n->prev;

	}

    }

    if ( n->next ) {                            // change current node

        curNode = n->next;

    } else if ( n->prev ) {

        curNode = n->prev;

        curIndex--;

    }

    if ( iterators )

	iterators->notifyRemove( n, curNode );

    numNodes--;

    return n;

}

/*!

  Removes the node \a n from the list.

*/

bool Q3GList::removeNode( Q3LNode *n )

{

#if defined(QT_CHECK_NULL)

    if ( n == 0 || (n->prev && n->prev->next != n) ||

	 (n->next && n->next->prev != n) ) {

	qWarning( "Q3GList::removeNode: Corrupted node" );

	return false;

    }

#endif

    curNode = n;

    unlink();					// unlink node

    deleteItem( n->data );			// deallocate this node

    delete n;

    curNode  = firstNode;