--- /dev/null
+/*\r
+Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
+For a list of contributors, see the accompanying CONTRIBUTORS file.\r
+\r
+This file is part of GtkRadiant.\r
+\r
+GtkRadiant is free software; you can redistribute it and/or modify\r
+it under the terms of the GNU General Public License as published by\r
+the Free Software Foundation; either version 2 of the License, or\r
+(at your option) any later version.\r
+\r
+GtkRadiant is distributed in the hope that it will be useful,\r
+but WITHOUT ANY WARRANTY; without even the implied warranty of\r
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
+GNU General Public License for more details.\r
+\r
+You should have received a copy of the GNU General Public License\r
+along with GtkRadiant; if not, write to the Free Software\r
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
+*/\r
+\r
+#ifndef __UTIL_LIST_H__\r
+#define __UTIL_LIST_H__\r
+\r
+#include <stdlib.h>\r
+#include <assert.h>\r
+\r
+template< class type >\r
+class idList {\r
+private:\r
+ int m_num;\r
+ int m_size;\r
+ int m_granularity;\r
+ type *m_list;\r
+\r
+public:\r
+ idList( int granularity = 16 );\r
+ ~idList<type>();\r
+ void Clear( void );\r
+ int Num( void );\r
+ void SetNum( int num );\r
+ void SetGranularity( int granularity );\r
+ void Condense( void );\r
+ int Size( void );\r
+ void Resize( int size );\r
+ type operator[]( int index ) const;\r
+ type &operator[]( int index );\r
+ int Append( type const & obj );\r
+ int AddUnique( type const & obj );\r
+ type *Find( type const & obj, int *index = NULL );\r
+ bool RemoveIndex( int index );\r
+ bool Remove( type const & obj );\r
+ typedef int cmp_t(const void *, const void *);\r
+ void Sort( cmp_t *compare );\r
+};\r
+\r
+/*\r
+================\r
+idList<type>::idList( int )\r
+================\r
+*/\r
+template< class type >\r
+inline idList<type>::idList( int granularity ) {\r
+ assert( granularity > 0 );\r
+\r
+ m_list = NULL;\r
+ m_granularity = granularity;\r
+ Clear();\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::~idList<type>\r
+================\r
+*/\r
+template< class type >\r
+inline idList<type>::~idList() {\r
+ Clear();\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Clear\r
+================\r
+*/\r
+template< class type >\r
+inline void idList<type>::Clear( void ) {\r
+ if ( m_list ) {\r
+ delete[] m_list;\r
+ }\r
+\r
+ m_list = NULL;\r
+ m_num = 0;\r
+ m_size = 0;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Num\r
+================\r
+*/\r
+template< class type >\r
+inline int idList<type>::Num( void ) {\r
+ return m_num;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::SetNum\r
+================\r
+*/\r
+template< class type >\r
+inline void idList<type>::SetNum( int num ) {\r
+ assert( num >= 0 );\r
+ if ( num > m_size ) {\r
+ // resize it up to the closest level of granularity\r
+ Resize( ( ( num + m_granularity - 1 ) / m_granularity ) * m_granularity );\r
+ }\r
+ m_num = num;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::SetGranularity\r
+================\r
+*/\r
+template< class type >\r
+inline void idList<type>::SetGranularity( int granularity ) {\r
+ int newsize;\r
+\r
+ assert( granularity > 0 );\r
+ m_granularity = granularity;\r
+\r
+ if ( m_list ) {\r
+ // resize it to the closest level of granularity\r
+ newsize = ( ( m_num + m_granularity - 1 ) / m_granularity ) * m_granularity;\r
+ if ( newsize != m_size ) {\r
+ Resize( newsize );\r
+ }\r
+ }\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Condense\r
+\r
+Resizes the array to exactly the number of elements it contains\r
+================\r
+*/\r
+template< class type >\r
+inline void idList<type>::Condense( void ) {\r
+ if ( m_list ) {\r
+ if ( m_num ) {\r
+ Resize( m_num );\r
+ } else {\r
+ Clear();\r
+ }\r
+ }\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Size\r
+================\r
+*/\r
+template< class type >\r
+inline int idList<type>::Size( void ) {\r
+ return m_size;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Resize\r
+================\r
+*/\r
+template< class type >\r
+inline void idList<type>::Resize( int size ) {\r
+ type *temp;\r
+ int i;\r
+\r
+ assert( size > 0 );\r
+\r
+ if ( size <= 0 ) {\r
+ Clear();\r
+ return;\r
+ }\r
+\r
+ temp = m_list;\r
+ m_size = size;\r
+ if ( m_size < m_num ) {\r
+ m_num = m_size;\r
+ }\r
+\r
+ m_list = new type[ m_size ];\r
+ for( i = 0; i < m_num; i++ ) {\r
+ m_list[ i ] = temp[ i ];\r
+ }\r
+\r
+ if ( temp ) {\r
+ delete[] temp;\r
+ }\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::operator[] const\r
+================\r
+*/\r
+template< class type >\r
+inline type idList<type>::operator[]( int index ) const {\r
+ assert( index >= 0 );\r
+ assert( index < m_num );\r
+\r
+ return m_list[ index ];\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::operator[]\r
+================\r
+*/\r
+template< class type >\r
+inline type &idList<type>::operator[]( int index ) {\r
+ assert( index >= 0 );\r
+ assert( index < m_num );\r
+\r
+ return m_list[ index ];\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Append\r
+================\r
+*/\r
+template< class type >\r
+inline int idList<type>::Append( type const & obj ) {\r
+ if ( !m_list ) {\r
+ Resize( m_granularity );\r
+ }\r
+\r
+ if ( m_num == m_size ) {\r
+ Resize( m_size + m_granularity );\r
+ }\r
+\r
+ m_list[ m_num ] = obj;\r
+ m_num++;\r
+\r
+ return m_num - 1;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::AddUnique\r
+================\r
+*/\r
+template< class type >\r
+inline int idList<type>::AddUnique( type const & obj ) {\r
+ int index;\r
+\r
+ if ( !Find( obj, &index ) ) {\r
+ index = Append( obj );\r
+ }\r
+\r
+ return index;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Find\r
+================\r
+*/\r
+template< class type >\r
+inline type *idList<type>::Find( type const & obj, int *index ) {\r
+ int i;\r
+\r
+ for( i = 0; i < m_num; i++ ) {\r
+ if ( m_list[ i ] == obj ) {\r
+ if ( index ) {\r
+ *index = i;\r
+ }\r
+ return &m_list[ i ];\r
+ }\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::RemoveIndex\r
+================\r
+*/\r
+template< class type >\r
+inline bool idList<type>::RemoveIndex( int index ) {\r
+ int i;\r
+\r
+ if ( !m_list || !m_num ) {\r
+ return false;\r
+ }\r
+\r
+ assert( index >= 0 );\r
+ assert( index < m_num );\r
+\r
+ if ( ( index < 0 ) || ( index >= m_num ) ) {\r
+ return false;\r
+ }\r
+\r
+ m_num--;\r
+ for( i = index; i < m_num; i++ ) {\r
+ m_list[ i ] = m_list[ i + 1 ];\r
+ }\r
+\r
+ return true;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Remove\r
+================\r
+*/\r
+template< class type >\r
+inline bool idList<type>::Remove( type const & obj ) {\r
+ int index;\r
+\r
+ if ( Find( obj, &index ) ) {\r
+ return RemoveIndex( index );\r
+ }\r
+ \r
+ return false;\r
+}\r
+\r
+/*\r
+================\r
+idList<type>::Sort\r
+================\r
+*/\r
+template< class type >\r
+inline void idList<type>::Sort( cmp_t *compare ) {\r
+ if ( !m_list ) {\r
+ return;\r
+ }\r
+\r
+ qsort( ( void * )m_list, ( size_t )m_num, sizeof( type ), compare );\r
+}\r
+\r
+#endif /* !__UTIL_LIST_H__ */\r