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

# $Id: ResultSet.pm,v 1.116 2007-11-13 01:26:25 eric Exp $

use strict;
require Exporter;
#require AutoLoader;

$W3C::Rdf::ResultSet::REVISION = '$Id: ResultSet.pm,v 1.116 2007-11-13 01:26:25 eric Exp $ ';

package W3C::Rdf::Result;
use W3C::Util::Exception;

sub new {
    my ($proto, $resultSet, $row, $iterator) = @_;
    my $class = ref($proto) || $proto;
    my $self = {RESULT_SET => $resultSet, RowNo => $row, 
		Iterator => $iterator, Eliminated => 0};
    bless ($self, $class);
    return $self;
}
sub DESTROY {
    my ($self) = @_;
    $self->{RESULT_SET}->removeRow($self);
}
sub test {
    my ($self, $operation) = @_;
    if ($self->{Eliminated}) {
	&throw(new W3C::Util::Exception(-message => "attempt to $operation eliminated row"));
    }
}
sub get {
    my ($self, $column) = @_;
    return $self->{RESULT_SET}{Results}[$self->{RowNo}][$column];
}
sub set {
    my ($self, $column, $value) = @_;
    $self->{RESULT_SET}{Results}[$self->{RowNo}][$column] = $value;
}
sub addCaveat {
    my ($self, $ex) = @_;
    push (@{$self->{RESULT_SET}{Caveats}[$self->{RowNo}]}, $ex);
}
sub duplicate {
    my ($self) = @_;
    $self->test("duplicate");
    $self->{RESULT_SET}->_test();
    return $self->{RESULT_SET}->duplicateRow($self->{RowNo}, $self->{Iterator});
}
sub eliminate {
    my ($self) = @_;
    $self->{RESULT_SET}->eliminateRow($self);
    $self->{Eliminated} = 1;;
}
# unduplicate - remove duplicated rows that weren't needed.
sub unduplicate {
    my ($self, $doomed) = @_;
    $doomed->eliminate();
    --$self->{RowNo};
}
sub addProofs {
    my ($self, $proofs) = @_;$self->{RESULT_SET}->_test();
    foreach my $proof (@$proofs) {
	my $db = $self->{RESULT_SET}{STATEMENTS}[$self->{RowNo}];
	$db->addTriple($proof);
	foreach my $handle (keys %{$self->{RESULT_SET}{ByStatementHandle}}) {
	    push (@{$self->{RESULT_SET}{ByStatementHandle}{$handle}[$self->{RowNo}]}, $proof);
	}
    }$self->{RESULT_SET}->_test();
}
sub getProofs {
    my ($self) = @_;
    return $self->{RESULT_SET}{STATEMENTS}[$self->{RowNo}]->getTriples;
}
sub getProofDB {
    my ($self) = @_;
    return $self->{RESULT_SET}{STATEMENTS}[$self->{RowNo}];
}
sub forgetProofStreamStatements {
    my ($self, $handle) = @_;$self->{RESULT_SET}->_test();
#    print "$self forgetProofStreamStatements $self->{RowNo} ", $self->{RESULT_SET}->_before(), "\n";
    my $thisHandle = $self->{RESULT_SET}{ByStatementHandle}{$handle};
    my $ret = $thisHandle->[$self->{RowNo}];
#    print "removing ${thisHandle}->[$self->{RowNo}]\n";
    $thisHandle->[$self->{RowNo}] = [];

    # See if all the proof handles have been emptied.
    if ((grep {@$_} @$thisHandle) == 0) {
#	print "deleting $thisHandle\n";
	delete $self->{RESULT_SET}{ByStatementHandle}{$handle};
    }

#    print "forgetProofStreamStatements ", $self->{RESULT_SET}->_after(), "\n";
    $self->{RESULT_SET}->_test();
    return $ret;
}
sub getBindings {
    my ($self) = @_;
    my %ret;
    for (my $col = 0; $col < @{$self->{RESULT_SET}{INDEX_VAR}}; $col++) {
	$ret{$self->{RESULT_SET}{INDEX_VAR}[$col]} = $self->{RESULT_SET}{Results}[$self->{RowNo}][$col];
    }
    return %ret;
}
sub makeResultSet {
    my ($self) = @_;
    my $ret = {%{$self->{RESULT_SET}}};
    bless ($ret, 'W3C::Rdf::ResultSet');
    $ret->{Results} = [[@{$self->{RESULT_SET}{Results}[$self->{RowNo}]}]];
    $ret->{Caveats} = [[@{$self->{RESULT_SET}{Caveats}[$self->{RowNo}]}]];
    $ret->{Iterators} = [];
    $ret->{Rows} = [];
    my $newProofs = $self->{RESULT_SET}->_makeDB;
    $newProofs->copyTriples($self->{RESULT_SET}{STATEMENTS}[$self->{RowNo}]);
    $ret->{STATEMENTS} = [$newProofs];

#    print "$self makeResultSet", $self->{RESULT_SET}->_before(), "\n";
    $ret->{ByStatementHandle} = {};
    foreach my $handle (keys %{$self->{RESULT_SET}{ByStatementHandle}}) {
	my $thisHandle = $self->{RESULT_SET}{ByStatementHandle}{$handle};
	$ret->{ByStatementHandle}{$handle} = [[@{$thisHandle->[$self->{RowNo}]}]];
    }
#    print "makeResultSet ", $self->{RESULT_SET}->_after(), "\n";
    return $ret;
}
sub assumeNewBindings {
    my ($self, $copyFrom) = @_;
    my $newDLen = @{$copyFrom->{RESULT_SET}{Results}[$copyFrom->{RowNo}]};
    my @sTriples = $self->{RESULT_SET}{STATEMENTS}[$self->{RowNo}]->getTriples;
    my @cfTriples = $copyFrom->{RESULT_SET}{STATEMENTS}[$copyFrom->{RowNo}]->getTriples;
    for (my $i = 0; $i < $newDLen; $i++) {
	$self->set($i, $copyFrom->get($i));
    }
    foreach my $cfTriple (@cfTriples) {
	if (! grep {$_ == $cfTriple} @sTriples) {
	    $self->addProofs([$cfTriple]);
	}
    }
    $self->{RESULT_SET}->debugCheck;
}
sub assumeNewProofs {
    my ($self, $copyFrom) = @_;
    my @sTriples = $self->{RESULT_SET}{STATEMENTS}[$self->{RowNo}]->getTriples;
    my @cfTriples = $copyFrom->{RESULT_SET}{STATEMENTS}[$copyFrom->{RowNo}]->getTriples;
    foreach my $cfTriple (@cfTriples) {
	if (! grep {$_ == $cfTriple} @sTriples) {
	    $self->addProofs([$cfTriple]);
	}
    }
    $self->{RESULT_SET}->debugCheck;
}
sub getCousinWithBindings {
    my ($self, $copyFrom) = @_;
    my $width = @{$copyFrom->{RESULT_SET}{Results}[$copyFrom->{RowNo}]};
    my $ret = undef;
    for (my $rowNo = 0; $rowNo < @{$self->{RESULT_SET}{Results}}; $rowNo++) {
	my $matches = 1;
	if (@{$self->{RESULT_SET}{Results}[$rowNo]} != $width) {
	    last;
	}
	for (my $i = 0; $i < $width; $i++) {
	    if ($self->{RESULT_SET}{Results}[$rowNo][$i] != $copyFrom->get($i)) {
		$matches = 0;
		last;
	    }
	}
	if ($matches) {
	    $ret = new W3C::Rdf::Result($self->{RESULT_SET}, $rowNo, $self->{Iterator});
	    last;
	}
    }
    return $ret;
}
sub toString {
    my ($self, %flags) = @_;
    if ($flags{-lang} eq 'SPARQL') {
	return '('.join(' '. @{$self->{RESULT_SET}{Results}[$self->{RowNo}]}).')';
    } else {
	return $self->{RESULT_SET}->toString(%flags, -markRow => $self->{RowNo}, -rowMarker => "row:$self->{RowNo}");
    }
}

