qglist.cpp

Trolltech公司发布的图形界面操作系统。可在qt-embedded-2.3.10平台上编译为嵌入式图形界面操作系统。

/**********************************************************************
** Copyright (C) 2000-2005 Trolltech AS.  All rights reserved.
**
** This file is part of the Qtopia Environment.
** 
** This program is free software; you can redistribute it and/or modify it
** under the terms of the GNU General Public License as published by the
** Free Software Foundation; either version 2 of the License, or (at your
** option) any later version.
** 
** A copy of the GNU GPL license version 2 is included in this package as 
** LICENSE.GPL.
**
** This program is distributed in the hope that it will be useful, but
** WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
** See the GNU General Public License for more details.
**
** In addition, as a special exception Trolltech gives permission to link
** the code of this program with Qtopia applications copyrighted, developed
** and distributed by Trolltech under the terms of the Qtopia Personal Use
** License Agreement. You must comply with the GNU General Public License
** in all respects for all of the code used other than the applications
** licensed under the Qtopia Personal Use License Agreement. If you modify
** this file, you may extend this exception to your version of the file,
** but you are not obligated to do so. If you do not wish to do so, delete
** this exception statement from your version.
** 
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact [e-mail] if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/

#include "qglist.h"
#include "qgvector.h"
#include "qdatastream.h"
#include "qvaluelist.h"

/*!
  \class QLNode qglist.h
  \reentrant
  \ingroup collection
  \brief The QLNode class is an internal class for the QPtrList template collection.

  \internal

  QLNode 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 QPtrList, 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 QPtrList::currentNode(), QPtrList::removeNode(), QPtrList::takeNode()
*/

/*!
  \fn QPtrCollection::Item QLNode::getData()
  Returns a pointer (\c void*) to the actual data in the list node.
*/


/*!
  \class QGList qglist.h
  \reentrant
  \ingroup collection
  \brief The QGList class is an internal class for implementing Qt collection classes.

  \internal

  QGList is a strictly internal class that acts as a base class for
  several collection classes; QPtrList, QPtrQueue and QPtrStack.

  QGList 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 QGList. Contains some optimization for
   the typically case where only one iterators is activre on the list.
 */
class QGListIteratorList
{
public:
    QGListIteratorList()
	: list(0), iterator(0) {
    }
    ~QGListIteratorList() {
	notifyClear( TRUE );
	delete list;
    }

    void add( QGListIterator* i ) {
	if ( !iterator ) {
	    iterator = i;
	} else if ( list ) {
	    list->push_front( i );
	} else {
	    list = new QValueList<QGListIterator*>;
	    list->push_front( i );
	}
    }

    void remove( QGListIterator* 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 ( QValueList<QGListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) {
		if ( zeroList )
		    (*i)->list = 0;
		(*i)->curNode = 0;
	    }
	}
    }

    void notifyRemove( QLNode* n, QLNode* curNode ) {
	if ( iterator ) {
	    if ( iterator->curNode == n )
		iterator->curNode = curNode;
	}
	if ( list ) {
	    for ( QValueList<QGListIterator*>::Iterator i = list->begin(); i != list->end(); ++i ) {
		if ( (*i)->curNode == n )
		    (*i)->curNode = curNode;
	    }
	}
    }

private:
    QValueList<QGListIterator*>* list;
    QGListIterator* iterator;
};



/*****************************************************************************
  Default implementation of virtual functions
 *****************************************************************************/

