list.hpp File Reference

#include "basic.hpp"
#include "list.ipp"

Include dependency graph for list.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	list< T >
	The list class represents a linked list. More...
class	list_rep< T >
	The list_rep class represents a node in a linked list. More...

Macros
#define	TMPL   template <class T>

Functions
template<class T >
bool	is_nil (list< T > l)
	Check if a list is nil (i.e., an empty list).
template<class T >
bool	is_atom (list< T > l)
	Check if a list is an atom (i.e., a single item).
template<class T >
bool	strong_equal (list< T > l1, list< T > l2)
	Check if two lists are strongly equal (i.e., have the same items in the same order).
	CONCRETE_NULL_TEMPLATE_CODE (list, class, T)
template<class T >
int	N (list< T > l)
	Get the number of items in a list.
template<class T >
list< T >	copy (list< T > l)
	Create a copy of a list.
template<class T >
list< T >	operator* (list< T > l1, T x)
	Create a new list by appending an item to the end of an existing list.
template<class T >
list< T >	operator* (list< T > l1, list< T > l2)
	Create a new list by concatenating two existing lists.
template<class T >
list< T >	head (list< T > l, int n=1)
	Get the first n items of a list.
template<class T >
list< T >	tail (list< T > l, int n=1)
	Get all but the first n items of a list.
template<class T >
T	last_item (list< T > l)
	Return the last item of the list. The input list must not be an empty list.
template<class T >
T &	access_last (list< T > &l)
	Get a reference to the last item in a list.
template<class T >
list< T > &	suppress_last (list< T > &l)
	Remove the last item from a list.
template<class T >
list< T >	reverse (list< T > l)
	Create a new list with the items in reverse order.
template<class T >
list< T >	remove (list< T > l, T what)
	Create a new list with a specific item removed.
template<class T >
bool	contains (list< T > l, T what)
	Check if a list contains a specific item.
template<class T >
tm_ostream &	operator<< (tm_ostream &out, list< T > l)
template<class T >
list< T > &	operator<< (list< T > &l, T item)
template<class T >
list< T > &	operator<< (list< T > &l1, list< T > l2)
template<class T >
list< T > &	operator>> (T item, list< T > &l)
template<class T >
list< T > &	operator<< (T &item, list< T > &l)
template<class T >
bool	operator== (list< T > l1, list< T > l2)
template<class T >
bool	operator!= (list< T > l1, list< T > l2)
template<class T >
bool	operator< (list< T > l1, list< T > l2)
template<class T >
bool	operator<= (list< T > l1, list< T > l2)

Variables
int	list_count

Detailed Description

Copyright

GPLv3

linked lists with reference counting

Author

Joris van der Hoeven

Date

1999

Definition in file list.hpp.

Macro Definition Documentation

TMPL

#define TMPL   template <class T>

Definition at line 136 of file list.hpp.

Function Documentation

is_nil()

template<class T >

bool is_nil

(

list< T >

l

)

Check if a list is nil (i.e., an empty list).

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list to be checked.

Returns

true if the list is nil, false otherwise.

is_atom()

template<class T >

bool is_atom ( list< T > l )

inline

Check if a list is an atom (i.e., a single item).

Parameters

l	The list to be checked.

Returns

true if the list is an atom, false otherwise.

Definition at line 146 of file list.hpp.

                    {
  return (!is_nil (l)) && is_nil (l->next);
}

strong_equal()

template<class T >

bool strong_equal	(	list< T >	l1,
		list< T >	l2 )

Check if two lists are strongly equal (i.e., have the same items in the same order).

Parameters

l1	The first list to be compared.
l2	The second list to be compared.

Returns

true if the lists are strongly equal, false otherwise.

Definition at line 110 of file list.ipp.

                                      {
  return l1.rep == l2.rep;
}

CONCRETE_NULL_TEMPLATE_CODE()

CONCRETE_NULL_TEMPLATE_CODE	(	list	,
		class	,
		T	)

