+// This may look like C code, but it is really -*- C++ -*-
+/*
+Copyright (C) 1988 Free Software Foundation
+ written by Doug Lea (dl@rocky.oswego.edu)
+
+This file is part of GNU CC.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY. No author or distributor
+accepts responsibility to anyone for the consequences of using it
+or for whether it serves any particular purpose or works at all,
+unless he says so in writing. Refer to the GNU CC General Public
+License for full details.
+
+Everyone is granted permission to copy, modify and redistribute
+GNU CC, but only under the conditions described in the
+GNU CC General Public License. A copy of this license is
+supposed to have been given to you along with GNU CC so you
+can know your rights and responsibilities. It should be in a
+file named COPYING. Among other things, the copyright notice
+and this notice must be preserved on all copies.
+*/
+
+
+#ifndef _<T>AVL_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>AVL_h 1
+
+#include "<T>.Set.h"
+
+struct <T>AVLNode
+{
+ <T>AVLNode* lt;
+ <T>AVLNode* rt;
+ <T> item;
+ char stat;
+ <T>AVLNode(<T&> h, <T>AVLNode* l=0, <T>AVLNode* r=0);
+ ~<T>AVLNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>AVLNode::<T>AVLNode(<T&> h, <T>AVLNode* l, <T>AVLNode* r)
+:item(h), lt(l), rt(r), stat(0) {}
+
+inline <T>AVLNode::~<T>AVLNode() {}
+
+#endif
+
+typedef <T>AVLNode* <T>AVLNodePtr;
+
+
+class <T>AVLSet : public <T>Set
+{
+protected:
+ <T>AVLNode* root;
+
+ <T>AVLSet(<T>AVLNode* p, int l);
+
+ <T>AVLNode* leftmost();
+ <T>AVLNode* rightmost();
+ <T>AVLNode* pred(<T>AVLNode* t);
+ <T>AVLNode* succ(<T>AVLNode* t);
+ void _kill(<T>AVLNode* t);
+ void _add(<T>AVLNode*& t);
+ void _del(<T>AVLNode* p, <T>AVLNode*& t);
+
+public:
+ <T>AVLSet();
+ <T>AVLSet(<T>AVLSet& a);
+ ~<T>AVLSet();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ int owns(Pix i);
+ Pix seek(<T&> item);
+
+ Pix last();
+ void prev(Pix& i);
+
+ void operator |= (<T>AVLSet& b);
+ void operator -= (<T>AVLSet& b);
+ void operator &= (<T>AVLSet& b);
+
+ int operator == (<T>AVLSet& b);
+ int operator != (<T>AVLSet& b);
+ int operator <= (<T>AVLSet& b);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>AVLSet::~<T>AVLSet()
+{
+ _kill(root);
+}
+
+inline <T>AVLSet::<T>AVLSet()
+{
+ root = 0;
+ count = 0;
+}
+
+inline <T>AVLSet::<T>AVLSet(<T>AVLNode* p, int l)
+{
+ root = p;
+ count = l;
+}
+
+inline int <T>AVLSet::operator != (<T>AVLSet& b)
+{
+ return ! ((*this) == b);
+}
+
+inline Pix <T>AVLSet::first()
+{
+ return Pix(leftmost());
+}
+
+inline Pix <T>AVLSet::last()
+{
+ return Pix(rightmost());
+}
+
+inline void <T>AVLSet::next(Pix& i)
+{
+ if (i != 0) i = Pix(succ((<T>AVLNode*)i));
+}
+
+inline void <T>AVLSet::prev(Pix& i)
+{
+ if (i != 0) i = Pix(pred((<T>AVLNode*)i));
+}
+
+inline <T>& <T>AVLSet::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T>AVLNode*)i)->item;
+}
+
+inline void <T>AVLSet::clear()
+{
+ _kill(root);
+ count = 0;
+ root = 0;
+}
+
+inline int <T>AVLSet::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+
+
+#endif
+#endif