mudgangster

Tiny, scriptable MUD client
Log | Files | Refs | README

array.h (2135B)


      1 #pragma once
      2 
      3 #include "common.h"
      4 
      5 template< typename T >
      6 class DynamicArray {
      7 	size_t n;
      8 	size_t capacity;
      9 	T * elems;
     10 
     11 public:
     12 	NONCOPYABLE( DynamicArray );
     13 
     14 	DynamicArray( size_t initial_capacity = 0 ) {
     15 		capacity = initial_capacity;
     16 		elems = capacity == 0 ? NULL : alloc_many< T >( capacity );
     17 		clear();
     18 	}
     19 
     20 	~DynamicArray() {
     21 		free( elems );
     22 	}
     23 
     24 	size_t add( const T & x ) {
     25 		size_t idx = extend( 1 );
     26 		elems[ idx ] = x;
     27 		return idx;
     28 	}
     29 
     30 	void insert( const T & x, size_t pos ) {
     31 		ASSERT( pos <= n );
     32 
     33 		extend( 1 );
     34 		memmove( elems + pos + 1, elems + pos, ( n - pos - 1 ) * sizeof( T ) );
     35 		elems[ pos ] = x;
     36 	}
     37 
     38 	void from_span( Span< const T > s ) {
     39 		resize( s.n );
     40 		memcpy( elems, s.ptr, s.num_bytes() );
     41 	}
     42 
     43 	bool remove( size_t pos ) {
     44 		if( n == 0 || pos >= n )
     45 			return false;
     46 
     47 		resize( n - 1 );
     48 		memmove( elems + pos, elems + pos + 1, ( n - pos ) * sizeof( T ) );
     49 
     50 		return true;
     51 	}
     52 
     53 	void clear() {
     54 		n = 0;
     55 	}
     56 
     57 	void resize( size_t new_size ) {
     58 		if( new_size < n ) {
     59 			n = new_size;
     60 			return;
     61 		}
     62 
     63 		if( new_size <= capacity ) {
     64 			n = new_size;
     65 			return;
     66 		}
     67 
     68 		size_t new_capacity = max( size_t( 64 ), capacity );
     69 		while( new_capacity < new_size )
     70 			new_capacity *= 2;
     71 
     72 		elems = realloc_many< T >( elems, new_capacity );
     73 		capacity = new_capacity;
     74 		n = new_size;
     75 	}
     76 
     77 	size_t extend( size_t by ) {
     78 		size_t old_size = n;
     79 		resize( n + by );
     80 		return old_size;
     81 	}
     82 
     83 	T & operator[]( size_t i ) {
     84 		ASSERT( i < n );
     85 		return elems[ i ];
     86 	}
     87 
     88 	const T & operator[]( size_t i ) const {
     89 		ASSERT( i < n );
     90 		return elems[ i ];
     91 	}
     92 
     93 	T & top() {
     94 		ASSERT( n > 0 );
     95 		return elems[ n - 1 ];
     96 	}
     97 
     98 	const T & top() const {
     99 		ASSERT( n > 0 );
    100 		return elems[ n - 1 ];
    101 	}
    102 
    103 	T * ptr() { return elems; }
    104 	const T * ptr() const { return elems; }
    105 	size_t size() const { return n; }
    106 	size_t num_bytes() const { return sizeof( T ) * n; }
    107 
    108 	T * begin() { return elems; }
    109 	T * end() { return elems + n; }
    110 	const T * begin() const { return elems; }
    111 	const T * end() const { return elems + n; }
    112 
    113 	Span< T > span() { return Span< T >( elems, n ); }
    114 	Span< const T > span() const { return Span< const T >( elems, n ); }
    115 };