From f279107065146a4940f5e73602a1c3c09e58b31d Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sun, 18 Oct 2020 18:56:43 +0200 Subject: chore: name of first year folder --- 1_anno/Programmazione_2/data_structures/bfs.cc | 186 +++++++++++++++++ 1_anno/Programmazione_2/data_structures/bst.cc | 225 +++++++++++++++++++++ .../data_structures/circle_double_list.cc | 185 +++++++++++++++++ .../data_structures/circle_list.cc | 189 +++++++++++++++++ 1_anno/Programmazione_2/data_structures/dfs.cc | 191 +++++++++++++++++ 1_anno/Programmazione_2/data_structures/graph.cc | 164 +++++++++++++++ .../Programmazione_2/data_structures/graph_stl.cc | 221 ++++++++++++++++++++ 1_anno/Programmazione_2/data_structures/list.cc | 164 +++++++++++++++ .../data_structures/list_double.cc | 182 +++++++++++++++++ .../data_structures/matrix-graph.cc | 81 ++++++++ 1_anno/Programmazione_2/data_structures/queue.cc | 72 +++++++ .../data_structures/queue_w_array.cc | 66 ++++++ 1_anno/Programmazione_2/data_structures/stack.cc | 70 +++++++ .../data_structures/stack_w_array.cc | 50 +++++ .../Programmazione_2/data_structures/top-sort.cc | 212 +++++++++++++++++++ 15 files changed, 2258 insertions(+) create mode 100644 1_anno/Programmazione_2/data_structures/bfs.cc create mode 100644 1_anno/Programmazione_2/data_structures/bst.cc create mode 100644 1_anno/Programmazione_2/data_structures/circle_double_list.cc create mode 100644 1_anno/Programmazione_2/data_structures/circle_list.cc create mode 100644 1_anno/Programmazione_2/data_structures/dfs.cc create mode 100644 1_anno/Programmazione_2/data_structures/graph.cc create mode 100644 1_anno/Programmazione_2/data_structures/graph_stl.cc create mode 100644 1_anno/Programmazione_2/data_structures/list.cc create mode 100644 1_anno/Programmazione_2/data_structures/list_double.cc create mode 100644 1_anno/Programmazione_2/data_structures/matrix-graph.cc create mode 100644 1_anno/Programmazione_2/data_structures/queue.cc create mode 100644 1_anno/Programmazione_2/data_structures/queue_w_array.cc create mode 100644 1_anno/Programmazione_2/data_structures/stack.cc create mode 100644 1_anno/Programmazione_2/data_structures/stack_w_array.cc create mode 100644 1_anno/Programmazione_2/data_structures/top-sort.cc (limited to '1_anno/Programmazione_2/data_structures') diff --git a/1_anno/Programmazione_2/data_structures/bfs.cc b/1_anno/Programmazione_2/data_structures/bfs.cc new file mode 100644 index 0000000..2b4efbd --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/bfs.cc @@ -0,0 +1,186 @@ +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +public: + +private: + int _len, _nodes, _edges; + int* _parents; + int* _distances; + H** _k; // it works like a dictionary, it saves the keys + list** _adj; + int _index(H val) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == val) return i; + + return -1; + } +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new list*[_len]; + _parents = new int[_len]; + _distances = new int[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* add_node(H k) { + if(_nodes == _len) return this; + if(_index(k) >= 0) return this; // node is already there + + _k[_nodes++] = new H(k); + + return this; + } + + void bfs(int s) { + int colors[_len]; + queue q; + + for(int i = 0; i < _nodes; ++i) { + colors[i] = W; + _parents[i] = -1; + _distances[i] = 999999999; + } + q.push(s); + colors[s] = G; + _distances[s] = 0; + while(!q.empty()) { + int x = q.front(); + q.pop(); + for(auto const& j : _adj[x]->as_vector()) { + if(colors[j] == W) { + colors[j] = G; + q.push(j); + _parents[j] = x; + _distances[j] = _distances[x] + 1; + } + } + colors[x] = B; + } + + for(int i = 0; i < _nodes; ++i) { + cout << "[" << i << "]->"; + if(_distances[i]==999999999) cout << "inf." << endl; + else cout << _distances[i] << endl; + } + } + + void bfs(H x) { + int s = _index(x); + if(s != -1) + bfs(s); + } + + graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + + if(!_adj[i]->search(j)) { + _adj[i]->push(j); + _edges++; + } + + return this; + } + + void print() { + for(int i = 0; i < _nodes; ++i) { + cout << "(" << i << ", " << *_k[i] << "): "; + for(auto const& j : _adj[i]->as_vector()) + cout << "(" << j << ", " << *_k[j] << "), "; + cout << '\n'; + } + } +}; + + +int main() { + graph* g = new graph(5); + g->add_node("hello")->add_node("greg")->add_node("yes"); + g->add_node("nop")->add_node("ok"); + g->add_edge("hello", "ok"); + g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); + g->add_edge("yes", "nop"); + g->print(); + g->bfs("hello"); + + delete g; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/bst.cc b/1_anno/Programmazione_2/data_structures/bst.cc new file mode 100644 index 0000000..9223e04 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/bst.cc @@ -0,0 +1,225 @@ +#include + +using namespace std; + +template +struct node { + T key; + node* prev; + node* right; + node* left; +}; + +template +class bst { +public: + bst() : root{nullptr} {} + + ~bst() { + // TODO + } + + bst* insert(initializer_list&& list) { + for(auto const& i : list) + insert(i); + + return this; + } + + bst* insert(T k) { + node* nodus = new node{k, nullptr, nullptr, nullptr}; + node* iter = root; + node* prev = nullptr; + + while(iter) { + prev = iter; + iter = (k < iter->key) ? iter->left : iter->right; + } + + nodus->prev = prev; + if(!prev) + root = nodus; + else if(k < prev->key) + prev->left = nodus; + else + prev->right = nodus; + + return this; + } + + bst* remove(initializer_list&& list) { + for(auto const& i : list) + remove(i); + + return this; + } + + bst* remove(T k) { + node* nodus = search(k); + if(!nodus) return this; + + if(!nodus->left) { + _transplant(nodus, nodus->right); + } else if(!nodus->right) { + _transplant(nodus, nodus->left); + } else { + node* iter = _min(nodus->right); + if(iter->prev != nodus) { + _transplant(iter, iter->right); + iter->right = nodus->right; + iter->right->prev = iter; + } + _transplant(nodus, iter); + iter->left = nodus->left; + iter->left->prev = iter; + } + + delete nodus; + return this; + } + + node* min() { + return _min(root); + } + + node* min(node* nodus) { + return _min(nodus); + } + + node* max() { + return _max(root); + } + + node* max(node* nodus) { + return _max(nodus); + } + + node* search(T k) { + node* iter = root; + while(iter && iter->key != k) + iter = (iter->key > k) ? iter->left : iter->right; + + return iter; + } + + node* successor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->right) + return min(nodus->right); + + node* prev = nodus->prev; + while(prev && nodus == prev->right) { + nodus = prev; + prev = prev->prev; + } + + return prev; + + } + node* predecessor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->left) + return max(nodus->left); + + node* prev = nodus->prev; + while(prev && nodus == prev->left) { + nodus = prev; + prev = prev->prev; + } + + return prev; + } + + friend ostream& operator<<(ostream& os, bst* tree) { + tree->_preorder(os, tree->root); + return os; + } +private: + void _transplant(node* u, node* v) { + if(!u->prev) { + root = v; + } else if(u == u->prev->left) { + u->prev->left = v; + } else { + u->prev->right = v; + } + + if(v) + v->prev = u->prev; + } + + node* _min(node* root) { + node* iter = root; + while(iter && iter->left) + iter = iter->left; + + return iter; + } + + node* _max(node* root) { + node* iter = root; + while(iter && iter->right) + iter = iter->right; + + return iter; + } + + void _inorder(ostream& os, node* root) { + if(root) { + _inorder(os, root->left); + os << root->key << ' '; + _inorder(os, root->right); + } + } + + void _preorder(ostream& os, node* root) { + if(root) { + os << root->key << ' '; + _inorder(os, root->left); + _inorder(os, root->right); + } + } + + void _postorder(ostream& os, node* root) { + if(root) { + _inorder(os, root->left); + _inorder(os, root->right); + os << root->key << ' '; + } + } + node* root; +}; + +int main() { + bst* b = new bst{}; + + // b->insert(12)->insert(5)->insert(18)->insert(2)->insert(9); + // b->insert(15)->insert(13)->insert(17)->insert(19); + + b->insert({12, 5, 18, 2, 9, 15, 13, 17, 19}); + cout << b << endl; + cout << (b->search(5) != nullptr) << endl; + cout << (b->search(1) != nullptr) << endl; + cout << b->max()->key << ' ' << b->min()->key << endl; + for(auto const& i : {12, 9, 14, 18}) { + auto elem = b->successor(i); + if(elem) + cout << "(" << i << ", " << elem->key << ") "; + } + cout << endl; + + for(auto const& i : {9, 2, 5, 15, 18, 12, 19}) { + auto elem = b->predecessor(i); + if(elem) + cout << "(" << i << ", " << elem->key << ") "; + } + cout << endl; + b->remove({5, 12}); + cout << b << endl; + + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/circle_double_list.cc b/1_anno/Programmazione_2/data_structures/circle_double_list.cc new file mode 100644 index 0000000..f162e57 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/circle_double_list.cc @@ -0,0 +1,185 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* prev; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + node* iter = _head; + while(iter->next != _head) { + node* tmp = iter; + delete tmp; + iter = iter->next; + } + node* tmp = iter; + delete tmp; + } + + list* push_front(T val) { + auto elem = _last(); + if(!_head) { + _head = new node{val, nullptr, nullptr}; + _head->prev = _head->next = _head; + } else { + _head = new node{val, elem, _head}; + elem->next = _head->next->prev = _head; + } + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + auto last_e = _last(); + last_e->next = new node{val, last_e, _head}; + _head->prev = last_e->next; + + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _search(val); + if(iter) { + node* nod = new node{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + } + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + node* nod = new node{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + if(elem == _head) return this->pop_front(); + + node* iter = elem->prev; + node* temp = iter->next; + iter->next = iter->next->next; + iter->next->prev = iter; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + auto last_e = _last(); + node* elem = _head; + _head = _head->next; + _head->prev = last_e; + last_e->next = _head; + delete elem; + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + auto last_e = _last(); + + if(last_e == _head) { + delete _head; + _head = nullptr; + } else { + auto iter = last_e->prev; + delete iter->next; + iter->next = _head; + _head->prev = iter; + } + + return this; + } + + void print() { + node* iter = _head; + while(iter != nullptr) { + cout << iter->value << ' '; + cout << "[[ " << iter->prev->value << ", "; + cout << iter->next->value << " ]], "; + iter = iter->next; + if(iter == _head) break; + } + } +private: + node* _last() { + node* iter = _head; + while(iter && iter->next != _head) { + iter = iter->next; + } + + return iter; + } + + node* _search(T val) { + node* iter = _head; + if(iter->value == val) return iter; + + while(iter && iter->value != val) { + iter = iter->next; + if(iter == _head) return nullptr; + } + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + l->push_front(2); + l->push_back(1)->push_back(3); + l->push_front(5)->push_front(9); + l->push_back(0)->push_back(6); + l->print(); cout << '\n'; + l->push_after_value(7, -2); + l->push_before_value(9, 10); + l->print(); cout << '\n'; + l->pop_front(); + l->pop_front(); + l->pop_back(); + l->pop_front(); + l->print(); cout << '\n'; + l->pop(2); + l->print(); cout << '\n'; + + delete l; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/circle_list.cc b/1_anno/Programmazione_2/data_structures/circle_list.cc new file mode 100644 index 0000000..2143ac1 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/circle_list.cc @@ -0,0 +1,189 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + node* iter = _head; + while(iter->next != _head) { + node* tmp = iter; + delete tmp; + iter = iter->next; + } + node* tmp = iter; + delete tmp; + } + + list* push_front(T val) { + auto elem = _last(); + _head = new node{val, _head}; + if(!elem) + elem = _head; + + elem->next = _head; + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + auto last_e = _last(); + last_e->next = new node{val, _head}; + + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _search(val); + if(iter) + iter->next = new node{newval, iter->next}; + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + iter->next = new node{newval, iter->next}; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + if(iter == elem) return this->pop_front(); + + while(iter->next != elem) + iter = iter->next; + + node* temp = iter->next; + iter->next = iter->next->next; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + auto last_e = _last(); + + if(last_e == _head) { + delete _head; + _head = nullptr; + } else { + node* elem = _head; + _head = _head->next; + last_e->next = _head; + delete elem; + } + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + node* iter = _head; + auto last_e = _last(); + + if(last_e == _head) { + delete iter; + _head = nullptr; + } else { + while(iter->next != last_e) { + iter = iter->next; + } + + delete iter->next; + iter->next = _head; + } + + return this; + } + + void print() { + node* iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + if(iter == _head) break; + } + } +private: + node* _last() { + node* iter = _head; + while(iter && iter->next != _head) { + iter = iter->next; + } + + return iter; + } + + node* _search(T val) { + node* iter = _head; + if(iter->value == val) return iter; + + while(iter && iter->value != val) { + iter = iter->next; + if(iter == _head) return nullptr; + } + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + l->push_before_value(4, 1); + l->push_back(4); + l->push_back(1); + l->push_back(0); + l->push_front(2); + l->print(); cout << endl; + l->pop_back(); + l->print(); cout << endl; + l->pop_front(); + l->print(); cout << endl; + l->pop_back(); + l->print(); cout << endl; + l->push_front(3); + l->print(); cout << endl; + l->push_after_value(4, 7); + l->print(); cout << endl; + l->push_before_value(3, 5); + l->print(); cout << endl; + l->pop(5); + l->print(); cout << endl; + + delete l; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/dfs.cc b/1_anno/Programmazione_2/data_structures/dfs.cc new file mode 100644 index 0000000..744f153 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/dfs.cc @@ -0,0 +1,191 @@ +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +private: + int _len, _nodes, _edges; + int* _parents; + int* _radixes; + int* _distances; + int* _finishes; + int* _colors; + int _time; + int _current; + H** _k; // it works like a dictionary, it saves the keys + list** _adj; + int _index(H val) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == val) return i; + + return -1; + } + void _dfsvisit(int u) { + _colors[u] = G; + _distances[u] = _time++; + _radixes[u] = _current; + for(auto const& v : _adj[u]->as_vector()) { + if(_colors[v] == W) { + _parents[v] = u; + _dfsvisit(v); + } + } + _colors[u] = B; + _finishes[u] = _time++; + } +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new list*[_len]; + _parents = new int[_len]; + _radixes = new int[_len]; + _distances = new int[_len]; + _finishes = new int[_len]; + _colors = new int[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* add_node(H k) { + if(_nodes == _len) return this; + if(_index(k) >= 0) return this; // node is already there + + _k[_nodes++] = new H(k); + + return this; + } + + + void dfs() { + _time = 0; + for(int i = 0; i < _nodes; ++i) { + _colors[i] = W; + _parents[i] = -1; + } + + for(int i = 0; i < _nodes; ++i) { + if(_colors[i] == W) { + _current = i; + _dfsvisit(i); + } + } + for(int i = 0; i < _nodes; ++i) { + cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl; + } + } + + graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + + if(!_adj[i]->search(j)) { + _adj[i]->push(j); + _edges++; + } + + return this; + } + + void print() { + for(int i = 0; i < _nodes; ++i) { + cout << "(" << i << ", " << *_k[i] << "): "; + for(auto const& j : _adj[i]->as_vector()) + cout << "(" << j << ", " << *_k[j] << "), "; + cout << '\n'; + } + } +}; + + +int main() { + graph* g = new graph(6); + g->add_node('u')->add_node('v')->add_node('x')->add_node('y'); + g->add_node('w')->add_node('z'); + g->add_edge('u', 'v'); + g->add_edge('u', 'x'); + g->add_edge('x', 'v'); + g->add_edge('y', 'x'); + g->add_edge('v', 'y'); + g->add_edge('w', 'y'); + g->add_edge('w', 'z'); + g->add_edge('z', 'z'); + + g->print(); + g->dfs(); + + delete g; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/graph.cc b/1_anno/Programmazione_2/data_structures/graph.cc new file mode 100644 index 0000000..12837be --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/graph.cc @@ -0,0 +1,164 @@ +#include +#include + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + list* pop(H val) { + auto elem = search(val); + if(!elem) + return this; + + auto iter = _head; + // This is the case when head is the element we want to pop + if(iter == elem) { + delete _head; + _head = nullptr; + return this; + } + + while(iter && iter->next() != elem) + iter = iter->next(); + + auto tmp = iter->next(); + if(iter->next()->next()) { + iter->next() = iter->next()->next(); + } else { // the element we want to pop is the tail + iter->next() = nullptr; + } + delete tmp; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +public: + +private: + int _len, _nodes, _edges; + H **_k; + list **_adj; + int _index(H val) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == val) return i; + + return -1; + } +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new list*[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* add_node(H k) { + if(_nodes == _len) return this; + if(_index(k) >= 0) return this; // node is already there + + _k[_nodes++] = new H(k); + + return this; + } + + graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + + if(!_adj[i]->search(j)) { + _adj[i]->push(j); + _edges++; + } + + return this; + } + + void print() { + for(int i = 0; i < _nodes; ++i) { + cout << "(" << i << ", " << *_k[i] << "): "; + for(auto const& j : _adj[i]->as_vector()) + cout << "(" << j << ", " << *_k[j] << "), "; + cout << '\n'; + } + } +}; + + +int main() { + graph* g = new graph(5); + g->add_node("hello")->add_node("greg")->add_node("yes"); + g->add_node("nop")->add_node("ok"); + g->add_edge("hello", "ok"); + g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); + g->add_edge("yes", "nop"); + g->print(); + + delete g; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/graph_stl.cc b/1_anno/Programmazione_2/data_structures/graph_stl.cc new file mode 100644 index 0000000..5381747 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/graph_stl.cc @@ -0,0 +1,221 @@ +#include +#include +#include +#include +#include +#define INF 99999999 +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class graph { +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new vector[len]; + _colors = new int[len]; + _d = new int[len]; + _f = new int[len]; + _p = new int[len]; + + for(int i = 0; i < len; ++i) { + _k[i] = nullptr; + } + } + ~graph() { + delete[] _k; + delete[] _adj; + } + + graph* add_node(H x) { + if(_index(x) > -1) return this; + if(_nodes == _len) return this; + _k[_nodes++] = new H(x); + + return this; + } + graph* add_edge(H u, H v) { + int i = _index(u); + int j = _index(v); + if(i < 0 || j < 0) return this; + + if(find(_adj[i].begin(), _adj[i].end(), j) == _adj[i].end()) { + _adj[i].push_back(j); + } + return this; + } + void print() { + for(int i = 0; i < _nodes; ++i) { + cout << "(" << *_k[i] << ", " << i << "): "; + for(auto const& j : _adj[i]) { + cout << "(" << *_k[j] << ", " << j << ") "; + } + cout << endl; + } + } + void dfsvisit(int u, bool visited[]) { + visited[u] = true; + cout << "(" << *_k[u] << ", " << u << ") "; + for(auto const& i : _adj[u]) { + if(!visited[i]) + dfsvisit(i, visited); + } + } + int dfsvisit(int u) { + int cycle = 0; + _colors[u] = G; + _d[u] = _time++; + + for(auto const& j : _adj[u]) { + if(_colors[j] == W) + cycle |= dfsvisit(j); + } + + _colors[u] = B; + _stack.push(u); + _f[u] = _time++; + return cycle; + } + int dfs() { + int cycle = 0; + for(int i = 0; i < _nodes; ++i) { + _colors[i] = W; + } + _time = 0; + for(int i = 0; i < _nodes; ++i) { + if(_colors[i] == W) + cycle |= dfsvisit(i); + else if(_colors[i] == G) + cycle = 1; + } + for(int i = 0; i < _nodes; ++i) { + cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "," << _f[i] << "]" << endl; + } + return cycle; + } + + void top_sort() { + int cycle = dfs(); + if(cycle) { + cout << "cyclic graph!" << endl; + return; + } + int* s = new int[_nodes]; + for(int i = 0; i < _nodes; ++i) s[i] = i; + _sort(s, _nodes, _f); + for(int i = 0; i < _nodes; ++i) { + cout << "(" << s[i] << ", " << _f[s[i]] << ") "; + } + + } + + void bfs(H v) { + int s = _index(v); + if(s < 0) return; + + for(int i = 0; i < _nodes; ++i) { + _colors[i] = W; + _d[i] = INF; + _p[i] = -1; + } + _colors[s] = G; + _d[s] = 0; + queue q; + q.push(s); + while(!q.empty()) { + int u = q.front(); + q.pop(); + for(auto const& j : _adj[u]) { + if(_colors[j] == W) { + _colors[j] = G; + _d[j] = _d[u]+1; + _p[j] = u; + q.push(j); + } + } + _colors[u] = B; + } + for(int i = 0; i < _nodes; ++i) { + cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "]" << endl; + } + } + void ssc() { + dfs(); + cout << endl << endl; + auto gr = _transpose(); + bool* visited = new bool[_nodes]; + for(int i = 0; i < _nodes; ++i) + visited[i] = false; + + while(!_stack.empty()) { + int v = _stack.top(); + _stack.pop(); + if(!visited[v]) { + gr->dfsvisit(v, visited); + cout << endl; + } + } + delete[] visited; + } +private: + graph* _transpose() { + graph* g = new graph{_len}; + for(int i = 0; i < _nodes; ++i) { + g->add_node(*_k[i]); + } + + for(int i = 0; i < _nodes; ++i) { + for(auto const& j : _adj[i]) { + g->add_edge(j, i); + } + } + + return g; + } + void _sort(int* d, int n, int* s) { + for(int i = -1; i < n; ++i) { + int j = i-1; + while(j > -1 && s[d[j+1]]>s[d[j]]) { + swap(d[s[j+1]], d[s[j]]); + --j; + } + } + } + int _index(H x) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == x) return i; + + return -1; + } + stack _stack; + H** _k; + vector* _adj; + int _len, _nodes, _edges; + int* _colors; + int _time; + int* _d; + int* _f; + int* _p; +}; + +int main() { + graph* g = new graph{5}; + for(auto const& i : {0, 1, 2, 3, 4}) + g->add_node(i); + g->add_edge(1, 0); + g->add_edge(2, 1); + g->add_edge(0, 2); + g->add_edge(0, 3); + g->add_edge(3, 4); + //g->print(); + cout << endl; + //g->top_sort(); + g->ssc(); + cout << endl; + //g->bfs(0); + delete g; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/list.cc b/1_anno/Programmazione_2/data_structures/list.cc new file mode 100644 index 0000000..8ddcbf9 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/list.cc @@ -0,0 +1,164 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + while(_head) { + node* tmp = _head->next; + delete tmp; + _head = tmp; + } + } + + list* push_front(T val) { + _head = new node{val, _head}; + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + node* iter = _head; + while(iter->next) { + iter = iter->next; + } + iter->next = new node{val, nullptr}; + + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _search(val); + if(iter) + iter->next = new node{newval, iter->next}; + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + iter->next = new node{newval, iter->next}; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + if(iter == elem) return this->pop_front(); + + while(iter->next != elem) + iter = iter->next; + + node* temp = iter->next; + iter->next = iter->next->next; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + node* elem = _head; + _head = _head->next; + delete elem; + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + node* iter = _head; + + while(iter->next && iter->next->next) { + iter = iter->next; + } + + if(!iter->next) { + delete iter; + _head = nullptr; + } else if(iter->next->next) { + delete iter->next->next; + } else { + delete iter->next; + } + + iter->next = nullptr; + + return this; + } + + void print() { + node* iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + } + } +private: + node* _search(T value) { + node* iter = _head; + while(iter && iter->value != value) + iter = iter->next; + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + l->push_front(2)->push_front(1); + l->print(); cout << endl; + l->push_back(5); + l->print(); cout << endl; + l->push_back(10)->push_back(15); + l->print(); cout << endl; + l->push_after_value(5, 6); + l->print(); cout << endl; + l->push_before_value(5, 4); + l->print(); cout << endl; + l->push_before_value(4, 3); + l->print(); cout << endl; + l->pop_back(); + l->print(); cout << endl; + l->pop_front(); + l->print(); cout << endl; + l->push_front(1); + l->print(); cout << endl; + l->pop(1); + l->print(); cout << endl; + + delete l; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/list_double.cc b/1_anno/Programmazione_2/data_structures/list_double.cc new file mode 100644 index 0000000..fa0af26 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/list_double.cc @@ -0,0 +1,182 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* prev; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + while(_head != nullptr) { + node* tmp = _head->next; + delete tmp; + _head = tmp; + } + } + + list* push_front(T val) { + if(!_head) { + _head = new node{val, nullptr, nullptr}; + } else { + _head = new node{val, nullptr, _head}; + _head->next->prev = _head; + } + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + node* iter = _head; + while(iter->next) { + iter = iter->next; + } + iter->next = new node{val, iter, nullptr}; + + return this; + } + + list* push_after_value(T val, T newval) { + node* elem = _search(val); + if(elem) { + node* nod = new node{newval, elem, elem->next}; + elem->next = nod; + nod->next->prev = nod; + } + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + node* nod = new node{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + if(elem == _head) return this->pop_front(); + + node* iter = elem->prev; + node* temp = iter->next; + iter->next = iter->next->next; + iter->next->prev = iter; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + node* elem = _head; + _head = _head->next; + _head->prev = nullptr; + delete elem; + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + node* iter = _last()->prev; + + if(iter->next == nullptr) { + delete iter; + _head = nullptr; + } else if(iter->next->next) { + delete iter->next->next; + } else { + delete iter->next; + } + + iter->next = nullptr; + + return this; + } + + void print() { + node* iter = _head; + while(iter) { + cout << iter->value << ' '; + cout << "[[ " << (iter->prev!=nullptr ? iter->prev->value : -1) << ", "; + cout << (iter->next!=nullptr ? iter->next->value : -1) << " ]], "; + iter = iter->next; + } + } +private: + node* _last() { + node* iter = _head; + while(iter->next) { + iter = iter->next; + } + + return iter; + } + + node* _search(T value) { + node* iter = _head; + while(iter && iter->value != value) + iter = iter->next; + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + l->push_front(2)->push_front(1); + l->print(); cout << endl; + l->push_back(5); + l->print(); cout << endl; + l->push_back(10)->push_back(15); + l->print(); cout << endl; + l->push_after_value(5, 6); + l->print(); cout << endl; + l->push_after_value(5, 7); + l->print(); cout << endl; + l->push_before_value(5, 4); + l->print(); cout << endl; + l->push_before_value(5, 3); + l->print(); cout << endl; + l->pop_back(); + l->print(); cout << endl; + l->pop_front(); + l->print(); cout << endl; + l->pop(2); + l->print(); cout << endl; + + delete l; + + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/matrix-graph.cc b/1_anno/Programmazione_2/data_structures/matrix-graph.cc new file mode 100644 index 0000000..a644ec1 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/matrix-graph.cc @@ -0,0 +1,81 @@ +#include +#include + +using namespace std; + +template +class matrix_graph { +public: + ~matrix_graph() { + delete[] _m; + delete[] _k; + } + matrix_graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _m = new int*[len]; + _k = new H*[len]; + for(int i = 0; i < len; ++i) { + _m[i] = new int[len]; + _k[i] = nullptr; + for(int j = 0; j < len; ++j) + _m[i][j] = 0; + } + } + + matrix_graph* add_node(H k) { + if(_len == _nodes) return this; // no more space for new nodes + if(_index(k) > -1) return this; // nodes already exists + + _k[_nodes++] = new H(k); + + return this; + } + + matrix_graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + if(!_m[i][j]) { + _m[i][j] = 1; + _edges++; + } + return this; + } + void print() { + for(int i = 0; i < _len; ++i) { + cout << i << ' ' << *_k[i] << ": "; + for(int j = 0; j < _len; ++j) { + if(_m[i][j]) + cout << *_k[j] << ' '; + } + cout << '\n'; + } + cout << endl; + for(int i = 0; i < _len; ++i) { + for(int j = 0; j < _len; ++j) { + cout << _m[i][j] << ' '; + } + cout << '\n'; + } + } +private: + int _len, _nodes, _edges; + int** _m; + H** _k; + int _index(H x) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == x) return i; + return -1; + } +}; + +int main() { + matrix_graph* g = new matrix_graph(5); + g->add_node("hello")->add_node("greg")->add_node("yes"); + g->add_node("nop")->add_node("ok"); + g->add_edge("hello", "ok"); + g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes"); + g->add_edge("yes", "nop"); + g->print(); + delete g; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/queue.cc b/1_anno/Programmazione_2/data_structures/queue.cc new file mode 100644 index 0000000..8398459 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/queue.cc @@ -0,0 +1,72 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + +template +class queue { +public: + queue() : _head{nullptr} {} + + ~queue() { + auto iter = _head; + while(iter) { + delete iter; + iter = iter->next; + } + } + + queue* enqueue(T val) { + + if(!_head) { + _head = new node{val, nullptr}; + _tail = _head; + } else { + _tail->next = new node{val, nullptr}; + _tail = _tail->next; + } + + return this; + } + + node* dequeue() { + if(!_head) return nullptr; + auto iter = _head; + delete _head; + _head = iter->next; + return iter; + } + + void print() { + auto iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + } + cout << endl; + } +private: + node* _head; + node* _tail; +}; + +int main() { + queue* q = new queue(); + + q->dequeue(); + q->enqueue(4)->enqueue(2)->enqueue(8); + q->print(); + auto e = q->dequeue(); + if(e) + cout << e->value << endl; + q->enqueue(1); + q->print(); + + delete q; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/queue_w_array.cc b/1_anno/Programmazione_2/data_structures/queue_w_array.cc new file mode 100644 index 0000000..fb92d68 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/queue_w_array.cc @@ -0,0 +1,66 @@ +#include + +using namespace std; + +template +class queue { +public: + queue(int n) : _size{n}, _counter{0}, _head{0}, _tail{0} { + _arr = new H[n]; + } + ~queue() { + delete _arr; + } + bool is_empty() { + return _counter == 0; + } + bool is_full() { + return _counter == _size; + } + + queue* enqueue(H x) { + if(!is_full()) { + _arr[_tail] = x; + if(_tail == _size-1) + _tail = 0; + else + ++_tail; + _counter++; + } + + return this; + } + H dequeue() { + if(is_empty()) return -1; + H x = _arr[_head]; + + if(_head == _size-1) + _head = 0; + else + ++_head; + + _counter--; + return x; + } +private: + H* _arr; + int _size; + short _counter; + short _head; + short _tail; +}; + +int main() { + queue* q = new queue{4}; + q->enqueue(5)->enqueue(13)->enqueue(3); + cout << q->dequeue() << '\n'; + q->enqueue(4)->enqueue(6)->enqueue(7); + q->dequeue(); + q->enqueue(7); + + for(int i = 0; i < 6; ++i) { + cout << q->dequeue() << ' '; + } + delete q; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/stack.cc b/1_anno/Programmazione_2/data_structures/stack.cc new file mode 100644 index 0000000..ffff780 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/stack.cc @@ -0,0 +1,70 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + +template +class stack { +public: + stack() : _head{nullptr} {} + + ~stack() { + auto iter = _head; + while(iter) { + delete iter; + iter = iter->next; + } + } + + stack* push(T val) { + + if(!_head) { + _head = new node{val, nullptr}; + } else { + _head = new node{val, _head}; + } + + return this; + } + + node* pop() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next; + + return elem; + } + + void print() { + auto iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + } + cout << endl; + } +private: + node* _head; +}; + +int main() { + stack* s = new stack(); + + s->pop(); + s->push(4)->push(2)->push(8); + s->print(); + auto e = s->pop(); + if(e) + cout << e->value << endl; + s->push(1); + s->print(); + + delete s; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/stack_w_array.cc b/1_anno/Programmazione_2/data_structures/stack_w_array.cc new file mode 100644 index 0000000..c20db90 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/stack_w_array.cc @@ -0,0 +1,50 @@ +#include + +using namespace std; + +template +class stack { +public: + stack(int n) : _size{n}, _top{-1} { + _arr = new H[n]; + } + ~stack() { + delete _arr; + } + bool is_empty() { + return _top == -1; + } + bool is_full() { + return _top == _size-1; + } + stack* push(H x) { + if(!is_full()) { + _arr[++_top] = x; + } + return this; + } + H pop() { + if(is_empty()) + return -1; + _top--; + return _arr[_top+1]; + } +private: + int _size; + H* _arr; + short _top; +}; + +int main() { + stack* s = new stack{7}; + + s->push(15)->push(6)->push(2)->push(9)->push(17)->push(3); + cout << s->pop() << '\n'; + s->push(18)->push(19)->push(12); + + for(int i = 0; i < 7; ++i) + cout << s->pop() << ' '; + + delete s; + return 0; +} diff --git a/1_anno/Programmazione_2/data_structures/top-sort.cc b/1_anno/Programmazione_2/data_structures/top-sort.cc new file mode 100644 index 0000000..7441ee9 --- /dev/null +++ b/1_anno/Programmazione_2/data_structures/top-sort.cc @@ -0,0 +1,212 @@ + +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +private: + int _len, _nodes, _edges; + int* _parents; + int* _radixes; + int* _distances; + int* _finishes; + int* _colors; + int _time; + int _current; + H** _k; // it works like a dictionary, it saves the keys + list** _adj; + int _index(H val) { + for(int i = 0; i < _nodes; ++i) + if(*_k[i] == val) return i; + + return -1; + } + bool _dfsvisit(int u) { + bool cycle = false; + _colors[u] = G; + _distances[u] = _time++; + _radixes[u] = _current; + for(auto const& v : _adj[u]->as_vector()) { + if(_colors[v] == W) { + _parents[v] = u; + _dfsvisit(v); + } else if(_colors[v] == G) { + cycle = true; + } + } + _colors[u] = B; + _finishes[u] = _time++; + return cycle; + } +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new list*[_len]; + _parents = new int[_len]; + _radixes = new int[_len]; + _distances = new int[_len]; + _finishes = new int[_len]; + _colors = new int[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* add_node(H k) { + if(_nodes == _len) return this; + if(_index(k) >= 0) return this; // node is already there + + _k[_nodes++] = new H(k); + + return this; + } + + + bool dfs() { + bool cycle = 0; + _time = 0; + for(int i = 0; i < _nodes; ++i) { + _colors[i] = W; + _parents[i] = -1; + } + + for(int i = 0; i < _nodes; ++i) { + if(_colors[i] == W) { + _current = i; + cycle |= _dfsvisit(i); + } + } + for(int i = 0; i < _nodes; ++i) { + cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl; + } + return cycle; + } + + void top_sort() { + bool cycle = dfs(); + if(cycle) { + cerr << "Grafo ciclico\n"; + return; + } + vector s(_finishes, _finishes+_nodes); + sort(begin(s), end(s)); + for(auto const& i : s) { + cout << "(" << i << ", " << _finishes[i] << ") "; + } + } + + graph* add_edge(H x, H y) { + int i = _index(x); + int j = _index(y); + if(i < 0 || j < 0) return this; + + if(!_adj[i]->search(j)) { + _adj[i]->push(j); + _edges++; + } + + return this; + } + + void print() { + for(int i = 0; i < _nodes; ++i) { + cout << "(" << i << ", " << *_k[i] << "): "; + for(auto const& j : _adj[i]->as_vector()) + cout << "(" << j << ", " << *_k[j] << "), "; + cout << '\n'; + } + } +}; + + +int main() { + graph* g = new graph(6); + g->add_node('u')->add_node('v')->add_node('x')->add_node('y'); + g->add_node('w')->add_node('z'); + g->add_edge('u', 'v'); + g->add_edge('u', 'x'); + g->add_edge('x', 'v'); + g->add_edge('y', 'x'); + g->add_edge('v', 'y'); + g->add_edge('w', 'y'); + g->add_edge('w', 'z'); + g->add_edge('z', 'z'); + + g->print(); + g->dfs(); + g->top_sort(); + + delete g; + return 0; +} -- cgit v1.2.3-18-g5258