#include	"global.h"
#include	"list.h"
#include	"nodes.h"
#include	"conf.h"

// The closure() member function adds the configuration implied by the
// current node and rule head to closureSet.  It returns 1 if it is a
// new configuration, and 0 if it has been encountered previously.

int ParNode::closure(ParRule *head, LConfList *closureSet)
{
	Conf *thisConf;
	LConf *thisLConf = 0;

	thisConf = Conf::confs.find(this);
	if (thisConf == 0)
		thisConf = new Conf(head, this);

	thisLConf = LConf::cogs.find(thisConf);
	if (thisLConf == 0)
		thisLConf = new LConf(thisConf);

	if (closureSet->find(thisLConf->conf) == 0) {
		closureSet->append(thisLConf);
		return 1;
	}
	return 0;
}

// For non-terminals, the current configuration is noted, and if it has
// not been encountered previously, the configurations anticipated by
// its constituents are also included.

void ParNonTermNode::findClosure(ParRule *head, LConfList *closureSet)
{
	if (closure(head, closureSet) && nonterm()->isNonTerm())
	    nonterm()->rhs()->findClosure(nonterm(), closureSet);
}

// The current configuration is merely noted for the end of rule
// sequences.  No further additions are required since no other
// configurations are implied.

void ParEndNode::findClosure(ParRule *head, LConfList *closureSet)
{
	closure(head, closureSet);
}

// The closure for an Inherited attribute marker is similar to that of
// non-terminals since they are implemented as such.

void ParActionNode::findClosure(ParRule *head, LConfList *closureSet)
{
	if (closure(head, closureSet))
	    nontermRule()->rhs()->findClosure(nontermRule(), closureSet);
}

// The closure for a selection node is computed by propagating the
// request down the individual rule bodies.

void ParSelectNode::findClosure(ParRule *head, LConfList *closure)
{
	alt1()->findClosure(head, closure);
	alt2()->findClosure(head, closure);
}

// The member function findMoves() enumerates symbols that are
// anticipated from a the current state, and constructs destination
// configuration sets if they don't already exist.  It is recursively
// invoked from new configuration sets.

void ConfSet::findMoves()
{
	list<ParRule *> triggerSet;
	listIter<LConf *> forEachLConf(closure);
	LConf **item;

// Symbols involved in shift transition are first accumulated by
// traversing through all configurations.

	while (item = forEachLConf()) {
	    ParNode *n = (*item)->conf->dot;
	    if (n->next() && !triggerSet.find(n->nontermRule()))
		triggerSet.append(n->nontermRule());
	}

	listIter<ParRule *> forEachRule(&triggerSet);
	ParRule **rule;
	ConfSet *newConfSet;
	LConfList *destClosure = new LConfList();

	while (rule = forEachRule()) {
	    listIter<LConf *> forEachLConf(closure);
	    LConf **cg;

// For each symbol involved in a transition, the closure for the new
// configuration is found together with the corresponding configuration
// set.

	    while (cg = forEachLConf()) {
		ParNode *n = (*cg)->conf->dot;
		if (n->next() && n->nontermRule() == *rule)
		    n->next()->findClosure((*cg)->conf->rule, destClosure);
	    }

// If the computed closure may be found in a configuration set, it must
// have existed and need not be created or re-visited.

	    newConfSet = confSets.find(destClosure);
	    if (newConfSet)
	        delete destClosure;
	    else {

// Alternatively, a new configuration set with the new closure set is
// created, and findMoves() is invoked recursively.

	        newConfSet = new ConfSet(destClosure);
	        newConfSet->findMoves();
	    }
	    moves.append(new Move(*rule, newConfSet));
	    destClosure = new LConfList();
	}
	delete destClosure;
}

// The following find member functions searches for a item in a list.

ConfSet *MoveList::findDest(ParRule *target)
{
	node<Move *> *p = (node<Move *> *) head;

	while (p) {
		if (target == p->item->trigger)
			return(p->item->dest);
		p = (node<Move *> *) p->next;
	}
	return 0;
}

Conf *ConfList::find(ParNode *d)
{
	node<Conf *> *p = (node<Conf *> *) head;

	while (p) {
		if (d == p->item->dot)
			return(p->item);
		p = (node<Conf *> *) p->next;
	}
	return 0;
}

LConf *LConfList::find(Conf *c)
{
	node<LConf *> *p = (node<LConf *> *) head;

	while (p) {
		if (c == p->item->conf)
			return(p->item);
		p = (node<LConf *> *) p->next;
	}
	return 0;
}

void LConfList::replicate()
{
	node<LConf *> *p = (node<LConf *> *) head;

	while (p) {
		p->item = new LConf(p->item->conf);
		p = (node<LConf *> *) p->next;
	}
}

ConfSet *ConfSetList::find(LConfList *c)
{
	node<ConfSet *> *p = (node<ConfSet *> *) head;

	while (p) {
		if (c->contains(*(p->item->closure)) &&
		    p->item->closure->contains(*c))
			return(p->item);
		p = (node<ConfSet *> *) p->next;
	}
	return 0;
}

// The following show() member functions are for reporting purposes.

void Conf::show(FILE *fp)
{
	fprintf(fp, "%s ::=", rule->name());
	ParNode *prod = rule->rhs()->leadsTo(dot);
	prod->show(dot, fp);
}

void LConf::show(FILE *fp)
{
	conf->show(fp);
	fprintf(fp, ",");
	listIter<ParRule *> forEachRule(&lookAhead);
	ParRule **r;
	while (r = forEachRule())
		fprintf(fp, " %s", (*r)->name());
	fprintf(fp, "\n");
}

void ConfSet::show(FILE *fp)
{
	printf("ConfSet %d:\n", id());
	listIter<LConf *> forEach(closure);
	LConf **item;

	// print out lconfs
	while (item = forEach())
		(*item)->show(fp);

	// print out moves
	listIter<Move *> forEachMove(&moves);
	Move **m;
	while (m = forEachMove())
		fprintf(fp, "\t%s -> %d\n", (*m)->trigger->name(),
				  (*m)->dest->id());

	fprintf(fp, "\n");
}

// The append() member function for LConfList is redefined so that
// insertions for LConf items are ordered by their reduceOrder.  This
// allows for correct reduce-reduce conflict resolution.

void LConfList::append(const LConf *i)
{
	node<const LConf *> *n = new node<const LConf *>(i);

	if (!len) {
		len = 1;
		head = tail = n;
		return;
	}
	node<LConf *> *prev = 0, *h = (node<LConf *> *) head;
	len++;
	while (h)
	    if (i->conf->dot->reduceOrder() <
		h->item->conf->dot->reduceOrder()) {
		n->next = h;
		if (prev)
		    prev->next = n;      // middle of list
		else
		    head = n;	         // first in list
		return;
	    } else {
		prev = h;
		h = (node<LConf *> *) h->next;
	    }
	prev->next = n;                  // last
	tail = n;
}

ConfList Conf::confs;
LConfList LConf::cogs;
ConfSetList ConfSet::confSets;
int ConfSet::NextId = 1;