Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <functional>
  5. #include <cmath>
  6. #include <time.h>
  7. #include <cstdlib>
  8.  
  9. using namespace std;
  10.  
  11. class Person {
  12. public:
  13. string name;
  14. int age;
  15.  
  16. Person() {}
  17.  
  18. Person(int age, string name) {
  19. this->name = name;
  20. this->age = age;
  21. }
  22. };
  23.  
  24. template<class T>
  25. class Node {
  26. public:
  27. Node *next;
  28. Node *prev;
  29. T value;
  30. //Node *node;
  31.  
  32. Node() {
  33. next = NULL;
  34. prev = NULL;
  35. //node->value =
  36. }
  37. };
  38.  
  39. template<class T>
  40. class List {
  41. Node<T> *head;
  42. Node<T> *tail;
  43. int size;
  44. public:
  45. List() {
  46. head = NULL;
  47. tail = NULL;
  48. size = 0;
  49. }
  50.  
  51. ~List() {
  52. Node<T> *tmp1 = head;
  53. Node<T> *tmp2 = tmp1;
  54.  
  55. while (tmp1 != NULL) {
  56. tmp1 = tmp1->next;
  57. delete tmp2;
  58. tmp2 = tmp1;
  59. }
  60. }
  61.  
  62. void addTail(T data) {
  63. Node<T> *node = new Node<T>();
  64. node->value = data;
  65.  
  66. if (head == NULL) {
  67. head = node;
  68. } else {
  69. Node<T> *tmp;
  70. tmp = head;
  71. while (tmp->next != NULL) {
  72. tmp = tmp->next;
  73. }
  74. tmp->next = node;
  75. node->prev = tmp;
  76. }
  77. tail = node;
  78. size++;
  79. }
  80.  
  81. void addHead(T data) {
  82. Node<T> *node = new Node<T>();
  83. node->value = data;
  84.  
  85. if (head) {
  86. head->prev = node;
  87. node->next = head;
  88. head = node;
  89. } else {
  90. head = node;
  91. tail = node;
  92. }
  93. size++;
  94. }
  95.  
  96. void removeTail() {
  97. if (head == NULL) {
  98. return;
  99. }
  100. if (head == tail) {
  101. delete tail;
  102. tail = NULL;
  103. head = NULL;
  104. size--;
  105. return;
  106. }
  107. tail = tail->prev;
  108. delete tail->next;
  109. tail->next = NULL;
  110. size--;
  111. }
  112.  
  113. void removeHead() {
  114.  
  115. if (head == NULL) {
  116. return;
  117. }
  118. if (head == tail) {
  119. delete head;
  120. head = NULL;
  121. tail = NULL;
  122. size--;
  123. return;
  124. }
  125. head = head->next;
  126. delete head->prev;
  127. head->prev = NULL;
  128. size--;
  129. }
  130.  
  131. T get(int index) {
  132. if (index > size) {
  133. throw 0;
  134. }
  135. Node<T> *tmp = head;
  136. for (int i = 0; i < index; i++) {
  137. tmp = tmp->next;
  138. }
  139. return tmp->value;
  140. }
  141.  
  142. void set(int index, T data) {
  143. if (index > size) {
  144. throw 0;
  145. }
  146. Node<T> *tmp = head;
  147. for (int i = 0; i < index; i++) {
  148. tmp = tmp->next;
  149. }
  150. tmp->value = data;
  151. }
  152.  
  153. T *find(T data, function<bool(T, T)> compare) {
  154. Node<T> *tmp = head;
  155. for (int i = 0; i < size; i++) {
  156. if (compare(tmp->value, data)) {
  157. return &tmp->value;
  158. } else {
  159. tmp = tmp->next;
  160. }
  161. }
  162. return NULL;
  163. }
  164.  
  165. bool remove(T data, function<bool(T, T)> compare) {
  166. Node<T> *tmp = head;
  167. for (int i = 0; i < size; i++) {
  168. if (compare(tmp->value, data)) {
  169. if (tmp == tail) {
  170. removeTail();
  171. } else if (tmp == head) {
  172. removeHead();
  173. } else {
  174. tmp->prev->next = tmp->next;
  175. tmp->next->prev = tmp->prev;
  176. delete tmp;
  177. size--;
  178. }
  179. return true;
  180. } else {
  181. tmp = tmp->next;
  182. }
  183. }
  184. return false;
  185. }
  186.  
  187. void addAndSort(T data, function<int(T, T)> compare) {
  188. if (size == 0) {
  189. addHead(data);
  190. return;
  191. }
  192. Node<T> *tmp = head;
  193. for (int i = 0; i < size; i++) {
  194. int x = compare(data, tmp->value);
  195. if (x == 0 || x == 1) {
  196. addBefore(data, tmp);
  197. return;
  198. } else if (tmp->next == NULL) {
  199. addTail(data);
  200. return;
  201. } else {
  202. tmp = tmp->next;
  203. }
  204. }
  205. }
  206.  
  207. void removeAll(bool freeSpace = false) {
  208. int oldSize = size;
  209. for (int i = 0; i < oldSize; i++) {
  210. if (freeSpace) {
  211. //delete head->value;
  212. }
  213. removeHead();
  214. }
  215. }
  216.  
  217. string toString(function<string(T)> f) {
  218. ostringstream result; //zamiana inta na stringa
  219. result << "Size = " << size << endl;
  220. Node<T> *tmp = head;
  221. for (int i = 0; i < size; i++) {
  222. result << i << ": " << f(tmp->value) << endl;
  223. tmp = tmp->next;
  224. }
  225. return result.str();
  226. }
  227.  
  228. private:
  229. void addBefore(T data, Node<T> *current) {
  230. Node<T> *node = new Node<T>();
  231. node->value = data;
  232. if (current == head) {
  233. addHead(data);
  234. return;
  235. }
  236. node->next = current;
  237. node->prev = current->prev;
  238. current->prev->next = node;
  239. current->prev = node;
  240. size++;
  241. }
  242. };
  243.  
  244. bool comparePerson(Person person, Person pattern) {
  245. if ((person.name == pattern.name) && (person.age == pattern.age)) {
  246. return true;
  247. } else {
  248. return false;
  249. }
  250. }
  251.  
  252. int compare(Person newPerson, Person elem) {
  253. if (newPerson.age == elem.age) {
  254. return 0;
  255. }
  256. if (newPerson.age < elem.age) {
  257. return 1;
  258. }
  259. if (newPerson.age > elem.age) {
  260. return -1;
  261. }
  262. }
  263.  
  264. string personToString(Person p) {
  265. ostringstream result; //zamiana inta na stringa
  266. result << "age: " << p.age << ", " << "imie: " << p.name;
  267. return result.str();
  268. }
  269.  
  270. void testList(int n) {
  271. List<Person> l;
  272. Person *persons = new Person[n];
  273.  
  274. clock_t t1 = clock();
  275. for (int i = 0; i < n; ++i) {
  276. // cout << i << "/" << n << endl;
  277. persons[i].age = i + 1;
  278. persons[i].name = "xyz";
  279. l.addTail(persons[i]);
  280. }
  281. clock_t t2 = clock();
  282. double addTime = (t2 - t1) / (double) CLOCKS_PER_SEC;
  283. cout << "czas dodawania: " << addTime << endl;
  284.  
  285. const int m = pow(10, 4); // liczba prob wyszukania
  286. t1 = clock();
  287. for (int i = 0; i < m; i++) {
  288. int age = (rand() % n) + 1;
  289. Person person(age, "xyz");
  290. l.remove(person, compare);
  291. }
  292. t2 = clock();
  293. double removeTime = (t2 - t1) / (double) CLOCKS_PER_SEC;
  294. cout << "czas usuwania: " << addTime << endl;
  295.  
  296.  
  297. delete[] persons;
  298. l.removeAll();
  299. }
  300.  
  301. int main() {
  302.  
  303. srand(time(NULL));
  304.  
  305.  
  306. const int MAX_ORDER = 6;
  307.  
  308. for (int o = 1; o <= MAX_ORDER; o++) {
  309. int n = pow(10, o);
  310. testList(n);
  311. }
  312. //List<Person> list;
  313.  
  314. // List<Person *> list2;
  315. // list2.addHead(new Person(1, "k"));
  316. // list2.removeAll(true);
  317.  
  318.  
  319.  
  320. //cout << list.toString(personToString);
  321.  
  322.  
  323.  
  324. // Person person(4, "a");
  325. // Person person1(6, "b");
  326. // Person person2(10, "c");
  327.  
  328. //
  329. // for (int j = 0; j < 100; j++) {
  330. // list.addHead(persons[j]);
  331. // }
  332. //
  333. // list.remove(persons[44], comparePerson);
  334. //
  335.  
  336. // list.addTail(person);
  337. // list.addTail(person1);
  338. // list.addTail(person);
  339. // list.addAndSort(person, compare);
  340. // list.addAndSort(person2, compare);
  341. // list.addAndSort(person1, compare);
  342.  
  343.  
  344. //Person *found = list.find(person, comparePerson);
  345. //found->age = 9;
  346.  
  347. //cout << list.toString(personToString);
  348.  
  349. return 0;
  350.  
  351. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement