1// This may look like C code, but it is really -*- C++ -*- 2/* 3Copyright (C) 1988 Free Software Foundation 4 written by Doug Lea (dl@rocky.oswego.edu) 5 6This file is part of GNU CC. 7 8GNU CC is distributed in the hope that it will be useful, 9but WITHOUT ANY WARRANTY. No author or distributor 10accepts responsibility to anyone for the consequences of using it 11or for whether it serves any particular purpose or works at all, 12unless he says so in writing. Refer to the GNU CC General Public 13License for full details. 14 15Everyone is granted permission to copy, modify and redistribute 16GNU CC, but only under the conditions described in the 17GNU CC General Public License. A copy of this license is 18supposed to have been given to you along with GNU CC so you 19can know your rights and responsibilities. It should be in a 20file named COPYING. Among other things, the copyright notice 21and this notice must be preserved on all copies. 22*/ 23 24 25#ifndef _<T><C>AVLMap_h 26#ifdef __GNUG__ 27#pragma once 28#pragma interface 29#endif 30#define _<T><C>AVLMap_h 1 31 32#include "<T>.<C>.Map.h" 33 34struct <T><C>AVLNode 35{ 36 <T><C>AVLNode* lt; 37 <T><C>AVLNode* rt; 38 <T> item; 39 <C> cont; 40 char stat; 41 <T><C>AVLNode(<T&> h, <C&> c, 42 <T><C>AVLNode* l=0, <T><C>AVLNode* r=0); 43 ~<T><C>AVLNode(); 44}; 45 46#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES) 47 48inline <T><C>AVLNode::<T><C>AVLNode(<T&> h, <C&> c, 49 <T><C>AVLNode* l, <T><C>AVLNode* r) 50 :item(h), cont(c), lt(l), rt(r), stat(0) {} 51 52inline <T><C>AVLNode::~<T><C>AVLNode() {} 53 54#endif 55 56typedef <T><C>AVLNode* <T><C>AVLNodePtr; 57 58 59class <T><C>AVLMap : public <T><C>Map 60{ 61protected: 62 <T><C>AVLNode* root; 63 64 <T><C>AVLNode* leftmost(); 65 <T><C>AVLNode* rightmost(); 66 <T><C>AVLNode* pred(<T><C>AVLNode* t); 67 <T><C>AVLNode* succ(<T><C>AVLNode* t); 68 void _kill(<T><C>AVLNode* t); 69 void _add(<T><C>AVLNode*& t); 70 void _del(<T><C>AVLNode* p, <T><C>AVLNode*& t); 71 72public: 73 <T><C>AVLMap(<C&> dflt); 74 <T><C>AVLMap(<T><C>AVLMap& a); 75 ~<T><C>AVLMap(); 76 77 <C>& operator [] (<T&> key); 78 79 void del(<T&> key); 80 81 Pix first(); 82 void next(Pix& i); 83 <T>& key(Pix i); 84 <C>& contents(Pix i); 85 86 Pix seek(<T&> key); 87 int contains(<T&> key); 88 89 void clear(); 90 91 Pix last(); 92 void prev(Pix& i); 93 94 int OK(); 95}; 96 97#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES) 98 99inline <T><C>AVLMap::~<T><C>AVLMap() 100{ 101 _kill(root); 102} 103 104inline <T><C>AVLMap::<T><C>AVLMap(<C&> dflt) :(dflt) 105{ 106 root = 0; 107} 108 109 110inline Pix <T><C>AVLMap::first() 111{ 112 return Pix(leftmost()); 113} 114 115inline Pix <T><C>AVLMap::last() 116{ 117 return Pix(rightmost()); 118} 119 120inline void <T><C>AVLMap::next(Pix& i) 121{ 122 if (i != 0) i = Pix(succ((<T><C>AVLNode*)i)); 123} 124 125inline void <T><C>AVLMap::prev(Pix& i) 126{ 127 if (i != 0) i = Pix(pred((<T><C>AVLNode*)i)); 128} 129 130inline <T>& <T><C>AVLMap::key(Pix i) 131{ 132 if (i == 0) error("null Pix"); 133 return ((<T><C>AVLNode*)i)->item; 134} 135 136inline <C>& <T><C>AVLMap::contents(Pix i) 137{ 138 if (i == 0) error("null Pix"); 139 return ((<T><C>AVLNode*)i)->cont; 140} 141 142inline void <T><C>AVLMap::clear() 143{ 144 _kill(root); 145 count = 0; 146 root = 0; 147} 148 149inline int <T><C>AVLMap::contains(<T&> key) 150{ 151 return seek(key) != 0; 152} 153 154 155 156#endif 157#endif 158