1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
|
<HTML>
<HEAD>
<TITLE>Stack - A stack implementation for Python</TITLE>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000">
<HR NOSHADE WIDTH="100%">
<H2>mxStack - A stack implementation for Python</H2>
<HR SIZE=1 NOSHADE WIDTH="100%">
<TABLE WIDTH="100%">
<TR>
<TD>
<SMALL>
<A HREF="#Interface">Interface</A> :
<A HREF="#Examples">Examples</A> :
<A HREF="#API">C API</A> :
<A HREF="#Structure">Structure</A> :
<A HREF="#Installation">Download & Installation</A> :
<A HREF="#Copyright">Copyright</A> :
<A HREF="#History">History</A> :
<A HREF="" TARGET="_top">Home</A>
</SMALL>
</TD>
<TD ALIGN=RIGHT>
<SMALL>
<FONT COLOR="#FF0000">Version 0.3.0</FONT>
</SMALL>
</TD>
</TABLE>
<HR SIZE=1 NOSHADE WIDTH="100%">
<H3>Introduction</H3>
<UL>
<P>
Though stacks can be emulated with Python lists, this type
provides a simple interface to the data structure, both in
Python and in C. Because of the function call overhead
calling the methods from Python it is only a tad faster than
a corresponding list emulation. Called from within an C
extension shows a more significant performance increase. The
included <TT>stackbench.py</TT> gives an impression of how
the different methods relate w/r to speed:
<PRE>
projects/Stack> python1.5 -O stackbench.py 1000 100 100
list: 1.11
tuples: 0.6
Stack (with push + pop): 0.72
Stack (with push + pop_many): 0.5
Stack (with << + >>): 0.85
Stack (with push_many + pop_many): 0.47
UserStack: 1.79
</PRE>
<P>
Note that the tuple version has a few disadvantages when
used for big stacks: for one it uses lots of memory (20
bytes per entry slot; Stack uses 20 bytes + 4 bytes per
entry slot) and deallocation can become a problem -- this is
done using recursion with one level per stack element. For
small stacks it still is unbeatable, though (it has no
function call overhead). BTW, the UserStack implementation
uses the same technique: the figures shown mainly result
from Python method call overhead.
<P>
Because stacks are normally used only temporarily, the Stack
implementation only grows the memory buffer used for holding
the entry slots. It never shrinks it. This has an advantage
of reducing malloc overhead when doing e.g. depth first
search, but also the disadvantage of using more memory in
degenerate cases. To compensate for this, simply call the
.resize() method every now and then. It forces the used
buffer to be resized.
<P>
</UL>
<A NAME="Interface">
<H3>Interface</H3>
<UL>
<P><B>Stack Constructors</B>
<P>There are two ways to construct a <TT>Stack</TT> from scratch:
<P><DL>
<DT><CODE><FONT COLOR="#000099">
Stack([initial_size])
</FONT></CODE></DT>
<DD>Returns a new empty Stack instance allocating at least
the given number of slots for stack elements. If the
parameter is not given a reasonable default is
chosen.</DD><P>
<DT><CODE><FONT COLOR="#000099">
StackFromSequence(seq)
</FONT></CODE></DT>
<DD>Constructs a Stack instance from the given sequence. The
instance is filled with all the elements found in the
sequence by pushing the items from index 0 to len(seq)-1 in
that order, i.e. popping all elements from the Stack results
in a reversed sequence. </DD><P>
</DL>
<B>Instance Methods</B>
<P>A <TT>Stack</TT> instance has the following methods:
<P><DL>
<DT><CODE><FONT COLOR="#000099">
push(x)</FONT></CODE></DT>
<DD>
Pushes the object x onto the stack.</DD><P>
<DT><CODE><FONT COLOR="#000099">
push_many(sequences)</FONT></CODE></DT>
<DD>
Pushes the objects in <CODE>sequence</CODE> from left to
right onto the stack. If errors occur during this process,
the already pushed elements are discarded from the stack
and it returns to its original state.</CODE></DD><P>
<DT><CODE><FONT COLOR="#000099">
pop()</FONT></CODE></DT>
<DD>
Pops the top element off of the stack.</DD><P>
<DT><CODE><FONT COLOR="#000099">
pop_many(n)</FONT></CODE></DT>
<DD>
Pops the top <CODE>n</CODE> elements and returns them in
form of a tuple. If less than <CODE>n</CODE> elements are
on the stack, the tuple will contain all stack entries and
the stack will then be empty again. The order is top to
bottom, i.e. <CODE>s.pop_many(2) ==
(s.pop(),s.pop())</CODE></DD><P>
<DT><CODE><FONT COLOR="#000099">
as_tuple()</FONT></CODE></DT>
<DD>
Returns the stack's content as tuple, without modifying
it.</DD><P>
<DT><CODE><FONT COLOR="#000099">
as_list()</FONT></CODE></DT>
<DD>
Returns the stack's content as list, without modifying
it.</DD><P>
<DT><CODE><FONT COLOR="#000099">
clear()</FONT></CODE></DT>
<DD>
Clears the stack.</DD><P>
<DT><CODE><FONT COLOR="#000099">
resize([size=len(stack)])</FONT></CODE></DT>
<DD>
Resize the stack buffer to hold at least <CODE>size</CODE>
entries.
<P>
You can call this method without argument to force the
stack to shrink its memory buffer to the minimal limit
needed to hold the contained elements. </DD><P>
</DL>
<P>Note that no method for testing emtpyness is provided. Use
len() for that or simply test for trueness, e.g. <CODE>while
s: print s.pop()</CODE> will loop as long as there are
elements left on the Stack s. This is much faster than going
through the method calling process -- even when the method
being called is written in C.
<P>
</UL>
<A NAME="Examples">
<H3>Examples of Use</H3>
<UL>
<P>Well, there's not much to show:
<FONT COLOR="#000099"><PRE>
from Stack import *
s = Stack()
for i in range(1000):
s.push(i)
while s:
print s.pop()
# which could also be done as:
s = StackFromSequence(range(1000))
while s:
print s.pop()
# or a little different
s = StackFromSequence(range(1000))
print s.as_tuple()
print s.as_list()
</PRE></FONT>
</UL>
<A NAME="API">
<H3>Supported Data Types in the C-API</H3>
<UL>
<P>Please have look at the file <TT>mxStack.h</TT> for
details. Basically all of the above Python interfaces are
also available in the C API.
<P>To access the module, do the following (note the
similarities with Python's way of accessing functions from a
module):
<PRE>
#include "mxStack.h"
...
PyObject *v;
/* Import the mxStack module */
if (mxStack_ImportModuleAndAPI())
goto onError;
/* Access functions from the exported C API through mxStack */
v = mxStack.Stack(0);
if (!v)
goto onError;
/* Type checking */
if (mxStack_Check(v))
printf("Works.\n");
Py_DECREF(v);
...
</PRE>
<P>
</UL>
<A NAME="Structure">
<H3>Package Structure</H3>
<UL>
<PRE>
[Stack]
mxStack
</PRE>
<P>Entries enclosed in brackets are packages (i.e. they are
directories that include a <TT>__init__.py</TT> file). Ones
without brackets are just simple subdirectories that are not
accessible via <CODE>import</CODE>. These are used for
compiling the C extension modules which will get installed in
the same place where all your other site specific extensions
live (e.g. <TT>/usr/local/lib/python-x.xx/site-packages</TT>).
<P>The package Stack imports all symbols from the extension
mxStack, so <CODE>import Stack; s = Stack.Stack()</CODE> gives
you a Stack instance in <CODE>s</CODE>.
<P>
</UL>
<A NAME="Installation">
<H3>Installation</H3>
<UL>
<P>First, download the <A HREF="mxStack-0.3.0.zip">archive</A>,
unzip it to a <I>directory on your Python path</I>
e.g. <TT>/usr/local/lib/python1.5/site-packages/</TT> on Unix
or <TT>C:\Python\Lib\</TT> under Windows and then follow these
steps (assuming you have already installed Python):
<P>
An pre-compiled Windows version of the extension is included
in the package, so if you're running WinXX, you can skip the
following and start using the package right away.
<P><OL>
<LI>
run <TT>make -f Makefile.pre.in boot</TT> in the mxStack
directory</LI>
<LI>
run <TT>make</TT></LI>
<LI>
get Python 1.5 or above running, and execute <TT>test.py</TT>; it
should not report any errors.</LI>
<LI>
give me feedback <TT>:-)</TT></LI>
</OL>
<P>Though the module has been tested, there may still be some
bugs left. Please post any bug reports, questions
etc. directly to <A
HREF="mailto:mal@lemburg.com?subject=mxStack">me</A>.
</UL>
<H3>What I'd like to hear from you...</H3>
<UL>
<P><UL>
<LI>
Can you get the module to compile/work on other Unix
platforms other than Linux ? </LI>
<!--
<LI>
Could someone contribute a compiled .pyd-file for Windows 95/NT ?
-->
</UL>
</UL>
<A NAME="Copyright">
<H3>Copyright & Disclaimer</H3>
<UL>
<P>© 1997, 1998, Copyright by Marc-André Lemburg; All
Rights Reserved. mailto: <A
HREF="mailto:mal@lemburg.com?subject=mxStack">mal@lemburg.com</A>
<P>Permission to use, copy, modify, and distribute this
software and its documentation for any purpose and without fee
or royalty is hereby granted, provided that the above
copyright notice appear in all copies and that both the
copyright notice and this permission notice appear in
supporting documentation or portions thereof, including
modifications, that you make.
<P>THE AUTHOR MARC-ANDRE LEMBURG DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL THE AUTHOR BE
LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
OR PERFORMANCE OF THIS SOFTWARE !
</UL>
<A NAME="History">
<H3>History & Future</H3>
<UL>
<P>Changes from <A HREF="mxStack-0.2.zip">0.2.2</A> to 0.3.0:
<UL>
<LI>Added .pop_many(), .resize() and .clear().
<P><LI>Added mxStack_PopMany, mxStack_PushMany,
mxStack_Clear, mxStack_Length to the C API.
<P><LI>Fixed a memory leak in StackFromSequence().
<P><LI>Fixed in bug in the non-zero testing code.
</UL>
<P>Changes from <A HREF="mxStack-0.1.zip">0.1</A> to 0.2.2:
<UL>
<LI>Version 0.2.2: Fixed a bug that caused stack.push()
to dump core when called without argument. Also added some
minor speedups.
<P><LI>Version 0.2.1: added method pop_many().
<P><LI>Converted the module into a package called
'Stack'. This imports the C extension mxStack.
</UL>
<P>
</UL>
<HR WIDTH="100%">
<CENTER><FONT SIZE=-1>© 1997, 1998, Copyright by
Marc-André Lemburg; All Rights Reserved. mailto: <A
HREF="mailto:mal@lemburg.com?subject=mxStack">mal@lemburg.com</A>
</FONT></CENTER>
</BODY>
</HTML>
|
