Panda3D
|
00001 00002 /* Note: This module can probably go away when we upgrade to Python 2.4. 00003 Python 2.3 has a heapq implementation, but it is in Python. This is 00004 reported to be about 20x faster. In 2.4 they reimplemented heapq in C so 00005 it should be comparable to this. At this time though, Python 2.4 is 00006 still in alpha. 00007 00008 Note: This code has been bastardized to only work on Tasks temporarily. 00009 00010 */ 00011 00012 #include <Python.h> 00013 00014 /* Prototypes */ 00015 static PyObject * heappush(PyObject *self, PyObject *args); 00016 static PyObject * heappop(PyObject *self, PyObject *args); 00017 static PyObject * heapreplace(PyObject *self, PyObject *args); 00018 static PyObject * heapify(PyObject *self, PyObject *args); 00019 static int _siftdown(PyObject *list, int startpos, int pos); 00020 static int _siftup(PyObject *list, int pos); 00021 00022 #ifdef _WIN32 00023 extern "C" __declspec(dllexport) void initlibheapq(void); 00024 extern "C" __declspec(dllexport) void initlibp3heapq(void); 00025 #else 00026 extern "C" void initlibheapq(); 00027 extern "C" void initlibp3heapq(); 00028 #endif 00029 00030 static PyObject * 00031 heappush(PyObject *self, PyObject *args) { 00032 int len; 00033 PyObject *list = NULL; 00034 PyObject *node = NULL; 00035 00036 if (!PyArg_ParseTuple(args,"O!O",&PyList_Type,&list,&node)) 00037 return NULL; 00038 00039 len = PyList_Size(list); 00040 if (PyList_Append(list,node)) 00041 return NULL; 00042 00043 if (_siftdown(list,0,len)) 00044 return NULL; 00045 00046 Py_INCREF(Py_None); 00047 return Py_None; 00048 } 00049 00050 static PyObject * 00051 heappop(PyObject *self, PyObject *args) { 00052 PyObject *list = NULL; 00053 PyObject *node = NULL; 00054 PyObject *returnNode = NULL; 00055 int len; 00056 00057 if (!PyArg_ParseTuple(args,"O!",&PyList_Type,&list)) 00058 return NULL; 00059 00060 len = PyList_Size(list); 00061 if (len == 0) { 00062 /* Special-case most common failure cause */ 00063 PyErr_SetString(PyExc_IndexError, "pop from empty list"); 00064 return NULL; 00065 } 00066 00067 node = PySequence_GetItem(list,-1); 00068 PySequence_DelItem(list,-1); 00069 00070 len -= 1; 00071 if (len > 0) { 00072 returnNode = PySequence_GetItem(list,0); 00073 PyList_SetItem(list,0,node); 00074 if (_siftup(list,0)) 00075 return NULL; 00076 } else { 00077 returnNode = node; 00078 } 00079 00080 return returnNode; 00081 } 00082 00083 static PyObject * 00084 heapreplace(PyObject *self, PyObject *args) { 00085 PyObject *list = NULL; 00086 PyObject *node = NULL; 00087 PyObject *returnNode = NULL; 00088 int len; 00089 00090 if (!PyArg_ParseTuple(args,"O!O",&PyList_Type,&list,&node)) 00091 return NULL; 00092 00093 len = PyList_Size(list); 00094 if (len == 0) { 00095 /* Special-case most common failure cause */ 00096 PyErr_SetString(PyExc_IndexError, "replace on an empty list"); 00097 return NULL; 00098 } 00099 00100 returnNode = PySequence_GetItem(list,0); 00101 PySequence_SetItem(list,0,node); 00102 if (_siftup(list,0)) 00103 return NULL; 00104 00105 return returnNode; 00106 } 00107 00108 static PyObject * 00109 heapify(PyObject *self, PyObject *args) { 00110 int n, i; 00111 PyObject *list; 00112 00113 if (!PyArg_ParseTuple(args,"O!",&PyList_Type,&list)) 00114 return NULL; 00115 n = (PyList_Size(list)/2)-1; 00116 00117 for (i=n;i>=0;i--) { 00118 if (_siftup(list,i)) 00119 return NULL; 00120 } 00121 00122 Py_INCREF(Py_None); 00123 return Py_None; 00124 } 00125 00126 static int 00127 _siftdown(PyObject *list, int startpos, int pos) { 00128 PyObject *newitem, *parent; 00129 int parentpos; 00130 00131 newitem = PySequence_GetItem(list,pos); 00132 00133 PyObject *newitem_wakeTime_obj = PyObject_GetAttrString(newitem, "wakeTime"); 00134 double newitem_wakeTime = 0.0; 00135 if (newitem_wakeTime_obj != NULL) { 00136 newitem_wakeTime = PyFloat_AS_DOUBLE(newitem_wakeTime_obj); 00137 Py_DECREF(newitem_wakeTime_obj); 00138 } 00139 00140 while (pos > startpos) { 00141 parentpos = (pos - 1) >> 1; 00142 parent = PyList_GetItem(list,parentpos); 00143 00144 /* 00145 cmp = PyObject_RichCompareBool(parent,newitem,Py_LE); 00146 if (cmp > 0) 00147 break; 00148 else if (cmp < 0) 00149 return -1; 00150 */ 00151 00152 PyObject *parent_wakeTime_obj = PyObject_GetAttrString(parent, "wakeTime"); 00153 double parent_wakeTime = 0.0; 00154 if (parent_wakeTime_obj != NULL) { 00155 parent_wakeTime = PyFloat_AS_DOUBLE(parent_wakeTime_obj); 00156 Py_DECREF(parent_wakeTime_obj); 00157 } 00158 00159 if (parent_wakeTime <= newitem_wakeTime) { 00160 break; 00161 } 00162 00163 Py_INCREF(parent); 00164 PyList_SetItem(list,pos,parent); 00165 pos = parentpos; 00166 } 00167 PyList_SetItem(list,pos,newitem); 00168 return 0; 00169 } 00170 00171 static int 00172 _siftup(PyObject *list, int pos) { 00173 PyObject *newitem, *right, *child; 00174 int endpos, rightpos, childpos; 00175 int startpos = pos; 00176 00177 endpos = PyList_Size(list); 00178 newitem = PySequence_GetItem(list,pos); 00179 00180 childpos = (2*pos)+1; 00181 while (childpos < endpos) { 00182 rightpos = childpos + 1; 00183 child = PySequence_Fast_GET_ITEM(list,childpos); 00184 00185 PyObject *child_wakeTime_obj = PyObject_GetAttrString(child, "wakeTime"); 00186 double child_wakeTime = 0.0; 00187 if (child_wakeTime_obj != NULL) { 00188 child_wakeTime = PyFloat_AS_DOUBLE(child_wakeTime_obj); 00189 Py_DECREF(child_wakeTime_obj); 00190 } 00191 00192 00193 if (rightpos < endpos) { 00194 right = PySequence_Fast_GET_ITEM(list,rightpos); 00195 00196 PyObject *right_wakeTime_obj = PyObject_GetAttrString(right, "wakeTime"); 00197 double right_wakeTime = 0.0; 00198 if (right_wakeTime_obj != NULL) { 00199 right_wakeTime = PyFloat_AS_DOUBLE(right_wakeTime_obj); 00200 Py_DECREF(right_wakeTime_obj); 00201 } 00202 00203 /* 00204 cmp = PyObject_RichCompareBool(right,child,Py_LE); 00205 if (cmp > 0) 00206 childpos = rightpos; 00207 else if (cmp < 0) 00208 return -1; 00209 */ 00210 00211 if (right_wakeTime <= child_wakeTime) { 00212 childpos = rightpos; 00213 } 00214 } 00215 child = PySequence_GetItem(list,childpos); 00216 PyList_SetItem(list,pos,child); 00217 pos = childpos; 00218 childpos = (2*pos)+1; 00219 } 00220 PyList_SetItem(list,pos,newitem); 00221 00222 return _siftdown(list,startpos,pos); 00223 } 00224 00225 static PyMethodDef heapqcMethods[] = { 00226 {"heappush",heappush,METH_VARARGS}, 00227 {"heappop",heappop,METH_VARARGS}, 00228 {"heapreplace",heapreplace,METH_VARARGS}, 00229 {"heapify",heapify,METH_VARARGS}, 00230 {NULL, NULL} /* Sentinel */ 00231 }; 00232 00233 void initlibheapq(void) { 00234 (void) Py_InitModule("libheapq", heapqcMethods); 00235 }; 00236 00237 void initlibp3heapq(void) { 00238 (void) Py_InitModule("libp3heapq", heapqcMethods); 00239 }; 00240