/* graphs.cpp -- C++ source file for KSI Constraint Graphs
*/
/*
 *
 * Copyright (c) 1996
 * Knowledge Science Institute, University of Calgary
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  The Knowledge Science Institute makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

#ifdef __BCPLUSPLUS__ //---Borland C++
#include 
#pragma hdrstop
#endif

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define MAX_NAME 200

extern ObjectLibrary* AttributeTypeLibrary;
extern ObjectLibrary* GraphsTypeLibrary;
extern ObjectLibrary* ConstraintLibrary;

/*******************************************************************************
************************************ Attribute *********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

ostream& Attribute::printOn(ostream& o) const
  {
  Lexer::writeQuotedString(o,Name);
  Lexer::writeDelim(o);
  Lexer::writeUnsigned(o,Priority);
  Lexer::writeDelim(o);
  Lexer::writeUnsigned(o,Flags);
  return o;
  }

istream& Attribute::readFrom(istream& i)
  {
  Lexer::readQuotedString(i,Name);
  Lexer::readDelim(i);
  unsigned long temp;
  Lexer::readUnsigned(i,temp);
  Priority = temp;
  Lexer::readDelim(i);
  Lexer::readUnsigned(i,temp);
  Flags = temp;
  return i;
  }

/*******************************************************************************
************************************ Terminal **********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

ostream& Terminal::printOn(ostream& o) const
  {
  o << Anchor;
  Lexer::writeDelim(o);
  Lexer::writeUnsigned(o,Direction);
  return o;
  }

istream& Terminal::readFrom(istream& i)
  {
  i >> Anchor;
  Lexer::readDelim(i);
  unsigned long temp;
  Lexer::readUnsigned(i,temp);
  Direction = temp;
  return i;
  }

/*******************************************************************************
************************************ Component0 ********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

bool Component0::setAttr(Attribute* a)
  { //returns true if the attribute is a new one, false if an attribute is replaced
  MASSERT_COMPONENT(a);
  Ref2 r(a);
  pair res = Attributes.insert(r);
  bool ret = res.second;
  if (!ret) { // there was already such an attribute -- replace it
    Attributes.erase(res.first);
    Attributes.insert(r);
    ret = true;
    }
  notify();
  return ret;
  }

Component0::AttrIterator Component0::getAttr(const string& name) const
  {
  Attribute a(name,0u,(Attribute::Attr_Flags)0);
  Ref2 r(&a);
  PolySetOfAttributes::iterator i(Attributes.find(r));
  return i;
  }

bool Component0::eraseAttr(const string& name)
  {
  PolySetOfAttributes::iterator i(Attributes.find(Ref2(Attribute(name,0u,(Attribute::Attr_Flags)0))));
  bool ret;
  if (i == Attributes.end())
    ret = false;
  else {
    ret = true;
    Attributes.erase(i);
    notify();
    }
  return ret;
  }

Component0& Component0::operator=(const Component0& c)
  {
  Name = c.Name;
  Level = c.Level;
  PolySetOfAttributes::iterator i;
  Attributes = c.Attributes;
  Id = c.Id;
  notify();
  return *this;
  }

int Component0::operator==(const Component0& c) const
  {
  return Id == c.Id;
  }

int Component0::operator<(const Component0& c) const
  {
  return Id < c.Id;
  }

int Component0::addConstraint(const string& constraintName)
  {
  int ret = 0;
  AttrIterator ai = getAttr("constraints");
  if (ai==endAttr()) {
    setAttr(MakeAttribute("constraints",ConjunctionOfValidators(),100,0));
    ai = getAttr("constraints");
    }
  AttributeValuePair* ap = dynamic_cast*>(&**ai);
  MASSERT(ap);
  ConjunctionOfValidators* v = &(ConjunctionOfValidators&)ap->getValue();
  MASSERT(v);
  MASSERT(ConstraintLibrary);
  Validator* con = ConstraintLibrary->makeCopy(constraintName);
  if (con) v->push_back(Ref2(con,true));
  else {
    ret = -7;
    error(0,'E',"Unable to find constraint '%s' in ConstraintLibrary",constraintName.c_str());
    }
  return ret;
  }

ostream& Component0::printOn(ostream& out) const
  {
  Lexer::writeUnsigned(out,Id);
  Lexer::writeDelim(out);
  Lexer::writeQuotedString(out,Name);
  Lexer::writeDelim(out);
  Lexer::writeUnsigned(out,Level);
  Lexer::writeDelim(out);
  Lexer::writeDelim(out,'(');
  for(AttrIterator i(Attributes.begin()); i!=Attributes.end(); i++) {
    Lexer::writeDelim(out,'(');
    Lexer::writeQuotedString(out,typeid(**i).name());
    Lexer::writeDelim(out);
    out << **i;
    Lexer::writeDelim(out,')');
    }
  Lexer::writeDelim(out,')');
  return out;
  }

istream& Component0::readFrom(istream& in)
  {
  unsigned long temp;
  Lexer::readUnsigned(in,temp); Id = temp;
  Lexer::readDelim(in);
  Lexer::readQuotedString(in,Name);
  Lexer::readDelim(in);
  Lexer::readUnsigned(in,temp); Level = temp;
  Lexer::readDelim(in);
  Lexer::readDelim(in,'(');
  Attributes.erase(Attributes.begin(),Attributes.end()); //clear any current attributes
  while (!Lexer::readDelim(in,'(')) {
    string t;
    Lexer::readQuotedString(in,t);
    Lexer::readDelim(in);
    Attribute* a = AttributeTypeLibrary->makeCopy(t);
    if (a) {
      in >> *a;
      setAttr(a);
      }
    else error(0,'E',"Can't find %s in AttributeTypeLibrary",t.c_str());
    Lexer::readDelim(in,')');
    }
  Lexer::readDelim(in,')');
  return in;
  }

/*******************************************************************************
*************************************** Arc0 ***********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

void Arc0::putAnchor(int n, ID_type c, Terminal::DIRECTION dir)
  {
  if (n>=Terminals.size()) Terminals.insert(Terminals.end(),(n+1)-Terminals.size(),Terminal());
  Terminals[n] = Terminal(c,dir);
  MASSERT_THROW(Terminals.size() > n,true);
  MASSERT_THROW(Terminals[n].getAnchorID()==c,true);
  MASSERT_THROW(Terminals[n].getDirection()==dir,true);
  }

int Arc0::findAnchor(ID_type id) //returns the matching terminal index; -1 on failure
  {
  int j=0;
  for (TerminalIterator i=Terminals.begin(); i!=Terminals.end(); i++,j++) {
    if ((*i).getAnchorID()==id) return j;
    }
  return -1;
  }

/*******************************************************************************
********************************* ArcComponent *********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

void ArcComponent::verify()
  {
  Arc0::verify();
  }

ostream& ArcComponent::printOn(ostream& out) const
  {
  Component0::printOn(out);
  Lexer::writeDelim(out);
  Lexer::writeDelim(out,'(');
  for (terminals_type::const_iterator i(Terminals.begin()); i!=Terminals.end(); i++) {
    Lexer::writeDelim(out,'(');
    out << *i;
    Lexer::writeDelim(out,')');
    }
  Lexer::writeDelim(out,')');
  return out;
  }

istream& ArcComponent::readFrom(istream& in)
  {
  Component0::readFrom(in);
  Lexer::readDelim(in);
  Terminals.erase(Terminals.begin(),Terminals.end()); //clear any terminals
  Lexer::readDelim(in,'(');
  while (!Lexer::readDelim(in,'(')) {
    Terminal t;
    in >> t;
    Terminals.push_back(t);
    Lexer::readDelim(in,')');
    }
  Lexer::readDelim(in,')');
  return in;
  }

/*******************************************************************************
********************************** IsaComponent ********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

IsaComponent* IsaComponent::Prototype = NULL;

void IsaComponent::verify()
  {
  ArcComponent::verify();
  //These should all be handled by Validators
  //MASSERT_COMPONENT(Terminals.size()==2);
  //MASSERT_COMPONENT(getTerminalDir(0) == Terminal::FROM);
  //MASSERT_COMPONENT(getTerminalDir(1) == Terminal::TO);
  //MASSERT_COMPONENT(getTerminalID(0));
  //MASSERT_COMPONENT(getTerminalID(1));
  //MASSERT_COMPONENT(getName()=="isa"?true:!(getTerminalID(0)==getTerminalID(1)));
  }

Component0::AttrIterator IsaComponent::getAttr(const string& name) const
  {
  AttrIterator ret = ArcComponent::getAttr(name);
  if (ret==endAttr() && Prototype && Prototype->getID()!=getID()) {
    AttrIterator ret2 = Prototype->getAttr(name);
    if (!(ret2 == Prototype->endAttr())) ret = ret2;
    }
  return ret;
  }

/*******************************************************************************
************************************ TypedGraph ********************************
*******************************************************************************/
/*
  Z spec,
  declaration */

