#Copyright Massachusetts Institute of technology, 1998.
#Written by Eric Prud'hommeaux for the World Wide Web Consortium

# $Id: RdfDB.pm,v 1.210 2007-08-14 21:46:20 eric Exp $

use strict;
require Exporter;
#require AutoLoader;

use W3C::Rdf::EmitterInterface;

$W3C::Rdf::RdfDB::REVISION = '$Id: RdfDB.pm,v 1.210 2007-08-14 21:46:20 eric Exp $ ';

package W3C::Rdf::RdfDB;
use vars qw($VERSION $DSLI @ISA @TODO @EXPORT_OK);
@ISA = qw(Exporter); # AutoLoader);
@TODO = qw();
@EXPORT_OK = qw();
$VERSION = 0.95;
$DSLI = 'adpO';

use vars qw($VERSION $DSLI @ISA @EXPORT @EXPORT_OK);
use W3C::Rdf::Atoms qw($ATTRIB_GroundFact $ATTRIB_FactRef $ATTRIB_Reification $ATTRIB_RuleRef $ATTRIB_Inference);

# Common ancestor for all RdfDB exceptions.
package W3C::Rdf::RdfDBException;
use W3C::XML::SAXException;
@W3C::Rdf::RdfDBException::ISA = ('W3C::Util::Exception');

# Simple printing error handler.
# This default error handler will be created if none is supplied to the RdfDB
# constructor.
package W3C::Rdf::RdfDbErrorHandler;
use W3C::Util::Exception;
use W3C::XML::ErrorHandlerImpl;
use vars qw(@ISA);
@ISA = qw(W3C::XML::ErrorHandlerImpl);

sub warning {
    my ($self, $exception) = @_;
    $DB::single = 1;
    print 'warning: '.$exception->getMessage."\n";
}

sub error {
    my ($self, $exception) = @_;
    $DB::single = 1;
    &throw($exception);
    # warn 'error: '.$exception->getMessage."\n";
}

package W3C::Rdf::RdfDB::Serializer::ExceptionHandler;
use W3C::Util::Object;
@W3C::Rdf::RdfDB::Serializer::ExceptionHandler::ISA = ('W3C::Util::NamedParmObject');
use W3C::Util::Exception;

sub error {
    my ($self, $serializer, $ex) = @_;
    &throw($ex);
}

package W3C::Rdf::RdfDB::Serializer::ExceptionIgnorer;
@W3C::Rdf::RdfDB::Serializer::ExceptionIgnorer::ISA = ('W3C::Rdf::RdfDB::Serializer::ExceptionHandler');
use W3C::Util::Exception;
sub error {
    my ($self, $serializer, $ex) = @_;
    $serializer->startElement('http://dev.w3.org/cvsweb/~checkout~/perl/modules/W3C/Rdf/RdfDB.pm#serializationError', {});
    $serializer->characters($ex->toString);
    $serializer->endElement('http://dev.w3.org/cvsweb/~checkout~/perl/modules/W3C/Rdf/RdfDB.pm#serializationError');
    $serializer->finishElement;
}

package W3C::Rdf::RdfDB::SerializerIterator;
use W3C::Util::Exception;
sub new {
    my ($proto, $algae2, %flags) = @_;
    my $class = ref($proto) || $proto;
    my $self = {ALGAE2 => $algae2, %flags};
    bless ($self, $class);
    $self->{-exceptionHandler} ||= new W3C::Rdf::RdfDB::Serializer::ExceptionHandler;
    return $self;
}

sub iterate {
    my ($self, $serializer) = @_;
    $self->{-serializer} = $serializer;

    # Pick List bits out whimsically.
    if ($serializer->collection()) {
	my $lists = $self->{-RdfDB}->listsFrom(undef, $self->{-view});
	$self->{-RdfDB}->_pruneViewCollectionArcs($lists, $self->{-view});
    }

    if ($serializer->nest()) {
	$self->makeNodeIndexes();
#	print join("\n", map {$_->toString(-brief=>1)} @{$self->{-view}}), "\n";
	my @toDo = sort {$a->toString <=> $b->toString} map {(values %$_)[0]->getSubject()} values %{$self->{BYSUBJECT}}; # !!! works with $a->toString cmp $b->toString
#	print ">>>>>>>>>>>>>>>>>>>>\n", (map {sprintf("%s\n", $_->toString)} @toDo);
	@toDo =  sort {$self->outerMostFirst($a, $b, {})} @toDo;
#	print "-->\n", (map {sprintf("%s\n", $_->toString)} @toDo), "<<<<<<<<<<<<<<<<<<<<\n";
	# sort the subjects to iterate according to nesting convenience
	# Debugging note: reverse pessimizes this.
	# @toDo = sort {&main::SubjectSorter((values %{$self->{BYSUBJECT}{$a}})[0], (values %{$self->{BYSUBJECT}{$b}})[0])} keys %{$self->{BYSUBJECT}};
	# print join ("\n", map {(values %{$self->{BYSUBJECT}{$_}})[0]->getSubject->toString} @toDo)."\n";

	use W3C::Util::Enumerator;
	$self->{-serializer}->startDocument();
	for ($self->{ENUMERATOR} = new W3C::Util::ArrayEnumerator(@toDo); $self->{ENUMERATOR}->hasMoreElements;) {
	    my $subject = $self->{ENUMERATOR}->getNextElement;
	    eval {
# 		my $refsToSubject = $self->bySubject($subject);
# 		$self->serializeSubject($subject, $self, @$refsToSubject > 0);
		my $refsToSubject = $self->byObject($subject);
		$self->serializeSubject($subject, $self, @$refsToSubject > 0);
	    }; if ($@) {
		my $ex;
		if ($ex = &catch('W3C::Util::Exception')) {
		    $self->{-exceptionHandler}->error($self->{-serializer}, $ex);
		} else {
		    $self->{-exceptionHandler}->error($self->{-serializer}, new W3C::Util::PerlException);
		}
	    }
	}
	$self->{-serializer}->endDocument();
    } else {
	$self->{-serializer}->startDocument();
	$self->{-serializer}->serializeStatements($self->{-view}, undef);
	$self->{-serializer}->endDocument();
    }
}

sub makeNodeIndexes {
    my ($self) = @_;
    $self->{BYSUBJECT} = {};
    $self->{BYOBJECT} = {};

#    $self->{STATEMENT_ATOMS} = {};
    foreach my $statement (@{$self->{-view}}) {
#	    my $predicte = $statement->getPredicate;
	my $subject = $statement->getSubject;

#	    handy for debugging
#	    $self->{STATEMENT_ATOMS}{$predicate} = $predicate;
#	    $self->{STATEMENT_ATOMS}{$subject} = $subject;

	# Add reificiation attributes. @@@ this is in flux.
	if ($self->{-serializeReificationsFoo}) {
	    if ($self->{-ignoreReifications}) {
	    } elsif ($self->{-ignoreAnonymousReifications}) {
		if (!$statement->getReifiedFoo->isa('W3C::Rdf::BNode')) {
		    $subject .= '-in-'.$statement->getReifiedFoo;
		}
	    } else {
		$subject .= '-in-'.$statement->getReifiedFoo;
	    }
	}
	$self->{BYSUBJECT}{$subject}{$statement} = $statement;
	$self->{BYNODE}{$subject} = $subject;
	my $objects = $statement->isa('W3C::Rdf::ListStatement') ? $statement->getObjects : [$statement->getObject];
	foreach my $object (@$objects) {
#		$self->{STATEMENT_ATOMS}{$object} = $object;
	    $self->{BYOBJECT}{$object}{$statement} = $statement;
	    $self->{BYNODE}{$object} = $object;
	}
    }
}

