/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Machine handling.
 * Copyright (C) 2000 Vincent Le Maout (vlemaout@lexiquest.fr).
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */


#ifndef ASTL_CURSOR_DEBUG
#define ASTL_CURSOR_DEBUG

#include <cursor.h>

#ifdef WIN32_OBSOLET_STREAMS
#include <iostream.h>
#else
#include <iostream>
#endif

#ifdef WIN32
using namespace std;
#endif

#include <utility>  // pair<>
#include <iostream>

// A plain cursor with default behavior checking its state before any processing
template <class DFA>
class cursor_debug : public cursor_concept
{
public:
  typedef cursor_debug        self;
  typedef typename DFA::State State;
  typedef typename DFA::Tag   Tag;
  typedef typename DFA::Alphabet Alphabet;

protected:
  const DFA *dfa;
  State q;
  bool singular;

public:
  cursor_debug()
    : dfa(NULL), singular(true)
  { cerr << "\t create " << endl; }

  cursor_debug(const DFA &a)
    : dfa(&a), singular(true)
  { cerr << "\t create " << endl; }

  cursor_debug(const DFA &a, State p)
    : dfa(&a), q(p)
  {
    cerr << "\t create " << endl;
    if (q == dfa->null_state) {
      cerr << "cursor::cursor(DFA, State) : warning" << endl;
      cerr << "\t cursor set on the sink state" << endl;
    }
  }

  State src() const {
    cerr << "\t src " << endl;
    if (singular) {
      cerr << "cursor::src() : warning" << endl;
      cerr << "\t trying to access state through a singular cursor" << endl;
    }
    return q;
  }

  self& operator= (State p) { 
    cerr << "\t = State " << endl;
    q = p;
    if (q == dfa->null_state) {
      cerr << "cursor::operator= (State) : warning" << endl;
      cerr << "\t assigning sink state to the cursor" << endl;
    }
    singular = false;
    return *this;
  }

  self& operator= (const self &x) {  
    cerr << "\t = self " << endl;
    if (this == &x) {
      cerr << "cursor::operator= (cursor &x) : warning" << endl;
      cerr << "\t assigning cursor to itself (this == &x)" << endl;
    }
    q = x.q;
    dfa = x.dfa;
    singular = x.singular;
    if (singular) {
      cerr << "cursor::operator= (cursor &x) : warning" << endl;
      cerr << "\t x has a singular value" << endl;
    }
    return *this;
  }

  bool operator== (const self &x) const {
      cerr << "\t == " << endl;
    if (this == &x) {
      cerr << "cursor::operator== (cursor &x) : warning" << endl;
      cerr << "\t comparing cursor to itself (this == &x)" << endl;
    }
    if (singular) {
      cerr << "cursor::operator==() : warning" << endl;
      cerr << "\t comparing a singular cursor" << endl;
    }
    return q == x.q;
  }

  bool sink() const {  cerr << "\t sink " << endl;
    if (singular) {
      cerr << "cursor::sink() : warning" << endl;
      cerr << "\t testing a singular cursor" << endl;
    }
    return q == dfa->null_state;
  }

  bool forward(const Alphabet &letter) {  cerr << "\tforward  " << letter <<  endl;
    if (singular) {
      cerr << "cursor::forward(letter) : warning" << endl;
      cerr << "\t trying to move along a transition through a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "cursor::forward(letter) : warning" << endl;
	cerr << "\t source state is the sink state" << endl;
      }
    q = dfa->delta1(q, letter);
    return q != dfa->null_state;
  }

  bool src_final() const {  cerr << "\t =src_final" << endl;
    if (singular) {
      cerr << "cursor::src_final() : warning" << endl;
      cerr << "\t trying to access source state of a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "cursor::src_final() : warning" << endl;
	cerr << "\t trying to access sink state" << endl;
      }
    return dfa->final(q);
  }

  const Tag& src_tag() const  {   cerr << "\t =src_tag " << endl;
    if (singular) {
      cerr << "cursor::src_tag() : warning" << endl;
      cerr << "\t testing a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "cursor::src_tag() : warning" << endl;
	cerr << "\t trying to access tag of sink state" << endl;
      }
    return dfa->tag(q);
  }

