forked from rubinius/rubinius
-
Notifications
You must be signed in to change notification settings - Fork 0
/
array19.rb
689 lines (544 loc) · 16.6 KB
/
array19.rb
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
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
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
# -*- encoding: us-ascii -*-
class Array
# Try to convert obj into an array, using to_ary method.
# Returns converted array or nil if obj cannot be converted
# for any reason. This method is to check if an argument is an array.
def self.try_convert(obj)
Rubinius::Type.try_convert obj, Array, :to_ary
end
def set_index(index, ent, fin=undefined)
Rubinius.primitive :array_aset
Rubinius.check_frozen
ins_length = nil
unless fin.equal? undefined
ins_length = Rubinius::Type.coerce_to ent, Fixnum, :to_int
ent = fin # 2nd arg (ins_length) is the optional one!
end
# Normalise Ranges
if index.kind_of? Range
if ins_length
raise ArgumentError, "Second argument invalid with a range"
end
last = Rubinius::Type.coerce_to index.last, Fixnum, :to_int
last += @total if last < 0
last += 1 unless index.exclude_end?
index = Rubinius::Type.coerce_to index.first, Fixnum, :to_int
if index < 0
index += @total
raise RangeError, "Range begin #{index-@total} out of bounds" if index < 0
end
# m..n, m > n allowed
last = index if index > last
ins_length = last - index
else
index = Rubinius::Type.coerce_to index, Fixnum, :to_int
if index < 0
index += @total
raise IndexError,"Index #{index-@total} out of bounds" if index < 0
end
end
if ins_length
# ins_length < 0 not allowed
raise IndexError, "Negative length #{ins_length}" if ins_length < 0
# MRI seems to be forgiving here!
space = @total - index
if ins_length > space
ins_length = space > 0 ? space : 0
end
replace_count = 0
if ent.kind_of? Array
replacement = ent
replace_count = replacement.size
replacement = replacement.first if replace_count == 1
elsif ent.respond_to? :to_ary
replacement = ent.to_ary
replace_count = replacement.size
replacement = replacement.first if replace_count == 1
else
replacement = ent
replace_count = 1
end
new_total = (index > @total) ? index : @total
if replace_count > ins_length
new_total += replace_count - ins_length
elsif replace_count < ins_length
new_total -= ins_length - replace_count
end
if new_total > @tuple.size - @start
# Expand the size just like #<< does.
# MRI uses a straight realloc here to the exact size, but
# realloc can easily include bumper data so it's pretty fast.
# We simply compensate by using the same logic to reduce
# having to copy data.
new_tuple = Rubinius::Tuple.new(new_total + @tuple.size / 2)
new_tuple.copy_from(@tuple, @start, index < @total ? index : @total, 0)
case replace_count
when 1
new_tuple[index] = replacement
when 0
# nothing
else
new_tuple.copy_from(replacement.tuple, replacement.start,
replace_count, index)
end
if index < @total
new_tuple.copy_from(@tuple, @start + index + ins_length,
@total - index - ins_length,
index + replace_count)
end
@start = 0
@tuple = new_tuple
@total = new_total
else
# Move the elements to the right
if index < @total
right_start = @start + index + ins_length
right_len = @total - index - ins_length
@tuple.copy_from(@tuple, right_start, right_len,
@start + index + replace_count)
end
case replace_count
when 1
@tuple[@start + index] = replacement
when 0
# nothing
else
@tuple.copy_from(replacement.tuple, replacement.start,
replace_count, @start + index)
end
@total = new_total
end
return ent
else
nt = @start + index + 1
reallocate(nt) if @tuple.size < nt
@tuple.put @start + index, ent
if index >= @total - 1
@total = index + 1
end
return ent
end
end
alias_method :[]=, :set_index
private :set_index
def *(multiplier)
if multiplier.respond_to? :to_str
return join(multiplier)
else
# Aaargh stupid MRI's stupid specific stupid error stupid types stupid
multiplier = Rubinius::Type.coerce_to multiplier, Fixnum, :to_int
raise ArgumentError, "Count cannot be negative" if multiplier < 0
case @total
when 0
# Edge case
out = self.class.allocate
Rubinius::Type.infect(out, self)
return out
when 1
# Easy case
tuple = Rubinius::Tuple.pattern multiplier, at(0)
out = self.class.allocate
out.tuple = tuple
out.total = multiplier
Rubinius::Type.infect(out, self)
return out
end
new_total = multiplier * @total
new_tuple = Rubinius::Tuple.new(new_total)
out = self.class.allocate
out.tuple = new_tuple
out.total = new_total
Rubinius::Type.infect(out, self)
offset = 0
while offset < new_total
new_tuple.copy_from @tuple, @start, @total, offset
offset += @total
end
out
end
end
def concat(other)
Rubinius.primitive :array_concat
other = Rubinius::Type.coerce_to(other, Array, :to_ary)
Rubinius.check_frozen
return self if other.empty?
concat other
end
def flatten(level=-1)
level = Rubinius::Type.coerce_to(level, Integer, :to_int)
return self.dup if level == 0
out = new_reserved size
recursively_flatten(self, out, level)
out
end
def flatten!(level=-1)
Rubinius.check_frozen
level = Rubinius::Type.coerce_to(level, Integer, :to_int)
return nil if level == 0
out = new_reserved size
if recursively_flatten(self, out, level)
replace(out)
return self
end
nil
end
def insert(idx, *items)
Rubinius.check_frozen
return self if items.length == 0
# Adjust the index for correct insertion
idx = Rubinius::Type.coerce_to idx, Fixnum, :to_int
idx += (@total + 1) if idx < 0 # Negatives add AFTER the element
raise IndexError, "#{idx} out of bounds" if idx < 0
self[idx, 0] = items # Cheat
self
end
def join(sep=nil)
return "" if @total == 0
out = ""
raise ArgumentError, "recursive array join" if Thread.detect_recursion self do
sep = sep.nil? ? $, : StringValue(sep)
# We've manually unwound the first loop entry for performance
# reasons.
x = @tuple[@start]
if str = String.try_convert(x)
x = str
elsif ary = Array.try_convert(x)
x = ary.join(sep)
else
x = x.to_s
end
out.force_encoding(x.encoding)
out << x
total = @start + size()
i = @start + 1
while i < total
out << sep if sep
x = @tuple[i]
if str = String.try_convert(x)
x = str
elsif ary = Array.try_convert(x)
x = ary.join(sep)
else
x = x.to_s
end
out << x
i += 1
end
end
Rubinius::Type.infect(out, self)
end
def keep_if(&block)
Rubinius.check_frozen
return to_enum :keep_if unless block_given?
replace select(&block)
end
def pack(directives)
Rubinius.primitive :array_pack19
unless directives.kind_of? String
return pack(StringValue(directives))
end
raise ArgumentError, "invalid directives string: #{directives}"
end
# Implementation notes: We build a block that will generate all the
# combinations by building it up successively using "inject" and starting
# with one responsible to append the values.
def product(*args, &block)
args.map! { |x| Rubinius::Type.coerce_to(x, Array, :to_ary) }
# Check the result size will fit in an Array.
sum = args.inject(size) { |n, x| n * x.size }
if sum > Fixnum::MAX
raise RangeError, "product result is too large"
end
# TODO rewrite this to not use a tree of Proc objects.
# to get the results in the same order as in MRI, vary the last argument first
args.reverse!
result = []
args.push self
outer_lambda = args.inject(result.method(:push)) do |trigger, values|
lambda do |partial|
values.each do |val|
trigger.call(partial.dup << val)
end
end
end
outer_lambda.call([])
if block_given?
block_result = self
result.each { |v| block_result << yield(v) }
block_result
else
result
end
end
def push(*args)
Rubinius.check_frozen
return self if args.empty?
concat args
end
def repeated_combination(combination_size, &block)
combination_size = combination_size.to_i
unless block_given?
return Enumerator.new(self, :repeated_combination, combination_size)
end
if combination_size < 0
# yield nothing
else
Rubinius.privately do
dup.compile_repeated_combinations(combination_size, [], 0, combination_size, &block)
end
end
return self
end
def compact
out = dup
out.untaint if out.tainted?
out.trust if out.untrusted?
out.compact! || out
end
def compile_repeated_combinations(combination_size, place, index, depth, &block)
if depth > 0
(length - index).times do |i|
place[combination_size-depth] = index + i
compile_repeated_combinations(combination_size,place,index + i,depth-1, &block)
end
else
yield place.map { |element| self[element] }
end
end
private :compile_repeated_combinations
def reject(&block)
return to_enum(:reject) unless block_given?
Array.new(self).delete_if(&block)
end
def repeated_permutation(combination_size, &block)
combination_size = combination_size.to_i
unless block_given?
return Enumerator.new(self, :repeated_permutation, combination_size)
end
if combination_size < 0
# yield nothing
elsif combination_size == 0
yield []
else
Rubinius.privately do
dup.compile_repeated_permutations(combination_size, [], 0, &block)
end
end
return self
end
def compile_repeated_permutations(combination_size, place, index, &block)
length.times do |i|
place[index] = i
if index < (combination_size-1)
compile_repeated_permutations(combination_size, place, index + 1, &block)
else
yield place.map { |element| self[element] }
end
end
end
private :compile_repeated_permutations
def rotate(n=1)
n = Rubinius::Type.coerce_to(n, Integer, :to_int)
return Array.new(self) if length == 1
return [] if empty?
ary = Array.new(self)
idx = n % ary.size
ary[idx..-1].concat ary[0...idx]
end
def rotate!(cnt=1)
Rubinius.check_frozen
return self if length == 0 || length == 1
ary = rotate(cnt)
replace ary
end
def sample(*args)
random_generator = Kernel
n = nil
args.each do |a|
if options = Rubinius::Type.check_convert_type(a, Hash, :to_hash)
random_generator = options[:random] if options[:random].respond_to?(:rand)
else
n = Rubinius::Type.coerce_to(a, Fixnum, :to_int)
raise ArgumentError, "negative array size" if n < 0
end
end
return at(random_generator.rand(size)) unless n
n = size if n > size
result = Array.new(self)
n.times do |i|
r = i + random_generator.rand(size - i)
result.tuple.swap(i, r)
end
result[n..size] = []
result
end
def select!(&block)
Rubinius.check_frozen
return to_enum :select! unless block_given?
ary = select(&block)
replace ary unless size == ary.size
end
def shuffle(options = undefined)
return dup.shuffle!(options) if instance_of? Array
Array.new(self).shuffle!(options)
end
def shuffle!(options = undefined)
Rubinius.check_frozen
random_generator = Kernel
unless options.equal? undefined
options = Rubinius::Type.coerce_to options, Hash, :to_hash
random_generator = options[:random] if options[:random].respond_to?(:rand)
end
size.times do |i|
r = i + random_generator.rand(size - i)
@tuple.swap(@start + i, @start + r)
end
self
end
def slice!(start, length=undefined)
Rubinius.check_frozen
if length.equal? undefined
if start.kind_of? Range
range = start
out = self[range]
range_start = Rubinius::Type.coerce_to range.begin, Fixnum, :to_int
if range_start < 0
range_start = range_start + @total
end
range_end = Rubinius::Type.coerce_to range.end, Fixnum, :to_int
if range_end < 0
range_end = range_end + @total
elsif range_end >= @total
range_end = @total - 1
end
range_length = range_end - range_start
range_length += 1 unless range.exclude_end?
if range_start < @total && range_start >= 0 && range_end < @total && range_end >= 0 && range_length > 0
delete_range(range_start, range_length)
end
else
# make sure that negative values are not passed through to the
# []= assignment
start = Rubinius::Type.coerce_to start, Integer, :to_int
start = start + @total if start < 0
# This is to match the MRI behaviour of not extending the array
# with nil when specifying an index greater than the length
# of the array.
return out unless start >= 0 and start < @total
out = @tuple.at start + @start
# Check for shift style.
if start == 0
@tuple.put @start, nil
@total -= 1
@start += 1
else
delete_range(start, 1)
end
end
else
start = Rubinius::Type.coerce_to start, Fixnum, :to_int
length = Rubinius::Type.coerce_to length, Fixnum, :to_int
out = self[start, length]
if start < 0
start = @total + start
end
if start + length > @total
length = @total - start
end
if start < @total && start >= 0
delete_range(start, length)
end
end
out
end
# WARNING: This method does no boundary checking. It is expected that
# the caller handle that, eg #slice!
def delete_range(index, del_length)
# optimize for fast removal..
reg_start = index + del_length
reg_length = @total - reg_start
if reg_start <= @total
# If we're removing from the front, also reset @start to better
# use the Tuple
if index == 0
# Use a shift start optimization if we're only removing one
# element and the shift started isn't already huge.
if del_length == 1
@start += 1
else
@tuple.copy_from @tuple, reg_start + @start, reg_length, 0
@start = 0
end
else
@tuple.copy_from @tuple, reg_start + @start, reg_length,
@start + index
end
# TODO we leave the old references in the Tuple, we should
# probably clear them out though.
@total -= del_length
end
end
private :delete_range
def sort_by!(&block)
Rubinius.check_frozen
return to_enum :sort_by! unless block_given?
replace sort_by(&block)
end
alias_method :to_s, :inspect
def uniq(&block)
dup.uniq!(&block) or dup
end
def uniq!(&block)
Rubinius.check_frozen
if block_given?
im = Rubinius::IdentityMap.from(self, &block)
else
im = Rubinius::IdentityMap.from(self)
end
return if im.size == size
array = im.to_array
@tuple = array.tuple
@start = array.start
@total = array.total
self
end
def zip(*others)
out = Array.new(size) { [] }
others = others.map do |ary|
if ary.respond_to?(:to_ary)
ary.to_ary
else
elements = []
ary.each { |e| elements << e }
elements
end
end
size.times do |i|
slot = out.at(i)
slot << @tuple.at(@start + i)
others.each { |ary| slot << ary.at(i) }
end
if block_given?
out.each { |ary| yield ary }
return nil
end
out
end
def unshift(*values)
Rubinius.check_frozen
return self if values.empty?
if @start > values.size
# fit the new values in between 0 and @start if possible
@start -= values.size
@tuple.copy_from(values.tuple, 0, values.size, @start)
else
new_tuple = Rubinius::Tuple.new @total + values.size
new_tuple.copy_from values.tuple, 0, values.size, 0
new_tuple.copy_from @tuple, @start, @total, values.size
@start = 0
@tuple = new_tuple
end
@total += values.size
self
end
end