TypedGraph::TypedGraph()
	: _top("top",1),
          _node("node",1,1),
          _arc("arc",1,vector()),
          _isa("isa",1,vector()),
          _nodeIsa("isa",1,vector()),
          _arcIsa("isa",1,vector()),
          _isaIsa("isa",1,vector())
  {
  NextID = 1; //we reserve 0 as an "uninstantiated" ID number
  Flags = checking;

  //these are "fundamental" objects
  _top.Id  = getNextID();
  _node.Id = getNextID();
  _arc.Id  = getNextID();
  _isa.Id  = getNextID();
  _isa.setPrototype(&_isa);
  _nodeIsa.Id = getNextID();
  _arcIsa.Id = getNextID();
  _isaIsa.Id = getNextID();
  LastFundamentalObject = _isaIsa.Id;

  //connect up the "fundamental" objects
  _isa.putAnchor(0,_top.getID(),Terminal::FROM);
  _isa.putAnchor(1,_top.getID(),Terminal::TO);
  _arc.putAnchor(0,_top.getID(),Terminal::BIDIRECT);
  //define the type hierarchy
  _nodeIsa.putAnchor(0,_node.getID(),Terminal::FROM);
  _nodeIsa.putAnchor(1,_top.getID(),Terminal::TO);
  _arcIsa.putAnchor(0,_arc.getID(),Terminal::FROM);
  _arcIsa.putAnchor(1,_top.getID(),Terminal::TO);
  _isaIsa.putAnchor(0,_isa.getID(),Terminal::FROM);
  _isaIsa.putAnchor(1,_arc.getID(),Terminal::TO);

  //add in their constraints attributes
  _top.setAttr(MakeAttribute((string)"constraints",ConjunctionOfValidators(),100u,0u));
  _node.setAttr(MakeAttribute((string)"constraints",ConjunctionOfValidators(),100u,0u));
  _arc.setAttr(MakeAttribute((string)"constraints",ConjunctionOfValidators(),100u,0u));
  _isa.setAttr(MakeAttribute((string)"constraints",ConjunctionOfValidators(),100u,0u));

  //add the actual constraints
  _top.addConstraint("NoConstAttrOverrides");
  _arc.addConstraint("NoSelfReference");
  _arc.addConstraint("ConfinedToGraph");
  _arc.addConstraint("ArcConformance");
  _isa.addConstraint("Upward"); //implies "Directed" and "Arity=2"
  _isa.addConstraint("NoDanglingTerminals");

  //insert them
  Contents.insert(content_element_type( _top.getID(),Ref2(& _top)));
  Contents.insert(content_element_type(_node.getID(),Ref2(&_node)));
  Contents.insert(content_element_type( _arc.getID(),Ref2(& _arc)));
  Contents.insert(content_element_type( _isa.getID(),Ref2(& _isa)));
  Contents.insert(content_element_type( _nodeIsa.getID(),Ref2(& _nodeIsa)));
  Contents.insert(content_element_type( _arcIsa.getID(),Ref2(& _arcIsa)));
  Contents.insert(content_element_type( _isaIsa.getID(),Ref2(& _isaIsa)));
  }