  bool exists(const Alphabet &letter) const {  // transition exists ?
    cerr << "\t exist " << endl;
   
    if (singular) {
      cerr << "cursor::exist() : warning" << endl;
      cerr << "\t testing for a transition through a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {  
	cerr << "cursor::exist() : warning" << endl;
	cerr << "\t testing for an outgoing transition of sink state" << endl;
      }
    return dfa->delta1(q, letter) != dfa->null_state;
  }
};

// A forward cursor with default behavior checking its state before any processing
template <class DFA>
class forward_cursor_debug : public forward_cursor_concept
{
public:
  typedef forward_cursor_debug self;
  typedef typename DFA::State  State;
  typedef typename DFA::Tag    Tag;
  typedef typename DFA::Alphabet Alphabet;

protected:
  typedef typename DFA::Edges::const_iterator edges_iterator;
  const DFA *dfa;
  State q;
  edges_iterator transition;
  bool dereferenceable, singular;  // singular: the only allowed operation is assignment
  // dereferenceable: letter and aim of current transition
  //                  are accessible

public:
  forward_cursor_debug(const DFA &a, State p, unsigned int Letter) 
    : dfa(&a), q(p), dereferenceable(false), singular(false)
  { 
    if (q == dfa->null_state) 
      cerr << "forward_cursor::forward_cursor(DFA, State, letter): warning" << endl
	   << "\t cursor initialized with null state" << endl;
    else
      if ((transition = dfa->delta2(q).find(Letter)) == dfa->delta2(q).end()) {
	cerr << "forward_cursor::forward_cursor(DFA, State, letter): warning" << endl;
	cerr << "\t cursor set on a sink transition" << endl; 
      }
      else
	dereferenceable = true;
  }
  
  forward_cursor_debug(const DFA &a, State p, edges_iterator t)
    : dfa(&a), q(p), transition(t), dereferenceable(false), singular(false)
  { 
    if (q == dfa->null_state) {
      cerr << "forward_cursor::forward_cursor(DFA, State, edges_iterator):";
      cerr << " warning" << endl << "\t cursor initialized with null state" << endl;
    } 
    else 
      dereferenceable = t != dfa->delta2(q).end();
  }
  
  forward_cursor_debug(const DFA &a, State p)
    : dfa(&a), q(p), dereferenceable(false), singular(false)
  {  cerr << "\t create " << endl;
    if (q == dfa->null_state) {
      cerr << "forward_cursor::forward_cursor(DFA, State): warning" << endl;
      cerr << "\t cursor initialized with null state" << endl;
    } 
  }

  forward_cursor_debug(const DFA &a)
    : dfa(&a), q(a.initial()), dereferenceable(false), singular(true)
  { 
    if (q == dfa->null_state) {
      cerr << "forward_cursor::forward_cursor(DFA): warning" << endl;
      cerr << "\t cursor initialized with initial state which is null" << endl;
    } 
  }

  forward_cursor_debug()
    : dfa(NULL), dereferenceable(false), singular(true)
  { }

  self& operator= (State p) { cerr << "\t assigning" << endl;
    q = p;
    dereferenceable = false;
    if (q == dfa->null_state) {
      cerr << "forward_cursor::operator= (State): warning" << endl;
      cerr << "\t assigning null state" << endl;
    }
    singular = false;
    return *this;
  }

  self& operator= (const self &x) { cerr << "\t assigning self " << endl;
    if (this == &x) {
      cerr << "forward_cursor::operator= (forward_cursor x): warning" << endl;
      cerr << "\t assigning cursor to itself (this == &x)" << endl;
    }
    q = x.q;
    transition = x.transition;
    dereferenceable = x.dereferenceable;
    singular = x.singular;
    dfa = x.dfa;
    if (singular) {
      cerr << "forward_cursor::operator= (forward_cursor x): warning" << endl;
      cerr << "\t x has a singular value" << endl;
    }
    if (dfa == NULL) {
      cerr << "forward_cursor::operator= (forward_cursor x): WARNING" << endl;
      cerr << "\t assigning a non-initialized cursor x (dfa == NULL)" << endl;
    }
      
    return *this;
  }

