// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey // Author(s): Michael Dineen (Los Alamos National Laboratory) // This software is copyrighted by the DIMACS Center at Rutgers, The State // University of New Jersey. IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND // RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY DISCLAIM // ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL // DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY // DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE // POSSIBILITY OF SUCH DAMAGE. // THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE // IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE // NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR // MODIFICATIONS. // The authors hereby grant permission to use, copy, modify, distribute, // and license this software and its documentation for any purpose, provided // that existing copyright notices are retained in all copies and that this // notice is included verbatim in any distributions. No written agreement, // license, or royalty fee is required for any of the authorized uses. // Modifications to this software may be copyrighted by their authors // and need not follow the licensing terms described here, provided that // the new terms are clearly indicated on the first page of each file where // they apply. // Last File Update: 31-Jul-1996 // #ifndef _dyarray_h #define _dyarray_h class istream; class ostream; #include // qsort #include #include // To catch uncomparable objects -- non operator== objects at run-time // template< class T > inline Bool operator==(const T&, const T&) { assert(FALSE); return FALSE; } // To catch the case when the stdlib quick sort routine is called without // a predefined compare function // template< class T > inline int compare( const T*, const T* ) { assert(FALSE); return 1; } // Allow for efficient Arrays for simple types (memory copyable types) // #define Inline inline #ifndef __GNUC__ /* Doesn't g++ support template specialization? */ // Inline Bool simpleType( const int& ) { return TRUE; } Inline Bool simpleType( const char& ) { return TRUE; } Inline Bool simpleType( const short& ) { return TRUE; } Inline Bool simpleType( const long& ) { return TRUE; } Inline Bool simpleType( const uint& ) { return TRUE; } #ifndef CRI Inline Bool simpleType( const uchar& ) { return TRUE; } #endif Inline Bool simpleType( const ushort& ) { return TRUE; } Inline Bool simpleType( const ulong& ) { return TRUE; } // #endif template Inline Bool simpleType( const T& ) // false if not above #ifdef Inline { return FALSE; } #else ; #endif #undef Inline // ------------------------------------------------------------------- template< class T > class UnArray { _io_declarations( UnArray< T > ) private: // current size // int _size; protected: // Copy length elements from to self. // No error checking. // void copy( const T* a, int length ); // the actual array // memory management in dyarray needs access // T* array; // For dyarray (and others who need to know about storage). // // Return the amount of storage allocated. // virtual int allocSize() const { return _size; } // virtual void allocate( int i ); // // Reallocate to newSize, copying first keepNum elements to new. // virtual void reallocate( int newSize, int keepNum ); // // Fiddle with the usable size of the array. // For dyarray. // void setSize( int size ) { _size = size; } // For marray, to set the internal pointer // void setBaseAddr( void* p ) { array = (T*) p; } public: // constructor : create with 0 size // UnArray() { allocate( 0 ); } // constructor : create with given size // UnArray( int size ); // copy constructor // UnArray( const UnArray& ); // copy constructor, with extra entries // UnArray( const UnArray&, int size ); // assignment // does not reallocate if size(rhs)=size(lhs) // UnArray& operator=( const UnArray& ); // resize the array and copy old elements to new. // does nothing if newSize == size(). // void resize( int newSize ); // resize the array, and do not copy old elements to new. // does nothing if newSize == size(). // void resizeNoCopy( int newSize ); // resize the array and copy old elements to new // does nothing if newSize == size() // If the array grows, the new area is filled with fill. // void resize( int newSize, const T& fill ); /* * extend the array by "addSize" elements. */ void extend( int addSize ) { resize( size()+addSize ); } // void extend( int addSize, const T& fill ) { resize( size()+addSize, fill ); } // void append( const T& item ) { extend( 1, item ); } // void shrink( int addSize ) { resize( size()-addSize ); } /* * Add and subtract other subarrays/sets */ void append( const UnArray &A ); // void minus( const UnArray &A ); // Load from file. Resize according to the stored size, // then load. Does no free store operation if new size // == old size. // This is a binary operation, not ascii. // It is not implemented in general, but is specialised for uchar. // void loadFromFile( istream& ); // Same as above, but the length is not loaded from the file. // void loadFromFile( istream&, int length ); // Save to file. This is a binary operation, not ascii. // Length is written out initially. // It is not implemented in general, but is specialised for uchar. // void saveToFile( ostream& ); // Same as above, but the length is not saved to the file. // void saveToFileNoLength( ostream& ); // destructor // virtual ~UnArray(); // fill the array // void fill(const T &fill); // subscripting // T& operator[]( int i ) const { assert( i>=0 && i<_size ); return array[i]; } // non-lvalue access // T get( int i) const { assert( i>=0 && i<_size ); return array[i]; } // void put( int i, const T val ) { assert( i>=0 && i<_size ); array[i] = (T) val; } int size() const { return _size; } int length() const { return _size; } // Array comparison functions. // Bool operator==( const UnArray& ) const; Bool operator!=( const UnArray& a ) const { return ! (*this == a); } /* * Return index of an prospective element of the array * (returns _size if the element isn't found.) */ int index( const T& ) const; /* * for PermEnum class */ void swap( int i, int j ) { assert( i>=0 && i<_size && j>=0 && j<_size ); T val = array[i]; array[i] = array[j]; array[j] = val; } // void reverse( int i, int j ); void reverse( int j ) { reverse( 0, j ); } void reverse( ) { reverse( 0, _size-1 ); } // void rotate( int i, int j ); // void rotateLeft( int num ); void rotateRight( int num ); // void shiftLeft( int index, int num ); void shiftAndResizeLeft( int index, int num ); void shiftAndResizeRight( int index, int num ); // Direct internal access // void* baseAddr() const { return &( array[ 0 ] ); } // void* offsetAddr( int pos ) const { return &( array[ pos ] ); } // // copy the passed memory to the location array[index] // void binaryInsert( int index, char* buffer, int length ); // Simple sorting (only implemented for char, short, int) // void simpleSortUp(); // General sorting method which requires an externally defined // QSORT function compare defined // void sort() { int (*comp)( const T*, const T* ) = compare; qsort( baseAddr(), size(), sizeof(T), (int (*)(const void*,const void*)) comp ); } }; // ********************************************************************* // ********** D Y N A M I C A R R A Y *********** // ********************************************************************* /* * Commented out member functions are inherited from class UnArray. */ template< class T > class DyArray : public UnArray { private: // Actual allocated size of the array // int _allocSize; protected: // These functions and resize(...) redefine the storage management. // virtual int allocSize() const { return _allocSize; } // virtual void allocate( int size ); // virtual void reallocate( int newSize, int keepNum ); public: // constructor : create with 0 size // DyArray() { allocate(0); } /* * constructor : create with given size and extra space to grow. */ DyArray( int size, int moreSpace=0 ); // copy ctors // DyArray( const UnArray& a ); // DyArray( const DyArray& a ); /* * Copy constructor, with extra entries (size may be negative!) */ DyArray( const UnArray& a, int size ); /* * Assignment: * does not reallocate if space(rhs) >= size(lhs) */ DyArray& operator=( const UnArray& a ); // DyArray& operator=( const DyArray& a ); // Resize and over-allocate the array. // Array's usable size is newSize, and allocSize is newSize + extraSize // void resizeAndOverAllocate( int newSize, int extraSize ); // void resizeNoCopyAndOverAllocate( int newSize, int extraSize ); // comparison // Bool operator==( const DyArray &DA ) const { // the virtual stuff should kick in. // return UnArray::operator==( DA ); } }; #ifdef DEFINE_TEMPLATE #include #endif #endif