Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <sstream>
- #include <functional>
- #include <cmath>
- #include <time.h>
- #include <cstdlib>
- using namespace std;
- class Person {
- public:
- string name;
- int age;
- Person() {}
- Person(int age, string name) {
- this->name = name;
- this->age = age;
- }
- };
- template<class T>
- class Node {
- public:
- Node *next;
- Node *prev;
- T value;
- //Node *node;
- Node() {
- next = NULL;
- prev = NULL;
- //node->value =
- }
- };
- template<class T>
- class List {
- Node<T> *head;
- Node<T> *tail;
- int size;
- public:
- List() {
- head = NULL;
- tail = NULL;
- size = 0;
- }
- ~List() {
- Node<T> *tmp1 = head;
- Node<T> *tmp2 = tmp1;
- while (tmp1 != NULL) {
- tmp1 = tmp1->next;
- delete tmp2;
- tmp2 = tmp1;
- }
- }
- void addTail(T data) {
- Node<T> *node = new Node<T>();
- node->value = data;
- if (head == NULL) {
- head = node;
- } else {
- Node<T> *tmp;
- tmp = head;
- while (tmp->next != NULL) {
- tmp = tmp->next;
- }
- tmp->next = node;
- node->prev = tmp;
- }
- tail = node;
- size++;
- }
- void addHead(T data) {
- Node<T> *node = new Node<T>();
- node->value = data;
- if (head) {
- head->prev = node;
- node->next = head;
- head = node;
- } else {
- head = node;
- tail = node;
- }
- size++;
- }
- void removeTail() {
- if (head == NULL) {
- return;
- }
- if (head == tail) {
- delete tail;
- tail = NULL;
- head = NULL;
- size--;
- return;
- }
- tail = tail->prev;
- delete tail->next;
- tail->next = NULL;
- size--;
- }
- void removeHead() {
- if (head == NULL) {
- return;
- }
- if (head == tail) {
- delete head;
- head = NULL;
- tail = NULL;
- size--;
- return;
- }
- head = head->next;
- delete head->prev;
- head->prev = NULL;
- size--;
- }
- T get(int index) {
- if (index > size) {
- throw 0;
- }
- Node<T> *tmp = head;
- for (int i = 0; i < index; i++) {
- tmp = tmp->next;
- }
- return tmp->value;
- }
- void set(int index, T data) {
- if (index > size) {
- throw 0;
- }
- Node<T> *tmp = head;
- for (int i = 0; i < index; i++) {
- tmp = tmp->next;
- }
- tmp->value = data;
- }
- T *find(T data, function<bool(T, T)> compare) {
- Node<T> *tmp = head;
- for (int i = 0; i < size; i++) {
- if (compare(tmp->value, data)) {
- return &tmp->value;
- } else {
- tmp = tmp->next;
- }
- }
- return NULL;
- }
- bool remove(T data, function<bool(T, T)> compare) {
- Node<T> *tmp = head;
- for (int i = 0; i < size; i++) {
- if (compare(tmp->value, data)) {
- if (tmp == tail) {
- removeTail();
- } else if (tmp == head) {
- removeHead();
- } else {
- tmp->prev->next = tmp->next;
- tmp->next->prev = tmp->prev;
- delete tmp;
- size--;
- }
- return true;
- } else {
- tmp = tmp->next;
- }
- }
- return false;
- }
- void addAndSort(T data, function<int(T, T)> compare) {
- if (size == 0) {
- addHead(data);
- return;
- }
- Node<T> *tmp = head;
- for (int i = 0; i < size; i++) {
- int x = compare(data, tmp->value);
- if (x == 0 || x == 1) {
- addBefore(data, tmp);
- return;
- } else if (tmp->next == NULL) {
- addTail(data);
- return;
- } else {
- tmp = tmp->next;
- }
- }
- }
- void removeAll(bool freeSpace = false) {
- int oldSize = size;
- for (int i = 0; i < oldSize; i++) {
- if (freeSpace) {
- //delete head->value;
- }
- removeHead();
- }
- }
- string toString(function<string(T)> f) {
- ostringstream result; //zamiana inta na stringa
- result << "Size = " << size << endl;
- Node<T> *tmp = head;
- for (int i = 0; i < size; i++) {
- result << i << ": " << f(tmp->value) << endl;
- tmp = tmp->next;
- }
- return result.str();
- }
- private:
- void addBefore(T data, Node<T> *current) {
- Node<T> *node = new Node<T>();
- node->value = data;
- if (current == head) {
- addHead(data);
- return;
- }
- node->next = current;
- node->prev = current->prev;
- current->prev->next = node;
- current->prev = node;
- size++;
- }
- };
- bool comparePerson(Person person, Person pattern) {
- if ((person.name == pattern.name) && (person.age == pattern.age)) {
- return true;
- } else {
- return false;
- }
- }
- int compare(Person newPerson, Person elem) {
- if (newPerson.age == elem.age) {
- return 0;
- }
- if (newPerson.age < elem.age) {
- return 1;
- }
- if (newPerson.age > elem.age) {
- return -1;
- }
- }
- string personToString(Person p) {
- ostringstream result; //zamiana inta na stringa
- result << "age: " << p.age << ", " << "imie: " << p.name;
- return result.str();
- }
- void testList(int n) {
- List<Person> l;
- Person *persons = new Person[n];
- clock_t t1 = clock();
- for (int i = 0; i < n; ++i) {
- // cout << i << "/" << n << endl;
- persons[i].age = i + 1;
- persons[i].name = "xyz";
- l.addTail(persons[i]);
- }
- clock_t t2 = clock();
- double addTime = (t2 - t1) / (double) CLOCKS_PER_SEC;
- cout << "czas dodawania: " << addTime << endl;
- const int m = pow(10, 4); // liczba prob wyszukania
- t1 = clock();
- for (int i = 0; i < m; i++) {
- int age = (rand() % n) + 1;
- Person person(age, "xyz");
- l.remove(person, compare);
- }
- t2 = clock();
- double removeTime = (t2 - t1) / (double) CLOCKS_PER_SEC;
- cout << "czas usuwania: " << addTime << endl;
- delete[] persons;
- l.removeAll();
- }
- int main() {
- srand(time(NULL));
- const int MAX_ORDER = 6;
- for (int o = 1; o <= MAX_ORDER; o++) {
- int n = pow(10, o);
- testList(n);
- }
- //List<Person> list;
- // List<Person *> list2;
- // list2.addHead(new Person(1, "k"));
- // list2.removeAll(true);
- //cout << list.toString(personToString);
- // Person person(4, "a");
- // Person person1(6, "b");
- // Person person2(10, "c");
- //
- // for (int j = 0; j < 100; j++) {
- // list.addHead(persons[j]);
- // }
- //
- // list.remove(persons[44], comparePerson);
- //
- // list.addTail(person);
- // list.addTail(person1);
- // list.addTail(person);
- // list.addAndSort(person, compare);
- // list.addAndSort(person2, compare);
- // list.addAndSort(person1, compare);
- //Person *found = list.find(person, comparePerson);
- //found->age = 9;
- //cout << list.toString(personToString);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement