1 #ifndef FILE_Array 2 #define FILE_Array 3 4 /**************************************************************************/ 5 /* File: array.hpp */ 6 /* Author: Joachim Schoeberl */ 7 /* Date: 01. Jun. 95 */ 8 /**************************************************************************/ 9 10 11 namespace netgen 12 { 13 14 // template <class T, int B1, int B2> class IndirectArray; 15 16 17 18 /** 19 A simple array container. 20 Array represented by size and data-pointer. 21 No memory allocation and deallocation, must be provided by user. 22 Helper functions for printing. 23 Optional range check by macro RANGE_CHECK 24 */ 25 26 template <class T, int BASE = 0> 27 class FlatArray 28 { 29 protected: 30 /// the size 31 int size; 32 /// the data 33 T * data; 34 public: 35 36 /// provide size and memory FlatArray(int asize,T * adata)37 FlatArray (int asize, T * adata) 38 : size(asize), data(adata) { ; } 39 40 /// the size Size() const41 int Size() const { return size; } 42 Begin() const43 int Begin() const { return BASE; } End() const44 int End() const { return size+BASE; } 45 46 /// Access array. BASE-based operator [](int i) const47 T & operator[] (int i) const 48 { 49 #ifdef DEBUG 50 if (i-BASE < 0 || i-BASE >= size) 51 cout << "array<" << typeid(T).name() << "> out of range, i = " << i << ", s = " << size << endl; 52 #endif 53 54 return data[i-BASE]; 55 } 56 57 /// Access array, one-based (old fashioned) Elem(int i)58 T & Elem (int i) 59 { 60 #ifdef DEBUG 61 if (i < 1 || i > size) 62 cout << "Array<" << typeid(T).name() 63 << ">::Elem out of range, i = " << i 64 << ", s = " << size << endl; 65 #endif 66 67 return ((T*)data)[i-1]; 68 } 69 70 /// Access array, one-based (old fashioned) Get(int i) const71 const T & Get (int i) const 72 { 73 #ifdef DEBUG 74 if (i < 1 || i > size) 75 cout << "Array<" << typeid(T).name() << ">::Get out of range, i = " << i 76 << ", s = " << size << endl; 77 #endif 78 79 return ((const T*)data)[i-1]; 80 } 81 82 /// Access array, one-based (old fashioned) Set(int i,const T & el)83 void Set (int i, const T & el) 84 { 85 #ifdef DEBUG 86 if (i < 1 || i > size) 87 cout << "Array<" << typeid(T).name() << ">::Set out of range, i = " << i 88 << ", s = " << size << endl; 89 #endif 90 91 ((T*)data)[i-1] = el; 92 } 93 94 /// access first element First() const95 T & First () const 96 { 97 return data[0]; 98 } 99 100 101 /// access last element. check by macro CHECK_RANGE Last() const102 T & Last () const 103 { 104 return data[size-1]; 105 } 106 107 /// Fill array with value val operator =(const T & val)108 FlatArray & operator= (const T & val) 109 { 110 for (int i = 0; i < size; i++) 111 data[i] = val; 112 return *this; 113 } 114 115 /// takes range starting from position start of end-start elements Range(int start,int end)116 const FlatArray<T> Range (int start, int end) 117 { 118 return FlatArray<T> (end-start, data+start); 119 } 120 121 /// first position of element elem, returns -1 if element not contained in array Pos(const T & elem) const122 int Pos(const T & elem) const 123 { 124 int pos = -1; 125 for(int i=0; pos==-1 && i < this->size; i++) 126 if(elem == data[i]) pos = i; 127 return pos; 128 } 129 130 /// does the array contain element elem ? Contains(const T & elem) const131 bool Contains(const T & elem) const 132 { 133 return ( Pos(elem) >= 0 ); 134 } 135 }; 136 137 138 139 // print array 140 template <class T, int BASE> operator <<(ostream & s,const FlatArray<T,BASE> & a)141 inline ostream & operator<< (ostream & s, const FlatArray<T,BASE> & a) 142 { 143 for (int i = a.Begin(); i < a.End(); i++) 144 s << i << ": " << a[i] << endl; 145 return s; 146 } 147 148 149 150 /** 151 Dynamic array container. 152 153 Array<T> is an automatically increasing array container. 154 The allocated memory doubles on overflow. 155 Either the container takes care of memory allocation and deallocation, 156 or the user provides one block of data. 157 */ 158 template <class T, int BASE = 0> 159 class Array : public FlatArray<T, BASE> 160 { 161 protected: 162 using FlatArray<T,BASE>::size; 163 using FlatArray<T,BASE>::data; 164 165 /// physical size of array 166 int allocsize; 167 /// memory is responsibility of container 168 bool ownmem; 169 170 public: 171 172 /// Generate array of logical and physical size asize Array(int asize=0)173 explicit Array(int asize = 0) 174 : FlatArray<T, BASE> (asize, asize ? new T[asize] : 0) 175 { 176 allocsize = asize; 177 ownmem = 1; 178 } 179 180 /// Generate array in user data Array(int asize,T * adata)181 Array(int asize, T* adata) 182 : FlatArray<T, BASE> (asize, adata) 183 { 184 allocsize = asize; 185 ownmem = 0; 186 } 187 188 /// array copy Array(const Array<T> & a2)189 explicit Array (const Array<T> & a2) 190 : FlatArray<T, BASE> (a2.Size(), a2.Size() ? new T[a2.Size()] : 0) 191 { 192 allocsize = size; 193 ownmem = 1; 194 for (int i = BASE; i < size+BASE; i++) 195 (*this)[i] = a2[i]; 196 } 197 198 199 200 /// if responsible, deletes memory ~Array()201 ~Array() 202 { 203 if (ownmem) 204 delete [] data; 205 } 206 207 /// Change logical size. If necessary, do reallocation. Keeps contents. SetSize(int nsize)208 void SetSize(int nsize) 209 { 210 if (nsize > allocsize) 211 ReSize (nsize); 212 size = nsize; 213 } 214 215 /// Change physical size. Keeps logical size. Keeps contents. SetAllocSize(int nallocsize)216 void SetAllocSize (int nallocsize) 217 { 218 if (nallocsize > allocsize) 219 ReSize (nallocsize); 220 } 221 222 223 /// Add element at end of array. reallocation if necessary. Append(const T & el)224 int Append (const T & el) 225 { 226 if (size == allocsize) 227 ReSize (size+1); 228 data[size] = el; 229 size++; 230 return size; 231 } 232 233 template <typename T2, int B2> Append(FlatArray<T2,B2> a2)234 void Append (FlatArray<T2, B2> a2) 235 { 236 if (size+a2.Size() > allocsize) 237 ReSize (size+a2.Size()); 238 for (int i = 0; i < a2.Size(); i++) 239 data[size+i] = a2[i+B2]; 240 size += a2.Size(); 241 } 242 243 244 /// Delete element i (0-based). Move last element to position i. Delete(int i)245 void Delete (int i) 246 { 247 #ifdef CHECK_Array_RANGE 248 RangeCheck (i+1); 249 #endif 250 251 data[i] = data[size-1]; 252 size--; 253 // DeleteElement (i+1); 254 } 255 256 257 /// Delete element i (1-based). Move last element to position i. DeleteElement(int i)258 void DeleteElement (int i) 259 { 260 #ifdef CHECK_Array_RANGE 261 RangeCheck (i); 262 #endif 263 264 data[i-1] = data[size-1]; 265 size--; 266 } 267 268 /// Delete last element. DeleteLast()269 void DeleteLast () 270 { 271 size--; 272 } 273 274 /// Deallocate memory DeleteAll()275 void DeleteAll () 276 { 277 if (ownmem) 278 delete [] data; 279 data = 0; 280 size = allocsize = 0; 281 } 282 283 /// Fill array with val operator =(const T & val)284 Array & operator= (const T & val) 285 { 286 FlatArray<T, BASE>::operator= (val); 287 return *this; 288 } 289 290 /// array copy operator =(const Array & a2)291 Array & operator= (const Array & a2) 292 { 293 SetSize (a2.Size()); 294 for (int i = BASE; i < size+BASE; i++) 295 (*this)[i] = a2[i]; 296 return *this; 297 } 298 299 /// array copy operator =(const FlatArray<T> & a2)300 Array & operator= (const FlatArray<T> & a2) 301 { 302 SetSize (a2.Size()); 303 for (int i = BASE; i < size+BASE; i++) 304 (*this)[i] = a2[i]; 305 return *this; 306 } 307 308 309 private: 310 311 /// resize array, at least to size minsize. copy contents ReSize(int minsize)312 void ReSize (int minsize) 313 { 314 int nsize = 2 * allocsize; 315 if (nsize < minsize) nsize = minsize; 316 317 if (data) 318 { 319 T * p = new T[nsize]; 320 321 int mins = (nsize < size) ? nsize : size; 322 memcpy (p, data, mins * sizeof(T)); 323 324 if (ownmem) 325 delete [] data; 326 ownmem = 1; 327 data = p; 328 } 329 else 330 { 331 data = new T[nsize]; 332 ownmem = 1; 333 } 334 335 allocsize = nsize; 336 } 337 }; 338 339 340 341 template <class T, int S> 342 class ArrayMem : public Array<T> 343 { 344 using Array<T>::size; 345 using Array<T>::data; 346 using Array<T>::ownmem; 347 348 // T mem[S]; // Intel C++ calls dummy constructor 349 // char mem[S*sizeof(T)]; 350 double mem[(S*sizeof(T)+7) / 8]; 351 public: 352 /// Generate array of logical and physical size asize ArrayMem(int asize=0)353 explicit ArrayMem(int asize = 0) 354 : Array<T> (S, static_cast<T*> (static_cast<void*>(&mem[0]))) 355 { 356 size = asize; 357 if (asize > S) 358 { 359 data = new T[asize]; 360 ownmem = 1; 361 } 362 // SetSize (asize); 363 } 364 operator =(const T & val)365 ArrayMem & operator= (const T & val) 366 { 367 Array<T>::operator= (val); 368 return *this; 369 } 370 371 /// array copy operator =(const FlatArray<T> & a2)372 ArrayMem & operator= (const FlatArray<T> & a2) 373 { 374 this->SetSize (a2.Size()); 375 for (int i = 0; i < size; i++) 376 (*this)[i] = a2[i]; 377 return *this; 378 } 379 380 }; 381 382 383 384 385 386 /* 387 template <class T, int B1, int B2> 388 class IndirectArray 389 { 390 const FlatArray<T, B1> & array; 391 const FlatArray<int, B2> & ia; 392 393 public: 394 IndirectArray (const FlatArray<T,B1> & aa, const FlatArray<int, B2> & aia) 395 : array(aa), ia(aia) { ; } 396 int Size() const { return ia.Size(); } 397 const T & operator[] (int i) const { return array[ia[i]]; } 398 }; 399 */ 400 401 402 403 404 405 406 407 408 409 /// 410 template <class T, int BASE = 0> 411 class MoveableArray 412 { 413 int size; 414 int allocsize; 415 DynamicMem<T> data; 416 417 public: 418 MoveableArray()419 MoveableArray() 420 { 421 size = allocsize = 0; 422 data.SetName ("MoveableArray"); 423 } 424 MoveableArray(int asize)425 MoveableArray(int asize) 426 : size(asize), allocsize(asize), data(asize) 427 { ; } 428 ~MoveableArray()429 ~MoveableArray () { ; } 430 Size() const431 int Size() const { return size; } 432 SetSize(int nsize)433 void SetSize(int nsize) 434 { 435 if (nsize > allocsize) 436 { 437 data.ReAlloc (nsize); 438 allocsize = nsize; 439 } 440 size = nsize; 441 } 442 SetAllocSize(int nallocsize)443 void SetAllocSize (int nallocsize) 444 { 445 data.ReAlloc (nallocsize); 446 allocsize = nallocsize; 447 } 448 449 /// operator [](int i)450 T & operator[] (int i) 451 { return ((T*)data)[i-BASE]; } 452 453 /// operator [](int i) const454 const T & operator[] (int i) const 455 { return ((const T*)data)[i-BASE]; } 456 457 /// Elem(int i)458 T & Elem (int i) 459 { return ((T*)data)[i-1]; } 460 461 /// Get(int i) const462 const T & Get (int i) const 463 { return ((const T*)data)[i-1]; } 464 465 /// Set(int i,const T & el)466 void Set (int i, const T & el) 467 { ((T*)data)[i-1] = el; } 468 469 /// Last()470 T & Last () 471 { return ((T*)data)[size-1]; } 472 473 /// Last() const474 const T & Last () const 475 { return ((const T*)data)[size-1]; } 476 477 /// Append(const T & el)478 int Append (const T & el) 479 { 480 if (size == allocsize) 481 { 482 SetAllocSize (2*allocsize+1); 483 } 484 ((T*)data)[size] = el; 485 size++; 486 return size; 487 } 488 489 /// Delete(int i)490 void Delete (int i) 491 { 492 DeleteElement (i+1); 493 } 494 495 /// DeleteElement(int i)496 void DeleteElement (int i) 497 { 498 ((T*)data)[i-1] = ((T*)data)[size-1]; 499 size--; 500 } 501 502 /// DeleteLast()503 void DeleteLast () 504 { size--; } 505 506 /// DeleteAll()507 void DeleteAll () 508 { 509 size = allocsize = 0; 510 data.Free(); 511 } 512 513 /// PrintMemInfo(ostream & ost) const514 void PrintMemInfo (ostream & ost) const 515 { 516 ost << Size() << " elements of size " << sizeof(T) << " = " 517 << Size() * sizeof(T) << endl; 518 } 519 operator =(const T & el)520 MoveableArray & operator= (const T & el) 521 { 522 for (int i = 0; i < size; i++) 523 ((T*)data)[i] = el; 524 return *this; 525 } 526 527 Copy(const MoveableArray & a2)528 MoveableArray & Copy (const MoveableArray & a2) 529 { 530 SetSize (a2.Size()); 531 for (int i = 0; i < this->size; i++) 532 data[i] = a2.data[i]; 533 return *this; 534 } 535 536 /// array copy operator =(const MoveableArray & a2)537 MoveableArray & operator= (const MoveableArray & a2) 538 { 539 return Copy(a2); 540 } 541 542 SetName(const char * aname)543 void SetName (const char * aname) 544 { 545 data.SetName(aname); 546 } 547 private: 548 /// 549 //MoveableArray & operator= (MoveableArray &); //??? 550 /// 551 //MoveableArray (const MoveableArray &); //??? 552 }; 553 554 555 template <class T> operator <<(ostream & ost,MoveableArray<T> & a)556 inline ostream & operator<< (ostream & ost, MoveableArray<T> & a) 557 { 558 for (int i = 0; i < a.Size(); i++) 559 ost << i << ": " << a[i] << endl; 560 return ost; 561 } 562 563 564 565 /// bubble sort array 566 template <class T> BubbleSort(const FlatArray<T> & data)567 inline void BubbleSort (const FlatArray<T> & data) 568 { 569 for (int i = 0; i < data.Size(); i++) 570 for (int j = i+1; j < data.Size(); j++) 571 if (data[i] > data[j]) 572 { 573 T hv = data[i]; 574 data[i] = data[j]; 575 data[j] = hv; 576 } 577 } 578 579 /// bubble sort array 580 template <class T, class S> BubbleSort(FlatArray<T> & data,FlatArray<S> & slave)581 inline void BubbleSort (FlatArray<T> & data, FlatArray<S> & slave) 582 { 583 for (int i = 0; i < data.Size(); i++) 584 for (int j = i+1; j < data.Size(); j++) 585 if (data[i] > data[j]) 586 { 587 T hv = data[i]; 588 data[i] = data[j]; 589 data[j] = hv; 590 591 S hvs = slave[i]; 592 slave[i] = slave[j]; 593 slave[j] = hvs; 594 } 595 } 596 597 598 template <class T, class S> QuickSortRec(FlatArray<T> & data,FlatArray<S> & slave,int left,int right)599 void QuickSortRec (FlatArray<T> & data, 600 FlatArray<S> & slave, 601 int left, int right) 602 { 603 int i = left; 604 int j = right; 605 T midval = data[(left+right)/2]; 606 607 do 608 { 609 while (data[i] < midval) i++; 610 while (midval < data[j]) j--; 611 612 if (i <= j) 613 { 614 Swap (data[i], data[j]); 615 Swap (slave[i], slave[j]); 616 i++; j--; 617 } 618 } 619 while (i <= j); 620 if (left < j) QuickSortRec (data, slave, left, j); 621 if (i < right) QuickSortRec (data, slave, i, right); 622 } 623 624 template <class T, class S> QuickSort(FlatArray<T> & data,FlatArray<S> & slave)625 void QuickSort (FlatArray<T> & data, FlatArray<S> & slave) 626 { 627 QuickSortRec (data, slave, 0, data.Size()-1); 628 } 629 630 631 632 633 634 635 636 637 638 template <class T> Intersection(const FlatArray<T> & in1,const FlatArray<T> & in2,Array<T> & out)639 void Intersection (const FlatArray<T> & in1, const FlatArray<T> & in2, 640 Array<T> & out) 641 { 642 out.SetSize(0); 643 for(int i=0; i<in1.Size(); i++) 644 if(in2.Contains(in1[i])) 645 out.Append(in1[i]); 646 } 647 template <class T> Intersection(const FlatArray<T> & in1,const FlatArray<T> & in2,const FlatArray<T> & in3,Array<T> & out)648 void Intersection (const FlatArray<T> & in1, const FlatArray<T> & in2, const FlatArray<T> & in3, 649 Array<T> & out) 650 { 651 out.SetSize(0); 652 for(int i=0; i<in1.Size(); i++) 653 if(in2.Contains(in1[i]) && in3.Contains(in1[i])) 654 out.Append(in1[i]); 655 } 656 657 658 } 659 660 #endif 661 662