← Back to branch summary

~ubuntu-branches/ubuntu/wily/julia/wily

« back to all changes in this revision

Viewing changes to base/intset.jl

  • Committer: Package Import Robot
  • Author(s): Sébastien Villemot
  • Date: 2013-02-06 17:54:29 UTC
  • mfrom: (1.1.3)
  • Revision ID: package-import@ubuntu.com-20130206175429-13br5kqpkfjqdmre
Tags: 0.0.0+20130206.git32ff5759-1
* New upstream snapshot.
* debian/copyright: reflect upstream changes
* debian/rules: update get-orig-source to reflect upstream changes
   + Don't ship nginx
   + Adapt for new configure-random target in deps/Makefile
* Enable build of Tk wrapper.
   + debian/control: add build dependency on tk-dev
   + debian/rules: add tk rule to build-arch
* debian/julia.install: install VERSION and COMMIT files
* no-webrepl.patch: new patch
* Refresh other patches
* Add source override for config.status file under deps/random/

Show diffs side-by-side

added added

removed removed

Lines of Context:
base/intset.jl
6
6
    IntSet() = new(zeros(Uint32,256>>>5), 256, false)
7
7
end
8
8
 
9
 
IntSet(args...) = (s=IntSet(); for a in args; add(s,a); end; s)
 
9
IntSet(args...) = (s=IntSet(); for a in args; add!(s,a); end; s)
10
10
 
11
11
similar(s::IntSet) = IntSet()
12
12
 
17
17
        lim = ((top+31) & -32)>>>5
18
18
        olsz = length(s.bits)
19
19
        if olsz < lim
20
 
            grow(s.bits, lim-olsz)
 
20
            grow!(s.bits, lim-olsz)
21
21
            fill = s.fill1s ? uint32(-1) : uint32(0)
22
22
            for i=(olsz+1):lim; s.bits[i] = fill; end
23
23
        end
26
26
    s.limit
27
27
end
28
28
 
29
 
function add(s::IntSet, n::Integer)
 
29
function add!(s::IntSet, n::Integer)
30
30
    if n >= s.limit
31
31
        if s.fill1s
32
32
            return s
39
39
    return s
40
40
end
41
41
 
42
 
function add_each(s::IntSet, ns)
 
42
function add_each!(s::IntSet, ns)
43
43
    for n in ns
44
 
        add(s, n)
 
44
        add!(s, n)
45
45
    end
46
46
    return s
47
47
end
48
48
 
49
 
function del(s::IntSet, n::Integer)
 
49
function delete!(s::IntSet, n::Integer, deflt)
50
50
    if n >= s.limit
51
51
        if s.fill1s
52
52
            lim = int(n + div(n,2))
53
53
            resize(s, lim)
54
54
        else
55
 
            return s
 
55
            return deflt
56
56
        end
57
57
    end
58
 
    s.bits[n>>5 + 1] &= ~(uint32(1)<<(n&31))
59
 
    return s
60
 
end
61
 
 
62
 
function del_each(s::IntSet, ns)
 
58
    mask = uint32(1)<<(n&31)
 
59
    idx = n>>5 + 1
 
60
    b = s.bits[idx]
 
61
    if (b&mask)==0; return deflt; end
 
62
    s.bits[idx] = b&~mask
 
63
    return n
 
64
end
 
65
 
 
66
function delete!(s::IntSet, n::Integer)
 
67
    if delete!(s, n, n+1) == n+1
 
68
        throw(KeyError(n))
 
69
    end
 
70
    return n
 
71
end
 
72
 
 
73
function del_each!(s::IntSet, ns)
63
74
    for n in ns
64
 
        del(s, n)
 
75
        delete!(s, n)
65
76
    end
66
77
    return s
67
78
end
68
79
 
69
 
setdiff(a::IntSet, b::IntSet) = del_each(copy(a),b)
 