sub _dumpLists { # static
    my ($lists, $width, %flags) = @_;
    my @elements;
    my $good = 1;
    foreach my $key (keys %$lists) {
	my $root = $lists->{$key};
	my ($listMembers, $listNodes, $good2, $rootObj, $first) = @$root;
	$good &= $good2;
	my @nodes = ($rootObj, @$listNodes);
	for (my $i = 0; $i < @nodes; $i++) {
	    push (@elements, &_shortNode($nodes[$i], $width, %flags)."\->".&_shortNode($listMembers->[$i], $width, %flags));
	}
    }
    return '(', join (', ', @elements), ")\n";
}

sub _shortNode { # static
    my ($node, $width, %flags) = @_;
    my $str = $node->toString(%flags);
    $width |= 10;
    return substr($str, length($str)-$width, $width);
}

sub outerMostFirst {
    my ($self, $left, $right, $recurseList, $pad) = @_;
    if ($left == $right) {
	return 0;
    }
    if (exists $recurseList->{$left}) {
	return exists $recurseList->{$right} ? 0 : -1;
    }
    if (exists $recurseList->{$right}) {
	return 1;
    }

    my $ret = undef;
    if (($left->isa('W3C::Rdf::BNode') && 
	 $right->isa('W3C::Rdf::BNode')) || 
	($left->isa('W3C::Rdf::Uri') && 
	 $right->isa('W3C::Rdf::Uri'))) {
	# Sort by number of referrers.
	if ($self->{BYOBJECT}{$right} && %{$self->{BYOBJECT}{$right}}) {
	    if ($self->{BYOBJECT}{$left} && %{$self->{BYOBJECT}{$left}}) {
		my $cmpReferrers = values %{$self->{BYOBJECT}{$left}} <=> values %{$self->{BYOBJECT}{$right}};
		if ($cmpReferrers != 0) {
		    return $cmpReferrers;
		}
	    } else {
		return -1;
	    }
	} elsif ($self->{BYOBJECT}{$left} && %{$self->{BYOBJECT}{$left}}) {
	    return 1;
	}

	my $lRecurseList = {%$recurseList, $left => 1, $right => 1};

	my @lStatements = map {[$_, undef, -1]} values %{$self->{BYSUBJECT}{$left}};
	my @rStatements = map {[$_, undef, +1]} values %{$self->{BYSUBJECT}{$right}};
	my @sorted = sort {$a->[0]->getPredicate()->getUri() cmp $b->[0]->getPredicate()->getUri() || 
			       $self->outerMostFirst($a->[0]->getObject, $b->[0]->getObject, $lRecurseList, "$pad  ") || 
			       ($a->[1] = $b->[1] = 0)} @lStatements, @rStatements;
	for (my $i = 0; $i < @sorted-1; $i++) {
	    if (!defined $sorted[$i]->[1]) {
		return $sorted[$i]->[2];
	    }
	}

	my @lStatements = map {[$_, undef, -1]} values %{$self->{BYOBJECT}{$left}};
	my @rStatements = map {[$_, undef, +1]} values %{$self->{BYOBJECT}{$right}};
	my @sorted = sort {$a->[0]->getPredicate()->getUri() cmp $b->[0]->getPredicate()->getUri() || 
			       $self->outerMostFirst($a->[0]->getSubject, $b->[0]->getSubject, $lRecurseList, "$pad  ") || 
			       ($a->[1] = $b->[1] = 0);} @lStatements, @rStatements;
	for (my $i = 0; $i < @sorted-1; $i++) {
	    if (!defined $sorted[$i]->[1]) {
		return $sorted[$i]->[2];
	    }
	}

	if ($left->isa('W3C::Rdf::BNode')) {
	    if (!%$recurseList) {
		if ($main::DIAGNOSTIC_MODE) {
		    my $lStr = $left->toString;
		    my $rStr = $right->toString;
		    my $exStr = join("\n", map {(%{$self->{BYSUBJECT}{$_}} ? (values %{$self->{BYSUBJECT}{$_}})[0]->getSubject : (values %{$self->{BYOBJECT}{$_}})[0]->getObject)->toString} keys %$recurseList);
		    my $dbStr = join("\n", map {map {$_->toString(-brief => 1)} values %{$self->{BYSUBJECT}{$_}}} keys %{$self->{BYSUBJECT}});
		    &throw(new W3C::Util::Exception(-message => "don't know how to sort $lStr and $rStr excluding:\n$exStr\nin:\n$dbStr"));
		}
		return 0;
	    }
	}
    }

    return W3C::Rdf::ResultSet::orderTerm($left, $right, $self->{ALGAE2}, undef, 1, 1);
}

sub serializeSubject {
    my ($self, $subject, $iterator, $forceAbout) = @_;
    my $withThisSubject = [sort {$a->getPredicate()->getUri() cmp $b->getPredicate()->getUri() || 
				     $self->outerMostFirst($a->getObject, $b->getObject, {}, '')} 
			   values %{$self->{BYSUBJECT}{$subject}}];
    $self->{-serializer}->serializeStatements($withThisSubject, $iterator, $forceAbout);
}

sub bySubject {
    my ($self, $subject) = @_;
    return exists $self->{BYSUBJECT}{$subject} ? [values %{$self->{BYSUBJECT}{$subject}}] : [];
}

sub byObject {
    my ($self, $object) = @_;
    return exists $self->{BYOBJECT}{$object} ? [values %{$self->{BYOBJECT}{$object}}] : [];
}

sub remove {
    my ($self, $statement) = @_;
    my $subject = $statement->getSubject;
    my $object = $statement->getObject;
    if (!exists $self->{BYSUBJECT}{$subject} || 
	!exists $self->{BYSUBJECT}{$subject}{$statement} || 
	!exists $self->{BYOBJECT}{$object} || 
	!exists $self->{BYOBJECT}{$object}{$statement}) {
	&throw(new W3C::Util::ProgramFlowException());
    }
    delete $self->{BYSUBJECT}{$subject}{$statement};
    if (!%{$self->{BYSUBJECT}{$subject}}) {
	delete $self->{BYSUBJECT}{$subject};
    }
    delete $self->{BYOBJECT}{$object}{$statement};
    if (!%{$self->{BYOBJECT}{$object}}) {
	delete $self->{BYOBJECT}{$object};
    }
}

sub deleteWithSubject {
    my ($self, $subject) = @_;
    return $self->{ENUMERATOR}->deleteFromRemaining($subject)
}

sub handleNestedStatements {
    my ($self, $subject, $forceAbout) = @_;
    if (my $nestedSubject = $self->{ENUMERATOR}->deleteFromRemaining($subject)) {
	# we haven't already nested that element
	$self->serializeSubject($nestedSubject, $self, $forceAbout);
	return 1;
    }
    return 0;
}


package W3C::Rdf::NestingSorter;
sub new {
    my ($proto, $rdfDB, $algae2) = @_;
    my $class = ref($proto) || $proto;
    my $self = {Statements => []};
    bless ($self, $class);

    my $iterator = $rdfDB->makeSerializerIterator(undef, $algae2);
    $iterator->iterate($self);

    return $self;
}
sub getStatementList {
    my ($self) = @_;
    $self->{Statements};
}
sub nest {
    return 1;
}
sub collection {
    return 0;
}
sub startDocument {}
sub serializeStatements {
    my ($self, $withThisSubject, $iterator, $forceAbout) = @_;
    my $subjectNode = $withThisSubject->[0]->getSubject;
    for (my $iStatement = 0; $iStatement < @$withThisSubject; $iStatement++) {
	my $statement = $withThisSubject->[$iStatement];
	my $object = $statement->getObject();
	push (@{$self->{Statements}}, $statement);
	if ($object->isa('W3C::Rdf::BNode')) {
	    $iterator->handleNestedStatements($object, 1);
	}
    }
}
sub endDocument {}