package W3C::Rdf::_TestResult;
use W3C::Util::Exception;

sub new {
    my ($proto, $data, $proofs) = @_;
    my $class = ref($proto) || $proto;
    my $self = {Data => $data, Proofs => $proofs};
    bless ($self, $class);
    return $self;
}
sub get {
    my ($self, $column) = @_;
    return $self->{Data}[$column];
}
sub getProofs {
    my ($self) = @_;
    return $self->{Proofs}->getTriples;
}

package W3C::Rdf::ResultSetIterator;
use W3C::Util::Exception;
sub new {
    my ($proto, $resultSet) = @_;
    my $class = ref($proto) || $proto;
    my $self = {RESULT_SET => $resultSet, CUR_ROW => -1};
    bless ($self, $class);
    return $self;
}
sub DESTROY {
    my ($self) = @_;
    $self->{RESULT_SET}->removeIterator($self);
}
sub hasMoreElements {
    my ($self) = @_;
    return $self->{CUR_ROW} < @{$self->{RESULT_SET}{Results}}-1;
}
sub hasMoreResults {
    my ($self) = @_;
    return $self->{CUR_ROW} < @{$self->{RESULT_SET}{Results}}-1;
}
sub nextElement {
    my ($self) = @_;
    if (!$self->hasMoreElements) {
	&throw(new W3C::Util::Exception(-message => "no next element at $self->{CUR_ROW}"));
    }
    my $ret = new W3C::Rdf::Result($self->{RESULT_SET}, ++$self->{CUR_ROW}, $self);
    $self->{RESULT_SET}->addRow($ret);
    return $ret;
}

package W3C::Rdf::ResultSet;
@W3C::Rdf::ResultSet::ISA = qw(W3C::Util::NamedParmObject);
use W3C::Util::Exception;
use Scalar::Util qw(weaken);
use W3C::Rdf::Atoms qw($Value_NULL);

