Menu
▾
▴
[Jason-developers] SF.net SVN: jason:[1738] trunk/src
|
From: <jom...@us...> - 2013-07-14 00:40:42
|
Revision: 1738
http://sourceforge.net/p/jason/svn/1738
Author: jomifred
Date: 2013-07-14 00:40:37 +0000 (Sun, 14 Jul 2013)
Log Message:
-----------
improve subset implementation
Modified Paths:
--------------
trunk/src/jason/asSyntax/ListTermImpl.java
trunk/src/jason/asSyntax/Literal.java
trunk/src/test/ListTermTest.java
Modified: trunk/src/jason/asSyntax/ListTermImpl.java
===================================================================
--- trunk/src/jason/asSyntax/ListTermImpl.java 2013-07-13 20:14:39 UTC (rev 1737)
+++ trunk/src/jason/asSyntax/ListTermImpl.java 2013-07-14 00:40:37 UTC (rev 1738)
@@ -418,16 +418,24 @@
}
/** returns all subsets that take k elements of this list */
- public Iterator<List<Term>> subSets(int k) {
- // DFS algorithm
- final List<SubSetSearchState> open = new LinkedList<SubSetSearchState>(); // states to explore
- open.add(new SubSetSearchState(new ArrayList<Term>(), getAsList(), k)); // initial state (root of search tree)
+ public Iterator<List<Term>> subSets(final int k) {
+ // based on a DFS algorithm
return new Iterator<List<Term>>() {
+ LinkedList<SubSetSearchState> open = null;
+ Term[] thisAsArray = new Term[0];
+
List<Term> next = null;
public boolean hasNext() {
- if (next == null)
+ if (open == null) {
+ open = new LinkedList<SubSetSearchState>(); // states to explore
+ //open.add(new SubSetSearchState(new ArrayList<Term>(), getAsList(), k)); // initial state (root of search tree)
+ thisAsArray = getAsList().toArray(thisAsArray);
+ open.add(new SubSetSearchState(0, k, null, null)); // initial state (root of search tree)
+ }
+ if (next == null) {
getNext();
+ }
return next != null;
}
@@ -439,37 +447,71 @@
void getNext() {
while (! open.isEmpty() ) {
- SubSetSearchState s = open.remove(0);
- if (s.k == 0) {
- next = s.prefix;
+ SubSetSearchState s = open.removeFirst();
+ if (s.d == 0) {
+ next = s.getAsList();
return;
} else {
- s.addNexts(open);
+ s.addNexts();
}
}
next = null;
}
public void remove() { }
+
+ class SubSetSearchState {
+ int pos;
+ int d;
+ Term value = null;
+ SubSetSearchState f = null;
+
+ SubSetSearchState(int pos, int d, Term t, SubSetSearchState father) {
+ this.pos = pos; this.d = d; this.value = t; this.f = father;
+ }
+ void addNexts() {
+ int pSize = (k-d)+thisAsArray.length;
+ for (int i = thisAsArray.length-1; i >= pos; i--) {
+ if (pSize-i >= k) {
+ open.addFirst(new SubSetSearchState(i+1, d-1, thisAsArray[i], this));
+ }
+ }
+ }
+
+ List<Term> getAsList() {
+ LinkedList<Term> np = new LinkedList<Term>();
+ SubSetSearchState c = this;
+ while (c.value != null) {
+ np.addFirst(c.value);
+ c = c.f;
+ }
+ return np;
+ }
+ }
+
+ /*// old code
+ class SubSetSearchState {
+ List<Term> prefix, elements;
+ int d;
+ SubSetSearchState(List<Term> p, List<Term> e, int d) {
+ prefix = p; elements = e; this.d = d;
+ }
+ void addNexts(List<SubSetSearchState> open) {
+ int esize = elements.size();
+ int maxNextSize = prefix.size()+esize;
+ for (int i = esize-1; i >= 0; i--) {
+ if (maxNextSize-i >= k) {
+ List<Term> np = new ArrayList<Term>(prefix);
+ np.add(elements.get(i));
+ open.add(0, new SubSetSearchState(np, elements.subList(i+1, esize), d-1));
+ }
+ }
+ }
+ }
+ */
};
}
- class SubSetSearchState {
- List<Term> prefix, elements;
- int k;
- SubSetSearchState(List<Term> p, List<Term> e, int k) {
- prefix = p; elements = e; this.k = k;
- }
- void addNexts(List<SubSetSearchState> open) {
- int esize = elements.size();
- for (int i = esize-1; i >= 0; i--) {
- List<Term> np = new ArrayList<Term>(prefix);
- np.add(elements.get(i));
- open.add(0, new SubSetSearchState(np, elements.subList(i+1, esize), k-1));
- }
- }
- }
-
/*
public List<List<Term>> subSets(int k) {
List<List<Term>> result = new ArrayList<List<Term>>();
Modified: trunk/src/jason/asSyntax/Literal.java
===================================================================
--- trunk/src/jason/asSyntax/Literal.java 2013-07-13 20:14:39 UTC (rev 1737)
+++ trunk/src/jason/asSyntax/Literal.java 2013-07-14 00:40:37 UTC (rev 1738)
@@ -351,7 +351,6 @@
if (annotsOptions != null) {
while (annotsOptions.hasNext()) {
Literal belToTry = belInBB.copy().setAnnots(null).addAnnots( annotsOptions.next() );
-
Unifier u = un.clone();
if (u.unifiesNoUndo(Literal.this, belToTry)) {
current = u;
@@ -445,8 +444,6 @@
if (belInBB.hasAnnot()) {
int nbAnnotsB = belInBB.getAnnots().size();
if (nbAnnotsB >= nbAnnots) {
- if (nbAnnots > 5)
- logger.warning("I am generating "+Math.pow(2, nbAnnots)+" subsets for the annotation backtracking consult of "+Literal.this);
annotsOptions = belInBB.getAnnots().subSets( nbAnnots );
get();
if (current != null) // if it get a value
Modified: trunk/src/test/ListTermTest.java
===================================================================
--- trunk/src/test/ListTermTest.java 2013-07-13 20:14:39 UTC (rev 1737)
+++ trunk/src/test/ListTermTest.java 2013-07-14 00:40:37 UTC (rev 1738)
@@ -334,14 +334,17 @@
public void testSubSet() {
ListTerm l3 = ListTermImpl.parseList("[a,b,c,8]");
- /*Set<PredicateIndicator> types = new HashSet<PredicateIndicator>();
- types.add( ((Literal)l3.get(1) ).getPredicateIndicator());
- types.add( ((Literal)l3.get(2) ).getPredicateIndicator());
- types.add( ((Literal)l3.get(3) ).getPredicateIndicator());*/
assertEquals("[[a], [b], [c], [8]]", iterator2list(l3.subSets(1)).toString());
assertEquals("[[a, b], [a, c], [a, 8], [b, c], [b, 8], [c, 8]]", iterator2list(l3.subSets(2)).toString());
assertEquals("[[a, b, c], [a, b, 8], [a, c, 8], [b, c, 8]]", iterator2list(l3.subSets(3)).toString());
assertEquals("[[a, b, c, 8]]", iterator2list(l3.subSets(4)).toString());
+
+ l3 = ListTermImpl.parseList("[a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20]");
+ //for (int i=0; i< 20;i++)
+ // System.out.println(iterator2list(l3.subSets(i+1)).size());
+ assertEquals("[[a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20]]",iterator2list(l3.subSets(20)).toString());
+ assertEquals(38760, iterator2list(l3.subSets(6)).size());
+ assertEquals(38760, iterator2list(l3.subSets(14)).size());
}
public void testMkVarAn() {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