package W3C::Rdf::RdfDB;
@W3C::Rdf::RdfDB::ISA = qw(W3C::Util::NamedParmObject);
use W3C::Util::Exception;
use W3C::Rdf::Atoms qw($RDF_SCHEMA_URI);
use W3C::Util::ArrayUtils qw(&DecorateArray);

#####
# per-object data

#####
# new - prepare an empty W3C::Rdf::RdfDB

sub new {
    my ($proto, @parms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new(@parms);

    if (!$self->{-atomDictionary}) {
	&throw(new W3C::Util::Exception(-message => "$class must have an -atomDictionary"));
    }
    if (!UNIVERSAL::can($self->{-atomDictionary}, 'getUriLink')) {
	&throw(new W3C::Util::Exception(-message => "$class must have an -atomDictionary (not $self->{-atomDictionary})"));
    }

    $self->{OBSERVERS} = [];
    $self->{RDF_SCHEMA_URI} = $RDF_SCHEMA_URI;
    $self->{-errorHandler} ||= new W3C::Rdf::RdfDbErrorHandler();
    $self->clear;

    # keep some handy constants around
    my $consts = {
	-rdfType => 'http://www.w3.org/1999/02/22-rdf-syntax-ns#type', 
	-rdfsSubClassOf => 'http://www.w3.org/2000/01/rdf-schema#subClassOf', 
	-rdfsSubPropertyOf => 'http://www.w3.org/2000/01/rdf-schema#subPropertyOf', 
	-rdfsDomain => 'http://www.w3.org/2000/01/rdf-schema#domain', 
	-rdfsRange => 'http://www.w3.org/2000/01/rdf-schema#range', 
	-subCategoryOf => 'http://www.w3.org/2002/01/bookmark#subCategoryOf', 
	-hasCategory => 'http://www.w3.org/2002/01/bookmark#hasCategory', 
	-rdfList => 'http://www.w3.org/1999/02/22-rdf-syntax-ns#List', 
	-rdfFirst => 'http://www.w3.org/1999/02/22-rdf-syntax-ns#first', 
	-rdfRest => 'http://www.w3.org/1999/02/22-rdf-syntax-ns#rest', 
	-rdfNil => 'http://www.w3.org/1999/02/22-rdf-syntax-ns#nil'};
    $self->{CONSTS} = {};
    foreach my $key (keys %$consts) {
        $self->{CONSTS}{$key} = $self->{-atomDictionary}->getUriLink($consts->{$key}, undef);
    }


    return $self;
}

sub disconnect {
    my ($self) = @_;
    # g'bye!
}

sub getStatementId {
    my ($self) = @_;
    return $self;
}

sub getAttributionId {
    my ($self, $attribution) = @_;
    return $attribution;
}

sub getAlgaeInterface {
    my ($self) = @_;
    return $self;
}

sub addForwardChainingRule {
    my ($self, $rule, $algaeInterface, $resultSet, $attribution) = @_;
    $self->compileRule($rule, $algaeInterface, $resultSet, $self->{FORWARD_CHAINING_RULES});
    $algaeInterface->tryRule(undef, undef, $rule->getBody, $rule, $resultSet, $self, undef, {}, {}, undef, $attribution);
}

sub addInterface {
    my ($self, $api, $impl, $algaeInterface, $resultSet, $attribution) = @_;
    $self->compileRule($api, $impl, $algaeInterface, $resultSet, $self->{INTERFACES_APItoImpl}, $attribution);
    $self->compileRule($impl, $api, $algaeInterface, $resultSet, $self->{INTERFACES_implToAPI}, $attribution);
    push (@{$self->{INTERFACES_list}}, [undef, undef, $api, $impl, $algaeInterface, $resultSet]);
}

sub compileRule {
    my ($self, $rule, $algaeInterface, $resultSet, $ruleGroup) = @_;
    my @previousTerms;
    my @followingTerms = ($rule->getBody->getCNF);
    while (my $bodyTerm = shift (@followingTerms)) {
	my $constCount = 0;
	my $constPositions = 0;
	my @constIndexes;
	for (my $iPostion = 0; $iPostion < $bodyTerm->arity; $iPostion++) {
	    my $piece = $bodyTerm->getSlot($iPostion);
	    if (!$piece->isa('W3C::Rdf::AlgaeCompileTree::Var')) {
		$constCount++;
		$constPositions |= (1 << $iPostion);
		push (@constIndexes, $piece->lookfor(undef, undef, undef));
	    }
	}

	# indexed first by the number of consts
	if (!exists $ruleGroup->{$constCount}) {
	    $ruleGroup->{$constCount} = {};
	}
	my $rulePointer = $ruleGroup->{$constCount};

	# then by the positions of the consts
	if (!exists $rulePointer->{$constPositions}) {
	    if (@constIndexes) {
		$rulePointer->{$constPositions} = {};
	    } else {
		$rulePointer->{$constPositions} = [];
	    }
	}
	my $rulePointer = $rulePointer->{$constPositions};

	# then be each const used
	for (my $iConstIndex = 0; $iConstIndex < @constIndexes; $iConstIndex++) {
	    my $constIndex = $constIndexes[$iConstIndex];
	    if (!exists $rulePointer->{$constIndex}) {
		if ($iConstIndex == @constIndexes - 1) {
		    $rulePointer->{$constIndex} = [];
		} else {
		    $rulePointer->{$constIndex} = {};
		}
	    }
	    $rulePointer = $rulePointer->{$constIndex};
	}

	# Some old code to build an optimized rule without the term we just
	# indexed. This assumes that there's no reason match it once we
	# triggered on it.

	## build a rule set with the remaining rules
	#my $querySet = new W3C::Rdf::Algae::SetQueryPiece(@previousTerms, undef, 0, 0);
	#foreach my $term (@previousTerms, @followingTerms) {
	#    $term->{PARTOFSPEACH} = $querySet->arity; # !!! cheater! decide what to do with semi-helpful indexes
	#    $querySet->addTerm($term);
	#}
	#push (@$rulePointer, [$bodyTerm, $querySet, $body, $head, $algaeInterface, $resultSet]);

	# In the absense of that, just use the body again.
	push (@$rulePointer, [$bodyTerm, $rule->getBody, $rule, $algaeInterface, $resultSet]);
	push (@previousTerms, $bodyTerm);
    }
}

sub clear {
    my ($self) = @_;
    $self->{TRIPLES} = [];
    $self->{PSO} = {};
    $self->{SOP} = {};
    $self->{OPS} = {};
    $self->{CURRENT_VIEW} = [];
    # DBG $self->{BY_CONTENTS} = {};
    $self->{FORWARD_CHAINING_RULES} = {};
    $self->{INTERFACES_APItoImpl} = {};
    $self->{INTERFACES_implToAPI} = {};
    $self->{INTERFACES_list} = [];
}

# Junk for CGIApp statement serializer -- NUKE
sub getCurrentView {
    my ($self) = @_;
    return $self->{CURRENT_VIEW};}
sub setCurrentView {
    my ($self, $view) = @_;
    $self->{CURRENT_VIEW} = $view;}
sub getRdfDB {
    my ($self, $view) = @_;
    my $ret = {%$self};
    bless ($ret, 'W3C::Rdf::RdfDB');

    if ($view) {
	$self->{CURRENT_VIEW} = $view;
    }
    return $ret;}


sub applyRules {
    my ($self, $reified, $trigger, $visited, $attribution) = @_;
    my $triples = [$trigger, $self->applyClosureRules($visited, $trigger, $attribution)];
    push (@{$self->{CURRENT_VIEW}}, @$reified);
    return $trigger;
}
sub addStatement999 ($$$$$$) {
    my ($self, $predicate, $subject, $object, $reification, $container, $attribution) = @_;
    if (!ref $predicate || !ref $subject || !ref $object) {
	&throw(new W3C::Util::Exception(-message => "bad triple ('$predicate', '$subject', '$object')"));
    }
    my $triple = $self->{-atomDictionary}->getStatement($predicate, $subject, $object, $reification, $attribution);
    my @reified = $self->maybeReify($triple, $reification, $attribution);
    my $triples = [$triple, $self->applyClosureRules($triple)];
    push (@{$self->{CURRENT_VIEW}}, $triple, @reified);
    return $triple;
}

sub applyClosureRules {
    my ($self, $visited, $trigger, $attribution) = @_;
    my @ret;
    my $cur = [$trigger->getPredicate, 
	       $trigger->getSubject, 
	       $trigger->getObject, 
	       $trigger->getReifiedAs, 
	       $trigger->getAttributionList];
    foreach my $constCount (reverse sort keys %{$self->{FORWARD_CHAINING_RULES}}) {
	my $rulesAtCount = $self->{FORWARD_CHAINING_RULES}{$constCount};
      POSITION_SET:
	foreach my $positionSet (keys %$rulesAtCount) {
	    # rule indexed by number of consts and positions of the consts
	    my $rulePointer = $rulesAtCount->{$positionSet};
	    # then by each const used
	    for (my $iPosition = 0; $iPosition < 5; $iPosition++) {
		if ($positionSet & (1 << $iPosition)) {
		    if (!($rulePointer = $rulePointer->{$cur->[$iPosition]})) {
			next POSITION_SET;
		    }
		}
	    }

	    # We have arrived at the sets of rules the assertion triggers.
	    foreach my $ruleSet (@$rulePointer) {
		# We match the first rule, now iteratively check the rest:
		my ($matched, $rest, $rule, $algaeInterface, $resultSet) =@$ruleSet;
		my $view = undef;

		# Create a temp DB with the trigger statement.
		my $tmpDB = $self->getRdfDB();
		$tmpDB->clear;
		$tmpDB->addTriple($trigger);
		#$tmpDB->toString; # reasonable way to check integrity
		# Get bindings into resultSet.
		$matched->evaluateQTermAndConstraints($resultSet, $tmpDB, undef);

		# Try the rest of the terms in this rule body.
		$algaeInterface->tryRule($cur, $matched, $rest, $rule, $resultSet, $self, $view, {}, $visited, $trigger, $attribution);
		$resultSet->clear;
	    }
	}
    }
    return ();
}

sub maybeReify ($$$$$) {
    my ($self, $triple, $reification, $attribution) = @_;
    my @all;
    push (@all, $self->addTriple($triple));
    push (@all, $self->reify($triple, $reification));
    return @all;
}

#####
# public triple manipulators

sub clearAttribution {
    my ($self, $attribution) = @_;
    foreach my $triple (@{$self->{TRIPLES}}) {
	my $al = $triple->getAttributionList;
	if ($al->hasAttribution($attribution)) {
	    my @a = grep {$_ != $attribution} $al->getAllDirect();
	    if (@a) {
		my $new = $self->{-atomDictionary}->getAttributionList(@a);
		$triple->setAttributionList($new);
	    } else {
		$self->removeTriple($triple);
	    }
	}
    }
    # $self->{NodesToRefresh}{$attribution} = $attribution; # whatever
}

sub addTriple {
    my ($self, $triple, $attribution) = @_;

    # do some sanity checks, at least while we are in the debugging stage
    # should move this into Statements::debugCheck
    my @errors;
    eval {
	if (!ref $triple) {push (@errors, "!ref $triple");}
	if (!$triple->isa('W3C::Rdf::Statement')) {push (@errors, "!$triple->isa('W3C::Rdf::Statement')");}
	if (!defined $triple->getPredicate || !$triple->getPredicate->isa('W3C::Rdf::Uri')) {
	    push (@errors, $self->makeAtomErrorString('predicate', $triple->getPredicate));}
	if (!defined $triple->getSubject || !($triple->getSubject->isa('W3C::Rdf::Uri') || 
					      $triple->getSubject->isa('W3C::Rdf::BNode'))) {
	    push (@errors, $self->makeAtomErrorString('subject', $triple->getSubject));}
	if (!defined $triple->getObject || !($triple->getObject->isa('W3C::Rdf::Uri') || 
					     $triple->getObject->isa('W3C::Rdf::BNode') || 
					     $triple->getObject->isa('W3C::Rdf::String'))) {
	    push (@errors, $self->makeAtomErrorString('object', $triple->getObject));}
	if (!defined $triple->getAttributionList || $triple->getAttributionList->debugCheck) {
	    push (@errors, $self->makeAtomErrorString('attrib', $triple->getAttributionList));}
	if (@errors) {
	    $self->{-errorHandler}->fatalError(new W3C::Rdf::RdfDBException(-message => "added bogus triple $triple to triple database: $self - ".join(' - ', @errors)));
	}
	# DBG if (exists $self->{BY_CONTENTS}{$triple->getPredicate->toString}{$triple->getSubject->toString}{
	# DBG     $triple->getObject}{$triple->getAttributionList->toString}) {
	# DBG     $self->{-errorHandler}->warning(new W3C::Rdf::RdfDBException(-message => 'added duplicage triple '.$triple->toString.' to triple database: '.$self));
	# DBG }
    }; if ($@) {
	if (my $ex = &catch('W3C::Util::Exception')) {
	    $self->{-errorHandler}->error($ex);
	} else {
	    $self->{-errorHandler}->error(new W3C::Util::PerlException());
	}
    }

    if (!$self->index($triple)) {
	return undef;
    }
    push (@{$self->{TRIPLES}}, $triple);
    # DBG $self->{BY_CONTENTS}{$triple->getPredicate->toString}{$triple->getSubject->toString}{
    # DBG     $triple->getObject}{$triple->getAttribution->toString} = $triple; # !!!

    # notify interested observers
    foreach my $observerEntry (@{$self->{OBSERVERS}}) {
	my ($triples, $observer) = @$observerEntry;
	# leverage off the already written triplesMatching
	$observer->notifyTriple($triple); # !!! not implemented if $self->triplesMatching([$triple], $triples);
    }

    return $triple;
}

sub removeTriple {
    my ($self, $triple) = @_;

    if (my $comp = $self->{PSO}{$triple->getPredicate}{$triple->getSubject}{$triple->getObject}) {
	if ($comp == $triple) {
	    delete $self->{PSO}{$triple->getPredicate}{$triple->getSubject}{$triple->getObject};
	    delete $self->{SOP}{$triple->getSubject}{$triple->getObject}{$triple->getPredicate};
	    delete $self->{OPS}{$triple->getObject}{$triple->getPredicate}{$triple->getSubject};
	    for (my $i = 0; $i < @{$self->{TRIPLES}}; $i++) {
		if ($self->{TRIPLES}[$i] == $triple) {
		    splice(@{$self->{TRIPLES}}, $i, 1);
		    last;
		}
	    }
	    return ($triple);
	} else {
	    &throw(new W3C::Util::ProgramFlowException());
	}
    }
    return ($triple);
}

# copy a set of tripes from another RdfDB
sub copyTriples {
    my ($self, $copyFrom) = @_;
    foreach my $statement (@{$copyFrom->{TRIPLES}}) {
	$self->addTriple($statement);
    }
}

sub getTriples {
    my ($self) = @_;
    return @{$self->{TRIPLES}};
}

sub makeAtomErrorString {
    my ($self, $type, $atom) = @_;
    my $ret = $type;
    if ($atom) {
	$ret .= " $type ".$atom->toString;
    } else {
	$ret .= ' NULL';
    }
    return $ret;
}

sub index {
    my ($self, $triple) = @_;
    if (my $comp = $self->{PSO}{$triple->getPredicate}{$triple->getSubject}{$triple->getObject}) {
	if ($comp == $triple) {
	    return undef;
	} else {
	    &throw(new W3C::Util::ProgramFlowException());
	}
    }
    $self->{PSO}{$triple->getPredicate}{$triple->getSubject}{$triple->getObject} = $triple;
    $self->{SOP}{$triple->getSubject}{$triple->getObject}{$triple->getPredicate} = $triple;
    $self->{OPS}{$triple->getObject}{$triple->getPredicate}{$triple->getSubject} = $triple;
    return $triple;
}

# passed a single triple or a HASH of triples
# return: # - number of deleted elements

sub deleteTriple {
    my ($self, $triples) = @_;
    my $start = $#{$self->{TRIPLES}};
    my $doomed = {};
    if (ref $triples eq 'HASH') {
	$doomed = $triples;
    } elsif (ref $triples eq 'ARRAY') {
	foreach my $triple (@$triples) {
	    $doomed->{$triple} = $triple;
	}
    } else {
	$doomed->{$triples} = $triples;
    }
    $self->{TRIPLES} = [grep {
	if ($doomed->{$_}) {
	    delete $self->{PSO}{$_->getPredicate}{$_->getSubject}{$_->getObject};
	    delete $self->{SOP}{$_->getSubject}{$_->getObject}{$_->getPredicate};
	    delete $self->{OPS}{$_->getObject}{$_->getPredicate}{$_->getSubject};
	    # DBG delete $self->{BY_CONTENTS}{$_->getPredicate.$_->getSubject.$_->getObject};
	    0;
	} else {
	    # 1;
	}} @{$self->{TRIPLES}}];
    return $start - $#{$self->{TRIPLES}};
}

sub reify {
    my ($self, $triple, $nodeId) = @_;
    return if (!$nodeId);
    $triple->setReifiedAs($nodeId);
    my @ret;
    @ret = $self->reallyReify($triple) if (!$self->{-lazyReification});
    return @ret;
}

sub reallyReify {
    my ($self, $triple) = @_;
    my $attrib = new W3C::Rdf::Attribution::Reification(1, $triple, undef);
    my @reificationStatements = $triple->getReification($self, $self->{-atomDictionary}, $attrib);
    foreach my $statement (@reificationStatements) {
	$self->addTriple($statement);
    }
    return @reificationStatements;
}

sub setLazyReification {
    my ($self, $newState) = @_;
    return () if ($newState == $self->{-lazyReification});
    $self->{-lazyReification} = $newState;
    my @ret;
    if ($newState) {
	my %doomed;
	foreach my $triple (@{$self->{TRIPLES}}) {
	    if ($triple->getAttribution->isa('W3C::Rdf::Attribution::Reification')) {
		$doomed{$triple} = $triple;
		# DBG delete $self->{BY_CONTENTS}{$triple->getPredicate->toString}{
		# DBG     $triple->getSubject->toString}{$triple->getObject}{$triple->getAttribution->toString};
	    }
	}
	$self->deleteTriple(\%doomed);
    } else {
	foreach my $triple (@{$self->{TRIPLES}}) {
	    push (@ret, $self->reallyReify($triple));
	}
    }
    return @ret;
}

#####
# triplet database callbacks

# These slow the addTriple method down so they should only be used
# where needed because the parsing needs to change as a result of
# added triples, as in the case of the trust mechanism in W3C::Rdf::RdfParser.

sub registerTripleObserver {
    my ($self, $triples, $observer) = @_;
    push (@{$self->{OBSERVERS}}, [$triples, $observer]);
}

#####
# triplet database queries

#####
# supplied - strain view for supplied triples (ones that were added to DB rather than reified or something like that

sub supplied {
    my ($self, $view) = @_;
    $view ||= $self->{TRIPLES};
    my @ret;
    foreach my $triple (@$view) {
	push (@ret, $triple) if ($triple->getAttribution->supplied);
    }
    return @ret;
}

#####
# triplesMatching (lookFor) - returns all triplets that match any of the triples in @$lookFors
# ex:	my @resourceList = $rdfDB->triplesMatching(undef, [['http://www.w3.org/schema/certHTMLv1/hasAccessTo', $node, undef]]);
# bug - ignores attribution filter
sub triplesMatching {
    my ($self, $view, $lookFors, %flags) = @_;
    $lookFors = [@$lookFors]; # protect orig
    my $useSubIndexes = 0;
    my $ret = {};

    if (!defined $view) {
	# weed out some queries with the indexes
	for (my $i = 0; $i < @$lookFors;) {
	    my $lookFor = $lookFors->[$i];
	    if (defined $lookFor->[0]) {
		if (defined $lookFor->[1]) {
		    $self->_walkViews($self->{PSO}, $lookFor->[0], $lookFor->[1], $lookFors, $ret, %flags);
		} elsif (defined $lookFor->[2]) {
		    $self->_walkViews($self->{OPS}, $lookFor->[2], $lookFor->[0], $lookFors, $ret, %flags);
		} else {
		    $self->_walkViewsHash($self->{PSO}, $lookFor->[0], $lookFors, $ret, %flags);
		}
		splice(@$lookFors, $i, 1);
	    } elsif (defined $lookFor->[1]) {
		if (defined $lookFor->[2]) {
		    $self->_walkViews($self->{SOP}, $lookFor->[1], $lookFor->[2], $lookFors, $ret, %flags);
		} else {
		    $self->_walkViewsHash($self->{SOP}, $lookFor->[1], $lookFors, $ret, %flags);
		}
		splice(@$lookFors, $i, 1);
	    } elsif (defined $lookFor->[2]) {
		$self->_walkViewsHash($self->{OPS}, $lookFor->[2], $lookFors, $ret, %flags);
		splice(@$lookFors, $i, 1);
	    } else {
		++$i;
	    }
	}
    }

    if (!defined $view) {
	$view = $self->{TRIPLES};
    }

    # search all triples for any remaining $lookFors
    if (@$lookFors) {
	$self->_walkView($view, $lookFors, $ret, %flags);
    }
    return values %$ret; # sort {$b->getSubject->toString cmp $a->getSubject->toString} values %$ret;
}

sub _walkViewsHash {
    my ($self, $cache, $key1s, $lookFors, $ret, %flags) = @_;
    my $view = {};
    foreach my $key1 (ref $key1s eq 'ARRAY' ? @$key1s : $key1s) {
	my $viewSet = $cache->{$key1};
	foreach my $setKey (keys %$viewSet) {
	    my $views = $viewSet->{$setKey};
	    foreach my $key (keys %$views) {
		my $statement = $views->{$key};
		$view->{$statement} = $statement;
	    }
	}
    }
    return $self->_walkView([values %$view], $lookFors, $ret, %flags);
}

sub _walkViews {
    my ($self, $cache, $key1s, $key2s, $lookFors, $ret, %flags) = @_;
    my $view = {};
    foreach my $key1 (ref $key1s eq 'ARRAY' ? @$key1s : $key1s) {
	foreach my $key2 (ref $key2s eq 'ARRAY' ? @$key2s : $key2s) {
	    my $views = $cache->{$key1}{$key2};
	    foreach my $key (keys %$views) {
		my $statement = $views->{$key};
#		if ($self->followList($statement->getObject(), $statement, $view, %flags)) {
#		} else {
		    $view->{$statement} = $statement;
#		}
	    }
	}
    }
    return $self->_walkView([values %$view], $lookFors, $ret, %flags);
}

sub listsFrom {
    my ($self, $startNode, $view) = @_;
    my $lists = $self->_sequesterCollection($view);

    # API usage: get list elements starting with this node.
    if ($startNode) {
	return [@{$lists->{$startNode}[0]}];
    } else {
	# Use by iterators to yank the lists.
	return $lists;
    }
}

sub _sequesterCollection {
    my ($self, $view) = @_;
    my $typeN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'type');
    my $listN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'List');
    my $firstN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'first');
    my $restN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'rest');
    my $nilN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'nil');
    my $BAD = "BAD";
    my ($lists, %roots) = ({}, ());
    # If there is anything of type List
    # if (my @listStatements = sort {int(rand(3))-1} $self->triplesMatching($view, [[$typeN, undef, $listN]])) {
    if (my @listStatements = $self->triplesMatching($view, [[$typeN, undef, $listN]])) {
	# DEBUGGING -- force the order of list nodes in list.owl
	# @listStatements = sort {$ORDER{$a->getSubject->toString} <=> $ORDER{$b->getSubject->toString}} @listStatements;
	# print join("\n", map {$_->toString} @listStatements),"\n";

	# Single-pass algorythm to check List integrity -- has only: (first, rest) | nil
	foreach my $listStatement (@listStatements) {
	    my $listNode = $listStatement->getSubject;
	    my ($first, $rest, $nil);
	    my $good = 1;
	    #print $listStatement->toString,"\n";
	    my @nodeStatements = $self->triplesMatching($view, [[undef, $listNode, undef]]);

	    # Make sure each statement about listNode is expected.
	    foreach my $nodeTerm (@nodeStatements) {
		my ($p, $o) = ($nodeTerm->getPredicate, $nodeTerm->getObject);

		# Make sure statement is one of the expected nil || first,rest
		if ($p == $typeN && $o == $listN) {
		    next;
		}
		if ($p == $firstN) {
		    if ($first || $nil) {
			$good = 0;
			last;
		    }
		    $first = $o;
		    next;
		}
		if ($p == $restN) {
		    if ($rest || $nil || $lists->{$o} == \$BAD) {
			$good = 0;
			last;
		    }
		    $rest = $o;
		    next;
		}
		if ($p == $nilN) {
		    if ($rest || $rest || $nil) {
			$good = 0;
			last;
		    }
		    $nil = $o;
		    next;
		}
		$good = 0;
		last;
	    }

	    # Make sure the node has all the required statements.
	    if (!(($first && $rest) || $nil)) {
		$good = 0;
	    }
	    next if ($listNode == $nilN);

	    my $root;

	    # Get pointer to structure of the list with listNode in it.
	    if (exists $roots{$listNode}) {
		# root ...-rest-> listNode has been encountered so it's the root.
		$root = $roots{$listNode};
		delete $roots{$listNode};
	    } else {
		# root is a new structure pointing to listNode
		$root = $lists->{$listNode} = [[], [], $good, $listNode, $first];
	    }

	    # root->[0] is a list of all elements in this list
	    push (@{$root->[0]}, $first);

	    # If this isn't the last element in the list...
	    if ($rest && $rest != $nilN) {
		# Uodate list of list nodes.
		push (@{$root->[1]}, $rest);

		# If there is a structure assicated with the rest...
		if (exists $lists->{$rest}) {
		    # Absorb it into the current list.
		    push (@{$root->[0]}, @{$lists->{$rest}[0]});
		    push (@{$root->[1]}, @{$lists->{$rest}[1]});
		    # this list is bad if it absorbs a bad list
		    $root->[2] &= $lists->{$rest}[2];
		    # rest of last list nodes points to root.
		    $roots{$lists->{$rest}[1][-1]} = $root;
		    delete $lists->{$rest};
		} else {
		    # root ...-rest-> rest
		    $roots{$rest} = $root;
		}
	    }
	}

	# Remove lists that were not flagged as following "Collection" semantics.
	foreach my $key (keys %$lists) {
	    my $root = $lists->{$key};
	    if (!$root->[2]) {
		delete $lists->{$key};
	    }
	}
	#print join ("\n", map {
	#    $lists->{$_}[3].':'.$lists->{$_}[2].' '.
	#	$lists->{$_}[3]->toString.' ['.join (' | ', map {
	#	    $_->toString} @{$lists->{$_}[1]}).']'} 
	#	    keys %$lists),"\n";
    }
    return $lists;
}

