/****************************************************************************
**
**
** Implementation of QGList and QGListIterator classes
**
** Created : 920624
**
** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
**
** This file is part of the tools module of the Qt GUI Toolkit.
**
** This file may be distributed under the terms of the Q Public License
** as defined by Trolltech AS of Norway and appearing in the file
** LICENSE.QPL included in the packaging of this file.
**
** This file may be distributed and/or modified under the terms of the
** GNU General Public License version 2 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.
**
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
** licenses may use this file in accordance with the Qt Commercial License
** Agreement provided with the Software.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
** information about Qt Commercial License Agreements.
** See http://www.trolltech.com/qpl/ for QPL licensing information.
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact info@trolltech.com if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/
#include "qglist.h"
#include "qdatastream.h"
// NOT REVISED
/*!
\class QLNode qglist.h
\brief The QLNode class is an internal class for the QList template collection.
QLNode is a doubly linked list node; it has three pointers:
- Pointer to the previous node.
- Pointer to the next node.
- Pointer to the actual data.
Sometimes it might be practical to have direct access to the list nodes
in a QList, but it is seldom required.
\warning Be very careful if you want to access the list nodes. The heap
can easily get corrupted if you make a mistake.
\sa QList::currentNode(), QList::removeNode(), QList::takeNode()
*/
/*!
\fn QCollection::Item QLNode::getData()
Returns a pointer (\c void*) to the actual data in the list node.
*/
/*!
\class QGList qglist.h
\brief The QGList class is an internal class for implementing Qt collection classes.
QGList is a strictly internal class that acts as a base class for several
\link collection.html collection classes\endlink; QList, QQueue and
QStack.
QGList has some virtual functions that can be reimplemented to customize
the subclasses.
- compareItems() compares two collection/list items.
- read() reads a collection/list item from a QDataStream.
- write() writes a collection/list item to a QDataStream.
Normally, you do not have to reimplement any of these functions.
If you still want to reimplement them, see the QStrList class (qstrlist.h),
which is a good example.
*/
/*****************************************************************************
Default implementation of virtual functions
*****************************************************************************/
/*!
This virtual function compares two list items.
Returns:
- 0 if \e item1 == \e item2
- non-zero if \e item1 != \e item2
This function returns \e int rather than \e bool so that
reimplementations can return three values and use it to sort by:
- 0 if \e item1 == \e item2
- \> 0 (positive integer) if \e item1 \> \e item2
- \< 0 (negative integer) if \e item1 \< \e item2
The QList::inSort() function requires that compareItems() is implemented
as described here.
This function should not modify the list because some const functions
call compareItems().
The default implementation compares the pointers:
\code
\endcode
*/
int QGList::compareItems( QCollection::Item item1, QCollection::Item item2 )
{
return item1 != item2; // compare pointers
}
#ifndef QT_NO_DATASTREAM
/*!
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, QCollection::Item &item )
{
item = 0;
return s;
}
/*!
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, QCollection::Item ) const
{
return s;
}
#endif // QT_NO_DATASTREAM
/*****************************************************************************
QGList member functions
*****************************************************************************/
/*!
\internal
Constructs an empty list.
*/
QGList::QGList()
{
firstNode = lastNode = curNode = 0; // initialize list
numNodes = 0;
curIndex = -1;
iterators = 0; // initialize iterator list
}
/*!
\internal
Constructs a copy of \e list.
*/
QGList::QGList( const QGList & list )
: QCollection( 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;
}
}
/*!
\internal
Removes all items from the list and destroys the list.
*/
QGList::~QGList()
{
clear();
if ( !iterators ) // no iterators for this list
return;
QGListIterator *i = (QGListIterator*)iterators->first();
while ( i ) { // notify all iterators that
i->list = 0; // this list is deleted
i->curNode = 0;
i = (QGListIterator*)iterators->next();
}
delete iterators;
}
/*!
\internal
Assigns \e list to this list.
*/
QGList& QGList::operator=( const QGList &list )
{
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, else 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
\internal
Returns the number of items in the list.
*/
/*!
\internal
Returns the node at position \e 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;
}
QLNode *node;
int distance = index - curIndex; // node distance to cur node
bool forward; // direction to traverse
if ( index >= numNodes ) {
#if defined(CHECK_RANGE)
qWarning( "QGList::locate: Index %d out of range", index );
#endif
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;
}
/*!
\internal
Inserts an item at its sorted position in the list.
*/
void QGList::inSort( QCollection::Item d )
{
int index = 0;
QLNode *n = firstNode;
while ( n && compareItems(n->data,d) < 0 ){ // find position in list
n = n->next;
index++;
}
insertAt( index, d );
}
/*!
\internal
Inserts an item at the start of the list.
*/
void QGList::prepend( QCollection::Item d )
{
QLNode *n = new QLNode( newItem(d) );
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;
}
/*!
\internal
Inserts an item at the end of the list.
*/
void QGList::append( QCollection::Item d )
{
QLNode *n = new QLNode( newItem(d) );
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++;
}
/*!
\internal
Inserts an item at position \e index in the list.
*/
bool QGList::insertAt( uint index, QCollection::Item d )
{
if ( index == 0 ) { // insert at head of list
prepend( d );
return TRUE;
} else if ( index == numNodes ) { // append at tail of list
append( d );
return TRUE;
}
QLNode *nextNode = locate( index );
if ( !nextNode ) // illegal position
return FALSE;
QLNode *prevNode = nextNode->prev;
QLNode *n = new QLNode( newItem(d) );
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;
}
/*!
\internal
Relinks node \e 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;
}
/*!
\internal
Unlinks the current list node and returns a pointer to this node.
*/
QLNode *QGList::unlink()
{
if ( curNode == 0 ) // null current node
return 0;
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->count() ) { // update iterators
QGListIterator *i = (QGListIterator*)iterators->first();
while ( i ) { // fix all iterators that
if ( i->curNode == n ) // refers to pending node
i->curNode = curNode;
i = (QGListIterator*)iterators->next();
}
}
numNodes--;
return n;
}
/*!
\internal
Removes the node \e n from the list.
*/
bool QGList::removeNode( QLNode *n )
{
#if defined(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;
}
/*!
\internal
Removes the item \e d from the list. Uses compareItems() to find the item.
*/
bool QGList::remove( QCollection::Item d )
{
if ( d ) { // find the item
if ( find(d) == -1 )
return FALSE;
}
QLNode *n = unlink(); // unlink node
if ( !n )
return FALSE;
deleteItem( n->data ); // deallocate this node
delete n;
return TRUE;
}
/*!
\internal
Removes the item \e d from the list.
*/
bool QGList::removeRef( QCollection::Item d )
{
if ( d ) { // find the item
if ( findRef(d) == -1 )
return FALSE;
}
QLNode *n = unlink(); // unlink node
if ( !n )
return FALSE;
deleteItem( n->data ); // deallocate this node
delete n;
return TRUE;
}
/*!
\fn bool QGList::removeFirst()
\internal
Removes the first item in the list.
*/
/*!
\fn bool QGList::removeLast()
\internal
Removes the last item in the list.
*/
/*!
\internal
Removes the item at position \e index from the list.
*/
bool QGList::removeAt( uint index )
{
if ( !locate(index) )
return FALSE;
QLNode *n = unlink(); // unlink node
if ( !n )
return FALSE;
deleteItem( n->data ); // deallocate this node
delete n;
return TRUE;
}
/*!
\internal
Takes the node \e n out of the list.
*/
QCollection::Item QGList::takeNode( QLNode *n )
{
#if defined(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;
}
/*!
\internal
Takes the current item out of the list.
*/
QCollection::Item QGList::take()
{
QLNode *n = unlink(); // unlink node
Item d = n ? n->data : 0;
delete n; // delete node, keep contents
return d;
}
/*!
\internal
Takes the item at position \e index out of the list.
*/
QCollection::Item QGList::takeAt( uint index )
{
if ( !locate(index) )
return 0;
QLNode *n = unlink(); // unlink node
Item d = n ? n->data : 0;
delete n; // delete node, keep contents
return d;
}
/*!
\internal
Takes the first item out of the list.
*/
QCollection::Item QGList::takeFirst()
{
first();
QLNode *n = unlink(); // unlink node
Item d = n ? n->data : 0;
delete n;
return d;
}
/*!
\internal
Takes the last item out of the list.
*/
QCollection::Item QGList::takeLast()
{
last();
QLNode *n = unlink(); // unlink node
Item d = n ? n->data : 0;
delete n;
return d;
}
/*!
\internal
Removes all items from the list.
*/
void QGList::clear()
{
QLNode *n = firstNode;
firstNode = lastNode = curNode = 0; // initialize list
numNodes = 0;
curIndex = -1;
if ( iterators && iterators->count() ) {
QGListIterator *i = (QGListIterator*)iterators->first();
while ( i ) { // notify all iterators that
i->curNode = 0; // this list is empty
i = (QGListIterator*)iterators->next();
}
}
QLNode *prevNode;
while ( n ) { // for all nodes ...
deleteItem( n->data ); // deallocate data
prevNode = n;
n = n->next;
delete prevNode; // deallocate node
}
}
/*!
\internal
Finds an item in the list.
*/
int QGList::findRef( QCollection::Item d, bool fromStart )
{
QLNode *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
}
/*!
\internal
Finds an item in the list. Uses compareItems().
*/
int QGList::find( QCollection::Item d, bool fromStart )
{
QLNode *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
}
/*!
\internal
Counts the number an item occurs in the list.
*/
uint QGList::containsRef( QCollection::Item d ) const
{
QLNode *n = firstNode;
uint count = 0;
while ( n ) { // for all nodes...
if ( n->data == d ) // count # exact matches
count++;
n = n->next;
}
return count;
}
/*!
\internal
Counts the number an item occurs in the list. Uses compareItems().
*/
uint QGList::contains( QCollection::Item d ) const
{
QLNode *n = firstNode;
uint count = 0;
QGList *that = (QGList*)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 QCollection::Item QGList::at( uint index )
\internal
Sets the item at position \e index to the current item.
*/
/*!
\fn int QGList::at() const
\internal
Returns the current index.
*/
/*!
\fn QLNode *QGList::currentNode() const
\internal
Returns the current node.
*/
/*!
\fn QCollection::Item QGList::get() const
\internal
Returns the current item.
*/
/*!
\fn QCollection::Item QGList::cfirst() const
\internal
Returns the first item in the list.
*/
/*!
\fn QCollection::Item QGList::clast() const
\internal
Returns the last item in the list.
*/
/*!
\internal
Returns the first list item. Sets this to current.
*/
QCollection::Item QGList::first()
{
if ( firstNode ) {
curIndex = 0;
return (curNode=firstNode)->data;
}
return 0;
}
/*!
\internal
Returns the last list item. Sets this to current.
*/
QCollection::Item QGList::last()
{
if ( lastNode ) {
curIndex = numNodes-1;
return (curNode=lastNode)->data;
}
return 0;
}
/*!
\internal
Returns the next list item (after current). Sets this to current.
*/
QCollection::Item QGList::next()
{
if ( curNode ) {
if ( curNode->next ) {
curIndex++;
curNode = curNode->next;
return curNode->data;
}
curIndex = -1;
curNode = 0;
}
return 0;
}
/*!
\internal
Returns the previous list item (before current). Sets this to current.
*/
QCollection::Item QGList::prev()
{
if ( curNode ) {
if ( curNode->prev ) {
curIndex--;
curNode = curNode->prev;
return curNode->data;
}
curIndex = -1;
curNode = 0;
}
return 0;
}
void QGList::heapSortPushDown( QCollection::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 ) {
QCollection::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
QCollection::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
QCollection::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 QGList::sort()
{
uint n = count();
if ( n < 2 )
return;
// Create the heap
QCollection::Item* realheap = new QCollection::Item[ n ];
// Wow, what a fake. But I want the heap to be indexed as 1...n
QCollection::Item* heap = realheap - 1;
int size = 0;
QLNode* 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 ) {
QCollection::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;
}
/*****************************************************************************
QGList stream functions
*****************************************************************************/
#ifndef QT_NO_DATASTREAM
QDataStream &operator>>( QDataStream &s, QGList &list )
{ // read list
return list.read( s );
}
QDataStream &operator<<( QDataStream &s, const QGList &list )
{ // write list
return list.write( s );
}
/*!
\internal
Reads a list from the stream \e s.
*/
QDataStream &QGList::read( QDataStream &s )
{
uint num;
s >> num; // read number of items
clear(); // clear list
while ( num-- ) { // read all items
Item d;
read( s, d );
CHECK_PTR( d );
if ( !d ) // no memory
break;
QLNode *n = new QLNode( d );
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;
}
/*!
\internal
Writes the list to the stream \e s.
*/
QDataStream &QGList::write( QDataStream &s ) const
{
s << count(); // write number of items
QLNode *n = firstNode;
while ( n ) { // write all items
write( s, n->data );
n = n->next;
}
return s;
}
#endif // QT_NO_DATASTREAM
/*****************************************************************************
QGListIterator member functions
*****************************************************************************/
/*!
\class QGListIterator qglist.h
\brief The QGListIterator class is an internal class for implementing QListIterator.
QGListIterator is a strictly internal class that does the heavy work for
QListIterator.
*/
/*!
\internal
Constructs an iterator that operates on the list \e l.
*/
QGListIterator::QGListIterator( const QGList &l )
{
list = (QGList *)&l; // get reference to list
curNode = list->firstNode; // set to first node
if ( !list->iterators ) {
list->iterators = new QGList; // create iterator list
CHECK_PTR( list->iterators );
}
list->iterators->append( this ); // attach iterator to list
}
/*!
\internal
Constructs a copy of the iterator \e it.
*/
QGListIterator::QGListIterator( const QGListIterator &it )
{
list = it.list;
curNode = it.curNode;
if ( list )
list->iterators->append( this ); // attach iterator to list
}
/*!
\internal
Assigns a copy of the iterator \e it and returns a reference to this
iterator.
*/
QGListIterator &QGListIterator::operator=( const QGListIterator &it )
{
if ( list ) // detach from old list
list->iterators->removeRef( this );
list = it.list;
curNode = it.curNode;
if ( list )
list->iterators->append( this ); // attach to new list
return *this;
}
/*!
\internal
Destroys the iterator.
*/
QGListIterator::~QGListIterator()
{
if ( list ) // detach iterator from list
list->iterators->removeRef(this);
}
/*!
\fn bool QGListIterator::atFirst() const
\internal
Returns TRUE if the iterator points to the first item, otherwise FALSE.
*/
/*!
\fn bool QGListIterator::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.
*/
QCollection::Item QGListIterator::toFirst()
{
if ( !list ) {
#if defined(CHECK_NULL)
qWarning( "QGListIterator::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.
*/
QCollection::Item QGListIterator::toLast()
{
if ( !list ) {
#if defined(CHECK_NULL)
qWarning( "QGListIterator::toLast: List has been deleted" );
#endif
return 0;
}
return list->lastNode ? (curNode = list->lastNode)->getData() : 0;
}
/*!
\fn QCollection::Item QGListIterator::get() const
\internal
Returns the iterator item.
*/
/*!
\internal
Moves to the next item (postfix).
*/
QCollection::Item QGListIterator::operator()()
{
if ( !curNode )
return 0;
QCollection::Item d = curNode->getData();
curNode = curNode->next;
return d;
}
/*!
\internal
Moves to the next item (prefix).
*/
QCollection::Item QGListIterator::operator++()
{
if ( !curNode )
return 0;
curNode = curNode->next;
return curNode ? curNode->getData() : 0;
}
/*!
\internal
Moves \e jumps positions forward.
*/
QCollection::Item QGListIterator::operator+=( uint jumps )
{
while ( curNode && jumps-- )
curNode = curNode->next;
return curNode ? curNode->getData() : 0;
}
/*!
\internal
Moves to the previous item (prefix).
*/
QCollection::Item QGListIterator::operator--()
{
if ( !curNode )
return 0;
curNode = curNode->prev;
return curNode ? curNode->getData() : 0;
}
/*!
\internal
Moves \e jumps positions backward.
*/
QCollection::Item QGListIterator::operator-=( uint jumps )
{
while ( curNode && jumps-- )
curNode = curNode->prev;
return curNode ? curNode->getData() : 0;
}