void TypedGraph::verify(unsigned long flags)
  {
  if (!getChecking()) return;

  /*	| % node, arc, and isa are the only level one objects
	| Level1Objects subset Contents; */
  //MASSERT_THROW(Contents.find(Ref2(_node))!=Contents.end(),!flags&Validator::silent);
  MASSERT_THROW((*this)[     _top.getID()] == _top    ,!flags&Validator::silent);
  MASSERT_THROW((*this)[    _node.getID()] == _node   ,!flags&Validator::silent);
  MASSERT_THROW((*this)[     _arc.getID()] == _arc    ,!flags&Validator::silent);
  MASSERT_THROW((*this)[     _isa.getID()] == _isa    ,!flags&Validator::silent);
  MASSERT_THROW((*this)[ _nodeIsa.getID()] == _nodeIsa,!flags&Validator::silent);
  MASSERT_THROW((*this)[  _arcIsa.getID()] == _arcIsa ,!flags&Validator::silent);
  MASSERT_THROW((*this)[  _isaIsa.getID()] == _isaIsa ,!flags&Validator::silent);

  /*
  contents_type::iterator c;
  for (c=Contents.begin(); c!=Contents.end(); c++) {
    Component0& c0 = *(*c).second;
    verify(c0,flags);
    }
  */
  verify(_top,flags);
  }

void TypedGraph::verify(Component0& c, unsigned long flags)
  {
  if (!getChecking()) return;

  verifyPrimative(c,flags);

  //verify all the subtypes of c
  contents_type::iterator i;
  for (i=Contents.begin(); i!=Contents.end(); i++) {
    if (parentof(c.getID(),(*i).first)) {
      Component0& c0 = *(*i).second;
      verifyPrimative(c0,flags);
      }
    }
  }

