Blame qtools/qgvector.cpp

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