--- /dev/null
+// 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>Bag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Bag_h 1
+
+#include <Pix.h>
+#include "<T>.defs.h"
+
+class <T>Bag
+{
+protected:
+ int count;
+
+public:
+ virtual ~<T>Bag();
+
+ int length(); // current number of items
+ int empty();
+
+ virtual Pix add(<T&> item) = 0; // add item; return Pix
+
+ virtual void del(<T&> item) = 0; // delete 1 occurrence of item
+ virtual void remove(<T&> item); // delete all occurrences
+ virtual void clear(); // delete all items
+
+ virtual int contains(<T&> item); // is item in Bag?
+ virtual int nof(<T&> item); // how many in Bag?
+
+ virtual Pix first() = 0; // Pix of first item or 0
+ virtual void next(Pix& i) = 0; // advance to next or 0
+
+ virtual <T>& operator () (Pix i) = 0; // access item at i
+
+ virtual Pix seek(<T&> item, Pix from=0); // Pix of next occurrence
+ virtual int owns(Pix i); // is i a valid Pix ?
+
+ void error(const char* msg);
+ virtual int OK() = 0; // rep invariant
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>Bag::~<T>Bag() {}
+
+inline int <T>Bag::length()
+{
+ return count;
+}
+
+inline int <T>Bag::empty()
+{
+ return count == 0;
+}
+
+inline int <T>Bag::contains(<T&> item)
+{
+ return seek(item) != 0;
+}
+
+#endif
+#endif
--- /dev/null
+// 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>CHBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>CHBag_h 1
+
+#include "<T>.Bag.h"
+
+
+#ifndef _<T>CHNode_h
+#define _<T>CHNode_h 1
+
+struct <T>CHNode
+{
+ <T>CHNode* tl;
+ <T> hd;
+ <T>CHNode();
+ <T>CHNode(<T&> h, <T>CHNode* t = 0);
+ ~<T>CHNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>CHNode::<T>CHNode() {}
+
+inline <T>CHNode::<T>CHNode(<T&> h, <T>CHNode* t) :hd(h), tl(t) {}
+
+inline <T>CHNode::~<T>CHNode() {}
+
+#endif
+
+typedef <T>CHNode* <T>CHNodePtr;
+
+#endif
+
+
+class <T>CHBag : public <T>Bag
+{
+protected:
+ <T>CHNode** tab;
+ unsigned int size;
+
+public:
+ <T>CHBag(unsigned int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>CHBag(<T>CHBag& a);
+ ~<T>CHBag();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+ int nof(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item, Pix from = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>CHBag::~<T>CHBag()
+{
+ clear();
+ delete tab;
+}
+
+inline int <T>CHBag::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+inline <T>& <T>CHBag::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T>CHNode*)i)->hd;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>CHSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>CHSet_h 1
+
+#include "<T>.Set.h"
+
+
+#ifndef _<T>CHNode_h
+#define _<T>CHNode_h 1
+
+struct <T>CHNode
+{
+ <T>CHNode* tl;
+ <T> hd;
+ <T>CHNode();
+ <T>CHNode(<T&> h, <T>CHNode* t = 0);
+ ~<T>CHNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>CHNode::<T>CHNode() {}
+
+inline <T>CHNode::<T>CHNode(<T&> h, <T>CHNode* t) : hd(h), tl(t) {}
+
+inline <T>CHNode::~<T>CHNode() {}
+
+#endif
+
+typedef <T>CHNode* <T>CHNodePtr;
+
+#endif
+
+
+class <T>CHSet : public <T>Set
+{
+protected:
+ <T>CHNode** tab;
+ unsigned int size;
+
+public:
+ <T>CHSet(unsigned int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>CHSet(<T>CHSet& a);
+ ~<T>CHSet();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item);
+
+ void operator |= (<T>CHSet& b);
+ void operator -= (<T>CHSet& b);
+ void operator &= (<T>CHSet& b);
+
+ int operator == (<T>CHSet& b);
+ int operator != (<T>CHSet& b);
+ int operator <= (<T>CHSet& b);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>CHSet::~<T>CHSet()
+{
+ clear();
+ delete tab;
+}
+
+inline int <T>CHSet::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+inline <T>& <T>CHSet::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T>CHNode*)i)->hd;
+}
+
+inline int <T>CHSet::operator != (<T>CHSet& b)
+{
+ return ! ((*this) == b);
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>DLDeque_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>DLDeque_h
+
+#include "<T>.DLList.h"
+#include "<T>.Deque.h"
+
+class <T>DLDeque : public <T>Deque
+{
+ <T>DLList p;
+
+public:
+ <T>DLDeque();
+ <T>DLDeque(const <T>DLDeque& d);
+ ~<T>DLDeque();
+
+ void operator = (const <T>DLDeque&);
+
+ void push(<T&> item); // insert at front
+ void enq(<T&> item); // insert at rear
+
+ <T>& front();
+ <T>& rear();
+
+ <T> deq();
+ void del_front();
+ void del_rear();
+
+ void clear();
+ int empty();
+ int full();
+ int length();
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>DLDeque::<T>DLDeque() : p() {}
+inline <T>DLDeque::<T>DLDeque(const <T>DLDeque& d) : p(d.p) {}
+
+inline <T>DLDeque::~<T>DLDeque() {}
+
+inline void <T>DLDeque::push(<T&>item)
+{
+ p.prepend(item);
+}
+
+inline void <T>DLDeque::enq(<T&>item)
+{
+ p.append(item);
+}
+
+inline <T> <T>DLDeque::deq()
+{
+ return p.remove_front();
+}
+
+inline <T>& <T>DLDeque::front()
+{
+ return p.front();
+}
+
+inline <T>& <T>DLDeque::rear()
+{
+ return p.rear();
+}
+
+inline void <T>DLDeque::del_front()
+{
+ p.del_front();
+}
+
+inline void <T>DLDeque::del_rear()
+{
+ p.del_rear();
+}
+
+inline void <T>DLDeque::operator =(const <T>DLDeque& s)
+{
+ p.operator = (s.p);
+}
+
+
+inline int <T>DLDeque::empty()
+{
+ return p.empty();
+}
+
+inline int <T>DLDeque::full()
+{
+ return 0;
+}
+
+inline int <T>DLDeque::length()
+{
+ return p.length();
+}
+
+inline int <T>DLDeque::OK()
+{
+ return p.OK();
+}
+
+inline void <T>DLDeque::clear()
+{
+ p.clear();
+}
+
+#endif
+#endif
--- /dev/null
+// 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>DLList_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>DLList_h 1
+
+#include <Pix.h>
+#include "<T>.defs.h"
+
+#ifndef _<T>DLListNode_h
+#define _<T>DLListNode_h 1
+
+struct <T>DLListNode
+{
+ <T>DLListNode* bk;
+ <T>DLListNode* fd;
+ <T> hd;
+ <T>DLListNode();
+ <T>DLListNode(<T&> h,
+ <T>DLListNode* p = 0,
+ <T>DLListNode* n = 0);
+ ~<T>DLListNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>DLListNode::<T>DLListNode() {}
+
+inline <T>DLListNode::<T>DLListNode(<T&> h, <T>DLListNode* p,
+ <T>DLListNode* n)
+ :hd(h), bk(p), fd(n) {}
+
+inline <T>DLListNode::~<T>DLListNode() {}
+
+#endif
+
+typedef <T>DLListNode* <T>DLListNodePtr;
+
+#endif
+
+class <T>DLList
+{
+ friend class <T>DLListTrav;
+
+ <T>DLListNode* h;
+
+public:
+ <T>DLList();
+ <T>DLList(<T>DLList& a);
+ ~<T>DLList();
+
+ <T>DLList& operator = (<T>DLList& a);
+
+ int empty();
+ int length();
+
+ void clear();
+
+ Pix prepend(<T&> item);
+ Pix append(<T&> item);
+ void join(<T>DLList&);
+
+ <T>& front();
+ <T> remove_front();
+ void del_front();
+
+ <T>& rear();
+ <T> remove_rear();
+ void del_rear();
+
+ <T>& operator () (Pix p);
+ Pix first();
+ Pix last();
+ void next(Pix& p);
+ void prev(Pix& p);
+ int owns(Pix p);
+ Pix ins_after(Pix p, <T&> item);
+ Pix ins_before(Pix p, <T&> item);
+ void del(Pix& p, int dir = 1);
+
+ void error(const char* msg);
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>DLList::~<T>DLList()
+{
+ clear();
+}
+
+inline <T>DLList::<T>DLList()
+{
+ h = 0;
+}
+
+inline int <T>DLList::empty()
+{
+ return h == 0;
+}
+
+
+inline void <T>DLList::next(Pix& p)
+{
+ p = (p == 0 || p == h->bk)? 0 : Pix(((<T>DLListNode*)p)->fd);
+}
+
+inline void <T>DLList::prev(Pix& p)
+{
+ p = (p == 0 || p == h)? 0 : Pix(((<T>DLListNode*)p)->bk);
+}
+
+inline Pix <T>DLList::first()
+{
+ return Pix(h);
+}
+
+inline Pix <T>DLList::last()
+{
+ return (h == 0)? 0 : Pix(h->bk);
+}
+
+inline <T>& <T>DLList::operator () (Pix p)
+{
+ if (p == 0) error("null Pix");
+ return ((<T>DLListNode*)p)->hd;
+}
+
+inline <T>& <T>DLList::front()
+{
+ if (h == 0) error("front: empty list");
+ return h->hd;
+}
+
+inline <T>& <T>DLList::rear()
+{
+ if (h == 0) error("rear: empty list");
+ return h->bk->hd;
+}
+
+
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>Deque_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Deque_h
+
+#include <builtin.h>
+
+#include "<T>.defs.h"
+
+class <T>Deque
+{
+public:
+ <T>Deque();
+ ~<T>Deque();
+
+ virtual void push(<T&> item) = 0; // insert at front
+ virtual void enq(<T&> item) = 0; // insert at rear
+
+ virtual <T>& front() = 0;
+ virtual <T>& rear() = 0;
+
+ virtual <T> deq() = 0;
+ virtual void del_front() = 0;
+ virtual void del_rear() = 0;
+
+ virtual int empty() = 0;
+ virtual int full() = 0;
+ virtual int length() = 0;
+ virtual void clear() = 0;
+
+ virtual int OK() = 0;
+
+ void error(const char*);
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+inline <T>Deque::<T>Deque() {}
+#endif
+
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>FPlex_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>FPlex_h 1
+
+#include "<T>.Plex.h"
+
+class <T>FPlex : public <T>Plex
+{
+public:
+ <T>FPlex(); // set low = 0;
+ // fence = 0;
+ // csize = default
+
+ <T>FPlex(int maxsize); // low = 0;
+ // fence = 0;
+ // csize = maxsize
+
+ <T>FPlex(int lo, // low = lo;
+ int maxsize); // fence=lo
+ // csize = maxsize
+
+ <T>FPlex(int lo, // low = lo
+ int hi, // fence = hi+1
+ const <T&> initval,// fill with initval,
+ int maxsize = 0); // csize = maxsize
+ // or fence - lo if 0
+
+ <T>FPlex(const <T>FPlex&); // X(X&)
+
+ ~<T>FPlex();
+
+ void operator= (const <T>FPlex&);
+
+// virtuals
+
+ <T>& high_element ();
+ <T>& low_element ();
+
+ const <T>& high_element () const;
+ const <T>& low_element () const;
+
+ Pix first() const;
+ Pix last() const;
+ void prev(Pix& ptr) const;
+ void next(Pix& ptr) const;
+ int owns(Pix p) const;
+ <T>& operator () (Pix p);
+ const <T>& operator () (Pix p) const;
+
+ int low() const;
+ int high() const;
+ int valid(int idx) const;
+ void prev(int& idx) const;
+ void next(int& x) const;
+ <T>& operator [] (int index);
+ const <T>& operator [] (int index) const;
+
+ int Pix_to_index(Pix p) const;
+ Pix index_to_Pix(int idx) const;
+
+ int can_add_high() const;
+ int can_add_low() const;
+ int full() const;
+
+ int add_high(const <T&> elem);
+ int del_high ();
+ int add_low (const <T&> elem);
+ int del_low ();
+
+ void fill(const <T&> x);
+ void fill(const <T&> x, int from, int to);
+ void clear();
+ void reverse();
+ void append(const <T>FPlex& a);
+ void prepend(const <T>FPlex& a);
+
+ int OK () const;
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline int <T>FPlex::valid (int idx) const
+{
+ return idx >= lo && idx < fnc;
+}
+
+inline int <T>FPlex::low() const
+{
+ return lo;
+}
+
+inline int <T>FPlex::high() const
+{
+ return fnc - 1;
+}
+
+inline Pix <T>FPlex::first() const
+{
+ return (Pix)(hd-><T>IChunk::first_pointer());
+}
+
+inline void <T>FPlex::prev(Pix& p) const
+{
+ p = Pix(hd-><T>IChunk::pred((<T>*) p));
+}
+
+inline void <T>FPlex::next(Pix& p) const
+{
+ p = Pix(hd-><T>IChunk::succ((<T>*) p));
+}
+
+inline Pix <T>FPlex::last() const
+{
+ return Pix(hd-><T>IChunk::last_pointer());
+}
+
+inline int <T>FPlex::full () const
+{
+ return fnc - lo == csize;
+}
+
+inline void <T>FPlex::prev(int& idx) const
+{
+ --idx;
+}
+
+inline void <T>FPlex::next(int& idx) const
+{
+ ++idx;
+}
+
+inline <T>& <T>FPlex:: operator [] (int idx)
+{
+ if (idx < lo || idx >= fnc) index_error();
+ return *(hd->pointer_to(idx));
+}
+
+inline <T>& <T>FPlex:: operator () (Pix p)
+{
+ return *((<T>*)p);
+}
+
+inline <T>& <T>FPlex::low_element ()
+{
+ if (empty()) index_error();
+ return *(hd->pointer_to(lo));
+}
+
+inline <T>& <T>FPlex::high_element ()
+{
+ if (empty()) index_error();
+ return *(hd->pointer_to(fnc - 1));
+}
+
+inline const <T>& <T>FPlex:: operator [] (int idx) const
+{
+ if (idx < lo || idx >= fnc) index_error();
+ return *(hd->pointer_to(idx));
+}
+
+inline const <T>& <T>FPlex:: operator () (Pix p) const
+{
+ return *((const <T>*)p);
+}
+
+inline const <T>& <T>FPlex::low_element () const
+{
+ if (empty()) index_error();
+ return *(hd->pointer_to(lo));
+}
+
+inline const <T>& <T>FPlex::high_element () const
+{
+ if (empty()) index_error();
+ return *(hd->pointer_to(fnc - 1));
+}
+
+inline int <T>FPlex::can_add_high() const
+{
+ return hd->can_grow_high();
+}
+
+inline int <T>FPlex::can_add_low() const
+{
+ return hd->can_grow_low();
+}
+
+inline int <T>FPlex::add_high(const <T&> elem)
+{
+ if (!can_add_high()) full_error();
+ *((hd-><T>IChunk::grow_high())) = elem;
+ return fnc++;
+}
+
+inline int <T>FPlex::del_high ()
+{
+ if (empty()) empty_error();
+ hd-><T>IChunk::shrink_high();
+ return --fnc - 1;
+}
+
+inline int <T>FPlex::add_low (const <T&> elem)
+{
+ if (!can_add_low()) full_error();
+ *((hd-><T>IChunk::grow_low())) = elem;
+ return --lo;
+}
+
+inline int <T>FPlex::del_low ()
+{
+ if (empty()) empty_error();
+ hd-><T>IChunk::shrink_low();
+ return ++lo;
+}
+
+inline int <T>FPlex::owns (Pix p) const
+{
+ return hd->actual_pointer((<T>*)p);
+}
+
+inline int <T>FPlex::Pix_to_index(Pix p) const
+{
+ if (!hd->actual_pointer((const <T>*)p)) index_error();
+ return hd->index_of((const <T>*)p);
+}
+
+inline Pix <T>FPlex::index_to_Pix(int idx) const
+{
+ if (idx < lo || idx >= fnc) index_error();
+ return Pix(hd->pointer_to(idx));
+}
+
+inline <T>FPlex::~<T>FPlex() {}
+
+#endif
+#endif
--- /dev/null
+// 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>List_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>List_h 1
+
+#ifndef _<T>_typedefs
+#define _<T>_typedefs 1
+typedef void (*<T>Procedure)(<T&>);
+typedef <T> (*<T>Mapper)(<T&>);
+typedef <T> (*<T>Combiner)(<T&>, <T&>);
+typedef int (*<T>Predicate)(<T&>);
+typedef int (*<T>Comparator)(<T&>, <T&>);
+#endif
+
+#include <Pix.h>
+
+struct <T>ListNode
+{
+ <T>ListNode* tl;
+ short ref;
+ <T> hd;
+};
+
+extern <T>ListNode Nil<T>ListNode;
+
+class <T>List
+{
+protected:
+ <T>ListNode* P;
+
+ <T>List(<T>ListNode* p);
+public:
+ <T>List();
+ <T>List(<T&> head);
+ <T>List(<T&> head, <T>List& tl);
+ <T>List(<T>List& a);
+ <T>List(Pix p);
+ ~<T>List();
+
+ <T>List& operator = (<T>List& a);
+
+ int null();
+ int valid();
+ operator const void* ();
+ int operator ! ();
+
+ int length();
+ int list_length();
+
+ <T>& get();
+ <T>& head();
+ <T>& operator [] (int n);
+
+ <T>List nth(int n);
+ <T>List tail();
+ <T>List last();
+
+ <T>List find(<T&> targ);
+ <T>List find(<T>List& targ);
+ int contains(<T&> targ);
+ int contains(<T>List& targ);
+ int position(<T&> targ);
+
+ friend <T>List copy(<T>List& a);
+ friend <T>List concat(<T>List& a, <T>List& b);
+ friend <T>List append(<T>List& a, <T>List& b);
+ friend <T>List map(<T>Mapper f, <T>List& a);
+ friend <T>List merge(<T>List& a, <T>List& b, <T>Comparator f);
+ friend <T>List combine(<T>Combiner f, <T>List& a, <T>List& b);
+ friend <T>List reverse(<T>List& a);
+ friend <T>List select(<T>Predicate f, <T>List& a);
+ friend <T>List remove(<T&> targ, <T>List& a);
+ friend <T>List remove(<T>Predicate f, <T>List& a);
+ friend <T>List subst(<T&> old, <T&> repl, <T>List& a);
+
+ void push(<T&> x);
+ <T> pop();
+
+ void set_tail(<T>List& p);
+ void append(<T>List& p);
+ void prepend(<T>List& p);
+ void del(<T&> targ);
+ void del(<T>Predicate f);
+ void select(<T>Predicate f);
+ void subst(<T&> old, <T&> repl);
+ void reverse();
+ void sort(<T>Comparator f);
+
+ void apply(<T>Procedure f);
+ <T> reduce(<T>Combiner f, <T&> base);
+
+ friend int operator == (<T>List& a, <T>List& b);
+ friend int operator != (<T>List& a, <T>List& b);
+
+ Pix first();
+ void next(Pix& p);
+ Pix seek(<T&> item);
+ <T>& operator () (Pix p);
+ int owns(Pix p);
+
+ void error(const char*);
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline void reference(<T>ListNode* p)
+{
+ if (p->ref >= 0) ++p->ref;
+}
+
+inline void dereference(<T>ListNode* p)
+{
+ while (p->ref > 0 && --p->ref == 0)
+ {
+ <T>ListNode* n = p->tl;
+ delete(p);
+ p = n;
+ }
+}
+
+
+inline <T>ListNode* new<T>ListNode(<T&> h)
+{
+ <T>ListNode* p = new <T>ListNode;
+ p->ref = 1;
+ p->hd = h;
+ return p;
+}
+
+inline <T>ListNode* new<T>ListNode(<T&> h, <T>ListNode* t)
+{
+ <T>ListNode* p = new <T>ListNode;
+ p->ref = 1;
+ p->hd = h;
+ p->tl = t;
+ return p;
+}
+
+
+inline <T>List::~<T>List()
+{
+ dereference(P);
+}
+
+inline <T>List::<T>List()
+{
+ P = &Nil<T>ListNode;
+}
+
+inline <T>List::<T>List(<T>ListNode* p)
+{
+ P = p;
+}
+
+inline <T>List::<T>List(<T&> head)
+{
+ P = new<T>ListNode(head);
+ P->tl = &Nil<T>ListNode;
+}
+
+inline <T>List::<T>List(<T&> head, <T>List& tl)
+{
+ P = new<T>ListNode(head, tl.P);
+ reference(P->tl);
+}
+
+inline <T>List::<T>List(<T>List& a)
+{
+ reference(a.P);
+ P = a.P;
+}
+
+
+inline <T>& <T>List::get()
+{
+ return P->hd;
+}
+
+inline <T>& <T>List::head()
+{
+ return P->hd;
+}
+
+
+inline <T>List <T>List::tail()
+{
+ reference(P->tl);
+ return <T>List(P->tl);
+}
+
+
+
+inline int <T>List::null()
+{
+ return P == &Nil<T>ListNode;
+}
+
+inline int <T>List::valid()
+{
+ return P != &Nil<T>ListNode;
+}
+
+inline <T>List::operator const void* ()
+{
+ return (P == &Nil<T>ListNode)? 0 : this;
+}
+
+inline int <T>List::operator ! ()
+{
+ return (P == &Nil<T>ListNode);
+}
+
+
+inline void <T>List::push(<T&> head)
+{
+ <T>ListNode* oldp = P;
+ P = new<T>ListNode(head, oldp);
+}
+
+
+inline int operator != (<T>List& x, <T>List& y)
+{
+ return !(x == y);
+}
+
+inline Pix <T>List::first()
+{
+ return (P == &Nil<T>ListNode)? 0 : Pix(P);
+}
+
+inline <T>& <T>List::operator () (Pix p)
+{
+ return ((<T>ListNode*)p)->hd;
+}
+
+inline void <T>List::next(Pix& p)
+{
+ if (p != 0)
+ {
+ p = Pix(((<T>ListNode*)p)->tl);
+ if (p == &Nil<T>ListNode) p = 0;
+ }
+}
+
+inline <T>List::<T>List(Pix p)
+{
+ P = (<T>ListNode*)p;
+ reference(P);
+}
+
+#endif
+#endif
--- /dev/null
+// 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><C>Map_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T><C>Map_h 1
+
+#include <Pix.h>
+#include "<T>.defs.h"
+
+class <T><C>Map
+{
+protected:
+ int count;
+ <C> def;
+
+public:
+ <T><C>Map(<C&> dflt);
+ virtual ~<T><C>Map();
+
+ int length(); // current number of items
+ int empty();
+
+ virtual int contains(<T&> key); // is key mapped?
+
+ virtual void clear(); // delete all items
+
+ virtual <C>& operator [] (<T&> key) = 0; // access contents by key
+
+ virtual void del(<T&> key) = 0; // delete entry
+
+ virtual Pix first() = 0; // Pix of first item or 0
+ virtual void next(Pix& i) = 0; // advance to next or 0
+ virtual <T>& key(Pix i) = 0; // access key at i
+ virtual <C>& contents(Pix i) = 0; // access contents at i
+
+ virtual int owns(Pix i); // is i a valid Pix ?
+ virtual Pix seek(<T&> key); // Pix of key
+
+ <C>& dflt(); // access default val
+
+ void error(const char* msg);
+ virtual int OK() = 0; // rep invariant
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T><C>Map::~<T><C>Map() {}
+
+inline int <T><C>Map::length()
+{
+ return count;
+}
+
+inline int <T><C>Map::empty()
+{
+ return count == 0;
+}
+
+inline <C>& <T><C>Map::dflt()
+{
+ return def;
+}
+
+inline <T><C>Map::<T><C>Map(<C&> dflt) :def(dflt)
+{
+ count = 0;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>OSLBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>OSLBag_h 1
+
+#include "<T>.Bag.h"
+#include "<T>.SLList.h"
+
+class <T>OSLBag : public <T>Bag
+{
+protected:
+ <T>SLList p;
+
+public:
+ <T>OSLBag();
+ <T>OSLBag(const <T>OSLBag&);
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+
+ int contains(<T&> item);
+ int nof(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ int owns(Pix i);
+ Pix seek(<T&> item, Pix from = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>OSLBag::<T>OSLBag() : p() { count = 0; }
+
+inline <T>OSLBag::<T>OSLBag(const <T>OSLBag& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>OSLBag::first()
+{
+ return p.first();
+}
+
+inline void <T>OSLBag::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>OSLBag::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>OSLBag::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>OSLBag::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+inline int <T>OSLBag::contains(<T&> item)
+{
+ return seek(item) != 0;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>OSLSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>OSLSet_h 1
+
+#include "<T>.Set.h"
+#include "<T>.SLList.h"
+
+class <T>OSLSet : public <T>Set
+{
+protected:
+ <T>SLList p;
+
+public:
+ <T>OSLSet();
+ <T>OSLSet(const <T>OSLSet&);
+
+ 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);
+
+ void operator |= (<T>OSLSet& b);
+ void operator -= (<T>OSLSet& b);
+ void operator &= (<T>OSLSet& b);
+
+ int operator == (<T>OSLSet& b);
+ int operator != (<T>OSLSet& b);
+ int operator <= (<T>OSLSet& b);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>OSLSet::<T>OSLSet() : p() { count = 0; }
+
+inline <T>OSLSet::<T>OSLSet(const <T>OSLSet& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>OSLSet::first()
+{
+ return p.first();
+}
+
+inline void <T>OSLSet::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>OSLSet::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>OSLSet::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>OSLSet::contains (<T&> item)
+{
+ return seek(item) != 0;
+}
+
+inline int <T>OSLSet::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+inline int <T>OSLSet::operator != (<T>OSLSet& b)
+{
+ return !(*this == b);
+}
+
+#endif
+#endif
--- /dev/null
+#ifndef _<T>OXPBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>OXPBag_h 1
+
+#include "<T>.Bag.h"
+#include "<T>.XPlex.h"
+
+class <T>OXPBag : public <T>Bag
+{
+protected:
+ <T>XPlex p;
+
+public:
+ <T>OXPBag(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>OXPBag(const <T>OXPBag&);
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+ int nof(<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 from = 0);
+
+ int OK();
+};
+
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>OXPBag::<T>OXPBag(int chunksize)
+ : p(chunksize) { count = 0; }
+
+inline <T>OXPBag::<T>OXPBag(const <T>OXPBag& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>OXPBag::first()
+{
+ return p.first();
+}
+
+inline void <T>OXPBag::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>OXPBag::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>OXPBag::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>OXPBag::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+inline int <T>OXPBag::contains(<T&> item)
+{
+ return seek(item) != 0;
+}
+
+#endif
+#endif
--- /dev/null
+// 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>OXPSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>OXPSet_h 1
+
+#include "<T>.Set.h"
+#include "<T>.XPlex.h"
+
+class <T>OXPSet : public <T>Set
+{
+protected:
+ <T>XPlex p;
+
+public:
+ <T>OXPSet(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>OXPSet(const <T>OXPSet&);
+
+ 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);
+
+ void operator |= (<T>OXPSet& b);
+ void operator -= (<T>OXPSet& b);
+ void operator &= (<T>OXPSet& b);
+
+ int operator == (<T>OXPSet& b);
+ int operator != (<T>OXPSet& b);
+ int operator <= (<T>OXPSet& b);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>OXPSet::<T>OXPSet(int chunksize)
+ : p(chunksize) { count = 0; }
+
+inline <T>OXPSet::<T>OXPSet(const <T>OXPSet& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>OXPSet::first()
+{
+ return p.first();
+}
+
+inline void <T>OXPSet::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>OXPSet::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>OXPSet::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>OXPSet::contains (<T&> item)
+{
+ return seek(item) != 0;
+}
+
+inline int <T>OXPSet::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+inline int <T>OXPSet::operator != (<T>OXPSet& b)
+{
+ return !(*this == b);
+}
+
+#endif
+#endif
--- /dev/null
+// This may look like C code, but it is really -*- C++ -*-
+/*
+Copyright (C) 1988 Free Software Foundation
+ written by Dirk Grunwald (grunwald@cs.uiuc.edu)
+ adapted for libg++ 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>PHPQ_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define <T>PHPQ_h 1
+
+#include "<T>.PQ.h"
+
+#ifndef <T>PHPQIndex
+#define <T>PHPQIndex unsigned short
+#endif
+
+struct <T>PHPQNode
+{
+ <T>PHPQIndex sibling;
+ <T>PHPQIndex children;
+ <T> item;
+ char valid;
+};
+
+
+class <T>PHPQ : public <T>PQ
+{
+ <T>PHPQNode* storage; // table -- freelist in storage[0].sibling
+ int root;
+ int size;
+
+ void prealloc(int);
+ int check_sibling_list(int, int);
+
+public:
+
+ <T>PHPQ(int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>PHPQ(<T>PHPQ&);
+ ~<T>PHPQ();
+
+ Pix enq(<T&> item);
+ <T> deq();
+
+ <T>& front();
+ void del_front();
+
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ void del(Pix i);
+ Pix seek(<T&> item);
+
+ int OK(); // rep invariant
+};
+
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>PHPQ::~<T>PHPQ()
+{
+ delete [size] storage;
+}
+
+
+inline <T> <T>PHPQ::deq()
+{
+ if (count == 0) error("deq of empty PQ");
+ <T> x = storage[root].item;
+ del_front();
+ return x;
+}
+
+
+inline <T>& <T>PHPQ::front()
+{
+ if (count == 0) error("front of empty PQ");
+ return storage[root].item;
+}
+
+inline int <T>PHPQ::contains(<T&> item)
+{
+ return seek(item) != 0;
+}
+
+inline <T>& <T>PHPQ::operator() (Pix p)
+{
+ if (p == 0) error("null Pix");
+ return storage[int(p)].item;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>Plex_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Plex_h 1
+
+#include <std.h>
+#include <Pix.h>
+#include "<T>.defs.h"
+
+// Plexes are made out of <T>IChunks
+
+#include <stddef.h>
+
+class <T>IChunk
+{
+//public: // kludge until C++ `protected' policies settled
+protected:
+
+ <T>* data; // data, from client
+
+ int base; // lowest possible index
+ int low; // lowest valid index
+ int fence; // highest valid index + 1
+ int top; // highest possible index + 1
+
+ <T>IChunk* nxt; // circular links
+ <T>IChunk* prv;
+
+public:
+
+// constructors
+
+ <T>IChunk(<T>* d, // ptr to array of elements
+ int base_idx, // initial indices
+ int low_idx,
+ int fence_idx,
+ int top_idx);
+
+ virtual ~<T>IChunk();
+
+// status reports
+
+ int size() const; // number of slots
+
+ virtual int empty() const ;
+ virtual int full() const ;
+
+ int can_grow_high () const ; // there is space to add data
+ int can_grow_low () const;
+
+ int base_index() const; // lowest possible index;
+ int low_index() const; // lowest actual index;
+ virtual int first_index() const; // lowest valid index or fence if none
+ virtual int last_index() const; // highest valid index or low-1 if none
+ int fence_index() const; // highest actual index + 1
+ int top_index() const; // highest possible index + 1
+
+// indexing conversion
+
+ int possible_index(int i) const; // i between base and top
+ int actual_index(int i) const; // i between low and fence
+ virtual int valid_index(int i) const; // i not deleted (mainly for mchunks)
+
+ int possible_pointer(const <T>* p) const; // same for ptr
+ int actual_pointer(const <T>* p) const;
+ virtual int valid_pointer(const <T>* p) const;
+
+ <T>* pointer_to(int i) const ; // pointer to data indexed by i
+ // caution: i is not checked for validity
+ int index_of(const <T>* p) const; // index of data pointed to by p
+ // caution: p is not checked for validity
+
+ virtual int succ(int idx) const; // next valid index or fence if none
+ virtual int pred(int idx) const; // previous index or low - 1 if none
+
+ virtual <T>* first_pointer() const; // pointer to first valid pos or 0
+ virtual <T>* last_pointer() const; // pointer to first valid pos or 0
+ virtual <T>* succ(<T>* p) const; // next pointer or 0
+ virtual <T>* pred(<T>* p) const; // previous pointer or 0
+
+// modification
+
+ virtual <T>* grow_high (); // return spot to add an element
+ virtual <T>* grow_low ();
+
+ virtual void shrink_high (); // logically delete top index
+ virtual void shrink_low ();
+
+ virtual void clear(int lo); // reset to empty ch with base = lo
+ virtual void cleardown(int hi); // reset to empty ch with top = hi
+ void re_index(int lo); // re-index so lo is new low
+
+// chunk traversal
+
+ <T>IChunk* next() const;
+ <T>IChunk* prev() const;
+
+ void link_to_prev(<T>IChunk* prev);
+ void link_to_next(<T>IChunk* next);
+ void unlink();
+
+// state checks
+
+ <T>* invalidate(); // mark self as invalid; return data
+ // for possible deletion
+
+ virtual int OK() const; // representation invariant
+
+ volatile void error(const char*) const;
+ volatile void empty_error() const;
+ volatile void full_error() const;
+ volatile void index_error() const;
+};
+
+// <T>Plex is a partly `abstract' class: few of the virtuals
+// are implemented at the Plex level, only in the subclasses
+
+class <T>Plex
+{
+protected:
+
+ <T>IChunk* hd; // a chunk holding the data
+ int lo; // lowest index
+ int fnc; // highest index + 1
+ int csize; // size of the chunk
+
+ void invalidate(); // mark so OK() is false
+ void del_chunk(<T>IChunk*); // delete a chunk
+
+ <T>IChunk* tl() const; // last chunk;
+ int one_chunk() const; // true if hd == tl()
+
+public:
+
+// constructors, etc.
+
+ <T>Plex(); // no-op
+
+ virtual ~<T>Plex();
+
+
+// Access functions
+
+ virtual <T>& operator [] (int idx) = 0; // access by index;
+ virtual <T>& operator () (Pix p) = 0; // access by Pix;
+
+ virtual <T>& high_element () = 0; // access high element
+ virtual <T>& low_element () = 0; // access low element
+
+// read-only versions for const Plexes
+
+ virtual const <T>& operator [] (int idx) const = 0; // access by index;
+ virtual const <T>& operator () (Pix p) const = 0; // access by Pix;
+
+ virtual const <T>& high_element () const = 0; // access high element
+ virtual const <T>& low_element () const = 0; // access low element
+
+
+// Index functions
+
+ virtual int valid (int idx) const = 0; // idx is an OK index
+
+ virtual int low() const = 0; // lowest index or fence if none
+ virtual int high() const = 0; // highest index or low-1 if none
+
+ int ecnef() const; // low limit index (low-1)
+ int fence() const; // high limit index (high+1)
+
+ virtual void prev(int& idx) const= 0; // set idx to preceding index
+ // caution: pred may be out of bounds
+
+ virtual void next(int& idx) const = 0; // set to next index
+ // caution: succ may be out of bounds
+
+ virtual Pix first() const = 0; // Pix to low element or 0
+ virtual Pix last() const = 0; // Pix to high element or 0
+ virtual void prev(Pix& pix) const = 0; // preceding pix or 0
+ virtual void next(Pix& pix) const = 0; // next pix or 0
+ virtual int owns(Pix p) const = 0; // p is an OK Pix
+
+// index<->Pix
+
+ virtual int Pix_to_index(Pix p) const = 0; // get index via Pix
+ virtual Pix index_to_Pix(int idx) const = 0; // Pix via index
+
+// Growth
+
+ virtual int add_high(const <T&> elem) =0;// add new element at high end
+ // return new high
+
+ virtual int add_low(const <T&> elem) = 0; // add new low element,
+ // return new low
+
+// Shrinkage
+
+ virtual int del_high() = 0; // remove the element at high end
+ // return new high
+ virtual int del_low() = 0; // delete low element, return new lo
+
+ // caution: del_low/high
+ // does not necessarily
+ // immediately call <T>::~<T>
+
+
+// operations on multiple elements
+
+ virtual void fill(const <T&> x); // set all elements = x
+ virtual void fill(const <T&> x, int from, int to); // fill from to to
+ virtual void clear() = 0; // reset to zero-sized Plex
+ virtual int reset_low(int newlow); // change low index,return old
+ virtual void reverse(); // reverse in-place
+ virtual void append(const <T>Plex& a); // concatenate a copy
+ virtual void prepend(const <T>Plex& a); // prepend a copy
+
+// status
+
+ virtual int can_add_high() const = 0;
+ virtual int can_add_low() const = 0;
+
+ int length () const; // number of slots
+
+ int empty () const; // is the plex empty?
+ virtual int full() const = 0; // it it full?
+
+ int chunk_size() const; // report chunk size;
+
+ virtual int OK() const = 0; // representation invariant
+
+ volatile void error(const char* msg) const;
+ volatile void index_error() const;
+ volatile void empty_error() const;
+ volatile void full_error() const;
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+// <T>IChunk ops
+
+inline int <T>IChunk:: size() const
+{
+ return top - base;
+}
+
+
+inline int <T>IChunk:: base_index() const
+{
+ return base;
+}
+
+inline int <T>IChunk:: low_index() const
+{
+ return low;
+}
+
+inline int <T>IChunk:: fence_index() const
+{
+ return fence;
+}
+
+inline int <T>IChunk:: top_index() const
+{
+ return top;
+}
+
+inline <T>* <T>IChunk:: pointer_to(int i) const
+{
+ return &(data[i-base]);
+}
+
+inline int <T>IChunk:: index_of(const <T>* p) const
+{
+ return ((int)p - (int)data) / sizeof(<T>) + base;
+}
+
+inline int <T>IChunk:: possible_index(int i) const
+{
+ return i >= base && i < top;
+}
+
+inline int <T>IChunk:: possible_pointer(const <T>* p) const
+{
+ return p >= data && p < &(data[top-base]);
+}
+
+inline int <T>IChunk:: actual_index(int i) const
+{
+ return i >= low && i < fence;
+}
+
+inline int <T>IChunk:: actual_pointer(const <T>* p) const
+{
+ return p >= data && p < &(data[fence-base]);
+}
+
+inline int <T>IChunk:: can_grow_high () const
+{
+ return fence < top;
+}
+
+inline int <T>IChunk:: can_grow_low () const
+{
+ return base < low;
+}
+
+inline <T>* <T>IChunk:: invalidate()
+{
+ <T>* p = data;
+ data = 0;
+ return p;
+}
+
+
+inline <T>IChunk* <T>IChunk::prev() const
+{
+ return prv;
+}
+
+inline <T>IChunk* <T>IChunk::next() const
+{
+ return nxt;
+}
+
+inline void <T>IChunk::link_to_prev(<T>IChunk* prev)
+{
+ nxt = prev->nxt;
+ prv = prev;
+ nxt->prv = this;
+ prv->nxt = this;
+}
+
+inline void <T>IChunk::link_to_next(<T>IChunk* next)
+{
+ prv = next->prv;
+ nxt = next;
+ nxt->prv = this;
+ prv->nxt = this;
+}
+
+inline void <T>IChunk::unlink()
+{
+ <T>IChunk* n = nxt;
+ <T>IChunk* p = prv;
+ n->prv = p;
+ p->nxt = n;
+ prv = nxt = this;
+}
+
+inline int <T>IChunk:: empty() const
+{
+ return low == fence;
+}
+
+inline int <T>IChunk:: full() const
+{
+ return top - base == fence - low;
+}
+
+inline int <T>IChunk:: first_index() const
+{
+ return (low == fence)? fence : low;
+}
+
+inline int <T>IChunk:: last_index() const
+{
+ return (low == fence)? low - 1 : fence - 1;
+}
+
+inline int <T>IChunk:: succ(int i) const
+{
+ return (i < low) ? low : i + 1;
+}
+
+inline int <T>IChunk:: pred(int i) const
+{
+ return (i > fence) ? (fence - 1) : i - 1;
+}
+
+inline int <T>IChunk:: valid_index(int i) const
+{
+ return i >= low && i < fence;
+}
+
+inline int <T>IChunk:: valid_pointer(const <T>* p) const
+{
+ return p >= &(data[low - base]) && p < &(data[fence - base]);
+}
+
+inline <T>* <T>IChunk:: grow_high ()
+{
+ if (!can_grow_high()) full_error();
+ return &(data[fence++ - base]);
+}
+
+inline <T>* <T>IChunk:: grow_low ()
+{
+ if (!can_grow_low()) full_error();
+ return &(data[--low - base]);
+}
+
+inline void <T>IChunk:: shrink_high ()
+{
+ if (empty()) empty_error();
+ --fence;
+}
+
+inline void <T>IChunk:: shrink_low ()
+{
+ if (empty()) empty_error();
+ ++low;
+}
+
+inline <T>* <T>IChunk::first_pointer() const
+{
+ return (low == fence)? 0 : &(data[low - base]);
+}
+
+inline <T>* <T>IChunk::last_pointer() const
+{
+ return (low == fence)? 0 : &(data[fence - base - 1]);
+}
+
+inline <T>* <T>IChunk::succ(<T>* p) const
+{
+ return ((p+1) < &(data[low - base]) || (p+1) >= &(data[fence - base])) ?
+ 0 : (p+1);
+}
+
+inline <T>* <T>IChunk::pred(<T>* p) const
+{
+ return ((p-1) < &(data[low - base]) || (p-1) >= &(data[fence - base])) ?
+ 0 : (p-1);
+}
+
+
+// generic Plex operations
+
+inline <T>Plex::<T>Plex() {}
+
+inline int <T>Plex::chunk_size() const
+{
+ return csize;
+}
+
+inline int <T>Plex::ecnef () const
+{
+ return lo - 1;
+}
+
+
+inline int <T>Plex::fence () const
+{
+ return fnc;
+}
+
+inline int <T>Plex::length () const
+{
+ return fnc - lo;
+}
+
+inline int <T>Plex::empty () const
+{
+ return fnc == lo;
+}
+
+inline <T>IChunk* <T>Plex::tl() const
+{
+ return hd->prev();
+}
+
+inline int <T>Plex::one_chunk() const
+{
+ return hd == hd->prev();
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>Queue_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Queue_h
+
+#include <builtin.h>
+
+#include "<T>.defs.h"
+
+class <T>Queue
+{
+public:
+ <T>Queue();
+ virtual ~<T>Queue();
+
+ virtual void enq(<T&> item) = 0;
+ virtual <T> deq() = 0;
+ virtual <T>& front() = 0;
+ virtual void del_front() = 0;
+
+ virtual void clear() = 0;
+ virtual int empty() = 0;
+ virtual int full() = 0;
+ virtual int length() = 0;
+
+ void error(const char*);
+
+ virtual int OK() = 0;
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>Queue::<T>Queue() {}
+
+#endif
+#endif
--- /dev/null
+// 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)
+ ranking code from Paul Anderson (paul%lfcs.ed.ac.uk)
+
+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><C>RAVLMap_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T><C>RAVLMap_h 1
+
+#include "<T>.<C>.Map.h"
+
+struct <T><C>RAVLNode
+{
+ <T><C>RAVLNode* lt;
+ <T><C>RAVLNode* rt;
+ <T> item;
+ <C> cont;
+ int rank;
+ char stat;
+ <T><C>RAVLNode(<T&> h, <C&> c,
+ <T><C>RAVLNode* l=0, <T><C>RAVLNode* r=0, int k=1);
+ ~<T><C>RAVLNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T><C>RAVLNode::<T><C>RAVLNode(<T&> h, <C&> c,
+ <T><C>RAVLNode* l, <T><C>RAVLNode* r, int k)
+ :item(h), cont(c), lt(l), rt(r), rank(k), stat(0) {}
+
+inline <T><C>RAVLNode::~<T><C>RAVLNode() {}
+
+#endif
+
+typedef <T><C>RAVLNode* <T><C>RAVLNodePtr;
+
+
+class <T><C>RAVLMap : public <T><C>Map
+{
+protected:
+ <T><C>RAVLNode* root;
+
+ <T><C>RAVLNode* leftmost();
+ <T><C>RAVLNode* rightmost();
+ <T><C>RAVLNode* pred(<T><C>RAVLNode* t);
+ <T><C>RAVLNode* succ(<T><C>RAVLNode* t);
+ void _kill(<T><C>RAVLNode* t);
+ void _add(<T><C>RAVLNode*& t);
+ void _del(<T><C>RAVLNode* p, <T><C>RAVLNode*& t);
+
+public:
+ <T><C>RAVLMap(<C&> dflt);
+ <T><C>RAVLMap(<T><C>RAVLMap& a);
+ ~<T><C>RAVLMap();
+
+ <C>& operator [] (<T&> key);
+
+ void del(<T&> key);
+
+ Pix first();
+ void next(Pix& i);
+ <T>& key(Pix i);
+ <C>& contents(Pix i);
+
+ Pix seek(<T&> key);
+ int contains(<T&> key);
+
+ Pix ranktoPix(int i);
+ int rankof(<T&> key);
+
+ void clear();
+
+ Pix last();
+ void prev(Pix& i);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T><C>RAVLMap::~<T><C>RAVLMap()
+{
+ _kill(root);
+}
+
+inline <T><C>RAVLMap::<T><C>RAVLMap(<C&> dflt) :(dflt)
+{
+ root = 0;
+}
+
+
+inline Pix <T><C>RAVLMap::first()
+{
+ return Pix(leftmost());
+}
+
+inline Pix <T><C>RAVLMap::last()
+{
+ return Pix(rightmost());
+}
+
+inline void <T><C>RAVLMap::next(Pix& i)
+{
+ if (i != 0) i = Pix(succ((<T><C>RAVLNode*)i));
+}
+
+inline void <T><C>RAVLMap::prev(Pix& i)
+{
+ if (i != 0) i = Pix(pred((<T><C>RAVLNode*)i));
+}
+
+inline <T>& <T><C>RAVLMap::key(Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T><C>RAVLNode*)i)->item;
+}
+
+inline <C>& <T><C>RAVLMap::contents(Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T><C>RAVLNode*)i)->cont;
+}
+
+inline void <T><C>RAVLMap::clear()
+{
+ _kill(root);
+ count = 0;
+ root = 0;
+}
+
+inline int <T><C>RAVLMap::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>RPlex_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>RPlex_h 1
+
+#include "<T>.Plex.h"
+
+// minimum number of chunks to index
+
+#ifndef MIN_NCHUNKS
+#define MIN_NCHUNKS 16
+#endif
+
+class <T>RPlex: public <T>Plex
+{
+ int base; // base index of lowest chunk
+ int lch; // index of lowest used chunk
+ int fch; // 1 + index of highest used chunk
+ int maxch; // max chunks in array
+ <T>IChunk** chunks; // array of chunks
+ <T>IChunk* ch; // cached chunk
+
+ void make_initial_chunks(int up = 1);
+
+ void cache(int idx) const;
+ void cache(const <T>* p) const;
+ <T>* dopred(const <T>* p) const;
+ <T>* dosucc(const <T>* p) const;
+
+ void set_cache(const <T>IChunk* t) const; // logically,
+ // not physically const
+
+public:
+ <T>RPlex(); // set low = 0;
+ // fence = 0;
+ // csize = default
+
+ <T>RPlex(int ch_size); // low = 0;
+ // fence = 0;
+ // csize = ch_size
+
+ <T>RPlex(int lo, // low = lo;
+ int ch_size); // fence=lo
+ // csize = ch_size
+
+ <T>RPlex(int lo, // low = lo
+ int hi, // fence = hi+1
+ const <T&> initval,// fill with initval,
+ int ch_size = 0); // csize= ch_size
+ // or fence-lo if 0
+
+ <T>RPlex(const <T>RPlex&);
+
+ ~<T>RPlex();
+
+ void operator= (const <T>RPlex&);
+
+// virtuals
+
+ <T>& high_element ();
+ <T>& low_element ();
+
+ const <T>& high_element () const;
+ const <T>& low_element () const;
+
+ Pix first() const;
+ Pix last() const;
+ void prev(Pix& ptr) const;
+ void next(Pix& ptr) const;
+ int owns(Pix p) const;
+ <T>& operator () (Pix p);
+ const <T>& operator () (Pix p) const;
+
+ int low() const;
+ int high() const;
+ int valid(int idx) const;
+ void prev(int& idx) const;
+ void next(int& x) const;
+ <T>& operator [] (int index);
+ const <T>& operator [] (int index) const;
+
+ int Pix_to_index(Pix p) const;
+ Pix index_to_Pix(int idx) const;
+
+ int can_add_high() const;
+ int can_add_low() const;
+ int full() const;
+
+ int add_high(const <T&> elem);
+ int del_high ();
+ int add_low (const <T&> elem);
+ int del_low ();
+
+ void fill(const <T&> x);
+ void fill(const <T&> x, int from, int to);
+ void clear();
+ void reverse();
+ void append(const <T>RPlex& a);
+ void prepend(const <T>RPlex& a);
+
+ int reset_low(int newlow);
+
+ int OK () const;
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline void <T>RPlex::prev(int& idx) const
+{
+ --idx;
+}
+
+inline void <T>RPlex::next(int& idx) const
+{
+ ++idx;
+}
+
+inline int <T>RPlex::full () const
+{
+ return 0;
+}
+
+inline int <T>RPlex::can_add_high() const
+{
+ return 1;
+}
+
+inline int <T>RPlex::can_add_low() const
+{
+ return 1;
+}
+
+inline int <T>RPlex::valid (int idx) const
+{
+ return idx >= lo && idx < fnc;
+}
+
+inline int <T>RPlex::low() const
+{
+ return lo;
+}
+
+inline int <T>RPlex::high() const
+{
+ return fnc - 1;
+}
+
+inline void <T>RPlex::set_cache(const <T>IChunk* t) const
+{
+ ((<T>RPlex*)(this))->ch = (<T>IChunk*)t;
+}
+
+inline void <T>RPlex::cache(int idx) const
+{
+ if (idx < lo || idx >= fnc) index_error();
+ set_cache(chunks[(idx - base) / csize]);
+}
+
+inline <T>& <T>RPlex::low_element ()
+{
+ cache(lo); return *(ch->pointer_to(lo));
+}
+
+inline <T>& <T>RPlex::high_element ()
+{
+ cache(fnc-1); return *(ch->pointer_to(fnc - 1));
+}
+
+inline const <T>& <T>RPlex::low_element () const
+{
+ cache(lo); return *((const <T>*)(ch->pointer_to(lo)));
+}
+
+inline const <T>& <T>RPlex::high_element () const
+{
+ cache(fnc-1); return *((const <T>*)(ch->pointer_to(fnc - 1)));
+}
+
+inline int <T>RPlex::Pix_to_index(Pix px) const
+{
+ <T>* p = (<T>*)px;
+ if (!ch->actual_pointer(p)) cache(p);
+ return ch->index_of(p);
+}
+
+inline Pix <T>RPlex::index_to_Pix(int idx) const
+{
+ if (!ch->actual_index(idx)) cache(idx);
+ return (Pix)(ch->pointer_to(idx));
+}
+
+inline Pix <T>RPlex::first() const
+{
+ return Pix(hd-><T>IChunk::first_pointer());
+}
+
+inline Pix <T>RPlex::last() const
+{
+ return Pix(tl()-><T>IChunk::last_pointer());
+}
+
+inline void <T>RPlex::prev(Pix& p) const
+{
+ Pix q = Pix(ch-><T>IChunk::pred((<T>*)p));
+ p = (q == 0)? Pix(dopred((<T>*)p)) : q;
+}
+
+inline void <T>RPlex::next(Pix& p) const
+{
+ Pix q = Pix(ch-><T>IChunk::succ((<T>*)p));
+ p = (q == 0)? Pix(dosucc((<T>*)p)) : q;
+}
+
+inline <T>& <T>RPlex:: operator () (Pix p)
+{
+ return *((<T>*)p);
+}
+
+
+inline <T>& <T>RPlex:: operator [] (int idx)
+{
+ cache(idx); return *(ch->pointer_to(idx));
+}
+
+inline const <T>& <T>RPlex:: operator () (Pix p) const
+{
+ return *((const <T>*)p);
+}
+
+inline const <T>& <T>RPlex:: operator [] (int idx) const
+{
+ cache(idx); return *((const <T>*)(ch->pointer_to(idx)));
+}
+
+inline <T>RPlex::~<T>RPlex()
+{
+ delete chunks;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SLBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SLBag_h 1
+
+#include "<T>.Bag.h"
+#include "<T>.SLList.h"
+
+class <T>SLBag : public <T>Bag
+{
+protected:
+ <T>SLList p;
+
+public:
+ <T>SLBag();
+ <T>SLBag(const <T>SLBag&);
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+ int contains(<T&> item);
+ int nof(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ int owns(Pix i);
+ Pix seek(<T&> item, Pix from = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SLBag::<T>SLBag() : p() { count = 0; }
+
+inline <T>SLBag::<T>SLBag(const <T>SLBag& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>SLBag::first()
+{
+ return p.first();
+}
+
+inline void <T>SLBag::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>SLBag::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>SLBag::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>SLBag::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+inline Pix <T>SLBag::add(<T&> item)
+{
+ ++count;
+ return p.append(item);
+}
+
+inline int <T>SLBag::contains(<T&> item)
+{
+ return seek(item) != 0;
+}
+
+#endif
+#endif
--- /dev/null
+// 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>SLList_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SLList_h 1
+
+#include <Pix.h>
+#include "<T>.defs.h"
+
+#ifndef _<T>SLListNode_h
+#define _<T>SLListNode_h 1
+
+struct <T>SLListNode
+{
+ <T>SLListNode* tl;
+ <T> hd;
+ <T>SLListNode();
+ <T>SLListNode(<T&> h, <T>SLListNode* t = 0);
+ ~<T>SLListNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SLListNode::<T>SLListNode() {}
+
+inline <T>SLListNode::<T>SLListNode(<T&> h, <T>SLListNode* t) :hd(h), tl(t) {}
+
+inline <T>SLListNode::~<T>SLListNode() {}
+
+#endif
+
+typedef <T>SLListNode* <T>SLListNodePtr;
+
+#endif
+
+
+class <T>SLList
+{
+protected:
+ <T>SLListNode* last;
+
+public:
+ <T>SLList();
+ <T>SLList(<T>SLList& a);
+ ~<T>SLList();
+
+ <T>SLList& operator = (<T>SLList& a);
+
+ int empty();
+ int length();
+
+ void clear();
+
+ Pix prepend(<T&> item);
+ Pix append(<T&> item);
+
+ void join(<T>SLList&);
+
+ Pix prepend(<T>SLListNode*);
+ Pix append(<T>SLListNode*);
+
+ <T>& operator () (Pix p);
+ Pix first();
+ void next(Pix& p);
+ int owns(Pix p);
+ Pix ins_after(Pix p, <T&> item);
+ void del_after(Pix p);
+
+ <T>& front();
+ <T>& rear();
+ <T> remove_front();
+ int remove_front(<T>& x);
+ void del_front();
+
+ void error(const char* msg);
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SLList::~<T>SLList()
+{
+ clear();
+}
+
+inline <T>SLList::<T>SLList()
+{
+ last = 0;
+}
+
+inline int <T>SLList::empty()
+{
+ return last == 0;
+}
+
+
+inline Pix <T>SLList::first()
+{
+ return (last == 0)? 0 : Pix(last->tl);
+}
+
+inline void <T>SLList::next(Pix& p)
+{
+ p = (p == 0 || p == last)? 0 : Pix(((<T>SLListNode*)(p))->tl);
+}
+
+inline <T>& <T>SLList::operator () (Pix p)
+{
+ if (p == 0) error("null Pix");
+ return ((<T>SLListNode*)(p))->hd;
+}
+
+inline <T>& <T>SLList::front()
+{
+ if (last == 0) error("front: empty list");
+ return last->tl->hd;
+}
+
+inline <T>& <T>SLList::rear()
+{
+ if (last == 0) error("rear: empty list");
+ return last->hd;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SLQueue_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SLQueue_h
+
+#include "<T>.SLList.h"
+#include "<T>.Queue.h"
+
+class <T>SLQueue : public <T>Queue
+{
+ <T>SLList p;
+
+public:
+ <T>SLQueue();
+ <T>SLQueue(const <T>SLQueue& q);
+ ~<T>SLQueue();
+
+ void operator = (const <T>SLQueue&);
+
+ void enq(<T&> item);
+ <T> deq();
+ <T>& front();
+ void del_front();
+
+ void clear();
+ int empty();
+ int full();
+ int length();
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SLQueue::<T>SLQueue() :p() {}
+inline <T>SLQueue::<T>SLQueue(const <T>SLQueue& q) : p(q.p) {}
+
+inline <T>SLQueue::~<T>SLQueue() {}
+
+inline void <T>SLQueue::enq(<T&>item)
+{
+ p.append(item);
+}
+
+inline <T> <T>SLQueue::deq()
+{
+ return p.remove_front();
+}
+
+inline <T>& <T>SLQueue::front()
+{
+ return p.front();
+}
+
+
+inline void <T>SLQueue::del_front()
+{
+ p.del_front();
+}
+
+inline void <T>SLQueue::operator =(const <T>SLQueue& s)
+{
+ p = s.p;
+}
+
+inline int <T>SLQueue::empty()
+{
+ return p.empty();
+}
+
+inline int <T>SLQueue::full()
+{
+ return 0;
+}
+
+inline int <T>SLQueue::length()
+{
+ return p.length();
+}
+
+inline int <T>SLQueue::OK()
+{
+ return p.OK();
+}
+
+inline void <T>SLQueue::clear()
+{
+ p.clear();
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SLSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SLSet_h 1
+
+#include "<T>.Set.h"
+#include "<T>.SLList.h"
+
+class <T>SLSet : public <T>Set
+{
+protected:
+ <T>SLList p;
+
+public:
+ <T>SLSet();
+ <T>SLSet(const <T>SLSet&);
+
+ 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);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SLSet::<T>SLSet() : p() { count = 0; }
+
+inline <T>SLSet::<T>SLSet(const <T>SLSet& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>SLSet::first()
+{
+ return p.first();
+}
+
+inline void <T>SLSet::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>SLSet::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>SLSet::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>SLSet::contains (<T&> item)
+{
+ return seek(item) != 0;
+}
+
+inline int <T>SLSet::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SLStack_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SLStack_h 1
+
+#include "<T>.SLList.h"
+#include "<T>.Stack.h"
+
+class <T>SLStack : public <T>Stack
+{
+ <T>SLList p;
+
+public:
+ <T>SLStack();
+ <T>SLStack(const <T>SLStack& s);
+ ~<T>SLStack();
+
+ void operator = (const <T>SLStack&);
+
+ void push(<T&> item);
+ <T> pop();
+ <T>& top();
+ void del_top();
+
+ int empty();
+ int full();
+ int length();
+
+ void clear();
+
+ int OK();
+
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SLStack::<T>SLStack() :p() {}
+inline <T>SLStack::<T>SLStack(const <T>SLStack& a) : p(a.p) {}
+inline <T>SLStack::~<T>SLStack() {}
+
+inline void <T>SLStack::push(<T&> item)
+{
+ p.prepend(item);
+}
+
+inline <T> <T>SLStack::pop()
+{
+ return p.remove_front();
+}
+
+inline <T>& <T>SLStack::top()
+{
+ return p.front();
+}
+
+inline void <T>SLStack::del_top()
+{
+ p.del_front();
+}
+
+inline void <T>SLStack::operator =(const <T>SLStack& s)
+{
+ p = s.p;
+}
+
+inline int <T>SLStack::empty()
+{
+ return p.empty();
+}
+
+inline int <T>SLStack::full()
+{
+ return 0;
+}
+
+inline int <T>SLStack::length()
+{
+ return p.length();
+}
+
+inline int <T>SLStack::OK()
+{
+ return p.OK();
+}
+
+inline void <T>SLStack::clear()
+{
+ p.clear();
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>Set_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Set_h 1
+
+#include <Pix.h>
+#include "<T>.defs.h"
+
+class <T>Set
+{
+protected:
+
+ int count;
+
+public:
+ virtual ~<T>Set();
+
+ int length(); // current number of items
+ int empty();
+
+ virtual Pix add(<T&> item) = 0; // add item; return Pix
+ virtual void del(<T&> item) = 0; // delete item
+ virtual int contains(<T&> item); // is item in set?
+
+ virtual void clear(); // delete all items
+
+ virtual Pix first() = 0; // Pix of first item or 0
+ virtual void next(Pix& i) = 0; // advance to next or 0
+ virtual <T>& operator () (Pix i) = 0; // access item at i
+
+ virtual int owns(Pix i); // is i a valid Pix ?
+ virtual Pix seek(<T&> item); // Pix of item
+
+ void operator |= (<T>Set& b); // add all items in b
+ void operator -= (<T>Set& b); // delete items also in b
+ void operator &= (<T>Set& b); // delete items not in b
+
+ int operator == (<T>Set& b);
+ int operator != (<T>Set& b);
+ int operator <= (<T>Set& b);
+
+ void error(const char* msg);
+ virtual int OK() = 0; // rep invariant
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>Set::~<T>Set() {}
+
+inline int <T>Set::length()
+{
+ return count;
+}
+
+inline int <T>Set::empty()
+{
+ return count == 0;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SplayBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SplayBag_h 1
+
+#include "<T>.Bag.h"
+
+#ifndef _<T>SplayNode
+#define _<T>SplayNode 1
+
+struct <T>SplayNode
+{
+ <T>SplayNode* lt;
+ <T>SplayNode* rt;
+ <T>SplayNode* par;
+ <T> item;
+ <T>SplayNode(<T&> h, <T>SplayNode* l=0, <T>SplayNode* r=0);
+ ~<T>SplayNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SplayNode::<T>SplayNode(<T&> h, <T>SplayNode* l, <T>SplayNode* r)
+:item(h), lt(l), rt(r), par(0) {}
+
+inline <T>SplayNode::~<T>SplayNode() {}
+
+#endif
+
+typedef <T>SplayNode* <T>SplayNodePtr;
+
+#endif
+
+class <T>SplayBag : public <T>Bag
+{
+protected:
+ <T>SplayNode* root;
+
+ <T>SplayNode* leftmost();
+ <T>SplayNode* rightmost();
+ <T>SplayNode* pred(<T>SplayNode* t);
+ <T>SplayNode* succ(<T>SplayNode* t);
+ void _kill(<T>SplayNode* t);
+ <T>SplayNode* _copy(<T>SplayNode* t);
+ void _del(<T>SplayNode* t);
+
+public:
+ <T>SplayBag();
+ <T>SplayBag(<T>SplayBag& a);
+ ~<T>SplayBag();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+ int nof(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item, Pix from = 0);
+
+ Pix last();
+ void prev(Pix& i);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SplayBag::~<T>SplayBag()
+{
+ _kill(root);
+}
+
+inline <T>SplayBag::<T>SplayBag()
+{
+ root = 0;
+ count = 0;
+}
+
+inline <T>SplayBag::<T>SplayBag(<T>SplayBag& b)
+{
+ count = b.count;
+ root = _copy(b.root);
+}
+
+inline Pix <T>SplayBag::first()
+{
+ return Pix(leftmost());
+}
+
+inline Pix <T>SplayBag::last()
+{
+ return Pix(rightmost());
+}
+
+inline void <T>SplayBag::next(Pix& i)
+{
+ if (i != 0) i = Pix(succ((<T>SplayNode*)i));
+}
+
+inline void <T>SplayBag::prev(Pix& i)
+{
+ if (i != 0) i = Pix(pred((<T>SplayNode*)i));
+}
+
+inline <T>& <T>SplayBag::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T>SplayNode*)i)->item;
+}
+
+inline void <T>SplayBag::clear()
+{
+ _kill(root);
+ count = 0;
+ root = 0;
+}
+
+inline int <T>SplayBag::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+inline void <T>SplayBag::del(<T&> key)
+{
+ _del((<T>SplayNode*)(seek(key)));
+}
+
+#endif
+#endif
--- /dev/null
+// 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><C>SplayMap_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T><C>SplayMap_h 1
+
+#include "<T>.<C>.Map.h"
+
+#ifndef _<T><C>SplayNode
+#define _<T><C>SplayNode 1
+
+struct <T><C>SplayNode
+{
+ <T><C>SplayNode* lt;
+ <T><C>SplayNode* rt;
+ <T><C>SplayNode* par;
+ <T> item;
+ <C> cont;
+ <T><C>SplayNode(<T&> h, <C&> c,
+ <T><C>SplayNode* l=0,
+ <T><C>SplayNode* r=0);
+ ~<T><C>SplayNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T><C>SplayNode::<T><C>SplayNode(<T&> h, <C&> c,
+ <T><C>SplayNode* l,
+ <T><C>SplayNode* r)
+ :item(h), cont(c), lt(l), rt(r), par(0) {}
+
+inline <T><C>SplayNode::~<T><C>SplayNode() {}
+
+#endif
+
+typedef <T><C>SplayNode* <T><C>SplayNodePtr;
+
+#endif
+
+class <T><C>SplayMap : public <T><C>Map
+{
+protected:
+ <T><C>SplayNode* root;
+
+ <T><C>SplayNode* leftmost();
+ <T><C>SplayNode* rightmost();
+ <T><C>SplayNode* pred(<T><C>SplayNode* t);
+ <T><C>SplayNode* succ(<T><C>SplayNode* t);
+ void _kill(<T><C>SplayNode* t);
+ <T><C>SplayNode* _copy(<T><C>SplayNode* t);
+
+public:
+ <T><C>SplayMap(<C&> dflt);
+ <T><C>SplayMap(<T><C>SplayMap& a);
+ ~<T><C>SplayMap();
+
+ <C>& operator [] (<T&> key);
+
+ void del(<T&> key);
+
+ Pix first();
+ void next(Pix& i);
+ <T>& key(Pix i);
+ <C>& contents(Pix i);
+
+ Pix seek(<T&> key);
+ int contains(<T&> key);
+
+ void clear();
+
+ Pix last();
+ void prev(Pix& i);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T><C>SplayMap::~<T><C>SplayMap()
+{
+ _kill(root);
+}
+
+inline <T><C>SplayMap::<T><C>SplayMap(<C&> dflt) :(dflt)
+{
+ root = 0;
+}
+
+inline <T><C>SplayMap::<T><C>SplayMap(<T><C>SplayMap& b) :(b.def)
+{
+ count = b.count;
+ root = _copy(b.root);
+}
+
+inline Pix <T><C>SplayMap::first()
+{
+ return Pix(leftmost());
+}
+
+inline Pix <T><C>SplayMap::last()
+{
+ return Pix(rightmost());
+}
+
+inline void <T><C>SplayMap::next(Pix& i)
+{
+ if (i != 0) i = Pix(succ((<T><C>SplayNode*)i));
+}
+
+inline void <T><C>SplayMap::prev(Pix& i)
+{
+ if (i != 0) i = Pix(pred((<T><C>SplayNode*)i));
+}
+
+inline <T>& <T><C>SplayMap::key (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T><C>SplayNode*)i)->item;
+}
+
+inline <C>& <T><C>SplayMap::contents (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T><C>SplayNode*)i)->cont;
+}
+
+inline void <T><C>SplayMap::clear()
+{
+ _kill(root);
+ count = 0;
+ root = 0;
+}
+
+inline int <T><C>SplayMap::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SplayPQ_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SplayPQ_h 1
+
+#include "<T>.PQ.h"
+
+#ifndef _<T>SplayNode
+#define _<T>SplayNode 1
+
+struct <T>SplayNode
+{
+ <T>SplayNode* lt;
+ <T>SplayNode* rt;
+ <T>SplayNode* par;
+ <T> item;
+ <T>SplayNode(<T&> h, <T>SplayNode* l=0, <T>SplayNode* r=0);
+ ~<T>SplayNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SplayNode::<T>SplayNode(<T&> h, <T>SplayNode* l, <T>SplayNode* r)
+:item(h), lt(l), rt(r), par(0) {}
+
+inline <T>SplayNode::~<T>SplayNode() {}
+
+#endif
+
+typedef <T>SplayNode* <T>SplayNodePtr;
+
+#endif
+
+class <T>SplayPQ : public <T>PQ
+{
+protected:
+ <T>SplayNode* root;
+
+ <T>SplayNode* leftmost();
+ <T>SplayNode* rightmost();
+ <T>SplayNode* pred(<T>SplayNode* t);
+ <T>SplayNode* succ(<T>SplayNode* t);
+ void _kill(<T>SplayNode* t);
+ <T>SplayNode* _copy(<T>SplayNode* t);
+
+public:
+ <T>SplayPQ();
+ <T>SplayPQ(<T>SplayPQ& a);
+ ~<T>SplayPQ();
+
+ Pix enq(<T&> item);
+ <T> deq();
+
+ <T>& front();
+ void del_front();
+
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ Pix last();
+ void next(Pix& i);
+ void prev(Pix& i);
+ <T>& operator () (Pix i);
+ void del(Pix i);
+ Pix seek(<T&> item);
+
+ int OK(); // rep invariant
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SplayPQ::~<T>SplayPQ()
+{
+ _kill(root);
+}
+
+inline <T>SplayPQ::<T>SplayPQ()
+{
+ root = 0;
+ count = 0;
+}
+
+inline <T>SplayPQ::<T>SplayPQ(<T>SplayPQ& b)
+{
+ count = b.count;
+ root = _copy(b.root);
+}
+
+inline Pix <T>SplayPQ::first()
+{
+ return Pix(leftmost());
+}
+
+inline Pix <T>SplayPQ::last()
+{
+ return Pix(rightmost());
+}
+
+inline void <T>SplayPQ::next(Pix& i)
+{
+ if (i != 0) i = Pix(succ((<T>SplayNode*)i));
+}
+
+inline void <T>SplayPQ::prev(Pix& i)
+{
+ if (i != 0) i = Pix(pred((<T>SplayNode*)i));
+}
+
+inline <T>& <T>SplayPQ::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T>SplayNode*)i)->item;
+}
+
+inline void <T>SplayPQ::clear()
+{
+ _kill(root);
+ count = 0;
+ root = 0;
+}
+
+inline int <T>SplayPQ::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>SplaySet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>SplaySet_h 1
+
+#include "<T>.Set.h"
+
+#ifndef _<T>SplayNode
+#define _<T>SplayNode 1
+
+struct <T>SplayNode
+{
+ <T>SplayNode* lt;
+ <T>SplayNode* rt;
+ <T>SplayNode* par;
+ <T> item;
+ <T>SplayNode(<T&> h, <T>SplayNode* l=0, <T>SplayNode* r=0);
+ ~<T>SplayNode();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SplayNode::<T>SplayNode(<T&> h, <T>SplayNode* l, <T>SplayNode* r)
+:item(h), lt(l), rt(r), par(0) {}
+
+inline <T>SplayNode::~<T>SplayNode() {}
+
+#endif
+
+typedef <T>SplayNode* <T>SplayNodePtr;
+
+#endif
+
+class <T>SplaySet : public <T>Set
+{
+protected:
+ <T>SplayNode* root;
+
+ <T>SplayNode* leftmost();
+ <T>SplayNode* rightmost();
+ <T>SplayNode* pred(<T>SplayNode* t);
+ <T>SplayNode* succ(<T>SplayNode* t);
+ void _kill(<T>SplayNode* t);
+ <T>SplayNode* _copy(<T>SplayNode* t);
+
+public:
+ <T>SplaySet();
+ <T>SplaySet(<T>SplaySet& a);
+ ~<T>SplaySet();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item);
+
+ Pix last();
+ void prev(Pix& i);
+
+ void operator |= (<T>SplaySet& b);
+ void operator -= (<T>SplaySet& b);
+ void operator &= (<T>SplaySet& b);
+
+ int operator == (<T>SplaySet& b);
+ int operator != (<T>SplaySet& b);
+ int operator <= (<T>SplaySet& b);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>SplaySet::~<T>SplaySet()
+{
+ _kill(root);
+}
+
+inline <T>SplaySet::<T>SplaySet()
+{
+ root = 0;
+ count = 0;
+}
+
+inline <T>SplaySet::<T>SplaySet(<T>SplaySet& b)
+{
+ count = b.count;
+ root = _copy(b.root);
+}
+
+
+inline int <T>SplaySet::operator != (<T>SplaySet& b)
+{
+ return ! (*this == b);
+}
+
+inline Pix <T>SplaySet::first()
+{
+ return Pix(leftmost());
+}
+
+inline Pix <T>SplaySet::last()
+{
+ return Pix(rightmost());
+}
+
+inline void <T>SplaySet::next(Pix& i)
+{
+ if (i != 0) i = Pix(succ((<T>SplayNode*)i));
+}
+
+inline void <T>SplaySet::prev(Pix& i)
+{
+ if (i != 0) i = Pix(pred((<T>SplayNode*)i));
+}
+
+inline <T>& <T>SplaySet::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return ((<T>SplayNode*)i)->item;
+}
+
+inline void <T>SplaySet::clear()
+{
+ _kill(root);
+ count = 0;
+ root = 0;
+}
+
+inline int <T>SplaySet::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>Stack_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Stack_h
+
+#include <builtin.h>
+
+#include "<T>.defs.h"
+
+class <T>Stack
+{
+public:
+ <T>Stack();
+ virtual ~<T>Stack();
+
+ virtual void push(<T&> item) = 0;
+ virtual <T> pop() = 0;
+ virtual <T>& top() = 0;
+ virtual void del_top() = 0;
+
+ virtual int empty() = 0;
+ virtual int full() = 0;
+ virtual int length() = 0;
+
+ virtual void clear() = 0;
+
+ void error(const char*);
+ virtual int OK() = 0;
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+inline <T>Stack::<T>Stack() {}
+#endif
+
+
+#endif
--- /dev/null
+// 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>VHBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>VHBag_h 1
+
+#include "<T>.Bag.h"
+
+
+class <T>VHBag : public <T>Bag
+{
+protected:
+ <T>* tab;
+ char* status;
+ unsigned int size;
+
+public:
+ <T>VHBag(unsigned int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>VHBag(<T>VHBag& a);
+ ~<T>VHBag();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+ int nof(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item, Pix from = 0);
+
+ int capacity();
+ void resize(unsigned int newsize = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>VHBag::~<T>VHBag()
+{
+ delete [size] tab;
+ delete status;
+}
+
+
+inline int <T>VHBag::capacity()
+{
+ return size;
+}
+
+inline int <T>VHBag::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+inline <T>& <T>VHBag::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return *((<T>*)i);
+}
+
+#endif
+#endif
--- /dev/null
+// 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><C>VHMap_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T><C>VHMap_h 1
+
+#include "<T>.<C>.Map.h"
+
+
+class <T><C>VHMap : public <T><C>Map
+{
+protected:
+ <T>* tab;
+ <C>* cont;
+ char* status;
+ unsigned int size;
+
+public:
+ <T><C>VHMap(<C&> dflt,unsigned int sz=DEFAULT_INITIAL_CAPACITY);
+ <T><C>VHMap(<T><C>VHMap& a);
+ ~<T><C>VHMap();
+
+ <C>& operator [] (<T&> key);
+
+ void del(<T&> key);
+
+ Pix first();
+ void next(Pix& i);
+ <T>& key(Pix i);
+ <C>& contents(Pix i);
+
+ Pix seek(<T&> key);
+ int contains(<T&> key);
+
+ void clear();
+ void resize(unsigned int newsize = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T><C>VHMap::~<T><C>VHMap()
+{
+ delete [size] tab;
+ delete [size] cont;
+ delete [size] status;
+}
+
+inline int <T><C>VHMap::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+inline <T>& <T><C>VHMap::key(Pix i)
+{
+ if (i == 0) error("null Pix");
+ return *((<T>*)i);
+}
+
+inline <C>& <T><C>VHMap::contents(Pix i)
+{
+ if (i == 0) error("null Pix");
+ return cont[((unsigned)(i) - (unsigned)(tab)) / sizeof(<T>)];
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>VHSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>VHSet_h 1
+
+#include "<T>.Set.h"
+
+
+
+class <T>VHSet : public <T>Set
+{
+protected:
+ <T>* tab;
+ char* status;
+ unsigned int size;
+
+public:
+ <T>VHSet(unsigned int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>VHSet(<T>VHSet& a);
+ ~<T>VHSet();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item);
+
+ void operator |= (<T>VHSet& b);
+ void operator -= (<T>VHSet& b);
+ void operator &= (<T>VHSet& b);
+
+ int operator == (<T>VHSet& b);
+ int operator != (<T>VHSet& b);
+ int operator <= (<T>VHSet& b);
+
+ int capacity();
+ void resize(unsigned int newsize = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>VHSet::~<T>VHSet()
+{
+ delete [size] tab;
+ delete status;
+}
+
+
+inline int <T>VHSet::capacity()
+{
+ return size;
+}
+
+inline int <T>VHSet::contains(<T&> key)
+{
+ return seek(key) != 0;
+}
+
+inline <T>& <T>VHSet::operator () (Pix i)
+{
+ if (i == 0) error("null Pix");
+ return *((<T>*)i);
+}
+
+inline int <T>VHSet::operator != (<T>VHSet& b)
+{
+ return ! ((*this) == b);
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Doug Schmidt
+
+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>VOHSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>VOHSet_h 1
+
+#include "<T>.Set.h"
+
+
+
+class <T>VOHSet : public <T>Set
+{
+ <T>* tab;
+ char* status;
+ int size;
+ int cnt; // keeps track of VALIDCELLs and DELETEDCELLs
+
+public:
+ <T>VOHSet(int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>VOHSet(<T>VOHSet&);
+ ~<T>VOHSet();
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ Pix seek(<T&> item);
+
+ void operator |= (<T>VOHSet& b);
+ void operator -= (<T>VOHSet& b);
+ void operator &= (<T>VOHSet& b);
+
+ int operator == (<T>VOHSet& b);
+ int operator != (<T>VOHSet& b);
+ int operator <= (<T>VOHSet& b);
+
+ int capacity();
+ void resize(int newsize = 0);
+
+ int OK();
+};
+
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>VOHSet::~<T>VOHSet()
+{
+ delete [size] tab;
+ delete status;
+}
+
+
+inline int <T>VOHSet::contains(int key)
+{
+ return seek(key) != 0;
+}
+
+
+inline <T>& <T>VOHSet::operator () (Pix p)
+{
+ if (p == 0) error("null Pix");
+ return *((<T>*)p);
+}
+
+#endif
+#endif
--- /dev/null
+// 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>VQueue_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>VQueue_h 1
+
+#include "<T>.Queue.h"
+
+class <T>VQueue : public <T>Queue
+{
+protected:
+ int size;
+ int cnt;
+ int inp;
+ int outp;
+ <T>* s;
+
+public:
+
+ <T>VQueue(int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>VQueue(<T>VQueue&);
+ ~<T>VQueue();
+
+ void operator = (<T>VQueue&);
+
+ void enq(<T&> item);
+ <T> deq();
+ <T>& front();
+ void del_front();
+
+ int length();
+ int empty();
+ int full();
+
+ int capacity();
+ void resize(int sz);
+ void clear();
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>VQueue::<T>VQueue(int sz)
+{
+ s = new <T> [size = sz];
+ cnt = inp = outp = 0;
+}
+
+inline <T>VQueue::~<T>VQueue()
+{
+ delete [size] s;
+}
+
+inline void <T>VQueue::clear()
+{
+ inp = outp = 0;
+ cnt = 0;
+}
+
+inline int <T>VQueue::empty()
+{
+ return cnt <= 0;
+}
+
+inline int <T>VQueue::capacity()
+{
+ return size;
+}
+
+inline int <T>VQueue::full()
+{
+ return cnt >= size;
+}
+
+inline int <T>VQueue::length()
+{
+ return cnt;
+}
+
+inline void <T>VQueue::enq(<T&> item)
+{
+ if (cnt >= size) error("enq to full Queue.");
+ ++cnt;
+ s[inp] = item;
+ if (++inp == size) inp = 0;
+}
+
+inline <T> <T>VQueue::deq()
+{
+ if (cnt <= 0) error("deq from empty Queue.");
+ --cnt;
+ int i = outp;
+ if (++outp == size) outp = 0;
+ return s[i];
+}
+
+
+inline void <T>VQueue::del_front()
+{
+ if (cnt <= 0) error("delete from empty Queue.");
+ --cnt;
+ if (++outp == size) outp = 0;
+}
+
+inline <T>& <T>VQueue::front()
+{
+ if (empty()) error("top from empty Queue.");
+ return s[outp];
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>VStack_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>VStack_h 1
+
+#include "<T>.Stack.h"
+
+class <T>VStack : public <T>Stack
+{
+protected:
+ int size;
+ int ptr;
+ <T>* s;
+
+public:
+
+ <T>VStack(int sz = DEFAULT_INITIAL_CAPACITY);
+ <T>VStack(<T>VStack&);
+ ~<T>VStack();
+
+ void operator = (<T>VStack&);
+ void push(<T&> item);
+ <T> pop();
+ <T>& top();
+ void del_top();
+
+ int length();
+ int empty();
+ int full();
+ void clear();
+
+ void resize(int sz);
+ int capacity();
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>VStack::<T>VStack(int sz)
+{
+ s = new <T> [size = sz];
+ ptr = 0;
+}
+
+inline <T>VStack::~<T>VStack()
+{
+ delete [size] s;
+}
+
+inline void <T>VStack::clear()
+{
+ ptr = 0;
+}
+
+inline int <T>VStack::capacity()
+{
+ return size;
+}
+
+inline int <T>VStack::empty()
+{
+ return ptr == 0;
+}
+
+inline int <T>VStack::full()
+{
+ return ptr == size;
+}
+
+inline int <T>VStack::length()
+{
+ return ptr;
+}
+
+inline void <T>VStack::push(<T&> item)
+{
+ if (full()) error("push to full stack.");
+ s[ptr++] = item;
+}
+
+inline <T> <T>VStack::pop()
+{
+ if (empty()) error("pop from empty stack.");
+ return s[--ptr];
+}
+
+
+inline void <T>VStack::del_top()
+{
+ if (empty()) error("del_top from empty stack.");
+ --ptr;
+}
+
+inline <T>& <T>VStack::top()
+{
+ if (empty()) error("top from empty stack.");
+ return s[ptr-1];
+}
+
+#endif
+#endif
--- /dev/null
+// 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>Vec_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>Vec_h 1
+
+#ifndef _<T>_typedefs
+#define _<T>_typedefs 1
+typedef void (*<T>Procedure)(<T&>);
+typedef <T> (*<T>Mapper)(<T&>);
+typedef <T> (*<T>Combiner)(<T&>, <T&>);
+typedef int (*<T>Predicate)(<T&>);
+typedef int (*<T>Comparator)(<T&>, <T&>);
+#endif
+
+
+class <T>Vec
+{
+protected:
+ int len;
+ <T> *s;
+
+ <T>Vec(int l, <T>* d);
+public:
+ <T>Vec ();
+ <T>Vec (int l);
+ <T>Vec (int l, <T&> fill_value);
+ <T>Vec (<T>Vec&);
+ ~<T>Vec ();
+
+ <T>Vec & operator = (<T>Vec & a);
+ <T>Vec at(int from = 0, int n = -1);
+
+ int capacity();
+ void resize(int newlen);
+
+ <T>& operator [] (int n);
+ <T>& elem(int n);
+
+ friend <T>Vec concat(<T>Vec & a, <T>Vec & b);
+ friend <T>Vec map(<T>Mapper f, <T>Vec & a);
+ friend <T>Vec merge(<T>Vec & a, <T>Vec & b, <T>Comparator f);
+ friend <T>Vec combine(<T>Combiner f, <T>Vec & a, <T>Vec & b);
+ friend <T>Vec reverse(<T>Vec & a);
+
+ void reverse();
+ void sort(<T>Comparator f);
+ void fill(<T&> val, int from = 0, int n = -1);
+
+ void apply(<T>Procedure f);
+ <T> reduce(<T>Combiner f, <T&> base);
+ int index(<T&> targ);
+
+ friend int operator == (<T>Vec& a, <T>Vec& b);
+ friend int operator != (<T>Vec& a, <T>Vec& b);
+
+ void error(const char* msg);
+ void range_error();
+};
+
+extern void default_<T>Vec_error_handler(const char*);
+extern one_arg_error_handler_t <T>Vec_error_handler;
+
+extern one_arg_error_handler_t
+ set_<T>Vec_error_handler(one_arg_error_handler_t f);
+
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>Vec::<T>Vec()
+{
+ len = 0; s = 0;
+}
+
+inline <T>Vec::<T>Vec(int l)
+{
+ s = new <T> [len = l];
+}
+
+
+inline <T>Vec::<T>Vec(int l, <T>* d) :len(l), s(d) {}
+
+
+inline <T>Vec::~<T>Vec()
+{
+ delete[len] s;
+}
+
+
+inline <T>& <T>Vec::operator [] (int n)
+{
+ if ((unsigned)n >= len)
+ range_error();
+ return s[n];
+}
+
+inline <T>& <T>Vec::elem(int n)
+{
+ return s[n];
+}
+
+
+inline int <T>Vec::capacity()
+{
+ return len;
+}
+
+
+
+inline int operator != (<T>Vec& a, <T>Vec& b)
+{
+ return !(a == b);
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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>XPBag_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPBag_h 1
+
+#include "<T>.Bag.h"
+#include "<T>.XPlex.h"
+
+class <T>XPBag : public <T>Bag
+{
+protected:
+ <T>XPlex p;
+
+public:
+ <T>XPBag(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>XPBag(const <T>XPBag&);
+
+ Pix add(<T&> item);
+ void del(<T&> item);
+ void remove(<T&>item);
+ int nof(<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 from = 0);
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>XPBag::<T>XPBag(int chunksize)
+ : p(chunksize) { count = 0; }
+
+inline <T>XPBag::<T>XPBag(const <T>XPBag& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>XPBag::first()
+{
+ return p.first();
+}
+
+inline void <T>XPBag::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>XPBag::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>XPBag::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>XPBag::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+inline Pix <T>XPBag::add(<T&> item)
+{
+ ++count;
+ return p.index_to_Pix(p.add_high(item));
+}
+
+inline int <T>XPBag::contains(<T&> item)
+{
+ return seek(item) != 0;
+}
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>XPDeque_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPDeque_h
+
+#include "<T>.XPlex.h"
+#include "<T>.Deque.h"
+
+class <T>XPDeque : public <T>Deque
+{
+ <T>XPlex p;
+
+public:
+ <T>XPDeque(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>XPDeque(const <T>XPDeque& d);
+ ~<T>XPDeque();
+
+ void operator = (const <T>XPDeque&);
+
+ void push(<T&> item); // insert at front
+ void enq(<T&> item); // insert at rear
+
+ <T>& front();
+ <T>& rear();
+
+ <T> deq();
+ void del_front();
+ void del_rear();
+
+ void clear();
+ int empty();
+ int full();
+ int length();
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>XPDeque::<T>XPDeque(int chunksize)
+ : p(chunksize) {}
+inline <T>XPDeque::<T>XPDeque(const <T>XPDeque& d) : p(d.p) {}
+
+inline <T>XPDeque::~<T>XPDeque() {}
+
+inline void <T>XPDeque::push(<T&>item)
+{
+ p.add_low(item);
+}
+
+inline void <T>XPDeque::enq(<T&>item)
+{
+ p.add_high(item);
+}
+
+inline <T> <T>XPDeque::deq()
+{
+ <T> res = p.low_element();
+ p.del_low();
+ return res;
+}
+
+inline <T>& <T>XPDeque::front()
+{
+ return p.low_element();
+}
+
+inline <T>& <T>XPDeque::rear()
+{
+ return p.high_element();
+}
+
+inline void <T>XPDeque::del_front()
+{
+ p.del_low();
+}
+
+inline void <T>XPDeque::del_rear()
+{
+ p.del_high();
+}
+
+inline void <T>XPDeque::operator =(const <T>XPDeque& s)
+{
+ p.operator = (s.p);
+}
+
+
+inline int <T>XPDeque::empty()
+{
+ return p.empty();
+}
+
+inline int <T>XPDeque::full()
+{
+ return p.full();
+}
+
+inline int <T>XPDeque::length()
+{
+ return p.length();
+}
+
+inline int <T>XPDeque::OK()
+{
+ return p.OK();
+}
+
+inline void <T>XPDeque::clear()
+{
+ p.clear();
+}
+
+#endif
+#endif
--- /dev/null
+// 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>XPPQ_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPPQ_h 1
+
+#include "<T>.PQ.h"
+#include "<T>.XPlex.h"
+
+class <T>XPPQ : public <T>PQ
+{
+protected:
+ <T>XPlex p;
+
+public:
+ <T>XPPQ(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>XPPQ(const <T>XPPQ&);
+
+ Pix enq(<T&> item);
+ <T> deq();
+
+ <T>& front();
+ void del_front();
+
+ int contains(<T&> item);
+
+ void clear();
+
+ Pix first();
+ void next(Pix& i);
+ <T>& operator () (Pix i);
+ void del(Pix i);
+ int owns(Pix i);
+ Pix seek(<T&> item);
+
+ int OK(); // rep invariant
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>XPPQ::<T>XPPQ(int chunksize)
+ : p(1, chunksize) { count = 0; }
+
+inline <T>XPPQ::<T>XPPQ(const <T>XPPQ& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>XPPQ::first()
+{
+ return p.first();
+}
+
+inline void <T>XPPQ::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>XPPQ::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline <T>& <T>XPPQ::front ()
+{
+ return p.low_element();
+}
+
+inline <T> <T>XPPQ::deq ()
+{
+ <T> x = p.low_element();
+ del_front();
+ return x;
+}
+
+inline void <T>XPPQ::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>XPPQ::contains (<T&> item)
+{
+ return seek(item) != 0;
+}
+
+inline int <T>XPPQ::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>XPQueue_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPQueue_h
+
+#include "<T>.XPlex.h"
+#include "<T>.Queue.h"
+
+class <T>XPQueue : public <T>Queue
+{
+protected:
+ <T>XPlex p;
+
+public:
+ <T>XPQueue(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>XPQueue(const <T>XPQueue& q);
+ ~<T>XPQueue();
+
+ void operator = (const <T>XPQueue&);
+
+ void enq(<T&> item);
+ <T> deq();
+ <T>& front();
+ void del_front();
+
+ void clear();
+ int empty();
+ int full();
+ int length();
+
+ int OK();
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>XPQueue::<T>XPQueue(int chunksize)
+ : p(chunksize) {}
+inline <T>XPQueue::<T>XPQueue(const <T>XPQueue& q) : p(q.p) {}
+
+inline <T>XPQueue::~<T>XPQueue() {}
+
+inline void <T>XPQueue::enq(<T&>item)
+{
+ p.add_high(item);
+}
+
+inline <T> <T>XPQueue::deq()
+{
+ <T> res = p.low_element();
+ p.del_low();
+ return res;
+}
+
+inline <T>& <T>XPQueue::front()
+{
+ return p.low_element();
+}
+
+
+inline void <T>XPQueue::del_front()
+{
+ p.del_low();
+}
+
+inline void <T>XPQueue::operator =(const <T>XPQueue& s)
+{
+ p.operator = (s.p);
+}
+
+inline int <T>XPQueue::empty()
+{
+ return p.empty();
+}
+
+inline int <T>XPQueue::full()
+{
+ return p.full();
+}
+
+inline int <T>XPQueue::length()
+{
+ return p.length();
+}
+
+inline int <T>XPQueue::OK()
+{
+ return p.OK();
+}
+
+inline void <T>XPQueue::clear()
+{
+ p.clear();
+}
+
+#endif
+#endif
--- /dev/null
+// 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>XPSet_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPSet_h 1
+
+#include "<T>.Set.h"
+#include "<T>.XPlex.h"
+
+class <T>XPSet : public <T>Set
+{
+protected:
+ <T>XPlex p;
+
+public:
+ <T>XPSet(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>XPSet(const <T>XPSet&);
+
+ 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);
+
+ int OK();
+};
+
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>XPSet::<T>XPSet(int chunksize)
+ : p(chunksize) { count = 0; }
+
+inline <T>XPSet::<T>XPSet(const <T>XPSet& s) : p(s.p) { count = s.count; }
+
+inline Pix <T>XPSet::first()
+{
+ return p.first();
+}
+
+inline void <T>XPSet::next(Pix & idx)
+{
+ p.next(idx);
+}
+
+inline <T>& <T>XPSet::operator ()(Pix idx)
+{
+ return p(idx);
+}
+
+inline void <T>XPSet::clear()
+{
+ count = 0; p.clear();
+}
+
+inline int <T>XPSet::contains (<T&> item)
+{
+ return seek(item) != 0;
+}
+
+inline int <T>XPSet::owns (Pix idx)
+{
+ return p.owns(idx);
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>XPStack_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPStack_h
+
+#include "<T>.XPlex.h"
+#include "<T>.Stack.h"
+
+class <T>XPStack : public <T>Stack
+{
+ <T>XPlex p;
+
+public:
+ <T>XPStack(int chunksize = DEFAULT_INITIAL_CAPACITY);
+ <T>XPStack(const <T>XPStack& s);
+ ~<T>XPStack();
+
+ void operator = (const <T>XPStack&);
+
+ void push(<T&> item);
+ <T> pop();
+ <T>& top();
+ void del_top();
+
+ int empty();
+ int full();
+ int length();
+
+ void clear();
+
+ int OK();
+
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline <T>XPStack::<T>XPStack(int chunksize)
+ : p(chunksize) {}
+inline <T>XPStack::<T>XPStack(const <T>XPStack& s) : p(s.p) {}
+
+inline <T>XPStack::~<T>XPStack() {}
+
+inline void <T>XPStack::push(<T&>item)
+{
+ p.add_high(item);
+}
+
+inline <T> <T>XPStack::pop()
+{
+ <T> res = p.high_element();
+ p.del_high();
+ return res;
+}
+
+inline <T>& <T>XPStack::top()
+{
+ return p.high_element();
+}
+
+inline void <T>XPStack::del_top()
+{
+ p.del_high();
+}
+
+inline void <T>XPStack::operator =(const <T>XPStack& s)
+{
+ p.operator = (s.p);
+}
+
+inline int <T>XPStack::empty()
+{
+ return p.empty();
+}
+
+inline int <T>XPStack::full()
+{
+ return p.full();
+}
+
+inline int <T>XPStack::length()
+{
+ return p.length();
+}
+
+inline int <T>XPStack::OK()
+{
+ return p.OK();
+}
+
+inline void <T>XPStack::clear()
+{
+ p.clear();
+}
+
+
+#endif
+#endif
--- /dev/null
+// 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)
+ based on code by Marc Shapiro (shapiro@sor.inria.fr)
+
+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>XPlex_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _<T>XPlex_h 1
+
+#include "<T>.Plex.h"
+
+class <T>XPlex: public <T>Plex
+{
+ <T>IChunk* ch; // cached chunk
+
+ void make_initial_chunks(int up = 1);
+
+ void cache(int idx) const;
+ void cache(const <T>* p) const;
+
+ <T>* dopred(const <T>* p) const;
+ <T>* dosucc(const <T>* p) const;
+
+ void set_cache(const <T>IChunk* t) const; // logically,
+ // not physically const
+public:
+ <T>XPlex(); // set low = 0;
+ // fence = 0;
+ // csize = default
+
+ <T>XPlex(int ch_size); // low = 0;
+ // fence = 0;
+ // csize = ch_size
+
+ <T>XPlex(int lo, // low = lo;
+ int ch_size); // fence=lo
+ // csize = ch_size
+
+ <T>XPlex(int lo, // low = lo
+ int hi, // fence = hi+1
+ const <T&> initval,// fill with initval,
+ int ch_size = 0); // csize= ch_size
+ // or fence-lo if 0
+
+ <T>XPlex(const <T>XPlex&);
+
+ void operator= (const <T>XPlex&);
+
+// virtuals
+
+
+ <T>& high_element ();
+ <T>& low_element ();
+
+ const <T>& high_element () const;
+ const <T>& low_element () const;
+
+ Pix first() const;
+ Pix last() const;
+ void prev(Pix& ptr) const;
+ void next(Pix& ptr) const;
+ int owns(Pix p) const;
+ <T>& operator () (Pix p);
+ const <T>& operator () (Pix p) const;
+
+ int low() const;
+ int high() const;
+ int valid(int idx) const;
+ void prev(int& idx) const;
+ void next(int& x) const;
+ <T>& operator [] (int index);
+ const <T>& operator [] (int index) const;
+
+ int Pix_to_index(Pix p) const;
+ Pix index_to_Pix(int idx) const;
+
+ int can_add_high() const;
+ int can_add_low() const;
+ int full() const;
+
+ int add_high(const <T&> elem);
+ int del_high ();
+ int add_low (const <T&> elem);
+ int del_low ();
+
+ void fill(const <T&> x);
+ void fill(const <T&> x, int from, int to);
+ void clear();
+ void reverse();
+ void append(const <T>XPlex& a);
+ void prepend(const <T>XPlex& a);
+
+ int OK () const;
+
+};
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+inline void <T>XPlex::prev(int& idx) const
+{
+ --idx;
+}
+
+inline void <T>XPlex::next(int& idx) const
+{
+ ++idx;
+}
+
+inline int <T>XPlex::full () const
+{
+ return 0;
+}
+
+inline int <T>XPlex::can_add_high() const
+{
+ return 1;
+}
+
+inline int <T>XPlex::can_add_low() const
+{
+ return 1;
+}
+
+inline int <T>XPlex::valid (int idx) const
+{
+ return idx >= lo && idx < fnc;
+}
+
+inline int <T>XPlex::low() const
+{
+ return lo;
+}
+
+inline int <T>XPlex::high() const
+{
+ return fnc - 1;
+}
+
+inline <T>& <T>XPlex:: operator [] (int idx)
+{
+ if (!ch->actual_index(idx)) cache(idx);
+ return *(ch->pointer_to(idx));
+}
+
+inline const <T>& <T>XPlex:: operator [] (int idx) const
+{
+ if (!ch->actual_index(idx)) cache(idx);
+ return *((const <T>*)(ch->pointer_to(idx)));
+}
+
+inline <T>& <T>XPlex::low_element ()
+{
+ if (empty()) index_error();
+ return *(hd->pointer_to(lo));
+}
+
+inline const <T>& <T>XPlex::low_element () const
+{
+ if (empty()) index_error();
+ return *((const <T>*)(hd->pointer_to(lo)));
+}
+
+inline <T>& <T>XPlex::high_element ()
+{
+ if (empty()) index_error();
+ return *(tl()->pointer_to(fnc - 1));
+}
+
+inline const <T>& <T>XPlex::high_element () const
+{
+ if (empty()) index_error();
+ return *((const <T>*)(tl()->pointer_to(fnc - 1)));
+}
+
+inline int <T>XPlex::Pix_to_index(Pix px) const
+{
+ <T>* p = (<T>*)px;
+ if (!ch->actual_pointer(p)) cache(p);
+ return ch->index_of(p);
+}
+
+inline Pix <T>XPlex::index_to_Pix(int idx) const
+{
+ if (!ch->actual_index(idx)) cache(idx);
+ return (Pix)(ch->pointer_to(idx));
+}
+
+inline Pix <T>XPlex::first() const
+{
+ return Pix(hd-><T>IChunk::first_pointer());
+}
+
+inline Pix <T>XPlex::last() const
+{
+ return Pix(tl()-><T>IChunk::last_pointer());
+}
+
+inline void <T>XPlex::prev(Pix& p) const
+{
+ Pix q = Pix(ch-><T>IChunk::pred((<T>*) p));
+ p = (q == 0)? Pix(dopred((const <T>*) p)) : q;
+}
+
+inline void <T>XPlex::next(Pix& p) const
+{
+ Pix q = Pix(ch-><T>IChunk::succ((<T>*) p));
+ p = (q == 0)? Pix(dosucc((const <T>*)p)) : q;
+}
+
+inline <T>& <T>XPlex:: operator () (Pix p)
+{
+ return *((<T>*)p);
+}
+
+inline const <T>& <T>XPlex:: operator () (Pix p) const
+{
+ return *((const <T>*)p);
+}
+
+inline void <T>XPlex::set_cache(const <T>IChunk* t) const
+{
+ ((<T>XPlex*)(this))->ch = (<T>IChunk*)t;
+}
+
+#endif
+#endif