opensim-development – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 eva 1 /*
2 * Copyright (C) 2007-2008, Jeff Thompson
3 *
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * * Neither the name of the copyright holder nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
27 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30  
31 using System;
32 using System.Collections;
33 using System.Collections.Generic;
34  
35 namespace OpenSim.Region.ScriptEngine.Shared.YieldProlog
36 {
37 /// <summary>
38 /// A BagofAnswers holds answers for bagof and setof.
39 /// </summary>
40 public class BagofAnswers
41 {
42 private object _template;
43 private Variable[] _freeVariables;
44 private Dictionary<object[], List<object>> _bagForFreeVariables;
45 private List<object> _findallBagArray;
46 private static TermArrayEqualityComparer _termArrayEqualityComparer =
47 new TermArrayEqualityComparer();
48  
49 /// <summary>
50 /// To get the free variables, split off any existential qualifiers from Goal such as the X in
51 /// "X ^ f(Y)", get the set of unbound variables in Goal that are not qualifiers, then remove
52 /// the unbound variables that are qualifiers as well as the unbound variables in Template.
53 /// </summary>
54 /// <param name="Template"></param>
55 /// <param name="Goal"></param>
56 public BagofAnswers(object Template, object Goal)
57 {
58 _template = Template;
59  
60 // First get the set of variables that are not free variables.
61 List<Variable> variableSet = new List<Variable>();
62 YP.addUniqueVariables(Template, variableSet);
63 object UnqualifiedGoal = YP.getValue(Goal);
64 while (UnqualifiedGoal is Functor2 && ((Functor2)UnqualifiedGoal)._name == Atom.HAT)
65 {
66 YP.addUniqueVariables(((Functor2)UnqualifiedGoal)._arg1, variableSet);
67 UnqualifiedGoal = YP.getValue(((Functor2)UnqualifiedGoal)._arg2);
68 }
69  
70 // Remember how many non-free variables there are so we can find the unique free variables
71 // that are added.
72 int nNonFreeVariables = variableSet.Count;
73 YP.addUniqueVariables(UnqualifiedGoal, variableSet);
74 int nFreeVariables = variableSet.Count - nNonFreeVariables;
75 if (nFreeVariables == 0)
76 {
77 // There were no free variables added, so we won't waste time with _bagForFreeVariables.
78 _freeVariables = null;
79 _findallBagArray = new List<object>();
80 }
81 else
82 {
83 // Copy the free variables.
84 _freeVariables = new Variable[nFreeVariables];
85 for (int i = 0; i < nFreeVariables; ++i)
86 _freeVariables[i] = variableSet[i + nNonFreeVariables];
87  
88 _bagForFreeVariables = new Dictionary<object[], List<object>>(_termArrayEqualityComparer);
89 }
90 }
91  
92 public void add()
93 {
94 if (_freeVariables == null)
95 // The goal has bound the values in _template but we don't bother with _freeVariables.
96 _findallBagArray.Add(YP.makeCopy(_template, new Variable.CopyStore()));
97 else
98 {
99 // The goal has bound the values in _template and _freeVariables.
100 // Find the entry for this set of _freeVariables values.
101 object[] freeVariableValues = new object[_freeVariables.Length];
102 for (int i = 0; i < _freeVariables.Length; ++i)
103 freeVariableValues[i] = YP.getValue(_freeVariables[i]);
104 List<object> bagArray;
105 if (!_bagForFreeVariables.TryGetValue(freeVariableValues, out bagArray))
106 {
107 bagArray = new List<object>();
108 _bagForFreeVariables[freeVariableValues] = bagArray;
109 }
110  
111 // Now copy the template and add to the bag for the freeVariables values.
112 bagArray.Add(YP.makeCopy(_template, new Variable.CopyStore()));
113 }
114 }
115  
116 // disable warning on l1, don't see how we can
117 // code this differently
118 #pragma warning disable 0168, 0219
119  
120 /// <summary>
121 /// For each result, unify the _freeVariables and unify bagArrayVariable with the associated bag.
122 /// </summary>
123 /// <param name="bagArrayVariable">this is unified with the List<object> of matches for template that
124 /// corresponds to the bindings for freeVariables. Be very careful: this does not unify with a Prolog
125 /// list.</param>
126 /// <returns></returns>
127 public IEnumerable<bool> resultArray(Variable bagArrayVariable)
128 {
129 if (_freeVariables == null)
130 {
131 // No unbound free variables, so we only filled one bag. If empty, bagof fails.
132 if (_findallBagArray.Count > 0)
133 {
134 foreach (bool l1 in bagArrayVariable.unify(_findallBagArray))
135 yield return false;
136 }
137 }
138 else
139 {
140 foreach (KeyValuePair<object[], List<object>> valuesAndBag in _bagForFreeVariables)
141 {
142 foreach (bool l1 in YP.unifyArrays(_freeVariables, valuesAndBag.Key))
143 {
144 foreach (bool l2 in bagArrayVariable.unify(valuesAndBag.Value))
145 yield return false;
146 }
147 // Debug: Should we free memory of the answers already returned?
148 }
149 }
150 }
151  
152 /// <summary>
153 /// For each result, unify the _freeVariables and unify Bag with the associated bag.
154 /// </summary>
155 /// <param name="Bag"></param>
156 /// <returns></returns>
157 public IEnumerable<bool> result(object Bag)
158 {
159 Variable bagArrayVariable = new Variable();
160 foreach (bool l1 in resultArray(bagArrayVariable))
161 {
162 foreach (bool l2 in YP.unify(Bag, ListPair.make((List<object>)bagArrayVariable.getValue())))
163 yield return false;
164 }
165 }
166  
167 /// <summary>
168 /// For each result, unify the _freeVariables and unify Bag with the associated bag which is sorted
169 /// with duplicates removed, as in setof.
170 /// </summary>
171 /// <param name="Bag"></param>
172 /// <returns></returns>
173 public IEnumerable<bool> resultSet(object Bag)
174 {
175 Variable bagArrayVariable = new Variable();
176 foreach (bool l1 in resultArray(bagArrayVariable))
177 {
178 List<object> bagArray = (List<object>)bagArrayVariable.getValue();
179 YP.sortArray(bagArray);
180 foreach (bool l2 in YP.unify(Bag, ListPair.makeWithoutRepeatedTerms(bagArray)))
181 yield return false;
182 }
183 }
184  
185 public static IEnumerable<bool> bagofArray
186 (object Template, object Goal, IEnumerable<bool> goalIterator, Variable bagArrayVariable)
187 {
188 BagofAnswers bagOfAnswers = new BagofAnswers(Template, Goal);
189 foreach (bool l1 in goalIterator)
190 bagOfAnswers.add();
191 return bagOfAnswers.resultArray(bagArrayVariable);
192 }
193  
194 public static IEnumerable<bool> bagof
195 (object Template, object Goal, IEnumerable<bool> goalIterator, object Bag)
196 {
197 BagofAnswers bagOfAnswers = new BagofAnswers(Template, Goal);
198 foreach (bool l1 in goalIterator)
199 bagOfAnswers.add();
200 return bagOfAnswers.result(Bag);
201 }
202  
203 public static IEnumerable<bool> setof
204 (object Template, object Goal, IEnumerable<bool> goalIterator, object Bag)
205 {
206 BagofAnswers bagOfAnswers = new BagofAnswers(Template, Goal);
207 foreach (bool l1 in goalIterator)
208 bagOfAnswers.add();
209 return bagOfAnswers.resultSet(Bag);
210 }
211 #pragma warning restore 0168, 0219
212  
213 /// <summary>
214 /// A TermArrayEqualityComparer implements IEqualityComparer to compare two object arrays using YP.termEqual.
215 /// </summary>
216 private class TermArrayEqualityComparer : IEqualityComparer<object[]>
217 {
218 public bool Equals(object[] array1, object[] array2)
219 {
220 if (array1.Length != array2.Length)
221 return false;
222 for (int i = 0; i < array1.Length; ++i)
223 {
224 if (!YP.termEqual(array1[i], array2[i]))
225 return false;
226 }
227 return true;
228 }
229  
230 public int GetHashCode(object[] array)
231 {
232 int hashCode = 0;
233 for (int i = 0; i < array.Length; ++i)
234 hashCode ^= array[i].GetHashCode();
235 return hashCode;
236 }
237 }
238 }
239 }