  bool operator== (const self &x) const { cerr << "\t == " << endl;
 
    if (this == &x) {
      cerr << "forward_cursor::operator== : warning" << endl;
      cerr << "\t comparing cursor with itself" << endl;
    }
    return (q == x.q && transition == x.transition);
  }

  Alphabet letter() const { cerr << "\t letter  " << endl;
    if (singular) {
      cerr << "forward_cursor::letter() : CRITICAL" << endl;
      cerr << "\t trying to access transition through a singular cursor" << endl;
    } 
    else
      if (!dereferenceable) {
	cerr << "forward_cursor::letter() : CRITICAL" << endl;
	cerr << "\t trying to access transition through a non dereferenceable cursor" << endl;
	cerr << "\t state = " << q << endl;
      }
    return (*transition).first;
  }

  bool sink() const {cerr << "\t sink  " << endl;
    if (singular) {
      cerr << "forward_cursor::sink() : WARNING" << endl;
      cerr << "\t testing for sink state on a singular cursor" << endl;
    } 
    return q == dfa->null_state;
  }

  State sink_state() const { cerr << "\t sink_state(  " << endl;
    if (singular) {
      cerr << "forward_cursor::sink_state() : WARNING" << endl;
      cerr << "\t requesting the sink state value from a singular cursor" << endl;
    } 
    return dfa->null_state;
  }

  // Obsolet:
  void to_sink() {
    if (singular) {
      cerr << "forward_cursor::to_sink() : WARNING" << endl;
      cerr << "\t moving a singular cursor to the sink state" << endl;
    } 
    if (dfa == NULL) {
      cerr << "forward_cursor::to_sink() : CRITICAL" << endl;
      cerr << "\t trying to move to the sink state with a non-initialized cursor (dfa == NULL)" << endl;
    } 
    q = dfa->null_state;
  }
    