80
setdiff(a::IntSet, b::IntSet) = del_each!(copy(a),b)
 
81
symdiff(a::IntSet, b::IntSet) = a $ b
70
82
 
71
 
function del_all(s::IntSet)
 
83
function empty!(s::IntSet)
72
84
    s.bits[:] = 0
73
85
    return s
74
86
end
75
87
 
76
 
function toggle(s::IntSet, n::Integer)
 
88
function symdiff!(s::IntSet, n::Integer)
77
89
    if n >= s.limit
78
90
        lim = int(n + dim(n,2))
79
91
        resize(s, lim)
80
92
    end
81
93
    s.bits[n>>5 + 1] $= (uint32(1)<<(n&31))
82
 
   return s
 
94
    return s
83
95
end
84
96
 
85
 
function toggle_each(s::IntSet, ns)
 
97
function symdiff!(s::IntSet, ns)
86
98
   for n in ns
87
 
       toggle(s, n)
 
99
       toggle!(s, n)
88
100
   end
89
101
   return s
90
102
end
91
103
 
92
 
function copy_to(to::IntSet, from::IntSet)
93
 
    del_all(to)
 
104
function copy!(to::IntSet, from::IntSet)
 
105
    empty!(to)
94
106
    union!(to, from)
95
107
end
96
108
 
116
128
isempty(s::IntSet) =
117
129
    !s.fill1s && ccall(:bitvector_any1, Uint32, (Ptr{Uint32}, Uint64, Uint64), s.bits, 0, s.limit)==0
118
130
 
119
 
function choose(s::IntSet)
 
131
function first(s::IntSet)
120
132
    n = next(s,0)[1]
121
133
    if n >= s.limit
122
 
        error("choose: set is empty")
 
134
        error("first: set is empty")
123
135
    end
124
136
    return n
125
137
end
126
138
 
127
 
function pop(s::IntSet)
128
 
    n = choose(s)
129
 
    del(s, n)
130
 
    n
131
 
end
 
139
shift!(s::IntSet) = delete!(s, first(s))
132
140
 
133
141
length(s::IntSet) = int(ccall(:bitvector_count, Uint64, (Ptr{Uint32}, Uint64, Uint64), s.bits, 0, s.limit)) +
134
142
    (s.fill1s ? typemax(Int) - s.limit : 0)
135
143
 
136
 
function show(io, s::IntSet)
 
144
function show(io::IO, s::IntSet)
137
145
    print(io, "IntSet(")
138
146
    first = true
139
147
    for n in s
174
182
 
175
183
union(s1::IntSet, s2::IntSet) = (s1.limit >= s2.limit ? union!(copy(s1), s2) : union!(copy(s2), s1))
176
184
 
177
 
add_each(s::IntSet, s2::IntSet) = union!(s, s2)
 
185
add_each!(s::IntSet, s2::IntSet) = union!(s, s2)
178
186
 
179
187
function intersect!(s::IntSet, s2::IntSet)
180
188
    if s2.limit > s.limit
205
213
 
206
214
complement(s::IntSet) = complement!(copy(s))
207
215
 
208
 
function xor!(s::IntSet, s2::IntSet)
 
216
function symdiff!(s::IntSet, s2::IntSet)
209
217
    if s2.limit > s.limit
210
218
        resize(s, s2.limit)
211
219
    end
222
230
    s
223
231
end
224
232
 
225
 
($)(s1::IntSet, s2::IntSet) = (s1.limit >= s2.limit ? xor!(copy(s1), s2) : xor!(copy(s2), s1))
 
233
($)(s1::IntSet, s2::IntSet) =
 
234
    (s1.limit >= s2.limit ? symdiff!(copy(s1), s2) : symdiff!!(copy(s2), s1))
226
235
 
227
236
|(s::IntSet, s2::IntSet) = union(s, s2)
228
237
(&)(s::IntSet, s2::IntSet) = intersect(s, s2)