Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!pikes!mercury.cair.du.edu!diana.cair.du.edu!ttoupin
From: ttoupin@diana.cair.du.edu (Aerin)
Newsgroups: comp.lang.c++
Subject: Re: Common data structures
Keywords: list, data structures, c++
Message-ID: <1991Jun11.200744.1204@mercury.cair.du.edu>
Date: 11 Jun 91 20:07:44 GMT
References: <1991Jun10.200429.26713@lynx.CS.ORST.EDU> <1991Jun11.061402.21934@lth.se>
Sender: news@mercury.cair.du.edu (netnews)
Organization: University of Denver
Lines: 95

In article <1991Jun11.061402.21934@lth.se> dag@control.lth.se (Dag Bruck) writes:
>1.  Member of multiple lists
>
>In most list packages an element can be the member of only one list
>at a time.  For me and my colleagues this is quite unacceptable.  We
>often keep a large group objects in a "master" list and then create
>temporary sub-lists for some particular processing task.
>
>The straigh-forward use of a base class "Link" which all other classes
>are derived from won't work; some sort of indirection is needed.

I have done something similar in the past.  First, we must have

	class Object {
		private:
			unsigned long int _users;
		public:
			Object() { _users=0; }
			Object(const Object &) { _users=0; }
			~Object() { --_users; }

			void operator delete(void *__mem) {
				if(!(((Object *)__mem)->_users))
					::operator delete(__mem);
			}

			unsigned long int operator++() { return _users++; }
			unsigned long int operator--() { return --_users; }
			operator unsigned long int() { return _users; }

			virtual Object *copy(int =0) =0;
			virtual enum ClassType typeOf() const =0;
			virtual void *delta(Object *__ptr) const { return __ptr; }
			virtual void *delta() { return this; }
	} ;

The copy member should, when given a non-zero value, make a legitimate copy
of the Object (i.e.: in a new spot in memory), or, otherwise, increment the
user count and just return a pointer to the object itself.  The delta functions
are used for casting up from a base to a derived class.

To keep list, use a structure

	class ListUser : virtual public Object {
		private:
			Object *_node;
			ListUser *_next;
		public:
			ListUser(Object *__node,ListUser *__next=NULL) {
				_node=__node;_next=__next; }
			ListUser(const ListUser &__list) {
				if(_node=__list._node) _node=__list.node->copy(-1); // (1)
				if(_next) _next=new ListUser(*_next);
			}
			~ListUser() { if(_node) delete _node; if (_next) delete _next; }

				// Put append, insert, search, etc. operations here

	/* 
	 * The typing information should make the ListUser object act like what-
	 * ever it contains...
	 */
			virtual enum ClassType typeOf() const
			{
				if(_node) return _node->typeOf();
				else return ListUserType;
			}
			virtual void *delta() const
			{
				if(_node) return _node;
				else return this;
			}
		} ;

Finally, a List class should have a ListUser which is the list that the List
is representing.  A copy of a master list in this way could be manipulated
as desired, w/o affecting the order of the master; however, modifications of
the copies affect the master as well.  (There is a lot missing here--if you
want the working source code, send me email.)

>Dag Bruck
>--
>Department of Automatic Control		E-mail: dag@control.lth.se
>Lund Institute of Technology
>P. O. Box 118				Phone:	+46 46-104287
>S-221 00 Lund, SWEDEN			Fax:    +46 46-138118
--
Tory S. Toupin                         |
ttoupin@diana.cair.du.edu              |  Existence toward perfection...
Unversity of Denver                    |      Life of mediocrity!
Undergraduate: Math & Computer Sciences|
Denver, CO  80208                      |         - M. E.

-----
Ceci n'est pas une signature.