Array.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791
  1. #ifndef Array_H
  2. #define Array_H
  3. #include "Errors.h"
  4. #include <stdexcept>
  5. #include "Text.h"
  6. #include "ReferenceCounter.h"
  7. namespace Framework
  8. {
  9. template< class TYP >
  10. //! Ein Eintrag in einer Linked List
  11. struct ArrayEintrag
  12. {
  13. TYP var;
  14. bool set = false;
  15. ArrayEintrag< TYP >* next = 0;
  16. //! Setzt den Eintrag auf die Werte des anderen Eintrages
  17. ArrayEintrag& operator=( ArrayEintrag& r )
  18. {
  19. var = r.var;
  20. set = r.set;
  21. next = r.next;
  22. return *this;
  23. }
  24. //! Gibt den aktuell gespeicherten Wert zurück
  25. operator TYP()
  26. {
  27. if( !set )
  28. {
  29. Text err = "Index out of Range Exception File: ";
  30. err += __FILE__;
  31. err += " Line: ";
  32. err += __LINE__;
  33. throw std::out_of_range( (char*)err );
  34. }
  35. return var;
  36. }
  37. //! inkrementiert durch die Linked List durch
  38. ArrayEintrag< TYP >& operator++() //! prefix
  39. {
  40. if( !next )
  41. {
  42. ArrayEintrag<TYP> tmp;
  43. tmp.set = 0;
  44. tmp.next = 0;
  45. *this = tmp;
  46. return *this;
  47. }
  48. *this = *next;
  49. return *next;
  50. }
  51. //! inkrementiert durch die Linked List durch
  52. ArrayEintrag< TYP >& operator++( int ) //! postfix
  53. {
  54. if( !next )
  55. {
  56. ArrayEintrag<TYP> tmp;
  57. tmp.set = 0;
  58. tmp.next = 0;
  59. *this = tmp;
  60. return *this;
  61. }
  62. *this = *next;
  63. return *next;
  64. }
  65. #ifdef WIN32
  66. #pragma warning( once : 26495 )
  67. };
  68. #else
  69. };
  70. #endif
  71. template< class TYP >
  72. class Iterator
  73. {
  74. private:
  75. ArrayEintrag< TYP >* current;
  76. public:
  77. Iterator( ArrayEintrag< TYP >* start )
  78. {
  79. current = start;
  80. while( current && !current->set )
  81. {
  82. current = current->next;
  83. }
  84. }
  85. Iterator( const Iterator& it )
  86. {
  87. current = it.current;
  88. }
  89. Iterator< TYP >& operator=( Iterator< TYP > r )
  90. {
  91. current = r.current;
  92. return *this;
  93. }
  94. bool hasNext()
  95. {
  96. ArrayEintrag< TYP >* next = current->next;
  97. while( next && !next->set )
  98. {
  99. next = next->next;
  100. }
  101. return next != 0;
  102. }
  103. TYP operator*()
  104. {
  105. return current->var;
  106. }
  107. Iterator< TYP > next()
  108. {
  109. if( !current )
  110. {
  111. Text err = "Index out of Range Exception File: ";
  112. err += __FILE__;
  113. err += " Line: ";
  114. err += __LINE__;
  115. throw std::out_of_range( (char*)err );
  116. }
  117. return Iterator( current->next );
  118. }
  119. operator bool()
  120. {
  121. return current != 0;
  122. }
  123. operator TYP()
  124. {
  125. if( !current || !current->set )
  126. {
  127. Text err = "Index out of Range Exception File: ";
  128. err += __FILE__;
  129. err += " Line: ";
  130. err += __LINE__;
  131. throw std::out_of_range( (char*)err );
  132. }
  133. return current->var;
  134. }
  135. Iterator< TYP >& operator++() //! prefix
  136. {
  137. do
  138. {
  139. if( current )
  140. current = current->next;
  141. } while( current && !current->set );
  142. return *this;
  143. }
  144. Iterator< TYP > operator++( int ) //! postfix
  145. {
  146. Iterator< TYP > temp( *this );
  147. do
  148. {
  149. if( current )
  150. current = current->next;
  151. } while( current && !current->set );
  152. return temp;
  153. }
  154. TYP operator->()
  155. {
  156. if( !current || !current->set )
  157. {
  158. Text err = "Index out of Range Exception File: ";
  159. err += __FILE__;
  160. err += " Line: ";
  161. err += __LINE__;
  162. throw std::out_of_range( (char*)err );
  163. }
  164. return current->var;
  165. }
  166. TYP val()
  167. {
  168. if( !current || !current->set )
  169. {
  170. Text err = "Index out of Range Exception File: ";
  171. err += __FILE__;
  172. err += " Line: ";
  173. err += __LINE__;
  174. throw std::out_of_range( (char*)err );
  175. }
  176. return current->var;
  177. }
  178. void set( TYP val )
  179. {
  180. if( current )
  181. {
  182. current->var = val;
  183. current->set = true;
  184. }
  185. else
  186. {
  187. Text err = "Index out of Range Exception File: ";
  188. err += __FILE__;
  189. err += " Line: ";
  190. err += __LINE__;
  191. throw std::out_of_range( (char*)err );
  192. }
  193. }
  194. bool operator!=( Iterator< TYP >& r )
  195. {
  196. return current != r.current;
  197. }
  198. };
  199. #define _ val()
  200. template< class TYP >
  201. //! Eine Linked List von Klassen, die kein Reference Counting berteiben
  202. class Array : public virtual ReferenceCounter
  203. {
  204. private:
  205. ArrayEintrag< TYP >* entries;
  206. ArrayEintrag< TYP >* last;
  207. int count;
  208. public:
  209. //! Erstellt eine neue Linked List
  210. Array() noexcept
  211. : ReferenceCounter()
  212. {
  213. entries = new ArrayEintrag< TYP >();
  214. entries->set = 0;
  215. entries->next = 0;
  216. last = entries;
  217. count = 0;
  218. }
  219. //! Kopiert eine Linked list
  220. //!
  221. Array( const Array& arr )
  222. : Array()
  223. {
  224. int anz = arr.getEintragAnzahl();
  225. for( int i = 0; i < anz; i++ )
  226. add( arr.get( i ) );
  227. }
  228. //! Leert und löscht die Linked List
  229. ~Array()
  230. {
  231. leeren();
  232. delete entries;
  233. }
  234. //! Hängt ein Element ans Ende der Liste an
  235. //! \param t Das neue Element
  236. void add( TYP t )
  237. {
  238. count++;
  239. if( !last->set )
  240. {
  241. last->var = t;
  242. last->set = 1;
  243. return;
  244. }
  245. last->next = new ArrayEintrag< TYP >();
  246. last = last->next;
  247. last->set = 1;
  248. last->var = t;
  249. }
  250. //! Fügt ein Element bei einer bestimmten Position in die Liste ein
  251. //! \param t das neue Element
  252. //! \param i Die Position, wo das Element eingefügt wird (danach der Index des neuen Elementes)
  253. void add( TYP t, int i )
  254. {
  255. if( i < 0 || i > count )
  256. throwOutOfRange( __FILE__, __LINE__, i, count );
  257. if( i == count )
  258. {
  259. add( t );
  260. return;
  261. }
  262. count++;
  263. ArrayEintrag< TYP >* e = entries;
  264. for( int a = 0; a < i; ++a )
  265. e = e->next;
  266. ArrayEintrag< TYP >* ne = new ArrayEintrag< TYP >();
  267. ne->var = e->var;
  268. ne->set = e->set;
  269. ne->next = e->next;
  270. e->next = ne;
  271. e->var = t;
  272. e->set = 1;
  273. }
  274. //! Setzt den Wert des i-ten Eintrags
  275. //! \param t der Neue Wert
  276. //! \param i Der Index des Eintrages der gesetzt werden soll
  277. void set( TYP t, int i )
  278. {
  279. if( i < 0 || i >= count )
  280. throwOutOfRange( __FILE__, __LINE__, i, count );
  281. ArrayEintrag< TYP >* e = entries;
  282. for( int a = 0; a < i; ++a )
  283. e = e->next;
  284. e->var = t;
  285. e->set = 1;
  286. }
  287. //! Verändert die Position des i-ten Elementes in der Liste
  288. //! \param i Der Index des Elementes, welches verschoben werden soll
  289. //! \param p Die Zielposition des Elementes (danach der neue Index des Elementes)
  290. void setPosition( int i, int p )
  291. {
  292. if( i == p )
  293. return;
  294. if( i < 0 || p < 0 || i >= count || p >= count )
  295. throwOutOfRange( __FILE__, __LINE__, i, count );
  296. ArrayEintrag< TYP >* e = entries;
  297. ArrayEintrag< TYP >* ve = 0;
  298. for( int a = 0; a < i; ++a )
  299. {
  300. ve = e;
  301. e = e->next;
  302. }
  303. ArrayEintrag< TYP >* e2 = entries == e ? e->next : entries;
  304. ArrayEintrag< TYP >* ve2 = 0;
  305. for( int a = 0; a < p; ++a )
  306. {
  307. ve2 = e2;
  308. if( e2->next == e )
  309. e2 = e->next;
  310. else
  311. e2 = e2->next;
  312. }
  313. if( e == last )
  314. last = e2;
  315. else if( e2 == last )
  316. last = e;
  317. if( !ve2 )
  318. entries = e;
  319. else
  320. ve2->next = e;
  321. if( ve )
  322. ve->next = e->next;
  323. else
  324. entries = e->next;
  325. e->next = e2;
  326. }
  327. //! Löscht ein Bestimmtes Element
  328. //! \param i Der Index des Elementes das gelöscht werden soll
  329. void remove( int i )
  330. {
  331. if( i < 0 || i >= count )
  332. throwOutOfRange( __FILE__, __LINE__, i, count );
  333. ArrayEintrag< TYP >* e = entries;
  334. for( int a = 0; a < i; ++a )
  335. e = e->next;
  336. if( e->next )
  337. {
  338. e->var = e->next->var;
  339. e->set = e->next->set;
  340. }
  341. else
  342. e->set = 0;
  343. ArrayEintrag< TYP >* del = e->next;
  344. if( e->next )
  345. e->next = e->next->next;
  346. else
  347. e->next = 0;
  348. if( del )
  349. {
  350. del->set = 0;
  351. del->next = 0;
  352. if( last == del )
  353. last = e;
  354. delete del;
  355. }
  356. count--;
  357. }
  358. //! Löscht ein Bestimmtes Element
  359. //! \param i Der Index des Elementes das gelöscht werden soll
  360. void removeValue( TYP value )
  361. {
  362. ArrayEintrag< TYP >* e = entries;
  363. while( e->var != value )
  364. {
  365. if( !e->next )
  366. return;
  367. e = e->next;
  368. }
  369. if( !e )
  370. return;
  371. if( e->next )
  372. {
  373. e->var = e->next->var;
  374. e->set = e->next->set;
  375. }
  376. else
  377. e->set = 0;
  378. ArrayEintrag< TYP >* del = e->next;
  379. if( e->next )
  380. e->next = e->next->next;
  381. else
  382. e->next = 0;
  383. if( del )
  384. {
  385. del->set = 0;
  386. del->next = 0;
  387. if( last == del )
  388. last = e;
  389. delete del;
  390. }
  391. count--;
  392. }
  393. //! Vertauscht zwei Elemente in der Liste
  394. //! \param vi Der Index des ersten Elementes
  395. //! \param ni Der Index des zweiten Elementes
  396. void tausch( int vi, int ni )
  397. {
  398. TYP tmp = get( ni );
  399. set( get( vi ), ni );
  400. set( tmp, vi );
  401. }
  402. //! Löscht alle Elemente der Liste
  403. void leeren()
  404. {
  405. ArrayEintrag< TYP >* e2 = 0;
  406. for( ArrayEintrag< TYP >* e = entries; e; e = e->next )
  407. {
  408. delete e2;
  409. e2 = e;
  410. }
  411. delete e2;
  412. entries = new ArrayEintrag< TYP >();
  413. entries->set = 0;
  414. entries->next = 0;
  415. last = entries;
  416. count = 0;
  417. }
  418. //! Gibt einen Iterator zurück.
  419. //! Mit ++ kann durch die Liste iteriert werden
  420. Iterator< TYP > begin() const
  421. {
  422. return Iterator< TYP >( entries );
  423. }
  424. Iterator< TYP > end() const
  425. {
  426. return Iterator< TYP >( 0 );
  427. }
  428. //! Gibt zurück, wie viele Elemente in der Liste sind
  429. int getEintragAnzahl() const
  430. {
  431. return count;
  432. }
  433. //! Gibt den Wert des i-ten Elementes zurück
  434. //! \param i Der index des gesuchten Elementes
  435. //! throws:
  436. //! \param std:out_of_range wenn i < 0 oder i >= getEintragAnzahl()
  437. TYP get( int i ) const
  438. {
  439. if( i < 0 || i >= count )
  440. throwOutOfRange( __FILE__, __LINE__, i, count );
  441. ArrayEintrag< TYP >* e = entries;
  442. for( int a = 0; a < i && e; ++a )
  443. e = e->next;
  444. return e->var;
  445. }
  446. //! Überprüft, ob ein Element in der Liste enthalten ist
  447. //! \param i Der Index des gesuchten Elementes
  448. //! \return (true), wenn der Index vorhanden ist. (false) sonnst
  449. bool hat( int i ) const
  450. {
  451. return i >= 0 && i < count;
  452. }
  453. //! Gibt den Index eines Wertes zurück
  454. //! \param t Der Wert, nach dem gesucht werden soll
  455. int getWertIndex( TYP t ) const
  456. {
  457. int ret = 0;
  458. for( ArrayEintrag< TYP >* e = entries; e; e = e->next )
  459. {
  460. if( e->set && e->var == t )
  461. return ret;
  462. ++ret;
  463. }
  464. return -1;
  465. }
  466. Array& operator=( const Array& arr )
  467. {
  468. leeren();
  469. int anz = arr.getEintragAnzahl();
  470. for( int i = 0; i < anz; i++ )
  471. add( arr.get( i ) );
  472. return *this;
  473. }
  474. };
  475. template< class TYP >
  476. //! Eine Linked List von Zeigern auf Zeichnunge, die Reference Counting berteiben
  477. class RCArray : public virtual ReferenceCounter
  478. {
  479. private:
  480. ArrayEintrag< TYP* >* entries;
  481. ArrayEintrag< TYP* >* last;
  482. int count;
  483. public:
  484. //! Erstellt eine neue Linked List
  485. RCArray() noexcept
  486. : ReferenceCounter()
  487. {
  488. entries = new ArrayEintrag< TYP* >();
  489. entries->set = 0;
  490. entries->next = 0;
  491. last = entries;
  492. count = 0;
  493. }
  494. //! Kopiert eine Linked list
  495. RCArray( const RCArray& arr )
  496. : RCArray()
  497. {
  498. int anz = arr.getEintragAnzahl();
  499. for( int i = 0; i < anz; i++ )
  500. add( arr.get( i ) );
  501. ref = 1;
  502. }
  503. //! Leert und löscht die Linked List
  504. ~RCArray()
  505. {
  506. leeren();
  507. delete entries;
  508. }
  509. //! Hängt ein Element ans Ende der Liste an
  510. //! \param t Das neue Element
  511. void add( TYP* t )
  512. {
  513. count++;
  514. if( !last->set )
  515. {
  516. last->var = t;
  517. last->set = 1;
  518. return;
  519. }
  520. last->next = new ArrayEintrag< TYP* >();
  521. last = last->next;
  522. last->var = t;
  523. last->set = 1;
  524. }
  525. //! Fügt ein Element bei einer bestimmten Position in die Liste ein
  526. //! \param t das neue Element
  527. //! \param i Die Position, wo das Element eingefügt wird (danach der Index des neuen Elementes)
  528. void add( TYP* t, int i )
  529. {
  530. if( i < 0 || i > count )
  531. throwOutOfRange( __FILE__, __LINE__, i, count );
  532. if( i == count )
  533. {
  534. add( t );
  535. return;
  536. }
  537. ArrayEintrag< TYP* >* e = entries;
  538. for( int a = 0; a < i; ++a )
  539. e = e->next;
  540. ArrayEintrag< TYP* >* ne = new ArrayEintrag< TYP* >();
  541. ne->var = e->var;
  542. ne->set = e->set;
  543. ne->next = e->next;
  544. e->next = ne;
  545. e->var = t;
  546. e->set = 1;
  547. if( last->next )
  548. last = last->next;
  549. count++;
  550. }
  551. //! Setzt den Wert des i-ten Eintrags
  552. //! \param t der Neue Wert
  553. //! \param i Der Index des Eintrages der gesetzt werden soll
  554. void set( TYP* t, int i )
  555. {
  556. if( i < 0 || i >= count )
  557. throwOutOfRange( __FILE__, __LINE__, i, count );
  558. ArrayEintrag< TYP* >* e = entries;
  559. for( int a = 0; a < i; ++a )
  560. e = e->next;
  561. if( e->set && e->var )
  562. e->var->release();
  563. e->var = t;
  564. e->set = 1;
  565. }
  566. //! Verändert die Position des i-ten Elementes in der Liste
  567. //! \param i Der Index des Elementes, welches verschoben werden soll
  568. //! \param p Die Zielposition des Elementes (danach der neue Index des Elementes)
  569. void setPosition( int i, int p )
  570. {
  571. if( i == p )
  572. return;
  573. if( i < 0 || p < 0 || i >= count || p >= count )
  574. throwOutOfRange( __FILE__, __LINE__, i, count );
  575. ArrayEintrag< TYP* >* ve = 0;
  576. ArrayEintrag< TYP* >* e = entries;
  577. for( int a = 0; a < i; ++a )
  578. {
  579. ve = e;
  580. e = e->next;
  581. }
  582. ArrayEintrag< TYP* >* e2 = entries == e ? e->next : entries;
  583. ArrayEintrag< TYP* >* ve2 = 0;
  584. for( int a = 0; a < p; ++a )
  585. {
  586. ve2 = e2;
  587. if( e2->next == e )
  588. e2 = e->next;
  589. else
  590. e2 = e2->next;
  591. }
  592. if( last == e )
  593. last = e2;
  594. else if( last == e2 )
  595. last = e;
  596. if( !ve2 )
  597. entries = e;
  598. else
  599. ve2->next = e;
  600. if( ve )
  601. ve->next = e->next;
  602. else
  603. entries = e->next;
  604. e->next = e2;
  605. }
  606. //! Löscht ein Bestimmtes Element
  607. //! \param i Der Index des Elementes das gelöscht werden soll
  608. void remove( int i )
  609. {
  610. if( i < 0 || i >= count )
  611. throwOutOfRange( __FILE__, __LINE__, i, count );
  612. ArrayEintrag< TYP* >* e = entries;
  613. for( int a = 0; a < i; ++a )
  614. e = e->next;
  615. if( e->next )
  616. {
  617. if( e->set && e->var )
  618. e->var->release();
  619. e->var = e->next->var;
  620. e->set = e->next->set;
  621. }
  622. else
  623. {
  624. if( e->set && e->var )
  625. e->var->release();
  626. e->set = 0;
  627. }
  628. ArrayEintrag< TYP* >* del = e->next;
  629. if( e->next )
  630. e->next = e->next->next;
  631. else
  632. e->next = 0;
  633. if( del )
  634. {
  635. del->set = 0;
  636. del->next = 0;
  637. if( last == del )
  638. last = e;
  639. delete del;
  640. }
  641. count--;
  642. }
  643. //! Vertauscht zwei Elemente in der Liste
  644. //! \param vi Der Index des ersten Elementes
  645. //! \param ni Der Index des zweiten Elementes
  646. void tausch( int vi, int ni )
  647. {
  648. if( vi < 0 || ni < 0 )
  649. return;
  650. TYP* tmp = get( ni );
  651. set( get( vi ), ni );
  652. set( tmp, vi );
  653. }
  654. //! Löscht alle Elemente der Liste
  655. void leeren()
  656. {
  657. for( ArrayEintrag< TYP* >* e = entries; e; )
  658. {
  659. if( e && e->var && e->set )
  660. e->var->release();
  661. auto tmp = e->next;
  662. delete e;
  663. e = tmp;
  664. }
  665. entries = new ArrayEintrag< TYP* >();
  666. entries->set = 0;
  667. entries->next = 0;
  668. last = entries;
  669. count = 0;
  670. }
  671. //! Gibt einen Iterator zurück.
  672. //! Mit ++ kann durch die Liste iteriert werden
  673. Iterator< TYP* > begin() const
  674. {
  675. return Iterator< TYP* >( entries );
  676. }
  677. Iterator< TYP* > end() const
  678. {
  679. return Iterator< TYP* >( 0 );
  680. }
  681. //! Gibt zurück, wie viele Elemente in der Liste sind
  682. int getEintragAnzahl() const
  683. {
  684. return count;
  685. }
  686. int getLastIndex() const
  687. {
  688. return count - 1;
  689. }
  690. //! Gibt den Wert des i-ten Elementes zurück mit erhöhtem Reference Counter
  691. //! \param i Der index des gesuchten Elementes, (0) wenn der Index nicht existiert
  692. TYP* get( int i ) const
  693. {
  694. if( i < 0 || i >= count )
  695. throwOutOfRange( __FILE__, __LINE__, i, count );
  696. ArrayEintrag< TYP* >* e = entries;
  697. for( int a = 0; a < i && e; ++a )
  698. e = e->next;
  699. if( e && e->set && e->var )
  700. return dynamic_cast<TYP*>(e->var->getThis());
  701. return (TYP*)0;
  702. }
  703. //! Gibt den Wert des i-ten Elementes zurück ohne erhöhten Reference Counter
  704. //! \param i Der index des gesuchten Elementes, (0) wenn der Index nicht existiert
  705. TYP* z( int i ) const //! gibt den index - ten T zurück
  706. {
  707. if( i < 0 || i >= count )
  708. throwOutOfRange( __FILE__, __LINE__, i, count );
  709. ArrayEintrag< TYP* >* e = entries;
  710. for( int a = 0; a < i && e; ++a )
  711. e = e->next;
  712. if( e && e->set && e->var )
  713. return (TYP*)e->var;
  714. return (TYP*)0;
  715. }
  716. //! Überprüft, ob ein Element in der Liste enthalten ist
  717. //! \param i Der Index des gesuchten Elementes
  718. //! \return (true), wenn der Index vorhanden ist. (false) sonnst
  719. bool hat( int i ) const
  720. {
  721. return i >= 0 && i < count;
  722. }
  723. RCArray& operator=( const RCArray& arr )
  724. {
  725. leeren();
  726. int anz = arr.getEintragAnzahl();
  727. for( int i = 0; i < anz; i++ )
  728. add( arr.get( i ) );
  729. return *this;
  730. }
  731. };
  732. }
  733. #endif