N()

template<class T >

int N

(

list< T >

l

)

Get the number of items in a list.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list whose length is to be calculated.

Returns

int The number of items in the list.

Definition at line 151 of file list.ipp.

              {
  if (is_nil (l)) return 0;
 
  int cnt= 1;
  while (!is_nil (l->next)) {
    cnt= cnt + 1;
    l  = l->next;
  }
  return cnt;
}

copy()

template<class T >

list< T > copy

(

list< T >

l

)

Create a copy of a list.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list to be copied.

Returns

list<T> A copy of the input list.

Definition at line 164 of file list.ipp.

                 {
  if (is_nil (l)) return list<T> ();
  else return list<T> (l->item, copy (l->next));
}

operator*() [1/2]

template<class T >

list< T > operator*	(	list< T >	l1,
		T	x )

Create a new list by appending an item to the end of an existing list.

Template Parameters

T	The type of the data stored in the lists.

Parameters

l1	The list to which the item will be appended.
x	The item to be appended.

Returns

list<T> A new list consisting of the input list with the item appended.

Definition at line 171 of file list.ipp.

                            {
  if (is_nil (l1)) return x;
  else return list<T> (l1->item, l1->next * x);
}

operator*() [2/2]

template<class T >

list< T > operator*	(	list< T >	l1,
		list< T >	l2 )

Create a new list by concatenating two existing lists.

Template Parameters

T	The type of the data stored in the lists.

Parameters

l1	The first list to be concatenated.
l2	The second list to be concatenated.

Returns

list<T> A new list consisting of the items in the input lists in order.

Definition at line 178 of file list.ipp.

                                   {
  if (is_nil (l1)) return copy (l2);
  else return list<T> (l1->item, l1->next * l2);
}

head()

template<class T >

list< T > head	(	list< T >	l,
		int	n = 1 )

Get the first n items of a list.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list whose items are to be retrieved.
n	The number of items to retrieve (default is 1).

Returns

list<T> A new list consisting of the first n items of the input list.

Definition at line 185 of file list.ipp.

                        {
  if (n == 0) return list<T> ();
  ASSERT (!is_nil (l), "list too short to get the head");
  return list<T> (l->item, head (l->next, n - 1));
}

tail()

template<class T >

list< T > tail	(	list< T >	l,
		int	n = 1 )

Get all but the first n items of a list.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list whose items are to be retrieved.
n	The number of items to skip (default is 1).

Returns

list<T> A new list consisting of all but the first n items of the input list.

Definition at line 193 of file list.ipp.

                        {
  for (; n > 0; n--) {
    ASSERT (!is_nil (l), "list too short to get the tail");
    l= l->next;
  }
  return l;
}

last_item()

template<class T >

T last_item

(

list< T >

l

)

Return the last item of the list. The input list must not be an empty list.

Template Parameters

T

Parameters

l

the list

Returns

T

Definition at line 79 of file list.ipp.

                      {
  ASSERT (!is_nil (l), "last_item on nil list");
  while (!is_nil (l->next)) {
    l= l->next;
  }
  return l->item;
}

access_last()

template<class T >

T & access_last

(

list< T > &

l

)

Get a reference to the last item in a list.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list whose last item is to be accessed.

Returns

T& A reference to the last item in the list.

Definition at line 89 of file list.ipp.

                         {
  ASSERT (!is_nil (l), "access_last on nil list");
  if (is_nil (l->next)) return l->item;
  return access_last (l->next);
}

suppress_last()

template<class T >

list< T > & suppress_last

(

list< T > &

l

)

Remove the last item from a list.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list from which the last item is to be removed.

Returns

list<T>& A reference to the modified list.

Definition at line 97 of file list.ipp.

                           {
  ASSERT (!is_nil (l), "empty path");
  if (is_nil (l->next)) l= list<T> ();
  else suppress_last (l->next);
  return l;
}

reverse()

template<class T >

list< T > reverse

(

list< T >

l

)