sub _pruneViewCollectionArcs {
    my ($self, $lists, $view) = @_;
    my $triples = $view || $self->{TRIPLES};
    my $typeN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'type');
    my $listN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'List');
    my $nilN = $self->{-atomDictionary}->getUri($self->{RDF_SCHEMA_URI}.'nil');
    foreach my $key (keys %$lists) {
	my ($listMembers, $listNodes, $good2, $rootObj, $first) = @{$lists->{$key}};
	my @users = $self->triplesMatching($view, [[undef, undef, $rootObj]]);
	next if (@users != 1); # All syntaxes (so far) do not allow multiple refs to the same list.

	for (my $i = 0; $i < @$triples; $i++) {
	    my $s = $triples->[$i];
	    next if ($s->isa('W3C::Rdf::ListStatement'));
	    # a little extra dance to keep the ListStatement in the same place as the orig statement - for debugging
	    if ($s->getObject == $rootObj) {
		my ($p, $s, $a) = ($s->getPredicate, $s->getSubject, $s->getAttributionList);
		$triples->[$i] = $self->{-atomDictionary}->createListStatement($p, $s, $a, @{$listMembers});
	    } elsif (($s->getSubject == $rootObj) || 
		     ($s->getPredicate == $typeN && $s->getSubject == $nilN && $s->getObject == $listN) || 
		     (grep {$_ == $s->getSubject || $_ == $s->getObject} @{$listNodes})
		     ) {
		splice(@$triples, $i, 1);
		--$i;
	    }
	}
    }
    # print join("\n", map {$_->toString} @$view),"\n";
}

