blob: d7190b59b0cea9fa704437c3c6f3beb0c6d449d6 [file] [log] [blame]
Raymond Hettingera690a992003-11-16 16:17:49 +00001#include "Python.h"
2
3/* set object implementation
4 written and maintained by Raymond D. Hettinger <python@rcn.com>
5 derived from sets.py written by Greg V. Wilson, Alex Martelli,
6 Guido van Rossum, Raymond Hettinger, and Tim Peters.
7
8 Copyright (c) 2003 Python Software Foundation.
9 All rights reserved.
10*/
11
Raymond Hettingera690a992003-11-16 16:17:49 +000012static PyObject *
13make_new_set(PyTypeObject *type, PyObject *iterable)
14{
15 PyObject *data;
16 PyObject *it = NULL;
17 PyObject *item;
18 PySetObject *so;
19
20 /* Get iterator. */
21 if (iterable != NULL) {
22 it = PyObject_GetIter(iterable);
23 if (it == NULL)
24 return NULL;
25 }
26
27 data = PyDict_New();
28 if (data == NULL) {
29 Py_DECREF(it);
30 return NULL;
31 }
32
33 while (it != NULL && (item = PyIter_Next(it)) != NULL) {
34 if (PyDict_SetItem(data, item, Py_True) == -1) {
35 Py_DECREF(it);
36 Py_DECREF(data);
37 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +000038 return NULL;
39 }
40 Py_DECREF(item);
41 }
42 Py_XDECREF(it);
43 if (PyErr_Occurred()) {
44 Py_DECREF(data);
45 return NULL;
46 }
47
48 /* create PySetObject structure */
49 so = (PySetObject *)type->tp_alloc(type, 0);
50 if (so == NULL) {
51 Py_DECREF(data);
52 return NULL;
53 }
54 so->data = data;
55 so->hash = -1;
56
57 return (PyObject *)so;
58}
59
60static PyObject *
Raymond Hettinger50a4bb32003-11-17 16:42:33 +000061frozenset_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
Raymond Hettingera690a992003-11-16 16:17:49 +000062{
63 PyObject *iterable = NULL;
64
65 if (!PyArg_UnpackTuple(args, type->tp_name, 0, 1, &iterable))
66 return NULL;
67 return make_new_set(type, iterable);
68}
69
Raymond Hettinger50a4bb32003-11-17 16:42:33 +000070static PyObject *
71set_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
72{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +000073 return make_new_set(type, NULL);
74}
75
Raymond Hettingera690a992003-11-16 16:17:49 +000076static void
77set_dealloc(PySetObject *so)
78{
79 PyObject_GC_UnTrack(so);
80 Py_XDECREF(so->data);
81 so->ob_type->tp_free(so);
82}
83
84static int
85set_traverse(PySetObject *so, visitproc visit, void *arg)
86{
87 if (so->data)
88 return visit(so->data, arg);
89 return 0;
90}
91
92static PyObject *
93set_iter(PySetObject *so)
94{
95 return PyObject_GetIter(so->data);
96}
97
98static int
99set_len(PySetObject *so)
100{
101 return PyDict_Size(so->data);
102}
103
104static int
105set_contains(PySetObject *so, PyObject *key)
106{
Raymond Hettinger1b92fd52003-11-18 14:15:31 +0000107 return PySequence_Contains(so->data, key);
Raymond Hettingera690a992003-11-16 16:17:49 +0000108}
109
110static PyObject *
111set_copy(PySetObject *so)
112{
113 PyObject *data;
114 PySetObject *newso;
115
116 data = PyDict_Copy(so->data);
117 if (data == NULL)
118 return NULL;
119
120 newso = (PySetObject *)(so->ob_type->tp_alloc(so->ob_type, 0));
121 if (newso == NULL) {
122 Py_DECREF(data);
123 return NULL;
124 }
125 newso->data = data;
126 newso->hash = so->hash;
127 return (PyObject *)newso;
128}
129
130PyDoc_STRVAR(copy_doc, "Return a shallow copy of a set.");
131
132static PyObject *
133set_union(PySetObject *so, PyObject *other)
134{
135 PySetObject *result;
136 PyObject *item, *data, *it;
137
138 result = (PySetObject *)set_copy(so);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000139 if (result == NULL)
140 return NULL;
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000141
142 if (PyAnySet_Check(other)) {
143 if (PyDict_Merge(result->data, ((PySetObject *)other)->data, 0) == -1) {
144 Py_DECREF(result);
145 return NULL;
146 }
147 return (PyObject *)result;
148 }
149
Raymond Hettingera690a992003-11-16 16:17:49 +0000150 it = PyObject_GetIter(other);
151 if (it == NULL) {
152 Py_DECREF(result);
153 return NULL;
154 }
155 data = result->data;
156 while ((item = PyIter_Next(it)) != NULL) {
157 if (PyDict_SetItem(data, item, Py_True) == -1) {
158 Py_DECREF(it);
159 Py_DECREF(result);
160 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000161 return NULL;
162 }
163 Py_DECREF(item);
164 }
165 Py_DECREF(it);
166 if (PyErr_Occurred()) {
167 Py_DECREF(result);
168 return NULL;
169 }
170 return (PyObject *)result;
171}
172
173PyDoc_STRVAR(union_doc,
174 "Return the union of two sets as a new set.\n\
175\n\
176(i.e. all elements that are in either set.)");
177
178static PyObject *
179set_union_update(PySetObject *so, PyObject *other)
180{
181 PyObject *item, *data, *it;
182
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000183 if (PyAnySet_Check(other)) {
184 if (PyDict_Merge(so->data, ((PySetObject *)other)->data, 0) == -1)
185 return NULL;
186 Py_INCREF(so);
187 return (PyObject *)so;
188 }
189
Raymond Hettingera690a992003-11-16 16:17:49 +0000190 it = PyObject_GetIter(other);
191 if (it == NULL)
192 return NULL;
193 data = so->data;
194
195 while ((item = PyIter_Next(it)) != NULL) {
196 if (PyDict_SetItem(data, item, Py_True) == -1) {
197 Py_DECREF(it);
198 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000199 return NULL;
200 }
201 Py_DECREF(item);
202 }
203 Py_DECREF(it);
204 if (PyErr_Occurred())
205 return NULL;
206 Py_RETURN_NONE;
207}
208
209PyDoc_STRVAR(union_update_doc,
210"Update a set with the union of itself and another.");
211
212static PyObject *
213set_or(PySetObject *so, PyObject *other)
214{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000215 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000216 Py_INCREF(Py_NotImplemented);
217 return Py_NotImplemented;
218 }
219 return set_union(so, other);
220}
221
222static PyObject *
223set_ior(PySetObject *so, PyObject *other)
224{
225 PyObject *result;
226
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000227 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000228 Py_INCREF(Py_NotImplemented);
229 return Py_NotImplemented;
230 }
231 result = set_union_update(so, other);
232 if (result == NULL)
233 return NULL;
234 Py_DECREF(result);
235 Py_INCREF(so);
236 return (PyObject *)so;
237}
238
239static PyObject *
240set_intersection(PySetObject *so, PyObject *other)
241{
242 PySetObject *result;
243 PyObject *item, *selfdata, *tgtdata, *it;
244
245 result = (PySetObject *)make_new_set(so->ob_type, NULL);
246 if (result == NULL)
247 return NULL;
248
249 it = PyObject_GetIter(other);
250 if (it == NULL) {
251 Py_DECREF(result);
252 return NULL;
253 }
254
255 selfdata = so->data;
256 tgtdata = result->data;
257 while ((item = PyIter_Next(it)) != NULL) {
Raymond Hettinger1b92fd52003-11-18 14:15:31 +0000258 if (PySequence_Contains(selfdata, item)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000259 if (PyDict_SetItem(tgtdata, item, Py_True) == -1) {
260 Py_DECREF(it);
261 Py_DECREF(result);
262 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000263 return NULL;
264 }
265 }
266 Py_DECREF(item);
267 }
268 Py_DECREF(it);
269 if (PyErr_Occurred()) {
270 Py_DECREF(result);
271 return NULL;
272 }
273 return (PyObject *)result;
274}
275
276PyDoc_STRVAR(intersection_doc,
277"Return the intersection of two sets as a new set.\n\
278\n\
279(i.e. all elements that are in both sets.)");
280
281static PyObject *
282set_intersection_update(PySetObject *so, PyObject *other)
283{
284 PyObject *item, *selfdata, *it, *newdict, *tmp;
285
286 newdict = PyDict_New();
287 if (newdict == NULL)
288 return newdict;
289
290 it = PyObject_GetIter(other);
291 if (it == NULL) {
292 Py_DECREF(newdict);
293 return NULL;
294 }
295
296 selfdata = so->data;
297 while ((item = PyIter_Next(it)) != NULL) {
Raymond Hettinger1b92fd52003-11-18 14:15:31 +0000298 if (PySequence_Contains(selfdata, item)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000299 if (PyDict_SetItem(newdict, item, Py_True) == -1) {
300 Py_DECREF(newdict);
301 Py_DECREF(it);
302 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000303 return NULL;
304 }
305 }
306 Py_DECREF(item);
307 }
308 Py_DECREF(it);
309 if (PyErr_Occurred()) {
310 Py_DECREF(newdict);
311 return NULL;
312 }
313 tmp = so->data;
314 so->data = newdict;
315 Py_DECREF(tmp);
316 Py_RETURN_NONE;
317}
318
319PyDoc_STRVAR(intersection_update_doc,
320"Update a set with the intersection of itself and another.");
321
322static PyObject *
323set_and(PySetObject *so, PyObject *other)
324{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000325 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000326 Py_INCREF(Py_NotImplemented);
327 return Py_NotImplemented;
328 }
329 return set_intersection(so, other);
330}
331
332static PyObject *
333set_iand(PySetObject *so, PyObject *other)
334{
335 PyObject *result;
336
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000337 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000338 Py_INCREF(Py_NotImplemented);
339 return Py_NotImplemented;
340 }
341 result = set_intersection_update(so, other);
342 if (result == NULL)
343 return NULL;
344 Py_DECREF(result);
345 Py_INCREF(so);
346 return (PyObject *)so;
347}
348
349static PyObject *
350set_difference(PySetObject *so, PyObject *other)
351{
352 PySetObject *result;
353 PyObject *item, *tgtdata, *it;
354
355 result = (PySetObject *)set_copy(so);
356 if (result == NULL)
357 return NULL;
358
359 it = PyObject_GetIter(other);
360 if (it == NULL) {
361 Py_DECREF(result);
362 return NULL;
363 }
364
365 tgtdata = result->data;
366 while ((item = PyIter_Next(it)) != NULL) {
367 if (PyDict_DelItem(tgtdata, item) == -1) {
368 if (PyErr_ExceptionMatches(PyExc_KeyError))
369 PyErr_Clear();
370 else {
371 Py_DECREF(it);
372 Py_DECREF(result);
373 Py_DECREF(item);
374 return NULL;
375 }
376 }
377 Py_DECREF(item);
378 }
379 Py_DECREF(it);
380 if (PyErr_Occurred()) {
381 Py_DECREF(result);
382 return NULL;
383 }
384 return (PyObject *)result;
385}
386
387PyDoc_STRVAR(difference_doc,
388"Return the difference of two sets as a new set.\n\
389\n\
390(i.e. all elements that are in this set but not the other.)");
391
392static PyObject *
393set_difference_update(PySetObject *so, PyObject *other)
394{
395 PyObject *item, *tgtdata, *it;
396
397 it = PyObject_GetIter(other);
398 if (it == NULL)
399 return NULL;
400
401 tgtdata = so->data;
402 while ((item = PyIter_Next(it)) != NULL) {
403 if (PyDict_DelItem(tgtdata, item) == -1) {
404 if (PyErr_ExceptionMatches(PyExc_KeyError))
405 PyErr_Clear();
406 else {
407 Py_DECREF(it);
408 Py_DECREF(item);
409 return NULL;
410 }
411 }
412 Py_DECREF(item);
413 }
414 Py_DECREF(it);
415 if (PyErr_Occurred())
416 return NULL;
417 Py_RETURN_NONE;
418}
419
420PyDoc_STRVAR(difference_update_doc,
421"Remove all elements of another set from this set.");
422
423static PyObject *
424set_sub(PySetObject *so, PyObject *other)
425{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000426 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000427 Py_INCREF(Py_NotImplemented);
428 return Py_NotImplemented;
429 }
430 return set_difference(so, other);
431}
432
433static PyObject *
434set_isub(PySetObject *so, PyObject *other)
435{
436 PyObject *result;
437
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000438 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000439 Py_INCREF(Py_NotImplemented);
440 return Py_NotImplemented;
441 }
442 result = set_difference_update(so, other);
443 if (result == NULL)
444 return NULL;
445 Py_DECREF(result);
446 Py_INCREF(so);
447 return (PyObject *)so;
448}
449
450static PyObject *
451set_symmetric_difference(PySetObject *so, PyObject *other)
452{
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000453 PySetObject *result, *otherset=NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000454 PyObject *item, *selfdata, *otherdata, *tgtdata, *it;
455
456 selfdata = so->data;
457
458 result = (PySetObject *)set_copy(so);
459 if (result == NULL)
460 return NULL;
461 tgtdata = result->data;
462
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000463 if (PyDict_Check(other))
464 otherdata = other;
465 else if (PyAnySet_Check(other))
466 otherdata = ((PySetObject *)other)->data;
467 else {
468 otherset = (PySetObject *)make_new_set(so->ob_type, other);
469 if (otherset == NULL) {
470 Py_DECREF(result);
471 return NULL;
472 }
473 otherdata = otherset->data;
474 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000475
476 it = PyObject_GetIter(otherdata);
477 if (it == NULL) {
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000478 Py_XDECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +0000479 Py_DECREF(result);
480 return NULL;
481 }
482
483 while ((item = PyIter_Next(it)) != NULL) {
484 if (PyDict_DelItem(tgtdata, item) == -1) {
485 PyErr_Clear();
486 if (PyDict_SetItem(tgtdata, item, Py_True) == -1) {
487 Py_DECREF(it);
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000488 Py_XDECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +0000489 Py_DECREF(result);
490 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000491 return NULL;
492 }
493 }
494 Py_DECREF(item);
495 }
496 Py_DECREF(it);
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000497 Py_XDECREF(otherset);
Raymond Hettingera690a992003-11-16 16:17:49 +0000498 if (PyErr_Occurred()) {
499 Py_DECREF(result);
500 return NULL;
501 }
502 return (PyObject *)result;
503}
504
505PyDoc_STRVAR(symmetric_difference_doc,
506"Return the symmetric difference of two sets as a new set.\n\
507\n\
508(i.e. all elements that are in exactly one of the sets.)");
509
510static PyObject *
511set_symmetric_difference_update(PySetObject *so, PyObject *other)
512{
513 PyObject *item, *selfdata, *it, *otherdata;
514 PySetObject *otherset = NULL;
515
516 selfdata = so->data;
517
518 if (PyDict_Check(other))
519 otherdata = other;
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000520 else if (PyAnySet_Check(other))
Raymond Hettingera690a992003-11-16 16:17:49 +0000521 otherdata = ((PySetObject *)other)->data;
522 else {
523 otherset = (PySetObject *)make_new_set(so->ob_type, other);
524 if (otherset == NULL)
525 return NULL;
526 otherdata = otherset->data;
527 }
528
529 it = PyObject_GetIter(otherdata);
530 if (it == NULL)
531 return NULL;
532
533 while ((item = PyIter_Next(it)) != NULL) {
Raymond Hettinger1b92fd52003-11-18 14:15:31 +0000534 if (PySequence_Contains(selfdata, item)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000535 if (PyDict_DelItem(selfdata, item) == -1) {
536 Py_XDECREF(otherset);
537 Py_DECREF(it);
538 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000539 return NULL;
540 }
541 } else {
542 if (PyDict_SetItem(selfdata, item, Py_True) == -1) {
543 Py_XDECREF(otherset);
544 Py_DECREF(it);
545 Py_DECREF(item);
Raymond Hettingera690a992003-11-16 16:17:49 +0000546 return NULL;
547 }
548 }
549 Py_DECREF(item);
550 }
551 Py_XDECREF(otherset);
552 Py_DECREF(it);
553 if (PyErr_Occurred())
554 return NULL;
555 Py_RETURN_NONE;
556}
557
558PyDoc_STRVAR(symmetric_difference_update_doc,
559"Update a set with the symmetric difference of itself and another.");
560
561static PyObject *
562set_xor(PySetObject *so, PyObject *other)
563{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000564 if (!PyAnySet_Check(so) || !PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000565 Py_INCREF(Py_NotImplemented);
566 return Py_NotImplemented;
567 }
568 return set_symmetric_difference(so, other);
569}
570
571static PyObject *
572set_ixor(PySetObject *so, PyObject *other)
573{
574 PyObject *result;
575
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000576 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000577 Py_INCREF(Py_NotImplemented);
578 return Py_NotImplemented;
579 }
580 result = set_symmetric_difference_update(so, other);
581 if (result == NULL)
582 return NULL;
583 Py_DECREF(result);
584 Py_INCREF(so);
585 return (PyObject *)so;
586}
587
588static PyObject *
589set_issubset(PySetObject *so, PyObject *other)
590{
591 PyObject *otherdata, *it, *item;
592
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000593 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000594 PyErr_SetString(PyExc_TypeError, "can only compare to a set");
595 return NULL;
596 }
597 if (set_len(so) > set_len((PySetObject *)other))
598 Py_RETURN_FALSE;
599
600 it = PyObject_GetIter(so->data);
601 if (it == NULL)
602 return NULL;
603
604 otherdata = ((PySetObject *)other)->data;
605 while ((item = PyIter_Next(it)) != NULL) {
Raymond Hettinger1b92fd52003-11-18 14:15:31 +0000606 if (!PySequence_Contains(otherdata, item)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000607 Py_DECREF(it);
608 Py_DECREF(item);
609 Py_RETURN_FALSE;
610 }
611 Py_DECREF(item);
612 }
613 Py_DECREF(it);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000614 if (PyErr_Occurred())
615 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000616 Py_RETURN_TRUE;
617}
618
619PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");
620
621static PyObject *
622set_issuperset(PySetObject *so, PyObject *other)
623{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000624 if (!PyAnySet_Check(other)) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000625 PyErr_SetString(PyExc_TypeError, "can only compare to a set");
626 return NULL;
627 }
628 return set_issubset((PySetObject *)other, (PyObject *)so);
629}
630
631PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");
632
633static long
634set_nohash(PyObject *self)
635{
636 PyErr_SetString(PyExc_TypeError, "set objects are unhashable");
637 return -1;
638}
639
640static int
641set_nocmp(PyObject *self)
642{
643 PyErr_SetString(PyExc_TypeError, "cannot compare sets using cmp()");
644 return -1;
645}
646
647static long
648frozenset_hash(PyObject *self)
649{
650 PyObject *it, *item;
651 PySetObject *so = (PySetObject *)self;
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000652 long hash = 0, x;
Raymond Hettingera690a992003-11-16 16:17:49 +0000653
654 if (so->hash != -1)
655 return so->hash;
656
657 it = PyObject_GetIter(((PySetObject *)so)->data);
658 if (it == NULL)
659 return -1;
660
661 while ((item = PyIter_Next(it)) != NULL) {
Raymond Hettinger82d73dd2003-11-20 22:54:33 +0000662 x = PyObject_Hash(item);
663 /* Applying x*(x+1) breaks-up linear relationships so that
664 h(1) ^ h(2) will be less likely to coincide with hash(3).
665 Multiplying by a large prime increases the dispersion
666 between consecutive hashes. Adding one bit from the
667 original restores the one bit lost during the multiply
668 (all the products are even numbers). */
669 hash ^= (x * (x+1) * 3644798167) | (x&1);
Raymond Hettingera690a992003-11-16 16:17:49 +0000670 Py_DECREF(item);
671 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000672 Py_DECREF(it);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000673 if (PyErr_Occurred())
674 return -1;
675 so->hash = hash;
Raymond Hettingera690a992003-11-16 16:17:49 +0000676 return hash;
677}
678
679static PyObject *
680set_richcompare(PySetObject *v, PyObject *w, int op)
681{
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000682 if(!PyAnySet_Check(w)) {
683 if (op == Py_EQ)
684 Py_RETURN_FALSE;
685 if (op == Py_NE)
686 Py_RETURN_TRUE;
Raymond Hettingera690a992003-11-16 16:17:49 +0000687 PyErr_SetString(PyExc_TypeError, "can only compare to a set");
688 return NULL;
689 }
690 switch (op) {
691 case Py_EQ:
692 case Py_NE:
693 return PyObject_RichCompare(((PySetObject *)v)->data,
694 ((PySetObject *)w)->data, op);
695 case Py_LE:
696 return set_issubset((PySetObject *)v, w);
697 case Py_GE:
698 return set_issuperset((PySetObject *)v, w);
699 case Py_LT:
700 if (set_len(v) >= set_len((PySetObject *)w))
701 Py_RETURN_FALSE;
702 return set_issubset((PySetObject *)v, w);
703 case Py_GT:
704 if (set_len(v) <= set_len((PySetObject *)w))
705 Py_RETURN_FALSE;
706 return set_issuperset((PySetObject *)v, w);
707 }
708 Py_INCREF(Py_NotImplemented);
709 return Py_NotImplemented;
710}
711
712static PyObject *
713set_repr(PySetObject *so)
714{
715 PyObject *keys, *result, *listrepr;
716
717 keys = PyDict_Keys(so->data);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000718 if (keys == NULL)
719 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000720 listrepr = PyObject_Repr(keys);
721 Py_DECREF(keys);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000722 if (listrepr == NULL)
723 return NULL;
Raymond Hettingera690a992003-11-16 16:17:49 +0000724
725 result = PyString_FromFormat("%s(%s)", so->ob_type->tp_name,
726 PyString_AS_STRING(listrepr));
727 Py_DECREF(listrepr);
728 return result;
729}
730
731static int
732set_tp_print(PySetObject *so, FILE *fp, int flags)
733{
734 PyObject *it, *item;
735 int firstpass=1;
736
737 it = PyObject_GetIter(so->data);
738 if (it == NULL)
739 return -1;
740 fprintf(fp, "%s([", so->ob_type->tp_name);
741
742 while ((item = PyIter_Next(it)) != NULL) {
743 if (firstpass == 1)
744 firstpass = 0;
745 else
Raymond Hettingere2c277a2003-11-16 16:36:58 +0000746 fprintf(fp, ", ");
Raymond Hettingera690a992003-11-16 16:17:49 +0000747 if (PyObject_Print(item, fp, 0) != 0) {
748 Py_DECREF(it);
749 Py_DECREF(item);
750 return -1;
751 }
752 Py_DECREF(item);
753 }
754 Py_DECREF(it);
755 fprintf(fp, "])");
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000756 if (PyErr_Occurred())
757 return -1;
Raymond Hettingera690a992003-11-16 16:17:49 +0000758 return 0;
759}
760
761static PyObject *
762set_clear(PySetObject *so)
763{
764 PyDict_Clear(so->data);
765 so->hash = -1;
766 Py_INCREF(Py_None);
767 return Py_None;
768}
769
770PyDoc_STRVAR(clear_doc, "Remove all elements from this set.");
771
772static int
773set_tp_clear(PySetObject *so)
774{
775 PyDict_Clear(so->data);
776 so->hash = -1;
777 return 0;
778}
779
780static PyObject *
781set_add(PySetObject *so, PyObject *item)
782{
783 if (PyDict_SetItem(so->data, item, Py_True) == -1)
784 return NULL;
785 Py_INCREF(Py_None);
786 return Py_None;
787}
788
789PyDoc_STRVAR(add_doc,
790"Add an element to a set.\n\
791\n\
792This has no effect if the element is already present.");
793
794static PyObject *
795set_remove(PySetObject *so, PyObject *item)
796{
797 if (PyDict_DelItem(so->data, item) == -1)
798 return NULL;
799 Py_INCREF(Py_None);
800 return Py_None;
801}
802
803PyDoc_STRVAR(remove_doc,
804"Remove an element from a set; it must be a member.\n\
805\n\
806If the element is not a member, raise a KeyError.");
807
808static PyObject *
809set_discard(PySetObject *so, PyObject *item)
810{
Guido van Rossumb61982b2003-11-18 19:27:19 +0000811 if (PyDict_DelItem(so->data, item) == -1) {
Raymond Hettingera690a992003-11-16 16:17:49 +0000812 if (PyErr_ExceptionMatches(PyExc_KeyError))
813 PyErr_Clear();
814 else
815 return NULL;
Guido van Rossumb61982b2003-11-18 19:27:19 +0000816 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000817 Py_INCREF(Py_None);
818 return Py_None;
819}
820
821PyDoc_STRVAR(discard_doc,
822"Remove an element from a set if it is a member.\n\
823\n\
824If the element is not a member, do nothing.");
825
826static PyObject *
827set_pop(PySetObject *so)
828{
829 PyObject *key, *value;
830 int pos = 0;
831
832 if (!PyDict_Next(so->data, &pos, &key, &value)) {
833 PyErr_SetString(PyExc_KeyError, "pop from an empty set");
834 return NULL;
835 }
836 Py_INCREF(key);
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000837 if (PyDict_DelItem(so->data, key) == -1) {
838 Py_DECREF(key);
839 return NULL;
840 }
Raymond Hettingera690a992003-11-16 16:17:49 +0000841 return key;
842}
843
844PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.");
845
846static PyObject *
847set_reduce(PySetObject *so)
848{
849 PyObject *keys=NULL, *args=NULL, *result=NULL;
850
851 keys = PyDict_Keys(so->data);
852 if (keys == NULL)
853 goto done;
854 args = PyTuple_Pack(1, keys);
855 if (args == NULL)
856 goto done;
857 result = PyTuple_Pack(2, so->ob_type, args);
858done:
859 Py_XDECREF(args);
860 Py_XDECREF(keys);
861 return result;
862}
863
864PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
865
Raymond Hettinger50a4bb32003-11-17 16:42:33 +0000866static int
867set_init(PySetObject *self, PyObject *args, PyObject *kwds)
868{
869 PyObject *iterable = NULL;
870 PyObject *result;
871
872 if (!PyAnySet_Check(self))
873 return -1;
874 if (!PyArg_UnpackTuple(args, self->ob_type->tp_name, 0, 1, &iterable))
875 return -1;
876 PyDict_Clear(self->data);
877 self->hash = -1;
878 if (iterable == NULL)
879 return 0;
880 result = set_union_update(self, iterable);
881 if (result != NULL) {
882 Py_DECREF(result);
883 return 0;
884 }
885 return -1;
886}
887
Raymond Hettingera690a992003-11-16 16:17:49 +0000888static PySequenceMethods set_as_sequence = {
889 (inquiry)set_len, /* sq_length */
890 0, /* sq_concat */
891 0, /* sq_repeat */
892 0, /* sq_item */
893 0, /* sq_slice */
894 0, /* sq_ass_item */
895 0, /* sq_ass_slice */
896 (objobjproc)set_contains, /* sq_contains */
897};
898
899/* set object ********************************************************/
900
901static PyMethodDef set_methods[] = {
902 {"add", (PyCFunction)set_add, METH_O,
903 add_doc},
904 {"clear", (PyCFunction)set_clear, METH_NOARGS,
905 clear_doc},
906 {"copy", (PyCFunction)set_copy, METH_NOARGS,
907 copy_doc},
908 {"__copy__", (PyCFunction)set_copy, METH_NOARGS,
909 copy_doc},
910 {"discard", (PyCFunction)set_discard, METH_O,
911 discard_doc},
912 {"difference", (PyCFunction)set_difference, METH_O,
913 difference_doc},
914 {"difference_update", (PyCFunction)set_difference_update, METH_O,
915 difference_update_doc},
916 {"intersection",(PyCFunction)set_intersection, METH_O,
917 intersection_doc},
918 {"intersection_update",(PyCFunction)set_intersection_update, METH_O,
919 intersection_update_doc},
920 {"issubset", (PyCFunction)set_issubset, METH_O,
921 issubset_doc},
922 {"issuperset", (PyCFunction)set_issuperset, METH_O,
923 issuperset_doc},
924 {"pop", (PyCFunction)set_pop, METH_NOARGS,
925 pop_doc},
926 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
927 reduce_doc},
928 {"remove", (PyCFunction)set_remove, METH_O,
929 remove_doc},
930 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
931 symmetric_difference_doc},
932 {"symmetric_difference_update",(PyCFunction)set_symmetric_difference_update, METH_O,
933 symmetric_difference_update_doc},
934 {"union", (PyCFunction)set_union, METH_O,
935 union_doc},
936 {"union_update",(PyCFunction)set_union_update, METH_O,
937 union_update_doc},
938 {NULL, NULL} /* sentinel */
939};
940
941static PyNumberMethods set_as_number = {
942 0, /*nb_add*/
943 (binaryfunc)set_sub, /*nb_subtract*/
944 0, /*nb_multiply*/
945 0, /*nb_divide*/
946 0, /*nb_remainder*/
947 0, /*nb_divmod*/
948 0, /*nb_power*/
949 0, /*nb_negative*/
950 0, /*nb_positive*/
951 0, /*nb_absolute*/
952 0, /*nb_nonzero*/
953 0, /*nb_invert*/
954 0, /*nb_lshift*/
955 0, /*nb_rshift*/
956 (binaryfunc)set_and, /*nb_and*/
957 (binaryfunc)set_xor, /*nb_xor*/
958 (binaryfunc)set_or, /*nb_or*/
959 0, /*nb_coerce*/
960 0, /*nb_int*/
961 0, /*nb_long*/
962 0, /*nb_float*/
963 0, /*nb_oct*/
964 0, /*nb_hex*/
965 0, /*nb_inplace_add*/
966 (binaryfunc)set_isub, /*nb_inplace_subtract*/
967 0, /*nb_inplace_multiply*/
968 0, /*nb_inplace_divide*/
969 0, /*nb_inplace_remainder*/
970 0, /*nb_inplace_power*/
971 0, /*nb_inplace_lshift*/
972 0, /*nb_inplace_rshift*/
973 (binaryfunc)set_iand, /*nb_inplace_and*/
974 (binaryfunc)set_ixor, /*nb_inplace_xor*/
975 (binaryfunc)set_ior, /*nb_inplace_or*/
976};
977
978PyDoc_STRVAR(set_doc,
979"set(iterable) --> set object\n\
980\n\
981Build an unordered collection.");
982
983PyTypeObject PySet_Type = {
984 PyObject_HEAD_INIT(&PyType_Type)
985 0, /* ob_size */
986 "set", /* tp_name */
987 sizeof(PySetObject), /* tp_basicsize */
988 0, /* tp_itemsize */
989 /* methods */
990 (destructor)set_dealloc, /* tp_dealloc */
991 (printfunc)set_tp_print, /* tp_print */
992 0, /* tp_getattr */
993 0, /* tp_setattr */
994 (cmpfunc)set_nocmp, /* tp_compare */
995 (reprfunc)set_repr, /* tp_repr */
996 &set_as_number, /* tp_as_number */
997 &set_as_sequence, /* tp_as_sequence */
998 0, /* tp_as_mapping */
999 set_nohash, /* tp_hash */
1000 0, /* tp_call */
1001 0, /* tp_str */
1002 PyObject_GenericGetAttr, /* tp_getattro */
1003 0, /* tp_setattro */
1004 0, /* tp_as_buffer */
1005 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
1006 Py_TPFLAGS_BASETYPE, /* tp_flags */
1007 set_doc, /* tp_doc */
1008 (traverseproc)set_traverse, /* tp_traverse */
1009 (inquiry)set_tp_clear, /* tp_clear */
1010 (richcmpfunc)set_richcompare, /* tp_richcompare */
1011 0, /* tp_weaklistoffset */
1012 (getiterfunc)set_iter, /* tp_iter */
1013 0, /* tp_iternext */
1014 set_methods, /* tp_methods */
1015 0, /* tp_members */
1016 0, /* tp_getset */
1017 0, /* tp_base */
1018 0, /* tp_dict */
1019 0, /* tp_descr_get */
1020 0, /* tp_descr_set */
1021 0, /* tp_dictoffset */
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001022 (initproc)set_init, /* tp_init */
Raymond Hettingera690a992003-11-16 16:17:49 +00001023 PyType_GenericAlloc, /* tp_alloc */
1024 set_new, /* tp_new */
1025 PyObject_GC_Del, /* tp_free */
1026};
1027
1028/* frozenset object ********************************************************/
1029
1030
1031static PyMethodDef frozenset_methods[] = {
1032 {"copy", (PyCFunction)set_copy, METH_NOARGS,
1033 copy_doc},
1034 {"__copy__", (PyCFunction)set_copy, METH_NOARGS,
1035 copy_doc},
1036 {"difference",(PyCFunction)set_difference, METH_O,
1037 difference_doc},
1038 {"intersection",(PyCFunction)set_intersection, METH_O,
1039 intersection_doc},
1040 {"issubset",(PyCFunction)set_issubset, METH_O,
1041 issubset_doc},
1042 {"issuperset",(PyCFunction)set_issuperset, METH_O,
1043 issuperset_doc},
1044 {"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
1045 reduce_doc},
1046 {"symmetric_difference",(PyCFunction)set_symmetric_difference, METH_O,
1047 symmetric_difference_doc},
1048 {"union", (PyCFunction)set_union, METH_O,
1049 union_doc},
1050 {NULL, NULL} /* sentinel */
1051};
1052
1053static PyNumberMethods frozenset_as_number = {
1054 0, /*nb_add*/
1055 (binaryfunc)set_sub, /*nb_subtract*/
1056 0, /*nb_multiply*/
1057 0, /*nb_divide*/
1058 0, /*nb_remainder*/
1059 0, /*nb_divmod*/
1060 0, /*nb_power*/
1061 0, /*nb_negative*/
1062 0, /*nb_positive*/
1063 0, /*nb_absolute*/
1064 0, /*nb_nonzero*/
1065 0, /*nb_invert*/
1066 0, /*nb_lshift*/
1067 0, /*nb_rshift*/
1068 (binaryfunc)set_and, /*nb_and*/
1069 (binaryfunc)set_xor, /*nb_xor*/
1070 (binaryfunc)set_or, /*nb_or*/
1071};
1072
1073PyDoc_STRVAR(frozenset_doc,
1074"frozenset(iterable) --> frozenset object\n\
1075\n\
1076Build an immutable unordered collection.");
1077
1078PyTypeObject PyFrozenSet_Type = {
1079 PyObject_HEAD_INIT(&PyType_Type)
1080 0, /* ob_size */
1081 "frozenset", /* tp_name */
1082 sizeof(PySetObject), /* tp_basicsize */
1083 0, /* tp_itemsize */
1084 /* methods */
1085 (destructor)set_dealloc, /* tp_dealloc */
1086 (printfunc)set_tp_print, /* tp_print */
1087 0, /* tp_getattr */
1088 0, /* tp_setattr */
1089 (cmpfunc)set_nocmp, /* tp_compare */
1090 (reprfunc)set_repr, /* tp_repr */
1091 &frozenset_as_number, /* tp_as_number */
1092 &set_as_sequence, /* tp_as_sequence */
1093 0, /* tp_as_mapping */
1094 frozenset_hash, /* tp_hash */
1095 0, /* tp_call */
1096 0, /* tp_str */
1097 PyObject_GenericGetAttr, /* tp_getattro */
1098 0, /* tp_setattro */
1099 0, /* tp_as_buffer */
1100 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_CHECKTYPES |
1101 Py_TPFLAGS_BASETYPE, /* tp_flags */
1102 frozenset_doc, /* tp_doc */
1103 (traverseproc)set_traverse, /* tp_traverse */
1104 0, /* tp_clear */
1105 (richcmpfunc)set_richcompare, /* tp_richcompare */
1106 0, /* tp_weaklistoffset */
1107 (getiterfunc)set_iter, /* tp_iter */
1108 0, /* tp_iternext */
1109 frozenset_methods, /* tp_methods */
1110 0, /* tp_members */
1111 0, /* tp_getset */
1112 0, /* tp_base */
1113 0, /* tp_dict */
1114 0, /* tp_descr_get */
1115 0, /* tp_descr_set */
1116 0, /* tp_dictoffset */
1117 0, /* tp_init */
1118 PyType_GenericAlloc, /* tp_alloc */
Raymond Hettinger50a4bb32003-11-17 16:42:33 +00001119 frozenset_new, /* tp_new */
Raymond Hettingera690a992003-11-16 16:17:49 +00001120 PyObject_GC_Del, /* tp_free */
1121};