  bool first_transition() { cerr << "\t first_transition()  " << endl;
    if (singular) {
      cerr << "forward_cursor::first_transition() : CRITICAL" << endl;
      cerr << "\t seeking first outgoing transition of a singular cursor" << endl;
    } 
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::first_transition() : CRITICAL" << endl;
	cerr << "\t trying to access first transition of sink source state" << endl;
      }
    return dereferenceable = (transition = dfa->delta2(q).begin()) != dfa->delta2(q).end();
  }
  
  bool next_transition() {  cerr << "\tnext_transition() " << endl;
    if (singular) {
      cerr << "forward_cursor::next_transition() : CRITICAL" << endl;
      cerr << "\t seeking next transition of a singular cursor" << endl;
    } 
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::next_transition() : CRITICAL" << endl;
	cerr << "\t seeking next transition of sink source state" << endl;
      }
      else
	if (!dereferenceable) {
	  cerr << "forward_cursor::next_transition() : WARNING" << endl;
	  cerr << "\t seeking next transition of a non dereferenceable cursor" << endl;
	}
    return dereferenceable = (++transition != dfa->delta2(q).end());
  }

  void forward() { cerr << "\t forward() " << endl;
    if (singular) {
      cerr << "forward_cursor::forward() : CRITICAL" << endl;
      cerr << "\t trying to move along transition of a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::forward() : CRITICAL" << endl;
	cerr << "\t trying to move along transition of sink source state" << endl;
      }
      else
	if (!dereferenceable) {
	  cerr << "forward_cursor::forward() : CRITICAL" << endl;
	  cerr << "\t trying to move along transition of a non dereferenceable cursor" << endl;
	}
    q = (*transition).second;
    dereferenceable = false;
  }

  bool find(const Alphabet &letter)  { cerr << "\t find(" << q << " " << letter << ") " << endl;
    if (singular) {
      cerr << "forward_cursor::find() : CRITICAL" << endl;
      cerr << "\t trying to find an outgoing transition through a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::find() : CRITICAL" << endl;
	cerr << "\t trying to find an outgoing transition of sink source state" << endl;
      }
    edges_iterator tmp = dfa->delta2(q).find(letter);
    if (tmp != dfa->delta2(q).end()) {
      transition = tmp;
      dereferenceable = true; cerr << " Found " << endl ;
      return true;
    }
    cerr << "not Found " << endl ;
    return false;
  }

  bool forward(const Alphabet &letter) {  cerr << "\t forward("<< letter <<") " << endl;
    if (singular) {
      cerr << "forward_cursor::forward(letter) : CRITICAL" << endl;
      cerr << "\t trying to move along transition through a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::forward(letter) : CRITICAL" << endl;
	cerr << "\t trying to move along outgoing transition of sink state" << endl;
      }
    dereferenceable = false;
    q = dfa->delta1(q, letter);
    return q != dfa->null_state;
  }

  State src() const { cerr << "\t src( "<< q  <<") " <<endl;
    if (singular) {
      cerr << "forward_cursor::src() : WARNING" << endl;
      cerr << "\t trying to access source state of a singular cursor" << endl;
    }
    return q;
  }

  State aim() const { cerr << "\t aim( " <<(*transition).second <<") " << endl;
    if (singular) {
      cerr << "forward_cursor::aim() : CRITICAL" << endl;
      cerr << "\t trying to access aim state of a singular cursor" << endl;
    }
    else
      if (!dereferenceable) {
	cerr << "forward_cursor::aim() : CRITICAL" << endl;
	cerr << "\t trying to access aim state of a non dereferenceable cursor" << endl;
      }
    return (*transition).second;
  }

  bool src_final() const {
    if (singular) {
      cerr << "forward_cursor::src_final() : WARNING" << endl;
      cerr << "\t trying to access source state of a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::src_final() : WARNING" << endl;
	cerr << "\t trying to access sink state" << endl;
      }
    return dfa->final(q);
  }

  bool aim_final() const {
    if (singular) {
      cerr << "forward_cursor::aim_final() : CRITICAL" << endl;
      cerr << "\t trying to access aim state of a singular cursor" << endl;
    }
    else
      if (!dereferenceable) {
	cerr << "forward_cursor::aim_final() : CRITICAL" << endl;
	cerr << "\t trying to access aim state of a non dereferenceable cursor" << endl;
      }
    return dfa->final((*transition).second);
  }

  const Tag& src_tag() const  {
    if (singular) {
      cerr << "forward_cursor::src_tag() : CRITICAL" << endl;
      cerr << "\t trying to access source tag of a singular cursor" << endl;
    }
    else
      if (q == dfa->null_state) {
	cerr << "forward_cursor::src_tag() : WARNING" << endl;
	cerr << "\t trying to access tag of sink state" << endl;
      }
    return dfa->tag(q);
  }

  const Tag& aim_tag() const {
    if (singular) {
      cerr << "forward_cursor::aim_tag() : CRITICAL" << endl;
      cerr << "\t trying to access aim tag of a singular cursor" << endl;
    }
    else
      if (!dereferenceable) {
	cerr << "forward_cursor::aim_tag() : CRITICAL" << endl;
	cerr << "\t trying to access aim tag of a non dereferenceable cursor";
      }
    return dfa->tag((*transition).second);
  }

  // Not a standard requirement:
  friend ostream& operator << (ostream &out, const self &x) {
    out << x.q << " , '";
    if (x.singular) out << "singular'";
    else
      if (!x.dereferenceable) {
	if (x.transition == x.dfa->delta2(x.q).end()) out << "end of range'";
	else
	  out << "not dereferenceable'";
      }
      else
	out << (*(x.transition)).first << "', " << (*(x.transition)).second;
    return out;
  }

  // Not a standard requirement:
  bool operator < (const self &x) const {   
    // STL containers need operator < on
    // their value_type (to define < on themselves)
    if (singular) 
      cerr << "forward_cursor::operator< (forward_cursor) : caution" << endl
	   << "\t comparing singular left cursor with"
	   << (x.singular ? " singular " : " ") << "right cursor" << endl; 
    else
      if (x.singular)
	cerr << "forward_cursor::operator< (forward_cursor) : caution" << endl
	     << "\t comparing left cursor with singular right cursor" << endl; 
    return q < x.q || (q == x.q && transition < x.transition);
  }
};