sub followListNUKE {
    my ($self, $listCandidate, $statement, $view, $flags) = @_;
    my $listCanditate = $statement->getObject;
    my $isaListStatement = $self->{PSO}{$self->{CONSTS}{-rdfType}}{$listCanditate}{$self->{CONSTS}{-rdfList}};
    if (!$isaListStatement) {
	return 0;
    }
    my @listStatements = $statement;
    push (@listStatements, $isaListStatement);
    my $match;
    while ($listCanditate != $self->{CONSTS}{-rdfNil}) {
	# Get the list car.
	$match = $self->_demandObject($self->{CONSTS}{-rdfFirst}, $listCanditate);
	# Fake a triple subsitituting the car as the object of the current statement.
	my $fakeTriple = new W3C::Rdf::MappedTriple($self, $statement->getPredicate, # !!!
						    $statement->getSubject, 
						    $match->getObject, 
						    $statement->getAttribution);
	$view->{$fakeTriple} = $fakeTriple;

	if ($flags->{-lowLevelStatements}) {
	    # Calling engine want to know the real statements.
	    push (@{$flags->{-lowLevelStatements}}, [@listStatements, $match]);
	}

	# Follow the list cdr.
	$match = $self->_demandObject($self->{CONSTS}{-rdfRest}, $listCanditate);
	$listCanditate = $match->getObject;
	push (@listStatements, $match);

	# Ugly bookkeeping hacks.
	if ($isaListStatement = $self->{PSO}{$self->{CONSTS}{-rdfType}}{$listCanditate}{$self->{CONSTS}{-rdfList}}) {
	    push (@listStatements, $isaListStatement);
	} else {
	    # I guess we just assume it is anyways.
	}
    }
    # Add the end of list marker.
    if ($flags->{-lowLevelStatements}) {
	# Calling engine want to know the real statements.
	push (@{$flags->{-lowLevelStatements}[-1]}, $match);
    }
    return 1;
}

