IP Moiseenko A.A. (MaaSoft/MaaSoftware OOO) |
|
|
// ToolsLib Project /* CryptLib library for RusRoute firewall and other projects of * Andrey A. Moiseenko and MaaSoftware (LLC, Russia) * e-mail: support@maasoftware.ru, maa2002@mail.ru * web: http://maasoftware.ru, http://maasoftware.com * Author's full name: Andrey Alekseevitch Moiseenko * (russian name: Моисеенко Андрей Алексеевич) */ // ToolsLib/avl_tree.h /* Copyright (C) 2002-2015 Andrey A. Moiseenko (support@maasoftware.ru) * All rights reserved. * * This library contains cross-platform templates for working heap * sutable for using them in sockets' timers. * The library implementation written * by Andrey A. Moiseenko (support@maasoftware.ru). * This library and applications are * FREE FOR COMMERCIAL AND NON-COMMERCIAL USE * as long as the following conditions are adhered to. * * Copyright remains Andrey A. Moiseenko's, and as such any Copyright notices in * the code are not to be removed. If this code is used in a product, * Andrey A. Moiseenko should be given attribution as the author of the parts used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by Andrey A. Moiseenko (support@maasoftware.ru) * * THIS SOFTWARE IS PROVIDED BY ANDREY A. MOISEENKO ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed. i.e. this code cannot simply be * copied and put under another distribution licence * [including the GNU Public Licence.] */ // AVL Tree (balanced tree) // Keys can not be duplicated // https://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE // template <class Key, class Data> class CMaaAVLTree { protected: class Node { public: Node* left; Node* right; unsigned char height; Key k; Data d; Node(const Key& _k, const Data& _d) : left(nullptr), right(nullptr), height(1), k(_k), d(_d) { } int UpdateHeightGetBalance() { unsigned char l = left ? left->height : 0; unsigned char r = right ? right->height : 0; height = 1 + (l > r ? l : r); return (int)r - (int)l; } /* Key key() { return k; } Data& data() { return d; } const Key& c_key() const { return k; } const Data& c_data() const { return d; } */ ADD_UL_ALLOCATOR(Node) }; Node * root; size_t N; struct AllocErr {}; public: CMaaAVLTree() : root(nullptr), N(0) { } ~CMaaAVLTree() { DeleteNode(root); } size_t GetCount() const { return N; } int GetHeight() const { return height(root); } // Adds element. ( Copy element to table ) // Returns 0 if success. 1 - Key alredy exists. 2 - Not enought free memory int Add(const Key& K, const Data& D, int fOverwrite = 0) { try { const size_t N0 = N; root = insert(root, K, D, fOverwrite); return fOverwrite || N > N0 ? 0 : 1; } catch(AllocErr) { } return 2; } // Adds element. ( Owerwrites it if exists ) // Returns 0 if success. 2 - Not enought free memory int AddOver(const Key& K, const Data& D) { return Add(K, D, 1); } // Finds element. // If ok: returns 0 and copy Data ( if Data != nullptr ) int Find(const Key& K, Data* D = nullptr) const { Node* n = search(root, K); if (n) { if (D) { *D = n->d; } return 0; } return 1; } // Removes element. // Returns 0 if ok. // it is sutable to add param void * Data ( witch is nullptr by default ) where to return deleted context of Data int Remove(const Key& K, Data* D = nullptr) { const size_t N0 = N; root = remove(root, K, D); return N < N0 ? 0 : 1; } void inorder() { __utf8_printf("%D: ", (_qword)N); inorder(root); __utf8_printf("\n"); } CMaaString Node2Text(Node* head); //{ // return CMaaString::sFormat("%d", x->k); //} void Print(Node* x = nullptr, int w = 79, int ll = 10) { x = x ? x : root; for (int l = 0; l < ll; l++) { bool e = false; CMaaString str = Print(x, w, l, &e); if (e) { break; } __utf8_printf("%S\n", &str); } } CMaaString Print(Node* x, int w = 79, int l = 0, bool* e = nullptr) { if (e) { *e = false; } if (!x) { CMaaString sp(nullptr, w); sp.Fill(' '); if (e) { *e = true; } return sp; } if (l == 0) { CMaaString Ret = Node2Text(x); int w2 = w - Ret.Length(); if (w2 < 2) { w2 = 2; } int w1 = w2 / 2; w2 -= w1; CMaaString sp1(nullptr, w1), sp2(nullptr, w2); sp1.Fill(' '); sp2.Fill(' '); return sp1 + Ret + sp2; } bool ee[2]; CMaaString Ret = Print(x->left, w / 2, l - 1, &ee[0]) + Print(x->right, w - w / 2, l - 1, &ee[1]); if (e) { *e = ee[0] && ee[1]; } return Ret; } protected: void DeleteNode(Node* t) { if (t) { DeleteNode(t->left); DeleteNode(t->right); delete t; } } unsigned char height(Node * x) const { return x ? x->height : 0; } // a b // / \ / \ // L b --> a R // / \ / \ // C R L C Node* small_l_rotate(Node* a) { Node* b = a->right; a->right = b->left; b->left = a; a->UpdateHeightGetBalance(); b->UpdateHeightGetBalance(); return b; } // a c // / \ / \ // L b --> a b // / \ / \ / \ // c R L M N R // / \ // M N Node* big_l_rotate(Node* a) { Node* b = a->right; Node* c = b->left; a->right = c->left; b->left = c->right; c->left = a; c->right = b; a->UpdateHeightGetBalance(); b->UpdateHeightGetBalance(); c->UpdateHeightGetBalance(); return c; } // a b // / \ / \ // b R --> L a // / \ / \ // L C C R Node* small_r_rotate(Node* a) { Node* b = a->left; a->left = b->right; b->right = a; a->UpdateHeightGetBalance(); b->UpdateHeightGetBalance(); return b; } // a c // / \ / \ // b R --> b a // / \ / \ / \ // L c L M N R // / \ // M N Node* big_r_rotate(Node* a) { Node* b = a->left; Node* c = b->right; a->left = c->right; b->right = c->left; c->right = a; c->left = b; a->UpdateHeightGetBalance(); b->UpdateHeightGetBalance(); c->UpdateHeightGetBalance(); return c; } void inorder(Node * head) { if (!head) { return; } inorder(head->left); //cout<<head->k<<" "; //__utf8_printf("%d ", head->k); CMaaString r = Node2Text(head); __utf8_printf("%S ", &r); inorder(head->right); } Node * insert(Node * x, const Key& _k, const Data& _d, int fOverwrite) { if (!x) { N++; x = new Node(_k, _d); if (!x) { AllocErr e; throw e; } return x; } if (_k < x->k) { x->left = insert(x->left, _k, _d, fOverwrite); } else if (_k > x->k) { x->right = insert(x->right, _k, _d, fOverwrite); } else { // dup k is not inserted if (fOverwrite) { x->d = _d; } } int bal = x->UpdateHeightGetBalance(); if (bal > 1) { if (height(x->right->left) <= height(x->right->right)) { x = small_l_rotate(x); } else { x = big_l_rotate(x); } } else if (bal < -1) { if (height(x->left->right) <= height(x->left->left)) { x = small_r_rotate(x); } else { x = big_r_rotate(x); } } return x; } Node * remove(Node * x, const Key& _k, Data* _d) { if (!x) { return x; } if (_k < x->k) { x->left = remove(x->left, _k, _d); } else if (_k > x->k) { x->right = remove(x->right, _k, _d); } else { if (_d) { *_d = x->d; } Node * l = x->left; Node * r = x->right; if (!r) { delete x; x = l; N--; } else if (!l) { delete x; x = r; N--; } else { if (height(x->right) >= height(x->left)) { while (r->left) { r = r->left; } x->k = r->k; x->d = r->d; x->right = remove(x->right, r->k, nullptr); } else { while (l->right) { l = l->right; } x->k = l->k; x->d = l->d; x->left = remove(x->left, l->k, nullptr); } } } if (!x) { return x; } int bal = x->UpdateHeightGetBalance(); if (bal > 1) { if (height(x->right->left) <= height(x->right->right)) { x = small_l_rotate(x); } else { x = big_l_rotate(x); } } else if (bal < -1) { if (height(x->left->right) <= height(x->left->left)) { x = small_r_rotate(x); } else { x = big_r_rotate(x); } } return x; } Node * search(Node * x, const Key &_k) const { if (x) { if (x->k > _k) { return search(x->left, _k); } if (x->k < _k) { return search(x->right, _k); } //if (x->k == x) //{ // return x; //} } return x; } }; #if 0 #ifdef __unix__ int getch() {return 0;} #endif template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node>* CMaaRBTree<int, int>::Node::s_pAllocator = nullptr; template<> CMaaFixedAllocator<CMaaAVLTree<int, int>::Node> * CMaaAVLTree<int, int>::Node::s_pAllocator = nullptr; template<> CMaaFixedAllocator<CMaaAVLTree<float, int>::Node>* CMaaAVLTree<float, int>::Node::s_pAllocator = nullptr; template<> CMaaString CMaaAVLTree<int, int>::Node2Text(CMaaAVLTree<int, int>::Node* n) { // cout << head->k; //__utf8_printf("%d", n->k); return CMaaString::sFormat("%d", n->k); } template<> CMaaString CMaaAVLTree<float, int>::Node2Text(CMaaAVLTree<float, int>::Node* n) { // cout << head->k; //__utf8_printf("%d", n->k); return CMaaString::sFormat("[%d]=%.1lf", n->d, n->k); } int main() { try { _qword t00 = GetUsTime(); if (0) { { CMaaAVLTree<int, int> t; //t.inorder(); int i; for (i = 1; i <= 9; i++) { t.Add(i, i); __utf8_printf("%D:\n", (_qword)t.GetCount()); t.Print(); getch(); } //t.inorder(); //t.Print(); t.Remove(4); //t.inorder(); __utf8_printf("%D:\n", (_qword)t.GetCount()); t.Print(); getch(); } __utf8_printf("---\n"); getch(); { CMaaAVLTree<int, int> t; //t.inorder(); t.Print(); int m[] = { 20, 25, 15, 10, 30, 5, 35, 67, 43, 21, 10, 89, 38, 69, -5, -35, -65, -89, -43, -88, -20, -38, 0 }; int i; for (i = 0; m[i]; i++) { if (m[i] > 0) { __utf8_printf("%D i%d\n", (_qword)t.GetCount(), m[i]); t.Add(m[i], m[i], false) && __utf8_printf("!"); t.Print(); getch(); } else { if (m[i] == -5) { //__utf8_printf("\n"); //t.inorder(); //t.Print(); } //__utf8_printf(" r%d", -m[i]); __utf8_printf("%D r%d\n", (_qword)t.GetCount(), -m[i]); t.Remove(-m[i]) && __utf8_printf("!"); t.Print(); getch(); } } __utf8_printf("===\n"); //t.inorder(); //t.Print(); } } //return 0; { const int N = 1000000; CMaaPtr<int> m(N); CMaaUnivHash<int, char> h; int i; for (i = 0; i < N; i++) { int x = 0; GetRnd(&x, (int)sizeof(x)); m[i] = x; if (h.Add(x, 0)) { i--; } } _qword t0 = GetUsTime(); CMaaRBTree<int, int> r; for (i = 0; i < N; i++) { r.Add(m[i], i) && __utf8_printf("0i%d[%d]! ", m[i], i); } _qword t01 = GetUsTime(); for (i = 0; i < N; i++) { r.Remove(m[i]) && __utf8_printf("0r%d[%d]! ", m[i], i); } _qword t1 = GetUsTime(); CMaaAVLTree<int, int> t; for (i = 0; i < N; i++) { t.Add(m[i], i) && __utf8_printf("1i%d[%d]! ", m[i], i); } int H = t.GetHeight(); _qword t11 = GetUsTime(); for (i = 0; i < N; i++) { t.Remove(m[i]) && __utf8_printf("1r%d[%d]! ", m[i], i); } _qword t2 = GetUsTime(); __utf8_printf("---\n"); r.Print(); __utf8_printf("===\n"); t.Print(); double hm = 1.45 * log(N + 2) / log(2); __utf8_printf("%,D\t%,D\n", t01 - t0, t1 - t01); __utf8_printf("%,D\t%,D\th=%d\tN=%d\t%.1lf\n", t11 - t1, t2 - t11, H, N, hm); } } /* catch (int x) { __utf8_printf("catch(%d)\n", x); } */ catch (...) { __utf8_printf("catch(...)\n"); } //return 0; { CMaaAVLTree<float, int> t; t.Add(1.3f, 1); t.Add(2.4f, 2); t.Add(3.5f, 3); t.Add(4.6f, 4); t.Add(5.7f, 5); t.Add(6.8f, 6); t.Add(7.9f, 7); t.Print(); t.Remove(5.7f); t.Remove(6.8f); t.Remove(7.9f); t.Print(); } return 0; } #endif //template<> CMaaFixedAllocator<CMaaAVLTree<int, int>::Node> * CMaaAVLTree<int, int>::Node::s_pAllocator = nullptr; /* // opt: template<> CMaaString CMaaAVLTree<int, int>::Node2Text(CMaaAVLTree<int, int>::Node* n) { return CMaaString::sFormat("%d", n->k); } */ Ratio: Back Top |
User
Новости [...] Архив новостей. New on site
Catalog:
Online
Guests: 0
Users: 0 Bots: 1 Total users: 7 |
We are processing with: |