/Users/mourrain/Devel/mmx/basix/include/basix/list.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : list.hpp
* DESCRIPTION: Linked lists
* COPYRIGHT  : (C) 2004  Joris van der Hoeven
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX_LIST_HPP
#define __MMX_LIST_HPP
#include <basix/vector.hpp>

// Linked lists

namespace mmx {
#define TMPL_DEF template<typename C>
#define TMPL template<typename C>
#define Format format<C>
#define List list<C>
#define List_rep list_rep<C>
TMPL class list_rep;
TMPL class list;
TMPL inline List cons (const C& c, const List& l);
TMPL inline const C& car (const List& l);
TMPL inline C& car (List& l);
TMPL inline const List& cdr (const List& l);
TMPL inline List& cdr (List& l);
TMPL inline bool is_nil (const List& l);

/******************************************************************************
* List class and its representation class
******************************************************************************/

TMPL_DEF
class list_rep REP_STRUCT {
  C    item;
  List next;

public:
  inline List_rep (const C& item2, const List& next2):
    item(item2), next(next2) {}
  friend class List;
  friend const C& car LESSGTR (const List& l);
  friend C& car LESSGTR (List& l);
  friend const List& cdr LESSGTR (const List& l);
  friend List& cdr LESSGTR (List& l);
};

TMPL_DEF
class list: public format<C> {
INDIRECT_PROTO_1 (list, list_rep, C)
private:
  inline list (const C& item, const List& next):
    Format (get_format (item)), rep (new List_rep (item, next)) {}
public:
  inline list ():
    Format (no_format ()), rep (NULL) {}
  inline list (const Format& fm):
    Format (fm), rep (NULL) {}
  inline list (const C& c1):
    Format (get_format (c1)), rep (new List_rep (c1, List ())) {}
  inline list (const C& c1, const C& c2):
    Format (get_format (c1)), rep (new List_rep (c1, List (c2))) {}
  inline list (const C& c1, const C& c2, const C& c3):
    Format (get_format (c1)), rep (new List_rep (c1, List (c2, c3))) {}
  inline list (const C& c1, const C& c2, const C& c3, const C& c4):
    Format (get_format (c1)), rep (new List_rep (c1, List (c2, c3, c4))) {}
  list (const vector<C>& v):
    Format (CF(v)), rep (NULL) {
    for (nat i=N(v)-1; i!=((nat) -1); i--) rep= new List_rep (v[i], *this); }
  list (const iterator<C>& it):
    Format (CF(it)) {
    if (busy (it)) { C c= *it; ++it; rep= new List_rep (c, it); }
    else rep= NULL; }
  const C& operator [] (nat i) const {
    ASSERT (rep != NULL, "non-empty list expected");
    return i==0? rep->item: read_only (rep->next) [i-1]; }
  C& operator [] (nat i) {
    ASSERT (rep != NULL, "non-empty list expected");
    secure ();
    return i==0? rep->item: rep->next[i-1]; }
  friend List cons LESSGTR (const C& c, const List& l);
  friend const C& car LESSGTR (const List& l);
  friend C& car LESSGTR (List& l);
  friend const List& cdr LESSGTR (const List& l);
  friend List& cdr LESSGTR (List& l);
  friend bool is_nil LESSGTR (const List& l);
};
DEFINE_UNARY_FORMAT_1 (list)

TMPL inline Format CF (const List& l) {
  return (Format) l; }
TMPL inline List::list (List_rep* rep2):
  Format (no_format ()), rep(rep2) {}
TMPL inline List::list (const List_rep* rep2, bool with_inc):
  Format (no_format ()), rep((List_rep*) (void*) rep2) {
  (void) with_inc; INC_NULL_COUNT (rep); }
TMPL inline List::list (const List& x):
  Format (CF(x)), rep(x.rep) {
  INC_NULL_COUNT (rep); }
TMPL inline List::~list () {
  DEC_NULL_COUNT (rep); }
TMPL inline const List_rep* List::operator -> () const {
  return rep; }
TMPL inline List_rep* List::operator -> () {
  return rep; }
TMPL inline List& List::operator = (const List& x) {
  INC_NULL_COUNT (x.rep); DEC_NULL_COUNT (rep);
  rep=x.rep; return *this; }
TMPL inline void List::secure () {
  if (rep->ref_count>1) *this= copy (*this); }
TMPL List_rep* inside (const List& x) {
  return const_cast<List_rep*> (x.operator -> ()); }
TMPL inline nat hard_hash (const List& x) {
  return as_hash (x.operator -> ()); }
TMPL inline bool hard_eq (const List& x, const List& y) {
  return (x.operator -> ()) == (y.operator -> ()); }
TMPL inline bool hard_neq (const List& x, const List& y) {
  return (x.operator -> ()) != (y.operator -> ()); }

TMPL struct species_type_information<List > {
  static const nat id= SPECIES_LIST; };

/******************************************************************************
* Basic constructors and accessors
******************************************************************************/

TMPL inline List cons (const C& c, const List& l) { return List (c, l); }
TMPL inline const C& car (const List& l) { return l.rep->item; }
TMPL inline const C& read_car (const List& l) { return car (l); }
TMPL inline C& car (List& l) { l.secure(); return l.rep->item; }
TMPL inline const List& cdr (const List& l) { return l.rep->next; }
TMPL inline const List& read_cdr (const List& l) { return cdr (l); }
TMPL inline List& cdr (List& l) { l.secure(); return l.rep->next; }
TMPL inline bool is_nil (const List& l) { return l.rep == NULL; }
TMPL inline bool is_atom (const List& l) {
  return !is_nil (l) && is_nil (cdr (l)); }
TMPL nat N (const List& l) { return is_nil (l)? 0: N (cdr (l)) + 1; }
TMPL inline const C& read (const List& l, nat i) { return l[i]; }

template<typename T, typename F>
struct as_helper<list<T>,list<F> > {
  static inline list<T>
  cv (const list<F>& l) {
    if (is_nil (l)) return list<T> ();
    else return cons (as<T> (car (l)), cv (cdr (l)));
  }
};

template<typename T, typename F> inline void
set_as (list<T>& r, const vector<F>& l) {
  if (is_nil (l)) r= list<T> (CF(r));
  else {
    T c; set_as (c, car (l));
    list<T> s (CF (r)); set_as (s, cdr (l));
    r= cons (c, s);
  }
}

template<typename C, typename T> inline void
set_as (List& r, const T& x) {
  T c; set_as (c, x);
  r= list<T> (c);
}

/******************************************************************************
* List iteration
******************************************************************************/

TMPL_DEF
class list_iterator_rep: public iterator_rep<C> {
  List l;  // the list to traverse
public:
  list_iterator_rep (const List& l2): l(l2) {}
protected:
  bool is_busy () { return !is_nil (l); }
  void advance () { l= read_cdr (l); }
  C current () { return read_car (l); }
  iterator_rep<C>* clone () { return new list_iterator_rep (l); }
};

TMPL iterator<C>
iterate (const List& l) {
  return iterator<C> (new list_iterator_rep<C> (l));
}

/******************************************************************************
* Hashing and equality testing
******************************************************************************/

template<typename Op,typename C> nat
unary_hash (const List& ll) {
  List l= ll;
  register nat h= 253648;
  while (!is_nil (l)) {
    h= (h<<1) ^ (h<<5) ^ (h>>27) ^ Op::op (read_car (l));
    l= read_cdr (l);
  }
  return h;
}

template<typename Op, typename C> bool
binary_test (const List& l1, const List& l2) {
  if (is_nil (l1) || is_nil (l2)) return is_nil (l1) && is_nil (l2);
  return Op::op (read_car (l1), read_car (l2)) &&
         binary_test<Op> (read_cdr (l1), read_cdr (l2));
}

TRUE_IDENTITY_OP_SUGAR(TMPL,List)
EXACT_IDENTITY_OP_SUGAR(TMPL,List)

/******************************************************************************
* Printing lists
******************************************************************************/

TMPL syntactic
flatten (const List& l) {
  vector<syntactic> v;
  List counter= l;
  while (!is_nil (counter)) {
    v << flatten (read_car (counter));
    counter= read_cdr (counter);
  }
  return apply (GEN_SQTUPLE, v);
}

TMPL
struct binary_helper<List >: public void_binary_helper<List > {
  static inline string short_type_name () {
    return "Li" * Short_type_name (C); }
  static inline generic full_type_name () {
    return gen ("List", Full_type_name (C)); }
  static inline generic disassemble (const List& l) {
    if (is_nil (l)) return gen_vec ();
    else return gen_vec (as<generic> (car (l)), as<generic> (cdr (l))); }
  static inline List assemble (const generic& x) {
    vector<generic> v= as<vector<generic> > (x);
    if (N(v) == 0) return List ();
    else return cons (as<C> (v[0]), as<List > (v[1])); }
  static inline void write (const port& out, const List& l) {
    if (is_nil (l)) binary_write<char> (out, '.');
    else {
      binary_write<char> (out, ',');
      binary_write<C> (out, car (l));
      binary_write<List > (out, cdr (l));
    } }
  static inline List read (const port& in) {
    if (binary_read<char> (in) == '.') return List ();
    else return cons (binary_read<C> (in), binary_read<List > (in)); }
};

/******************************************************************************
* Operations on lists
******************************************************************************/

TMPL List
copy (const List& l) {
  if (is_nil (l)) return l;
  return cons (car (l), cdr (l));
}

TMPL List
append (const List& l1, const List& l2) {
  if (is_nil (l1)) return copy (l2);
  return cons (car (l1), append (cdr (l1), l2));
}

TMPL inline List
operator * (const List& l1, const List& l2) {
  return append (l1, l2);
}

TMPL List
reverse (const List& ll) {
  List l= ll, r;
  while (!is_nil (l)) {
    r= cons (read_car (l), r);
    l= read_cdr (l);
  }
  return r;
}

TMPL List
range (const List& l, nat start, nat end) {
  if (start >= end) return List ();
  ASSERT (!is_nil (l), "non-empty list expected");
  if (start > 0) return range (cdr (l), start-1, end-1);
  return cons (car (l), range (cdr (l), 0, end-1));
}

TMPL List
insert (const List& l, const C& x) {
  if (is_nil (l)) return List (x);
  else if (car (l) == x) return l;
  else return cons (car (l), insert<C> (cdr (l), x));
}

TMPL int
find (const List& l, const C& x) {
  if (is_nil (l) || car (l) == x) return 0;
  else return find<C> (cdr (l), x) + 1;
}

TMPL bool
contains (const List& l, const C& x) {
  if (is_nil (l)) return false;
  else return car (l) == x || contains<C> (cdr (l), x);
}

/******************************************************************************
* Dynamic mappers
******************************************************************************/

template<typename S1, typename D> list<D>
map (const function_1<D,Argument(S1) >& fun,
     const list<S1>& l1, const format<D>& fm)
{
  if (is_nil (l1)) return list<D> (fm);
  else return cons (fun (car (l1)), map (fun, cdr (l1), fm));
}

template<typename S1, typename D> inline list<D>
map (D (*fun) (const S1&),
     const list<S1>& x1, const format<D>& fm) {
  return map (function_1<D,Argument(S1) > (fun), x1, fm);
}

#undef TMPL_DEF
#undef TMPL
#undef Format
#undef List
#undef List_rep
} // namespace mmx
#endif // __MMX_LIST_HPP