vararray.h #1

/*
 * Copyright 1995, 1996 Perforce Software.  All rights reserved.
 */

/*
 * VarArray.h - manage a list of void *'s
 *
 * Class Defined:
 *
 *	VarArray - list of void *'s
 *	VVarArray - VarArray with virtual Compare/Destroy functions
 *
 * Public methods:
 *
 *	VarArray::Clear() - zero out count for values
 *	VarArray::Count() - return count of elements in array
 *	VarArray::ElemTab() - return a pointer to the array
 *	VarArray::Get(i) - return a pointer to slot i in the array
 *	VarArray::Edit(i) - return a editable pointer to slot i in the array
 *	VarArray::Move(i,j) - move element i to j
 *	VarArray::Remove(i) - remove element i
 *	VarArray::Put(v) - set a new slot to v
 *	VarArray::WillGrow(i) - returns size of new vararray if it
 *	                        would have to grow in the next i rows.
 *
 *	VVarArray::Diff() - subtract/compare/add to VarArrays
 *		OpDiff - substract two VarArrays and drop duplicates
 *		OpIntersect - compare VarArrays to find matches
 *		OpMerge - add two VarArrays, eliminating duplicates
 *
 *	VVarArray::Sort() - Qsort of the VarArray in place
 *
 * Private methods:
 *
 *	VarArray::New() - return a pointer to a new slot in the array
 */

class VarArray {
	
    public:

			VarArray();
			VarArray( int max );
			~VarArray();

	void		Clear() { numElems = 0; }
	int		Count() const { return numElems; }
	void **		ElemTab() { return elems; }
	void *		Get( int i ) const { return i<numElems ? elems[i]:0; }
	void *		Edit( int i ) { return i<numElems ? elems[i]:0; }
	void 		Move( int i, int j ) { elems[j] = elems[i]; }
	void 		Remove( int i );
	void *		Put( void *v ) { return *New() = v; }
	void		SetCount( int i ) { numElems = i; }
	int		WillGrow( int interval );

	void 		Exchange( int i, int j )
	    		{ 
			    void *t = elems[j];
			    elems[j] = elems[i];
			    elems[i] = t; 
			}

	void		Swap( int i, int j ) 
			{ Exchange( i, j ); }

	void		Swap( int i, int j, int count )
			{ while( count-- > 0 ) Exchange( i++, j++ ); }

    private:
	friend class VVarArray;

	void **		New();

	int		maxElems;
	int		numElems;
	void		**elems;
} ;

class VVarArray : public VarArray {

    public:

	enum Op { OpDiff, OpIntersect, OpMerge };

	virtual		~VVarArray() {};
	virtual int	Compare( const void *, const void * ) const = 0;
	virtual void	Destroy( void * ) const = 0;

	void 		Diff( Op op, VarArray &that );
	void		Sort() { Sort( 0, Count() ); }
	void		Uniq();

    private:
	void		Sort( int l, int u );
	int		Med3( int i, int j, int k ) const;

	int		Compare( int i, int j ) const
			{ return Compare( Get( i ), Get( j ) ); }

} ;