Logo Search packages:      
Sourcecode: beagle version File versions  Download package

Query.cs

using System;
using System.Collections;
using System.IO;

using SemWeb;
using SemWeb.Stores;
using SemWeb.Util;

namespace SemWeb.Query {
      public class QueryException : ApplicationException {
            public QueryException(string message) : base(message) {
            }
                  
            public QueryException(string message, Exception cause) : base(message, cause) {
            }
      }
      
      public class QueryEngine {
            // Setup information
      
            ArrayList setupVariables = new ArrayList();
            ArrayList setupVariablesDistinct = new ArrayList();
            ArrayList setupValueFilters = new ArrayList();
            ArrayList setupStatements = new ArrayList();
            ArrayList setupOptionalStatements = new ArrayList();
            
            int start = -1;
            int limit = -1;
            
            // Query model information
            
            bool init = false;
            object sync = new object();
            Variable[] variables;
            Entity[] variableEntities;
            QueryStatement[][] statements;
            
            // contains functional and inverse functional properties
            ResSet fps = new ResSet(),
                      ifps = new ResSet();
            
            private struct Variable {
                  public Entity Entity;
                  public ValueFilter[] 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();
                  }
            }
            
            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 QueryResult(QueryEngine q) {
                        Bindings = new ResSet[q.variables.Length];
                  }
                  private QueryResult(int x) {
                        Bindings = new ResSet[x];
                  }
                  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);
                        for (int i = 0; i < Bindings.Length; i++)
                              if (Bindings[i] != null)
                                    r.Bindings[i] = Bindings[i].Clone();
                        return r;
                  }
            }
            
            class BindingSet {
                  public ArrayList Results = new ArrayList();
                  public QueryResult Union;
                  
                  public BindingSet(QueryEngine q) {
                        Union = new QueryResult(q);
                  }
            }
                              
            public void Select(Entity entity) {
                  if (entity.Uri == null) throw new QueryException("Anonymous nodes are automatically considered variables.");
                  if (setupVariables.Contains(entity)) return;
                  setupVariables.Add(entity);
            }

            public void MakeDistinct(Entity a, Entity b) {
                  SetupVariablesDistinct d = new SetupVariablesDistinct();
                  d.a = a;
                  d.b = b;
                  setupVariablesDistinct.Add(d);
            }
            
            public void AddValueFilter(Entity entity, ValueFilter filter) {
                  SetupValueFilter d = new SetupValueFilter();
                  d.a = entity;
                  d.b = filter;
                  setupValueFilters.Add(d);
            }
            
            public void AddFilter(Statement filter) {
                  setupStatements.Add(filter);
            }

            public void AddOptionalFilter(Statement filter) {
                  setupOptionalStatements.Add(filter);
            }
            
            public int ReturnStart { get { return start; } set { start = value; } }
            
            public int ReturnLimit { get { return limit; } set { limit = value; } }
            
            private class SetupVariablesDistinct {
                  public Entity a, b;
            }
            private class SetupValueFilter {
                  public Entity a;
                  public ValueFilter b;
            }
            
            public void Query(Store targetModel, QueryResultSink result) {
                  lock (sync) {
                        if (!init) {
                              Init();
                              init = true;
                        }
                  }
                  
                  result.Init(variableEntities);
                  
                  BindingSet bindings = new BindingSet(this);
                  foreach (QueryStatement[] group in statements) {
                        bool ret = Query(group, bindings, targetModel);
                        if (!ret) {
                              // A false return value indicates the query
                              // certainly failed.
                              result.Finished();
                              return;
                        }
                  }

                  VariableBinding[] finalbindings = new VariableBinding[variables.Length];
                  for (int i = 0; i < variables.Length; i++)
                        finalbindings[i].Variable = variableEntities[i];
                  
                  int ctr = -1;
                  foreach (QueryResult r in bindings.Results) {
                        Permutation permutation = new Permutation(r.Bindings);
                        do {
                              ctr++;
                              if (ctr < start) continue;
                              for (int i = 0; i < variables.Length; i++)
                                    finalbindings[i].Target = permutation[i];
                              result.Add(finalbindings);
                              if (ctr == start+limit) break;      
                        } while (permutation.Next());
                        if (ctr == start+limit) 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(QueryStatement[] group, BindingSet bindings, Store targetModel) {
                  if (group.Length == 1) {
                        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");
                              
                              Entity s, p;
                              Resource o;
                              
                              ArrayList templates = new ArrayList();
                              BindingEnumerator enumer = new BindingEnumerator(qs, bindings.Union);
                              while (enumer.MoveNext(out s, out p, out o))
                                    templates.Add(new Statement(s, p, o));
                              
                              Debug("\t" + templates.Count + " Templates");
                              
                              // But we still need to preserve the pairings of
                              // the multiply bound variable with the matching
                              // statements.
                              
                              MemoryStore matches1 = targetModel.Select((Statement[])templates.ToArray(typeof(Statement)));
                              
                              Debug("\t" + matches1.StatementCount + " Matches");
                              
                              // The memory store that we get back from a select
                              // won't do indexing, but indexing will help.
                              MemoryStore matches = new MemoryStore();
                              matches.Import(matches1);

                              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);
                                    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);
                                          
                                          // If no matches, the binding didn't match the filter.
                                          if (innermatches.StatementCount == 0) {
                                                if (qs.Optional) {
                                                      // Preserve the binding.
                                                      newbindings.Add(binding);
                                                } else {
                                                      // Toss out the binding.
                                                      continue;
                                                }
                                          }
                                          
                                          foreach (Statement m in innermatches) {
                                                if (!MatchesFilters(m, qs, targetModel)) {
                                                      if (qs.Optional) newbindings.Add(binding);
                                                      continue;
                                                }
                                                bindings.Union.Add(qs, m);
                                                
                                                QueryResult r = binding.Clone();
                                                r.Set(qs, m);
                                                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)
                                          && !qs.Optional)
                                          return false;
                              
                              } 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();
                                    foreach (Statement match in targetModel.Select(s)) {
                                          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;
                                    }
                                    
                              } else {
                                    // There are two or more unbound variables, the
                                    // third variable being uniquely bound, if bound.
                                    // Keep track of the pairing of unbound variables.
                                    
                                    Debug(qs.ToString() + " 2 or 3 Unbound");
                              
                                    if (bindings.Results.Count == 0)
                                          bindings.Results.Add(new QueryResult(this));
                                          
                                    ArrayList newbindings = new ArrayList();
                                    foreach (Statement match in targetModel.Select(s)) {
                                          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);
                                                newbindings.Add(r2);
                                          }
                                    }
                                    if (qs.Optional && newbindings.Count == 0)
                                          return true; // don't clear out bindings
                                    bindings.Results = newbindings;
                              }
                        }
                  
                  } else {
                        // There is more than one statement in the group.
                        // These are never optional.

                        Debug("Statement group.");
            
                        VarOrAnchor var = new VarOrAnchor();
                        foreach (QueryStatement qs in group) {
                              if (qs.Subject.IsVariable && bindings.Union.Bindings[qs.Subject.VarIndex] == null) var = qs.Subject;
                              if (qs.Predicate.IsVariable && bindings.Union.Bindings[qs.Predicate.VarIndex] == null) var = qs.Predicate;
                              if (qs.Object.IsVariable && bindings.Union.Bindings[qs.Object.VarIndex] == null) var = qs.Object;
                              break;
                        }
                        // The variable should be unbound so far.
                        if (bindings.Union.Bindings[var.VarIndex] != null)
                              throw new Exception();
                        
                        ArrayList findstatements = new ArrayList();
                        foreach (QueryStatement qs in group) {
                              Statement s = GetStatement(qs, bindings);
                              if (s == StatementFailed) return false;
                              findstatements.Add(s);
                        }
                        
                        ResSet values = new ResSet();
                        foreach (Entity r in targetModel.FindEntities((Statement[])findstatements.ToArray(typeof(Statement)))) {
                              if (!MatchesFilters(r, var, targetModel)) continue;
                              values.Add(r);
                        }
                        if (values.Count == 0) return false;
                        
                        bindings.Union.Bindings[var.VarIndex] = values;
                        
                        if (bindings.Results.Count == 0)
                              bindings.Results.Add(new QueryResult(this));
                  
                        foreach (QueryResult result in bindings.Results)
                              result.Bindings[var.VarIndex] = values;
                  }
                  
                  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) {
                  if (!e.IsVariable) return 0;
                  if (bindings.Union.Bindings[e.VarIndex] == null) return 0;
                  if (bindings.Union.Bindings[e.VarIndex].Items.Count == 1) return 0;
                  return 1;
            }
            private int IsUnbound(VarOrAnchor e, BindingSet bindings) {
                  if (!e.IsVariable) return 0;
                  if (bindings.Union.Bindings[e.VarIndex] == null) return 1;
                  return 0;
            }
            
            private Resource GetUniqueBinding(VarOrAnchor e, BindingSet bindings) {
                  if (!e.IsVariable) return e.Anchor;
                  if (bindings.Union.Bindings[e.VarIndex] == null || bindings.Union.Bindings[e.VarIndex].Count == 0) return null;
                  if (bindings.Union.Bindings[e.VarIndex].Count > 1) throw new Exception();
                  foreach (Resource r in bindings.Union.Bindings[e.VarIndex].Items)
                        return r;
                  throw new Exception();
            }
            
            Statement StatementFailed = new Statement(null, null, null);
            
            private Statement GetStatement(QueryStatement sq, BindingSet bindings) {
                  Resource s = GetUniqueBinding(sq.Subject, bindings);
                  Resource p = GetUniqueBinding(sq.Predicate, bindings);
                  Resource o = GetUniqueBinding(sq.Object, bindings);
                  if (s is Literal || p is Literal) return StatementFailed;
                  return new Statement((Entity)s, (Entity)p, o);
            }
            
            bool MatchesFilters(Statement s, QueryStatement q, Store targetModel) {
                  return MatchesFilters(s.Subject, q.Subject, targetModel)
                        && MatchesFilters(s.Predicate, q.Predicate, targetModel)
                        && MatchesFilters(s.Object, q.Object, targetModel);
            }
            
            bool MatchesFilters(Resource e, VarOrAnchor var, Store targetModel) {
                  if (!var.IsVariable) return true;
                  foreach (ValueFilter f in variables[var.VarIndex].Filters) {
                        if (!f.Filter(e, targetModel)) return false;
                  }
                  return true;
            }
            
            private void Init() {
                  // Any anonymous nodes in the graph are SelectFirst nodes
                  foreach (Statement s in setupStatements) {
                        InitAnonVariable(s.Subject);
                        InitAnonVariable(s.Predicate);
                        InitAnonVariable(s.Object);
                  }
                  foreach (Statement s in setupOptionalStatements) {
                        InitAnonVariable(s.Subject);
                        InitAnonVariable(s.Predicate);
                        InitAnonVariable(s.Object);
                  }
            
                  // Set up the variables array.
                  variables = new Variable[setupVariables.Count];
                  variableEntities = new Entity[variables.Length];
                  Hashtable varIndex = new Hashtable();
                  for (int i = 0; i < variables.Length; i++) {
                        variables[i].Entity = (Entity)setupVariables[i];
                        variableEntities[i] = variables[i].Entity;
                        varIndex[variables[i].Entity] = i;
                        
                        ArrayList filters = new ArrayList();
                        foreach (SetupValueFilter filter in setupValueFilters) {
                              if (filter.a == variables[i].Entity)
                                    filters.Add(filter.b);
                        }
                        
                        variables[i].Filters = (ValueFilter[])filters.ToArray(typeof(ValueFilter));
                  }
                  
                  // Set up the statements
                  ArrayList statements = new ArrayList();
                  foreach (Statement st in setupStatements)
                        InitSetStatement(st, statements, varIndex, false);
                  foreach (Statement st in setupOptionalStatements)
                        InitSetStatement(st, statements, varIndex, true);
                  
                  // Order the statements in the most efficient order
                  // for the recursive query.
                  Hashtable setVars = new Hashtable();
                  ArrayList sgroups = new ArrayList();
                  while (statements.Count > 0) {
                        QueryStatement[] group = InitBuildNode(statements, setVars);
                        sgroups.Add(group);
                        foreach (QueryStatement qs in group) {
                              if (qs.Subject.IsVariable) setVars[qs.Subject.VarIndex] = setVars;
                              if (qs.Predicate.IsVariable) setVars[qs.Predicate.VarIndex] = setVars;
                              if (qs.Object.IsVariable) setVars[qs.Object.VarIndex] = setVars;
                        }
                  }
                  
                  this.statements = (QueryStatement[][])sgroups.ToArray(typeof(QueryStatement[]));
            }
            
            private void InitAnonVariable(Resource r) {
                  if (r is Entity && r.Uri == null)
                        setupVariables.Add(r);
            }
            
            private void InitSetStatement(Statement st, ArrayList statements, Hashtable varIndex, bool optional) {
                  QueryStatement qs = new QueryStatement();
                  
                  InitSetStatement(st.Subject, ref qs.Subject, varIndex);
                  InitSetStatement(st.Predicate, ref qs.Predicate, varIndex);
                  InitSetStatement(st.Object, ref qs.Object, varIndex);
                  
                  qs.Optional = optional;
                  
                  // If this statement has no variables, just drop it.
                  if (!qs.Subject.IsVariable && !qs.Predicate.IsVariable && !qs.Object.IsVariable)
                        return;

                  statements.Add(qs);
            }
            
            private void InitSetStatement(Resource ent, ref VarOrAnchor st, Hashtable varIndex) {
                  if (!varIndex.ContainsKey(ent)) {
                        st.IsVariable = false;
                        st.Anchor = ent;
                  } else {
                        st.IsVariable = true;
                        st.VarIndex = (int)varIndex[ent];
                  }
            }
            
            private class QueryStatementComparer : IComparer {
                  Hashtable setVars;
                  ResSet fps, ifps;
                  
                  public QueryStatementComparer(Hashtable setVars, ResSet fps, ResSet ifps) {
                        this.setVars = setVars;
                        this.fps = fps;
                        this.ifps = ifps;
                  }
            
                  int IComparer.Compare(object a, object b) {
                        return Compare((QueryStatement)a, (QueryStatement)b);
                  }
                  
                  public int Compare(QueryStatement a, QueryStatement b) {
                        int optional = a.Optional.CompareTo(b.Optional);
                        if (optional != 0) return optional;
                        
                        int numvars = NumVars(a).CompareTo(NumVars(b));
                        if (numvars != 0) return numvars;
                        
                        int complexity = Complexity(a).CompareTo(Complexity(b));
                        return complexity;
                  }
                  
                  private int NumVars(QueryStatement s) {
                        int ret = 0;
                        if (s.Subject.IsVariable && !setVars.ContainsKey(s.Subject.VarIndex))
                              ret++;
                        if (s.Predicate.IsVariable && !setVars.ContainsKey(s.Predicate.VarIndex))
                              ret++;
                        if (s.Object.IsVariable && !setVars.ContainsKey(s.Object.VarIndex))
                              ret++;
                        return ret;
                  }
                  
                  private int Complexity(QueryStatement s) {
                        if (s.Predicate.IsVariable) return 2;
                        if ((!s.Subject.IsVariable || setVars.ContainsKey(s.Subject.VarIndex))
                              && fps.Contains(s.Predicate.Anchor))
                              return 0;
                        if ((!s.Object.IsVariable || setVars.ContainsKey(s.Object.VarIndex))
                              && ifps.Contains(s.Predicate.Anchor))
                              return 0;
                        return 1;
                  }
            }
            
            private QueryStatement[] InitBuildNode(ArrayList statements, Hashtable setVars) {
                  // Get the best statements to consider
                  // Because we can consider statements in groups, we need
                  // a list of lists.
                  QueryStatementComparer comparer = new QueryStatementComparer(setVars, fps, ifps);
                  ArrayList considerations = new ArrayList();
                  for (int i = 0; i < statements.Count; i++) {
                        QueryStatement next = (QueryStatement)statements[i];
                        int comp = 1;
                        if (considerations.Count > 0) {
                              QueryStatement curcomp = (QueryStatement) ((ArrayList)considerations[0])[0];
                              comp = comparer.Compare(curcomp, next);
                        }
                        
                        if (comp < 0) // next is worse than current
                              continue;
                        
                        if (comp > 0) // clear out worse possibilities
                              considerations.Clear();
                        
                        // next is equal to what we have.  we can either
                        // group it with an existing statement, or make
                        // a new group out of it.
                        
                        bool grouped = false;
                        foreach (ArrayList g in considerations) {
                              // We can group next in g, if the only
                              // unset variables in next are the only
                              // unset variables in the statements in g.
                              // AND if nothing else is a variable,
                              // because of having multiply-bound variables
                              // with FindEntities.  And none may be optional.
                              QueryStatement s = (QueryStatement)g[0];
                              int su = InitBuildNodeGetUniqueUnsetVar(s, setVars);
                              int nu = InitBuildNodeGetUniqueUnsetVar(next, setVars);
                              if (su == nu && su != -1 && s.NumVars() == 1 && next.NumVars() == 1
                                    && !s.Optional && !next.Optional) {
                                    g.Add(next);
                                    grouped = true;
                                    break;
                              }
                        }
                        if (grouped) continue;
                        
                        // we didn't group it with anything existing,
                        // so make a new group
                        
                        ArrayList group = new ArrayList();
                        group.Add(next);
                        considerations.Add(group);
                  }
                  
                  // Pick the group with the most number of statements.
                  ArrayList bestgroup = null;
                  foreach (ArrayList g in considerations) {
                        if (bestgroup == null || bestgroup.Count < g.Count)
                              bestgroup = g;
                  }
                  
                  foreach (QueryStatement qs in bestgroup)
                        statements.Remove(qs);
                  
                  return (QueryStatement[])bestgroup.ToArray(typeof(QueryStatement));
            }
            
            int InitBuildNodeGetUniqueUnsetVar(QueryStatement s, Hashtable setVars) {
                  int ret = -1;
                  if (s.Subject.IsVariable && !setVars.ContainsKey(s.Subject.VarIndex))
                        ret = s.Subject.VarIndex;
                  if (s.Predicate.IsVariable && !setVars.ContainsKey(s.Predicate.VarIndex)) {
                        if (ret != -1) return -1;
                        ret = s.Predicate.VarIndex;
                  }
                  if (s.Object.IsVariable && !setVars.ContainsKey(s.Object.VarIndex)) {
                        if (ret != -1) return -1;
                        ret = s.Object.VarIndex;
                  }
                  return ret;
            }
      }
      
      public abstract class QueryResultSink {
            public virtual void Init(Entity[] variables) {
            }
            
            public abstract bool Add(VariableBinding[] result);

            public virtual void Finished() {
            }
      }
      
      public struct VariableBinding {
            Entity v;
            Resource t;
            
            internal VariableBinding(Entity variable, Resource target) {
                  v = variable;
                  t = target;
            }
            
            public Entity Variable { get { return v; } internal set { v = value; } }
            public Resource Target { get { return t; } internal set { t = value; } }
      }
}     


Generated by  Doxygen 1.6.0   Back to index