Create a new list with the items in reverse order.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list to be reversed.

Returns

list<T> A new list with the items in reverse order.

Definition at line 203 of file list.ipp.

                    {
  list<T> r;
  while (!is_nil (l)) {
    r= list<T> (l->item, r);
    l= l->next;
  }
  return r;
}

remove()

template<class T >

list< T > remove	(	list< T >	l,
		T	what )

Create a new list with a specific item removed.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list from which the item is to be removed.
what	The item to be removed.

Returns

list<T> A new list with the specified item removed.

Definition at line 214 of file list.ipp.

                           {
  if (is_nil (l)) return l;
  else if (l->item == what) return remove<T> (l->next, what);
  else return list<T> (l->item, remove<T> (l->next, what));
}

contains()

template<class T >

bool contains	(	list< T >	l,
		T	what )

Check if a list contains a specific item.

Template Parameters

T	The type of the data stored in the list.

Parameters

l	The list to be searched.
what	The item to search for.

Returns

true if the item is found in the list, false otherwise.

Definition at line 222 of file list.ipp.

                             {
  if (is_nil (l)) return false;
  if (l->item == what) return true;
 
  return contains (l->next, what);
}

operator<<() [1/4]

template<class T >

tm_ostream & operator<<	(	tm_ostream &	out,
		list< T >	l )

Definition at line 21 of file list.ipp.

                                        {
  out << "[";
  if (!is_nil (l)) {
    out << " " << l->item;
    l= l->next;
  }
  while (!is_nil (l)) {
    out << ", " << l->item;
    l= l->next;
  }
  return out << " ]";
}

operator<<() [2/4]

template<class T >

list< T > & operator<<	(	list< T > &	l,
		T	item )

Definition at line 37 of file list.ipp.

                                {
  if (is_nil (l)) l= list<T> (item, list<T> ());
  else l->next << item;
  return l;
}

operator<<() [3/4]

template<class T >

list< T > & operator<<	(	list< T > &	l1,
		list< T >	l2 )

Definition at line 37 of file list.ipp.

                                     {
  if (is_nil (l1)) l1= l2;
  else l1->next << l2;
  return l1;
}

operator>>()

template<class T >

list< T > & operator>>	(	T	item,
		list< T > &	l )

Definition at line 65 of file list.ipp.

                                {
  return (l= list<T> (item, l));
}

operator<<() [4/4]

template<class T >

list< T > & operator<<	(	T &	item,
		list< T > &	l )

Definition at line 65 of file list.ipp.

                                 {
  item= l->item;
  l   = l->next;
  return l;
}

operator==()

template<class T >

bool operator==	(	list< T >	l1,
		list< T >	l2 )

Definition at line 116 of file list.ipp.

                                    {
  bool l1_nil= is_nil (l1), l2_nil= is_nil (l2);
  if (l1_nil || l2_nil) return l1_nil == l2_nil;
  if (l1->item != l2->item) return false;
 
  return l1->next == l2->next;
}

operator!=()

template<class T >

bool operator!=	(	list< T >	l1,
		list< T >	l2 )

Definition at line 126 of file list.ipp.

                                    {
  if (is_nil (l1) || is_nil (l2)) return (is_nil (l1) != is_nil (l2));
  return (l1->item != l2->item) || (l1->next != l2->next);
}

operator<()

template<class T >

bool operator<	(	list< T >	l1,
		list< T >	l2 )

Definition at line 132 of file list.ipp.

                                   {
  if (is_nil (l1) || is_nil (l2)) return !is_nil (l2);
  return (l1->item == l2->item) && (l1->next < l2->next);
}

operator<=()

template<class T >

bool operator<=	(	list< T >	l1,
		list< T >	l2 )

Definition at line 139 of file list.ipp.

                                    {
  if (is_nil (l1) || is_nil (l2)) return is_nil (l1);
  return (l1->item == l2->item) && (l1->next <= l2->next);
}

Variable Documentation

list_count

int list_count

extern