1 /** \file lvptrvec.h
2     \brief pointer vector template
3 
4     Implements vector of pointers.
5 
6     CoolReader Engine
7 
8     (c) Vadim Lopatin, 2000-2006
9     This source code is distributed under the terms of
10     GNU General Public License.
11 
12     See LICENSE file for details.
13 
14 */
15 
16 #ifndef __LVPTRVEC_H_INCLUDED__
17 #define __LVPTRVEC_H_INCLUDED__
18 
19 #include <stdlib.h>
20 #include "lvmemman.h"
21 
22 /** \brief template which implements vector of pointer
23 
24     Automatically deletes objects when vector items are destroyed.
25 */
26 template < class T, bool ownItems = true >
27 class LVPtrVector
28 {
29     T * * _list;
30     int _size;
31     int _count;
32     LVPtrVector & operator = (LVPtrVector&) {
33         // no assignment
34         return *this;
35     }
36 public:
37     /// default constructor
LVPtrVector()38     LVPtrVector() : _list(NULL), _size(0), _count(0) {}
39     /// retrieves item from specified position
40     T * operator [] ( int pos ) const { return _list[pos]; }
41     /// returns pointer array
get()42     T ** get() { return _list; }
43     /// retrieves item from specified position
get(int pos)44     T * get( int pos ) const { return _list[pos]; }
45     /// retrieves item reference from specified position
46     T * & operator [] ( int pos ) { return _list[pos]; }
47     /// ensures that size of vector is not less than specified value
reserve(int size)48     void reserve( int size )
49     {
50         if ( size > _size )
51         {
52             _list = cr_realloc( _list, size );
53             for (int i=_size; i<size; i++)
54                 _list[i] = NULL;
55             _size = size;
56         }
57     }
sort(int (comparator)(const T ** item1,const T ** item2))58     void sort(int (comparator)(const T ** item1, const T ** item2 ) ) {
59     	qsort(_list, _count, sizeof(T*), (int (*)(const void *, const void *))comparator);
60     }
61     /// sets item by index (extends vector if necessary)
set(int index,T * item)62     void set( int index, T * item )
63     {
64         reserve( index+1 );
65         while (length()<index)
66             add(NULL);
67         if ( ownItems && _list[index] )
68             delete _list[index];
69         _list[index] = item;
70         if (_count<=index)
71             _count = index + 1;
72     }
73     /// returns size of buffer
size()74     int size() const { return _size; }
75     /// returns number of items in vector
length()76     int length() const { return _count; }
77     /// returns true if there are no items in vector
empty()78     bool empty() const { return _count==0; }
79     /// clears all items
clear()80     void clear()
81     {
82         if (_list)
83         {
84             int cnt = _count;
85             _count = 0;
86             if ( ownItems ) {
87                 for (int i=cnt - 1; i>=0; --i)
88                     if (_list[i])
89                         delete _list[i];
90             }
91             free( _list );
92         }
93         _list = NULL;
94         _size = 0;
95         _count = 0;
96     }
97     /// removes several items from vector
erase(int pos,int count)98     void erase( int pos, int count )
99     {
100         if ( count<=0 )
101             return;
102         if ( pos<0 || pos+count > _count )
103             crFatalError();
104         int i;
105         for (i=0; i<count; i++)
106         {
107             if (_list[pos+i])
108             {
109                 if ( ownItems )
110                     delete _list[pos+i];
111                 _list[pos+i] = NULL;
112             }
113         }
114         for (i=pos+count; i<_count; i++)
115         {
116             _list[i-count] = _list[i];
117             _list[i] = NULL;
118         }
119         _count -= count;
120     }
121     /// removes item from vector by index
remove(int pos)122     T * remove( int pos )
123     {
124         if (pos < 0 || (unsigned)pos >= (unsigned)_count)
125             crFatalError();
126         int i;
127         T * item = _list[pos];
128         for ( i=pos; i<_count-1; i++ )
129         {
130             _list[i] = _list[i+1];
131             //_list[i+1] = NULL;
132         }
133         _count--;
134         return item;
135     }
136     /// returns vector index of specified pointer, -1 if not found
indexOf(T * p)137     int indexOf( T * p )
138     {
139         for ( int i=0; i<_count; i++ ) {
140             if ( _list[i] == p )
141                 return i;
142         }
143         return -1;
144     }
last()145     T * last()
146     {
147         if ( _count<=0 )
148             return NULL;
149         return _list[_count-1];
150     }
first()151     T * first()
152     {
153         if ( _count<=0 )
154             return NULL;
155         return _list[0];
156     }
157     /// removes item from vector by index
remove(T * p)158     T * remove( T * p )
159     {
160         int i;
161         int pos = indexOf( p );
162         if ( pos<0 )
163             return NULL;
164         T * item = _list[pos];
165         for ( i=pos; i<_count-1; i++ )
166         {
167             _list[i] = _list[i+1];
168         }
169         _count--;
170         return item;
171     }
172     /// adds new item to end of vector
add(T * item)173     void add( T * item ) { insert( -1, item ); }
174     /// inserts new item to specified position
insert(int pos,T * item)175     void insert( int pos, T * item )
176     {
177         if (pos<0 || pos>_count)
178             pos = _count;
179         if ( _count >= _size )
180             reserve( _count * 3 / 2  + 8 );
181         for (int i=_count; i>pos; --i)
182             _list[i] = _list[i-1];
183         _list[pos] = item;
184         _count++;
185     }
186     /// move item to specified position, other items will be shifted
move(int indexTo,int indexFrom)187     void move( int indexTo, int indexFrom )
188     {
189         if ( indexTo==indexFrom )
190             return;
191         T * p = _list[indexFrom];
192         if ( indexTo<indexFrom ) {
193             for ( int i=indexFrom; i>indexTo; i--)
194                 _list[i] = _list[i-1];
195         } else {
196             for ( int i=indexFrom; i<indexTo; i++)
197                 _list[i] = _list[i+1];
198         }
199         _list[ indexTo ] = p;
200     }
201     /// reverse items
reverse()202     void reverse()
203     {
204         if ( empty() )
205             return;
206         for ( int i=0; i < _count/2; i++ ) {
207             T * tmp = _list[i];
208             _list[i] = _list[_count-1 - i];
209             _list[_count-1 - i] = tmp;
210         }
211     }
212     /// copy constructor
LVPtrVector(const LVPtrVector & v)213     LVPtrVector( const LVPtrVector & v )
214         : _list(NULL), _size(0), _count(0)
215     {
216         if ( v._count>0 ) {
217             reserve( v._count );
218             for ( int i=0; i<v._count; i++ )
219                 add( new T(*v[i]) );
220         }
221     }
222     /// stack-like interface: pop top item from stack
pop()223     T * pop()
224     {
225         if ( empty() )
226             return NULL;
227         return remove( length() - 1 );
228     }
229     /// stack-like interface: pop top item from stack
popHead()230     T * popHead()
231     {
232         if ( empty() )
233             return NULL;
234         return remove( (int)0 );
235     }
236     /// stack-like interface: push item to stack
push(T * item)237     void push( T * item )
238     {
239         add( item );
240     }
241     /// stack-like interface: push item to stack
pushHead(T * item)242     void pushHead( T * item )
243     {
244         insert( 0, item );
245     }
246     /// stack-like interface: get top item w/o removing from stack
peek()247     T * peek()
248     {
249         if ( empty() )
250             return NULL;
251         return get( length() - 1 );
252     }
253     /// stack-like interface: get top item w/o removing from stack
peekHead()254     T * peekHead()
255     {
256         if ( empty() )
257             return NULL;
258         return get( 0 );
259     }
260     /// destructor
~LVPtrVector()261     ~LVPtrVector() { clear(); }
262 };
263 
264 template<class _Ty > class LVMatrix {
265 protected:
266     int numcols;
267     int numrows;
268     _Ty ** rows;
269 public:
270     LVMatrix<_Ty> () : numcols(0), numrows(0), rows(NULL) {}
Clear()271     void Clear() {
272         if (rows) {
273 			if (numrows && numcols) {
274 				for (int i=0; i<numrows; i++)
275 					free( rows[i] );
276 			}
277             free( rows );
278 		}
279         rows = NULL;
280         numrows = 0;
281         numcols = 0;
282     }
283     ~LVMatrix<_Ty> () {
284         Clear();
285     }
286 
287     _Ty * operator [] (int rowindex) { return rows[rowindex]; }
288 
SetSize(int nrows,int ncols,_Ty fill_elem)289     void SetSize( int nrows, int ncols, _Ty fill_elem ) {
290         if (!nrows || !ncols) {
291             Clear();
292             return;
293         }
294         if ( nrows<numrows ) {
295             for (int i=nrows; i<numrows; i++)
296                 free( rows[i] );
297             numrows = nrows;
298         } else if (nrows>numrows) {
299             rows = cr_realloc( rows, nrows );
300             for (int i=numrows; i<nrows; i++) {
301                 rows[i] = (_Ty*)malloc( sizeof(_Ty*) * ncols );
302                 for (int j=0; j<numcols; j++)
303                     rows[i][j]=fill_elem;
304             }
305         }
306         if (ncols>numcols) {
307             for (int i=0; i<numrows; i++) {
308                 rows[i] = cr_realloc( rows[i], ncols );
309                 for (int j=numcols; j<ncols; j++)
310                     rows[i][j]=fill_elem;
311             }
312             numcols = ncols;
313         }
314     }
315 };
316 
317 template <typename T1, typename T2> class LVPair
318 {
319     T1 _first;
320     T2 _second;
321 public:
LVPair(const T1 & first,const T2 & second)322     LVPair( const T1 & first, const T2 & second )
323     : _first(first), _second(second) {
324     }
LVPair(const LVPair & v)325     LVPair( const LVPair & v )
326     : _first(v._first), _second(v._second) {
327     }
328     LVPair & operator = ( const LVPair & v )
329     {
330         _first = v._first;
331         _second = v._second;
332         return *this;
333     }
first()334     T1 & first() { return _first; }
first()335     const T1 & first() const { return _first; }
second()336     T2 & second() { return _second; }
second()337     const T2 & second() const { return _second; }
~LVPair()338     ~LVPair() { }
339 };
340 
341 #endif
342