Changeset 3842


Ignore:
Timestamp:
Feb 28, 2015, 10:12:34 AM (7 years ago)
Author:
guite
Message:

map: starting bug fix

Location:
trunk/src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/lol/base/avl_tree.h

    r3836 r3842  
    224224            int i = -1 + (key < m_key) + 2 * (m_key < key);
    225225
     226            bool created = false;
     227
    226228            if (i < 0)
    227             {
    228229                m_value = value;
    229                 return false;
    230             }
    231 
    232             bool b_created = false;
    233 
    234             if (m_child[i])
    235                 b_created = m_child[i]->insert(key, value);
     230            else if (m_child[i])
     231                created = m_child[i]->insert(key, value);
    236232            else
    237233            {
    238                 b_created = true;
     234                created = true;
    239235
    240236                m_child[i] = new tree_node(key, value, &m_child[i]);
     
    248244            }
    249245
    250             if (b_created)
     246            if (created)
     247            {
    251248                rebalance_if_needed();
    252 
    253             return b_created;
     249            }
     250
     251
     252            return created;
    254253        }
    255254
     
    259258            int i = -1 + (key < m_key) + 2 * (m_key < key);
    260259
     260            bool erased = false;
     261
    261262            if (i < 0)
    262263            {
    263264                erase_self();
    264265                delete this;
    265                 return true;
     266                erased = true;
    266267            }
    267268            else if (m_child[i] && m_child[i]->erase(key))
    268269            {
    269270                rebalance_if_needed();
    270                 return true;
    271             }
    272 
    273             return false;
     271                erased = true;
     272            }
     273
     274            return erased;
    274275        }
    275276
     
    346347            update_balance();
    347348
    348             int i = (get_balance() ==  2);
    349             int j = (get_balance() == -2);
    350 
    351             if (i || j)
    352             {
    353                 tree_node * save = m_child[i];
    354                 tree_node ** save_parent = m_parent_slot;
    355 
    356                 set_child(i, save->m_child[j]);
    357                 save->set_child(j, this);
    358 
    359                 save->m_parent_slot = save_parent;
    360                 *save_parent = save;
    361 
    362                 update_balance();
    363                 save->update_balance();
    364             }
    365         }
    366 
    367         void set_child(int i, tree_node * node)
    368         {
    369             m_child[i] = node;
    370             if (node)
    371                 node->m_parent_slot = &m_child[i];
     349            int i = -1 + (get_balance() == -2) + 2 * (get_balance() == 2);
     350
     351            if (i != -1)
     352            {
     353                tree_node * replacement = nullptr;
     354
     355
     356                if (get_balance() / 2 + m_child[i]->get_balance() == 0)
     357                {
     358                    replacement = m_child[i]->m_child[1 - i];
     359                    tree_node * save0 = replacement->m_child[i];
     360                    tree_node * save1 = replacement->m_child[1 - i];
     361
     362                    replacement->m_parent_slot = this->m_parent_slot;
     363                    *replacement->m_parent_slot = replacement;
     364
     365                    replacement->m_child[i] = m_child[i];
     366                    m_child[i]->m_parent_slot = &replacement->m_child[i];
     367
     368                    replacement->m_child[1 - i] = this;
     369                    this->m_parent_slot = &replacement->m_child[1 - i];
     370
     371                    replacement->m_child[i]->m_child[1 - i] = save0;
     372                    if (save0)
     373                        save0->m_parent_slot = &replacement->m_child[i]->m_child[1 - i];
     374
     375                    replacement->m_child[1 - i]->m_child[i] = save1;
     376                    if (save1)
     377                        save1->m_parent_slot = &replacement->m_child[i]->m_child[1 - i];
     378                }
     379                else
     380                {
     381
     382                    replacement = m_child[i];
     383                    tree_node * save = replacement->m_child[1 - i];
     384
     385                    replacement->m_parent_slot = this->m_parent_slot;
     386                    *replacement->m_parent_slot = replacement;
     387
     388                    replacement->m_child[1 - i] = this;
     389                    this->m_parent_slot = &replacement->m_child[1 - i];
     390
     391                    this->m_child[i] = save;
     392                    if (save)
     393                        save->m_parent_slot = &this->m_child[i];
     394                }
     395
     396                replacement->m_child[0]->update_balance();
     397                replacement->m_child[1]->update_balance();
     398                replacement->update_balance();
     399            }
    372400        }
    373401
     
    399427                    replacement->m_child[1]->m_parent_slot = &replacement->m_child[1];
    400428
     429                if (replacement->m_child[1-i])
     430                    replacement->m_child[1-i]->deep_balance(replacement->m_key);
     431
    401432                replacement->update_balance();
    402433            }
     
    405436
    406437            replace_chain(replacement);
     438        }
     439
     440        void deep_balance(K const & key)
     441        {
     442            int i = -1 + (key < m_key) + 2 * (m_key < key);
     443
     444            if (i != -1 && m_child[i])
     445                m_child[i]->deep_balance(key);
     446
     447            update_balance();
    407448        }
    408449
  • trunk/src/t/base/map.cpp

    r3839 r3842  
    126126        for (int i = 0 ; i < 10000 ; ++i)
    127127        {
     128            // debug output
     129            // std::cout << "i " << i << ", a " << (int)a << ", b " << (int)b  << std::endl;
     130
    128131            m[a] = b;
    129132            m.remove(b);
     
    132135            value[a] = b;
    133136            presence[b] = 0;
    134 
    135             // debug output
    136             // std::cout << "a " << (int)a << ", b " << (int)b  << std::endl;
    137137
    138138            a = a * b + c;
Note: See TracChangeset for help on using the changeset viewer.