sub _demandObject {
    my ($self, $p, $s) = @_;
    my @keys = keys %{$self->{PSO}{$p}{$s}};
    if (@keys != 1) {
	&throw(new W3C::Util::ProgramFlowException());
    }
    return $self->{PSO}{$p}{$s}{$keys[0]};
}

sub _walkView {
    my ($self, $view, $lookFors, $ret, %flags) = @_;

  TRIPLE:
    foreach my $triple (@$view) {
	foreach my $lookFor (@$lookFors) {
	    if ((!defined $lookFor->[0] || &matches($triple->getPredicate, $lookFor->[0])) &&
		(!defined $lookFor->[1] || &matches($triple->getSubject, $lookFor->[1])) &&
		(!defined $lookFor->[2] || grep {&matches($_, $lookFor->[2])} $triple->isa('W3C::Rdf::ListStatement') ? 
					     $triple->getObjects : 
					     ($triple->getObject)) && 
		(!$flags{-attributions} || 
		 scalar grep {$triple->getAttribution->derivedFrom($_)} @{$flags{-attributions}})) {
		$ret->{$triple} = $triple;
		next TRIPLE; # don't bother checking the remaining lookFors, we've already added the triple
	    }
	}
    }
}

sub matches { # static
    my ($ob, $obs) = @_;
    if (ref $obs eq 'ARRAY') {
	for (my $i = 0; $i < @$obs; $i++) {
	    if ($obs->[$i] == $ob) {
		return 1;
	    }
	}
	return 0;
    } else {
	return ($ob == $obs); # || ($ob->toString) eq ($obs->toString)); # !!!
    }
}

