/* set.h */

/* a dc_set_atom has virtual functions that return true iff a label is a member
   of that set.
   a dc_finite_set is a set_atom that contains a rehashable set of dc_label*s 
   
   a dc_set consists of two list of set atoms, the members list, and the 
   exceptions list.  the members of the dc_set are then the difference of the
   union of all members and the union of all exceptions.
   */

#ifndef SET__H
#define SET__H

#include "user_types.h"
#include "data.h"
#include <LEDA/set.h>
#include <LEDA/list.h>

class dc_set_atom {
public:
  virtual bool member( const dc_label & ) const { return false; }

  virtual bool finite( void ) const { return false; }

  /* used to perform an operation on a set */
  virtual void exec( void ( dc_label * ) ) { return; }
  virtual void exec( void ( dc_label *, void * ), void * ) { return; }

  virtual ostream &display( ostream &stream = cout ) const;
  friend ostream &operator<<( ostream &stream, const dc_set_atom &s )
    { return s.display( stream ); }

  virtual dc_set_atom *duplicate( dc_label *origin ) = 0;
};

typedef dc_set_atom dc_empty_set;

class dc_all_set : public dc_set_atom {
public:
  bool member( const dc_label & ) const { return true; }

  void exec( void ( dc_label * ) );
  void exec( void ( dc_label *, void * ), void * );

  ostream &display( ostream &stream = cout ) const;

  dc_set_atom *duplicate( dc_label * ) { return new dc_all_set; }
};

class dc_finite_set : public dc_set_atom {
private:
  set<tag> S;

protected:
  void pr_add( dc_label &id ) { S.insert( id.get_tag() ); }
  void pr_remove( dc_label &id ) { S.del( id.get_tag() ); }
  void pr_clear( void ) { S.clear(); }

public:
  virtual ~dc_finite_set() { pr_clear(); }
  
  bool finite( void ) const { return true; }
  bool member( dc_label &id ) const { return S.member( id.get_tag() ); }
  int size( void ) const { return S.size(); }

  void exec( void ( dc_label * ) );
  void exec( void ( dc_label *, void * ), void * );

  virtual int rehash( void ) { return 0; }

  ostream &display( ostream &stream = cout ) const;

  set<tag> operator+( const set<tag> &s ) { return S + s; }
  set<tag> operator-( const set<tag> &s ) { return S - s; }
  set<tag> operator&( const set<tag> &s ) { return S & s; }
  friend inline set<tag> &operator+=( set<tag> &s, const dc_finite_set &S )
    { return s += S.S; }
  friend inline set<tag> &operator-=( set<tag> &s, const dc_finite_set &S )
    { return s -= S.S; }
  friend inline set<tag> &operator&=( set<tag> &s, const dc_finite_set &S )
    { return s &= S.S; }

  dc_set_atom *duplicate( dc_label *origin );
};

class dc_desc_set : public dc_finite_set {
protected:
  dc_label *desc_origin;
  string origin_str;

  dc_label *origin;

  user_type u_type;
  string key;
public:
  dc_desc_set( cstring, user_type, cstring, dc_label * );

  int rehash( void );

  friend bool desc_crit( dc_label *, void * ); /* search criterion needs to 
						  access key */
  friend void add_to_set( dc_label *, void * );
  ostream &display( ostream &stream = cout ) const;

  dc_set_atom *duplicate( dc_label *origin );
};

class dc_list_set : public dc_finite_set {
public:
  void add( dc_label &id ) { pr_add( id ); }
  void remove( dc_label &id ) { pr_remove( id ); }
  void clear( void ) { pr_clear(); }
};

class dc_label_set : public dc_finite_set {
private:
  /* used when rehashing */
  list<string> lbl_list;
  dc_label *origin;

public:
  dc_label_set() { origin = nil; }

  void add( cstring lbl ) { lbl_list.append( lbl ); }
  bool remove( cstring lbl  )
  { list_item li = lbl_list.search( lbl ); if( li ) { lbl_list.del_item( li ); return false; } return true; }
  void clear( void ) { lbl_list.clear(); pr_clear(); }

  void dc_set_origin( dc_label *o ) { origin = o; }

  int rehash( void );

  dc_set_atom *duplicate( dc_label *origin );
};

class dc_set : public dc_data {
private:
  list_item global_loc;

protected:
    /* list of sets and exceptions used to form arg list.  sets rehashed and
     only dc_data or dc_element returning arg_type are used */
  list<dc_finite_set *> sets;
  list<dc_finite_set *> exceptions;

  set<tag> members;
public:
  dc_set( void );
  dc_set( cstring label, dc_node *parent );
  
  ~dc_set( void );
  
  /* inherited functions */
  const dc_type type( void ) const { return Set_t; }
  string type_string( void ) const { return string( "set" ); }

  ostream &display( ostream &stream = cout ) { return display_c( stream ); }
  ostream &display_c( ostream &stream = cout ) const;
  friend ostream &operator<<( ostream &stream, const dc_set &S )
    { return S.display_c( stream ); }

  /* adds and removes will require a rehash before effects take place */
  void add_set( dc_finite_set &S ) { sets.append( &S ); }
  void add_exception( dc_finite_set &E ) { exceptions.append( &E ); }
  bool remove_set( int n ); /* removes nth member set */
  bool remove_exception( int n ); /* removes nth exception set */

  /* makes set empty */
  void clear();

  int size( void ) const { return members.size(); }

  bool member( dc_label &l ) const { return members.member( l.get_tag() ); }

  int rehash( void );

  void forall_members( void( dc_label * ) );
  void forall_members( void( dc_label *, void * ), void * );

  dc_set &operator=( const dc_set & );
  bool operator==( const dc_set & );
  bool operator!=( const dc_set & );
  bool operator<=( const dc_set & );
  bool operator>=( const dc_set & );
  bool operator<( const dc_set & );
  bool operator>( const dc_set & );

  dc_label *duplicate( dc_node *parent ) const;
};

int rehash_sets( void );

#endif
