/*ident "@(#)List.h 1.1.2.7" */ /****************************************************************************** * * C++ Standard Components, Release 3.0. * * Copyright (c) 1991, 1992 AT&T and Unix System Laboratories, Inc. * Copyright (c) 1988, 1989, 1990 AT&T. All Rights Reserved. * * THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and Unix System * Laboratories, Inc. The copyright notice above does not evidence * any actual or intended publication of such source code. * ******************************************************************************/ #ifndef LISTH #define LISTH #include #include class lnk_ATTLC; class Lizt_ATTLC; class ostream; typedef void* voidP; // implements two-way pointers struct lnk_ATTLC { lnk_ATTLC* nxt; lnk_ATTLC* prv; lnk_ATTLC() {} virtual ~lnk_ATTLC(); void init(lnk_ATTLC* p, lnk_ATTLC* s) { prv = p; nxt = s; } virtual lnk_ATTLC* copy(); virtual int operator==(lnk_ATTLC&); }; // base class for all [Const_]Listiter(T)'s class Liztiter_ATTLC { friend class Lizt_ATTLC; Liztiter_ATTLC(Lizt_ATTLC* lp) : theLizt(lp), cache(0), nextIt(0) {} protected: Lizt_ATTLC* theLizt; // associated List Liztiter_ATTLC* nextIt; // next on chain lnk_ATTLC* cache; // a recently retrieved link int cacheNo; // its index or garbage if cache == 0 int index; // current position lnk_ATTLC* pred; // current position lnk_ATTLC* getAt(int); lnk_ATTLC* next(); lnk_ATTLC* prev(); inline lnk_ATTLC* peek_next() const; inline lnk_ATTLC* peek_prev() const; void insert_prev(lnk_ATTLC*); void insert_next(lnk_ATTLC*); lnk_ATTLC* remove_prev(); lnk_ATTLC* remove_next(); void reset0(); public: Liztiter_ATTLC(Lizt_ATTLC&); Liztiter_ATTLC(const Liztiter_ATTLC&); ~Liztiter_ATTLC(); Liztiter_ATTLC& operator=(const Liztiter_ATTLC&); int operator==(const Liztiter_ATTLC& l) const { return theLizt == l.theLizt && index == l.index; } int operator!=(const Liztiter_ATTLC& l) const { return !(*this == l); } int position() const { return index; } void reset(unsigned = 0); void end_reset(unsigned = 0); int at_head() const { return index == 0; } int at_end() const; }; inline lnk_ATTLC* Liztiter_ATTLC::peek_next() const { return at_end() ? (lnk_ATTLC*)0 : pred->nxt; } inline lnk_ATTLC* Liztiter_ATTLC::peek_prev() const { return at_head() ? (lnk_ATTLC*)0 : pred; } // base class for all List's class Lizt_ATTLC { friend class Liztiter_ATTLC; protected: lnk_ATTLC* t; // tail int sz; // number of elements Liztiter_ATTLC* iter_head; Lizt_ATTLC(); Lizt_ATTLC(const Lizt_ATTLC& x) : iter_head(0) { init_all(x); } Lizt_ATTLC(const Lizt_ATTLC&, const Lizt_ATTLC&); ~Lizt_ATTLC(); void delete_all(); // used by dtor and operator=() void init_all(const Lizt_ATTLC&); // used by ctor and operator=() void init_all_to_empty(); // used by make_empty() void add_a_link(lnk_ATTLC*); // used by put() and unget() lnk_ATTLC* tail() const { return t; } lnk_ATTLC* head() const { return t ? t->nxt : 0; } operator void*() { return sz ? this : 0; } operator void*() const { return sz ? (void*)this : 0; } Lizt_ATTLC& unget(lnk_ATTLC*); Lizt_ATTLC& unget(const Lizt_ATTLC&); Lizt_ATTLC& put(lnk_ATTLC*); Lizt_ATTLC& put(const Lizt_ATTLC&); lnk_ATTLC* get(); lnk_ATTLC* unput(); lnk_ATTLC* getAt(int); public: Lizt_ATTLC& operator=(const Lizt_ATTLC&); int operator==(const Lizt_ATTLC&) const; int operator!=(const Lizt_ATTLC& x) const { return !(*this == x); } void make_empty(); int length() const { return sz; } void reset_all_iters(); }; #ifndef __GNUG__ #ifndef voidP_List #define voidP_List List #define voidP_Listiter Listiter #endif #endif #ifdef __GNUG__ class voidP_List : public Lizt_ATTLC { friend void voidP_List_sort_internal(voidP_List&, int (*)(const voidP &, const voidP &)); voidP_List(const voidP_List& a0, const voidP_List& a1) : Lizt_ATTLC((Lizt_ATTLC&)a0, (Lizt_ATTLC&)a1) {} voidP_List(const voidP_List&, const voidP&); protected: void** getAt(int); public: voidP_List(); voidP_List(const voidP_List&); voidP_List(const voidP&); voidP_List(const voidP&, const voidP&); voidP_List(const voidP&, const voidP&, const voidP&); voidP_List(const voidP&, const voidP&, const voidP&, const voidP&); ~voidP_List() {} operator void*() { return Lizt_ATTLC::operator void*(); } operator void*() const { return Lizt_ATTLC::operator void*(); } int operator==(const voidP_List& l) const { return (Lizt_ATTLC&)*this == (Lizt_ATTLC&)l; } int operator!=(const voidP_List& l) const { return (Lizt_ATTLC&)*this != (Lizt_ATTLC&)l; } voidP_List operator+(const voidP_List& ll) { return voidP_List(*this, ll); } voidP_List operator+(const voidP_List& ll) const { return voidP_List(*this, ll); } voidP_List operator+(const voidP& _t) { return voidP_List(*this, _t); } voidP_List operator+(const voidP& _t) const { return voidP_List(*this, _t); } voidP_List& operator=(const voidP_List& a) { return (voidP_List&)(*(Lizt_ATTLC*)this = *(Lizt_ATTLC*)&a); } voidP_List& put(const voidP& x); voidP_List& put(const voidP_List& ll) { return (voidP_List&) Lizt_ATTLC::put((Lizt_ATTLC&) ll); } void* unput(); int unput(voidP&); void* get(); int get(voidP&); voidP_List& unget(const voidP& x); voidP_List& unget(const voidP_List& ll) { return (voidP_List&)Lizt_ATTLC::unget((Lizt_ATTLC&) ll); } void** head() const; void** tail() const; voidP& operator[](int i) { return ((*this).operator[]((unsigned) i)); } const voidP& operator[](int i) const { return ((*this).operator[]((unsigned) i)); } voidP& operator[](unsigned); const voidP& operator[](unsigned) const; void sort(int (*)(const voidP&, const voidP&)); ostream& print(ostream&) const; }; class voidP_Const_listiter : public Liztiter_ATTLC { protected: void** getAt(int i); public: voidP_Const_listiter(const voidP_List&); voidP_Const_listiter(const voidP_Const_listiter&); ~voidP_Const_listiter() {} voidP_Const_listiter& operator=(const voidP_Const_listiter& l) { return (voidP_Const_listiter&) ((Liztiter_ATTLC&)*this = (const Liztiter_ATTLC&)l); } int operator==(const voidP_Const_listiter& l) const { return (const Liztiter_ATTLC&)*this == (const Liztiter_ATTLC&)l; } int operator!=(const voidP_Const_listiter& l) const { return (const Liztiter_ATTLC&)*this != (const Liztiter_ATTLC&)l; } int find_next(const voidP&); int find_prev(const voidP&); int next(voidP& t); int next(voidP*& t); void** next(); int prev(voidP& t); int prev(voidP*& t); void** prev(); int step_next() { return Liztiter_ATTLC::next() != 0; } int step_prev() { return Liztiter_ATTLC::prev() != 0; } int peek_next(voidP&) const; int peek_next(voidP*&) const; void** peek_next() const; int peek_prev(voidP&) const; int peek_prev(voidP*&) const; void** peek_prev() const; const voidP_List* the_list() { return (const voidP_List*)theLizt; } }; class voidP_Listiter : public voidP_Const_listiter { public: voidP_Listiter(voidP_List&); voidP_Listiter(const voidP_Listiter&); ~voidP_Listiter() {} voidP_Listiter& operator=(const voidP_Listiter& l) { return (voidP_Listiter&) ((Liztiter_ATTLC&)*this = (Liztiter_ATTLC&)l); } int operator==(const voidP_Listiter& l) const { return (Liztiter_ATTLC&)*this == (Liztiter_ATTLC&)l; } int operator!=(const voidP_Listiter& l) const { return (Liztiter_ATTLC&)*this != (Liztiter_ATTLC&)l; } voidP_List* the_list() { return (voidP_List*)theLizt; } // the following operations change the container int remove_prev(); int remove_next(); int remove_prev(voidP&); int remove_next(voidP&); void insert_prev(const voidP& x); void insert_next(const voidP& x); int replace_prev(const voidP&); int replace_next(const voidP&); }; #endif #ifdef __GNUG__ #pragma interface #endif template class List; template class Listiter; template class Const_listiter; template ostream& operator<<(ostream&, const List&); template void voidP_List_sort_internal(List&, int (*)(const T &, const T &)); template class lnnk_ATTLC : public lnk_ATTLC { friend class List; friend class Const_listiter; friend class Listiter; #if defined(__SUNPRO_CC) || defined(__GNUG__) friend void voidP_List_sort_internal(List&, int (*)(const T &, const T &)); #else template friend void voidP_List_sort_internal(List&, int (*)(const Type &, const Type &)); #endif #ifndef __GNUG__ static Pool* pool; #endif T val; lnnk_ATTLC(T& pp) : val(pp) {} #ifdef __GNUG__ ~lnnk_ATTLC() {} lnk_ATTLC* copy() { return new lnnk_ATTLC((T&)val); } int operator==(lnk_ATTLC&x) { return val == ((lnnk_ATTLC*)&x)->val; } #else ~lnnk_ATTLC(); lnk_ATTLC* copy(); int operator==(lnk_ATTLC&); #endif public: void* operator new(size_t); #ifdef __GNUG__ void operator delete(void* l) { pool()->free(l); } static Pool *pool(); #else void operator delete(void* l) { pool->free(l); } static void init_pool() { // should be called by List constructors if (pool == 0) pool = new Pool(sizeof(lnnk_ATTLC)); } #endif static lnk_ATTLC* getnewlnnk_ATTLC(const T&); static void deletelnnk_ATTLC(T&, lnnk_ATTLC*); }; template class List : public Lizt_ATTLC { #if defined(__SUNPRO_CC) || defined(__GNUG__) friend void voidP_List_sort_internal(List&, int (*)(const T &, const T &)); #else template friend void voidP_List_sort_internal(List&, int (*)(const Type &, const Type &)); #endif List(const List& a0, const List& a1) : Lizt_ATTLC((Lizt_ATTLC&)a0, (Lizt_ATTLC&)a1) {} List(const List&, const T&); protected: T* getAt(int); public: List(); List(const List&); List(const T&); List(const T&, const T&); List(const T&, const T&, const T&); List(const T&, const T&, const T&, const T&); ~List() {} operator void*() { return Lizt_ATTLC::operator void*(); } operator void*() const { return Lizt_ATTLC::operator void*(); } int operator==(const List& l) const { return (Lizt_ATTLC&)*this == (Lizt_ATTLC&)l; } int operator!=(const List& l) const { return (Lizt_ATTLC&)*this != (Lizt_ATTLC&)l; } List operator+(const List& ll) { return List(*this, ll); } List operator+(const List& ll) const { return List(*this, ll); } List operator+(const T& _t) { return List(*this, _t); } List operator+(const T& _t) const { return List(*this, _t); } List& operator=(const List& a) { return (List&)(*(Lizt_ATTLC*)this = *(Lizt_ATTLC*)&a); } List& put(const T& x); List& put(const List& ll) { return (List&) Lizt_ATTLC::put((Lizt_ATTLC&) ll); } T unput(); int unput(T&); T get(); int get(T&); List& unget(const T& x); List& unget(const List& ll) { return (List&)Lizt_ATTLC::unget((Lizt_ATTLC&) ll); } T* head() const; T* tail() const; T& operator[](int i) {return ((*this).operator[]((unsigned) i));} const T& operator[](int i) const {return ((*this).operator[]((unsigned) i));} T& operator[](unsigned); const T& operator[](unsigned) const; void sort(int (*)(const T&, const T&)); ostream& print(ostream&) const; }; template class Const_listiter : public Liztiter_ATTLC { protected: T* getAt(int i); public: Const_listiter(const List&); Const_listiter(const Const_listiter&); ~Const_listiter() {} Const_listiter& operator=(const Const_listiter& l) { return (Const_listiter&) ((Liztiter_ATTLC&)*this = (const Liztiter_ATTLC&)l); } int operator==(const Const_listiter& l) const { return (const Liztiter_ATTLC&)*this == (const Liztiter_ATTLC&)l; } int operator!=(const Const_listiter& l) const { return (const Liztiter_ATTLC&)*this != (const Liztiter_ATTLC&)l; } int find_next(const T&); int find_prev(const T&); int next(T& t); int next(T*& t); T* next(); int prev(T& t); int prev(T*& t); T* prev(); int step_next() { return Liztiter_ATTLC::next() != 0; } int step_prev() { return Liztiter_ATTLC::prev() != 0; } int peek_next(T&) const; int peek_next(T*&) const; T* peek_next() const; int peek_prev(T&) const; int peek_prev(T*&) const; T* peek_prev() const; const List* the_list() { return (const List*)theLizt; } }; template class Listiter : public Const_listiter { public: Listiter(List&); Listiter(const Listiter&); ~Listiter() {} Listiter& operator=(const Listiter& l) { return (Listiter&) ((Liztiter_ATTLC&)*this = (Liztiter_ATTLC&)l); } int operator==(const Listiter& l) const { return (Liztiter_ATTLC&)*this == (Liztiter_ATTLC&)l; } int operator!=(const Listiter& l) const { return (Liztiter_ATTLC&)*this != (Liztiter_ATTLC&)l; } List* the_list() { return (List*)theLizt; } // the following operations change the container int remove_prev(); int remove_next(); int remove_prev(T&); int remove_next(T&); void insert_prev(const T& x); void insert_next(const T& x); int replace_prev(const T&); int replace_next(const T&); }; template class List_of_p; template class List_of_piter; template ostream& operator<<(ostream&, const List_of_p&); template class List_of_p : public voidP_List { public: List_of_p() {} List_of_p(const T*); List_of_p(const T*, const T*); List_of_p(const T*, const T*, const T*); List_of_p(const T*, const T*, const T*, const T*); List_of_p(const List_of_p& ll) : voidP_List((const voidP_List&) ll) {} ~List_of_p() {} T*& operator[](int i) {return ((*this).operator[]((unsigned) i));} const T*& operator[](int i) const {return ((*this).operator[]((unsigned) i));} T*& operator[](unsigned); const T*& operator[](unsigned) const; operator void*() { return voidP_List::operator void*(); } operator void*() const { return voidP_List::operator void*(); } int operator==(const List_of_p& ll) const { return (const voidP_List&)*this == (const voidP_List&)ll; } int operator!=(const List_of_p& l) const { return !(*this == l); } List_of_p& operator=(const List_of_p& ll) { return (List_of_p&) ((voidP_List&)*this = (const voidP_List&)ll); } List_of_p operator+(const List_of_p&); List_of_p operator+(const T*); List_of_p& put(const T* _t) { return (List_of_p&) voidP_List::put((voidP)_t); } List_of_p& put(const List_of_p& ll) { return (List_of_p&) voidP_List::put((const voidP_List&)ll); } T* unput() { return (T*)voidP_List::unput(); } int unput(T*& _t) { return voidP_List::unput((voidP&)_t); } T* get() { return (T*)voidP_List::get(); } int get(T*& _t) { return voidP_List::get((voidP&)_t); } List_of_p& unget(const T* x) { return (List_of_p&) voidP_List::unget((voidP)x); } List_of_p& unget(const List_of_p& ll) { return (List_of_p&) voidP_List::unget((const voidP_List&)ll); } T* head() const { voidP* ptr = voidP_List::head(); return (ptr ? (T*)*ptr : 0); } T* tail() const { voidP* ptr = voidP_List::tail(); return (ptr ? (T*)*ptr : 0); } void sort(int (*pf)(const T* &, const T* &)) { voidP_List::sort((int (*)(const voidP &, const voidP &))pf); } ostream& print(ostream&) const; }; template class Const_list_of_piter : public voidP_Listiter { public: Const_list_of_piter(const List_of_p&); Const_list_of_piter(const Const_list_of_piter&); ~Const_list_of_piter() {} int operator==(const Const_list_of_piter& l) const { return (const voidP_Listiter&)*this == ((const voidP_Listiter&)l); } int operator!=(const Const_list_of_piter& l) const { return !(*this == l); } Const_list_of_piter& operator=(const Const_list_of_piter& ll) { return (Const_list_of_piter&)((voidP_Listiter&)*this = (const voidP_Listiter&)ll); } const List_of_p* the_list() { return (const List_of_p*)voidP_Listiter::the_list(); } int find_next(const T*const& t) { return voidP_Listiter::find_next((voidP&)t); } int find_prev(const T*const& t) { return voidP_Listiter::find_prev((voidP&)t); } T* next() { voidP* ptr = voidP_Listiter::next(); return (ptr ? (T*)*ptr : 0); } int next(T* &t) { return voidP_Listiter::next((voidP&)t); } int next(T**& t) { return voidP_Listiter::next((voidP*&)t); } T* prev() { voidP* ptr = voidP_Listiter::prev(); return (ptr ? (T*)*ptr : 0); } int prev(T*& t) { return voidP_Listiter::prev((voidP&)t); } int prev(T**& t) { return voidP_Listiter::prev((voidP*&)t); } T* peek_next() const { voidP* ptr = voidP_Listiter::peek_next(); return (ptr ? (T*)*ptr : 0); } int peek_next(T*& t) const { return voidP_Listiter::peek_next((voidP&)t); } int peek_next(T**& t) const { return voidP_Listiter::peek_next((voidP*&)t); } T* peek_prev() const { voidP* ptr = voidP_Listiter::peek_prev(); return (ptr ? (T*)*ptr : 0); } int peek_prev(T*& t) const { return voidP_Listiter::peek_prev((voidP&)t); } int peek_prev(T**& t) const { return voidP_Listiter::peek_prev((voidP*&)t); } }; template class List_of_piter : public Const_list_of_piter { public: List_of_piter(List_of_p&); List_of_piter(const List_of_piter&); ~List_of_piter(); int operator==(const List_of_piter& l) const { return (const Const_list_of_piter&)*this == ((const Const_list_of_piter&)l); } int operator!=(const List_of_piter& l) const { return !(*this == l); } List_of_piter& operator=(const List_of_piter& ll) { return (List_of_piter&)((voidP_Listiter&)*this = (const voidP_Listiter&)ll); } List_of_p* the_list() { return (List_of_p*)voidP_Listiter::the_list(); } // the following operations change the container int remove_prev() { return voidP_Listiter::remove_prev(); } int remove_prev(T*& x) { return voidP_Listiter::remove_prev((voidP&)x); } int remove_next() { return voidP_Listiter::remove_next(); } int remove_next(T*& x) { return voidP_Listiter::remove_next((voidP&)x); } void insert_prev(T*& x) { voidP_Listiter::insert_prev((voidP&)x); } void insert_next(T*& x) { voidP_Listiter::insert_next((voidP&)x); } int replace_prev(T* x) { return voidP_Listiter::replace_prev((voidP)x); } int replace_next(T* x) { return voidP_Listiter::replace_next((voidP)x); } }; #if (defined(__edg_att_40) || defined(__GNUG__)) && !defined(__IMPLICIT_INCLUDE) #include "List.c" #endif #endif