This repository has been archived by the owner on Jan 30, 2023. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 7
/
bitset.pxd
81 lines (70 loc) · 3.24 KB
/
bitset.pxd
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
"""
Cython bitset types
"""
#*****************************************************************************
# Copyright (C) 2008 Robert Bradshaw <robertwb@math.washington.edu>
#
# Distributed under the terms of the GNU General Public License (GPL)
# as published by the Free Software Foundation; either version 2 of
# the License, or (at your option) any later version.
# http://www.gnu.org/licenses/
#*****************************************************************************
# This file declares the bitset types. The implementation of the basic
# Cython type bitset_t (inline functions) is in bitset.pxi, the
# implementation of the Python class is in bitset.pyx. The latter file
# also contains all doctests.
cdef extern from *:
# Given an element index n in a set, (n >> index_shift) gives the
# corresponding limb number.
int index_shift "(sizeof(mp_limb_t) == 8 ? 6 : 5)"
from sage.libs.gmp.types cimport *
cdef struct bitset_s:
# The size of a bitset B counts the maximum number of bits that B can
# hold. This size is independent of how many elements of B are toggled to
# 1. For example, say B is the bitset 1001. Then B has size 4, with the
# first and fourth elements toggled to 1, reading from left to right.
# We can also think of the size of a bitset as its capacity.
mp_bitcnt_t size
# A limb is that part of a bitset that can fit into an mp_limb_t
# (typically, 32 bits on a 32-bit machine and 64 bits on a 64-bit
# machine). This counts the number of limbs to represent a bitset.
# If a bitset has size <= n, then the whole bitset fits into a limb
# and we only require one limb to represent the bitset. However, if
# the bitset has size > n, we require more than one limb to
# represent the bitset. For example, if a limb is 64 bits in length
# and the bitset has size 96 bits, then we require at most two limbs
# to represent the bitset.
#
# NOTE: some code assumes that mp_limb_t is an unsigned long
# (this assumption is always true in practice).
mp_size_t limbs
# The individual bits of a bitset.
mp_limb_t* bits
ctypedef bitset_s bitset_t[1]
# Python layer over bitset_t
cdef class FrozenBitset:
cdef bitset_t _bitset
cdef FrozenBitset _new(self,long int capacity)
cpdef FrozenBitset _larger_capacity_(self, long size)
cpdef long capacity(self)
cpdef bint isempty(self)
cpdef bint issubset(self, FrozenBitset other) except -1
cpdef bint issuperset(self, FrozenBitset other) except -1
cpdef bint isdisjoint(self, FrozenBitset other) except -1
cpdef _union(self, FrozenBitset other)
cpdef intersection(self, FrozenBitset other)
cpdef difference(self, FrozenBitset other)
cpdef symmetric_difference(self, FrozenBitset other)
cpdef complement(self)
cpdef __copy__(self)
cdef class Bitset(FrozenBitset):
cpdef __copy__(self)
cpdef update(self, FrozenBitset other)
cpdef intersection_update(self, FrozenBitset other)
cpdef difference_update(self, FrozenBitset other)
cpdef symmetric_difference_update(self, FrozenBitset other)
cpdef add(self, unsigned long n)
cpdef remove(self, unsigned long n)
cpdef discard(self, unsigned long n)
cpdef pop(self)
cpdef clear(self)