Class: Antlr4::Runtime::Array2DHashSet
- Inherits:
-
Object
- Object
- Antlr4::Runtime::Array2DHashSet
show all
- Defined in:
- lib/antlr4/runtime/array_2d_hash_set.rb
Defined Under Namespace
Classes: SetIterator
Constant Summary
collapse
- INITIAL_CAPACITY =
32
- INITIAL_BUCKET_CAPACITY =
4
- LOAD_FACTOR =
0.75
Instance Attribute Summary collapse
Instance Method Summary
collapse
Constructor Details
#initialize(comparator = nil, initial_capacity = INITIAL_CAPACITY, initial_bucket_capacity = INITIAL_BUCKET_CAPACITY) ⇒ Array2DHashSet
Returns a new instance of Array2DHashSet.
10
11
12
13
14
15
16
17
18
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 10
def initialize(comparator = nil, initial_capacity = INITIAL_CAPACITY, initial_bucket_capacity = INITIAL_BUCKET_CAPACITY)
comparator.nil? ? @comparator = ObjectEqualityComparator.instance : @comparator = comparator
@n_elements = 0
@initial_bucket_capacity = initial_bucket_capacity
@threshold = (initial_bucket_capacity * LOAD_FACTOR).floor @current_prime = 1 @buckets = create_buckets(initial_capacity)
end
|
Instance Attribute Details
#buckets ⇒ Object
Returns the value of attribute buckets.
8
9
10
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 8
def buckets
@buckets
end
|
Instance Method Details
#==(o) ⇒ Object
114
115
116
117
118
119
120
121
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 114
def ==(o)
return true if o.equal?(self)
return false unless o.is_a? Array2DHashSet
return false if o.size != size
contains_all(o)
end
|
#add(t) ⇒ Object
123
124
125
126
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 123
def add(t)
existing = get_or_add(t)
existing == t
end
|
#add_all(c) ⇒ Object
246
247
248
249
250
251
252
253
254
255
256
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 246
def add_all(c)
changed = false
i = 0
while i < c.length
o = c[i]
existing = get_or_add(o)
changed = true if existing != o
i += 1
end
changed
end
|
#contains(o) ⇒ Object
136
137
138
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 136
def contains(o)
contains_fast(o)
end
|
#contains_all(s) ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 213
def contains_all(s)
if s.is_a? Array2DHashSet
i = 0
while i < s.buckets.length
bucket = s.buckets[i]
if bucket.nil?
i += 1
next
end
j = 0
while j < bucket.length
o = bucket[j]
if o.nil?
j += 1
next
end
return false unless contains_fast(o)
j += 1
end
i += 1
end
else
i = 0
while i < s.length
o = s[i]
return false unless contains_fast(o)
i += 1
end
end
true
end
|
#contains_fast(obj) ⇒ Object
140
141
142
143
144
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 140
def contains_fast(obj)
return false if obj.nil?
!get(obj).nil?
end
|
#create_bucket(capacity) ⇒ Object
385
386
387
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 385
def create_bucket(capacity)
Array.new(capacity)
end
|
#create_buckets(capacity) ⇒ Object
381
382
383
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 381
def create_buckets(capacity)
Array.new(capacity)
end
|
#empty? ⇒ Boolean
132
133
134
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 132
def empty?
@n_elements == 0
end
|
#expand ⇒ Object
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 418
def expand
old = @buckets
@current_prime += 4
new_capacity = @buckets.length * 2
new_table = create_buckets(new_capacity)
new_bucket_lengths = Array.new(new_table.length, 0)
@buckets = new_table
@threshold = (new_capacity * LOAD_FACTOR).floor
old_size = size
j = 0
while j < old.length
bucket = old[j]
if bucket.nil?
j += 1
next
end
k = 0
while k < bucket.length
o = bucket[k]
break if o.nil?
b = get_bucket(o)
bucket_length = new_bucket_lengths[b]
if bucket_length == 0
new_bucket = create_bucket(@initial_bucket_capacity)
new_table[b] = new_bucket
else
new_bucket = new_table[b]
if bucket_length == new_bucket.length
tmp = Array.new(new_bucket.length * 2)
i = 0
while i < new_bucket.length
tmp[i] = new_bucket[i]
i += 1
end
new_bucket = tmp
new_table[b] = new_bucket
end
end
new_bucket[bucket_length] = o
new_bucket_lengths[b] += 1
k += 1
end
j += 1
end
raise StandardError, '@nElements != oldSize' if @n_elements != old_size
end
|
#get(o) ⇒ Object
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 60
def get(o)
return o if o.nil?
b = get_bucket(o)
bucket = @buckets[b]
if bucket.nil?
return nil end
i = 0
while i < bucket.length
e = bucket[i]
if e.nil?
i += 1
next
end
return e if @comparator.compare(e, o).zero?
i += 1
end
nil
end
|
#get_bucket(o) ⇒ Object
82
83
84
85
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 82
def get_bucket(o)
h = @comparator.hash(o)
h & (@buckets.length - 1) end
|
#get_or_add(o) ⇒ Object
20
21
22
23
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 20
def get_or_add(o)
expand if @n_elements > @threshold
get_or_add_impl(o)
end
|
#get_or_add_impl(o) ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 25
def get_or_add_impl(o)
b = get_bucket(o)
bucket = @buckets[b]
if bucket.nil?
bucket = create_bucket(@initial_bucket_capacity)
bucket[0] = o
@buckets[b] = bucket
@n_elements += 1
return o
end
i = 0
while i < bucket.length
existing = bucket[i]
if existing.nil? bucket[i] = o
@n_elements += 1
return o
end
if @comparator.compare(existing, o).zero?
return existing end
i += 1
end
@buckets[b] = bucket
bucket << o @n_elements += 1
o
end
|
#hash ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 87
def hash
objs = []
i = 0
while i < @buckets.length
bucket = @buckets[i]
if bucket.nil?
i += 1
next
end
j = 0
while j < bucket.length
o = bucket[j]
if o.nil?
j += 1
next
end
objs << o
j += 1
end
i += 1
end
@_hash = RumourHash.calculate(objs)
end
|
#iterator ⇒ Object
146
147
148
149
150
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 146
def iterator
a = to_a
a.sort! {|x, y| @comparator.compare(x, y)} unless @comparator.nil?
SetIterator.new(a, self)
end
|
#remove(o) ⇒ Object
180
181
182
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 180
def remove(o)
remove_fast(o)
end
|
#remove_all(c) ⇒ Object
301
302
303
304
305
306
307
308
309
310
311
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 301
def remove_all(c)
changed = false
i = 0
while i < c.length
o = c[i]
changed |= remove_fast(o)
i += 1
end
changed
end
|
#remove_fast(obj) ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 184
def remove_fast(obj)
return false if obj.nil?
b = get_bucket(obj)
bucket = @buckets[b]
if bucket.nil?
return false
end
i = 0
while i < bucket.length
e = bucket[i]
if e.nil?
i += 1
next
end
if @comparator.compare(e, obj).zero? bucket[i] = nil
@n_elements -= 1
return true
end
i += 1
end
false
end
|
#retain_all(c) ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 258
def retain_all(c)
newsize = 0
k = 0
while k < @buckets.length
bucket = @buckets[k]
if bucket.nil?
k += 1
next
end
i = 0
j = 0
while i < bucket.length
if bucket[i].nil?
i += 1
next
end
if c.include?(bucket[i])
bucket[j] = bucket[i] if i != j
j += 1
newsize += 1
end
i += 1
end
newsize += j
while j < i
bucket[j] = nil
j += 1
end
k += 1
end
changed = newsize != @n_elements
@n_elements = newsize
changed
end
|
#size ⇒ Object
128
129
130
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 128
def size
@n_elements
end
|
#to_a ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 152
def to_a
a = []
i = 0
j = 0
while j < @buckets.length
bucket = @buckets[j]
if bucket.nil?
j += 1
next
end
k = 0
while k < bucket.length
o = bucket[k]
if o.nil?
k += 1
next
end
a << o
i += 1
k += 1
end
j += 1
end
a
end
|
#to_s ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 319
def to_s
return '{}' if size == 0
buf = ''
buf << '{'
first = true
items = to_a
items.sort! {|a, b| @comparator.compare(a, b)} unless @comparator.nil?
i = 0
while i < items.length
item = items[i]
if item.nil?
i += 1
next
end
if first
first = false
else
buf << ', '
end
buf << item.to_s
i += 1
end
buf << '}'
buf
end
|
#to_table_string ⇒ Object
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
|
# File 'lib/antlr4/runtime/array_2d_hash_set.rb', line 349
def to_table_string
buf = ''
i = 0
while i < @buckets.length
bucket = @buckets[i]
if bucket.nil?
buf << "null\n"
else
buf << '['
first = true
j = 0
while j < bucket.length
o = bucket[j]
if first
first = false
else
buf << ' '
end
buf << if o.nil?
'_'
else
o.to_s
end
j += 1
end
buf << "]\n"
end
i += 1
end
buf
end
|