|
Packit |
1c1d7e |
/****************************************************************************
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Implementation of QGVector class
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Created : 930907
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file is part of the tools module of the Qt GUI Toolkit.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file may be distributed under the terms of the Q Public License
|
|
Packit |
1c1d7e |
** as defined by Trolltech AS of Norway and appearing in the file
|
|
Packit |
1c1d7e |
** LICENSE.QPL included in the packaging of this file.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file may be distributed and/or modified under the terms of the
|
|
Packit |
1c1d7e |
** GNU General Public License version 2 as published by the Free Software
|
|
Packit |
1c1d7e |
** Foundation and appearing in the file LICENSE.GPL included in the
|
|
Packit |
1c1d7e |
** packaging of this file.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
|
|
Packit |
1c1d7e |
** licenses may use this file in accordance with the Qt Commercial License
|
|
Packit |
1c1d7e |
** Agreement provided with the Software.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
|
|
Packit |
1c1d7e |
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
|
|
Packit |
1c1d7e |
** information about Qt Commercial License Agreements.
|
|
Packit |
1c1d7e |
** See http://www.trolltech.com/qpl/ for QPL licensing information.
|
|
Packit |
1c1d7e |
** See http://www.trolltech.com/gpl/ for GPL licensing information.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
** Contact info@trolltech.com if any conditions of this licensing are
|
|
Packit |
1c1d7e |
** not clear to you.
|
|
Packit |
1c1d7e |
**
|
|
Packit |
1c1d7e |
**********************************************************************/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#define QGVECTOR_CPP
|
|
Packit |
1c1d7e |
#include "qgvector.h"
|
|
Packit |
1c1d7e |
#include "qglist.h"
|
|
Packit |
1c1d7e |
#include "qstring.h"
|
|
Packit |
1c1d7e |
#include "qdatastream.h"
|
|
Packit |
1c1d7e |
#include <stdlib.h>
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#define USE_MALLOC // comment to use new/delete
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#undef NEW
|
|
Packit |
1c1d7e |
#undef DELETE
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#if defined(USE_MALLOC)
|
|
Packit |
1c1d7e |
#define NEW(type,size) ((type*)malloc(size*sizeof(type)))
|
|
Packit |
1c1d7e |
#define DELETE(array) (free((char*)array))
|
|
Packit |
1c1d7e |
#else
|
|
Packit |
1c1d7e |
#define NEW(type,size) (new type[size])
|
|
Packit |
1c1d7e |
#define DELETE(array) (delete[] array)
|
|
Packit |
1c1d7e |
#define DONT_USE_REALLOC // comment to use realloc()
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
// NOT REVISED
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\class QGVector qgvector.h
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
\brief The QGVector class is an internal class for implementing Qt
|
|
Packit |
1c1d7e |
collection classes.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QGVector is a strictly internal class that acts as a base class for
|
|
Packit |
1c1d7e |
the QVector collection class.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QGVector has some virtual functions that may be reimplemented in
|
|
Packit |
1c1d7e |
subclasses to to customize behavior.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
compareItems() compares two collection/vector items.
|
|
Packit |
1c1d7e |
read() reads a collection/vector item from a QDataStream.
|
|
Packit |
1c1d7e |
write() writes a collection/vector item to a QDataStream.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*****************************************************************************
|
|
Packit |
1c1d7e |
Default implementation of virtual functions
|
|
Packit |
1c1d7e |
*****************************************************************************/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
This virtual function compares two list items.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
Returns:
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
0 if \a item1 == \a item2
|
|
Packit |
1c1d7e |
non-zero if \a item1 != \a item2
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
This function returns \e int rather than \e bool so that
|
|
Packit |
1c1d7e |
reimplementations can return one of three values and use it to sort
|
|
Packit |
1c1d7e |
by:
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
0 if \e item1 == \e item2
|
|
Packit |
1c1d7e |
\> 0 (positive integer) if \a item1 \> \a item2
|
|
Packit |
1c1d7e |
\< 0 (negative integer) if \a item1 \< \a item2
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
The QVector::sort() and QVector::bsearch() functions require that
|
|
Packit |
1c1d7e |
compareItems() is implemented as described here.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
This function should not modify the vector because some const
|
|
Packit |
1c1d7e |
functions call compareItems().
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
int QGVector::compareItems( Item d1, Item d2 )
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return d1 != d2; // compare pointers
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#ifndef QT_NO_DATASTREAM
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
Reads a collection/vector item from the stream \a s and returns a reference
|
|
Packit |
1c1d7e |
to the stream.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
The default implementation sets \e item to 0.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
\sa write()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QDataStream &QGVector::read( QDataStream &s, Item &d )
|
|
Packit |
1c1d7e |
{ // read item from stream
|
|
Packit |
1c1d7e |
d = 0;
|
|
Packit |
1c1d7e |
return s;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
Writes a collection/vector item to the stream \a s and returns a reference
|
|
Packit |
1c1d7e |
to the stream.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
The default implementation does nothing.
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
\sa read()
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QDataStream &QGVector::write( QDataStream &s, Item ) const
|
|
Packit |
1c1d7e |
{ // write item to stream
|
|
Packit |
1c1d7e |
return s;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif // QT_NO_DATASTREAM
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*****************************************************************************
|
|
Packit |
1c1d7e |
QGVector member functions
|
|
Packit |
1c1d7e |
*****************************************************************************/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QGVector::QGVector() // create empty vector
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
vec = 0;
|
|
Packit |
1c1d7e |
len = numItems = 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
QGVector::QGVector( uint size ) // create vectors with nullptrs
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
len = size;
|
|
Packit |
1c1d7e |
numItems = 0;
|
|
Packit |
1c1d7e |
if ( len == 0 ) { // zero length
|
|
Packit |
1c1d7e |
vec = 0;
|
|
Packit |
1c1d7e |
return;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
vec = NEW(Item,len);
|
|
Packit |
1c1d7e |
CHECK_PTR( vec );
|
|
Packit |
1c1d7e |
memset( (void*)vec, 0, len*sizeof(Item) ); // fill with nulls
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QGVector::QGVector( const QGVector &a ) // make copy of other vector
|
|
Packit |
1c1d7e |
: QCollection( a )
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
len = a.len;
|
|
Packit |
1c1d7e |
numItems = a.numItems;
|
|
Packit |
1c1d7e |
vec = NEW(Item,len);
|
|
Packit |
1c1d7e |
CHECK_PTR( vec );
|
|
Packit |
1c1d7e |
for ( uint i=0; i
|
|
Packit |
1c1d7e |
vec[i] = a.vec[i] ? newItem( a.vec[i] ) : 0;
|
|
Packit |
1c1d7e |
CHECK_PTR( vec[i] );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QGVector::~QGVector()
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
clear();
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QGVector& QGVector::operator=( const QGVector &v )
|
|
Packit |
1c1d7e |
{ // assign from other vector
|
|
Packit |
1c1d7e |
clear(); // first delete old vector
|
|
Packit |
1c1d7e |
len = v.len;
|
|
Packit |
1c1d7e |
numItems = v.numItems;
|
|
Packit |
1c1d7e |
vec = NEW(Item,len); // create new vector
|
|
Packit |
1c1d7e |
CHECK_PTR( vec );
|
|
Packit |
1c1d7e |
for ( uint i=0; i
|
|
Packit |
1c1d7e |
vec[i] = v.vec[i] ? newItem( v.vec[i] ) : 0;
|
|
Packit |
1c1d7e |
CHECK_PTR( vec[i] );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return *this;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\fn Item *QGVector::data() const
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\fn uint QGVector::size() const
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\fn uint QGVector::count() const
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\fn Item QGVector::at( uint index ) const
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
bool QGVector::insert( uint index, Item d ) // insert item at index
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
#if defined(CHECK_RANGE)
|
|
Packit |
1c1d7e |
if ( index >= len ) { // range error
|
|
Packit |
1c1d7e |
qWarning( "QGVector::insert: Index %d out of range", index );
|
|
Packit |
1c1d7e |
return FALSE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
if ( vec[index] ) { // remove old item
|
|
Packit |
1c1d7e |
deleteItem( vec[index] );
|
|
Packit |
1c1d7e |
numItems--;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if ( d ) {
|
|
Packit |
1c1d7e |
vec[index] = newItem( d );
|
|
Packit |
1c1d7e |
CHECK_PTR( vec[index] );
|
|
Packit |
1c1d7e |
numItems++;
|
|
Packit |
1c1d7e |
return vec[index] != 0;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
vec[index] = 0; // reset item
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
bool QGVector::remove( uint index ) // remove item at index
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
#if defined(CHECK_RANGE)
|
|
Packit |
1c1d7e |
if ( index >= len ) { // range error
|
|
Packit |
1c1d7e |
qWarning( "QGVector::remove: Index %d out of range", index );
|
|
Packit |
1c1d7e |
return FALSE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
if ( vec[index] ) { // valid item
|
|
Packit |
1c1d7e |
deleteItem( vec[index] ); // delete it
|
|
Packit |
1c1d7e |
vec[index] = 0; // reset pointer
|
|
Packit |
1c1d7e |
numItems--;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QCollection::Item QGVector::take( uint index ) // take out item
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
#if defined(CHECK_RANGE)
|
|
Packit |
1c1d7e |
if ( index >= len ) { // range error
|
|
Packit |
1c1d7e |
qWarning( "QGVector::take: Index %d out of range", index );
|
|
Packit |
1c1d7e |
return 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
Item d = vec[index]; // don't delete item
|
|
Packit |
1c1d7e |
if ( d )
|
|
Packit |
1c1d7e |
numItems--;
|
|
Packit |
1c1d7e |
vec[index] = 0;
|
|
Packit |
1c1d7e |
return d;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QGVector::clear() // clear vector
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if ( vec ) {
|
|
Packit |
1c1d7e |
for ( uint i=0; i
|
|
Packit |
1c1d7e |
if ( vec[i] )
|
|
Packit |
1c1d7e |
deleteItem( vec[i] );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
DELETE(vec);
|
|
Packit |
1c1d7e |
vec = 0;
|
|
Packit |
1c1d7e |
len = numItems = 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
bool QGVector::resize( uint newsize ) // resize array
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if ( newsize == len ) // nothing to do
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
if ( vec ) { // existing data
|
|
Packit |
1c1d7e |
if ( newsize < len ) { // shrink vector
|
|
Packit |
1c1d7e |
uint i = newsize;
|
|
Packit |
1c1d7e |
while ( i < len ) { // delete lost items
|
|
Packit |
1c1d7e |
if ( vec[i] ) {
|
|
Packit |
1c1d7e |
deleteItem( vec[i] );
|
|
Packit |
1c1d7e |
numItems--;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
i++;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if ( newsize == 0 ) { // vector becomes empty
|
|
Packit |
1c1d7e |
DELETE(vec);
|
|
Packit |
1c1d7e |
vec = 0;
|
|
Packit |
1c1d7e |
len = numItems = 0;
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#if defined(DONT_USE_REALLOC)
|
|
Packit |
1c1d7e |
Item *newvec = NEW(Item,newsize); // manual realloc
|
|
Packit |
1c1d7e |
memcpy( newvec, vec, (len < newsize ? len : newsize)*sizeof(Item) );
|
|
Packit |
1c1d7e |
DELETE(vec);
|
|
Packit |
1c1d7e |
vec = newvec;
|
|
Packit |
1c1d7e |
#else
|
|
Packit |
1c1d7e |
vec = (Item*)realloc( (char *)vec, newsize*sizeof(Item) );
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
} else { // create new vector
|
|
Packit |
1c1d7e |
vec = NEW(Item,newsize);
|
|
Packit |
1c1d7e |
len = numItems = 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
CHECK_PTR( vec );
|
|
Packit |
1c1d7e |
if ( !vec ) // no memory
|
|
Packit |
1c1d7e |
return FALSE;
|
|
Packit |
1c1d7e |
if ( newsize > len ) // init extra space added
|
|
Packit |
1c1d7e |
memset( (void*)&vec[len], 0, (newsize-len)*sizeof(Item) );
|
|
Packit |
1c1d7e |
len = newsize;
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
bool QGVector::fill( Item d, int flen ) // resize and fill vector
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if ( flen < 0 )
|
|
Packit |
1c1d7e |
flen = len; // default: use vector length
|
|
Packit |
1c1d7e |
else if ( !resize( flen ) )
|
|
Packit |
1c1d7e |
return FALSE;
|
|
Packit |
1c1d7e |
for ( uint i=0; i<(uint)flen; i++ ) // insert d at every index
|
|
Packit |
1c1d7e |
insert( i, d );
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
static QGVector *sort_vec=0; // current sort vector
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#if defined(Q_C_CALLBACKS)
|
|
Packit |
1c1d7e |
extern "C" {
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
static int cmp_vec( const void *n1, const void *n2 )
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
return sort_vec->compareItems( *((QCollection::Item*)n1), *((QCollection::Item*)n2) );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
#if defined(Q_C_CALLBACKS)
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QGVector::sort() // sort vector
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if ( count() == 0 ) // no elements
|
|
Packit |
1c1d7e |
return;
|
|
Packit |
1c1d7e |
register Item *start = &vec[0];
|
|
Packit |
1c1d7e |
register Item *end = &vec[len-1];
|
|
Packit |
1c1d7e |
Item tmp;
|
|
Packit |
1c1d7e |
while ( TRUE ) { // put all zero elements behind
|
|
Packit |
1c1d7e |
while ( start < end && *start != 0 )
|
|
Packit |
1c1d7e |
start++;
|
|
Packit |
1c1d7e |
while ( end > start && *end == 0 )
|
|
Packit |
1c1d7e |
end--;
|
|
Packit |
1c1d7e |
if ( start < end ) {
|
|
Packit |
1c1d7e |
tmp = *start;
|
|
Packit |
1c1d7e |
*start = *end;
|
|
Packit |
1c1d7e |
*end = tmp;
|
|
Packit |
1c1d7e |
} else {
|
|
Packit |
1c1d7e |
break;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
sort_vec = (QGVector*)this;
|
|
Packit |
1c1d7e |
qsort( vec, count(), sizeof(Item), cmp_vec );
|
|
Packit |
1c1d7e |
sort_vec = 0;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
int QGVector::bsearch( Item d ) const // binary search; when sorted
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if ( !len )
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
if ( !d ) {
|
|
Packit |
1c1d7e |
#if defined(CHECK_NULL)
|
|
Packit |
1c1d7e |
qWarning( "QGVector::bsearch: Cannot search for null object" );
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
int n1 = 0;
|
|
Packit |
1c1d7e |
int n2 = len - 1;
|
|
Packit |
1c1d7e |
int mid = 0;
|
|
Packit |
1c1d7e |
bool found = FALSE;
|
|
Packit |
1c1d7e |
while ( n1 <= n2 ) {
|
|
Packit |
1c1d7e |
int res;
|
|
Packit |
1c1d7e |
mid = (n1 + n2)/2;
|
|
Packit |
1c1d7e |
if ( vec[mid] == 0 ) // null item greater
|
|
Packit |
1c1d7e |
res = -1;
|
|
Packit |
1c1d7e |
else
|
|
Packit |
1c1d7e |
res = ((QGVector*)this)->compareItems( d, vec[mid] );
|
|
Packit |
1c1d7e |
if ( res < 0 )
|
|
Packit |
1c1d7e |
n2 = mid - 1;
|
|
Packit |
1c1d7e |
else if ( res > 0 )
|
|
Packit |
1c1d7e |
n1 = mid + 1;
|
|
Packit |
1c1d7e |
else { // found it
|
|
Packit |
1c1d7e |
found = TRUE;
|
|
Packit |
1c1d7e |
break;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
if ( !found )
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
// search to first of equal items
|
|
Packit |
1c1d7e |
while ( (mid - 1 >= 0) && !((QGVector*)this)->compareItems(d, vec[mid-1]) )
|
|
Packit |
1c1d7e |
mid--;
|
|
Packit |
1c1d7e |
return mid;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
int QGVector::findRef( Item d, uint index) const // find exact item in vector
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
#if defined(CHECK_RANGE)
|
|
Packit |
1c1d7e |
if ( index >= len ) { // range error
|
|
Packit |
1c1d7e |
qWarning( "QGVector::findRef: Index %d out of range", index );
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
for ( uint i=index; i
|
|
Packit |
1c1d7e |
if ( vec[i] == d )
|
|
Packit |
1c1d7e |
return i;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
int QGVector::find( Item d, uint index ) const // find equal item in vector
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
#if defined(CHECK_RANGE)
|
|
Packit |
1c1d7e |
if ( index >= len ) { // range error
|
|
Packit |
1c1d7e |
qWarning( "QGVector::find: Index %d out of range", index );
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
for ( uint i=index; i
|
|
Packit |
1c1d7e |
if ( vec[i] == 0 && d == 0 ) // found null item
|
|
Packit |
1c1d7e |
return i;
|
|
Packit |
1c1d7e |
if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 )
|
|
Packit |
1c1d7e |
return i;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return -1;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
uint QGVector::containsRef( Item d ) const // get number of exact matches
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
uint count = 0;
|
|
Packit |
1c1d7e |
for ( uint i=0; i
|
|
Packit |
1c1d7e |
if ( vec[i] == d )
|
|
Packit |
1c1d7e |
count++;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return count;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
uint QGVector::contains( Item d ) const // get number of equal matches
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
uint count = 0;
|
|
Packit |
1c1d7e |
for ( uint i=0; i
|
|
Packit |
1c1d7e |
if ( vec[i] == 0 && d == 0 ) // count null items
|
|
Packit |
1c1d7e |
count++;
|
|
Packit |
1c1d7e |
if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 )
|
|
Packit |
1c1d7e |
count++;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return count;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
bool QGVector::insertExpand( uint index, Item d )// insert and grow if necessary
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
if ( index >= len ) {
|
|
Packit |
1c1d7e |
if ( !resize( index+1 ) ) // no memory
|
|
Packit |
1c1d7e |
return FALSE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
insert( index, d );
|
|
Packit |
1c1d7e |
return TRUE;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QGVector::toList( QGList *list ) const // store items in list
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
list->clear();
|
|
Packit |
1c1d7e |
for ( uint i=0; i
|
|
Packit |
1c1d7e |
if ( vec[i] )
|
|
Packit |
1c1d7e |
list->append( vec[i] );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
void QGVector::warningIndexRange( uint i )
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
#if defined(CHECK_RANGE)
|
|
Packit |
1c1d7e |
qWarning( "QGVector::operator[]: Index %d out of range", i );
|
|
Packit |
1c1d7e |
#else
|
|
Packit |
1c1d7e |
Q_UNUSED( i )
|
|
Packit |
1c1d7e |
#endif
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*****************************************************************************
|
|
Packit |
1c1d7e |
QGVector stream functions
|
|
Packit |
1c1d7e |
*****************************************************************************/
|
|
Packit |
1c1d7e |
#ifndef QT_NO_DATASTREAM
|
|
Packit |
1c1d7e |
QDataStream &operator>>( QDataStream &s, QGVector &vec )
|
|
Packit |
1c1d7e |
{ // read vector
|
|
Packit |
1c1d7e |
return vec.read( s );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QDataStream &operator<<( QDataStream &s, const QGVector &vec )
|
|
Packit |
1c1d7e |
{ // write vector
|
|
Packit |
1c1d7e |
return vec.write( s );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QDataStream &QGVector::read( QDataStream &s ) // read vector from stream
|
|
Packit |
1c1d7e |
{
|
|
Packit |
1c1d7e |
uint num;
|
|
Packit |
1c1d7e |
s >> num; // read number of items
|
|
Packit |
1c1d7e |
clear(); // clear vector
|
|
Packit |
1c1d7e |
resize( num );
|
|
Packit |
1c1d7e |
for (uint i=0; i
|
|
Packit |
1c1d7e |
Item d;
|
|
Packit |
1c1d7e |
read( s, d );
|
|
Packit |
1c1d7e |
CHECK_PTR( d );
|
|
Packit |
1c1d7e |
if ( !d ) // no memory
|
|
Packit |
1c1d7e |
break;
|
|
Packit |
1c1d7e |
vec[i] = d;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return s;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
/*!
|
|
Packit |
1c1d7e |
\internal
|
|
Packit |
1c1d7e |
*/
|
|
Packit |
1c1d7e |
|
|
Packit |
1c1d7e |
QDataStream &QGVector::write( QDataStream &s ) const
|
|
Packit |
1c1d7e |
{ // write vector to stream
|
|
Packit |
1c1d7e |
uint num = count();
|
|
Packit |
1c1d7e |
s << num; // number of items to write
|
|
Packit |
1c1d7e |
num = size();
|
|
Packit |
1c1d7e |
for (uint i=0; i
|
|
Packit |
1c1d7e |
if ( vec[i] )
|
|
Packit |
1c1d7e |
write( s, vec[i] );
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
return s;
|
|
Packit |
1c1d7e |
}
|
|
Packit |
1c1d7e |
#endif // QT_NO_DATASTREAM
|