void TypedGraph::verifyPrimative(Component0& c, unsigned long flags)
  {
  if (!getChecking()) return;

  //object itself is first verified...
  c.verify();

  /*	| % The only level 1 objects are TOP, NODE, ARC, and ISA and their
	| % isa arcs that define the type hierarchy
	| #{c:COMPONENT | c.Level = 1} = 7; */
  MASSERT_THROW(c.getLevel()>1?true:(c==_node    ||
				     c==_arc     ||
				     c==_isa     ||
				     c==_top     ||
                                     c==_nodeIsa ||
                                     c==_arcIsa  ||
                                     c==_isaIsa  ),!flags&Validator::silent);

  /*	| % there are no cycles over the isa relationship
	| forall c:Contents @ not (c ancestorof c); */
  MASSERT_THROW(c==_top || !ancestorof(c.getID(),c.getID()),!flags&Validator::silent);

  /*	| % everything is a NODE or ARC, but only one of these
	| forall c:Contents @
	|	(c isa NODE \/ c isa ARC)		/\
	|	(c isa NODE) => not (c isa ARC)		/\
	|	(c isa ARC ) => not (c isa NODE); */
  if (dynamic_cast(&c)) {
    MASSERT_THROW( isa(c.getID(),_isa.getID() ),!flags&Validator::silent);
    MASSERT_THROW(!isa(c.getID(),_node.getID()),!flags&Validator::silent);
    //MASSERT_THROW(!isa(c.getID(), _arc.getID()),!flags&Validator::silent);
    }
  else if (dynamic_cast(&c)) {
    //MASSERT_THROW(!isa(c.getID(), _isa.getID()),!flags&Validator::silent);
    MASSERT_THROW(!isa(c.getID(),_node.getID()),!flags&Validator::silent);
    MASSERT_THROW( isa(c.getID(), _arc.getID()),!flags&Validator::silent);
    }
  else if (dynamic_cast(&c)) {
    //MASSERT_THROW(!isa(c.getID(), _isa.getID()),!flags&Validator::silent);
    MASSERT_THROW( isa(c.getID(),_node.getID()),!flags&Validator::silent);
    MASSERT_THROW(!isa(c.getID(), _arc.getID()),!flags&Validator::silent);
    }
  else MASSERT_THROW(c==_top,!flags&Validator::silent);

  /*	| % all components satisfy their constraints
	| exists g:GRAPH0 | g.Contents = Contents @
	|    forall c:g.Contents @
	|	forall c2:g.Contents | c isa c2 @ forall v:VALIDATOR | v in c2.Constraints @
	|		v(c,c2,g) = PASS; */
  ConjunctionOfValidators v;
  //Ref2 valid(v);
  for (contents_type::iterator c2=Contents.begin(); c2!=Contents.end(); c2++) {
    if (isa(c.getID(),(*c2).first)) {
      if (!getValue(*this,(*c2).first,string("constraints"),v/*valid*/)) { //got a validator
        //MASSERT_THROW(((Validator&)valid)(*(*c2).second,*this),!flags&Validator::silent);
        MASSERT_THROW(v(c,*(*c2).second,*this,flags),false);
        }
      }
    }
  }

/*	| % _ parentof _ : a little complicated because we need a special case
	| %                for ISA_COMPONENTs to prevent endless recursion of isa's
	| (forall p,c:Contents | p /= ISA @
	|	p parentof c <=> (exists a:ISA_COMPONENT | a in Contents @
	|		GetTerminal(a,2) = p /\ GetTerminal(a,1) = c))
	| /\
	| (forall p,c:Contents | p = ISA @
	|	p parentof c <=> (c.Role in ran isa_arc /\ p /= c /\
	|		not (exists a:ISA_COMPONENT | a in Contents @
	|			GetTerminal(a,2) = p /\ GetTerminal(a,1) = c))); */
bool TypedGraph::parentof(ID_type p, ID_type c) const
  {
  if (c==getTopType() || p==c) return false;
  if (p && c) {
    for (contents_type::const_iterator i(Contents.begin()); i!=Contents.end(); i++) {
      IsaComponent* isa = dynamic_cast((Component0*)(*i).second);
      if (isa && isa->getTerminalID(0) && isa->getTerminalID(0)==c &&
		  isa->getTerminalID(1) && isa->getTerminalID(1)==p) return true;
      }
    if (p == getIsaType() && p!=c) { //the exception, any IsaComponent otherwise without a parent has the ISA prototype as a parent
      IsaComponent* isa = dynamic_cast(&(*this)[c]);
      if (isa) return true;
      }
    //the following 2 clauses fake isa arcs between {arcs|nodes} and the level-1
    //prototypes.  This is a bit a hack, but it allows us to cut the number of objects
    //in some graphs almost in half.
    if (p == getArcType() && p!=c) {
      ArcComponent* arc = dynamic_cast(&(*this)[c]);
      if (arc) return true;
      }
    if (p == getNodeType() && p!=c) {
      NodeComponent* node = dynamic_cast(&(*this)[c]);
      if (node) return true;
      }
    }
  return false;
  }

/*	| % _ancestorof _
	| forall c1,c2:Contents @
	|	c1 ancestorof c2 <=> (c1,c2) in ( _ parentof _ )^*; */
bool TypedGraph::ancestorof(ID_type p, ID_type c) const
  {
  //this implemenation does not mirror the spec very well, but it conforms and
  //it's a lot more efficient.
  if (c==getTopType() || p==c) return false;
  if (p==getTopType()) return true;
  if (p && c) {
    if (p == getIsaType()) { //the exception, all IsaComponents must be subtypes of the ISA prototype
      IsaComponent* isa = dynamic_cast(&(*this)[c]);
      if (isa) return true;
      }

    //the following 2 clauses fake isa arcs between {arcs|nodes} and the level-1
    //prototypes.  This is a bit a hack, but it allows us to cut the number of objects
    //in some graphs almost in half.
    if (p == getArcType()) {
      ArcComponent* arc = dynamic_cast(&(*this)[c]);
      if (arc) return true;
      }
    if (p == getNodeType()) {
      NodeComponent* node = dynamic_cast(&(*this)[c]);
      if (node) return true;
      }

    for (contents_type::const_iterator i=Contents.begin(); i!=Contents.end(); i++) {
      IsaComponent* isa = dynamic_cast((Component0*)(*i).second);
      if (isa && isa->getTerminalID(0) && isa->getTerminalID(0)==c && isa->getTerminalID(1)) {
	if (isa->getTerminalID(1)==p) return true;
	else if (ancestorof(p,isa->getTerminalID(1))) return true;
	}
      }
    }
  return false;
  }

