BagofAnswers.cs 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  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. using System;
  31. using System.Collections;
  32. using System.Collections.Generic;
  33. namespace OpenSim.Region.ScriptEngine.Shared.YieldProlog
  34. {
  35. /// <summary>
  36. /// A BagofAnswers holds answers for bagof and setof.
  37. /// </summary>
  38. public class BagofAnswers
  39. {
  40. private object _template;
  41. private Variable[] _freeVariables;
  42. private Dictionary<object[], List<object>> _bagForFreeVariables;
  43. private List<object> _findallBagArray;
  44. private static TermArrayEqualityComparer _termArrayEqualityComparer =
  45. new TermArrayEqualityComparer();
  46. /// <summary>
  47. /// To get the free variables, split off any existential qualifiers from Goal such as the X in
  48. /// "X ^ f(Y)", get the set of unbound variables in Goal that are not qualifiers, then remove
  49. /// the unbound variables that are qualifiers as well as the unbound variables in Template.
  50. /// </summary>
  51. /// <param name="Template"></param>
  52. /// <param name="Goal"></param>
  53. public BagofAnswers(object Template, object Goal)
  54. {
  55. _template = Template;
  56. // First get the set of variables that are not free variables.
  57. List<Variable> variableSet = new List<Variable>();
  58. YP.addUniqueVariables(Template, variableSet);
  59. object UnqualifiedGoal = YP.getValue(Goal);
  60. while (UnqualifiedGoal is Functor2 && ((Functor2)UnqualifiedGoal)._name == Atom.HAT)
  61. {
  62. YP.addUniqueVariables(((Functor2)UnqualifiedGoal)._arg1, variableSet);
  63. UnqualifiedGoal = YP.getValue(((Functor2)UnqualifiedGoal)._arg2);
  64. }
  65. // Remember how many non-free variables there are so we can find the unique free variables
  66. // that are added.
  67. int nNonFreeVariables = variableSet.Count;
  68. YP.addUniqueVariables(UnqualifiedGoal, variableSet);
  69. int nFreeVariables = variableSet.Count - nNonFreeVariables;
  70. if (nFreeVariables == 0)
  71. {
  72. // There were no free variables added, so we won't waste time with _bagForFreeVariables.
  73. _freeVariables = null;
  74. _findallBagArray = new List<object>();
  75. }
  76. else
  77. {
  78. // Copy the free variables.
  79. _freeVariables = new Variable[nFreeVariables];
  80. for (int i = 0; i < nFreeVariables; ++i)
  81. _freeVariables[i] = variableSet[i + nNonFreeVariables];
  82. _bagForFreeVariables = new Dictionary<object[], List<object>>(_termArrayEqualityComparer);
  83. }
  84. }
  85. public void add()
  86. {
  87. if (_freeVariables == null)
  88. // The goal has bound the values in _template but we don't bother with _freeVariables.
  89. _findallBagArray.Add(YP.makeCopy(_template, new Variable.CopyStore()));
  90. else
  91. {
  92. // The goal has bound the values in _template and _freeVariables.
  93. // Find the entry for this set of _freeVariables values.
  94. object[] freeVariableValues = new object[_freeVariables.Length];
  95. for (int i = 0; i < _freeVariables.Length; ++i)
  96. freeVariableValues[i] = YP.getValue(_freeVariables[i]);
  97. List<object> bagArray;
  98. if (!_bagForFreeVariables.TryGetValue(freeVariableValues, out bagArray))
  99. {
  100. bagArray = new List<object>();
  101. _bagForFreeVariables[freeVariableValues] = bagArray;
  102. }
  103. // Now copy the template and add to the bag for the freeVariables values.
  104. bagArray.Add(YP.makeCopy(_template, new Variable.CopyStore()));
  105. }
  106. }
  107. // disable warning on l1, don't see how we can
  108. // code this differently
  109. #pragma warning disable 0168, 0219
  110. /// <summary>
  111. /// For each result, unify the _freeVariables and unify bagArrayVariable with the associated bag.
  112. /// </summary>
  113. /// <param name="bagArrayVariable">this is unified with the List<object> of matches for template that
  114. /// corresponds to the bindings for freeVariables. Be very careful: this does not unify with a Prolog
  115. /// list.</param>
  116. /// <returns></returns>
  117. public IEnumerable<bool> resultArray(Variable bagArrayVariable)
  118. {
  119. if (_freeVariables == null)
  120. {
  121. // No unbound free variables, so we only filled one bag. If empty, bagof fails.
  122. if (_findallBagArray.Count > 0)
  123. {
  124. foreach (bool l1 in bagArrayVariable.unify(_findallBagArray))
  125. yield return false;
  126. }
  127. }
  128. else
  129. {
  130. foreach (KeyValuePair<object[], List<object>> valuesAndBag in _bagForFreeVariables)
  131. {
  132. foreach (bool l1 in YP.unifyArrays(_freeVariables, valuesAndBag.Key))
  133. {
  134. foreach (bool l2 in bagArrayVariable.unify(valuesAndBag.Value))
  135. yield return false;
  136. }
  137. // Debug: Should we free memory of the answers already returned?
  138. }
  139. }
  140. }
  141. /// <summary>
  142. /// For each result, unify the _freeVariables and unify Bag with the associated bag.
  143. /// </summary>
  144. /// <param name="Bag"></param>
  145. /// <returns></returns>
  146. public IEnumerable<bool> result(object Bag)
  147. {
  148. Variable bagArrayVariable = new Variable();
  149. foreach (bool l1 in resultArray(bagArrayVariable))
  150. {
  151. foreach (bool l2 in YP.unify(Bag, ListPair.make((List<object>)bagArrayVariable.getValue())))
  152. yield return false;
  153. }
  154. }
  155. /// <summary>
  156. /// For each result, unify the _freeVariables and unify Bag with the associated bag which is sorted
  157. /// with duplicates removed, as in setof.
  158. /// </summary>
  159. /// <param name="Bag"></param>
  160. /// <returns></returns>
  161. public IEnumerable<bool> resultSet(object Bag)
  162. {
  163. Variable bagArrayVariable = new Variable();
  164. foreach (bool l1 in resultArray(bagArrayVariable))
  165. {
  166. List<object> bagArray = (List<object>)bagArrayVariable.getValue();
  167. YP.sortArray(bagArray);
  168. foreach (bool l2 in YP.unify(Bag, ListPair.makeWithoutRepeatedTerms(bagArray)))
  169. yield return false;
  170. }
  171. }
  172. public static IEnumerable<bool> bagofArray
  173. (object Template, object Goal, IEnumerable<bool> goalIterator, Variable bagArrayVariable)
  174. {
  175. BagofAnswers bagOfAnswers = new BagofAnswers(Template, Goal);
  176. foreach (bool l1 in goalIterator)
  177. bagOfAnswers.add();
  178. return bagOfAnswers.resultArray(bagArrayVariable);
  179. }
  180. public static IEnumerable<bool> bagof
  181. (object Template, object Goal, IEnumerable<bool> goalIterator, object Bag)
  182. {
  183. BagofAnswers bagOfAnswers = new BagofAnswers(Template, Goal);
  184. foreach (bool l1 in goalIterator)
  185. bagOfAnswers.add();
  186. return bagOfAnswers.result(Bag);
  187. }
  188. public static IEnumerable<bool> setof
  189. (object Template, object Goal, IEnumerable<bool> goalIterator, object Bag)
  190. {
  191. BagofAnswers bagOfAnswers = new BagofAnswers(Template, Goal);
  192. foreach (bool l1 in goalIterator)
  193. bagOfAnswers.add();
  194. return bagOfAnswers.resultSet(Bag);
  195. }
  196. #pragma warning restore 0168, 0219
  197. /// <summary>
  198. /// A TermArrayEqualityComparer implements IEqualityComparer to compare two object arrays using YP.termEqual.
  199. /// </summary>
  200. private class TermArrayEqualityComparer : IEqualityComparer<object[]>
  201. {
  202. public bool Equals(object[] array1, object[] array2)
  203. {
  204. if (array1.Length != array2.Length)
  205. return false;
  206. for (int i = 0; i < array1.Length; ++i)
  207. {
  208. if (!YP.termEqual(array1[i], array2[i]))
  209. return false;
  210. }
  211. return true;
  212. }
  213. public int GetHashCode(object[] array)
  214. {
  215. int hashCode = 0;
  216. for (int i = 0; i < array.Length; ++i)
  217. hashCode ^= array[i].GetHashCode();
  218. return hashCode;
  219. }
  220. }
  221. }
  222. }