On Sat, 9 Jun 2012 18:40:33 +0200
Campbell Barton <[email protected]> wrote:
> Good work - sent new review
> http://codereview.appspot.com/6305077/
>
> python is currently single threaded so you could use a static var
> here, though I would like to avoid this where possible.
>
Here is a v3 attached.
Changes since v2:
- Fixed compilation warning about incompatible type of the comparison
functions.
- Use qsort: rely on a global variable to sort according to the 'keys'
array
- Don't use gotos
- Don't use PyNumber_Check(), it's faster to check the return value of
PyFloat_AsDouble() directly
- Don't call BM_mesh_elem_index_ensure(), leave the indices untouched,
mention BMEelemSeq.index_update() in the docstring.
I didn't move the check about (BMIterType)self->itype), see [1],
because I use elem_map_idx in there _after_ this has been allocated. If
I wanted to check self->itype before I had to do a check on the
type again later to decide what elements we are dealing with anyways.
If you've got any other suggestions, let me know.
I still think the old version with gotos were easier on the eyes :)
Thanks,
Antonio
[1]
http://codereview.appspot.com/6305077/diff/1/source/blender/python/bmesh/bmesh_py_types.c#newcode2257
--
Antonio Ospite
http://ao2.it
A: Because it messes up the order in which people normally read text.
See http://en.wikipedia.org/wiki/Posting_style
Q: Why is top-posting such a bad thing?
>From f7beed7d000890dd823dd261b584fbde2347860a Mon Sep 17 00:00:00 2001
From: Antonio Ospite <[email protected]>
Date: Thu, 7 Jun 2012 10:54:45 +0200
Subject: [PATCH v3] Add a BMElemSeq.sort() method
X-Face: z*RaLf`X<@C75u6Ig9}{oW$H;1_\2t5)({*|jhM<pyWR#k60!#=#>/Vb;]yA5<GWI5`6u&+
;6b'@y|8w"wB;4/e!7wYYrcqdJFY,~%Gk_4]cq$Ei/7<j&N3ah(m`ku?pX.&+~:_/wC~dwn^)MizBG
!pE^+iDQQ1yC6^,)YDKkxDd!T>\I~93>J<_`<4)A{':UrE
Add a method to sort BMElemSeq sequences, like python sequences.
---
source/blender/python/bmesh/bmesh_py_types.c | 206 ++++++++++++++++++++++++++
1 file changed, 206 insertions(+)
diff --git a/source/blender/python/bmesh/bmesh_py_types.c b/source/blender/python/bmesh/bmesh_py_types.c
index 053dac7..092c704 100644
--- a/source/blender/python/bmesh/bmesh_py_types.c
+++ b/source/blender/python/bmesh/bmesh_py_types.c
@@ -2083,6 +2083,207 @@ static PyObject *bpy_bmelemseq_index_update(BPy_BMElemSeq *self)
Py_RETURN_NONE;
}
+PyDoc_STRVAR(bpy_bmelemseq_sort_doc,
+".. method:: sort(key=None, reverse=False)\n"
+"\n"
+" Sort the elements of this sequence, using an optional custom sort key.\n"
+" Indices of elements are not changed, BMElemeSeq.index_update() can be used for that.\n"
+"\n"
+" :arg key: The key that sets the ordering of the elements.\n"
+" :type key: :function: returning a number\n"
+" :arg reverse: Reverse the order of the elements\n"
+" :type reverse: :boolean:\n"
+"\n"
+" .. code-block:: python\n"
+"\n"
+" mesh.faces.sort(key=lambda f: f.calc_area())\n"
+" mesh.faces.index_update()\n"
+"\n"
+" .. note::\n"
+"\n"
+" When the 'key' argument is not provided, the elements are reordered following their current index value.\n"
+" In particular this can be used by setting indices manually before calling this method.\n"
+"\n"
+);
+
+/* Use a static variable here because there is the need to sort some array
+ * doing comparisons on elements of another array, qsort_r would have been
+ * wonderful to use here, but unfortunately it is not standard and it's not
+ * portable across different platforms.
+ *
+ * If a portable alternative to qsort_r becomes available, remove this static
+ * var hack!
+ *
+ * Note: the functions below assumes the keys array has been allocated and it
+ * has enough elements to complete the task.
+ */
+static double *keys = NULL;
+
+static int bpy_bmelemseq_sort_cmp_by_keys_ascending(const void *index1_v, const void *index2_v)
+{
+ const int *index1 = (int *)index1_v;
+ const int *index2 = (int *)index2_v;
+
+ if (keys[*index1] < keys[*index2])
+ return -1;
+ else if (keys[*index1] > keys[*index2])
+ return 1;
+ else
+ return 0;
+}
+
+static int bpy_bmelemseq_sort_cmp_by_keys_descending(const void *index1_v, const void *index2_v)
+{
+ return -bpy_bmelemseq_sort_cmp_by_keys_ascending(index1_v, index2_v);
+}
+
+static PyObject *bpy_bmelemseq_sort(BPy_BMElemSeq *self, PyObject *args, PyObject *kw)
+{
+ static const char *kwlist[] = {"key", "reverse", NULL};
+ PyObject *keyfunc = NULL; /* optional */
+ int reverse = FALSE; /* optional */
+
+ const char htype = bm_iter_itype_htype_map[self->itype];
+ int n_elem;
+
+ BMIter iter;
+ BMElem *ele;
+
+ int *elem_idx;
+ int *elem_map_idx;
+ int (*elem_idx_compare_by_keys)(const void *, const void *);
+
+ int *vert_idx = NULL;
+ int *edge_idx = NULL;
+ int *face_idx = NULL;
+ int i;
+
+ BMesh *bm = self->bm;
+
+ BPY_BM_CHECK_OBJ(self);
+
+ if (args != NULL) {
+ if(!PyArg_ParseTupleAndKeywords(args, kw,
+ "|Oi:BMElemSeq.sort",
+ (char **)kwlist,
+ &keyfunc, &reverse))
+ return NULL;
+ }
+
+ if (keyfunc != NULL && !PyCallable_Check(keyfunc)) {
+ PyErr_SetString(PyExc_TypeError,
+ "the 'key' argument is not a callable object");
+ return NULL;
+ }
+
+ n_elem = BM_mesh_elem_count(bm, htype);
+ if (n_elem <= 1) {
+ /* 0 or 1 elements: sorted already */
+ Py_RETURN_NONE;
+ }
+
+ keys = PyMem_MALLOC(sizeof(*keys) * n_elem);
+ if (keys == NULL) {
+ PyErr_NoMemory();
+ return NULL;
+ }
+
+ i = 0;
+ BM_ITER_BPY_BM_SEQ (ele, &iter, self) {
+ if (keyfunc != NULL) {
+ PyObject *py_elem;
+ PyObject *index;
+
+ py_elem = BPy_BMElem_CreatePyObject(self->bm, (BMHeader *)ele);
+ index = PyObject_CallFunctionObjArgs(keyfunc, py_elem, NULL);
+ Py_DECREF(py_elem);
+ if (index == NULL) {
+ /* No need to set the exception here,
+ * PyObject_CallFunctionObjArgs() does that */
+ PyMem_FREE(keys);
+ return NULL;
+ }
+
+ keys[i] = PyFloat_AsDouble(index);
+ if (keys[i] == -1 && PyErr_Occurred()) {
+ PyErr_SetString(PyExc_ValueError,
+ "the value returned by the 'key' function is not a number");
+ Py_DECREF(index);
+ PyMem_FREE(keys);
+ return NULL;
+ }
+
+ Py_DECREF(index);
+ } else {
+ /* If the 'key' function is not provided we sort
+ * according to the current index values */
+ keys[i] = ele->head.index;
+ }
+
+ i++;
+ }
+
+ elem_idx = PyMem_MALLOC(sizeof(*elem_idx) * n_elem);
+ if (elem_idx == NULL) {
+ PyErr_NoMemory();
+ PyMem_FREE(keys);
+ return NULL;
+ }
+
+ /* Initialize the element index array */
+ range_vn_i(elem_idx, n_elem, 0);
+
+ /* Sort the index array according to the order of the 'keys' array */
+ if (reverse)
+ elem_idx_compare_by_keys = bpy_bmelemseq_sort_cmp_by_keys_descending;
+ else
+ elem_idx_compare_by_keys = bpy_bmelemseq_sort_cmp_by_keys_ascending;
+
+ qsort(elem_idx, n_elem, sizeof(*elem_idx), elem_idx_compare_by_keys);
+
+ elem_map_idx = PyMem_MALLOC(sizeof(*elem_map_idx) * n_elem);
+ if (elem_map_idx == NULL) {
+ PyErr_NoMemory();
+ PyMem_FREE(elem_idx);
+ PyMem_FREE(keys);
+ return NULL;
+ }
+
+ /* Initialize the map array
+ *
+ * We need to know the index such that if used as the new_index in
+ * BM_mesh_remap() will give the order of the sorted keys like in
+ * elem_idx */
+ for (i = 0; i < n_elem; i++) {
+ elem_map_idx[elem_idx[i]] = i;
+ }
+
+ switch ((BMIterType)self->itype) {
+ case BM_VERTS_OF_MESH:
+ vert_idx = elem_map_idx;
+ break;
+ case BM_EDGES_OF_MESH:
+ edge_idx = elem_map_idx;
+ break;
+ case BM_FACES_OF_MESH:
+ face_idx = elem_map_idx;
+ break;
+ default:
+ PyErr_Format(PyExc_TypeError, "element type %d not supported", self->itype);
+ PyMem_FREE(elem_map_idx);
+ PyMem_FREE(elem_idx);
+ PyMem_FREE(keys);
+ return NULL;
+ }
+
+ BM_mesh_remap(bm, vert_idx, edge_idx, face_idx);
+
+ PyMem_FREE(elem_map_idx);
+ PyMem_FREE(elem_idx);
+ PyMem_FREE(keys);
+
+ Py_RETURN_NONE;
+}
static struct PyMethodDef bpy_bmesh_methods[] = {
/* utility */
@@ -2166,6 +2367,7 @@ static struct PyMethodDef bpy_bmloop_methods[] = {
static struct PyMethodDef bpy_bmelemseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
@@ -2175,6 +2377,7 @@ static struct PyMethodDef bpy_bmvertseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
@@ -2186,6 +2389,7 @@ static struct PyMethodDef bpy_bmedgeseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
@@ -2197,12 +2401,14 @@ static struct PyMethodDef bpy_bmfaceseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
static struct PyMethodDef bpy_bmloopseq_methods[] = {
/* odd function, initializes index values */
/* no: index_update() function since we cant iterate over loops */
+ /* no: sort() function since we cant iterate over loops */
{NULL, NULL, 0, NULL}
};
--
1.7.10
#!/usr/bin/env python
import traceback
import bpy
import bmesh
def print_elems(elems, key=None):
print()
for e in elems:
print(e.index, key(e) if key else "")
print()
def print_elems_by_index(elems, key=None, reverse=False):
print()
sorted_elems = sorted(elems, key=lambda e: e.index, reverse=reverse)
for e in sorted_elems:
print(e.index, key(e) if key else "")
print()
cube = bpy.data .objects['Cube']
mesh = bmesh.new()
mesh.from_mesh(cube.data)
print(mesh)
print("\n\n")
print("A test for an invalid 'key' value, this is gonna fail")
try:
mesh.faces.sort(key=13)
mesh.faces.index_update()
except:
traceback.print_exc()
pass
print("\n\n")
print("A test for an invalid 'reverse' value, this is gonna fail")
try:
mesh.faces.sort(reverse='Ciao')
mesh.faces.index_update()
except:
traceback.print_exc()
pass
print("\n\n")
print("A test for an malformed function, this is gonna fail")
try:
mesh.verts.sort(key=lambda x: f.index)
mesh.verts.index_update()
except:
traceback.print_exc()
pass
print("\n\n")
print("A test for an invalid function, this is gonna fail")
def f(x, y):
return x.index
try:
mesh.verts.sort(key=f)
mesh.verts.index_update()
except:
traceback.print_exc()
pass
print("\n\n")
print("A test on using a key function which does not return a number, this is gonna fail")
try:
mesh.verts.sort(key=lambda f: "Ciao")
mesh.verts.index_update()
except:
traceback.print_exc()
pass
print("\n\n")
print("A test on sorting by the index values in reverse")
print_elems(mesh.faces, key=lambda f: f.calc_area())
mesh.faces.sort(key=lambda f: f.index, reverse=True)
mesh.faces.index_update()
print_elems(mesh.faces, key=lambda f: f.calc_area())
print("\n\n")
print("A test on sorting by setting the index values manually")
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts[0].index = 4
mesh.verts[4].index = 0
mesh.verts[1].index = 7
mesh.verts[7].index = 1
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts.sort()
mesh.verts.index_update()
print_elems(mesh.verts, key=lambda v: v.co[0])
print("\n\n")
print("A test on faces, sort according to face area")
print_elems(mesh.faces, key=lambda f: f.calc_area())
mesh.faces.sort(key=lambda f: f.calc_area())
mesh.faces.index_update()
#print("When iterating over the sorted elements we don't get the new natural order")
print_elems(mesh.faces, key=lambda f: f.calc_area())
#print("But if we sort by index then the order is right...")
#print_elems_by_index(mesh.faces, key=lambda f: f.calc_area())
print("\n\n")
print("A test on vertices, sort according to x coordinate")
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts.sort(key=lambda v: v.co[0])
mesh.verts.index_update()
#print("When iterating over the sorted elements we don't get the new natural order")
print_elems(mesh.verts, key=lambda v: v.co[0])
#print("But if we sort by index then the order is right...")
#print_elems_by_index(mesh.verts, key=lambda v: v.co[0])
mesh.to_mesh(cube.data)
mesh.free()
print("After exporting to mesh again the elements are properly sorted too")
print_elems(cube.data.vertices, key=lambda v: v.co[0])
_______________________________________________
Bf-python mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-python