/*	| % _ isa _
	| forall p,c:Contents @ c isa p <=> ((p = c) \/ (p ancestorof c)); */
bool TypedGraph::isa(ID_type c, ID_type p) const
  {
  return (p && c) && (c==p || ancestorof(p,c));
  }

  /*	| getAttr: TYPED_GRAPH & COMPONENT & ATTRIBUTE_NAME --> GETATTR_RESULT
	|--------------
	| forall g:TYPED_GRAPH; c:COMPONENT; a:ATTRIBUTE_NAME | c in g.Contents @
	|   getAttr(g,c,a) =
	|     if (exists at:c.Attributes @ a = at.Name)
	|	% c actually has the attribute
	|       then (mu x:c.Attributes | (a = x.Name))
	|       else if (forall c2:g.Contents | c2 parentof c @
	|						getAttr(g,c2,a) = NULLr)
	|	  % attribute not found
	|         then NULLr
	|	  % attribute found in one of the ancestors
	|         else (mu x:ATTRIBUTE | forall c2:g.Contents | c2->c in g.parentof0 /\
	|		(exists y:ATTRIBUTE @ y=Attr~(getAttr(g,c2,a))) @
	|		  exists y:ATTRIBUTE | y=Attr~(getAttr(g,c2,a)) @
	|		    forall c3:g.Contents | c3->c in g.parentof0 /\
	|		      (exists z:ATTRIBUTE @ z=Attr~(getAttr(g,c3,a))) /\
	|		      (not (c3->c2 in g.ancestorof0)) @
	|		        exists z:ATTRIBUTE | z=Attr~(getAttr(g,c3,a)) @
	|		          y.Priority<=z.Priority /\ x=y) */
Attribute* TypedGraph::getAttr(ID_type id, const string& attrName)
  {
  Attribute* ret = NULL;
  Component0& c = (*this)[id];
  Component0::AttrIterator a = c.getAttr(attrName);
  if (!(a == c.endAttr())) ret = (Attribute*)(*a);
  if (!ret) {
    ID_type idOfRet;
    for (contents_type::iterator i = Contents.begin(); i!=Contents.end(); i++) {
      if (parentof((*i).second->getID(),id)) {
	Attribute* temp = getAttr((*i).first/*second->getID()*/,attrName);
	if (temp) {
	  //if ((!ret) || (temp->getPriority() < ret->getPriority())) ret = temp;
          if (!ret) {
            ret = temp;
            idOfRet = (*i).first;
            }
          else {
            if (ancestorof(idOfRet,(*i).first)) {
              ret = temp;
              idOfRet = (*i).first;
              }
            else if ((!ancestorof((*i).first,idOfRet)) && (temp->getPriority() < ret->getPriority())) {
              ret = temp;
              idOfRet = (*i).first;
              }
            }
	  }
	}
      }
    }
  return ret;
  }

  /*	---setAttr----------------------------------------------------------------
	| Delta TYPED_GRAPH;
	| c?: COMPONENT;
	| attr?: ATTRIBUTE
	|---------------
	| c? in Contents;
	| Contents' = (Contents \ {c?}) || {(mu c2:Contents |
	|	c2.Name  = c?.Name	/\
	|	c2.Level = c?.Level	/\
	|	c2.Role  = c?.Role	/\
	|	c2.Attributes = (c?.Attributes \
	|		{a:c?.Attributes | a.Name = attr?.Name}) ||
	|		{attr?})}
	-------------------------------------------------------------------------- */
int TypedGraph::setAttr(ID_type id, Attribute* attr)
  {
  int ret = 0;

  Component0& comp = (*this)[id];
  Attribute* oldAttr = NULL;
  Component0::AttrIterator oai = comp.getAttr(attr->getName());
  if (!(oai==comp.endAttr())) {
    oldAttr = (**oai).clone();
    }

  comp.setAttr(attr);

  try {
    verify(comp,0);
    }
  catch(...) {
    error(0,'E',"Attribute '%s' caused a constraint violation; it will be %s",
    		attr->getName().c_str(),
                oldAttr?"restored to its original value":"deleted");
    if (oldAttr) {
      comp.setAttr(oldAttr);
      oldAttr = NULL;
      }
    else {
      comp.eraseAttr(attr->getName()); //so this lower-level version avoids the problem
      }
    ret = -2;
    }

  if (oldAttr) delete oldAttr;

  if (!ret) {
    //notify all the observers of subtypes just in case this attribute change affects them
    notifyDependents(id);
    }

  return ret;
  }

void TypedGraph::notifyDependents(ID_type id)
  {
  for (contents_type::iterator c=Contents.begin(); c!=Contents.end(); c++) {
    if (isa((*c).second->getID(),id)) (*c).second->notify();
    }
  ArcComponent* a = dynamic_cast(&(*this)[id]);
  if (a) {
    for (Arc0::TerminalIterator i = a->beginTerminal(); i!=a->endTerminal(); i++) {
      ID_type id = (*i).getAnchorID();
      if (id) {
        Component0& c = (*this)[id];
        c.notify();
        notifyDependents(c.getID());
        }
      }
    }
  }

