From: <zy...@us...> - 2009-04-30 06:25:42
|
Revision: 6280 http://jython.svn.sourceforge.net/jython/?rev=6280&view=rev Author: zyasoft Date: 2009-04-30 06:25:36 +0000 (Thu, 30 Apr 2009) Log Message: ----------- Fixed PyList#sort so that reversed sorts are stable and keyed sorts are keyed only once. Modified Paths: -------------- trunk/jython/src/org/python/core/PyList.java Removed Paths: ------------- trunk/jython/src/org/python/core/PyComparator.java Deleted: trunk/jython/src/org/python/core/PyComparator.java =================================================================== --- trunk/jython/src/org/python/core/PyComparator.java 2009-04-30 05:00:01 UTC (rev 6279) +++ trunk/jython/src/org/python/core/PyComparator.java 2009-04-30 06:25:36 UTC (rev 6280) @@ -1,53 +0,0 @@ -package org.python.core; - -import java.util.Comparator; - -public class PyComparator implements Comparator<PyObject> { - - protected PyList list; - protected PyObject cmp; - protected PyObject key; - protected boolean reverse = false; - - PyComparator(PyList list, PyObject cmp, PyObject key, boolean reverse) { - this.list = list; - this.cmp = cmp; - this.key = key; - this.reverse = reverse; - } - - // First cut at an implementation. FIXME: In CPython key is supposed to - // make things fast, accessing each element once. For this first cut I am - // cheating and calling the key function on every pass to get something - // that works right away. - public int compare(PyObject o1, PyObject o2) { - int result; - if (key != null && key != Py.None) { - o1 = key.__call__(o1); - o2 = key.__call__(o2); - } - if (cmp != null && cmp != Py.None) { - result = cmp.__call__(o1, o2).asInt(); - } else { - result = o1._cmp(o2); - } - if (reverse) { - return -result; - } - if (this.list.gListAllocatedStatus >= 0) { - throw Py.ValueError("list modified during sort"); - } - return result; - } - - public boolean equals(Object o) { - if(o == this) { - return true; - } - - if (o instanceof PyComparator) { - return key.equals(((PyComparator)o).key) && cmp.equals(((PyComparator)o).cmp); - } - return false; - } -} Modified: trunk/jython/src/org/python/core/PyList.java =================================================================== --- trunk/jython/src/org/python/core/PyList.java 2009-04-30 05:00:01 UTC (rev 6279) +++ trunk/jython/src/org/python/core/PyList.java 2009-04-30 06:25:36 UTC (rev 6280) @@ -11,6 +11,7 @@ import java.util.Collection; import java.util.Collections; +import java.util.Comparator; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.List; @@ -710,21 +711,183 @@ sort(cmp, key, reverse); } - public void sort(PyObject compare) { - sort(compare, Py.None, Py.False); + public void sort(PyObject cmp, PyObject key, PyObject reverse) { + boolean bReverse = reverse.__nonzero__(); + if (key == Py.None || key == null) { + if (cmp == Py.None || cmp == null) { + sort(bReverse); + } else { + sort(cmp, bReverse); + } + } else { + sort(cmp, key, bReverse); + } } + // a bunch of optimized paths for sort to avoid unnecessary work, such as DSU or checking compare functions for null + public void sort() { - sort(Py.None, Py.None, Py.False); + sort(false); } - public synchronized void sort(PyObject cmp, PyObject key, PyObject reverse) { + private synchronized void sort(boolean reverse) { gListAllocatedStatus = -1; - PyComparator c = new PyComparator(this, cmp, key, reverse.__nonzero__()); + if (reverse) { + Collections.reverse(list); // maintain stability of sort by reversing first + } + Collections.sort(list, new PyObjectDefaultComparator(this)); + if (reverse) { + Collections.reverse(list); // maintain stability of sort by reversing first + } + gListAllocatedStatus = __len__(); + } + + private static class PyObjectDefaultComparator implements Comparator<PyObject> { + + private final PyList list; + + PyObjectDefaultComparator(PyList list) { + this.list = list; + } + + public int compare(PyObject o1, PyObject o2) { + int result = o1._cmp(o2); + if (this.list.gListAllocatedStatus >= 0) { + throw Py.ValueError("list modified during sort"); + } + return result; + } + + public boolean equals(Object o) { + if (o == this) { + return true; + } + if (o instanceof PyObjectDefaultComparator) { + return true; + } + return false; + } + } + + public void sort(PyObject compare) { + sort(compare, false); + } + + private synchronized void sort(PyObject compare, boolean reverse) { + gListAllocatedStatus = -1; + if (reverse) { + Collections.reverse(list); // maintain stability of sort by reversing first + } + PyObjectComparator c = new PyObjectComparator(this, compare); Collections.sort(list, c); + if (reverse) { + Collections.reverse(list); + } gListAllocatedStatus = __len__(); } + private static class PyObjectComparator implements Comparator<PyObject> { + + private final PyList list; + private final PyObject cmp; + + PyObjectComparator(PyList list, PyObject cmp) { + this.list = list; + this.cmp = cmp; + } + + public int compare(PyObject o1, PyObject o2) { + int result = cmp.__call__(o1, o2).asInt(); + if (this.list.gListAllocatedStatus >= 0) { + throw Py.ValueError("list modified during sort"); + } + return result; + } + + public boolean equals(Object o) { + if (o == this) { + return true; + } + + if (o instanceof PyObjectComparator) { + return cmp.equals(((PyComparator) o).cmp); + } + return false; + } + } + + private static class KV { + + private final PyObject key; + private final PyObject value; + + KV(PyObject key, PyObject value) { + this.key = key; + this.value = value; + } + } + + private static class KVComparator implements Comparator<KV> { + + private final PyList list; + private final PyObject cmp; + + KVComparator(PyList list, PyObject cmp) { + this.list = list; + this.cmp = cmp; + } + + public int compare(KV o1, KV o2) { + int result; + if (cmp != null && cmp != Py.None) { + result = cmp.__call__(o1.key, o2.key).asInt(); + } else { + result = o1.key._cmp(o2.key); + } + if (this.list.gListAllocatedStatus >= 0) { + throw Py.ValueError("list modified during sort"); + } + return result; + } + + public boolean equals(Object o) { + if (o == this) { + return true; + } + + if (o instanceof PyObjectComparator) { + return cmp.equals(((PyComparator) o).cmp); + } + return false; + } + } + + private synchronized void sort(PyObject cmp, PyObject key, boolean reverse) { + gListAllocatedStatus = -1; + + int size = list.size(); + final ArrayList<KV> decorated = new ArrayList<KV>(size); + for (PyObject value : list) { + decorated.add(new KV(key.__call__(value), value)); + } + list.clear(); + KVComparator c = new KVComparator(this, cmp); + if (reverse) { + Collections.reverse(decorated); // maintain stability of sort by reversing first + } + Collections.sort(decorated, c); + if (reverse) { + Collections.reverse(decorated); + } + if (list instanceof ArrayList) { + ((ArrayList) list).ensureCapacity(size); + } + for (KV kv : decorated) { + list.add(kv.value); + } + gListAllocatedStatus = __len__(); + } + public int hashCode() { return list___hash__(); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |