00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151 #ifndef INC_MI32_SIMPLEAR_H
00152 #define INC_MI32_SIMPLEAR_H
00153
00154 #ifndef INC_MI32_MIODEFNS_H
00155 #include <mi32/miodefns.h>
00156 #endif
00157
00158 #ifndef INC_MI32_STDANSIC_H
00159 #include <mi32/stdansic.h>
00160 #endif
00161
00162 #ifndef INC_MI32_MEMBUF_H
00163 #include <mi32/membuf.h>
00164 #endif
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182 template <class _CT> class SIMPLE_ARRAY {
00183 public:
00184
00185
00186 SIMPLE_ARRAY (
00187 ):
00188 m_items(0),
00189 m_numitems(0),
00190 m_numalloc(0),
00191 m_spare(0)
00192 { }
00193
00194
00195 SIMPLE_ARRAY (
00196 const SIMPLE_ARRAY<_CT>& rhs
00197 ) {
00198 MmAllocExc((void**)&m_items,rhs.m_numalloc*sizeof(_CT));
00199 m_numalloc = rhs.m_numalloc;
00200 memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
00201 m_numitems = rhs.m_numitems;
00202 m_spare = rhs.m_spare;
00203 }
00204
00205
00206 ~SIMPLE_ARRAY (
00207 ) {
00208 if (m_items != 0) free(m_items);
00209 }
00210
00211
00212 SIMPLE_ARRAY<_CT>& operator= (
00213 const SIMPLE_ARRAY<_CT>& rhs
00214 ) {
00215 if (this != &rhs) {
00216 if (m_numalloc < rhs.m_numalloc) {
00217
00218 MmFree(m_items);
00219 MmAllocExc((void**)&m_items,rhs.m_numalloc*sizeof(_CT));
00220 m_numalloc = rhs.m_numalloc;
00221 }
00222 memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
00223 m_numitems = rhs.m_numitems;
00224 }
00225 return (*this);
00226 }
00227
00228
00229 bool operator== (
00230 const SIMPLE_ARRAY<_CT>& rhs
00231 ) const {
00232 if (m_numitems != rhs.m_numitems) return (false);
00233 if (m_numitems == 0) return (true);
00234 return (memcmp(m_items,rhs.m_items,m_numitems*sizeof(_CT)) == 0);
00235 }
00236
00237
00238 bool operator!= (
00239 const SIMPLE_ARRAY<_CT>& rhs
00240 ) const {
00241 return (!operator==(rhs));
00242 }
00243
00244
00245 operator const _CT*(
00246 ) const {
00247 return (m_items);
00248 }
00249
00250
00251 operator _CT*(
00252 ) {
00253 return (m_items);
00254 }
00255
00256
00257
00258
00259 const _CT& operator[] (
00260 int index
00261 ) const {
00262 return (m_items[index]);
00263 }
00264
00265
00266
00267
00268 _CT& operator[] (
00269 int index
00270 ) {
00271 return (m_items[index]);
00272 }
00273
00274 #ifndef GENERATING_DOXYGEN_OUTPUT
00275 #if defined(MAC_NATIVE) || defined(SUN64)
00276
00277
00278
00279
00280
00281 const _CT& operator[] (
00282 long index
00283 ) const {
00284 return (m_items[index]);
00285 }
00286
00287
00288
00289
00290 _CT& operator[] (
00291 long index
00292 ) {
00293 return (m_items[index]);
00294 }
00295 #endif
00296 #endif
00297
00298
00299 ERRVALUE Append (
00300 const _CT& item
00301 ) {
00302 if (m_numitems >= m_numalloc) {
00303 int err;
00304 if ((err = Reserve(MAX(16,2*m_numitems))) < 0) return (err);
00305 }
00306 m_items[m_numitems++] = item;
00307 return (0);
00308 }
00309
00310
00311 ERRVALUE Append (
00312 const _CT *items,
00313 int numitems
00314 ) {
00315 int err;
00316 if ((err = Reserve(m_numitems+numitems)) < 0) return (err);
00317 memcpy(m_items+m_numitems,items,numitems*sizeof(_CT));
00318 m_numitems += numitems;
00319 return (0);
00320 }
00321
00322
00323 ERRVALUE Append (
00324 const SIMPLE_ARRAY<_CT>& rhs
00325 ) {
00326 int err;
00327 if ((err = Reserve(m_numitems+rhs.m_numitems)) < 0) return (err);
00328 memcpy(m_items+m_numitems,rhs.m_items,rhs.m_numitems*sizeof(_CT));
00329 m_numitems += rhs.m_numitems;
00330 return (0);
00331 }
00332
00333
00334
00335 void AppendExc (
00336 const _CT& item
00337 ) {
00338 if (m_numitems >= m_numalloc) {
00339 ReserveExc(MAX(16,2*m_numitems));
00340 }
00341 m_items[m_numitems++] = item;
00342 return;
00343 }
00344
00345
00346
00347 void AppendExc (
00348 const _CT *items,
00349 int numitems
00350 ) {
00351 ReserveExc(m_numitems+numitems);
00352 memcpy(m_items+m_numitems,items,numitems*sizeof(_CT));
00353 m_numitems += numitems;
00354 return;
00355 }
00356
00357
00358
00359 void AppendExc (
00360 const SIMPLE_ARRAY<_CT>& rhs
00361 ) {
00362 ReserveExc(m_numitems+rhs.m_numitems);
00363 memcpy(m_items+m_numitems,rhs.m_items,rhs.m_numitems*sizeof(_CT));
00364 m_numitems += rhs.m_numitems;
00365 return;
00366 }
00367
00368
00369 ERRVALUE AppendUnique (
00370 const _CT& item
00371 ) {
00372 INT32 j;
00373 for (j = 0;(j < m_numitems);++j) {
00374 if (m_items[j] == item) break;
00375 }
00376 return ((j == m_numitems) ? Append(item) : 0);
00377 }
00378
00379
00380
00381 void AppendUniqueExc (
00382 const _CT& item
00383 ) {
00384 INT32 j;
00385 for (j = 0;(j < m_numitems);++j) {
00386 if (m_items[j] == item) break;
00387 }
00388 if (j == m_numitems) AppendExc(item);
00389 return;
00390 }
00391
00392
00393
00394 ERRVALUE Assign (
00395 const _CT *items,
00396 int numitems
00397 ) {
00398 int err;
00399 if ((err = Reserve(numitems)) < 0) return (err);
00400 memcpy(m_items,items,numitems*sizeof(_CT));
00401 m_numitems = numitems;
00402 return (0);
00403 }
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413 void Attach (
00414 _CT *& items,
00415 int numitems
00416 ) {
00417 Free();
00418 m_items = items;
00419 m_numitems = m_numalloc = numitems;
00420 items = 0;
00421 return;
00422 }
00423
00424
00425
00426 void Clear (
00427 ) {
00428 m_numitems = 0;
00429 return;
00430 }
00431
00432
00433 void ClearItems (
00434 int start = 0,
00435 int end = -1
00436 ) {
00437 if (end < start) end = m_numitems - 1;
00438 if (end >= start) {
00439 memset(m_items + start, 0, (end - start + 1) * sizeof(_CT));
00440 }
00441 return;
00442 }
00443
00444
00445
00446
00447 ERRVALUE Copy (
00448 const SIMPLE_ARRAY<_CT>& rhs
00449 ) {
00450 if (this != &rhs) {
00451 if (m_numalloc < rhs.m_numalloc) {
00452
00453 MmFree(m_items);
00454 ERRVALUE err = MmAlloc((void**)&m_items,rhs.m_numalloc*sizeof(_CT));
00455 if (err < 0) return (err);
00456 m_numalloc = rhs.m_numalloc;
00457 }
00458 memcpy(m_items,rhs.m_items,rhs.m_numitems*sizeof(_CT));
00459 m_numitems = rhs.m_numitems;
00460 }
00461 return (0);
00462 }
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473 _CT* Detach (
00474 ) {
00475 _CT* ret = m_items;
00476 m_numalloc = m_numitems = 0;
00477 m_items = 0;
00478 return (ret);
00479 }
00480
00481
00482 void Free (
00483 ) {
00484 m_numalloc = m_numitems = 0;
00485 MmFree(m_items);
00486 return;
00487 }
00488
00489
00490 const _CT& GetItem (
00491 int index
00492 ) const { return (m_items[index]); }
00493
00494
00495
00496 const _CT& GetLast (
00497 ) const { return (m_items[m_numitems-1]); }
00498
00499
00500 int GetMaxItems (
00501 ) const { return (m_numalloc); }
00502
00503
00504 int GetNumItems (
00505 ) const { return (m_numitems); }
00506
00507
00508 int GetSizeInBytes (
00509 ) const { return (m_numitems*sizeof(_CT)); }
00510
00511
00512
00513
00514 bool HasItem (
00515 const _CT& item
00516 ) const {
00517 for (INT32 i = 0;(i < m_numitems);++i) {
00518 if (m_items[i] == item) return (true);
00519 }
00520 return (false);
00521 }
00522
00523
00524 void InsertItems (
00525 int start,
00526 int num = 1
00527 ) {
00528 ReserveExc(m_numitems+num);
00529 memmove(&m_items[start + num], &m_items[start], (m_numitems - start) * sizeof(_CT));
00530 m_numitems += num;
00531 return;
00532 }
00533
00534
00535 bool IsEmpty (
00536 ) const { return (GetNumItems() == 0); }
00537
00538
00539
00540
00541
00542 template<class _Pr1>
00543 INT32 Locate (
00544 const _CT& item,
00545 _Pr1 _Pr
00546 ) const {
00547 if (m_numitems == 0) return (0);
00548 INT32 l = 0, r = m_numitems-1, q;
00549 do {
00550 q = (l+r)/2;
00551 int test = _Pr(item, m_items[q]);
00552 if (test == 0) return (q);
00553 if (test < 0) {
00554 r = q - 1;
00555 q = r;
00556 }
00557 else {
00558 l = q + 1;
00559 q = l;
00560 }
00561 } while (l <= r);
00562 return (q);
00563 }
00564
00565
00566 void RemoveDuplicates (
00567 ) {
00568 for (INT32 i = 0;(i < m_numitems);++i) {
00569 for (INT32 k = i+1;(k < m_numitems);++k) {
00570 if (m_items[i] == m_items[k]) {
00571 m_items[k] = m_items[m_numitems-1];
00572 m_numitems --;
00573 k --;
00574 }
00575 }
00576 }
00577 return;
00578 }
00579
00580
00581 void RemoveFast (
00582 INT32 item
00583 ) {
00584 if (item >= 0 && item < m_numitems) {
00585 m_numitems --;
00586 m_items[item] = m_items[m_numitems];
00587 }
00588 return;
00589 }
00590
00591
00592
00593 void RemoveItem (
00594 INT32 item
00595 ) {
00596 if (item < m_numitems && item >= 0) {
00597 --m_numitems;
00598 if (item < m_numitems) { memmove(&m_items[item], &m_items[item+1], (m_numitems - item) * sizeof(_CT)); }
00599 }
00600 return;
00601 }
00602
00603
00604 void RemoveLast (
00605 INT32 count = 1
00606 ) {
00607 if (count > m_numitems)
00608 m_numitems = 0;
00609 else
00610 m_numitems -= count;
00611 return;
00612 }
00613
00614
00615
00616
00617 bool RemoveMatchingItems (
00618 const _CT& item
00619 ) {
00620 INT32 i, num;
00621 for (num = i = 0;(i < m_numitems); ++i) {
00622 if (m_items[i] != item) {
00623 if (num < i) m_items[num] = m_items[i];
00624 num ++;
00625 }
00626 }
00627 bool retval = (m_numitems != num);
00628 m_numitems = num;
00629 return (retval);
00630 }
00631
00632
00633 ERRVALUE Reserve (
00634 int newmaxitems,
00635 bool clear = false
00636 ) {
00637 if (clear) m_numitems = 0;
00638 if (newmaxitems > m_numalloc) {
00639 int err;
00640 if (m_numitems == 0) {
00641
00642 MmFree(m_items);
00643 }
00644 if ((err = MmRealloc((void**)&m_items,newmaxitems*sizeof(_CT))) < 0) return (err);
00645 m_numalloc = newmaxitems;
00646 }
00647 return (0);
00648 }
00649
00650
00651
00652 void ReserveExc (
00653 int newmaxitems,
00654 bool clear = false
00655 ) {
00656 if (clear) m_numitems = 0;
00657 if (newmaxitems > m_numalloc) {
00658 if (m_numitems == 0) {
00659
00660 MmFree(m_items);
00661 }
00662 MmReallocExc((void**)&m_items,newmaxitems*sizeof(_CT));
00663 m_numalloc = newmaxitems;
00664 }
00665 return;
00666 }
00667
00668
00669
00670
00671 ERRVALUE Resize (
00672 int numitems,
00673 bool keepold = true,
00674 bool clear = false
00675 ) {
00676 int err;
00677 if ((err = Reserve(numitems,!keepold)) < 0) return (err);
00678 if (clear && numitems > m_numitems) memset(static_cast<void*>(m_items+m_numitems),0,(numitems-m_numitems)*sizeof(_CT));
00679 m_numitems = numitems;
00680 return (0);
00681 }
00682
00683
00684 void Reverse (
00685 ) {
00686 for (int i = 0; (i < m_numitems/2); ++i) {
00687 _CT temp(m_items[i]);
00688 m_items[i] = m_items[m_numitems-i-1];
00689 m_items[m_numitems-i-1] = temp;
00690 }
00691 return;
00692 }
00693
00694
00695 void SetItem (
00696 int index,
00697 const _CT& item
00698 ) {
00699 m_items[index] = item;
00700 }
00701
00702
00703
00704 ERRVALUE SetItems (
00705 int firstitem,
00706 const _CT *items,
00707 int numitems
00708 ) {
00709 int err;
00710 if ((err = Reserve(firstitem+numitems)) < 0) return (err);
00711 memcpy(m_items+firstitem,items,numitems*sizeof(_CT));
00712 if (m_numitems < firstitem + numitems) m_numitems = firstitem + numitems;
00713 return (0);
00714 }
00715
00716
00717
00718
00719 void Sort (
00720 int (*CompFunc)(_CT*, _CT*, void*),
00721 void *data = 0
00722 ) {
00723
00724 heapsort(m_items, m_numitems, sizeof(_CT), reinterpret_cast<int (*)(void*, void*, void*)>(CompFunc), data);
00725 }
00726
00727
00728
00729
00730 void SortRange (
00731 int (*CompFunc)(_CT*, _CT*, void*),
00732 int firstidx,
00733 int numitems,
00734 void *data = 0
00735 ) {
00736 if (numitems <= 0 || firstidx < 0 || firstidx + numitems > m_numitems) return;
00737 heapsort(m_items + firstidx, numitems, sizeof(_CT), reinterpret_cast<int (*)(void*, void*, void*)>(CompFunc), data);
00738 }
00739
00740
00741
00742 void Swap (
00743 SIMPLE_ARRAY<_CT>& rhs
00744 ) {
00745 _CT *t_items = m_items;
00746 m_items = rhs.m_items;
00747 rhs.m_items = t_items;
00748 int t_numitems = m_numitems;
00749 m_numitems = rhs.m_numitems;
00750 rhs.m_numitems = t_numitems;
00751 int t_numalloc = m_numalloc;
00752 m_numalloc = rhs.m_numalloc;
00753 rhs.m_numalloc = t_numalloc;
00754 }
00755
00756
00757 void SwapBytes (
00758 ) {
00759 for (int i = 0;(i < m_numitems);++i) ::SwapBytes(m_items[i]);
00760 }
00761
00762 private:
00763 #ifndef GENERATING_DOXYGEN_OUTPUT
00764 _CT *m_items;
00765 int m_numitems;
00766 int m_numalloc;
00767 int m_spare;
00768 #endif // GENERATING_DOXYGEN_OUTPUT
00769
00770 };
00771
00772 #endif