aboutsummaryrefslogtreecommitdiff
path: root/src/array.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2012-03-25 20:00:08 +0000
committerMike Buland <eichlan@xagasoft.com>2012-03-25 20:00:08 +0000
commit469bbcf0701e1eb8a6670c23145b0da87357e178 (patch)
treeb5b062a16e46a6c5d3410b4e574cd0cc09057211 /src/array.h
parentee1b79396076edc4e30aefb285fada03bb45e80d (diff)
downloadlibbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.tar.gz
libbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.tar.bz2
libbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.tar.xz
libbu++-469bbcf0701e1eb8a6670c23145b0da87357e178.zip
Code is all reorganized. We're about ready to release. I should write up a
little explenation of the arrangement.
Diffstat (limited to 'src/array.h')
-rw-r--r--src/array.h703
1 files changed, 0 insertions, 703 deletions
diff --git a/src/array.h b/src/array.h
deleted file mode 100644
index fcd800e..0000000
--- a/src/array.h
+++ /dev/null
@@ -1,703 +0,0 @@
1/*
2 * Copyright (C) 2007-2011 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_ARRAY_H
9#define BU_ARRAY_H
10
11#include <memory>
12#include "bu/exceptionbase.h"
13#include "bu/archivebase.h"
14#include "bu/sharedcore.h"
15
16namespace Bu
17{
18 subExceptionDecl( ArrayException )
19
20 template<typename value, int inc, typename valuealloc>
21 class Array;
22
23 /** @cond DEVEL */
24 template<typename value, int inc, typename valuealloc>
25 class ArrayCore
26 {
27 friend class Array<value, inc, valuealloc>;
28 friend class SharedCore<
29 Array<value, inc, valuealloc>,
30 ArrayCore<value, inc, valuealloc>
31 >;
32 private:
33 ArrayCore() :
34 pData( NULL ),
35 iSize( 0 ),
36 iCapacity( 0 )
37 { }
38
39 void setCapacity( int iNewLen )
40 {
41 //clear();
42 //iCapacity = iCapacity;
43 //pData = va.allocate( iCapacity );
44 if( iNewLen <= iCapacity ) return;
45 value *pNewData = va.allocate( iNewLen );
46 if( pData )
47 {
48 for( int j = 0; j < iSize; j++ )
49 {
50 va.construct( &pNewData[j], pData[j] );
51 va.destroy( &pData[j] );
52 }
53 va.deallocate( pData, iCapacity );
54 }
55 pData = pNewData;
56 iCapacity = iNewLen;
57 }
58
59 virtual ~ArrayCore()
60 {
61 clear();
62 }
63
64 void clear()
65 {
66 if( pData )
67 {
68 for( int j = 0; j < iSize; j++ )
69 {
70 va.destroy( &pData[j] );
71 }
72 va.deallocate( pData, iCapacity );
73 pData = NULL;
74 }
75 iSize = 0;
76 iCapacity = 0;
77 }
78
79 void erase( int iPos )
80 {
81 for( int j = iPos; j < iSize; j++ )
82 {
83 va.destroy( &pData[j] );
84 if( j == iSize-1 )
85 {
86 iSize--;
87 return;
88 }
89 va.construct( &pData[j], pData[j+1] );
90 }
91 }
92
93 void swapErase( int iPos )
94 {
95 if( iPos == iSize-1 )
96 {
97 erase( iPos );
98 return;
99 }
100 va.destroy( &pData[iPos] );
101 va.construct( &pData[iPos], pData[iSize-1] );
102 va.destroy( &pData[iSize-1] );
103 iSize--;
104 }
105
106 valuealloc va;
107 value *pData;
108 long iSize;
109 long iCapacity;
110 };
111 /** @endcond */
112
113 /**
114 * Array type container, just like a normal array only flexible and keeps
115 * track of your memory for you.
116 *
117 *@param value (typename) The type of data to store in your list
118 *@param valuealloc (typename) Memory Allocator for your value type
119 *@param linkalloc (typename) Memory Allocator for the list links.
120 *@ingroup Containers
121 */
122 template<typename value, int inc=10, typename valuealloc=std::allocator<value> >
123 class Array : public SharedCore<
124 Array<value, inc, valuealloc>,
125 ArrayCore<value, inc, valuealloc>
126 >
127 {
128 private:
129 typedef class Array<value, inc, valuealloc> MyType;
130 typedef class ArrayCore<value, inc, valuealloc> Core;
131
132 protected:
133 using SharedCore<MyType, Core>::core;
134 using SharedCore<MyType, Core>::_hardCopy;
135 using SharedCore<MyType, Core>::_resetCore;
136 using SharedCore<MyType, Core>::_allocateCore;
137
138 public:
139 struct const_iterator;
140 struct iterator;
141
142 Array()
143 {
144 }
145
146 Array( const MyType &src ) :
147 SharedCore<MyType, Core >( src )
148 {
149 }
150
151 Array( long iSetCap )
152 {
153 setCapacity( iSetCap );
154 }
155
156 ~Array()
157 {
158 }
159
160 bool operator==( const MyType &src ) const
161 {
162 if( core == src.core )
163 return true;
164 if( core->iSize != src.core->iSize )
165 return false;
166
167 for( int j = 0; j < core->iSize; j++ )
168 {
169 if( core->pData[j] != src.core->pData[j] )
170 return false;
171 }
172 return true;
173 }
174
175 bool operator!=( const MyType &src ) const
176 {
177 return !(*this == src);
178 }
179
180 /**
181 * Clear the array.
182 */
183 void clear()
184 {
185 _resetCore();
186 }
187
188 MyType &append( const value &rVal )
189 {
190 _hardCopy();
191 if( core->iSize == core->iCapacity )
192 {
193 core->setCapacity( core->iCapacity + inc );
194 }
195
196 core->va.construct( &core->pData[core->iSize++], rVal );
197
198 return *this;
199 }
200
201 MyType &append( const MyType &rVal )
202 {
203 _hardCopy();
204
205 if( core->iSize + rVal.core->iSize > core->iCapacity )
206 {
207 core->setCapacity( core->iSize + rVal.core->iSize + inc );
208 }
209
210 for( int j = 0; j < rVal.core->iSize; j++ )
211 {
212 core->va.construct(
213 &core->pData[core->iSize++],
214 rVal.core->pData[j]
215 );
216 }
217
218 return *this;
219 }
220
221 //operator
222 value &operator[]( long iIndex )
223 {
224 _hardCopy();
225 if( iIndex < 0 || iIndex >= core->iSize )
226 throw ArrayException(
227 "Index %d out of range 0:%d", iIndex, core->iSize );
228
229 return core->pData[iIndex];
230 }
231
232 const value &operator[]( long iIndex ) const
233 {
234 if( iIndex < 0 || iIndex >= core->iSize )
235 throw ArrayException(
236 "Index %d out of range 0:%d", iIndex, core->iSize );
237
238 return core->pData[iIndex];
239 }
240
241 value &get( long iIndex )
242 {
243 _hardCopy();
244 if( iIndex < 0 || iIndex >= core->iSize )
245 throw ArrayException(
246 "Index %d out of range 0:%d", iIndex, core->iSize );
247
248 return core->pData[iIndex];
249 }
250
251 const value &get( long iIndex ) const
252 {
253 if( iIndex < 0 || iIndex >= core->iSize )
254 throw ArrayException(
255 "Index %d out of range 0:%d", iIndex, core->iSize );
256
257 return core->pData[iIndex];
258 }
259
260 value &first()
261 {
262 _hardCopy();
263 return core->pData[0];
264 }
265
266 const value &first() const
267 {
268 return core->pData[0];
269 }
270
271 value &last()
272 {
273 _hardCopy();
274 return core->pData[core->iSize-1];
275 }
276
277 const value &last() const
278 {
279 return core->pData[core->iSize-1];
280 }
281
282 /**
283 * Get the current size of the array.
284 *@returns The current size of the array.
285 */
286 long getSize() const
287 {
288 return core->iSize;
289 }
290
291 /**
292 * Get the capacity of the array. This number will grow as data is
293 * added, and is mainly for the curious, it doesn't really determine
294 * much for the end user.
295 *@returns The current capacity of the array.
296 */
297 long getCapacity() const
298 {
299 return core->iCapacity;
300 }
301
302 /**
303 * Change the capacity of the array, very useful if you know you'll be
304 * adding a large amount of already counted items to the array, makes
305 * the appending much faster afterwords.
306 *@param iNewLen The new capacity of the array.
307 *@todo Set this up so it can reduce the size of the array as well as
308 * make it bigger.
309 */
310 void setCapacity( long iNewLen )
311 {
312 _hardCopy();
313 core->setCapacity( iNewLen );
314 }
315
316 typedef struct iterator
317 {
318 friend class Array<value, inc, valuealloc>;
319 private:
320 iterator( MyType &src, long iPos=0 ) :
321 src( src ),
322 iPos( iPos )
323 {
324 if( this->iPos >= src.getSize() )
325 this->iPos = -1;
326 }
327
328 MyType &src;
329 long iPos;
330
331 public:
332 iterator operator++( int )
333 {
334 if( iPos < 0 )
335 throw ArrayException(
336 "Cannot increment iterator past end of array.");
337 iPos++;
338 if( iPos >= src.getSize() )
339 iPos = -1;
340 return *this;
341 }
342
343 iterator operator++()
344 {
345 if( iPos >= 0 )
346 iPos++;
347 if( iPos >= src.getSize() )
348 iPos = -1;
349 return *this;
350 }
351
352 iterator operator+( int iAmnt )
353 {
354 if( iPos < 0 )
355 throw ArrayException(
356 "Cannot increment iterator past end of array.");
357 iPos += iAmnt;
358 if( iPos >= src.getSize() )
359 iPos = -1;
360 return *this;
361 }
362
363 iterator operator--( int )
364 {
365 if( iPos < 0 )
366 throw ArrayException(
367 "Cannot increment iterator past end of array.");
368 iPos--;
369 if( iPos < 0 )
370 iPos = -1;
371 return *this;
372 }
373
374 iterator operator--()
375 {
376 if( iPos < src.getSize() )
377 iPos--;
378 if( iPos <= 0 )
379 iPos = -1;
380 return *this;
381 }
382
383 iterator operator-( int iAmnt )
384 {
385 if( iPos < src.getSize() )
386 iPos -= iAmnt;
387 if( iPos <= 0 )
388 iPos = -1;
389 return *this;
390 }
391
392 bool operator==( const iterator &oth ) const
393 {
394 return iPos == oth.iPos;
395 }
396
397 bool operator!=( const iterator &oth ) const
398 {
399 return iPos != oth.iPos;
400 }
401
402 iterator operator=( const iterator &oth )
403 {
404 if( &src != &oth.src )
405 throw ArrayException(
406 "Cannot mix iterators from different array objects.");
407 iPos = oth.iPos;
408 }
409
410 value &operator*()
411 {
412 if( iPos < 0 )
413 throw ArrayException(
414 "Cannot dereference finished iterator.");
415 return src[iPos];
416 }
417
418 long getIndex() const
419 {
420 return iPos;
421 }
422
423 operator bool() const
424 {
425 return iPos >= 0;
426 }
427
428 bool isValid() const
429 {
430 return iPos >= 0;
431 }
432 } iterator;
433
434 typedef struct const_iterator
435 {
436 friend class Array<value, inc, valuealloc>;
437 private:
438 const_iterator( const MyType &src, long iPos=0 ) :
439 src( src ),
440 iPos( iPos )
441 {
442 if( this->iPos >= src.getSize() )
443 this->iPos = -1;
444 }
445
446 const MyType &src;
447 long iPos;
448
449 public:
450 const_iterator( iterator &rSrc ) :
451 src( rSrc.src ),
452 iPos( rSrc.iPos )
453 {
454 }
455 const_iterator operator++( int )
456 {
457 if( iPos < 0 )
458 throw ArrayException(
459 "Cannot increment iterator past end of array.");
460 iPos++;
461 if( iPos >= src.getSize() )
462 iPos = -1;
463 return *this;
464 }
465
466 const_iterator operator++()
467 {
468 if( iPos >= 0 )
469 iPos++;
470 if( iPos >= src.getSize() )
471 iPos = -1;
472 return *this;
473 }
474
475 const_iterator operator--( int )
476 {
477 if( iPos < 0 )
478 throw ArrayException(
479 "Cannot increment iterator past end of array.");
480 iPos--;
481 if( iPos < 0 )
482 iPos = -1;
483 return *this;
484 }
485
486 const_iterator operator--()
487 {
488 if( iPos < src.getSize() )
489 iPos--;
490 if( iPos <= 0 )
491 iPos = -1;
492 return *this;
493 }
494
495 bool operator==( const const_iterator &oth ) const
496 {
497 return iPos == oth.iPos;
498 }
499
500 bool operator!=( const const_iterator &oth ) const
501 {
502 return iPos != oth.iPos;
503 }
504
505 const_iterator operator=( const const_iterator &oth )
506 {
507 if( &src != &oth.src )
508 throw ArrayException(
509 "Cannot mix iterators from different array objects.");
510 iPos = oth.iPos;
511 }
512
513 const value &operator*() const
514 {
515 if( iPos < 0 )
516 throw ArrayException(
517 "Cannot dereference finished iterator.");
518 return src[iPos];
519 }
520
521 long getIndex() const
522 {
523 return iPos;
524 }
525
526 operator bool() const
527 {
528 return iPos >= 0;
529 }
530
531 bool isValid() const
532 {
533 return iPos >= 0;
534 }
535 } const_iterator;
536
537 iterator begin()
538 {
539 return iterator( *this );
540 }
541
542 const_iterator begin() const
543 {
544 return const_iterator( *this );
545 }
546
547 iterator end()
548 {
549 return iterator( *this, -1 );
550 }
551
552 const_iterator end() const
553 {
554 return const_iterator( *this, -1 );
555 }
556
557 MyType &insert( iterator i, const value &rVal )
558 {
559 if( i.iPos == -1 )
560 {
561 append( rVal );
562 return *this;
563 }
564
565 _hardCopy();
566 if( core->iSize == core->iCapacity )
567 {
568 core->setCapacity( core->iCapacity + inc );
569 }
570 core->iSize++;
571
572 core->va.construct(
573 &core->pData[core->iSize-1],
574 core->pData[core->iSize-2]
575 );
576 for( int iPos = core->iSize-2; iPos > i.iPos; iPos-- )
577 {
578 core->va.destroy( &core->pData[iPos] );
579 core->va.construct( &core->pData[iPos], core->pData[iPos-1] );
580 }
581 core->va.destroy( &core->pData[i.iPos] );
582 core->va.construct( &core->pData[i.iPos], rVal );
583
584 return *this;
585 }
586
587 /**
588 * If order is important, use this. It will delete the suggested item
589 * and move the rest of the data up a spot. This is a time O(n)
590 * operation. If the order isn't important, check swapErase
591 */
592 void erase( iterator i )
593 {
594 _hardCopy();
595 core->erase( i.iPos );
596 }
597
598 void erase( const value &v )
599 {
600 _hardCopy();
601 for( int j = 0; j < core->iSize; j++ )
602 {
603 if( core->pData[j] == v )
604 {
605 core->erase( j );
606 return;
607 }
608 }
609 }
610
611 void eraseLast()
612 {
613 _hardCopy();
614 core->erase( core->iSize-1 );
615 }
616
617 void eraseFirst()
618 {
619 _hardCopy();
620 core->erase( 0 );
621 }
622
623 /**
624 * In order to make swapErase faster, what it does is swap the given
625 * item in the array with the last item, then make the array shorter
626 * by one. It changes the order of the elements in the array, so it
627 * should be used carefully, but it is time O(1) instead of O(n) like
628 * erase.
629 */
630 void swapErase( iterator i )
631 {
632 _hardCopy();
633 core->swapErase( i.iPos );
634 }
635
636 protected:
637 virtual Core *_copyCore( Core *src )
638 {
639 Core *pRet = _allocateCore();
640 pRet->setCapacity( src->iCapacity );
641 pRet->iSize = src->iSize;
642 for( int j = 0; j < src->iSize; j++ )
643 {
644 pRet->va.construct( &pRet->pData[j], src->pData[j] );
645 }
646 return pRet;
647 }
648
649 private:
650 };
651
652 class Formatter;
653 Formatter &operator<<( Formatter &rOut, char *sStr );
654 Formatter &operator<<( Formatter &rOut, signed char c );
655 template<typename value>
656 Formatter &operator<<( Formatter &f, const Bu::Array<value> &a )
657 {
658 f << '[';
659 for( typename Bu::Array<value>::const_iterator i = a.begin(); i; i++ )
660 {
661 if( i != a.begin() )
662 f << ", ";
663 f << *i;
664 }
665 f << ']';
666
667 return f;
668 }
669
670 template<typename value, int inc, typename valuealloc>
671 ArchiveBase &operator<<( ArchiveBase &ar,
672 const Array<value, inc, valuealloc> &h )
673 {
674 ar << h.getSize();
675 for( typename Array<value, inc, valuealloc>::const_iterator i =
676 h.begin(); i != h.end(); i++ )
677 {
678 ar << (*i);
679 }
680
681 return ar;
682 }
683
684 template<typename value, int inc, typename valuealloc>
685 ArchiveBase &operator>>(ArchiveBase &ar, Array<value, inc, valuealloc> &h )
686 {
687 h.clear();
688 long nSize;
689 ar >> nSize;
690
691 h.setCapacity( nSize );
692 for( long j = 0; j < nSize; j++ )
693 {
694 value v;
695 ar >> v;
696 h.append( v );
697 }
698 return ar;
699 }
700
701}
702
703#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 10:44:03 +0000