sub new {
    my ($proto, @parms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new(@parms);
#    $self->{-sources} ||= [];
    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->clear;
    return $self;
}

sub makeSkeleton {
    my ($self) = @_;
    my $ret = {%$self};
    bless ($ret, 'W3C::Rdf::ResultSet');
    ($ret->{Results}, $ret->{Caveats}, $ret->{STATEMENTS}) = ([[]], [[]], [$self->_makeDB]);
    $ret->{Iterators} = [];
    $ret->{Rows} = [];

# ByStatementHandle stuff copied from Result::makeResultSet. Don't know its applicability.
#    print "$self makeResultSet", $self->{RESULT_SET}->_before(), "\n";
    $ret->{ByStatementHandle} = {};
    foreach my $handle (keys %{$self->{RESULT_SET}{ByStatementHandle}}) {
	my $thisHandle = $self->{RESULT_SET}{ByStatementHandle}{$handle};
	$ret->{ByStatementHandle}{$handle} = [[@{$thisHandle->[$self->{RowNo}]}]];
    }
#    print "makeResultSet ", $self->{RESULT_SET}->_after(), "\n";
    return $ret;
}

sub makeCopy999 {
    my ($self) = @_;
    my $ret = $self->makeSkeleton;
    ($ret->{Results}, $ret->{Caveats}, $ret->{STATEMENTS}) = 
	([@{$self->{Results}}], [@{$self->{Caveats}}], []);
    foreach my $row (@{$self->{STATEMENTS}}) {
	push (@{$ret->{STATEMENTS}}, $self->_makeDB);
    }
    return $ret;

    my $ret = {%$self};
    bless ($ret, 'W3C::Rdf::ResultSet');
    ($ret->{Results}, $ret->{Caveats}, $ret->{STATEMENTS}) = 
	([@{$self->{Results}}], [@{$self->{Caveats}}], []);
    foreach my $row (@{$self->{STATEMENTS}}) {
	push (@{$ret->{STATEMENTS}}, $self->_makeDB);
    }
    $ret->{Iterators} = [];
    $ret->{Rows} = [];

# ByStatementHandle stuff copied from Result::makeResultSet. Don't know its applicability.
#    print "$self makeResultSet", $self->{RESULT_SET}->_before(), "\n";
    $ret->{ByStatementHandle} = {};
    foreach my $handle (keys %{$self->{RESULT_SET}{ByStatementHandle}}) {
	my $thisHandle = $self->{RESULT_SET}{ByStatementHandle}{$handle};
	$ret->{ByStatementHandle}{$handle} = [[@{$thisHandle->[$self->{RowNo}]}]];
    }
#    print "makeResultSet ", $self->{RESULT_SET}->_after(), "\n";
    return $ret;
}

sub clear {
    my ($self) = @_;
    $self->{Results} = [[]];	# Matrix of node results.
    $self->{Caveats} = [[]];	# Matrix of node results.
    $self->{STATEMENTS}= [$self->_makeDB];	# Supporting statements for each row of results.
    $self->{VAR_INDEX} = {};	# RESULTS column for a give variable (or const).
    $self->{INDEX_VAR} = [];	# Variable (or const) assigned to each column.
#    $self->{REPORT_OFFSET} = 0;	# How many columns to skip for previous collects

    # Report stuff
    $self->{SELECTS} = [];
    $self->{Iterators} = [];
    $self->{Rows} = [];
    $self->{ByStatementHandle} = {};
    $self->{Sorted} = undef;
    $self->{isSorted} = 0;
    $self->{Distinct} = 0;
    $self->{Messages} = [];
    $self->{TestTrue} = undef;
    $self->{SingletonValue} = undef;
    $self->{PresentationMimetype} = undef;
#$main::err .= __FILE__.":".__LINE__.": ".(caller(0))[3]."(".join(',', @_).")\n".join('', map {"  \$self->{$_}[0]: $self->{$_}[0]\n"} qw(Caveats Results Rows STATEMENTS Iterators))."\n\n";
}

# join self against a set of ResultSets
# common case: just a single RS to join against, but was trivial to
# 	       augment to support UnionDisjunction.

sub join {
    my ($self, $againsts, $optional, $constraints, $handle, $algae) = @_;

    for (my $selfRowNo = 0; $selfRowNo < @{$self->{Results}}; $selfRowNo++) {
	my $selfRow = $self->{Results}[$selfRowNo];
	my $rowsAdded = 0;
	foreach my $against (@$againsts) {
	  againstRow:
	    for (my $againstRowNo = 0; $againstRowNo < @{$against->{Results}}; $againstRowNo++) {
		my $againstRow = $against->{Results}[$againstRowNo];
		my $newRow = [];
		for (my $colNo = 0; $colNo < @{$self->{INDEX_VAR}}; $colNo++) {
		    my $selfVal = defined $selfRow->[$colNo] && $selfRow->[$colNo] != $Value_NULL ? $selfRow->[$colNo] : undef;
		    my $againstVal = defined $againstRow->[$colNo] && $againstRow->[$colNo] != $Value_NULL ? $againstRow->[$colNo] : undef;

		    if ($selfVal && $againstVal && $selfVal != $againstVal) {
			next againstRow;
		    }
		    $newRow->[$colNo] = $selfVal || $againstVal || $selfRow->[$colNo] || $againstRow->[$colNo];# || $Value_NULL;
		}
		my $newCaveats = [@{$self->{Caveats}[$selfRowNo]}];
		my $newProofs = $self->_makeDB;
		$newProofs->copyTriples($self->{STATEMENTS}[$selfRowNo]);
		foreach my $triple ($against->{STATEMENTS}[$againstRowNo]->getTriples()) {
		    $newProofs->addTriple($triple);
		}
		$self->_test();

		# test constraints before inserting new row
		if ($handle) {
		    my $statements = [@{$self->{ByStatementHandle}{$handle}[$selfRowNo]}, $against->{STATEMENTS}[$againstRowNo]->getTriples()];
		    $self->{ByStatementHandle}{$handle}[$selfRowNo] = [];
		    my $row = new W3C::Rdf::_TestResult($newRow, $newProofs);
		    foreach my $constraint (@$constraints) {
			if (!@$statements) {
			    next againstRow;
			}
			foreach my $triple (@$statements) {
			    eval {
				my $res = $constraint->val($triple, undef, $row);
				if (!$res || !$algae->getEBV($res)) { # ($res->isa('W3C::Rdf::String') && !$res->getString)) {
				    next againstRow;
				}
			    }; if ($@) {if (my $ex = &catch('W3C::Util::SafeEvaluationException')) {
				next againstRow;
			    } else {
				&throw();
			    }}
			}
		    }
		}

		splice (@{$self->{Results}}, $selfRowNo, 0, $newRow);
		splice (@{$self->{Caveats}}, $selfRowNo, 0, $newCaveats);
		splice (@{$self->{STATEMENTS}}, $selfRowNo, 0, $newProofs);
		foreach my $handle (keys %{$self->{ByStatementHandle}}) {
		    my $thisHandle = $self->{ByStatementHandle}{$handle};
		    if (ref $thisHandle ne 'ARRAY') {
			&throw();
		    }
		    if (ref $thisHandle->[$selfRowNo] ne 'ARRAY') {
			&throw();
		    }
		    my $newStatementHandleList = [@{$thisHandle->[$selfRowNo]}, $against->{STATEMENTS}[$againstRowNo]->getTriples()];
		    splice (@$thisHandle, $selfRowNo, 0, $newStatementHandleList);
		}
		$self->_test();
		$rowsAdded++;
		$selfRowNo++;
	    }
	}
	if (!$optional || $rowsAdded) {
	    splice (@{$self->{Results}}, $selfRowNo, 1);
	    splice (@{$self->{Caveats}}, $selfRowNo, 1);
	    splice (@{$self->{STATEMENTS}}, $selfRowNo, 1);
	    foreach my $handle (keys %{$self->{ByStatementHandle}}) {
		my $thisHandle = $self->{ByStatementHandle}{$handle};
		if (@$thisHandle == 1) {
		    delete $self->{ByStatementHandle}{$handle};
		} else {
		    splice (@$thisHandle, $selfRowNo, 1);
		}	
	    }
	    $self->_test();
	    $selfRowNo--;
	}
    }
}

sub projectOutNUKE {
    my ($self, $symbol) = @_;
    my $index = $self->{VAR_INDEX}{$symbol};
    map {splice (@$_, $index, 1)} @{$self->{Results}};
    delete $self->{VAR_INDEX}{$symbol};
    splice (@{$self->{INDEX_VAR}}, $index, 1);
}

sub _makeDB {new W3C::Rdf::RdfDB(-atomDictionary => $_[0]->{-atomDictionary}, -lazyReification => 1);}

# Make sure the result set has at least one row. This is useful when a previous
# query has eliminated the last row from the result set. It then seems to make
# sense to let the unification begin again.
sub atLeastOneRow {
    my ($self) = @_;
    if (!@{$self->{Results}}) {
	$self->{Results} = [[]];
	$self->{Caveats} = [[]];
	$self->{STATEMENTS}= [$self->_makeDB];
    }
}
sub isFresh {
    my ($self) = @_;
    return @{$self->{Results}} == 1 && @{$self->{Results}[0]} == 0;
}

sub getProofStreamHandle {
    my ($self) = @_;$self->_test();
    my $handle = [];
    for (my $i = 0; $i < @{$self->{Results}}; $i++) {
	$self->{ByStatementHandle}{$handle}[$i] = [];
    }$self->_test();
    return $handle;
}

# RdfDB interface to ResultSet -- used by RdfDB::processQueries
sub getResults {($_[0]->{Results}, $_[0]->{STATEMENTS})}
sub setResultsNUKE {$_[0]->{Results} = $_[1]; $_[0]->{STATEMENTS} = $_[2];}
sub isDistinct {$_[0]->{Distinct}}
sub isSorted {$_[0]->{isSorted}}

# clearResults - Called when someone else knows that the constraints
#                aren't going to be met.
sub clearResults {
    my ($self) = @_;
    ($self->{Results}, $self->{Caveats}, $self->{STATEMENTS}) = ([[]], [[]], [$self->_makeDB]);
}

# $baseUri	URI from which relative URIs are referenced
# $flags	special control flags for this opperation

sub buildQuerySets {
    my ($self, $pattern, $messages, $db, $algae, $namespaceHandler, $baseUri, $flags) = @_;
    my $ret = new W3C::Rdf::Algae::SetQueryPiece(-999, $pattern->[0], 0, 0);
    $self->_parseExprs($ret, $pattern, $messages, $db, $algae, $namespaceHandler, $baseUri, $flags);
    return $ret;
}

sub bindSymbol {
    my ($self, $symbol) = @_;
    my $index = @{$self->{INDEX_VAR}};
    push (@{$self->{INDEX_VAR}}, $symbol);
    $self->{VAR_INDEX}{$symbol} = $index;
    return $index;
}

sub getSymbols {
    my ($self) = @_;
    return grep {$_ !~ m/^_:/} @{$self->{INDEX_VAR}};
}

sub getIndex {
    my ($self, $symbol) = @_;
    return exists $self->{VAR_INDEX}{$symbol} ? $self->{VAR_INDEX}{$symbol} : undef;
}

sub addSelect {
    my ($self, $select) = @_;
#    $self->{REPORT_OFFSET}++;
    push (@{$self->{SELECTS}}, $select);
}
sub getSelectsNUKE {
    my ($self, $select) = @_;
    my $ret = [];
    foreach my $select (@{$self->{SELECTS}}) {
	push (@$ret, $self->{INDEX_VAR}[$select]);
    }
    return $ret;
}

sub duplicateRow {
    my ($self, $rowNo, $iterator) = @_;$self->_test();
    # splice in at current index and increment indexes
    if (@{$self->{Results}} <= $rowNo) {
	&throw(new W3C::Util::OutOfBoundsException(-name => "$self(".(scalar @{$self->{Results}})."):Results", -index => $rowNo));
    }
    my $newRow = [@{$self->{Results}[$rowNo]}];
    my $newCaveats = [@{$self->{Caveats}[$rowNo]}];
    my $newProofs = $self->_makeDB;
    $newProofs->copyTriples($self->{STATEMENTS}[$rowNo]);
    my $newOb = new W3C::Rdf::Result($self, $rowNo, $iterator);
    splice (@{$self->{Results}}, $rowNo, 0, $newRow);
    splice (@{$self->{Caveats}}, $rowNo, 0, $newCaveats);
    splice (@{$self->{STATEMENTS}}, $rowNo, 0, $newProofs);
    foreach my $handle (keys %{$self->{ByStatementHandle}}) {
	my $thisHandle = $self->{ByStatementHandle}{$handle};
	if (ref $thisHandle ne 'ARRAY') {
	    &throw();
	}
#	print "duplicate ${thisHandle}->[$rowNo] $thisHandle->[$rowNo]\n";
	if (ref $thisHandle->[$rowNo] ne 'ARRAY') {
	    &throw();
	}
	my $newStatementHandleList = [@{$thisHandle->[$rowNo]}];
#	print "                                $newStatementHandleList\n";
	splice (@$thisHandle, $rowNo, 0, $newStatementHandleList);
    }
    foreach my $iterator (@{$self->{Iterators}}) {
	if ($iterator->{CUR_ROW} >= $rowNo) {
	    $iterator->{CUR_ROW}++;
	}
    }
    foreach my $otherRow (@{$self->{Rows}}) {
	if ($otherRow->{RowNo} >= $rowNo) {
	    $otherRow->{RowNo}++;
	}
    }
    $self->addRow($newOb);
    return $newOb;$self->_test();
}

sub eliminateRow {
    my ($self, $row) = @_;$self->_test();
    my $rowNo = $row->{RowNo};#print "$self(".(scalar @{$self->{Results}})."):eliminate($rowNo)\n";
#    print $self->toString(-proofStreams => 1, 
#					-namespaceHandler => 
#	new W3C::Util::NamespaceInventor(-namespaceCreativity => 1)),"\n";

    # splice out current and decrement indexes
    splice (@{$self->{Results}}, $rowNo, 1);
    splice (@{$self->{Caveats}}, $rowNo, 1);
    splice (@{$self->{STATEMENTS}}, $rowNo, 1);
    foreach my $handle (keys %{$self->{ByStatementHandle}}) {
	my $thisHandle = $self->{ByStatementHandle}{$handle};
#	print "eliminate: ${thisHandle}->[$rowNo] $thisHandle->[$rowNo]\n";
	if (@$thisHandle == 1) {
#	    print "deleting $thisHandle\n";
	    delete $self->{ByStatementHandle}{$handle};
	} else {
#	    print "removing ${thisHandle}->[$rowNo]\n";
	    splice (@$thisHandle, $rowNo, 1);
	}	
    }
    # --$rowNo;
    foreach my $iterator (@{$self->{Iterators}}) {
	if ($iterator->{CUR_ROW} >= $rowNo) {
	    $iterator->{CUR_ROW}--;
	}
    }
    $self->removeRow($row);
    foreach my $otherRow (@{$self->{Rows}}) {
	if ($otherRow->{RowNo} >= $rowNo) {
	    $otherRow->{RowNo}--;
	}
    }
}

sub testTrue {
    my ($self, $enable) = @_;
    $self->{TestTrue} = $enable ? @{$self->{Results}} > 0 ? 1 : 0 : undef;
}
sub getTruthValue {
    my ($self) = @_;
    return $self->{TestTrue};
}

sub setSingletonValue {
    my ($self, $count) = @_;
    $self->{SingletonValue} = $count;
}
sub getSingletonValue {
    my ($self) = @_;
    return $self->{SingletonValue};
}

sub eliminateRedundantBNodes {
    my ($self) = @_;
    # print $self->toString(-unicode => 0), "\n";
    my $rowNos = $self->{Sorted} || [0..@{$self->{Results}}-1];
    my $indexBy = [];
    for (my $iColumn = 0; $iColumn < @{$self->{INDEX_VAR}}; $iColumn++) {
	if ($self->{INDEX_VAR}[$iColumn] !~ /^<gensym/) {
	    push (@$indexBy, $iColumn);
	}
    }
    my $byValues = {};
    for (my $rowNo = 0; $rowNo < @$rowNos; $rowNo++) {
	my $row = $self->{Results}[$rowNos->[$rowNo]];
	my $index = join(' | ', map {$row->[$_]} @$indexBy);
	if (exists $byValues->{$index}) {
	    splice (@{$self->{Results}}, $rowNos->[$rowNo], 1);
	    splice (@{$self->{Caveats}}, $rowNos->[$rowNo], 1);
	    splice (@{$self->{STATEMENTS}}, $rowNos->[$rowNo], 1);
	    for (my $iSorted = 0; $iSorted < @$rowNos; $iSorted++) {
		if ($rowNos->[$iSorted] == $rowNo) {
		    splice (@$rowNos, $iSorted, 1);
		    $iSorted--;
		} elsif ($rowNos->[$iSorted] > $rowNo) {
		    $rowNos->[$iSorted]--;
		}
	    }
	    $rowNo--;
	} else {
	    $byValues->{$index} = $row;
	}
    }
}

sub gatherCollect {
    my ($self) = @_;
    my @variables;
    my $statements = $self->_makeDB;
    if (defined $self->{TestTrue}) {
	return ([@{$self->{Results}} > 0 ? 1 : 0], []);
    }
    if (defined $self->{SingletonValue}) {
	return ([$self->{SingletonValue}], []);
    }
    my $rows = $self->{Sorted} || [0..@{$self->{Results}}-1];
    for (my $rowNo = 0; $rowNo < @$rows; $rowNo++) {
	my $row = new W3C::Rdf::Result($self, $rows->[$rowNo], undef);
	my @resultRow;
	foreach my $select (@{$self->{SELECTS}}) {
	    if (defined $select) {
		if (UNIVERSAL::can($select, 'val')) {
		    push (@resultRow, $select->val(undef, undef, $row));
		} else {
		    push (@resultRow, $row->get($select));
		}
	    } else {
		push (@resultRow, undef);	# leave column unbound
	    }
	}
	if (@{$self->{Caveats}[$rowNo]}) {
	    push (@resultRow, $self->{-atomDictionary}->getString(join(' AND ', map {$_->getMessage()} @{$self->{Caveats}[$rowNo]}), undef, 'PLAIN', undef));
	}
	push (@variables, \@resultRow);
	$statements->copyTriples($self->{STATEMENTS}[$rowNo]);
    }
    return (\@variables, [@{$self->{STATEMENTS}}]);
}

# Sort solution sequence per SPARLQ Query.
# -> http://unagi/2001/sw/DataAccess/rq23/#modOrderBy

# Priorities ('_' indicates that the ordering with respect to the next type is
# not defined by SPARQL):

#   Value_NULL
# _1 "123"
# _2 "123"^^xs:boolean
#    "123"^^xs:integer __ ordered by W3C::Rdf::String::numericOrDTCompare
#    "123"^^xs:string
#    "124"^^xs:integer
#    xs:integer
#    _:1
# _3 _:2

# _1: Sort untyped literals before typed literals. (compatible with "# A plain
#     literal before an RDF literal with type xsd:string of the same lexical
#     form.")
# _2: Sort literals of different types by the order of the type URIs.
# _3: sort bNodes by their attribution,system index number.

# return: -1: $l < $r, 0: $l == $r, 1: $l > $r
sub sortResults { # static
    my ($a, $b, $ascDesc, $comparator) = @_;
    sub ret {
	my ($line, $a, $b, $col, $ret, $asc) = @_;
	# my $l = join('|', map {my $t = $a->[$_]->toString(); $_==$col+2 ? "!$t!" : $t} (2..@$a-1));
	# my $r = join('|', map {my $t = $b->[$_]->toString(); $_==$col+2 ? "!$t!" : $t} (2..@$b-1));
	# my $sign = {-1=>'<', 0=>'=', 1=>'>'}->{$ret};
	# print "$line: $l $sign $r\n";
	return $ret*$asc;
    }
    for (my $col = 0; $col < @$b-2; $col++) {
	my $l = $a->[$col+2];
	my $r = $b->[$col+2];
	if (my $ret = &orderTerm($l, $r, $comparator, $col, $ascDesc->[$col])) {
	    return $ret;
	}
    }
    $b->[1] = 1; # mark as a duplicate
    return &ret(__LINE__, $a, $b, -1, 0, 0);
}
# orderTerm -- used by SPARQL ORDER BY and RdfDB::outerMostFirst.
#   bNodesLast: needed by outerMostFirst.
sub orderTerm { # static
    my ($l, $r, $comparator, $col, $ad, $bNodesLast) = @_;

    if (!ref $l || !ref $r) {
	&throw(new W3C::Util::ProgramFlowException());
    }
    elsif ($l == $r) {
	# same node -- fall through to next order column
    }

# Value_NULL
    elsif ($l == $Value_NULL) {
	return &ret(__LINE__, $a, $b, $col, -1, $ad);
    } elsif ($r == $Value_NULL) {
	return &ret(__LINE__, $a, $b, $col, 1, $ad);
    }

#    _:1
# _3 _:2
    elsif (!$bNodesLast && $l->isa('W3C::Rdf::BNode')) {
	if ($r->isa('W3C::Rdf::BNode')) {
	    if ($l->getUri() != $r->getUri()) {
		if (my $ret = $l->getUri()->getUri() cmp $r->getUri()->getUri()) {
		    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
		}
		if ((my $ret = $l->getId() <=> $r->getId()) != 0) {
		    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
		}
	    }
	} else {
	    return &ret(__LINE__, $a, $b, $col, -1, $ad);
	}
    } elsif (!$bNodesLast && $r->isa('W3C::Rdf::BNode')) {
	return &ret(__LINE__, $a, $b, $col, 1, $ad);
    }

#    xs:integer
    elsif ($l->isa('W3C::Rdf::Uri')) {
	if ($r->isa('W3C::Rdf::Uri')) {
	    if ((my $ret = $l->getUri() cmp $r->getUri())) {
		return &ret(__LINE__, $a, $b, $col, $ret, $ad);
	    }
	} else {
	    return &ret(__LINE__, $a, $b, $col, -1, $ad);
	}
    } elsif ($r->isa('W3C::Rdf::Uri')) {
	return &ret(__LINE__, $a, $b, $col, 1, $ad);
    }

# _1 "123"
# _2 "123"^^xs:boolean
#    "123"^^xs:integer __ ordered by W3C::Rdf::String::numericOrDTCompare
#    "123"^^xs:string
#    "124"^^xs:integer
    elsif ($l->isa('W3C::Rdf::String')) {
	if ($r->isa('W3C::Rdf::String')) {
	    if (my $lDt = $l->getDatatype()) {
		if (my $rDt = $r->getDatatype()) {
		    my $ret = undef;
		    eval {
			$ret = $comparator->compare($l, $r);
		    }; if ($@) {if (my $ex = &catch('W3C::Rdf::IncorrectTypeException')) {
			# not a comparable type lexical sort then datatype sort.
			# $ret remains undef.
				} else {
				    &throw($ex);
				}}
		    if (defined $ret && $ret != 0) {
			return &ret(__LINE__, $a, $b, $col, $ret, $ad);
		    } else {
			# Either uncomparable, or same semantic value.
			# Could fall through to next order column, but total
			# ordering is critical to result set comparison.

			if ((my $ret = $l->getString() cmp $r->getString()) != 0) {
			    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
			}
			if ((my $ret = $lDt->getUri() cmp $rDt->getUri()) != 0) {
			    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
			}
			my ($lStr, $rStr) = ($l->toString(), $r->toString());
			&throw(new W3C::Util::Exception(-message => "Two atoms $l and $r appear to be the same."));
		    }
		} else {
		    return &ret(__LINE__, $a, $b, $col, 1, $ad);
		}
	    } else {
		if (my $rDt = $r->getDatatype()) {
		    return &ret(__LINE__, $a, $b, $col, -1, $ad);
		} elsif ((my $ret = ($l->getString() cmp $r->getString()) || 
			  ($l->getLang() cmp $r->getLang())) != 0) {
		    # lexical sort on lexical form, language
		    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
		}
	    }
	} else {
	    return &ret(__LINE__, $a, $b, $col, -1, $ad);
	}
    } elsif ($r->isa('W3C::Rdf::String')) {
	return &ret(__LINE__, $a, $b, $col, 1, $ad);
    }

    # If we're sorting for serialization...
    elsif ($bNodesLast && $l->isa('W3C::Rdf::BNode')) {
	if ($r->isa('W3C::Rdf::BNode')) {
	    if ($l->getUri() != $r->getUri()) {
		if (my $ret = $l->getUri()->getUri() cmp $r->getUri()->getUri()) {
		    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
		}
		if ((my $ret = $l->getId() <=> $r->getId()) != 0) {
		    return &ret(__LINE__, $a, $b, $col, $ret, $ad);
		}
	    }
	} else {
	    return &ret(__LINE__, $a, $b, $col, -1, $ad);
	}
    } elsif ($bNodesLast && $r->isa('W3C::Rdf::BNode')) {
	return &ret(__LINE__, $a, $b, $col, 1, $ad);
    }

# 4TF?
    else {
	&throw(new W3C::Util::ProgramFlowException());
    }
    return 0;
}
sub trim {
    my ($self, $offset, $limit, $orderBy, $distinct, $comparator, $distinctOnly) = @_;

    my $ascDesc = [map {$_->[1]} @$orderBy]; # grab the orders
    if (!$distinctOnly) {
	$self->{isSorted} = 1;
    }

    # Optimize sorting with a Schwartzian Transform.
    #   http://www.stllinux.org/meeting_notes/1997/0918/schwtr.html

    my @asRefs = map {[$_, 0, $self->_orderedValues($_, $orderBy)]} ($self->{Sorted} ? @{$self->{Sorted}} : 0..@{$self->{Results}}-1);
    my @sorted = sort {&sortResults($a, $b, $ascDesc, $comparator)} @asRefs;
    if ($distinct) {
	# It looks like SPARQL's counting semantics don't allow the elimination of non-unique results.
	# Note: this also eliminated rows that were not unique on the sort index (eg {1, 'A'} {1, 'B'}).
	@sorted = grep {!$_->[1]} @sorted;
	$self->{Distinct} = 1;
    }
    $self->{Sorted} = [map {$_->[0]} @sorted];	# get the ordinal back

    splice(@{$self->{Sorted}}, 0, $offset);
    if (defined $limit) {
	splice(@{$self->{Sorted}}, $limit, @{$self->{Sorted}});
    }
}
sub _orderedValues {
    my ($self, $rowNo, $orderBy) = @_;
    my $row = new W3C::Rdf::Result($self, $rowNo, undef);
    my @values;
    foreach my $nodePair (@$orderBy) {
	my ($func, $order) = @$nodePair;
	my $value;
	eval {
	    $value = $func->val(undef, undef, $row);
	}; if ($@) {if (my $ex = &catch('W3C::Util::SafeEvaluationException')) {
	    $value = undef;
	} else {
	    &throw($ex);
	}}
	push (@values, $value);
    }
    return @values;
}

sub _sortIndex {
    my ($self, $index, $orderBy, $bnodes) = @_;
    my @valueStrs;
    foreach my $value ($self->_orderedValues($self->{Sorted}[$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 compare {
    my ($self, $testRS, $fields, $comparator, %flags) = @_;
    my $selfFakeParser = new W3C::Rdf::AlgaeCompileTree::FakeParser($self);
    my $selfOrderBy = [map {[new W3C::Rdf::AlgaeCompileTree::Var($_, 0, $selfFakeParser), 1]} @$fields];
    my $testFakeParser = new W3C::Rdf::AlgaeCompileTree::FakeParser($testRS);
    my $testOrderBy = [map {[new W3C::Rdf::AlgaeCompileTree::Var($_, 0, $testFakeParser), 1]} @$fields];
    if (!$testRS->{isSorted}) {
	$self->trim(undef, undef, $selfOrderBy, $testRS->{Distinct}, $comparator);
	$testRS->trim(undef, undef, $testOrderBy, $testRS->{Distinct}, $comparator);
    }
    my $testBNodes = {};
    sub _buildIndex {
	my ($rs, $orderBy, $bNodeMap) = @_;
	my $indexes = {};
	for (my $i = 0; $i < @{$rs->{Sorted}}; $i++) {
	    my $index = $rs->_sortIndex($i, $orderBy, $bNodeMap);
	    if ($indexes->{$index}) {
		$indexes->{$index}[1] = $i;
	    } else {
		$indexes->{$index} = [$i, $i];
	    }
	}
	return $indexes;
    }
    my $testIndexes = &_buildIndex($testRS, $testOrderBy, $testBNodes);
    my $refBNodes = {};
    if ($flags{-verbose}) {
	print join("\n", map {my $list = join(',', @{$testIndexes->{$_}}); "$_: [$list]"} keys %$testIndexes), "\n";
	my $refIndexes = &_buildIndex($self, $selfOrderBy, $refBNodes);
	print "- vs the reference set -\n", join("\n", map {my $list = join(',', @{$refIndexes->{$_}}); "$_: [$list]"} keys %$refIndexes), "\n";
    }
    my @errors;
    my $testRow = 0;
    my $refRow;
    for ($refRow = 0; $refRow < @{$self->{Sorted}}; $refRow++) {
	my $refValue = $self->_sortIndex($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 = $testRS->_sortIndex($testRow, $testOrderBy, $testBNodes);
		    push (@errors, "$refRow:> $skippedValue");
		    $testRow++;
		}
		$testRow++;
	    }
	} else {
	    # There was no test row with this value.
	    push (@errors, "$refRow:< $refValue");
	}
    }
    while ($testRow < @{$testRS->{Sorted}}) {
	# We have not used up all the test rows.
	my $refValue = $testRS->_sortIndex($testRow, $testOrderBy, $testBNodes);
	push (@errors, "$refRow:> $refValue");
	$testRow++;
    }
    return @errors;
}

sub addMessage {
    my ($self, $message) = @_;
    push (@{$self->{Messages}}, $message);
}

sub getMessages {
    my ($self) = @_;
    return $self->{Messages};
}

sub setPresentationMimetype {
    my ($self, $mt) = @_;
    $self->{PresentationMimetype} = $mt;
}

sub getPresentationMimetype {
    my ($self) = @_;
    return $self->{PresentationMimetype};
}

sub debugCheck {
    my ($self) = @_;
    for (my $i = 0; $i < @{$self->{STATEMENTS}}; $i++) {
	$self->{STATEMENTS}[$i]->debugCheck;
    }
}

sub federate {
    my ($self, $remote, $queryString, $nsMap, $vars) = @_;

    my @varList;
    my @includeColumns;
    for (my $iCol = 0; $iCol < @{$self->{INDEX_VAR}}; $iCol++) {
	my $varName = $self->{INDEX_VAR}[$iCol];
	if ($includeColumns[$iCol] = exists $vars->{$varName} ? 1 : 0) {
	    push (@varList, $varName);
	}
    }
    my $varsString = join(' ', map {"?$_"} @varList);
    my @rows = ("BINDINGS $varsString {");
    my $rowsByValue = {};
    my $rowsByRow = {};

    for (my $e = $self->elements; $e->hasMoreElements;) {
	my $row = $e->nextElement;
	my @cols;
	my $refinedByValue = $rowsByValue;
	$rowsByRow->{$row} = $row;
	my $isDuplicate = 1;
	for (my $colNo = 0; $colNo < @includeColumns; $colNo++) {
	    if ($includeColumns[$colNo]) {
		my $cell = $row->get($colNo);
		push (@cols, $cell ? $cell->toString(-lang => 'SPARQL') : 'NULL');
		if ($refinedByValue->{$cell}) {
		} else {
		    $isDuplicate = 0;
		    $refinedByValue->{$cell} = {};
		}
		$refinedByValue = $refinedByValue->{$cell};
	    }
	}
	$refinedByValue->{$row} = $row;
	if (!$isDuplicate) {
	    my $colsString = join(' ', @cols);
	    push (@rows, "($colsString)");
	}
    }
    push (@rows, '}');

    $queryString .= join(' ', @rows);
    print "QUERY_STRING: $queryString\n";
#    print $self->toString(), "\n";
    require CGI;
    $queryString = &CGI::escape($queryString);
    my $remote = $remote;
    my $inputSource = &W3C::Rdf::RdfApp::getInputSource("$remote?query=$queryString", undef);
    my $attrib = $self->{-atomDictionary}->getGroundFactAttribution(
	$self->{-atomDictionary}->getAbsoluteUri($inputSource->getPublicId()));


    require W3C::Rdf::SRXParser;
    require W3C::XML::HandlerStack;
    require XML::SAX::ParserFactory;
    my $indexes = {};
    my $bnodeMap = {};

    my $handlerStack = new W3C::XML::HandlerStack();
    my $srxHandler = new W3C::Rdf::SRXParser($attrib, $handlerStack, 
					     -vars => sub {
						 my (@vars) = @_;
						 foreach my $var (@vars) {
						     $indexes->{$var} = $self->getIndex($var);
						 }
					     }, 
					     -bindings => sub {
						 my (%bindings) = @_;
						 my $refinedByValue = $rowsByValue;
						 foreach my $varName (@varList) {
						     my $atom = $bindings{$varName};
						     if ($refinedByValue->{$atom}) {
							 $refinedByValue = $refinedByValue->{$atom};
						     } elsif ($refinedByValue->{''}) {
							 $refinedByValue = $refinedByValue->{''};
						     } else {
							 &throw(new W3C::Util::Exception(-message => "key \"".$atom->toString()."\"not found"));
						     }
						 }
						 # For each row in the original result set,
						 foreach my $key (keys %$refinedByValue) {
						     my $newRow = $refinedByValue->{$key}->duplicate();

						     # assign each returned value.
						     foreach my $varName (keys %bindings) {
							 # next if (grep {$_ eq $varName} @varList);
							 my $atom = $bindings{$varName};
							 $newRow->set($indexes->{$varName}, $atom);
						     }
						     # $newRow->addProofs([$match]);
						 }
					     }, -atomDictionary => $self->{-atomDictionary});
    $handlerStack->set_handler($srxHandler);
    my $srxParser = XML::SAX::ParserFactory->parser(Handler => $handlerStack);
    $srxParser->parse_string($inputSource->getByteStream());

    # Eliminate the original set of rows.
    foreach my $key (keys %$rowsByRow) {
	$rowsByRow->{$key}->eliminate;
    }
}

sub toString {
    my ($self, %flags) = @_;
    require W3C::Util::TableRenderer;
    my $df = sub {
	eval {
	    if (ref $_) {
		if ($_ == $Value_NULL) {
		    $_ = 'NULL';
		} elsif ($_->can('toString')) {
		    $_ = $_->toString(%flags);
		} elsif ($_->can('toString')) {
		    $_ = $_->toString(%flags);
		}
	    }
	};  if ($@) {if (my $ex = &catch('W3C::Util::Exception')) {
	    $_ = $ex->toString(%flags);
	} else {
	    $_ = new W3C::Util::PerlException()->toString(%flags);
	}}
    };
    if ($flags{-lang} eq 'SPARQL') {
	my %vars = map {$_->toString(%flags) => undef} @{$self->{SELECTS}};
	return $self->_toBindings(\%vars, %flags);
    }
    my $renderer;
    if (defined $self->{TestTrue}) {
	$renderer = new W3C::Util::TableRenderer({%flags});
	$renderer->addData([$self->{TestTrue} ? 'true' : 'false']);
    } else {
	$renderer = new W3C::Util::TableRenderer({%flags, -dataFilter => $df});
	$renderer->addHeaders($flags{-htmlClassMap} ? 
			      [[map {s/</&lt;/g;
				     s/>/&gt;/g; $_} @{$self->{INDEX_VAR}}]] : 
			      [$self->{INDEX_VAR}]);

	my $results = $self->{Results};
	if (@$results == 0) {
	    $renderer->addData([['-no solutions-']]);
	} elsif (@$results == 1 && @{$results->[0]} == 0) {
	    $renderer->addData([['-initialized-']]);
	} else {
	    my $rows = $self->{Sorted} && !$flags{-unsorted} ? $self->{Sorted} : [0..@{$self->{Results}}-1];
	    for (my $rowNo = 0; $rowNo < @$rows; $rowNo++) {
		my $result = $results->[$rows->[$rowNo]];
		my $caveats = $self->{Caveats}[$rows->[$rowNo]];
		my ($openData, $closeData) = ('', '');
		if ($flags{-htmlClassMap} && (my $class = $flags{-htmlClassMap}{'data'})) {
		    ($openData, $closeData) = ("<div class=\"$class\">", "</div>");
		}
		my @rendered = map {$openData.$self->{-atomDictionary}->renderAtom($_, %flags).$closeData} @$result;
		if (@rendered) {
		    $renderer->addData(@rendered);
		} else {
		    $renderer->addData(['-empty row-']);
		}
		if ($flags{-proofs}) {
		    my ($open, $close) = ('', '');
		    if ($flags{-htmlClassMap} && (my $class = $flags{-htmlClassMap}{ref $self->{STATEMENTS}->[$rowNo]})) {
			($open, $close) = ("<div class=\"$class\">", "</div>");
		    }
		    my $proofStr = join ("\n", map {$open.join ("\n", $_->toString(%flags)).$close} $self->{STATEMENTS}->[$rowNo]->getTriples());
		    $renderer->addRow($proofStr);
		}
		if (@$caveats) {
		    my $caveatsStr = join ("\n", map {$_->getMessage(%flags)} @$caveats);
		    $renderer->addRow($caveatsStr);
		}
		if ($flags{-proofStreams}) {
		    foreach my $handle (keys %{$self->{ByStatementHandle}}) {
			my $proofStr = join ("\n\\ ", $handle, map {$_->toString(%flags)} @{$self->{ByStatementHandle}{$handle}[$rowNo]});
			$renderer->addRow($proofStr);
		    }
		}
	    }
	}
    }
    return $renderer->toString(%flags);
}

sub _toBindings {
    my ($self, $vars, %flags) = @_;
    my @include = map {exists $vars->{$self->{INDEX_VAR}[$_]} ? 1 : 0} 0..@{$self->{INDEX_VAR}};
    my $varsString = join(' ', map {$include[$_] ? "?$self->{INDEX_VAR}[$_]" : undef} 0..@{$self->{INDEX_VAR}}); # keys %$vars);
    my @rows = ("BINDINGS $varsString {");
    foreach my $row (@{$self->{Results}}) {
	my @cols;
	for (my $i = 0; $i < @include; $i++) {
	    if ($include[$i]) {
		push (@cols, defined $row->[$i] ? $row->[$i]->toString(%flags) : 'NULL');
	    }
	}
	my $colsString = join(' ', @cols);
	push (@rows, "($colsString)");
    }
    push (@rows, '}');
    return wantarray ? @rows : join(' ', @rows);
}
sub _before {
    my ($self) = @_;
    return join ("\n", '<'x79, 
		 $self->toString(-proofStreams => 1, 
				 -namespaceHandler => 
	    new W3C::Util::NamespaceInventor(-namespaceCreativity => 1)));
}
sub _after {
    my ($self) = @_;
    return join ("\n", '='x79, 
		 $self->toString(-proofStreams => 1, 
				 -namespaceHandler => 
	    new W3C::Util::NamespaceInventor(-namespaceCreativity => 1)), 
		 '>'x79, );
}

#use W3C::Util::NamespaceHandler;
sub _test {
    my ($self) = @_;
#    print $self->toString(-namespaceHandler => new W3C::Util::NamespaceInventor(-namespaceCreativity => 1)),"\n" if (%{$self->{ByStatementHandle}});
    foreach my $handle (keys %{$self->{ByStatementHandle}}) {
	my $thisHandle = $self->{ByStatementHandle}{$handle};
	if (ref $thisHandle ne 'ARRAY') {
	    &throw();
	}
	for (my $i = 0; $i < @{$self->{Results}}; $i++) {
#	    print "_test: ${thisHandle}->[$i] $thisHandle->[$i]\n";
	    if (ref $thisHandle->[$i] ne 'ARRAY') {
		&throw(new W3C::Util::Exception(-message => "$thisHandle->[$i] ne 'ARRAY'"));
	    }
	}
    }
}

# <ITERATOR>
sub elements {
    my ($self) = @_;
    my $ret = new W3C::Rdf::ResultSetIterator($self);
    push (@{$self->{Iterators}}, $ret);
    weaken($self->{Iterators}[-1]);
    return $ret;
}
sub removeIterator {
    my ($self, $iterator) = @_;
    for (my $i = 0; $i < @{$self->{Iterators}}; $i++) {
	if (!defined $self->{Iterators}[$i]) {
	    splice(@{$self->{Iterators}}, $i, 1);
	    $i--;
#	    print STDERR "#";
	} elsif ($self->{Iterators}[$i] == $iterator) {
	    splice(@{$self->{Iterators}}, $i, 1);
#	    print STDERR " ";
	    last;
	}
    }
#    print STDERR "*";
}
sub addRow {
    my ($self, $row) = @_;
    $row->test('add');
    push (@{$self->{Rows}}, $row);
    weaken($self->{Rows}[-1]);
}
sub removeRow {
    my ($self, $row) = @_;
    for (my $i = 0; $i < @{$self->{Rows}}; $i++) {
	if (!defined $self->{Rows}[$i]) {
	    splice(@{$self->{Rows}}, $i, 1);
	    $i--;
#	    print STDERR "#";
	} elsif ($self->{Rows}[$i] == $row) {
	    splice(@{$self->{Rows}}, $i, 1);
#	    print STDERR " ";
	    last;
	}
    }
#    print STDERR "*";
}
# </ITERATOR>

package W3C::Rdf::ChildResultSet;
@W3C::Rdf::ChildResultSet::ISA = qw(W3C::Rdf::ResultSet);
use W3C::Util::Exception;
use W3C::Rdf::Atoms qw($Value_NULL);

sub new {
    my ($proto, $parent, @parms) = @_;
    my $class = ref($proto) || $proto;
    my $self = $class->SUPER::new(@parms);
#    $self->{-sources} ||= [];
    $self->{PARENT} = $parent;
    # Overloaded values from parent constructor.

    $self->{VAR_INDEX} = $parent->{VAR_INDEX};
    $self->{INDEX_VAR} = $parent->{INDEX_VAR};
    return $self;
}

package W3C::Rdf::ResultSet;

1;

__END__

=head1 NAME

W3C::Rdf::ResultSet - query state (results and proofs)

=head1 SYNOPSIS

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

  my $atoms = new W3C::Rdf::Atoms();
  my $rs = new W3C::Rdf::ResultSet(-atomDictionary => $atoms);
  $rs->addSelect('firstName');
  for (my $e = $rs->elements; $e->hasMoreElements;) {
      my $row = $e->nextElement;
      my @matches = &getMatches($row);
      foreach my $match (@matches) {
         my $newRow = $row->duplicate();
         $newRow->addProofs([$match]);
         for (my $i = 0; $i < $self->arity; $i++) {
            $newRow->set($resultSet->getIndex('varName'), $match->getPosition($i));
         }
      }
      $row->eliminate;
  }
  my ($nodes, $statements) = $rs->gatherCollect();

=head1 DESCRIPTION

The ResultSet stores the state for a query. It associates variables with field
positions in a set of tuples. For each tuple, there is a corresponding proof,
in the form of an RdfDB containing statements supporting that tuple.

The ResultSet tuples are traversed with an Enumerator which is
returned by the C<elemens()> method.  If the ResultSet is fresh (no
tuple manipulations have occured), there is one tuple with no elements
in it.

Tuple set manipulation occurs through the maniplation of individual tuples
(see TUPLE MANIPULATION).

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

=head1 CONSTRUCTOR

=head2 new ( ATOM [, OPTS] )

ATOM is an instance of an W3C::Rdf::Atoms.

Returns a new ResultSet object

=head1 METHODS

=head2 elements ()

Get an enumerator for walking the tuples in the result set.

=head2 getIndex ( VAR )

Return the index for an already known variable or assign a new index if the
ResultSet has not yet encountered the variable.

=head2 addSelect ( VAR )

Add a variable to the list to be selected. See L<gatherCollect>

=head2 gatherCollect ()

Copy data from the solution tuples into a report. For each tuple, the fields
corresponding to variables that have been selected by the C<addSelect> method
witll be copied into the report. In addition, RdfDBs containing the proofs for
each tuple are copied into the report. The report is in the form:

  ( array of tuples, array of proofs )

=head1 TUPLE MANIPULATION

Tuple set manipulation occurs through the maniplation of individual tuples.

=head2 duplicate ()

Make the current tuple into two rows. Return the latter of the two.

=head2 addProofs ( STATEMENTS )

Associate more proofs with a given tuple.

=head2 set ( INDEX, VALUE )

Set a field identified by INDEX to VALUE.

=head2 eliminate ()

Remove this row from the solution set.

=head1 AUTHOR

Eric Prud'hommeaux <eric@w3.org>

=head1 SEE ALSO

L<W3C::Rdf::RdfDB>
L<W3C::Rdf::Atoms>

=cut