/*!
  Documented as QPtrList::compareItems().

  Compares \a item1 with \a item2.
*/
int QGList::compareItems( QPtrCollection::Item item1, QPtrCollection::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 &QGList::read( QDataStream &s, QPtrCollection::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 &QGList::write( QDataStream &s, QPtrCollection::Item ) const
{
    return s;
}
#endif // QT_NO_DATASTREAM

/*****************************************************************************
  QGList member functions
 *****************************************************************************/

/*!
  Constructs an empty list.
*/

QGList::QGList()
{
    firstNode = lastNode = curNode = 0;		// initialize list
    numNodes  = 0;
    curIndex  = -1;
    iterators = 0;				// initialize iterator list
}

/*!
  Constructs a copy of \a list.
*/

QGList::QGList( const QGList & list )
    : QPtrCollection( list )
{
    firstNode = lastNode = curNode = 0;		// initialize list
    numNodes  = 0;
    curIndex  = -1;
    iterators = 0;				// initialize iterator list
    QLNode *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.
*/

QGList::~QGList()
{
    clear();
    delete iterators;
    // Workaround for GCC 2.7.* bug. Compiler constructs 'static' QGList
    // 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.
*/

QGList& QGList::operator=( const QGList &list )
{
    if ( &list == this )
	return *this;

    clear();
    if ( list.count() > 0 ) {
	QLNode *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 QGList::operator==( const QGList &list ) const
{
    if ( count() != list.count() )
	return FALSE;

    if ( count() == 0 )
	return TRUE;

    QLNode *n1 = firstNode;
    QLNode *n2 = list.firstNode;
    while ( n1 && n2 ) {
	// should be mutable
	if ( ( (QGList*)this )->compareItems( n1->data, n2->data ) != 0 )
	    return FALSE;
	n1 = n1->next;
	n2 = n2->next;
    }

    return TRUE;
}

/*!
  \fn uint QGList::count() const

  Returns the number of items in the list.
*/


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

QLNode *QGList::locate( uint index )
{
    if ( index == (uint)curIndex )		// current node ?
	return curNode;
    if ( !curNode && firstNode ) {		// set current node
	curNode	 = firstNode;
	curIndex = 0;
    }
    register QLNode *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 QGList::inSort( QPtrCollection::Item d )
{
    int index = 0;
    register QLNode *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 QGList::prepend( QPtrCollection::Item d )
{
    register QLNode *n = new QLNode( 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 QGList::append( QPtrCollection::Item d )
{
    register QLNode *n = new QLNode( 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 QGList::insertAt( uint index, QPtrCollection::Item d )
{
    if ( index == 0 ) {
	prepend( d );
	return TRUE;
    } else if ( index == numNodes ) {
	append( d );
	return TRUE;
    }
    QLNode *nextNode = locate( index );
    if ( !nextNode )
	return FALSE;
    QLNode *prevNode = nextNode->prev;
    register QLNode *n = new QLNode( 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 QGList::relinkNode( QLNode *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.
*/

QLNode *QGList::unlink()
{
    if ( curNode == 0 )				// null current node
	return 0;
    register QLNode *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 QGList::removeNode( QLNode *n )
{
#if defined(QT_CHECK_NULL)
    if ( n == 0 || (n->prev && n->prev->next != n) ||
	 (n->next && n->next->prev != n) ) {
	qWarning( "QGList::removeNode: Corrupted node" );
	return FALSE;
    }
#endif
    curNode = n;
    unlink();					// unlink node
    deleteItem( n->data );			// deallocate this node
    delete n;
    curNode  = firstNode;
    curIndex = curNode ? 0 : -1;
    return TRUE;
}

/*!
  Removes the item \a d from the list.	Uses compareItems() to find the item.

  If \a d is 0, removes the current item.
*/

bool QGList::remove( QPtrCollection::Item d )
{
    if ( d && find(d) == -1 )
	return FALSE;
    QLNode *n = unlink();
    if ( !n )
	return FALSE;
    deleteItem( n->data );
    delete n;
    return TRUE;
}

/*!
  Removes the item \a d from the list.
*/

bool QGList::removeRef( QPtrCollection::Item d )
{
    if ( findRef(d) == -1 )
	return FALSE;
    QLNode *n = unlink();
    if ( !n )
	return FALSE;
    deleteItem( n->data );
    delete n;
    return TRUE;
}

/*!
  \fn bool QGList::removeFirst()

  Removes the first item in the list.
*/

/*!
  \fn bool QGList::removeLast()

  Removes the last item in the list.
*/

/*!
  Removes the item at position \a index from the list.
*/

bool QGList::removeAt( uint index )
{
    if ( !locate(index) )
	return FALSE;
    QLNode *n = unlink();
    if ( !n )
	return FALSE;
    deleteItem( n->data );
    delete n;
    return TRUE;
}


/*!
  Replaces the item at index \a index with \a d.
*/
bool QGList::replaceAt( uint index, QPtrCollection::Item d )
{
    QLNode *n = locate( index );
    if ( !n )
	return FALSE;
    if ( n->data != d ) {
	deleteItem( n->data );
	n->data = newItem( d );
    }
    return TRUE;
}



/*!
  Takes the node \a n out of the list.
*/

QPtrCollection::Item QGList::takeNode( QLNode *n )
{
#if defined(QT_CHECK_NULL)
    if ( n == 0 || (n->prev && n->prev->next != n) ||
	 (n->next && n->next->prev != n) ) {
	qWarning( "QGList::takeNode: Corrupted node" );
	return 0;
    }
#endif
    curNode = n;
    unlink();					// unlink node
    Item d = n->data;
    delete n;					// delete the node, not data
    curNode  = firstNode;
    curIndex = curNode ? 0 : -1;
    return d;
}

/*!
  Takes the current item out of the list.
*/