// Helper functions:
// Build a debug plain cursor from a DFA:
template <class DFA>
cursor_debug<DFA> debugplainc(const DFA &a) {
  return cursor_debug<DFA>(a, a.initial());
}

// Build a debug forward cursor from a DFA:
template <class DFA>
forward_cursor_debug<DFA> debugc(const DFA &a) {
  return forward_cursor_debug<DFA>(a, a.initial());
}

template <class Cursor>
class cursor_trace : public cursor_concept
{
public:
  typedef cursor_trace              self;
  typedef typename Cursor::State    State;
  typedef typename Cursor::Tag      Tag;
  typedef typename Cursor::Alphabet Alphabet;
  static int id;

protected:
  Cursor c;
  int ID;

public:
  cursor_trace()
    : c(), ID(++id) { 
    cerr << "cursor[" << ID << "]::cursor()" << endl;
  }

  cursor_trace(const Cursor &x)
    : c(x), ID(++id) {
    cerr << "cursor[" << ID << "]::cursor(Cursor " << &x << ")" << endl;
  }

  cursor_trace(const self &x) 
    : c(x.c), ID(x.ID) {
    cerr << "cursor[" << ID << "]::cursor(self)" << endl;
  }

  ~cursor_trace() {
    cerr << "cursor[" << ID << "]::~cursor()" << endl;
  }

  State src() const {
    cerr << "cursor[" << ID << "]::src() == " << c.src() << endl;
    return c.src();
  }

  self& operator= (State p) {
    cerr << "cursor[" << ID << "]::operator=(State " << p << ")" << endl;
    c = p;
    return *this;
  }

  self& operator= (const self &x) {
    cerr << "cursor[" << ID << "]::operator=(self [" << x.ID << "])" << endl;
    c = x.c;
    return *this;
  }

  bool operator== (const self &x) const {
    cerr << "cursor[" << ID << "]::operator==(self [" << x.ID << "]) == " << (c == x.c) << endl;
    return c == x.c;
  }

  bool sink() const {
    cerr << "cursor[" << ID << "]::sink() == " << c.sink() << endl;
    return c.sink();
  }

  bool forward(const Alphabet &letter) {
    cerr << "cursor[" << ID << "]::forward('" << letter << "') == ";
    cerr << c.forward(letter) << endl;
    return !c.sink();
  }

  bool src_final() const {
    cerr << "cursor[" << ID << "]::src_final() == " << c.src_final() << endl;
    return c.src_final();
  }

  const Tag& src_tag() const  {
    cerr << "cursor[" << ID << "]::src_tag()" << endl;
    return c.src_tag();
  }

  bool exists(const Alphabet &letter) const {      // transition exists ?
    cerr << "cursor[" << ID << "]::exist(int " << letter << ") == " << c.exists(letter) << endl;
    return c.exists(letter);
  }
};

template <class Cursor> int cursor_trace<Cursor>::id = 0;

template <class ForwardCursor>
class forward_cursor_trace : public forward_cursor_concept
{
public:
  typedef forward_cursor_trace             self;
  typedef typename ForwardCursor::State    State;
  typedef typename ForwardCursor::Tag      Tag;
  typedef typename ForwardCursor::Alphabet Alphabet;

protected:
  ForwardCursor c;
  static int id;
  int ID;

public:
  forward_cursor_trace(const ForwardCursor &x)
    : c(x), ID(++id)
  { 
    cerr << "fcursor[" << ID << "]::fcursor(forward_cursor " << &x << ")" << endl;
  }
  
  forward_cursor_trace()
    : c(), ID(++id)
  { 
    cerr << "fcursor[" << ID << "]::fcursor()";
  }

  forward_cursor_trace(const self &x) 
    : c(x.c), ID(++id)
  { 
    cerr << "fcursor[" << ID << "](self[" << x.ID << "])" << endl;
  }

  ~forward_cursor_trace()
  {
    cerr << "fcursor[" << ID << "]::~fcursor()" << endl;
  }
  
