
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_tree3.h (parents, iterators) /* 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 aheared 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) (v3 - parent+, iterators version) // 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 CMaaAVLTree3 { protected: class Node { public: Node* p, * left, * right; unsigned char height; Key k; Data d; Node(const Key& _k, const Data& _d) : p(NULL), left(NULL), right(NULL), 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) }; public: typedef Node* Handle; protected: Node* root; size_t N; struct AllocErr {}; //Handle m_h[128], m_p[128]; char m_t[128]; public: static Key key(Handle x) { return x->key(); } static Data& data(Handle x) { return x->data(); } static const Key& c_key(Handle x) { return x->c_key(); } static const Data& c_data(Handle x) { return x->c_data(); } Key k(Handle x) { return x->key(); } Data& d(Handle x) { return x->data(); } /* Handle GetHandle(const Key &k) const { return FindNode(k); } */ CMaaAVLTree3() : root(NULL), N(0) { } ~CMaaAVLTree3() { 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, NULL, K, D, fOverwrite); if (root) { //root->p = NULL; } 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 != NULL ) int Find(const Key& K, Data* D = NULL) 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 NULL by default ) where to return deleted context of Data int Remove(const Key& K, Data* D = NULL) { const size_t N0 = N; root = remove(root, NULL, K, D); if (root) { //root->p = NULL; } return N < N0 ? 0 : 1; } void inorder() { __utf8_printf("%D: ", (_qword)N); inorder(root); __utf8_printf("\n"); } CMaaString Node2Text(Node* x); //{ // return CMaaString::sFormat("%d", x->k); //} void Print(Node* x = NULL, 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); } Handle it; /* Key k; if (!FindMin(&k)) { //CMaaString str = Node2Text(it); //__utf8_printf("(%S) ", &str); __utf8_printf("(%d) ", k); //__utf8_printf("(%f) ", k); } */ for (it = begin(); it != end(); it = FindSucc(it)) { CMaaString str = Node2Text(it); __utf8_printf("%S ", &str); } if (begin() != end()) { __utf8_printf("\n"); } /* if (!FindMax(&k)) { //CMaaString str = Node2Text(it); //__utf8_printf("(%S) ", &str); __utf8_printf("(%d) ", k); //__utf8_printf("(%f) ", k); } */ for (it = rbegin(); it != rend(); it = FindPred(it)) { CMaaString str = Node2Text(it); __utf8_printf("%S ", &str); } if (begin() != end()) { __utf8_printf("\n"); } } CMaaString Print(Node* x, int w = 79, int l = 0, bool* e = NULL) { if (e) { *e = false; } if (!x) { CMaaString sp(NULL, 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(NULL, w1), sp2(NULL, w2); sp1.Fill(' '); sp2.Fill(' '); return sp1 + Ret + sp2; } /* // checks if (x->left && x->left->p != x) { static char err[512]; sprintf(err, "chk: %d->left error", x->k); throw err; } if (x->right && x->right->p != x) { static char err[512]; sprintf(err, "chk: %d->right error", x->k); throw err; } */ 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; } bool Check(Node* x) { if (x->p) { if (x->p->left == x && x->p->right != x) { } else if (x->p->left != x && x->p->right == x) { } else { return false; } } if (x->left && x->left->p != x) { return false; } if (x->right && x->right->p != x) { return false; } return true; } bool CheckAll(Node* x = NULL) { if (!x) { x = root; } if (!Check(x)) { return false; } if (x->left && !Check(x->left)) { return false; } if (x->right && !Check(x->right)) { return false; } return true; } 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; if (a->right) { a->right->p = a; } a->p = b; 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; if (a->right) { a->right->p = a; } if (b->left) { b->left->p = b; } a->p = b->p = c; 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; if (a->left) { a->left->p = a; } a->p = b; 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; if (a->left) { a->left->p = a; } if (b->right) { b->right->p = b; } a->p = b->p = c; 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, Node* parent, const Key& _k, const Data& _d, int fOverwrite) { if (!x) { N++; x = new Node(_k, _d); if (!x) { AllocErr e; throw e; } x->p = parent; return x; } if (_k < x->k) { x->left = insert(x->left, x, _k, _d, fOverwrite); } else if (_k > x->k) { x->right = insert(x->right, x, _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); } x->p = parent; } else if (bal < -1) { if (height(x->left->right) <= height(x->left->left)) { x = small_r_rotate(x); } else { x = big_r_rotate(x); } x->p = parent; } return x; } /* Node* insert_it(Node* x, Node* parent, const Key& _k, const Data& _d, int fOverwrite) { int idx = 0; m_h[idx] = x; m_p[idx] = parent; m_t[idx] = 0; for (; m_h[idx]; idx++) { if (_k < m_h[idx]->k) { m_h[idx + 1] = m_h[idx]->left; m_p[idx + 1] = m_h[idx]; m_t[idx] = -1; //x->left = insert(x->left, x, _k, _d, fOverwrite); } else if (_k > m_h[idx]->k) { m_h[idx + 1] = m_h[idx]->right; m_p[idx + 1] = m_h[idx]; m_t[idx] = 1; //x->right = insert(x->right, x, _k, _d, fOverwrite); } else { // dup k is not inserted if (fOverwrite) { x->d = _d; } return m_h[0]; } } if (!m_h[idx]) { N++; x = new Node(_k, _d); if (!x) { AllocErr e; throw e; } x->p = m_p[idx]; } for (; --idx >= 0; ) { if (m_t[idx] < 0) { m_p[idx + 1]->left = x; } else { m_p[idx + 1]->right = x; } x = m_p[idx + 1]; 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); } x->p = m_p[idx]; } else if (bal < -1) { if (height(x->left->right) <= height(x->left->left)) { x = small_r_rotate(x); } else { x = big_r_rotate(x); } x->p = m_p[idx]; } } return x; } */ Node* insert_it3(Node* x, Node* parent, const Key& _k, const Data& _d, int fOverwrite) { Node* x0 = x; int idx = 0; //m_h[idx] = x; //m_p[idx] = parent; m_t[idx] = 0; for (; x; idx++) { if (_k < x->k) { //m_h[idx + 1] = m_h[idx]->left; //m_p[idx + 1] = m_h[idx]; m_t[idx] = -1; //x->left = insert(x->left, x, _k, _d, fOverwrite); parent = x; x = x->left; } else if (_k > x->k) { //m_h[idx + 1] = m_h[idx]->right; //m_p[idx + 1] = m_h[idx]; m_t[idx] = 1; //x->right = insert(x->right, x, _k, _d, fOverwrite); parent = x; x = x->right; } else { // dup k is not inserted if (fOverwrite) { x->d = _d; } return x0; } } if (!x) { N++; x = new Node(_k, _d); if (!x) { AllocErr e; throw e; } x->p = parent;// m_p[idx]; } for (; --idx >= 0; ) { if (m_t[idx] < 0) { //m_p[idx + 1]->left = x; parent->left = x; } else { //m_p[idx + 1]->right = x; parent->right = x; } //x = m_p[idx + 1]; x = parent; parent = x->p; 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); } x->p = parent;// m_p[idx]; } else if (bal < -1) { if (height(x->left->right) <= height(x->left->left)) { x = small_r_rotate(x); } else { x = big_r_rotate(x); } x->p = parent;// m_p[idx]; } } return x; } Node* remove(Node* x, Node* parent, const Key& _k, Data* _d) { if (!x) { return x; } if (_k < x->k) { x->left = remove(x->left, x, _k, _d); } else if (_k > x->k) { x->right = remove(x->right, x, _k, _d); } else { if (_d) { *_d = x->d; } Node* l = x->left; Node* r = x->right; if (!r) { delete x; x = l; if (x) { x->p = parent; } N--; } else if (!l) { delete x; x = r; //if (x) //{ x->p = parent; //} 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, x, r->k, NULL); } else { while (l->right) { l = l->right; } x->k = l->k; x->d = l->d; x->left = remove(x->left, x, l->k, NULL); } } } 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); } x->p = parent; } else if (bal < -1) { if (height(x->left->right) <= height(x->left->left)) { x = small_r_rotate(x); } else { x = big_r_rotate(x); } x->p = parent; } 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; //return NULL; } public: Node* begin() const { return root ? TreeMinimum(root) : root; } // next: p = rb.TreeSuccessor(p); // for (CMaaRBTree<int, int>::Handle p = r.begin(); p != r.end(); p = r.TreeSuccessor(p)) Node* end() const { return NULL; } Node* rbegin() const { return root ? TreeMaximum(root) : root; } // prev: p = rb.TreePredecessor(p); // for (CMaaRBTree<int, int>::Handle p = r.begin(); p != r.end(); p = r.TreePredecessor(p)) Node* rend() const { return NULL; } Node* TreeMinimum(Node* x) const { while (x->left) { x = x->left; } return x; } Node* TreeMaximum(Node* x) const { while (x->right) { x = x->right; } return x; } Node* TreeSuccessor(Node* x) const { if (x->right) { return TreeMinimum(x->right); } Node* y = x->p; while (y && x == y->right) { x = y; y = y->p; } return y; } Node* TreePredecessor(Node* x) const { if (x->left) { return TreeMaximum(x->left); } Node* y = x->p; while (y && x == y->left) { x = y; y = y->p; } return y; } Node* RecursiveTreeSearch(Node* x, const Key& k) const { if (!x || k == x->k) { return x; } if (k < x->k) { return TreeSearch(x->left, k); } else { return TreeSearch(x->right, k); } } Node* IteractiveTreeSearch(Node* x, const Key& k) const { while (x && k != x->k) { if (k < x->k) { x = x->left; } else { x = x->right; } } return x; } Node* TreeSearchLQ(const Key& k, bool bRetEq = true, Node* x = NULL) const { x = x ? x : root; Node* y; if (bRetEq) { y = IteractiveTreeSearch(x, k); if (y) { return y; } } y = NULL; while (x) { if (k == x->k) { x = x->left; } else if (k < x->k) { x = x->left; } else { y = x; x = x->right; } } return y; } Node* TreeSearchGQ(const Key& k, bool bRetEq = true, Node* x = NULL) const { x = x ? x : root; Node* y; if (bRetEq) { y = IteractiveTreeSearch(x, k); if (y) { return y; } } y = NULL; while (x) { if (k == x->k) { x = x->right; } else if (k < x->k) { y = x; x = x->left; } else { x = x->right; } } return y; } /* int Find(const Key& k, Data* d = NULL) { Node* x = IteractiveTreeSearch(root, k); if (x != _nil) { if (d) { *d = x->d; } return 0; } return 1; } */ Handle FindNode(const Key& k) const { Node* x = IteractiveTreeSearch(root, k); //return x ? x : NULL; return x; } /* int Remove(const Key &k, Data *d = NULL) { Node * x = IteractiveTreeSearch(root, k); if (x != _nil) { if (d) { *d = x->d; } RBDelete(x); return 0; } return 1; } */ int FindMin(Key *k = NULL, Data *d = NULL) const { Node * x = root ? TreeMinimum(root) : root; if (x) { if (k) { *k = x->k; } if (d) { *d = x->d; } return 0; } return 1; } int FindMax(Key *k = NULL, Data *d = NULL) const { Node * x = root ? TreeMaximum(root) : root; if (x) { if (k) { *k = x->k; } if (d) { *d = x->d; } return 0; } return 1; } int FindSucc(const Key &_k, Key *k = NULL, Data *d = NULL) const { Node * x = root ? IteractiveTreeSearch(root, _k) : root; if (x) { x = TreeSuccessor(x); if (x) { if (k) { *k = x->k; } if (d) { *d = x->d; } return 0; } return 2; } return 1; } int FindPred(const Key &_k, Key *k = NULL, Data *d = NULL) const { Node * x = root ? IteractiveTreeSearch(root, _k) : root; if (x) { x = TreePredecessor(x); if (x) { if (k) { *k = x->k; } if (d) { *d = x->d; } return 0; } return 2; } return 1; } Handle FindSucc(Handle x) const { if (x)// && x != _nil) { x = TreeSuccessor(x); //return x != _nil ? x : NULL; } //return NULL; return x; } Handle FindPred(Handle x) const { if (x)// && x != _nil) { x = TreePredecessor(x); //return x != _nil ? x : NULL; } //return NULL; return x; } int FindLQ(const Key& _k, bool bRetEq, Key* k = NULL, Data* d = NULL) const { Node* x = TreeSearchLQ(_k, bRetEq, root); if (x) { if (k) { *k = x->k; } if (d) { *d = x->d; } return 0; } return 1; } int FindGQ(const Key& _k, bool bRetEq, Key* k = NULL, Data* d = NULL) const { Node* x = TreeSearchGQ(_k, bRetEq, root); if (x) { if (k) { *k = x->k; } if (d) { *d = x->d; } return 0; } return 1; } int FindLQ(const Key& _k, Key* k = NULL, Data* d = NULL) const { return FindLQ(_k, true, k, d); } int FindGQ(const Key& _k, Key* k = NULL, Data* d = NULL) const { return FindGQ(_k, true, k, d); } int FindLnQ(const Key& _k, Key* k = NULL, Data* d = NULL) const { return FindLQ(_k, false, k, d); } int FindGnQ(const Key& _k, Key* k = NULL, Data* d = NULL) const { return FindGQ(_k, false, k, d); } }; #if 0 #ifdef __unix__ int getch() { return 0; } #endif template<> CMaaFixedAllocator<CMaaRBTree<int, int>::Node>* CMaaRBTree<int, int>::Node::s_pAllocator = NULL; template<> CMaaString CMaaRBTree<int, int>::Node2Text(CMaaRBTree<int, int>::Node* x) { return CMaaString::sFormat("%d%c", x->k, (char)x->color); } template<> CMaaFixedAllocator<CMaaAVLTree3<int, int>::Node>* CMaaAVLTree3<int, int>::Node::s_pAllocator = NULL; template<> CMaaFixedAllocator<CMaaAVLTree3<float, int>::Node>* CMaaAVLTree3<float, int>::Node::s_pAllocator = NULL; template<> CMaaString CMaaAVLTree3<int, int>::Node2Text(CMaaAVLTree3<int, int>::Node* n) { return CMaaString::sFormat("%d", n->k); } template<> CMaaString CMaaAVLTree3<float, int>::Node2Text(CMaaAVLTree3<float, int>::Node* n) { return CMaaString::sFormat("[%d]=%.1lf", n->d, n->k); } template<> CMaaFixedAllocator<CMaaAVLTree<int, int>::Node>* CMaaAVLTree<int, int>::Node::s_pAllocator = NULL; template<> CMaaFixedAllocator<CMaaAVLTree<float, int>::Node>* CMaaAVLTree<float, int>::Node::s_pAllocator = NULL; template<> CMaaString CMaaAVLTree<int, int>::Node2Text(CMaaAVLTree<int, int>::Node* n) { 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 main2222() { try { _qword t00 = GetUsTime(); if (0) { { CMaaAVLTree3<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(); { CMaaAVLTree3<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", (_qword)t.GetCount(), m[i]); t.Add(m[i], m[i]) && __utf8_printf("!"); __utf8_printf("\n"); 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", (_qword)t.GetCount(), -m[i]); t.Remove(-m[i]) && __utf8_printf("!"); __utf8_printf("\n"); t.Print(); getch(); } } __utf8_printf("===\n"); //t.inorder(); //t.Print(); } } //return 0; { const int N = 1000000;// / 50000; CMaaPtr<int> m(N); CMaaUnivHash<int, char> h; __utf8_printf("Get unique random ints...\n"); int i; for (i = 0; i < N; i++) { int x = 0; GetRnd(&x, (int)sizeof(x)); /* if (i == 0) { x = 1287757060; } if (i == 1) { x = -1885024578; } if (i == 2) { x = -452717411; } */ //x = i; m[i] = x; if (h.Add(x, 0)) { i--; } } _qword mt[8][10]; // [0] - rb, [1] - v3, [2] - v1; [][0] - ins, [][1] - remove __utf8_printf("Testing CMaaRBTree<int, int>...\n"); int idx = 0; CMaaRBTree<int, int> r; mt[idx][0] = GetUsTime(); for (i = 0; i < N; i++) { r.Add(m[i], i, false) && __utf8_printf("0i%d[%d]! ", m[i], i); /* if (i < 3) { r.Add(m[i], i, false) || __utf8_printf("0i%d[%d]!\n", m[i], i); } */ //tt.Add(m[i], i) && __utf8_printf("0i%d[%d]! ", m[i], i); } mt[idx][0] = GetUsTime() - mt[idx][0]; __utf8_printf(">>>"); mt[idx][2] = GetUsTime(); int R = r.GetHeightSlow(); mt[idx][2] = GetUsTime() - mt[idx][2]; __utf8_printf("..."); mt[idx][1] = GetUsTime(); for (i = 0; i < N; i++) { r.Remove(m[i]) && __utf8_printf("0r%d[%d]! ", m[i], i); //tt.Remove(m[i]) && __utf8_printf("0r%d[%d]! ", m[i], i); } mt[idx][1] = GetUsTime() - mt[idx][1]; __utf8_printf("<<<\n"); r.Print(); idx++; __utf8_printf("Testing CMaaAVLTree3<int, int>...\n"); CMaaAVLTree3<int, int> t; mt[idx][0] = GetUsTime(); for (i = 0; i < N; i++) { t.Add(m[i], i) && __utf8_printf("1i%d[%d]! ", m[i], i); /* if (i < 3) { int y; !t.Find(m[i], &y) && __utf8_printf("%d\n", y); } */ } mt[idx][0] = GetUsTime() - mt[idx][0]; mt[idx][2] = GetUsTime(); int H = t.GetHeight(); mt[idx][2] = GetUsTime() - mt[idx][2]; mt[idx][3] = GetUsTime(); CMaaAVLTree3<int, int>::Handle it; it = t.begin(); int e = 0; int prev = t.key(it); for (it = t.FindSucc(it); it != t.end(); it = t.FindSucc(it)) { if (prev >= t.key(it)) { __utf8_printf("error prev=%d, key=%d\n", prev, t.key(it)); e++; } prev = t.key(it); } e&& __utf8_printf("\n"); mt[idx][3] = GetUsTime() - mt[idx][3]; mt[idx][4] = GetUsTime(); it = t.rbegin(); e = 0; int next = t.key(it); for (it = t.FindPred(it); it != t.rend(); it = t.FindPred(it)) { if (next <= t.key(it)) { __utf8_printf("error next=%d, key=%d\n", next, t.key(it)); e++; } next = t.key(it); } e&& __utf8_printf("\n"); mt[idx][4] = GetUsTime() - mt[idx][4]; mt[idx][5] = GetUsTime(); for (it = t.begin(); it != t.end(); it = t.FindSucc(it)) { if (!t.Check(it)) { __utf8_printf("1. error chk, key=%d\n", t.key(it)); } } for (it = t.rbegin(); it != t.rend(); it = t.FindPred(it)) { if (!t.Check(it)) { __utf8_printf("2. error chk, key=%d\n", t.key(it)); } } mt[idx][5] = (GetUsTime() - mt[idx][5]) / 2; mt[idx][6] = GetUsTime(); if (!t.CheckAll()) { __utf8_printf("3. error chk all\n"); } mt[idx][6] = GetUsTime() - mt[idx][6]; mt[idx][1] = GetUsTime(); for (i = 0; i < N; i++) { t.Remove(m[i]) && __utf8_printf("1r%d[%d]! ", m[i], i); } mt[idx][1] = GetUsTime() - mt[idx][1]; idx++; __utf8_printf("Testing CMaaAVLTree<int, int>...\n"); CMaaAVLTree<int, int> _t2; mt[idx][0] = GetUsTime(); for (i = 0; i < N; i++) { //r.Add(m[i], i) || __utf8_printf("0i%d[%d]! ", m[i], i); _t2.Add(m[i], i) && __utf8_printf("0i%d[%d]! ", m[i], i); /* if (i < 3) { int y; !_t2.Find(m[i], &y) && __utf8_printf("%d\n", y); } */ } mt[idx][0] = GetUsTime() - mt[idx][0]; mt[idx][2] = GetUsTime(); int H2 = _t2.GetHeight(); mt[idx][2] = GetUsTime() - mt[idx][2]; mt[idx][1] = GetUsTime(); for (i = 0; i < N; i++) { //r.Remove(m[i]) && __utf8_printf("0r%d[%d]! ", m[i], i); _t2.Remove(m[i]) && __utf8_printf("0r%d[%d]! ", m[i], i); } mt[idx][1] = GetUsTime() - mt[idx][1]; __utf8_printf("--r--\n"); r.Print(); __utf8_printf("--3--\n"); t.Print(); __utf8_printf("--1--\n"); _t2.Print(); // mt: [0] - rb, [1] - v3, [2] - v1; [][0] - ins, [][1] - remove // hm: max theoretical avl height double hm = 1.45 * log(N + 2) / log(2), kir = mt[2][0] / (double)mt[0][0], krr = mt[2][1] / (double)mt[0][1], ki = mt[1][0] / (double)mt[2][0], kr = mt[1][1] / (double)mt[2][1]; __utf8_printf("%,D\t%,D\th=%d\t%,D\n", mt[0][0], mt[0][1], R, mt[0][2]); __utf8_printf("%,D\t%,D\th=%d\tN=%d\t%.1lf\t%.3lf\t%.3lf\n", mt[2][0], mt[2][1], H2, N, hm, kir, krr); __utf8_printf("%,D\t%,D\th=%d\tN=%d\t%.1lf\t%.3lf\t%.3lf\n", mt[1][0], mt[1][1], H, N, hm, ki, kr); } } /* catch (int x) { __utf8_printf("catch(%d)\n", x); } */ catch (const char* m) { __utf8_printf("catch(%s)\n", m); } catch (...) { __utf8_printf("catch(...)\n"); } //return 0; { CMaaAVLTree3<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.Add(4.6f, 44, 1); t.Remove(6.8f); t.Remove(7.9f); //t.Print(); } return 0; } int main() { main2222(); //__utf8_printf("==--==--==\n"); main2222(); return 0; } #endif //template<> CMaaFixedAllocator<CMaaAVLTree3<int, int>::Node> * CMaaAVLTree3<int, int>::Node::s_pAllocator = NULL; /* // opt: template<> CMaaString CMaaAVLTree3<int, int>::Node2Text(CMaaAVLTree3<int, int>::Node* n) { return CMaaString::sFormat("%d", n->k); } */ Ratio: Back Top |
User
Новости [...] Архив новостей. New on site
Online
Guests: 0
Users: 0 Bots: 1 Total users: 2 |
We are processing with: |