The list class provides a convenient and tolerably efficient structure to store pointers to objects. It is a template class, and by convention the template argument represents the object type while the list stores pointers to objects. The class is actually called dvlist and a macro definition is used to define list as dvlist. Undefine list if this leads to a name clash.
In order to avoid any reuqirements on the contents of the lists, the lists provides default functions for printing, element-wise comparison and list-wise comparison. These properties may be overrided by installing appropriate functions for format, equality and order.
The list
The most convenient to deal with modalities is to select one
of the standard subclasses of list
The modalities together with a number of properties,
that determine element-wise and list-wise equality
and comparison.
The properties include
These properties are set when creating the claas.
Properties may be changed dynamically, but this is likely
to lead to unpredictable results.
The list
Apart from the standard refinements, any combination
of modalities and properties may be set by the user.
The list
The standard refinements of list are given below.
The list class has a default constructor, to create an empty
list, and a copy constructor, which may be used to initialize
a list with another list.
Reference counting is used to keep track of the number of copies.
Lists initialized with the copy constructor share
their underlying containers.
Use clone to prevent sharing!
The list class provides (virtual) comparison operators,
which may be refined by a derived (list) class.
Also tests are provided, which allow the user to
check whether the list is empty, to ask for the length of the list,
to check whether the list contains and element and to
ask for the number of times an element is contained.
Notice that these tests are based on pointer
comparisons.
Insertion and removal of an element is done by
respectively insert and remove.
As a shorthand the use of operator<<
is allowed. (See examples/hush/list.c.)
The list class provides three kinds of access
methods.
The recommended way to access elements of a list is
by obtaining in iterator as described in iter(4).
Alternatively one may employ a cursor which is maintained
in the list itself.
Notice that the use of a cursor may lead
to problems when the list is shared
between different parts of the program.
Also the traditional head and tail functions
are provided. It is however not recommended to use
these due to the overhead involved in constructing sublists.
A list may be printed by calling the method print
which prints the elements according to a default format
function.
The format function may be redefined by installing
one's own format function.
For advanced users the list class
process the list with some function, or to map the list
into another list by a user-defined function.
Also, the opportunity of generating a list of lists
by applying some function is provided.
Finally, for garbage collection the system-level
function _register
is provided.
Normally, this function need not be invoked by the user,
except when using the apply function to generate
lists of lists.
In the example below a list of (pointers to) integers
is declared.
Also a format function is defined and an iterator
is used to access the elements of list.
hush -- file <hush/list.h>
PROPERTIES
CLASSES
OPERATORS
For T *p, *q; list<T> x, y; int i,j;
Operators provide a concise way to perform operations on
lists. For those who dislike the cryptic flavor of
operators. the more conventional method
are provided also.
for arbitrary T
x << p; insert or put p
x << y; insert list y
x >> p; remove or get p, destructively
iter<T>& it = x; while ( (p = it()) ) cout << p; iter(4)
p = x(); get element at cursor
x() = p; set element at cursor to p;
p = x[i]; find i'th element, and set cursor
p = x[q]; find element equal to p, and set cursor
p = x++; get element at cursor and advance cursor
p = x--; get element at cursor and move corsor back
x[i] = p; replace i'th element by q
x[p] = q; replace p by q first occurrence
x[i] = y; idem, with list
x[p] = y;
y = x(i,j); y become the sublist starting at i with length j
x(i,j) = p; sublist (i,j) is replaced by p
x(i,j) = y; sublist (i,j) is replaced by y
x << i; rotate x i times anti-clockwise
x >> i; rotate x i times clockwise
olist<T> x = y; x is the sorted version of y
Elements
interface element<T> { auxiliary class
operator T*(); to get element
operator=(const T*); to put elemt
operator=(const list<T>&); to replace by (sub)list
};
Sublists
interface sublist<T> { auxiliary class
operator list<T>*; to get (sub)list
operator=(T*); to put elemt
operator=(list<T>&); to replace by (sub)list
};
The list -- with modalities and properties
interface list<T> { <hush/list.h>
<hush/list.idl>
examples/hush/tutorial/util/clist.c
enum { _plain = 0, _ordered, _lifo, _fifo }; modalities
// Constructors and assignment
list();
list( const list<T>& );
list<T>& operator=(const list<T>& ); assignment
// Cloning -- to prevent derived lists from being destroyed
list<T>* clone(); to obtain a copy
_copy( list<T>& x ); to obtain the properties of x
// Destructor
~list(); does not delete the elements
void destroy(); deletes elements but not the list itself
// Insertion and removal -- abbreviations
operator<<( list<T>&, T* ); l << p; -- insertion
operator>>( list<T>&, T*& ); // l >> p; -- destructive removal
// Insertion and removal -- explicit form
void insert(const T* el);
void remove(const T* el = 0);
// Tests
int empty() const;
int length() const;
T* find(const T* el); sets cursor if found, like x[el];
int contains(const T* el) const; tests for object equality
int count(const T* el = 0) const; equals length when el == 0;
// Iterator
operator iter<T>&(); // by assignment
// Cursor
T* current( ); gets element pointed to by cursor
T* first(); resets cursor, like x[0];
T* next(); like x++;
// Alternative access method
T* head() const;
list<T>* tail() const;
// Comparison operators -- see equality and order
int operator==(const list<T>& ); uses lequality
int operator<(const list<T>& ); uses lorder
int operator<=(const list<T>& ); == || <
// Indexing and sublists -- operators
element<T>* operator[](int i); element at i
element<T>* operator[](T*); element at p
element<T>* operator()(); element at cursor
element<T>* operator()(int i); element at i
element<T>* operator[](T* p); element at p
sublist<T>* operator()(int p, int len); for splicing
T* operator++(int); delivers element at cursor and advances
T* operator--(int); delivers element at cursor and goes back
// Printing
typedef ostream& format_type(ostream& os, T* e);
void print(ostream& os);
void format(format_type* fun); to set format
format_type* format(); to get format
// Equality and order -- properties
typedef int compare_type( const T*, const T* );
typedef int lcompare_type( const T*, const T* );
void equality(compare_type* fun); to set equality for elements
compare_type* equality(); to get element-wise equality
void order(compare_type* fun); to set order for elements
compare_type* order(); to get element-wise order
void lequality(lcompare_type* fun); to set equality for lists
lcompare_type* lequality(); to get list-wise equality
void lorder(lcompare_type* fun); to set order for lists
lcompare_type* lorder(); to get list-wise order
// For insertion and extraction
typedef T* element_type(const T*, const dvlist<T>&);
void insertion( element_type* fun); to set insertion property
element_type* insertion( ); to get insertion property
void extraction( element_type* fun); to set extraction property
element_type* extraction( ); to get extraction property
void selection( element_type* fun); to set selection property
element_type* selection( ); to get selection property
// Processing (advanced users only)
typedef int predicate_type(const T*, const dvlist<T>&);
typedef T* element_type(const T*, const dvlist<T>&);
int process( predicate_type* ) const; may have side-effects
list<T>* apply( element_type* ) const;
// Garbage collection
void _register(const T*) const;
void _register(const list<T>*) const;
void _register(const garbage<T>*) const;
};
SUBCLASSES
// Refinements
interface slist<T> : list<T> { a list with value semantics
}
interface set<T> : slist<T> { a list with setwise modality
void put(const T* el);
T* get();
}
interface olist<T> : slist<T> { a list order
void put(const T* el);
T* get();
};
interface oset<T> : olist<T> { an ordered list with setwise modality
}
interface stack<T> : list<T> { a list with fifo modality
void push(const T* el);
T* pop();
}
interface queue<T> : list<T> { a list with lifo modality
void enque(const T* el);
T* deque();
}
DESCRIPTION
EXAMPLES
// The << operator must be defined by the user!
static ostream& operator<<(ostream& os, list<int>& l) {
l.print(os);
return os;
}
// A format function may be defined by the user.
static ostream& e_format(ostream& os, int* p ) { // format function
os << "EL: " << *p << endl;
return os;
}
// The main function
int main(int argc, char** argv) {
list<int> l; // define list of (pointers to) int
int i1 = 1; int i2 = 2; int i3 = 3;
l.insert(&i1); // insert element
l << &i2 << &i3; // alternative way of inserting
l.format(e_format); // define format function
int sum = 0;
iter<int>& it = l; // convert to iter by assignment
int* pn = 0; // declare pointer
while ( pn = it() ) {
sum += *pn;
}
cout << "LIST: " << l << "TOTAL: " << sum << endl;
return 0;
}
Notice that, in line with the hush conventions,
both the list and the iterator have int as
template parameter whereas pointers to int are
respectively stored and delivered.
Notice also that if you wish to employ the << operator
for output then you must define this yourself.
In contrast, you do not need to define a format function,
but you may do so if you find it necessary.
See examples/hush/list.c, examples/hush/container.c,
examples/hush/stack.c, hush/examples/queue.c,
examples/hush/set.c
LIBRARY
SEE ALSO
iter(4)
[.]
Papers
Tutorials
Examples
Manuals
Interfaces
Sources
Packages
Resources
?
Hush Online Technology
hush@cs.vu.nl
09/24/99
