q3glist.cpp

奇趣公司比较新的qt/emd版本

Q3PtrCollection::Item Q3GList::take()
{
    Q3LNode *n = unlink();			// unlink node
    Item d = n ? n->data : 0;
    delete n;					// delete node, keep contents
    return d;
}

/*!
  Takes the item at position \a index out of the list.
*/

Q3PtrCollection::Item Q3GList::takeAt( uint index )
{
    if ( !locate(index) )
	return 0;
    Q3LNode *n = unlink();			// unlink node
    Item d = n ? n->data : 0;
    delete n;					// delete node, keep contents
    return d;
}

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

Q3PtrCollection::Item Q3GList::takeFirst()
{
    first();
    Q3LNode *n = unlink();			// unlink node
    Item d = n ? n->data : 0;
    delete n;
    return d;
}

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

Q3PtrCollection::Item Q3GList::takeLast()
{
    last();
    Q3LNode *n = unlink();			// unlink node
    Item d = n ? n->data : 0;
    delete n;
    return d;
}


/*!
  Removes all items from the list.
*/

void Q3GList::clear()
{
    register Q3LNode *n = firstNode;

    firstNode = lastNode = curNode = 0;		// initialize list
    numNodes = 0;
    curIndex = -1;

    if ( iterators )
	iterators->notifyClear( false );

    Q3LNode *prevNode;
    while ( n ) {				// for all nodes ...
	deleteItem( n->data );			// deallocate data
	prevNode = n;
	n = n->next;
	delete prevNode;			// deallocate node
    }
}


/*!
  Finds item \a d in the list. If \a fromStart is true the search
  begins at the first node; otherwise it begins at the current node.
*/

int Q3GList::findRef( Q3PtrCollection::Item d, bool fromStart )
{
    register Q3LNode *n;
    int	     index;
    if ( fromStart ) {				// start from first node
	n = firstNode;
	index = 0;
    } else {					// start from current node
	n = curNode;
	index = curIndex;
    }
    while ( n && n->data != d ) {		// find exact match
	n = n->next;
	index++;
    }
    curNode = n;
    curIndex = n ? index : -1;
    return curIndex;				// return position of item
}

/*!
  Finds item \a d in the list using compareItems(). If \a fromStart is
  true the search begins at the first node; otherwise it begins at the
  current node.
*/

int Q3GList::find( Q3PtrCollection::Item d, bool fromStart )
{
    register Q3LNode *n;
    int	     index;
    if ( fromStart ) {				// start from first node
	n = firstNode;
	index = 0;
    } else {					// start from current node
	n = curNode;
	index = curIndex;
    }
    while ( n && compareItems(n->data,d) ){	// find equal match
	n = n->next;
	index++;
    }
    curNode = n;
    curIndex = n ? index : -1;
    return curIndex;				// return position of item
}


/*!
  Counts the number item \a d occurs in the list.
*/

uint Q3GList::containsRef( Q3PtrCollection::Item d ) const
{
    register Q3LNode *n = firstNode;
    uint     count = 0;
    while ( n ) {				// for all nodes...
	if ( n->data == d )			// count # exact matches
	    count++;
	n = n->next;
    }
    return count;
}

/*!
  Counts the number of times item \a d occurs in the list. Uses
  compareItems().
*/

uint Q3GList::contains( Q3PtrCollection::Item d ) const
{
    register Q3LNode *n = firstNode;
    uint     count = 0;
    Q3GList  *that = (Q3GList*)this;		// mutable for compareItems()
    while ( n ) {				// for all nodes...
	if ( !that->compareItems(n->data,d) )	// count # equal matches
	    count++;
	n = n->next;
    }
    return count;
}


/*!
  \fn Q3PtrCollection::Item Q3GList::at( uint index )
  \overload

  Sets the item at position \a index to the current item.
*/

/*!
  \fn int Q3GList::at() const

  Returns the current index.
*/

/*!
  \fn Q3LNode *Q3GList::currentNode() const

  Returns the current node.
*/

/*!
  \fn Q3PtrCollection::Item Q3GList::get() const

  Returns the current item.
*/

/*!
  \fn Q3PtrCollection::Item Q3GList::cfirst() const

  Returns the first item in the list.
*/

/*!
  \fn Q3PtrCollection::Item Q3GList::clast() const

  Returns the last item in the list.
*/


/*!
  Returns the first list item.	Sets this to current.
*/

Q3PtrCollection::Item Q3GList::first()
{
    if ( firstNode ) {
	curIndex = 0;
	return (curNode=firstNode)->data;
    }
    return 0;
}

/*!
  Returns the last list item.  Sets this to current.
*/

Q3PtrCollection::Item Q3GList::last()
{
    if ( lastNode ) {
	curIndex = numNodes-1;
	return (curNode=lastNode)->data;
    }
    return 0;
}

/*!
  Returns the next list item (after current).  Sets this to current.
*/

