<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta name="robots" content="noindex">
<meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>eavlmmap.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body bgcolor="#ffffff">
<!-- Generated by Doxygen 1.2.5 on Mon Oct 14 14:16:36 2002 -->
<center>
<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Compound Members</a> <a class="qindex" href="pages.html">Related Pages</a> </center>
<hr><h1>eavlmmap.h</h1><div class="fragment"><pre>00001 <font class="comment">//</font>
00002 <font class="comment">// eavlmmap.h --- definition for embedded avl multimap class</font>
00003 <font class="comment">//</font>
00004 <font class="comment">// Copyright (C) 1996 Limit Point Systems, Inc.</font>
00005 <font class="comment">//</font>
00006 <font class="comment">// Author: Curtis Janssen <cljanss@limitpt.com></font>
00007 <font class="comment">// Maintainer: LPS</font>
00008 <font class="comment">//</font>
00009 <font class="comment">// This file is part of the SC Toolkit.</font>
00010 <font class="comment">//</font>
00011 <font class="comment">// The SC Toolkit is free software; you can redistribute it and/or modify</font>
00012 <font class="comment">// it under the terms of the GNU Library General Public License as published by</font>
00013 <font class="comment">// the Free Software Foundation; either version 2, or (at your option)</font>
00014 <font class="comment">// any later version.</font>
00015 <font class="comment">//</font>
00016 <font class="comment">// The SC Toolkit is distributed in the hope that it will be useful,</font>
00017 <font class="comment">// but WITHOUT ANY WARRANTY; without even the implied warranty of</font>
00018 <font class="comment">// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</font>
00019 <font class="comment">// GNU Library General Public License for more details.</font>
00020 <font class="comment">//</font>
00021 <font class="comment">// You should have received a copy of the GNU Library General Public License</font>
00022 <font class="comment">// along with the SC Toolkit; see the file COPYING.LIB. If not, write to</font>
00023 <font class="comment">// the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.</font>
00024 <font class="comment">//</font>
00025 <font class="comment">// The U.S. Government is granted a limited license as per AL 91-7.</font>
00026 <font class="comment">//</font>
00027
00028 <font class="preprocessor">#ifndef _util_container_eavlmmap_h</font>
00029 <font class="preprocessor"></font><font class="preprocessor">#define _util_container_eavlmmap_h</font>
00030 <font class="preprocessor"></font>
00031 <font class="preprocessor">#ifdef HAVE_CONFIG_H</font>
00032 <font class="preprocessor"></font><font class="preprocessor"># include <scconfig.h></font>
00033 <font class="preprocessor">#endif</font>
00034 <font class="preprocessor"></font><font class="preprocessor">#include <iostream></font>
00035 <font class="preprocessor">#include <util/misc/exenv.h></font>
00036 <font class="preprocessor">#include <util/container/compare.h></font>
00037 <font class="preprocessor">#include <unistd.h></font> <font class="comment">// for size_t on solaris</font>
00038 <font class="preprocessor">#include <stdlib.h></font>
00039
00040 <font class="preprocessor">#ifdef __GNUC__</font>
00041 <font class="preprocessor"></font><font class="comment">// gcc typename seems to be broken in some cases</font>
00042 <font class="preprocessor"># define eavl_typename</font>
00043 <font class="preprocessor"></font><font class="preprocessor">#else</font>
00044 <font class="preprocessor"></font><font class="preprocessor"># define eavl_typename typename</font>
00045 <font class="preprocessor"></font><font class="preprocessor">#endif</font>
00046 <font class="preprocessor"></font>
00047 <font class="keyword">namespace </font>sc {
00048
00049 template <class K, class T>
00050 <font class="keyword">class </font>EAVLMMapNode {
00051 <font class="keyword">public</font>:
00052 K key;
00053 T* lt;
00054 T* rt;
00055 T* up;
00056 <font class="keywordtype">int</font> balance;
00057 <font class="keyword">public</font>:
00058 EAVLMMapNode(<font class="keyword">const</font> K& k): key(k) {}
00059 };
00060
00061 template <class K, class T>
00062 <font class="keyword">class </font>EAVLMMap {
00063 <font class="keyword">private</font>:
00064 size_t length_;
00065 T *root_;
00066 T *start_;
00067 EAVLMMapNode<K,T> T::* node_;
00068 <font class="keyword">public</font>:
00069 T*& rlink(T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).rt; }
00070 T* rlink(<font class="keyword">const</font> T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).rt; }
00071 T*& llink(T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).lt; }
00072 T* llink(<font class="keyword">const</font> T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).lt; }
00073 T*& uplink(T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).up; }
00074 T* uplink(<font class="keyword">const</font> T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).up; }
00075 <font class="keywordtype">int</font>& balance(T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).balance; }
00076 <font class="keywordtype">int</font> balance(<font class="keyword">const</font> T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).balance; }
00077 K& key(T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).key; }
00078 <font class="keyword">const</font> K& key(<font class="keyword">const</font> T* n)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> (n->*node_).key; }
00079 <font class="keywordtype">int</font> compare(T*n,T*m)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> sc::compare(key(n), key(m)); }
00080 <font class="keywordtype">int</font> compare(T*n,<font class="keyword">const</font> K&m)<font class="keyword"> const </font>{ <font class="keywordflow">return</font> sc::compare(key(n), m); }
00081 <font class="keyword">private</font>:
00082 <font class="keywordtype">void</font> adjust_balance_insert(T* A, T* child);
00083 <font class="keywordtype">void</font> adjust_balance_remove(T* A, T* child);
00084 <font class="keywordtype">void</font> clear(T*);
00085 <font class="keyword">public</font>:
00086 <font class="keyword">class </font>iterator {
00087 <font class="keyword">private</font>:
00088 EAVLMMap<K,T> *map_;
00089 T *node;
00090 <font class="keyword">public</font>:
00091 iterator(EAVLMMap<K,T> *m, T *n):map_(m),node(n){}
00092 iterator(<font class="keyword">const</font> eavl_typename EAVLMMap<K,T>::iterator &i)<font class="keyword"> </font>{ map_=i.map_; node=i.node; }
00093 <font class="keywordtype">void</font> operator++()<font class="keyword"> </font>{ map_->next(node); }
00094 <font class="keywordtype">void</font> operator++(<font class="keywordtype">int</font>)<font class="keyword"> </font>{ operator++(); }
00095 <font class="keywordtype">int</font> operator == (<font class="keyword">const</font> eavl_typename EAVLMMap<K,T>::iterator &i)<font class="keyword"> const</font>
00096 <font class="keyword"> </font>{ <font class="keywordflow">return</font> map_ == i.map_ && node == i.node; }
00097 <font class="keywordtype">int</font> operator != (<font class="keyword">const</font> eavl_typename EAVLMMap<K,T>::iterator &i)<font class="keyword"> const</font>
00098 <font class="keyword"> </font>{ <font class="keywordflow">return</font> !operator == (i); }
00099 <font class="keywordtype">void</font> operator = (<font class="keyword">const</font> eavl_typename EAVLMMap<K,T>::iterator &i)<font class="keyword"></font>
00100 <font class="keyword"> </font>{ map_ = i.map_; node = i.node; }
00101 <font class="keyword">const</font> K &key()<font class="keyword"> const </font>{ <font class="keywordflow">return</font> map_->key(node); }
00102 T & operator *()<font class="keyword"> </font>{ <font class="keywordflow">return</font> *node; }
00103 T * operator->()<font class="keyword"> </font>{ <font class="keywordflow">return</font> node; }
00104 };
00105 <font class="keyword">public</font>:
00106 EAVLMMap();
00107 EAVLMMap(EAVLMMapNode<K,T> T::* node);
00108 ~EAVLMMap()<font class="keyword"> </font>{ clear(root_); }
00109 <font class="keywordtype">void</font> initialize(EAVLMMapNode<K,T> T::* node);
00110 <font class="keywordtype">void</font> clear_without_delete()<font class="keyword"> </font>{ initialize(node_); }
00111 <font class="keywordtype">void</font> clear()<font class="keyword"> </font>{ clear(root_); initialize(node_); }
00112 <font class="keywordtype">void</font> insert(T*);
00113 <font class="keywordtype">void</font> remove(T*);
00114 T* find(<font class="keyword">const</font> K&) <font class="keyword">const</font>;
00115
00116 <font class="keywordtype">int</font> height(T* node);
00117 <font class="keywordtype">int</font> height()<font class="keyword"> </font>{ <font class="keywordflow">return</font> height(root_); }
00118 <font class="keywordtype">void</font> check();
00119 <font class="keywordtype">void</font> check_node(T*) <font class="keyword">const</font>;
00120
00121 T* start()<font class="keyword"> const </font>{ <font class="keywordflow">return</font> start_; }
00122 <font class="keywordtype">void</font> next(<font class="keyword">const</font> T*&) <font class="keyword">const</font>;
00123 <font class="keywordtype">void</font> next(T*&) <font class="keyword">const</font>;
00124
00125 iterator begin()<font class="keyword"> </font>{ <font class="keywordflow">return</font> iterator(<font class="keyword">this</font>,start()); }
00126 iterator end()<font class="keyword"> </font>{ <font class="keywordflow">return</font> iterator(<font class="keyword">this</font>,0); }
00127
00128 <font class="keywordtype">void</font> print();
00129 <font class="keywordtype">int</font> length()<font class="keyword"> const </font>{ <font class="keywordflow">return</font> length_; }
00130 <font class="keywordtype">int</font> depth(T*);
00131 };
00132
00133 template <class K, class T>
00134 T*
00135 EAVLMMap<K,T>::find(<font class="keyword">const</font> K& key)<font class="keyword"> const</font>
00136 <font class="keyword"></font>{
00137 T* n = root_;
00138
00139 <font class="keywordflow">while</font> (n) {
00140 <font class="keywordtype">int</font> cmp = compare(n, key);
00141 <font class="keywordflow">if</font> (cmp < 0) n = rlink(n);
00142 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (cmp > 0) n = llink(n);
00143 <font class="keywordflow">else</font> <font class="keywordflow">return</font> n;
00144 }
00145
00146 <font class="keywordflow">return</font> 0;
00147 }
00148
00149 template <class K, class T>
00150 <font class="keywordtype">void</font>
00151 EAVLMMap<K,T>::remove(T* node)<font class="keyword"></font>
00152 <font class="keyword"></font>{
00153 <font class="keywordflow">if</font> (!node) <font class="keywordflow">return</font>;
00154
00155 length_--;
00156
00157 <font class="keywordflow">if</font> (node == start_) {
00158 next(start_);
00159 }
00160
00161 T *rebalance_point;
00162 T *q;
00163
00164 <font class="keywordflow">if</font> (llink(node) == 0) {
00165 q = rlink(node);
00166 rebalance_point = uplink(node);
00167
00168 <font class="keywordflow">if</font> (q) uplink(q) = rebalance_point;
00169
00170 <font class="keywordflow">if</font> (rebalance_point) {
00171 <font class="keywordflow">if</font> (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
00172 <font class="keywordflow">else</font> llink(rebalance_point) = q;
00173 }
00174 <font class="keywordflow">else</font> root_ = q;
00175 }
00176 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (rlink(node) == 0) {
00177 q = llink(node);
00178 rebalance_point = uplink(node);
00179
00180 <font class="keywordflow">if</font> (q) uplink(q) = rebalance_point;
00181
00182 <font class="keywordflow">if</font> (rebalance_point) {
00183 <font class="keywordflow">if</font> (rlink(rebalance_point) == node) rlink(rebalance_point) = q;
00184 <font class="keywordflow">else</font> llink(rebalance_point) = q;
00185 }
00186 <font class="keywordflow">else</font> root_ = q;
00187 }
00188 <font class="keywordflow">else</font> {
00189 T *r = node;
00190 next(r);
00191
00192 <font class="keywordflow">if</font> (r == 0 || llink(r) != 0) {
00193 ExEnv::errn() << <font class="stringliteral">"EAVLMMap::remove: inconsistency"</font> << std::endl;
00194 abort();
00195 }
00196
00197 <font class="keywordflow">if</font> (r == rlink(node)) {
00198 llink(r) = llink(node);
00199 <font class="keywordflow">if</font> (llink(r)) uplink(llink(r)) = r;
00200 balance(r) = balance(node);
00201 rebalance_point = r;
00202 q = rlink(r);
00203 }
00204 <font class="keywordflow">else</font> {
00205 q = rlink(r);
00206
00207 rebalance_point = uplink(r);
00208
00209 <font class="keywordflow">if</font> (llink(rebalance_point) == r) llink(rebalance_point) = q;
00210 <font class="keywordflow">else</font> rlink(rebalance_point) = q;
00211
00212 <font class="keywordflow">if</font> (q) uplink(q) = rebalance_point;
00213
00214 balance(r) = balance(node);
00215 rlink(r) = rlink(node);
00216 llink(r) = llink(node);
00217 <font class="keywordflow">if</font> (rlink(r)) uplink(rlink(r)) = r;
00218 <font class="keywordflow">if</font> (llink(r)) uplink(llink(r)) = r;
00219 }
00220 <font class="keywordflow">if</font> (r) {
00221 T* up = uplink(node);
00222 uplink(r) = up;
00223 <font class="keywordflow">if</font> (up) {
00224 <font class="keywordflow">if</font> (rlink(up) == node) rlink(up) = r;
00225 <font class="keywordflow">else</font> llink(up) = r;
00226 }
00227 <font class="keywordflow">if</font> (up == 0) root_ = r;
00228 }
00229 }
00230
00231 <font class="comment">// adjust balance won't work if both children are null,</font>
00232 <font class="comment">// so handle this special case here</font>
00233 <font class="keywordflow">if</font> (rebalance_point &&
00234 llink(rebalance_point) == 0 && rlink(rebalance_point) == 0) {
00235 balance(rebalance_point) = 0;
00236 q = rebalance_point;
00237 rebalance_point = uplink(rebalance_point);
00238 }
00239 adjust_balance_remove(rebalance_point, q);
00240 }
00241
00242 template <class K, class T>
00243 <font class="keywordtype">void</font>
00244 EAVLMMap<K,T>::print()<font class="keyword"></font>
00245 <font class="keyword"></font>{
00246 <font class="keywordflow">for</font> (T*n=start(); n; next(n)) {
00247 <font class="keywordtype">int</font> d = depth(n) + 1;
00248 <font class="keywordflow">for</font> (<font class="keywordtype">int</font> i=0; i<d; i++) ExEnv::out0() << <font class="stringliteral">" "</font>;
00249 <font class="keywordflow">if</font> (balance(n) == 1) ExEnv::out0() << <font class="stringliteral">" (+)"</font> << std::endl;
00250 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(n) == -1) ExEnv::out0() << <font class="stringliteral">" (-)"</font> << std::endl;
00251 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(n) == 0) ExEnv::out0() << <font class="stringliteral">" (.)"</font> << std::endl;
00252 <font class="keywordflow">else</font> ExEnv::out0() << <font class="stringliteral">" ("</font> << balance(n) << <font class="stringliteral">")"</font> << std::endl;
00253 }
00254 }
00255
00256 template <class K, class T>
00257 <font class="keywordtype">int</font>
00258 EAVLMMap<K,T>::depth(T*node)<font class="keyword"></font>
00259 <font class="keyword"></font>{
00260 <font class="keywordtype">int</font> d = 0;
00261 <font class="keywordflow">while</font> (node) {
00262 node = uplink(node);
00263 d++;
00264 }
00265 <font class="keywordflow">return</font> d;
00266 }
00267
00268 template <class K, class T>
00269 <font class="keywordtype">void</font>
00270 EAVLMMap<K,T>::check_node(T*n)<font class="keyword"> const</font>
00271 <font class="keyword"></font>{
00272 <font class="keywordflow">if</font> (uplink(n) && uplink(n) == n) abort();
00273 <font class="keywordflow">if</font> (llink(n) && llink(n) == n) abort();
00274 <font class="keywordflow">if</font> (rlink(n) && rlink(n) == n) abort();
00275 <font class="keywordflow">if</font> (rlink(n) && rlink(n) == llink(n)) abort();
00276 <font class="keywordflow">if</font> (uplink(n) && uplink(n) == llink(n)) abort();
00277 <font class="keywordflow">if</font> (uplink(n) && uplink(n) == rlink(n)) abort();
00278 <font class="keywordflow">if</font> (uplink(n) && !(llink(uplink(n)) == n
00279 || rlink(uplink(n)) == n)) abort();
00280 }
00281
00282 template <class K, class T>
00283 <font class="keywordtype">void</font>
00284 EAVLMMap<K,T>::clear(T*n)<font class="keyword"></font>
00285 <font class="keyword"></font>{
00286 <font class="keywordflow">if</font> (!n) <font class="keywordflow">return</font>;
00287 clear(llink(n));
00288 clear(rlink(n));
00289 <font class="keyword">delete</font> n;
00290 }
00291
00292 template <class K, class T>
00293 <font class="keywordtype">int</font>
00294 EAVLMMap<K,T>::height(T* node)<font class="keyword"></font>
00295 <font class="keyword"></font>{
00296 <font class="keywordflow">if</font> (!node) <font class="keywordflow">return</font> 0;
00297 <font class="keywordtype">int</font> rh = height(rlink(node)) + 1;
00298 <font class="keywordtype">int</font> lh = height(llink(node)) + 1;
00299 <font class="keywordflow">return</font> rh>lh?rh:lh;
00300 }
00301
00302 template <class K, class T>
00303 <font class="keywordtype">void</font>
00304 EAVLMMap<K,T>::check()<font class="keyword"></font>
00305 <font class="keyword"></font>{
00306 T* node;
00307 T* prev=0;
00308 size_t computed_length = 0;
00309 <font class="keywordflow">for</font> (node = start(); node; next(node)) {
00310 check_node(node);
00311 <font class="keywordflow">if</font> (prev && compare(prev,node) > 0) {
00312 ExEnv::errn() << <font class="stringliteral">"nodes out of order"</font> << std::endl;
00313 abort();
00314 }
00315 prev = node;
00316 computed_length++;
00317 }
00318 <font class="keywordflow">for</font> (node = start(); node; next(node)) {
00319 <font class="keywordflow">if</font> (balance(node) != height(rlink(node)) - height(llink(node))) {
00320 ExEnv::errn() << <font class="stringliteral">"balance inconsistency"</font> << std::endl;
00321 abort();
00322 }
00323 <font class="keywordflow">if</font> (balance(node) < -1 || balance(node) > 1) {
00324 ExEnv::errn() << <font class="stringliteral">"balance out of range"</font> << std::endl;
00325 abort();
00326 }
00327 }
00328 <font class="keywordflow">if</font> (length_ != computed_length) {
00329 ExEnv::errn() << <font class="stringliteral">"length error"</font> << std::endl;
00330 abort();
00331 }
00332 }
00333
00334 template <class K, class T>
00335 <font class="keywordtype">void</font>
00336 EAVLMMap<K,T>::next(<font class="keyword">const</font> T*& node)<font class="keyword"> const</font>
00337 <font class="keyword"></font>{
00338 <font class="keyword">const</font> T* r;
00339 <font class="keywordflow">if</font> (r = rlink(node)) {
00340 node = r;
00341 <font class="keywordflow">while</font> (r = llink(node)) node = r;
00342 <font class="keywordflow">return</font>;
00343 }
00344 <font class="keywordflow">while</font> (r = uplink(node)) {
00345 <font class="keywordflow">if</font> (node == llink(r)) {
00346 node = r;
00347 <font class="keywordflow">return</font>;
00348 }
00349 node = r;
00350 }
00351 node = 0;
00352 }
00353
00354 template <class K, class T>
00355 <font class="keywordtype">void</font>
00356 EAVLMMap<K,T>::next(T*& node)<font class="keyword"> const</font>
00357 <font class="keyword"></font>{
00358 T* r;
00359 <font class="keywordflow">if</font> (r = rlink(node)) {
00360 node = r;
00361 <font class="keywordflow">while</font> (r = llink(node)) node = r;
00362 <font class="keywordflow">return</font>;
00363 }
00364 <font class="keywordflow">while</font> (r = uplink(node)) {
00365 <font class="keywordflow">if</font> (node == llink(r)) {
00366 node = r;
00367 <font class="keywordflow">return</font>;
00368 }
00369 node = r;
00370 }
00371 node = 0;
00372 }
00373
00374 template <class K, class T>
00375 <font class="keywordtype">void</font>
00376 EAVLMMap<K,T>::insert(T* n)<font class="keyword"></font>
00377 <font class="keyword"></font>{
00378 <font class="keywordflow">if</font> (!n) {
00379 <font class="keywordflow">return</font>;
00380 }
00381
00382 length_++;
00383
00384 rlink(n) = 0;
00385 llink(n) = 0;
00386 balance(n) = 0;
00387
00388 <font class="keywordflow">if</font> (!root_) {
00389 uplink(n) = 0;
00390 root_ = n;
00391 start_ = n;
00392 <font class="keywordflow">return</font>;
00393 }
00394
00395 <font class="comment">// find an insertion point</font>
00396 T* p = root_;
00397 T* prev_p = 0;
00398 <font class="keywordtype">int</font> cmp;
00399 <font class="keywordtype">int</font> have_start = 1;
00400 <font class="keywordflow">while</font> (p) {
00401 <font class="keywordflow">if</font> (p == n) {
00402 abort();
00403 }
00404 prev_p = p;
00405 cmp = compare(n,p);
00406 <font class="keywordflow">if</font> (cmp < 0) p = llink(p);
00407 <font class="keywordflow">else</font> {
00408 p = rlink(p);
00409 have_start = 0;
00410 }
00411 }
00412
00413 <font class="comment">// insert the node</font>
00414 uplink(n) = prev_p;
00415 <font class="keywordflow">if</font> (prev_p) {
00416 <font class="keywordflow">if</font> (cmp < 0) llink(prev_p) = n;
00417 <font class="keywordflow">else</font> rlink(prev_p) = n;
00418 }
00419
00420 <font class="comment">// maybe update the first node in the map</font>
00421 <font class="keywordflow">if</font> (have_start) start_ = n;
00422
00423 <font class="comment">// adjust the balance factors</font>
00424 <font class="keywordflow">if</font> (prev_p) {
00425 adjust_balance_insert(prev_p, n);
00426 }
00427 }
00428
00429 template <class K, class T>
00430 <font class="keywordtype">void</font>
00431 EAVLMMap<K,T>::adjust_balance_insert(T* A, T* child)<font class="keyword"></font>
00432 <font class="keyword"></font>{
00433 <font class="keywordflow">if</font> (!A) <font class="keywordflow">return</font>;
00434 <font class="keywordtype">int</font> adjustment;
00435 <font class="keywordflow">if</font> (llink(A) == child) adjustment = -1;
00436 <font class="keywordflow">else</font> adjustment = 1;
00437 <font class="keywordtype">int</font> bal = balance(A) + adjustment;
00438 <font class="keywordflow">if</font> (bal == 0) {
00439 balance(A) = 0;
00440 }
00441 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (bal == -1 || bal == 1) {
00442 balance(A) = bal;
00443 adjust_balance_insert(uplink(A), A);
00444 }
00445 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (bal == 2) {
00446 T* B = rlink(A);
00447 <font class="keywordflow">if</font> (balance(B) == 1) {
00448 balance(B) = 0;
00449 balance(A) = 0;
00450 rlink(A) = llink(B);
00451 llink(B) = A;
00452 uplink(B) = uplink(A);
00453 uplink(A) = B;
00454 <font class="keywordflow">if</font> (rlink(A)) uplink(rlink(A)) = A;
00455 <font class="keywordflow">if</font> (llink(B)) uplink(llink(B)) = B;
00456 <font class="keywordflow">if</font> (uplink(B) == 0) root_ = B;
00457 <font class="keywordflow">else</font> {
00458 <font class="keywordflow">if</font> (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
00459 <font class="keywordflow">else</font> llink(uplink(B)) = B;
00460 }
00461 }
00462 <font class="keywordflow">else</font> {
00463 T* X = llink(B);
00464 rlink(A) = llink(X);
00465 llink(B) = rlink(X);
00466 llink(X) = A;
00467 rlink(X) = B;
00468 <font class="keywordflow">if</font> (balance(X) == 1) {
00469 balance(A) = -1;
00470 balance(B) = 0;
00471 }
00472 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(X) == -1) {
00473 balance(A) = 0;
00474 balance(B) = 1;
00475 }
00476 <font class="keywordflow">else</font> {
00477 balance(A) = 0;
00478 balance(B) = 0;
00479 }
00480 balance(X) = 0;
00481 uplink(X) = uplink(A);
00482 uplink(A) = X;
00483 uplink(B) = X;
00484 <font class="keywordflow">if</font> (rlink(A)) uplink(rlink(A)) = A;
00485 <font class="keywordflow">if</font> (llink(B)) uplink(llink(B)) = B;
00486 <font class="keywordflow">if</font> (uplink(X) == 0) root_ = X;
00487 <font class="keywordflow">else</font> {
00488 <font class="keywordflow">if</font> (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
00489 <font class="keywordflow">else</font> llink(uplink(X)) = X;
00490 }
00491 }
00492 }
00493 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (bal == -2) {
00494 T* B = llink(A);
00495 <font class="keywordflow">if</font> (balance(B) == -1) {
00496 balance(B) = 0;
00497 balance(A) = 0;
00498 llink(A) = rlink(B);
00499 rlink(B) = A;
00500 uplink(B) = uplink(A);
00501 uplink(A) = B;
00502 <font class="keywordflow">if</font> (llink(A)) uplink(llink(A)) = A;
00503 <font class="keywordflow">if</font> (rlink(B)) uplink(rlink(B)) = B;
00504 <font class="keywordflow">if</font> (uplink(B) == 0) root_ = B;
00505 <font class="keywordflow">else</font> {
00506 <font class="keywordflow">if</font> (llink(uplink(B)) == A) llink(uplink(B)) = B;
00507 <font class="keywordflow">else</font> rlink(uplink(B)) = B;
00508 }
00509 }
00510 <font class="keywordflow">else</font> {
00511 T* X = rlink(B);
00512 llink(A) = rlink(X);
00513 rlink(B) = llink(X);
00514 rlink(X) = A;
00515 llink(X) = B;
00516 <font class="keywordflow">if</font> (balance(X) == -1) {
00517 balance(A) = 1;
00518 balance(B) = 0;
00519 }
00520 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(X) == 1) {
00521 balance(A) = 0;
00522 balance(B) = -1;
00523 }
00524 <font class="keywordflow">else</font> {
00525 balance(A) = 0;
00526 balance(B) = 0;
00527 }
00528 balance(X) = 0;
00529 uplink(X) = uplink(A);
00530 uplink(A) = X;
00531 uplink(B) = X;
00532 <font class="keywordflow">if</font> (llink(A)) uplink(llink(A)) = A;
00533 <font class="keywordflow">if</font> (rlink(B)) uplink(rlink(B)) = B;
00534 <font class="keywordflow">if</font> (uplink(X) == 0) root_ = X;
00535 <font class="keywordflow">else</font> {
00536 <font class="keywordflow">if</font> (llink(uplink(X)) == A) llink(uplink(X)) = X;
00537 <font class="keywordflow">else</font> rlink(uplink(X)) = X;
00538 }
00539 }
00540 }
00541 }
00542
00543 template <class K, class T>
00544 <font class="keywordtype">void</font>
00545 EAVLMMap<K,T>::adjust_balance_remove(T* A, T* child)<font class="keyword"></font>
00546 <font class="keyword"></font>{
00547 <font class="keywordflow">if</font> (!A) <font class="keywordflow">return</font>;
00548 <font class="keywordtype">int</font> adjustment;
00549 <font class="keywordflow">if</font> (llink(A) == child) adjustment = 1;
00550 <font class="keywordflow">else</font> adjustment = -1;
00551 <font class="keywordtype">int</font> bal = balance(A) + adjustment;
00552 <font class="keywordflow">if</font> (bal == 0) {
00553 balance(A) = 0;
00554 adjust_balance_remove(uplink(A), A);
00555 }
00556 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (bal == -1 || bal == 1) {
00557 balance(A) = bal;
00558 }
00559 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (bal == 2) {
00560 T* B = rlink(A);
00561 <font class="keywordflow">if</font> (balance(B) == 0) {
00562 balance(B) = -1;
00563 balance(A) = 1;
00564 rlink(A) = llink(B);
00565 llink(B) = A;
00566 uplink(B) = uplink(A);
00567 uplink(A) = B;
00568 <font class="keywordflow">if</font> (rlink(A)) uplink(rlink(A)) = A;
00569 <font class="keywordflow">if</font> (llink(B)) uplink(llink(B)) = B;
00570 <font class="keywordflow">if</font> (uplink(B) == 0) root_ = B;
00571 <font class="keywordflow">else</font> {
00572 <font class="keywordflow">if</font> (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
00573 <font class="keywordflow">else</font> llink(uplink(B)) = B;
00574 }
00575 }
00576 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(B) == 1) {
00577 balance(B) = 0;
00578 balance(A) = 0;
00579 rlink(A) = llink(B);
00580 llink(B) = A;
00581 uplink(B) = uplink(A);
00582 uplink(A) = B;
00583 <font class="keywordflow">if</font> (rlink(A)) uplink(rlink(A)) = A;
00584 <font class="keywordflow">if</font> (llink(B)) uplink(llink(B)) = B;
00585 <font class="keywordflow">if</font> (uplink(B) == 0) root_ = B;
00586 <font class="keywordflow">else</font> {
00587 <font class="keywordflow">if</font> (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
00588 <font class="keywordflow">else</font> llink(uplink(B)) = B;
00589 }
00590 adjust_balance_remove(uplink(B), B);
00591 }
00592 <font class="keywordflow">else</font> {
00593 T* X = llink(B);
00594 rlink(A) = llink(X);
00595 llink(B) = rlink(X);
00596 llink(X) = A;
00597 rlink(X) = B;
00598 <font class="keywordflow">if</font> (balance(X) == 0) {
00599 balance(A) = 0;
00600 balance(B) = 0;
00601 }
00602 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(X) == 1) {
00603 balance(A) = -1;
00604 balance(B) = 0;
00605 }
00606 <font class="keywordflow">else</font> {
00607 balance(A) = 0;
00608 balance(B) = 1;
00609 }
00610 balance(X) = 0;
00611 uplink(X) = uplink(A);
00612 uplink(A) = X;
00613 uplink(B) = X;
00614 <font class="keywordflow">if</font> (rlink(A)) uplink(rlink(A)) = A;
00615 <font class="keywordflow">if</font> (llink(B)) uplink(llink(B)) = B;
00616 <font class="keywordflow">if</font> (uplink(X) == 0) root_ = X;
00617 <font class="keywordflow">else</font> {
00618 <font class="keywordflow">if</font> (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
00619 <font class="keywordflow">else</font> llink(uplink(X)) = X;
00620 }
00621 adjust_balance_remove(uplink(X), X);
00622 }
00623 }
00624 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (bal == -2) {
00625 T* B = llink(A);
00626 <font class="keywordflow">if</font> (balance(B) == 0) {
00627 balance(B) = 1;
00628 balance(A) = -1;
00629 llink(A) = rlink(B);
00630 rlink(B) = A;
00631 uplink(B) = uplink(A);
00632 uplink(A) = B;
00633 <font class="keywordflow">if</font> (llink(A)) uplink(llink(A)) = A;
00634 <font class="keywordflow">if</font> (rlink(B)) uplink(rlink(B)) = B;
00635 <font class="keywordflow">if</font> (uplink(B) == 0) root_ = B;
00636 <font class="keywordflow">else</font> {
00637 <font class="keywordflow">if</font> (llink(uplink(B)) == A) llink(uplink(B)) = B;
00638 <font class="keywordflow">else</font> rlink(uplink(B)) = B;
00639 }
00640 }
00641 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(B) == -1) {
00642 balance(B) = 0;
00643 balance(A) = 0;
00644 llink(A) = rlink(B);
00645 rlink(B) = A;
00646 uplink(B) = uplink(A);
00647 uplink(A) = B;
00648 <font class="keywordflow">if</font> (llink(A)) uplink(llink(A)) = A;
00649 <font class="keywordflow">if</font> (rlink(B)) uplink(rlink(B)) = B;
00650 <font class="keywordflow">if</font> (uplink(B) == 0) root_ = B;
00651 <font class="keywordflow">else</font> {
00652 <font class="keywordflow">if</font> (llink(uplink(B)) == A) llink(uplink(B)) = B;
00653 <font class="keywordflow">else</font> rlink(uplink(B)) = B;
00654 }
00655 adjust_balance_remove(uplink(B), B);
00656 }
00657 <font class="keywordflow">else</font> {
00658 T* X = rlink(B);
00659 llink(A) = rlink(X);
00660 rlink(B) = llink(X);
00661 rlink(X) = A;
00662 llink(X) = B;
00663 <font class="keywordflow">if</font> (balance(X) == 0) {
00664 balance(A) = 0;
00665 balance(B) = 0;
00666 }
00667 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (balance(X) == -1) {
00668 balance(A) = 1;
00669 balance(B) = 0;
00670 }
00671 <font class="keywordflow">else</font> {
00672 balance(A) = 0;
00673 balance(B) = -1;
00674 }
00675 balance(X) = 0;
00676 uplink(X) = uplink(A);
00677 uplink(A) = X;
00678 uplink(B) = X;
00679 <font class="keywordflow">if</font> (llink(A)) uplink(llink(A)) = A;
00680 <font class="keywordflow">if</font> (rlink(B)) uplink(rlink(B)) = B;
00681 <font class="keywordflow">if</font> (uplink(X) == 0) root_ = X;
00682 <font class="keywordflow">else</font> {
00683 <font class="keywordflow">if</font> (llink(uplink(X)) == A) llink(uplink(X)) = X;
00684 <font class="keywordflow">else</font> rlink(uplink(X)) = X;
00685 }
00686 adjust_balance_remove(uplink(X), X);
00687 }
00688 }
00689 }
00690
00691 template <class K, class T>
00692 <font class="keyword">inline</font>
00693 EAVLMMap<K,T>::EAVLMMap()<font class="keyword"></font>
00694 <font class="keyword"></font>{
00695 initialize(0);
00696 }
00697
00698 template <class K, class T>
00699 <font class="keyword">inline</font>
00700 EAVLMMap<K,T>::EAVLMMap(EAVLMMapNode<K,T> T::* node)<font class="keyword"></font>
00701 <font class="keyword"></font>{
00702 initialize(node);
00703 }
00704
00705 template <class K, class T>
00706 <font class="keyword">inline</font> <font class="keywordtype">void</font>
00707 EAVLMMap<K,T>::initialize(EAVLMMapNode<K,T> T::* node)<font class="keyword"></font>
00708 <font class="keyword"></font>{
00709 node_ = node;
00710 root_ = 0;
00711 start_ = 0;
00712 length_ = 0;
00713 }
00714
00715 }
00716
00717 <font class="preprocessor">#endif</font>
00718 <font class="preprocessor"></font>
00719 <font class="comment">// ///////////////////////////////////////////////////////////////////////////</font>
00720
00721 <font class="comment">// Local Variables:</font>
00722 <font class="comment">// mode: c++</font>
00723 <font class="comment">// c-file-style: "CLJ"</font>
00724 <font class="comment">// End:</font>
</div></pre><hr>
<address>
<small>
Generated at Mon Oct 14 14:16:36 2002 for <a
href="http://aros.ca.sandia.gov/~cljanss/mpqc">MPQC</a>
2.1.2 using the documentation package <a
href="http://www.stack.nl/~dimitri/doxygen/index.html">Doxygen</a>
1.2.5.
</small>
</address>
</body>
</html>
distrib
>
Mandriva
>
9.1
>
ppc
>
media
>
contrib
>
by-pkgid
>
263386785cefb9ae5d63b926d214d809
>
files
>
950