sub bNodeClosure { # for SPARQL::Describe
    my ($self, $node, $visited) = @_;
    my $ret = [];
    if (!$visited->{$node} && exists $self->{SOP}{$node}) {
	my $s = $self->{SOP}{$node};
	$visited->{$node} = $s; # just a marker now.
	foreach my $oStr (keys %$s) {
	    my $so = $s->{$oStr};
	    foreach my $pStr (keys %$so) {
		my $sop = $so->{$pStr}; # a Statement.
		push (@$ret, $sop);
		my $oNode = $sop->getObject;
		if ($oNode->isa('W3C::Rdf::BNode')) {
		    push (@$ret, @{$self->bNodeClosure($oNode, $visited)});
		}
	    }
	}
    }
    return $ret;
}

sub _orderedValues {
    my ($self, $triple, $orderBy) = @_;
    return ($triple->getPredicate, $triple->getSubject, $triple->getObject);
}

sub _sortIndex {
    my ($self, $sort, $index, $orderBy, $bnodes) = @_;
    my @valueStrs;
    foreach my $value ($self->_orderedValues($sort->[$index], $orderBy)) {
	my $valueStr;
	if (UNIVERSAL::isa($value, 'W3C::Rdf::BNode')) {
	    if (!exists $bnodes->{$value}) {
		my $nextBNode = scalar keys %$bnodes;
		$bnodes->{$value} = "#bnode${nextBNode}#";
	    }
	    $valueStr = $bnodes->{$value};
	} elsif (defined $value) {
	    $valueStr = $value->toString();
	} else {
	    $valueStr = undef;
	}
	push (@valueStrs, $valueStr);
    }
    return join('|', @valueStrs);
}

sub dumpN3 { # static
    my ($self) = @_;
    require W3C::Rdf::N3Serializer;
    my $serializer = new W3C::Rdf::N3Serializer(-atomDictionary => $self->{-atomDictionary});
    my $iterator = $self->makeSerializerIterator(undef, {}); # $statements, %flags
    $iterator->iterate($serializer);
    return $serializer->getText();
}

sub compare { # compare to another database
    my ($self, $testDB, %flags) = @_;
    my ($selfOrderBy, $testOrderBy) = (undef, undef);
    my @errors;
    my $refSort = new W3C::Rdf::NestingSorter($self, $flags{ALGAE2})->getStatementList();
    my $testSort = new W3C::Rdf::NestingSorter($testDB, $flags{ALGAE2})->getStatementList();
#    print "ref: ", join("\n     ", map {$_->toString(-brief=>1)} @$refSort), "\n";
#    print "tst: ", join("\n     ", map {$_->toString(-brief=>1)} @$testSort), "\n";
#    print $self->dumpN3();
#    print $testDB->dumpN3();

    my $testBNodes = {};
    sub _buildIndex {
	my ($rs, $sort, $orderBy, $bNodeMap) = @_;
	my $indexes = {};
	for (my $i = 0; $i < @$sort; $i++) {
	    my $index = $rs->_sortIndex($sort, $i, $orderBy, $bNodeMap);
	    if ($indexes->{$index}) {
		$indexes->{$index}[1] = $i;
	    } else {
		$indexes->{$index} = [$i, $i];
	    }
	}
	return $indexes;
    }
    my $testIndexes = &_buildIndex($testDB, $testSort, $testOrderBy, $testBNodes);

    my $refBNodes = {};
    if ($flags{-verbose}) {
	&throw();
    }
    my @errors;
    my $testRow = 0;
    my $refRow;
    for ($refRow = 0; $refRow < @$refSort; $refRow++) {
	my $refValue = $self->_sortIndex($refSort, $refRow, $selfOrderBy, $refBNodes);
	if (exists $testIndexes->{$refValue}) {
	    # Reference row also showed up in test result set.
	    # Expect testRow to point at that row.
	    if ($testRow > $testIndexes->{$refValue}[1]) {
		# We have already exhausted test rows with this value.
		push (@errors, "$refRow:< $refValue");
	    } else {
		while ($testRow < $testIndexes->{$refValue}[0]) {
		    # We've skipped past some rows in the test result set.
		    my $skippedValue = $testDB->_sortIndex($testSort, $testRow, $testOrderBy, $testBNodes);
		    push (@errors, "$refRow:> $skippedValue");
		    $testRow++;
		}
		$testRow++;
	    }
	} else {
	    # There was no test row with this value.
	    push (@errors, "$refRow:< $refValue");
	}
    }
    while ($testRow < @$testSort) {
	# We have not used up all the test rows.
	my $refValue = $testDB->_sortIndex($testSort, $testRow, $testOrderBy, $testBNodes);
	push (@errors, "$refRow:> $refValue");
	$testRow++;
    }
    return @errors;
}

sub debugCheck {
    my ($self) = @_;
    for (my $j = 0; $j < @{$self->{TRIPLES}}; $j++) {
	if (!defined $self->{TRIPLES}[$j] || 
	    !$self->{TRIPLES}[$j]->isa('W3C::Rdf::Statement')) {
	    &throw(new W3C::Util::DebugCheckException(-state => "$self had bad statement at ->{TRIPLES}[$j] : $self->{TRIPLES}[$j]"));
	}
    }
}