Q3PtrCollection::Item Q3GList::next()
{
    if ( curNode ) {
	if ( curNode->next ) {
	    curIndex++;
	    curNode = curNode->next;
	    return curNode->data;
	}
	curIndex = -1;
	curNode = 0;
    }
    return 0;
}

/*!
  Returns the previous list item (before current).  Sets this to current.
*/

Q3PtrCollection::Item Q3GList::prev()
{
    if ( curNode ) {
	if ( curNode->prev ) {
	    curIndex--;
	    curNode = curNode->prev;
	    return curNode->data;
	}
	curIndex = -1;
	curNode = 0;
    }
    return 0;
}


/*!
  Converts the list to a vector, \a vector.
*/

void Q3GList::toVector( Q3GVector *vector ) const
{
    vector->clear();
    if ( !vector->resize( count() ) )
	return;
    register Q3LNode *n = firstNode;
    uint i = 0;
    while ( n ) {
	vector->insert( i, n->data );
	n = n->next;
	i++;
    }
}

void Q3GList::heapSortPushDown( Q3PtrCollection::Item* heap, int first, int last )
{
    int r = first;
    while( r <= last/2 ) {
	// Node r has only one child ?
	if ( last == 2*r ) {
	    // Need for swapping ?
	    if ( compareItems( heap[r], heap[ 2*r ] ) > 0 ) {
		Q3PtrCollection::Item tmp = heap[r];
		heap[ r ] = heap[ 2*r ];
		heap[ 2*r ] = tmp;
	    }
	    // That's it ...
	    r = last;
	} else {
	    // Node has two children
	    if ( compareItems( heap[r], heap[ 2*r ] ) > 0 &&
		 compareItems( heap[ 2*r ], heap[ 2*r+1 ] ) <= 0 ) {
		// Swap with left child
		Q3PtrCollection::Item tmp = heap[r];
		heap[ r ] = heap[ 2*r ];
		heap[ 2*r ] = tmp;
		r *= 2;
	    } else if ( compareItems( heap[r], heap[ 2*r+1 ] ) > 0 &&
			compareItems( heap[ 2*r+1 ], heap[ 2*r ] ) < 0 ) {
		// Swap with right child
		Q3PtrCollection::Item tmp = heap[r];
		heap[ r ] = heap[ 2*r+1 ];
		heap[ 2*r+1 ] = tmp;
		r = 2*r+1;
	    } else {
		// We are done
		r = last;
	    }
	}
    }
}


/*! Sorts the list by the result of the virtual compareItems() function.

  The Heap-Sort algorithm is used for sorting.  It sorts n items with
  O(n*log n) compares.  This is the asymptotic optimal solution of the
  sorting problem.
*/

void Q3GList::sort()
{
    uint n = count();
    if ( n < 2 )
	return;

    // Create the heap
    Q3PtrCollection::Item* realheap = new Q3PtrCollection::Item[ n ];
    // Wow, what a fake. But I want the heap to be indexed as 1...n
    Q3PtrCollection::Item* heap = realheap - 1;
    int size = 0;
    Q3LNode* insert = firstNode;
    for( ; insert != 0; insert = insert->next ) {
	heap[++size] = insert->data;
	int i = size;
	while( i > 1 && compareItems( heap[i], heap[ i / 2 ] ) < 0 ) {
	    Q3PtrCollection::Item tmp = heap[ i ];
	    heap[ i ] = heap[ i/2 ];
	    heap[ i/2 ] = tmp;
	    i /= 2;
	}
    }

    insert = firstNode;
    // Now do the sorting
    for ( int i = n; i > 0; i-- ) {
	insert->data = heap[1];
	insert = insert->next;
	if ( i > 1 ) {
	    heap[1] = heap[i];
	    heapSortPushDown( heap, 1, i - 1 );
	}
    }

    delete [] realheap;
}


/*****************************************************************************
  Q3GList stream functions
 *****************************************************************************/

#ifndef QT_NO_DATASTREAM
QDataStream &operator>>( QDataStream &s, Q3GList &list )
{						// read list
    return list.read( s );
}

QDataStream &operator<<( QDataStream &s, const Q3GList &list )
{						// write list
    return list.write( s );
}

/*!
  Reads a list from the stream \a s.
*/

QDataStream &Q3GList::read( QDataStream &s )
{
    uint num;
    s >> num;					// read number of items
    clear();					// clear list
    while ( num-- ) {				// read all items
	Item d;
	read( s, d );
	Q_CHECK_PTR( d );
	if ( !d )				// no memory
	    break;
	Q3LNode *n = new Q3LNode( d );
	Q_CHECK_PTR( n );
	if ( !n )				// no memory
	    break;
	n->next = 0;
	if ( (n->prev = lastNode) )		// list is not empty
	    lastNode->next = n;
	else					// initialize list
	    firstNode = n;
	lastNode = n;
	numNodes++;
    }
    curNode  = firstNode;
    curIndex = curNode ? 0 : -1;
    return s;
}

