context: using System;
  using System.Collections;
  using System.IO;
  
  using SemWeb;
  using SemWeb.Filters;
  using SemWeb.Stores;
  using SemWeb.Util;
  
  namespace SemWeb.Query {
  
  	public class QueryFormatException : ApplicationException {
  		public QueryFormatException(string message) : base(message) { }
  		public QueryFormatException(string message, Exception cause) : base(message, cause) { }
  	}
  
  	public class QueryExecutionException : ApplicationException {
  		public QueryExecutionException(string message) : base(message) { }
  		public QueryExecutionException(string message, Exception cause) : base(message, cause) { }
  	}
  	
  	public abstract class RdfFunction {
  		public abstract string Uri { get; }
  		public abstract Resource Evaluate(Resource[] args);	
  	
  	}
  
  	public abstract class Query {
  		int start = 0;
  		int limit = -1;
  		Entity queryMeta = null;
  		
  		public int ReturnStart { get { return start; } set { start = value; if (start < 0) start = 0; } }
  		
  		public int ReturnLimit { get { return limit; } set { limit = value; } }
  		
  		public Entity QueryMeta { get { return queryMeta; } set { queryMeta = value; } }
  		
  		public virtual void Run(SelectableSource source, TextWriter output) {
  			Run(source, new SparqlXmlQuerySink(output));
  		}
  
  		public abstract void Run(SelectableSource source, QueryResultSink resultsink);
  
  		public abstract string GetExplanation();
  	}
  
  	public class GraphMatch : Query {
  		// Setup information
  	
  		ArrayList setupVariablesDistinct = new ArrayList();
  		ArrayList setupValueFilters = new ArrayList();
  		ArrayList setupStatements = new ArrayList();
  		ArrayList setupOptionalStatements = new ArrayList();
  		
  		// Query model information
  		
  		bool init = false;
  		object sync = new object();
  		Variable[] variables;
  		SemWeb.Variable[] variableEntities;
  		QueryStatement[][] statements;
  		ArrayList novariablestatements = new ArrayList();
  		
  		// contains functional and inverse functional properties
  		ResSet fps = new ResSet(),
  		          ifps = new ResSet();
  		
  		private struct Variable {
  			public SemWeb.Variable Entity;
  			public LiteralFilter[] Filters;
  		}
  		
  		private struct VarOrAnchor {
  			public bool IsVariable;
  			public int VarIndex;
  			public Resource Anchor;
  			public Resource[] ArrayOfAnchor;
  			
  			public override string ToString() {
  				if (IsVariable)
  					return "?" + VarIndex;
  				else
  					return Anchor.ToString();
  			}
  			
  			public Resource[] GetValues(QueryResult union, bool entities) {
  				if (!IsVariable) {
  					if (entities)
  						return new Entity[] { (Entity)Anchor };
  					else
  						return ArrayOfAnchor;
  				} else {
  					if (union.Bindings[VarIndex] == null) return null;
  					Resource[] res = union.Bindings[VarIndex].ToArray();
  					if (!entities) return res;
  					
  					ArrayList ret = new ArrayList();
  					foreach (Resource r in res)
  						if (r is Entity)
  							ret.Add(r);
  					return (Entity[])ret.ToArray(typeof(Entity));
  				}
  			}
  		}
  		
  		private class QueryStatement { // class because of use with IComparer
  			public bool Optional;
  			public VarOrAnchor 
  				Subject,
  				Predicate,
  				Object;
  			
  			public int NumVars() {
  				return (Subject.IsVariable ? 1 : 0)
  					+ (Predicate.IsVariable ? 1 : 0)
  					+ (Object.IsVariable ? 1 : 0);
  			}
  			
  			public override string ToString() {
  				return Subject + " " + Predicate + " " + Object;
  			}
  		}
  		
  		class QueryResult {
  			public ResSet[] Bindings;
  			public bool[] StatementMatched;
  			
  			public QueryResult(GraphMatch q) {
  				Bindings = new ResSet[q.variables.Length];
  				StatementMatched = new bool[q.statements.Length];
  			}
  			private QueryResult(int x, int y) {
  				Bindings = new ResSet[x];
  				StatementMatched = new bool[y];
  			}
  			public void Add(QueryStatement qs, Statement bs) {
  				if (qs.Subject.IsVariable) Add(qs.Subject.VarIndex, bs.Subject);
  				if (qs.Predicate.IsVariable) Add(qs.Predicate.VarIndex, bs.Predicate);
  				if (qs.Object.IsVariable) Add(qs.Object.VarIndex, bs.Object);
  			}
  			void Add(int varIndex, Resource binding) {
  				if (Bindings[varIndex] == null) Bindings[varIndex] = new ResSet();
  				Bindings[varIndex].Add(binding);
  			}
  			public void Clear(QueryStatement qs) {
  				if (qs.Subject.IsVariable && Bindings[qs.Subject.VarIndex] != null) Bindings[qs.Subject.VarIndex].Clear();
  				if (qs.Predicate.IsVariable && Bindings[qs.Predicate.VarIndex] != null) Bindings[qs.Predicate.VarIndex].Clear();
  				if (qs.Object.IsVariable && Bindings[qs.Object.VarIndex] != null) Bindings[qs.Object.VarIndex].Clear();
  			}
  			public void Set(QueryStatement qs, Statement bs) {
  				if (qs.Subject.IsVariable) Set(qs.Subject.VarIndex, bs.Subject);
  				if (qs.Predicate.IsVariable) Set(qs.Predicate.VarIndex, bs.Predicate);
  				if (qs.Object.IsVariable) Set(qs.Object.VarIndex, bs.Object);
  			}
  			void Set(int varIndex, Resource binding) {
  				if (Bindings[varIndex] == null) Bindings[varIndex] = new ResSet();
  				else Bindings[varIndex].Clear();
  				Bindings[varIndex].Add(binding);
  			}
  			public QueryResult Clone() {
  				QueryResult r = new QueryResult(Bindings.Length, StatementMatched.Length);
  				for (int i = 0; i < Bindings.Length; i++)
  					if (Bindings[i] != null)
  						r.Bindings[i] = Bindings[i].Clone();
  				for (int i = 0; i < StatementMatched.Length; i++)
  					r.StatementMatched[i] = StatementMatched[i];
  				return r;
  			}
  		}
  		
  		class BindingSet {
  			public ArrayList Results = new ArrayList();
  			public QueryResult Union;
  			
  			public BindingSet(GraphMatch q) {
  				Union = new QueryResult(q);
  			}
  		}
  		
  		public void MakeDistinct(BNode a, BNode b) {
  			SetupVariablesDistinct d = new SetupVariablesDistinct();
  			d.a = a;
  			d.b = b;
  			setupVariablesDistinct.Add(d);
  		}
  		
  		public void AddValueFilter(Entity entity, LiteralFilter filter) {
  			SetupValueFilter d = new SetupValueFilter();
  			d.a = entity;
  			d.b = filter;
  			setupValueFilters.Add(d);
  		}
  		
  		public void AddEdge(Statement filter) {
  			setupStatements.Add(filter);
  		}
  
  		public void AddOptionalEdge(Statement filter) {
  			setupOptionalStatements.Add(filter);
  		}
  		
  		private class SetupVariablesDistinct {
  			public Entity a, b;
  		}
  		private class SetupValueFilter {
  			public Entity a;
  			public LiteralFilter b;
  		}
  		
  		private void CheckInit() {
  			lock (sync) {
  				if (!init) {
  					Init();
  					init = true;
  				}
  			}
  		}
  
  		private static Entity qLimit = "http://purl.oclc.org/NET/rsquary/returnLimit";
  		private static Entity qStart = "http://purl.oclc.org/NET/rsquary/returnStart";
  		private static Entity qDistinctFrom = "http://purl.oclc.org/NET/rsquary/distinctFrom";
  		private static Entity qOptional = "http://purl.oclc.org/NET/rsquary/optional";
  		
  		public GraphMatch() {
  		}
  		
  		public GraphMatch(RdfReader query) :
  			this(new MemoryStore(query),
  				query.BaseUri == null ? null : new Entity(query.BaseUri)) {
  		}
  
  		public GraphMatch(Store queryModel) : this(queryModel, null) {
  		}
  		
  		private GraphMatch(Store queryModel, Entity queryNode) {
  			// Find the query options
  			if (queryNode != null) {
  				ReturnStart = GetIntOption(queryModel, queryNode, qStart);
  				ReturnLimit = GetIntOption(queryModel, queryNode, qLimit);
  			}
  
  			// Search the query for 'distinct' predicates between variables.
  			foreach (Statement s in queryModel.Select(new Statement(null, qDistinctFrom, null))) {
  				if (!(s.Object is BNode)) continue;
  				MakeDistinct((BNode)s.Subject, (BNode)s.Object);
  			}
  			
  			// Add all statements except the query predicates and value filters into a
  			// new store with just the statements relevant to the search.
  			foreach (Statement s in queryModel.Select(Statement.All)) {
  				if (IsQueryPredicate(s.Predicate)) continue;
  				
  				/*if (s.Predicate.Uri != null && extraValueFilters != null && extraValueFilters.Contains(s.Predicate.Uri)) {
  					ValueFilterFactory f = (ValueFilterFactory)extraValueFilters[s.Predicate.Uri];
  					AddValueFilter(s.Subject, f.GetValueFilter(s.Predicate.Uri, s.Object));
  					continue;
  				} else {
  					ValueFilter f = ValueFilter.GetValueFilter(s.Predicate, s.Object);
  					if (f != null) {
  						AddValueFilter(s.Subject, f);
  						continue;
  					}
  				}*/
  				
  				if (s.Meta == Statement.DefaultMeta)
  					AddEdge(s);
  				else if (queryNode != null && queryModel.Contains(new Statement(queryNode, qOptional, s.Meta)))
  					AddOptionalEdge(s);
  			}
  		}
  		
  		private int GetIntOption(Store queryModel, Entity query, Entity predicate) {
  			Resource[] rr = queryModel.SelectObjects(query, predicate);
  			if (rr.Length == 0) return -1;
  			Resource r = rr[0];
  			if (r == null || !(r is Literal)) return -1;
  			try {
  				return int.Parse(((Literal)r).Value);
  			} catch (Exception e) {
  				return -1;
  			}
  		}		
  
  		private bool IsQueryPredicate(Entity e) {
  			if (e == qDistinctFrom) return true;
  			if (e == qLimit) return true;
  			if (e == qStart) return true;
  			if (e == qOptional) return true;
  			return false;
  		}
  		
  		public override string GetExplanation() {
  			CheckInit();
  			string ret = "Query:\n";
  			foreach (Statement s in novariablestatements)
  				ret += " Check: " + s + "\n";
  			foreach (QueryStatement[] sgroup in statements) {
  				ret += " ";
  				if (sgroup.Length != 1)
  					ret += "{";
  				foreach (QueryStatement s in sgroup) {
  					ret += s.ToString();
  					if (s.Optional) ret += " (Optional)";
  					if (sgroup.Length != 1)
  						ret += " & ";
  				}
  				if (sgroup.Length != 1)
  					ret += "}";
  				ret += "\n";
  			}
  			return ret;
  		}
  		
  		public override void Run(SelectableSource targetModel, QueryResultSink result) {
  			CheckInit();
  			
  			foreach (Statement s in novariablestatements)
  				if (!targetModel.Contains(s))
  					return;
  			
  			VariableBinding[] finalbindings = new VariableBinding[variables.Length];
  			for (int i = 0; i < variables.Length; i++)
  				finalbindings[i].Variable = variableEntities[i];
  			
  			result.Init(finalbindings, true, false);
  			
  			Debug("Begnning Query");
  			
  			BindingSet bindings = new BindingSet(this);
  			for (int group = 0; group < statements.Length; group++) {
  				bool ret = Query(group, bindings, targetModel);
  				if (!ret) {
  					// A false return value indicates the query
  					// certainly failed -- a non-optional statement
  					// failed to match at all.
  					result.Finished();
  					return;
  				}
  			}
  
  			int ctr = -1;
  			foreach (QueryResult r in bindings.Results) {
  				Permutation permutation = new Permutation(r.Bindings);
  				do {
  					ctr++;
  					if (ctr < ReturnStart) continue;
  					for (int i = 0; i < variables.Length; i++)
  						finalbindings[i].Target = permutation[i];
  					result.Add(finalbindings);
  					if (ReturnLimit != -1 && ctr == ReturnStart+ReturnLimit) break;	
  				} while (permutation.Next());
  				if (ReturnLimit != -1 && ctr == ReturnStart+ReturnLimit) break;	
  			}
  
  			
  			result.Finished();
  		}
  		
  		class Permutation {
  			public int[] index;
  			public Resource[][] values;
  			
  			public Resource this[int i] {
  				get {
  					return values[i][index[i]];
  				}
  			}
  			
  			public Permutation(ResSet[] bindings) {
  				index = new int[bindings.Length];
  				values = new Resource[bindings.Length][];
  				for (int i = 0; i < bindings.Length; i++) {
  					values[i] = new Resource[bindings[i] == null ? 1 : bindings[i].Count];
  					if (bindings[i] != null) {
  						int ctr = 0;
  						foreach (Resource r in bindings[i])
  							values[i][ctr++] = r;
  					}
  				}
  			}
  			public bool Next() {
  				for (int i = 0; i < index.Length; i++) {
  					index[i]++;
  					if (index[i] < values[i].Length) break;
  					
  					index[i] = 0;
  					if (i == index.Length-1) return false;
  				}
  				return true;
  			}
  		}
  		
  		private void Debug(string message) {
  			//Console.Error.WriteLine(message);
  		}
  		
  		class BindingEnumerator {
  			IEnumerator[] loops = new IEnumerator[3];
  			int loop = 0;
  			
  			public BindingEnumerator(QueryStatement qs, QueryResult bindings) {
  				loops[0] = GetBindings(qs.Subject, bindings);
  				loops[1] = GetBindings(qs.Predicate, bindings);
  				loops[2] = GetBindings(qs.Object, bindings);
  			}
  			
  			public bool MoveNext(out Entity s, out Entity p, out Resource o) {
  				while (true) {
  					bool b = loops[loop].MoveNext();
  					if (!b) {
  						 if (loop == 0) { s = null; p = null; o = null; return false; }
  						 loops[loop].Reset();
  						 loop--;
  						 continue;
  					}
  					
  					if (loop <= 1) {
  						object obj = loops[loop].Current;
  						if (obj != null && !(obj is Entity)) continue;
  					}
  					
  					if (loop < 2) { loop++; continue; }
  					
  					s = loops[0].Current as Entity; 
  					p = loops[1].Current as Entity; 
  					o = loops[2].Current as Resource;
  					return true; 
  				}
  			}
  		}
  
  		private bool Query(int groupindex, BindingSet bindings, SelectableSource targetModel) {
  			QueryStatement[] group = statements[groupindex];
  			
  			QueryStatement qs = group[0];
  			
  			int numMultiplyBound = IsMultiplyBound(qs.Subject, bindings)
  				+ IsMultiplyBound(qs.Predicate, bindings)
  				+ IsMultiplyBound(qs.Object, bindings);
  			
  			if (numMultiplyBound >= 1) {
  				// If there is one or more multiply-bound variable,
  				// then we need to iterate through the permutations
  				// of the variables in the statement.
  				
  				Debug(qs.ToString() + " Something Multiply Bound");
  				
  				MemoryStore matches = new MemoryStore();
  				targetModel.Select(
  					new SelectFilter(
  						(Entity[])qs.Subject.GetValues(bindings.Union, true),
  						(Entity[])qs.Predicate.GetValues(bindings.Union, true),
  						qs.Object.GetValues(bindings.Union, false),
  						QueryMeta == null ? null : new Entity[] { QueryMeta }
  						),
  					new ClearMetaDupCheck(matches));
  				
  				Debug("\t" + matches.StatementCount + " Matches");
  				
  				if (matches.StatementCount == 0) {
  					// This statement doesn't match any of
  					// the existing bindings.  If this was
  					// optional, preserve the bindings.
  					return qs.Optional;
  				}
  				
  				// We need to preserve the pairings of
  				// the multiply bound variable with the matching
  				// statements.
  				
  				ArrayList newbindings = new ArrayList();
  				
  				if (!qs.Optional) bindings.Union.Clear(qs);
  				
  				foreach (QueryResult binding in bindings.Results) {
  					// Break apart the permutations in this binding.
  					BindingEnumerator enumer2 = new BindingEnumerator(qs, binding);
  					Entity s, p;
  					Resource o;
  					while (enumer2.MoveNext(out s, out p, out o)) {
  						// Get the matching statements from the union query
  						Statement bs = new Statement(s, p, o);
  						MemoryStore innermatches = matches.Select(bs).Load();
  						
  						// If no matches, the binding didn't match the filter.
  						if (innermatches.StatementCount == 0) {
  							if (qs.Optional) {
  								// Preserve the binding.
  								QueryResult bc = binding.Clone();
  								bc.Set(qs, bs);
  								newbindings.Add(bc);
  								continue;
  							} else {
  								// Toss out the binding.
  								continue;
  							}
  						}
  						
  						for (int si = 0; si < innermatches.StatementCount; si++) {
  							Statement m = innermatches[si];
  							if (!MatchesFilters(m, qs, targetModel)) {
  								if (qs.Optional) {
  									QueryResult bc = binding.Clone();
  									bc.Set(qs, bs);
  									newbindings.Add(bc);
  								}
  								continue;
  							}
  							bindings.Union.Add(qs, m);
  							
  							QueryResult r = binding.Clone();
  							r.Set(qs, m);
  							r.StatementMatched[groupindex] = true;
  							newbindings.Add(r);
  						}
  					}
  				}
  				
  				bindings.Results = newbindings;
  				
  			} else {
  				// There are no multiply bound variables, but if
  				// there are more than two unbound variables,
  				// we need to be sure to preserve the pairings
  				// of the matching values.
  			
  				int numUnbound = IsUnbound(qs.Subject, bindings)
  					+ IsUnbound(qs.Predicate, bindings)
  					+ IsUnbound(qs.Object, bindings);
  					
  				bool sunbound = IsUnbound(qs.Subject, bindings) == 1;
  				bool punbound = IsUnbound(qs.Predicate, bindings) == 1;
  				bool ounbound = IsUnbound(qs.Object, bindings) == 1;
  				
  				Statement s = GetStatement(qs, bindings);
  				
  				// If we couldn't get a statement out of this,
  				// then if this was not an optional filter,
  				// fail.  If this was optional, don't change
  				// the bindings any. 
  				if (s == StatementFailed) return qs.Optional;
  				
  				if (numUnbound == 0) {
  					Debug(qs.ToString() + " All bound");
  					
  					// All variables are singly bound already.
  					// We can just test if the statement exists.
  					if (targetModel.Contains(s)) {
  						// Mark each binding that it matched this statement.
  						foreach (QueryResult r in bindings.Results)
  							r.StatementMatched[groupindex] = true;
  					} else {
  						return qs.Optional;
  					}
  				
  				} else if (numUnbound == 1) {
  					Debug(qs.ToString() + " 1 Unbound");
  				
  					// There is just one unbound variable.  The others
  					// are not multiply bound, so they must be uniquely
  					// bound (but they may not be bound in all results).
  					// Run a combined select to find all possible values
  					// of the unbound variable at once, and set these to
  					// be the values of the variable for matching results.
  					
  					ResSet values = new ResSet();
  					MemoryStore ms = new MemoryStore();
  					targetModel.Select(s, ms);
  					for (int si = 0; si < ms.StatementCount; si++) {
  						Statement match = ms[si];
  						if (!MatchesFilters(match, qs, targetModel)) continue;
  						if (sunbound) values.Add(match.Subject);
  						if (punbound) values.Add(match.Predicate);
  						if (ounbound) values.Add(match.Object);
  					}
  					
  					Debug("\t" + values.Count + " matches");
  					
  					if (values.Count == 0)
  						return qs.Optional;
  						
  					int varIndex = -1;
  					if (sunbound) varIndex = qs.Subject.VarIndex;
  					if (punbound) varIndex = qs.Predicate.VarIndex;
  					if (ounbound) varIndex = qs.Object.VarIndex;
  					
  					if (bindings.Results.Count == 0)
  						bindings.Results.Add(new QueryResult(this));
  					
  					bindings.Union.Bindings[varIndex] = new ResSet();
  					foreach (Resource r in values)
  						bindings.Union.Bindings[varIndex].Add(r);
  						
  					foreach (QueryResult r in bindings.Results) {
  						// Check that the bound variables are bound in this result.
  						// If it is bound, it will be bound to the correct resource,
  						// but it might not be bound at all if an optional statement
  						// failed to match -- in which case, don't modify the binding.
  						if (qs.Subject.IsVariable && !sunbound && r.Bindings[qs.Subject.VarIndex] == null) continue;
  						if (qs.Predicate.IsVariable && !punbound && r.Bindings[qs.Predicate.VarIndex] == null) continue;
  						if (qs.Object.IsVariable && !ounbound && r.Bindings[qs.Object.VarIndex] == null) continue;
  					
  						r.Bindings[varIndex] = values;
  						r.StatementMatched[groupindex] = true;
  					}
  					
  				} else {
  					// There are two or more unbound variables, the
  					// third variable being uniquely bound, if bound.
  					// Keep track of the pairing of unbound variables.
  					
  					if (numUnbound == 3)
  						throw new QueryExecutionException("Query would select all statements in the store.");
  					
  					Debug(qs.ToString() + " 2 or 3 Unbound");
  				
  					if (bindings.Results.Count == 0)
  						bindings.Results.Add(new QueryResult(this));
  						
  					ArrayList newbindings = new ArrayList();
  					MemoryStore ms = new MemoryStore();
  					targetModel.Select(s, ms);
  					for (int si = 0; si < ms.StatementCount; si++) {
  						Statement match = ms[si];
  						if (!MatchesFilters(match, qs, targetModel)) continue;
  						bindings.Union.Add(qs, match);
  						foreach (QueryResult r in bindings.Results) {
  							if (numUnbound == 2) {
  								// Check that the bound variable is bound in this result.
  								// If it is bound, it will be bound to the correct resource,
  								// but it might not be bound at all if an optional statement
  								// failed to match -- in which case, preserve the binding if
  								// this was an optional statement.
  								bool matches = true;
  								if (qs.Subject.IsVariable && !sunbound && r.Bindings[qs.Subject.VarIndex] == null) matches = false;
  								if (qs.Predicate.IsVariable && !punbound && r.Bindings[qs.Predicate.VarIndex] == null) matches = false;
  								if (qs.Object.IsVariable && !ounbound && r.Bindings[qs.Object.VarIndex] == null) matches = false;
  								if (!matches) {
  									if (qs.Optional)
  										newbindings.Add(r);
  									continue;
  								}
  							}
  						
  							QueryResult r2 = r.Clone();
  							r2.Add(qs, match);
  							r2.StatementMatched[groupindex] = true;
  							newbindings.Add(r2);
  						}
  					}
  					if (newbindings.Count == 0)
  						return qs.Optional; // don't clear out bindings if this was optional and it failed
  					bindings.Results = newbindings;
  				}
  			}
  			
  			return true;
  		}
  		
  		static Resource[] ResourceArrayNull = new Resource[] { null };
  		
  		private static IEnumerator GetBindings(VarOrAnchor e, QueryResult bindings) {
  			if (!e.IsVariable) {
  				if (e.ArrayOfAnchor == null)
  					e.ArrayOfAnchor = new Resource[] { e.Anchor };
  				return e.ArrayOfAnchor.GetEnumerator();
  			}
  			if (bindings.Bindings[e.VarIndex] == null) return ResourceArrayNull.GetEnumerator();
  			return bindings.Bindings[e.VarIndex].Items.GetEnumerator();
  		}
  		private int IsMultiplyBound(VarOrAnchor e, BindingSet bindings) {
  
gt: 			if (!e.IsVariable) return 0;