  self& operator= (State p) {
    cerr << "fcursor[" << ID << "]::operator=(State " << p << ")" << endl;
    c = p;
    return *this;
  }

  self& operator= (const self &x) {
    cerr << "fcursor[" << ID << "]::operator=(self [" << x.ID << "])" << endl;
    c = x.c;
    return *this;
  }

  bool operator== (const self &x) const {
    cerr << "fcursor[" << ID << "]::operator==(self [" << x.ID << "]) == " << (c == x.c) << endl;
    return (c == x.c);
  }

  Alphabet letter() const {
    cerr << "fcursor[" << ID << "]::letter() == '" << c.letter() << "'" << endl;
    return c.letter();
  }

  bool first_transition() {
    cerr << "fcursor[" << ID << "]::first_transition() == ";
    if (c.first_transition())
      cerr << "(" << c.src() << ", '" << c.letter() << "', " << c.aim() << ")" << endl;
    else
      cerr << "0" << endl;
    return c.first_transition();
  }
  
  bool next_transition() {
    bool r = c.next_transition();
    cerr << "fcursor[" << ID << "]::next_transition() == ";
    if (r)
       cerr << "(" << c.src() << ", '" << c.letter() << "', " << c.aim() << ")" << endl;
    else
      cerr << "0" << endl;     
    return r;
  }

  bool forward(const Alphabet &letter) {
    cerr << "fcursor[" << ID << "]::forward('" << letter << "') == ";
    if (c.forward(letter))
      cerr << c.src() << endl;
    else
      cerr << "0" << endl;
    return !c.sink();
  }

  void forward() {
    c.forward();
    cerr << "fcursor[" << ID << "]::forward() == " << c.src() << endl;
  }

  bool find(const Alphabet &letter)  {
    cerr << "fcursor[" << ID << "]::find('" << letter << "') == ";
    if (c.find(letter))
      cerr << "(" << c.src() << ", '" << c.letter() << "', " << c.aim() << ")" << endl;
    else
      cerr << "0" << endl;     
    return c.find(letter);
  }

  State src() const {
    cerr << "fcursor[" << ID << "]::src() == " << c.src() << endl;
    return c.src();
  }

  bool src_final() const {
    cerr << "fcursor[" << ID << "]::src_final() == " << c.src_final() << endl;
    return c.src_final();
  }

  State aim() const {
    cerr << "fcursor[" << ID << "]::aim() == " << c.aim() << endl;
    return c.aim();
  }

  bool aim_final() const {
    cerr << "fcursor[" << ID << "]::aim_final() == " << c.aim_final() << endl;
    return c.aim_final();
  }

  const Tag& aim_tag() const {
    cerr << "fcursor[" << ID << "]::aim_tag()" << endl;
    return c.aim_tag();
  }

  const Tag& src_tag() const {
    cerr << "fcursor[" << ID << "]::src_tag()" << endl;
    return c.src_tag();
  }

  bool sink() const {
    cerr << "fcursor[" << ID << "]::sink() == " << c.sink() << endl;
    return c.sink();
  }

  State sink_state() const {
    cerr << "fcursor[" << ID << "]::sink_state() == " << c.sink_state() << endl;
    return c.sink_state();
  }
};

template <class ForwardCursor> int forward_cursor_trace<ForwardCursor>::id = 0;

template <class ForwardCursor>
forward_cursor_trace<ForwardCursor> tracec(const ForwardCursor &x) {
  return forward_cursor_trace<ForwardCursor>(x);
}

// That might be useful:
template <class T, class U>
ostream& operator<< (ostream &out, const pair<T, U> &p) {
  out << "<" << p.first << ", " << p.second << ">";
  return out;
}

template <class T, class Allocator>
ostream& operator<< (ostream &out, const vector<T, Allocator> &v) 
{
  out << "(";
  if (v.empty()) return out << " )";
  vector<T, Allocator>::const_iterator i = v.begin();
  while (1) {
    out << *i;
    if (++i != v.end()) out << ",";
    else return out << ")";
  }
}
#endif // ASTL_CURSOR_DEBUG