int TypedGraph::removeAttr(ID_type id, const string& attrName)
  {
  int ret = -3;
  //get a copy of the attr, just in case we have to restore it
  Attribute* orig = getAttr(id,attrName);
  if (orig) { //can't remove an attr that doesn't exist
    orig = orig->clone();
    bool shouldDelete = true;

    ret = (*this)[id].eraseAttr(attrName)?0:-1;

    if (!ret) {
      try {
	verify((*this)[id],0);
	}
      catch(...) {
	(*this)[id].setAttr(orig);
	ret = -2;
	shouldDelete = false;
	}
      }

    if (!ret) {
      //notify all the observers of subtypes just in case this attribute change affects them
      for (contents_type::iterator c=Contents.begin(); c!=Contents.end(); c++) {
	if (ancestorof(id,(*c).second->getID())) (*c).second->notify();
	}
      }

    if (shouldDelete) delete orig;
    }

  return ret;
  }

int TypedGraph::insertComponent(Component0& c) //this is a low-level method, no checks are done -- you must set its type, etc
  {
  if (!c.Id) c.Id = getNextID();
  int ret = c.Id;
  pair res = Contents.insert(contents_type::value_type(c.Id,Ref2(c)));
  if (!res.second) ret = -18;
  return ret;
  }

  /*	---ADD_NODE---------------------------------------------------------------
	| Delta TYPED_GRAPH;
	| node?: NODE_COMPONENT;
	| type?: NODE_COMPONENT
	|---------------
	| TYPED_GRAPH';
	| type? in Contents;
	| % not (node? in Level1Objects);
	| getAttr((mu x:TYPED_GRAPH|x.Contents=Contents),type?,individual) = NULLr;
	| Contents' = Contents || {node?, (mu a:ISA_COMPONENT |
	|	GetTerminal(a,1)=node? /\ GetTerminal(a,2)=type?) };
	-------------------------------------------------------------------------- */
int TypedGraph::addNode(NodeComponent& node, ID_type type)
  {
  Component0 &p = (*this)[type]; //may throw
  //if (!(p.getAttr("individual")==p.endAttr())) return -2;
  int ret =node.Id = getNextID();

  if (node.getName()=="?") {
    char buf[MAX_NAME];
    sprintf(buf,"%s-%lu",p.getName().c_str(),node.Id);
    node.setName(buf);
    }

  Contents.insert(contents_type::value_type(node.Id,Ref2(node)));

  ID_type typeID = 0;

  try {
    if (type!=getNodeType()) { // Nodes are automatically subtypes of the prototype Node without an actual isa arc (efficiency hack)
      IsaComponent typeArc(makeIsaRelation(node.getID(),type));
      typeID = typeArc.getID();
      verify(typeArc,0);
      }
    verify((*this)[type],0);
    verify(node,0);
    }
  catch(...) {ret = -5;}

  //if the insertion failed, we need to remove the garbage we've added.
  if (ret < 0) {
    error(0,'E',"Verfication failed; invalid node insertion undone");
    if (typeID) Contents.erase(typeID);
    Contents.erase(node.getID());
    }
  return ret;
  }

  /*	---ADD_ARC----------------------------------------------------------------
	| Delta TYPED_GRAPH;
	| arc?: ARC_COMPONENT;
	| type?: ARC_COMPONENT
	|---------------
	| TYPED_GRAPH';
	| type? in Contents; % redundant
	| not(arc? isa ISA);
	| % not(arc? in Level1Objects);
	| getAttr((mu x:TYPED_GRAPH|x.Contents=Contents),type?,individual) = NULLr;
	| Contents' = Contents || {arc?, (mu a:ISA_COMPONENT |
	|	GetTerminal(a,1)=arc? /\ GetTerminal(a,2)=type?)};
	-------------------------------------------------------------------------- */
//!!!!!!!!!!!!!!addArc and addNode look almost identical....
int TypedGraph::addArc(ArcComponent& arc, ID_type type)
  {
  //some inital checks...
  Component0 &p = (*this)[type]; //may throw
  //if (!(p.getAttr("individual")==p.endAttr())) return -2;
  int ret = arc.Id = getNextID();

  if (arc.getName()=="?") {
    char buf[MAX_NAME];
    sprintf(buf,"%s-%lu",p.getName().c_str(),arc.Id);
    arc.setName(buf);
    }

  Contents.insert(contents_type::value_type(arc.Id,Ref2(arc)));

  ID_type typeID = 0;

  try  {
    if (type!=getArcType()) { // Nodes are automatically subtypes of the prototype Node without an actual isa arc (efficiency hack)
      //create the necessary isa arc
      IsaComponent typeArc(makeIsaRelation(arc.getID(),type));
      typeID = typeArc.getID();
      verify(typeArc,0);
      }

    verify((*this)[type],0);
    verify(arc,0);
    }
  catch(...) {ret = -5;}

  //if the insertion failed, we need to remove the garbage we've added.
  if (ret < 0) {
    error(0,'E',"Arc insertion failed; invalid node insertion undone");
    if (typeID) Contents.erase(typeID);
    Contents.erase(arc.Id);
    }

  return ret;
  }

