flower/include/cons.hh

   1 /*
   2   cons.hh -- declare LISP like datatypes
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1999--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #ifndef CONS_HH
  10 #define CONS_HH
  11
  12 #include <cassert>
  13
  14 template<class T>
  15 class Cons
  16 {
  17 public:
  18   T *car_;
  19   Cons *next_;
  20   Cons ()
  21   {
  22     car_ = 0;
  23     next_ =0;
  24   }
  25   Cons (T *t, Cons<T>*c)
  26   {
  27     car_ = t;
  28     next_ = c;
  29   }
  30   virtual ~Cons ()
  31   {
  32     delete next_;
  33   }
  34 };
  35
  36 template<class T>
  37 class Killing_cons : public Cons<T>
  38 {
  39 public:
  40   Killing_cons (T *t, Cons<T> *p)
  41     : Cons<T> (t, p)
  42   {
  43   }
  44   virtual ~Killing_cons ();
  45 };
  46
  47 /// remove the link pointed to by *p.
  48 template<class T>
  49 Cons<T> *remove_cons (Cons<T> **pp)
  50 {
  51   Cons<T> *knip = *pp;
  52   *pp = (*pp)->next_;
  53   knip->next_ = 0;
  54   return knip;
  55 }
  56
  57 template<class T> int cons_list_size (Cons<T> *l)
  58 {
  59   int i = 0;
  60   while (l)
  61     {
  62       l = l->next_;
  63       i++;
  64     }
  65   return i;
  66 }
  67
  68
  69 template<class T>
  70 Cons<T> * last_cons (Cons<T> * head)
  71 {
  72   while (head && head->next_)
  73     {
  74       head = head->next_;
  75     }
  76   return head;
  77 }
  78
  79 /**
  80
  81 Invariants:
  82
  83 (*tail_) is either the head_ pointer, or a next_ pointer from the list.
  84
  85 **tail_ == NULL
  86 */
  87
  88 template<class T>
  89 class Cons_list
  90 {
  91 public:
  92   Cons<T> * head_;
  93   Cons<T> ** nil_pointer_address_;
  94   Cons_list ()
  95   {
  96     init ();
  97   }
  98   void init ()
  99   {
 100     head_ =0;
 101     nil_pointer_address_ = &head_;
 102   }
 103   void append (T *c)
 104   {
 105     append (new Cons<T> (c, 0));
 106   }
 107   void append (Cons<T> *c)
 108   {
 109     assert (!c->next_);
 110     *nil_pointer_address_ = c;
 111     while (*nil_pointer_address_)
 112       nil_pointer_address_ = &(*nil_pointer_address_)->next_;
 113   }
 114   /**
 115      PRE: *pp should either be the head_ pointer, or the next_ pointer
 116      from a list cell.
 117   */
 118   Cons<T> *remove_cons (Cons<T> **pp)
 119   {
 120     if (& (*pp)->next_ == nil_pointer_address_)
 121       nil_pointer_address_ = pp;
 122
 123     return ::remove_cons (pp);
 124   }
 125
 126   /// junk everything after the  first I elements.
 127   void truncate (int i)
 128   {
 129     Cons<T> **p = &head_;
 130     for (; *p && i; p = &((*p)->next_))
 131       {
 132         i--;
 133       }
 134
 135     if (*p)
 136       {
 137         delete *p;
 138         *p = 0;
 139       }
 140     nil_pointer_address_ = p;
 141   }
 142
 143   void junk ()
 144   {
 145     delete head_;
 146     head_ =0;
 147   }
 148   ~Cons_list ()
 149   {
 150     junk ();
 151   }
 152   int size ()
 153   {
 154     return cons_list_size (head_);
 155   }
 156 };
 157
 158 template<class T>
 159 void copy_killing_cons_list (Cons_list<T>&, Cons<T> *src);
 160 template<class T>
 161 void
 162 clone_killing_cons_list (Cons_list<T>&, Cons<T> *src);
 163
 164 #endif /* CONS_HH */
 165