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