libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file splay_fn_imps.hpp
  44  * Contains an implementation class for splay_tree_.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 void
  49 PB_DS_CLASS_C_DEC::
  50 splay(node_pointer p_nd)
  51 {
  52   while (p_nd->m_p_parent != PB_DS_BASE_C_DEC::m_p_head)
  53     {
  54 #ifdef PB_DS_SPLAY_TREE_DEBUG_
  55       {
  56         node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head;
  57
  58         assert_special_imp(p_head);
  59       }
  60 #endif // #ifdef PB_DS_SPLAY_TREE_DEBUG_
  61
  62       PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_nd);)
  63
  64         if (p_nd->m_p_parent->m_p_parent ==
  65             PB_DS_BASE_C_DEC::m_p_head)
  66           {
  67             PB_DS_BASE_C_DEC::rotate_parent(p_nd);
  68
  69             PB_DS_DBG_ASSERT(p_nd == this->m_p_head->m_p_parent);
  70           }
  71         else
  72           {
  73             const node_pointer p_parent = p_nd->m_p_parent;
  74             const node_pointer p_grandparent = p_parent->m_p_parent;
  75
  76 #ifdef PB_DS_SPLAY_TREE_DEBUG_
  77             const size_type total =
  78               PB_DS_BASE_C_DEC::recursive_count(p_grandparent);
  79
  80             PB_DS_DBG_ASSERT(total >= 3);
  81 #endif // #ifdef PB_DS_SPLAY_TREE_DEBUG_
  82
  83             if (p_parent->m_p_left == p_nd&&
  84                 p_grandparent->m_p_right == p_parent)
  85               splay_zig_zag_left(p_nd, p_parent, p_grandparent);
  86             else if (p_parent->m_p_right == p_nd&&
  87                      p_grandparent->m_p_left == p_parent)
  88               splay_zig_zag_right(p_nd, p_parent, p_grandparent);
  89             else if (p_parent->m_p_left == p_nd&&
  90                      p_grandparent->m_p_left == p_parent)
  91               splay_zig_zig_left(p_nd, p_parent, p_grandparent);
  92             else
  93               splay_zig_zig_right(p_nd, p_parent, p_grandparent);
  94
  95             PB_DS_DBG_ASSERT(total ==this->recursive_count(p_nd));
  96           }
  97
  98       PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_nd);)
  99         }
 100 }
 101
 102 PB_DS_CLASS_T_DEC
 103 inline void
 104 PB_DS_CLASS_C_DEC::
 105 splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
 106 {
 107   PB_DS_DBG_ASSERT(p_parent == p_nd->m_p_parent);
 108   PB_DS_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
 109
 110   PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);)
 111
 112     PB_DS_DBG_ASSERT(p_parent->m_p_left == p_nd&&
 113                      p_grandparent->m_p_right == p_parent);
 114
 115   splay_zz_start(p_nd, p_parent, p_grandparent);
 116
 117   node_pointer p_b = p_nd->m_p_right;
 118   node_pointer p_c = p_nd->m_p_left;
 119
 120   p_nd->m_p_right = p_parent;
 121   p_parent->m_p_parent = p_nd;
 122
 123   p_nd->m_p_left = p_grandparent;
 124   p_grandparent->m_p_parent = p_nd;
 125
 126   p_parent->m_p_left = p_b;
 127   if (p_b != NULL)
 128     p_b->m_p_parent = p_parent;
 129
 130   p_grandparent->m_p_right = p_c;
 131   if (p_c != NULL)
 132     p_c->m_p_parent = p_grandparent;
 133
 134   splay_zz_end(p_nd, p_parent, p_grandparent);
 135 }
 136
 137 PB_DS_CLASS_T_DEC
 138 inline void
 139 PB_DS_CLASS_C_DEC::
 140 splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
 141 {
 142   PB_DS_DBG_ASSERT(p_parent == p_nd->m_p_parent);
 143   PB_DS_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
 144
 145   PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);)
 146
 147     PB_DS_DBG_ASSERT(p_parent->m_p_right == p_nd&&
 148                      p_grandparent->m_p_left == p_parent);
 149
 150   splay_zz_start(p_nd, p_parent, p_grandparent);
 151
 152   node_pointer p_b = p_nd->m_p_left;
 153   node_pointer p_c = p_nd->m_p_right;
 154
 155   p_nd->m_p_left = p_parent;
 156   p_parent->m_p_parent = p_nd;
 157
 158   p_nd->m_p_right = p_grandparent;
 159   p_grandparent->m_p_parent = p_nd;
 160
 161   p_parent->m_p_right = p_b;
 162   if (p_b != NULL)
 163     p_b->m_p_parent = p_parent;
 164
 165   p_grandparent->m_p_left = p_c;
 166   if (p_c != NULL)
 167     p_c->m_p_parent = p_grandparent;
 168
 169   splay_zz_end(p_nd, p_parent, p_grandparent);
 170 }
 171
 172 PB_DS_CLASS_T_DEC
 173 inline void
 174 PB_DS_CLASS_C_DEC::
 175 splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
 176 {
 177   PB_DS_DBG_ASSERT(p_parent == p_nd->m_p_parent);
 178   PB_DS_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
 179
 180   PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);)
 181
 182     PB_DS_DBG_ASSERT(p_parent->m_p_left == p_nd&&
 183                      p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent);
 184
 185   splay_zz_start(p_nd, p_parent, p_grandparent);
 186
 187   node_pointer p_b = p_nd->m_p_right;
 188   node_pointer p_c = p_parent->m_p_right;
 189
 190   p_nd->m_p_right = p_parent;
 191   p_parent->m_p_parent = p_nd;
 192
 193   p_parent->m_p_right = p_grandparent;
 194   p_grandparent->m_p_parent = p_parent;
 195
 196   p_parent->m_p_left = p_b;
 197   if (p_b != NULL)
 198     p_b->m_p_parent = p_parent;
 199
 200   p_grandparent->m_p_left = p_c;
 201   if (p_c != NULL)
 202     p_c->m_p_parent = p_grandparent;
 203
 204   splay_zz_end(p_nd, p_parent, p_grandparent);
 205 }
 206
 207 PB_DS_CLASS_T_DEC
 208 inline void
 209 PB_DS_CLASS_C_DEC::
 210 splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
 211 {
 212   PB_DS_DBG_ASSERT(p_parent == p_nd->m_p_parent);
 213   PB_DS_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
 214
 215   PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_grandparent);)
 216
 217     PB_DS_DBG_ASSERT(p_parent->m_p_right == p_nd&&
 218                      p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent);
 219
 220   splay_zz_start(p_nd, p_parent, p_grandparent);
 221
 222   node_pointer p_b = p_nd->m_p_left;
 223   node_pointer p_c = p_parent->m_p_left;
 224
 225   p_nd->m_p_left = p_parent;
 226   p_parent->m_p_parent = p_nd;
 227
 228   p_parent->m_p_left = p_grandparent;
 229   p_grandparent->m_p_parent = p_parent;
 230
 231   p_parent->m_p_right = p_b;
 232   if (p_b != NULL)
 233     p_b->m_p_parent = p_parent;
 234
 235   p_grandparent->m_p_right = p_c;
 236   if (p_c != NULL)
 237     p_c->m_p_parent = p_grandparent;
 238
 239   PB_DS_BASE_C_DEC::update_to_top(
 240                                   p_grandparent, (node_update* )this);
 241
 242   splay_zz_end(p_nd, p_parent, p_grandparent);
 243 }
 244
 245 PB_DS_CLASS_T_DEC
 246 inline void
 247 PB_DS_CLASS_C_DEC::
 248 splay_zz_start(node_pointer p_nd,
 249 #ifdef PB_DS_SPLAY_TREE_DEBUG_
 250                node_pointer p_parent,
 251 #else // #ifdef PB_DS_SPLAY_TREE_DEBUG_
 252                node_pointer /*p_parent*/,
 253 #endif // #ifdef PB_DS_SPLAY_TREE_DEBUG_
 254                node_pointer p_grandparent)
 255 {
 256   PB_DS_DBG_ASSERT(p_nd != NULL);
 257   PB_DS_DBG_ASSERT(p_parent != NULL);
 258   PB_DS_DBG_ASSERT(p_grandparent != NULL);
 259
 260   const bool grandparent_head =
 261     p_grandparent->m_p_parent == PB_DS_BASE_C_DEC::m_p_head;
 262
 263   if (grandparent_head)
 264     {
 265       PB_DS_BASE_C_DEC::m_p_head->m_p_parent =
 266         PB_DS_BASE_C_DEC::m_p_head->m_p_parent;
 267
 268       p_nd->m_p_parent = PB_DS_BASE_C_DEC::m_p_head;
 269
 270       return;
 271     }
 272
 273   node_pointer p_greatgrandparent = p_grandparent->m_p_parent;
 274
 275   p_nd->m_p_parent = p_greatgrandparent;
 276
 277   if (p_grandparent == p_greatgrandparent->m_p_left)
 278     p_greatgrandparent->m_p_left = p_nd;
 279   else
 280     p_greatgrandparent->m_p_right = p_nd;
 281 }
 282
 283 PB_DS_CLASS_T_DEC
 284 inline void
 285 PB_DS_CLASS_C_DEC::
 286 splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
 287 {
 288   if (p_nd->m_p_parent == PB_DS_BASE_C_DEC::m_p_head)
 289     PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_nd;
 290
 291   apply_update(p_grandparent, (node_update* )this);
 292   apply_update(p_parent, (node_update* )this);
 293   apply_update(p_nd, (node_update* )this);
 294
 295   PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_node_consistent(p_nd);)
 296     }
 297