long TypedGraph::redirectArcTerminal(ID_type arc, unsigned int index, ID_type target,
			Terminal::DIRECTION* dir, unsigned long flags)
  {
  long ret = 0;
  //some inital checks...
  try {if (target) Component0 &p = (*this)[target];}
  catch(...) {
    error(0,'E',"TypedGraph::redirectArcTerminal: bad target parameter");
    return -8;
    }

  ArcComponent* a = NULL;
  try {
    Component0 &c = (*this)[arc]; //may throw
    a = dynamic_cast(&c);
    }
  catch(...) {
    error(0,'E',"TypedGraph::redirectArcTerminal: bad arc parameter");
    return -7;
    }

  if (!a) {
    error(0,'E',"TypedGraph::redirectArcTerminal: parameter ID_type arc is not an arc");
    return -6;
    }

  //if (!(p.getAttr("individual")==p.endAttr())) return -2;

  ID_type oldID = a->getTerminalID(index);
  ret = oldID;
  Terminal::DIRECTION oldDir = a->getTerminalDir(index);

  try  {
    a->putAnchor(index,target,dir?*dir:oldDir);
    verify(*a,flags);
    if (target) notifyDependents(target);
    if (oldID) notifyDependents(oldID);
    }
  catch(...) {ret = -5;}

  //if the mod failed, we need to return to the old state.
  if (ret < 0) {
    if (!flags&Validator::silent) error(0,'E',"Arc redirection failed; undone");
    if (oldID) a->putAnchor(index,oldID,oldDir);
    }

  return ret;
  }


int TypedGraph::setComponentType(ID_type c, ID_type type)
  {
  if (ancestorof(c,type)) {
    error(0,'E',"Can't create a circular chain of isa arcs");
    return -11;
    }
  int ret = 0;
  ID_type typeID = 0;
  int removeFromC = 0; //used to undo a failed operation
  try {
    //create the necessary isa arc
    IsaComponent typeArc = makeIsaRelation(c,type);
    ret = typeID = typeArc.getID();

    //arcs only: check conformance of the child terminals up to its arity,
    //then expand its arity as necessary
    ArcComponent* ac = dynamic_cast(&(*this)[c]);
    if (ac) {
      ArcComponent* atype = dynamic_cast(&(*this)[type]);
      if (!atype) {
        if (c!=getNodeType() && c!=getArcType()) { //exception: top of the type hierarchy
          error(0,'E',"Can't subtype an arc from a non-arc");
          ret = -6;
          }
        }
      else {
        //check conformance
        //++++++++++++++ this doesn't account for directions!!!!!!!!!!!!!!!!!!!!!
        int checkSize = min(atype->getTerminals()->size(),ac->getTerminals()->size());
	for (Arc0::terminals_type::size_type i = 0; igetTerminalID(i)&&atype->getTerminalID(i)&&(atype->getTerminalID(i))!=_top.getID())?
			isa(ac->getTerminalID(i),atype->getTerminalID(i)):true,true);
	  }
        //expand child arc if necessary
        for (int j=ac->getTerminals()->size(); jgetTerminals()->size(); j++) {
          ac->getTerminals()->push_back((*atype->getTerminals())[j]);
          removeFromC++;
          }
        }
      }

    if (ret >= 0) {
      verify((*this)[c],0);
      verify((*this)[type],0);
      verify(typeArc,0);
      }
    }
  catch(...) {ret = -5;}

  //if the insertion failed, we need to remove the garbage we've added.
  if (ret < 0) {
    error(0,'W',"isa arc insertion failed; invalid isa arc insertion undone");
    if (typeID) Contents.erase(typeID);
    //remove any added arc terminals form the child
    if (removeFromC) {
      ArcComponent* ac = dynamic_cast(&(*this)[c]); //guarenteed to be try if removeFromC > 0
      for (int i=removeFromC; i>0; i--) {
        ac->getTerminals()->pop_back();
        }
      }
    }

  return ret;
  }

IsaComponent TypedGraph::makeIsaRelation(ID_type c, ID_type type) //protected version, don't do checks: may throw
  {
  //create the necessary isa arc
  IsaComponent typeArc("isa",(*this)[c].getLevel(),vector());
  typeArc.putAnchor(0,c,Terminal::FROM);
  typeArc.putAnchor(1,type,Terminal::TO);
  typeArc.Id = getNextID();

  //make up a name
  char buf[MAX_NAME];
  sprintf(buf,"isa-%lu",typeArc.Id);
  typeArc.setName(buf);

  Contents.insert(contents_type::value_type(typeArc.Id,Ref2(typeArc)));
  return typeArc;
  }

