00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include <Python.h>
00013
00014
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
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
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
00146
00147
00148
00149
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
00205
00206
00207
00208
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}
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