Panda3D

heapq.cxx

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 
 All Classes Functions Variables Enumerations