int TypedGraph::remove(ID_type id)
  {
  int ret = 0;
  contents_type::iterator i = Contents.find(id);
  if (i!=Contents.end()) {
    //unhook this item form all arcs
    bool sideEffectRemoved = true;
    while (sideEffectRemoved) { //this loop is here to allow restarts after we did a side-effect remove (otherwise be may get a corrupt iterator)
      sideEffectRemoved = false;
      for (contents_type::iterator c=Contents.begin(); c!=Contents.end(); c++) {
        ArcComponent* a = dynamic_cast(&(*(*c).second));
        if (a) {
          int index = a->findAnchor(id);
          if (index>=0) {
            if (redirectArcTerminal(a->getID(),index,0)<0) { //arc won't verify, so remove it
              if (remove(a->getID())) ret = -2;
              else {sideEffectRemoved = true; break;}
              }
            }
          }
        }
      }

    //do the actual removal
    if (!ret) {
      ArcComponent* a = dynamic_cast(&(*(*i).second));
      if (a) { //arc case
        Arc0::terminals_type anchors(*a->getTerminals());
        Contents.erase(i);
        for (Arc0::TerminalIterator j(anchors.begin()); j!=anchors.end(); j++) {
          if ((*j).getAnchorID()) notifyDependents((*j).getAnchorID());
          }
        }
      else //node case
        Contents.erase(i);
      }
    }
  else ret = -1;
  return ret;
  }

ostream& TypedGraph::printOn(ostream& out) const
  {
  //header data
  Lexer::writeUnsigned(out,NextID);
  Lexer::writeDelim(out);
  out << '\n';
  //body data
  for (contents_type::const_iterator i(Contents.begin()); i!=Contents.end(); i++) {
    if ((*i).first > LastFundamentalObject) { //don't save the "fundamental" objects
      Lexer::writeDelim(out,'(');
      Lexer::writeQuotedString(out,typeid(*(*i).second).name());
      Lexer::writeDelim(out);
      out << *(*i).second;
      Lexer::writeDelim(out,')');
      out << '\n';
      }
    }
  return out;
  }

void TypedGraph::flush()
  {
  bool erased = true;
  while (erased) {
    erased = false;
    for (contents_type::iterator i(Contents.begin()); i!=Contents.end(); i++) {
      if ((*i).first > LastFundamentalObject) { //don't delete the "fundamental" objects
        Contents.erase(i);
        erased = true;
        break;
        }
      }
    }

  _top.clearObservers();
  _node.clearObservers();
  _arc.clearObservers();
  _isa.clearObservers();
  _nodeIsa.clearObservers();
  _arcIsa.clearObservers();
  _isaIsa.clearObservers();

  NextID = LastFundamentalObject+1;
  }

istream& TypedGraph::readFrom(istream& in)
  {
  Flags &= ~checking;

  try {
    flush();

    //header data
    unsigned long temp;
    Lexer::readUnsigned(in,temp); NextID=temp;
    Lexer::readDelim(in);

    //body data
    while (!Lexer::readDelim(in,'(')) {
      string t;
      Lexer::readQuotedString(in,t);
      Lexer::readDelim(in);
      Component0* c = GraphsTypeLibrary->makeCopy(t);
      if (c) {
        in >> *c;
        Contents.insert(contents_type::value_type(c->Id,Ref2(c,true)));
        }
      else error(0,'E',"Can't find %s in GraphsTypeLibrary",t.c_str());
      Lexer::readDelim(in,')');
      }
    }

  catch(...) {}

  Flags |= checking;

  return in;
  }

Component0& TypedGraph::operator[](ID_type id) const
  {
  contents_type::const_iterator i = Contents.find(id);
  if (i == ((const contents_type)Contents).end())
    throw BadIDException("TypedGraph::opeator[ID]: ID does not exist");
  if (!(*i).second)
    throw BadIDException("TypedGraph::opeator[ID]: ID has no value");
  return *(*i).second; //Contents[id];
  }

bool TypedGraph::contains(ID_type id) const
  {
  contents_type::const_iterator i = Contents.find(id);
  bool ret = (!(i == ((const contents_type)Contents).end())) && (*i).second;
  return ret;
  }

//helper function -- not strictly necessary
long TypedGraph::makeArc(string& name, unsigned int level, ID_type type, vector* terminals)
  {
  int ret;
  vector def(1);
  Component0& p = (*this)[type];
  if (dynamic_cast(&p)) {
    IsaComponent ident(name,level,terminals?*terminals:def);
    ret = addArc(ident,type);
    }
  else {
    ArcComponent ident(name,level,terminals?*terminals:def);
    ret = addArc(ident,type);
    }
  //ident.putAnchor(0,0,Terminal::BIDIRECT);
  return ret;
  }

//helper function -- not strictly necessary
long TypedGraph::makeDirArc2(string& name, unsigned int level, ID_type type, ID_type from, ID_type to)
  {
  ArcComponent ident(name,level,vector());
  ident.putAnchor(0,from,Terminal::FROM);
  ident.putAnchor(1,to,Terminal::TO);
  int ret = addArc(ident,type);
  return ret;
  }

//helper function -- not strictly necessary
long TypedGraph::makeNode(string& name, unsigned int level, ID_type type)
  {
  NodeComponent ident(name,level);
  int ret = addNode(ident,type);
  return ret;
  }

/*******************************************************************************
****************************** FirstOrderTypedGraph ****************************
*******************************************************************************/
/*
  Z spec,
  declaration */

FirstOrderTypedGraph::FirstOrderTypedGraph() : TypedGraph()
  {
  _arc.addConstraint("NoArcBtwnArcs");
  }

/*


*/