Array.h 13 KB

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