/*!
  Writes the list to the stream \a s.
*/

QDataStream &Q3GList::write( QDataStream &s ) const
{
    s << count();				// write number of items
    Q3LNode *n = firstNode;
    while ( n ) {				// write all items
	write( s, n->data );
	n = n->next;
    }
    return s;
}

#endif // QT_NO_DATASTREAM



/*! \internal
 */
Q3LNode* Q3GList::erase( Q3LNode* it )
{
    Q3LNode* n = it;
    it = it->next;
    removeNode( n );
    return it;
}


/*****************************************************************************
  Q3GListIterator member functions
 *****************************************************************************/

/*!
  \class Q3GListIterator qglist.h
  \reentrant
  \brief The Q3GListIterator class is an internal class for implementing Q3PtrListIterator.

  \internal

  Q3GListIterator is a strictly internal class that does the heavy work for
  Q3PtrListIterator.
*/

/*!
  \internal
  Constructs an iterator that operates on the list \a l.
*/

Q3GListIterator::Q3GListIterator( const Q3GList &l )
{
    list = (Q3GList *)&l;			// get reference to list
    curNode = list->firstNode;			// set to first node
    if ( !list->iterators ) {
	list->iterators = new Q3GListIteratorList;		// create iterator list
	Q_CHECK_PTR( list->iterators );
    }
    list->iterators->add( this );		// attach iterator to list
}

/*!
  \internal
  Constructs a copy of the iterator \a it.
*/

Q3GListIterator::Q3GListIterator( const Q3GListIterator &it )
{
    list = it.list;
    curNode = it.curNode;
    if ( list )
	list->iterators->add( this );	// attach iterator to list
}

/*!
  \internal
  Assigns a copy of the iterator \a it and returns a reference to this
  iterator.
*/

Q3GListIterator &Q3GListIterator::operator=( const Q3GListIterator &it )
{
    if ( list )					// detach from old list
	list->iterators->remove( this );
    list = it.list;
    curNode = it.curNode;
    if ( list )
	list->iterators->add( this );	// attach to new list
    return *this;
}

/*!
  \internal
  Destroys the iterator.
*/

Q3GListIterator::~Q3GListIterator()
{
    if ( list )					// detach iterator from list
	list->iterators->remove(this);
}


/*!
  \fn bool Q3GListIterator::atFirst() const
  \internal
  Returns true if the iterator points to the first item, otherwise false.
*/

/*!
  \fn bool Q3GListIterator::atLast() const
  \internal
  Returns true if the iterator points to the last item, otherwise false.
*/


/*!
  \internal
  Sets the list iterator to point to the first item in the list.
*/

Q3PtrCollection::Item Q3GListIterator::toFirst()
{
    if ( !list ) {
#if defined(QT_CHECK_NULL)
	qWarning( "Q3GListIterator::toFirst: List has been deleted" );
#endif
	return 0;
    }
    return list->firstNode ? (curNode = list->firstNode)->getData() : 0;
}

/*!
  \internal
  Sets the list iterator to point to the last item in the list.
*/

Q3PtrCollection::Item Q3GListIterator::toLast()
{
    if ( !list ) {
#if defined(QT_CHECK_NULL)
	qWarning( "Q3GListIterator::toLast: List has been deleted" );
#endif
	return 0;
    }
    return list->lastNode ? (curNode = list->lastNode)->getData() : 0;
}


/*!
  \fn Q3PtrCollection::Item Q3GListIterator::get() const
  \internal
  Returns the iterator item.
*/


/*!
  \internal
  Moves to the next item (postfix).
*/

Q3PtrCollection::Item Q3GListIterator::operator()()
{
    if ( !curNode )
	return 0;
    Q3PtrCollection::Item d = curNode->getData();
    curNode = curNode->next;
    return  d;
}

/*!
  \internal
  Moves to the next item (prefix).
*/

Q3PtrCollection::Item Q3GListIterator::operator++()
{
    if ( !curNode )
	return 0;
    curNode = curNode->next;
    return curNode ? curNode->getData() : 0;
}

/*!
  \internal
  Moves \a jumps positions forward.
*/

Q3PtrCollection::Item Q3GListIterator::operator+=( uint jumps )
{
    while ( curNode && jumps-- )
	curNode = curNode->next;
    return curNode ? curNode->getData() : 0;
}

/*!
  \internal
  Moves to the previous item (prefix).
*/

Q3PtrCollection::Item Q3GListIterator::operator--()
{
    if ( !curNode )
	return 0;
    curNode = curNode->prev;
    return curNode ? curNode->getData() : 0;
}

/*!
  \internal
  Moves \a jumps positions backward.
*/

Q3PtrCollection::Item Q3GListIterator::operator-=( uint jumps )
{
    while ( curNode && jumps-- )
	curNode = curNode->prev;
    return curNode ? curNode->getData() : 0;
}