sub toString {
    my ($self, %flags) = @_;
    my $prefix = $flags{-prefix} || '  ';

    my $ret = '';
    $ret .= $prefix.$self."\n";
    $ret .= $prefix.'SOURCE ATTRIBUTION: '.$self->{-sourceAttribution}->toString."\n" if ($self->{-sourceAttribution});
    $ret .= $prefix."TRIPLES:\n";
    $ret .= CORE::join ("\n", $self->expandStatements(%flags))."\n";

    foreach my $constCount (reverse sort keys %{$self->{FORWARD_CHAINING_RULES}}) {
	$ret .= "$constCount constants:\n";
	my $rulesAtCount = $self->{FORWARD_CHAINING_RULES}{$constCount};
	foreach my $positionSet (keys %$rulesAtCount) {
	    # rule indexed by number of consts and positions of the consts
	    my $keys = '';
	    if ($positionSet & 1) {$keys .= 'P'};
	    if ($positionSet & 2) {$keys .= 'S'};
	    if ($positionSet & 4) {$keys .= 'O'};
	    $ret .= "  indexed $keys:\n";
	    $ret .= $self->_ruleStr($rulesAtCount->{$positionSet}, $positionSet, 0);
	}
    }
    return $ret;
}

sub _ruleStr {
    my ($self, $rulePointer, $positionSet, $iPosition) = @_;
    my $ret;
    # then by each const used
    if ($iPosition < 3) {
	if ($positionSet & (1 << $iPosition)) {
	    foreach my $const (keys %$rulePointer) {
		$ret .= " $const ".$self->_ruleStr($rulePointer->{$const}, $positionSet, $iPosition+1);
	    }
	} else {
		$ret .= " _ ".$self->_ruleStr($rulePointer, $positionSet, $iPosition+1);
	}
    } else {

	# We have arrived at the sets of rules the assertion triggers.
	foreach my $ruleSet (@$rulePointer) {
	    # We match the first rule, now iteratively check the rest:
	    my ($matched, $rest, $rule, $algaeInterface, $resultSet) =@$ruleSet;
	    $ret .= join("\n", undef, &DecorateArray('   {', '    ', '', '}', $rule->toString), undef);
	}
    }
    return $ret;
}

sub expandStatements {
    my ($self, %flags) = @_;
    my @statements = $self->triplesMatching($flags{-view}, [[undef, undef, undef]], %flags);
    return map {$_->toString(%flags)} @statements;
}

sub makeSerializerIterator {
    my ($self, $view, $algae2, %iteratorFlags) = @_;
    $iteratorFlags{-view} = $view || $self->{TRIPLES};
    $iteratorFlags{-scheme} ||= 'guess';
    $iteratorFlags{-RdfDB} = $self;
    return new W3C::Rdf::RdfDB::SerializerIterator($algae2, %iteratorFlags);
}

sub changeId {
    my ($self, $view, $oldId, $newId) = @_;
    $view ||= $self->{TRIPLES};
    foreach my $statement (@$view) {
	if ($statement->getPredicate == $oldId) {
	    $statement->setPredicate($newId);
	}
	if ($statement->getSubject == $oldId) {
	    $statement->setSubject($newId);
	}
	if ($statement->getObject == $oldId) {
	    $statement->setObject($newId);
	}
#	if ($statement->getAttribution == $oldId) { # !!!
#	    $statement->setAttribution($newId);
#	}
	if ($statement->getReifiedAs == $oldId) {
	    $statement->setReifiedAs($newId);
	}
    }
    return $newId;
}

sub dbEvaluateQTerm {
    my ($self, $resultSet, $exprs, $dbSpec) = @_;
    $exprs->evaluateQTermAndConstraints($resultSet, $self);
}

sub dbEvaluateAssertion {
    my ($self, $resultSet, $exprs, $dbSpec, $visited, $trigger, $attribution) = @_;
    return $exprs->evaluateAssertion($resultSet, $self, $visited, $trigger, $attribution);
}

sub dbEvaluateDeletion {
    my ($self, $resultSet, $exprs, $dbSpec, $visited, $trigger, $attribution) = @_;
    return $exprs->evaluateDeletion($resultSet, $self, $visited, $trigger, $attribution);
}

sub tryRule {
    my ($self, $data, $matched, $rest, $rule, $resultSet, $db, $view, $flags, $visited, $trigger, $attribution) = @_;
    my $qret = $rest->delayedEvaluate($resultSet, $trigger, $matched); # @@@ correct inference trigger not enforced right now.

    # Some old code to use the optimized rule created above -- good for CNF query
#    my ($oldResults, $oldStatements) = $resultSet->getResults;
#    if ($matched) {
#	# preload the resultSet with the bindings from the matched statement
#	my $nextResults = [[]];
#	for (my $i = 0; $i < $matched->arity; $i++) {
#	    $matched->getSlot($i)->absorb($data->[$i], $resultSet, $nextResults);
#	}
#	$resultSet->setResults($nextResults, $oldStatements);
#    }
#    # now find whether the [rest of the] rules match
#    $self->processQueries($rest, $resultSet, $db, $view, undef, $flags);
#    # assert $head
#    if (@$oldStatements) {
    my ($results, $statements) = $resultSet->getResults;
    if (@$results) {
	eval {
	    $rule->getHead->delayedEvaluate($resultSet, $visited, $trigger, $rule);
	}; if ($@) {
	    my $ex;
	    if ($ex = &catch('W3C::Rdf::RdfDBException')) {
		$self->{-errorHandler}->warning($ex);
	    } else {&throw()}
	}
    }

    $resultSet->clearResults;
}

sub apiToImpl {
    my ($self, $apiQuerySets) = @_;
    if (@{$self->{-db}{INTERFACES_list}}) {
	my $outsideQuerySets = new W3C::Rdf::Algae::SetQueryPiece(0, undef, 0, 0); # = [];
	foreach my $ruleSet (@{$self->{-db}{INTERFACES_list}}) {
	    my ($matched, $rest, $api, $impl, $algaeInterface, $resultSet) =@$ruleSet;
	    $algaeInterface->{NEW_QUERY} = $outsideQuerySets;
	    $algaeInterface->tryRule(undef, undef, $api, $api, $resultSet, new W3C::Rdf::QueryDB(-atomDictionary => $self->{-db}{-atomDictionary}, -from => $self), [$apiQuerySets->getTerms], {}, {}, undef, $impl); # @@@ what to do with $impl
	}
	return $outsideQuerySets;
    } else {
	return $apiQuerySets;
    }
}

1;

__END__

=head1 NAME

W3C::Rdf::RdfDB - database to store RDF triples

=head1 SYNOPSIS

  use W3C::Rdf::Atoms;
  use W3C::Rdf::RdfDB;
  ues W3C::Util::NamespaceHandler;
  use W3C::Rdf::Algae2;

  my $atoms = new W3C::Rdf::Atoms();
  my $db = new W3C::Rdf::RdfDB(-atomDictionary => $atoms);
  my $nsh = new W3C::Util::NamespaceHandler();
  my $url = $atoms->getUri(new_abs URI($0, 'file://localhost/some/path'));
  $attrib = $atoms->getGroundFactAttribution($url, undef, undef, undef);
  my $queryHandler = new W3C::Rdf::Algae2($atoms
					  $nsh, 
					  {'' => $self}, $self, 
					  $attrib, 
					  {-uniqueResults => 1}, 
					  -rdfDB => $db);
  my ($nodes, $selects, $messages, $proofs) = 
      $queryHandler->interpret('ask (...)', $self->{-location}, $QL_ALGAE);

=head1 DESCRIPTION

Database to store RDF triples and a bunch of query opperations to retrieve them.

This module is part of the W3C::Rdf CPAN module.

=head1 AUTHOR

Eric Prud\'hommeaux <eric@w3.org>

=head1 SEE ALSO

W3C::Rdf::RdfParser(3) perl(1).

=cut
