Back to index

texmacs  1.0.7.15
list.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : list.cpp
00004 * DESCRIPTION: linked lists with reference counting
00005 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #ifndef LIST_CC
00013 #define LIST_CC
00014 #include "list.hpp"
00015 
00016 /******************************************************************************
00017 * output and convertion
00018 ******************************************************************************/
00019 
00020 template<class T> tm_ostream&
00021 operator << (tm_ostream& out, list<T> l) {
00022   out << "[";
00023   if (!is_nil (l)) {
00024     out << " " << l->item;
00025     l=l->next;
00026   }
00027   while (!is_nil (l)) {
00028     out << ", " << l->item;
00029     l=l->next;
00030   }
00031   return out << " ]";
00032 }
00033 
00034 template<class T> T&
00035 list<T>::operator [] (int i) {
00036   ASSERT (rep != NULL, "list too short");
00037   if (i==0) return rep->item;
00038   return rep->next[i-1];
00039 }
00040 
00041 template<class T> list<T>::operator tree () {
00042   list<T> l;
00043   int i, n=N(*this);
00044   tree t (TUPLE, n);
00045   for (i=0, l=*this; i<n; i++, l=l->next)
00046     t[i]= as_tree (l->item);
00047   return t;
00048 }
00049 
00050 /******************************************************************************
00051 * insertion and suppression
00052 ******************************************************************************/
00053 
00054 template<class T> list<T>&
00055 operator << (list<T>& l, T item) {
00056   if (is_nil (l)) l= list<T> (item, list<T> ());
00057   else l->next << item;
00058   return l;
00059 }
00060 
00061 template<class T> list<T>&
00062 operator << (list<T>& l1, list<T> l2) {
00063   if (is_nil (l1)) l1= l2;
00064   else l1->next << l2;
00065   return l1;
00066 }
00067 
00068 template<class T> list<T>&
00069 operator >> (T item, list<T>& l) {
00070   return (l= list<T> (item, l));
00071 }
00072 
00073 template<class T> list<T>&
00074 operator << (T& item, list<T>& l) {
00075   item= l->item;
00076   l   = l->next;
00077   return l;
00078 }
00079 
00080 template<class T> T
00081 last_item (list<T> l) {
00082   ASSERT (!is_nil (l), "empty path");
00083   if (is_nil (l->next)) return l->item;
00084   return last_item (l->next);
00085 }
00086 
00087 template<class T> T&
00088 access_last (list<T>& l) {
00089   ASSERT (!is_nil (l), "empty path");
00090   if (is_nil (l->next)) return l->item;
00091   return access_last (l->next);
00092 }
00093 
00094 template<class T> list<T>&
00095 suppress_last (list<T>& l) {
00096   ASSERT (!is_nil (l), "empty path");
00097   if (is_nil (l->next)) l= list<T> ();
00098   else suppress_last (l->next);
00099   return l;
00100 }
00101 
00102 /******************************************************************************
00103 * tests
00104 ******************************************************************************/
00105 
00106 template<class T> bool
00107 strong_equal (list<T> l1, list<T> l2) {
00108   return l1.rep == l2.rep;
00109 }
00110 
00111 template<class T> bool
00112 operator == (list<T> l1, list<T> l2) {
00113   if (is_nil (l1) || is_nil (l2)) return (is_nil (l1) == is_nil (l2));
00114   return (l1->item==l2->item) && (l1->next==l2->next);
00115 }
00116 
00117 template<class T> bool
00118 operator != (list<T> l1, list<T> l2) {
00119   if (is_nil (l1) || is_nil (l2)) return (is_nil (l1) != is_nil (l2));
00120   return (l1->item!=l2->item) || (l1->next!=l2->next);
00121 }
00122 
00123 template<class T> bool
00124 operator < (list<T> l1, list<T> l2) {
00125   if (is_nil (l1) || is_nil (l2)) return !is_nil (l2);
00126   return (l1->item==l2->item) && (l1->next<l2->next);
00127 }
00128 
00129 template<class T> bool
00130 operator <= (list<T> l1, list<T> l2) {
00131   if (is_nil (l1) || is_nil (l2)) return is_nil (l1);
00132   return (l1->item==l2->item) && (l1->next<=l2->next);
00133 }
00134 
00135 /******************************************************************************
00136 * computations with list<T> structures
00137 ******************************************************************************/
00138 
00139 template<class T> int
00140 N (list<T> l) {
00141   if (is_nil (l)) return 0;
00142   else return N (l->next) + 1;
00143 }
00144 
00145 template<class T> list<T>
00146 copy (list<T> l) {
00147   if (is_nil (l)) return list<T> ();
00148   else return list<T> (l->item, copy (l->next));
00149 }
00150 
00151 template<class T> list<T>
00152 operator * (list<T> l1, T x) {
00153   if (is_nil (l1)) return x;
00154   else return list<T> (l1->item, l1->next * x);
00155 }
00156 
00157 template<class T> list<T>
00158 operator * (list<T> l1, list<T> l2) {
00159   if (is_nil (l1)) return copy (l2);
00160   else return list<T> (l1->item, l1->next * l2);
00161 }
00162 
00163 template<class T> list<T>
00164 head (list<T> l, int n) {
00165   if (n==0) return list<T> ();
00166   ASSERT (!is_nil (l), "list too short");
00167   return list<T> (l->item, head (l->next, n-1));
00168 }
00169 
00170 template<class T> list<T>
00171 tail (list<T> l, int n) {
00172   for (; n>0; n--) {
00173     ASSERT (!is_nil (l), "list too short");
00174     l=l->next;
00175   }
00176   return l;
00177 }
00178 
00179 template<class T> list<T>
00180 reverse (list<T> l) {
00181   list<T> r;
00182   while (!is_nil(l)) {
00183     r= list<T> (l->item, r);
00184     l=l->next;
00185   }
00186   return r;
00187 }
00188 
00189 template<class T> list<T>
00190 remove (list<T> l, T what) {
00191   if (is_nil (l)) return l;
00192   else if (l->item == what) return remove (l->next, what);
00193   else return list<T> (l->item, remove (l->next, what));
00194 }
00195 
00196 template<class T> bool
00197 contains (list<T> l, T what) {
00198   return (!is_nil(l) && (l->item == what || contains(l->next, what)));
00199 }
00200 
00201 #endif // defined LIST_CC