1f1d973766002128fc479773e6e7bace8787036e
| blob | 1f1d973766002128fc479773e6e7bace8787036e |
1 class Array
2 ##
3 # call-seq:
4 # ary.uniq! -> ary or nil
5 # ary.uniq! { |item| ... } -> ary or nil
6 #
7 # Removes duplicate elements from +self+.
8 # Returns <code>nil</code> if no changes are made (that is, no
9 # duplicates are found).
10 #
11 # a = [ "a", "a", "b", "b", "c" ]
12 # a.uniq! #=> ["a", "b", "c"]
13 # b = [ "a", "b", "c" ]
14 # b.uniq! #=> nil
15 # c = [["student","sam"], ["student","george"], ["teacher","matz"]]
16 # c.uniq! { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
17 #
18 def uniq!(&block)
19 ary = self.dup
20 result = []
21 if block
22 hash = {}
23 while ary.size > 0
24 val = ary.shift
25 key = block.call(val)
26 hash[key] = val unless hash.has_key?(key)
27 end
28 hash.each_value do |value|
29 result << value
30 end
31 else
32 while ary.size > 0
33 result << ary.shift
34 ary.delete(result.last)
35 end
36 end
37 if result.size == self.size
38 nil
39 else
40 self.replace(result)
41 end
42 end
44 ##
45 # call-seq:
46 # ary.uniq -> new_ary
47 # ary.uniq { |item| ... } -> new_ary
48 #
49 # Returns a new array by removing duplicate values in +self+.
50 #
51 # a = [ "a", "a", "b", "b", "c" ]
52 # a.uniq #=> ["a", "b", "c"]
53 #
54 # b = [["student","sam"], ["student","george"], ["teacher","matz"]]
55 # b.uniq { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
56 #
57 def uniq(&block)
58 ary = self.dup
59 if block
60 ary.uniq!(&block)
61 else
62 ary.uniq!
63 end
64 ary
65 end
67 ##
68 # call-seq:
69 # ary - other_ary -> new_ary
70 #
71 # Array Difference---Returns a new array that is a copy of
72 # the original array, removing any items that also appear in
73 # <i>other_ary</i>. (If you need set-like behavior, see the
74 # library class Set.)
75 #
76 # [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ] #=> [ 3, 3, 5 ]
77 #
78 def -(elem)
79 raise TypeError, "can't convert #{elem.class} into Array" unless elem.class == Array
81 hash = {}
82 array = []
83 elem.each { |x| hash[x] = true }
84 self.each { |x| array << x unless hash[x] }
85 array
86 end
88 ##
89 # call-seq:
90 # ary | other_ary -> new_ary
91 #
92 # Set Union---Returns a new array by joining this array with
93 # <i>other_ary</i>, removing duplicates.
94 #
95 # [ "a", "b", "c" ] | [ "c", "d", "a" ]
96 # #=> [ "a", "b", "c", "d" ]
97 #
98 def |(elem)
99 raise TypeError, "can't convert #{elem.class} into Array" unless elem.class == Array
101 ary = self + elem
102 ary.uniq! or ary
103 end
105 ##
106 # call-seq:
107 # ary & other_ary -> new_ary
108 #
109 # Set Intersection---Returns a new array
110 # containing elements common to the two arrays, with no duplicates.
111 #
112 # [ 1, 1, 3, 5 ] & [ 1, 2, 3 ] #=> [ 1, 3 ]
113 #
114 def &(elem)
115 raise TypeError, "can't convert #{elem.class} into Array" unless elem.class == Array
117 hash = {}
118 array = []
119 elem.each{|v| hash[v] = true }
120 self.each do |v|
121 if hash[v]
122 array << v
123 hash.delete v
124 end
125 end
126 array
127 end
129 ##
130 # call-seq:
131 # ary.flatten -> new_ary
132 # ary.flatten(level) -> new_ary
133 #
134 # Returns a new array that is a one-dimensional flattening of this
135 # array (recursively). That is, for every element that is an array,
136 # extract its elements into the new array. If the optional
137 # <i>level</i> argument determines the level of recursion to flatten.
138 #
139 # s = [ 1, 2, 3 ] #=> [1, 2, 3]
140 # t = [ 4, 5, 6, [7, 8] ] #=> [4, 5, 6, [7, 8]]
141 # a = [ s, t, 9, 10 ] #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
142 # a.flatten #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
143 # a = [ 1, 2, [3, [4, 5] ] ]
144 # a.flatten(1) #=> [1, 2, 3, [4, 5]]
145 #
146 def flatten(depth=nil)
147 ar = []
148 self.each do |e|
149 if e.is_a?(Array) && (depth.nil? || depth > 0)
150 ar += e.flatten(depth.nil? ? nil : depth - 1)
151 else
152 ar << e
153 end
154 end
155 ar
156 end
158 ##
159 # call-seq:
160 # ary.flatten! -> ary or nil
161 # ary.flatten!(level) -> array or nil
162 #
163 # Flattens +self+ in place.
164 # Returns <code>nil</code> if no modifications were made (i.e.,
165 # <i>ary</i> contains no subarrays.) If the optional <i>level</i>
166 # argument determines the level of recursion to flatten.
167 #
168 # a = [ 1, 2, [3, [4, 5] ] ]
169 # a.flatten! #=> [1, 2, 3, 4, 5]
170 # a.flatten! #=> nil
171 # a #=> [1, 2, 3, 4, 5]
172 # a = [ 1, 2, [3, [4, 5] ] ]
173 # a.flatten!(1) #=> [1, 2, 3, [4, 5]]
174 #
175 def flatten!(depth=nil)
176 modified = false
177 ar = []
178 self.each do |e|
179 if e.is_a?(Array) && (depth.nil? || depth > 0)
180 ar += e.flatten(depth.nil? ? nil : depth - 1)
181 modified = true
182 else
183 ar << e
184 end
185 end
186 if modified
187 self.replace(ar)
188 else
189 nil
190 end
191 end
193 ##
194 # call-seq:
195 # ary.compact -> new_ary
196 #
197 # Returns a copy of +self+ with all +nil+ elements removed.
198 #
199 # [ "a", nil, "b", nil, "c", nil ].compact
200 # #=> [ "a", "b", "c" ]
201 #
202 def compact
203 result = self.dup
204 result.compact!
205 result
206 end
208 ##
209 # call-seq:
210 # ary.compact! -> ary or nil
211 #
212 # Removes +nil+ elements from the array.
213 # Returns +nil+ if no changes were made, otherwise returns
214 # <i>ary</i>.
215 #
216 # [ "a", nil, "b", nil, "c" ].compact! #=> [ "a", "b", "c" ]
217 # [ "a", "b", "c" ].compact! #=> nil
218 #
219 def compact!
220 result = self.select { |e| !e.nil? }
221 if result.size == self.size
222 nil
223 else
224 self.replace(result)
225 end
226 end
228 # for efficiency
229 def reverse_each(&block)
230 return to_enum :reverse_each unless block_given?
232 i = self.size - 1
233 while i>=0
234 block.call(self[i])
235 i -= 1
236 end
237 self
238 end
240 NONE=Object.new
241 ##
242 # call-seq:
243 # ary.fetch(index) -> obj
244 # ary.fetch(index, default) -> obj
245 # ary.fetch(index) { |index| block } -> obj
246 #
247 # Tries to return the element at position +index+, but throws an IndexError
248 # exception if the referenced +index+ lies outside of the array bounds. This
249 # error can be prevented by supplying a second argument, which will act as a
250 # +default+ value.
251 #
252 # Alternatively, if a block is given it will only be executed when an
253 # invalid +index+ is referenced. Negative values of +index+ count from the
254 # end of the array.
255 #
256 # a = [ 11, 22, 33, 44 ]
257 # a.fetch(1) #=> 22
258 # a.fetch(-1) #=> 44
259 # a.fetch(4, 'cat') #=> "cat"
260 # a.fetch(100) { |i| puts "#{i} is out of bounds" }
261 # #=> "100 is out of bounds"
262 #
264 def fetch(n=nil, ifnone=NONE, &block)
265 warn "block supersedes default value argument" if !n.nil? && ifnone != NONE && block
267 idx = n
268 if idx < 0
269 idx += size
270 end
271 if idx < 0 || size <= idx
272 return block.call(n) if block
273 if ifnone == NONE
274 raise IndexError, "index #{n} outside of array bounds: #{-size}...#{size}"
275 end
276 return ifnone
277 end
278 self[idx]
279 end
281 ##
282 # call-seq:
283 # ary.fill(obj) -> ary
284 # ary.fill(obj, start [, length]) -> ary
285 # ary.fill(obj, range ) -> ary
286 # ary.fill { |index| block } -> ary
287 # ary.fill(start [, length] ) { |index| block } -> ary
288 # ary.fill(range) { |index| block } -> ary
289 #
290 # The first three forms set the selected elements of +self+ (which
291 # may be the entire array) to +obj+.
292 #
293 # A +start+ of +nil+ is equivalent to zero.
294 #
295 # A +length+ of +nil+ is equivalent to the length of the array.
296 #
297 # The last three forms fill the array with the value of the given block,
298 # which is passed the absolute index of each element to be filled.
299 #
300 # Negative values of +start+ count from the end of the array, where +-1+ is
301 # the last element.
302 #
303 # a = [ "a", "b", "c", "d" ]
304 # a.fill("x") #=> ["x", "x", "x", "x"]
305 # a.fill("w", -1) #=> ["x", "x", "x", "w"]
306 # a.fill("z", 2, 2) #=> ["x", "x", "z", "z"]
307 # a.fill("y", 0..1) #=> ["y", "y", "z", "z"]
308 # a.fill { |i| i*i } #=> [0, 1, 4, 9]
309 # a.fill(-2) { |i| i*i*i } #=> [0, 1, 8, 27]
310 # a.fill(1, 2) { |i| i+1 } #=> [0, 2, 3, 27]
311 # a.fill(0..1) { |i| i+1 } #=> [1, 2, 3, 27]
312 #
314 def fill(arg0=nil, arg1=nil, arg2=nil, &block)
315 if arg0.nil? && arg1.nil? && arg2.nil? && !block
316 raise ArgumentError, "wrong number of arguments (0 for 1..3)"
317 end
319 beg = len = 0
320 ary = []
321 if block
322 if arg0.nil? && arg1.nil? && arg2.nil?
323 # ary.fill { |index| block } -> ary
324 beg = 0
325 len = self.size
326 elsif !arg0.nil? && arg0.kind_of?(Range)
327 # ary.fill(range) { |index| block } -> ary
328 beg = arg0.begin
329 beg += self.size if beg < 0
330 len = arg0.end
331 len += self.size if len < 0
332 len += 1 unless arg0.exclude_end?
333 elsif !arg0.nil?
334 # ary.fill(start [, length] ) { |index| block } -> ary
335 beg = arg0
336 beg += self.size if beg < 0
337 if arg1.nil?
338 len = self.size
339 else
340 len = arg0 + arg1
341 end
342 end
343 else
344 if !arg0.nil? && arg1.nil? && arg2.nil?
345 # ary.fill(obj) -> ary
346 beg = 0
347 len = self.size
348 elsif !arg0.nil? && !arg1.nil? && arg1.kind_of?(Range)
349 # ary.fill(obj, range ) -> ary
350 beg = arg1.begin
351 beg += self.size if beg < 0
352 len = arg1.end
353 len += self.size if len < 0
354 len += 1 unless arg1.exclude_end?
355 elsif !arg0.nil? && !arg1.nil?
356 # ary.fill(obj, start [, length]) -> ary
357 beg = arg1
358 beg += self.size if beg < 0
359 if arg2.nil?
360 len = self.size
361 else
362 len = beg + arg2
363 end
364 end
365 end
367 i = beg
368 if block
369 while i < len
370 self[i] = block.call(i)
371 i += 1
372 end
373 else
374 while i < len
375 self[i] = arg0
376 i += 1
377 end
378 end
379 self
380 end
382 ##
383 # call-seq:
384 # ary.rotate(count=1) -> new_ary
385 #
386 # Returns a new array by rotating +self+ so that the element at +count+ is
387 # the first element of the new array.
388 #
389 # If +count+ is negative then it rotates in the opposite direction, starting
390 # from the end of +self+ where +-1+ is the last element.
391 #
392 # a = [ "a", "b", "c", "d" ]
393 # a.rotate #=> ["b", "c", "d", "a"]
394 # a #=> ["a", "b", "c", "d"]
395 # a.rotate(2) #=> ["c", "d", "a", "b"]
396 # a.rotate(-3) #=> ["b", "c", "d", "a"]
398 def rotate(count=1)
399 ary = []
400 len = self.length
402 if len > 0
403 idx = (count < 0) ? (len - (~count % len) - 1) : (count % len) # rotate count
404 len.times do
405 ary << self[idx]
406 idx += 1
407 idx = 0 if idx > len-1
408 end
409 end
410 ary
411 end
413 ##
414 # call-seq:
415 # ary.rotate!(count=1) -> ary
416 #
417 # Rotates +self+ in place so that the element at +count+ comes first, and
418 # returns +self+.
419 #
420 # If +count+ is negative then it rotates in the opposite direction, starting
421 # from the end of the array where +-1+ is the last element.
422 #
423 # a = [ "a", "b", "c", "d" ]
424 # a.rotate! #=> ["b", "c", "d", "a"]
425 # a #=> ["b", "c", "d", "a"]
426 # a.rotate!(2) #=> ["d", "a", "b", "c"]
427 # a.rotate!(-3) #=> ["a", "b", "c", "d"]
429 def rotate!(count=1)
430 self.replace(self.rotate(count))
431 end
433 ##
434 # call-seq:
435 # ary.delete_if { |item| block } -> ary
436 # ary.delete_if -> Enumerator
437 #
438 # Deletes every element of +self+ for which block evaluates to +true+.
439 #
440 # The array is changed instantly every time the block is called, not after
441 # the iteration is over.
442 #
443 # See also Array#reject!
444 #
445 # If no block is given, an Enumerator is returned instead.
446 #
447 # scores = [ 97, 42, 75 ]
448 # scores.delete_if {|score| score < 80 } #=> [97]
450 def delete_if(&block)
451 return to_enum :delete_if unless block_given?
453 idx = 0
454 while idx < self.size do
455 if block.call(self[idx])
456 self.delete_at(idx)
457 else
458 idx += 1
459 end
460 end
461 self
462 end
464 ##
465 # call-seq:
466 # ary.reject! { |item| block } -> ary or nil
467 # ary.reject! -> Enumerator
468 #
469 # Equivalent to Array#delete_if, deleting elements from +self+ for which the
470 # block evaluates to +true+, but returns +nil+ if no changes were made.
471 #
472 # The array is changed instantly every time the block is called, not after
473 # the iteration is over.
474 #
475 # See also Enumerable#reject and Array#delete_if.
476 #
477 # If no block is given, an Enumerator is returned instead.
479 def reject!(&block)
480 return to_enum :reject! unless block_given?
482 len = self.size
483 idx = 0
484 while idx < self.size do
485 if block.call(self[idx])
486 self.delete_at(idx)
487 else
488 idx += 1
489 end
490 end
491 if self.size == len
492 nil
493 else
494 self
495 end
496 end
498 ##
499 # call-seq:
500 # ary.insert(index, obj...) -> ary
501 #
502 # Inserts the given values before the element with the given +index+.
503 #
504 # Negative indices count backwards from the end of the array, where +-1+ is
505 # the last element.
506 #
507 # a = %w{ a b c d }
508 # a.insert(2, 99) #=> ["a", "b", 99, "c", "d"]
509 # a.insert(-2, 1, 2, 3) #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
511 def insert(idx, *args)
512 idx += self.size + 1 if idx < 0
513 self[idx, 0] = args
514 self
515 end
517 ##
518 # call-seq:
519 # ary.bsearch {|x| block } -> elem
520 #
521 # By using binary search, finds a value from this array which meets
522 # the given condition in O(log n) where n is the size of the array.
523 #
524 # You can use this method in two use cases: a find-minimum mode and
525 # a find-any mode. In either case, the elements of the array must be
526 # monotone (or sorted) with respect to the block.
527 #
528 # In find-minimum mode (this is a good choice for typical use case),
529 # the block must return true or false, and there must be an index i
530 # (0 <= i <= ary.size) so that:
531 #
532 # - the block returns false for any element whose index is less than
533 # i, and
534 # - the block returns true for any element whose index is greater
535 # than or equal to i.
536 #
537 # This method returns the i-th element. If i is equal to ary.size,
538 # it returns nil.
539 #
540 # ary = [0, 4, 7, 10, 12]
541 # ary.bsearch {|x| x >= 4 } #=> 4
542 # ary.bsearch {|x| x >= 6 } #=> 7
543 # ary.bsearch {|x| x >= -1 } #=> 0
544 # ary.bsearch {|x| x >= 100 } #=> nil
545 #
546 # In find-any mode (this behaves like libc's bsearch(3)), the block
547 # must return a number, and there must be two indices i and j
548 # (0 <= i <= j <= ary.size) so that:
549 #
550 # - the block returns a positive number for ary[k] if 0 <= k < i,
551 # - the block returns zero for ary[k] if i <= k < j, and
552 # - the block returns a negative number for ary[k] if
553 # j <= k < ary.size.
554 #
555 # Under this condition, this method returns any element whose index
556 # is within i...j. If i is equal to j (i.e., there is no element
557 # that satisfies the block), this method returns nil.
558 #
559 # ary = [0, 4, 7, 10, 12]
560 # # try to find v such that 4 <= v < 8
561 # ary.bsearch {|x| 1 - (x / 4).truncate } #=> 4 or 7
562 # # try to find v such that 8 <= v < 10
563 # ary.bsearch {|x| 4 - (x / 2).truncate } #=> nil
564 #
565 # You must not mix the two modes at a time; the block must always
566 # return either true/false, or always return a number. It is
567 # undefined which value is actually picked up at each iteration.
569 def bsearch(&block)
570 return to_enum :bsearch unless block_given?
572 low = 0
573 high = self.size
574 satisfied = false
575 while low < high
576 mid = low + ((high - low) / 2).truncate
577 val = self[mid]
578 v = block.call(val)
579 if v.is_a?(Integer)
580 return val if v == 0
581 smaller = v < 0
582 elsif v == true
583 satisfied = true
584 smaller = true
585 elsif v == false || v.nil?
586 smaller = false
587 end
588 if smaller
589 high = mid
590 else
591 low = mid + 1
592 end
593 end
594 return nil if low == self.size
595 return nil unless satisfied
596 self[low]
597 end
599 ##
600 # call-seq:
601 # ary.delete_if { |item| block } -> ary
602 # ary.delete_if -> Enumerator
603 #
604 # Deletes every element of +self+ for which block evaluates to +true+.
605 #
606 # The array is changed instantly every time the block is called, not after
607 # the iteration is over.
608 #
609 # See also Array#reject!
610 #
611 # If no block is given, an Enumerator is returned instead.
612 #
613 # scores = [ 97, 42, 75 ]
614 # scores.delete_if {|score| score < 80 } #=> [97]
616 def delete_if(&block)
617 return to_enum :delete_if unless block_given?
619 idx = 0
620 while idx < self.size do
621 if block.call(self[idx])
622 self.delete_at(idx)
623 else
624 idx += 1
625 end
626 end
627 self
628 end
630 ##
631 # call-seq:
632 # ary.keep_if { |item| block } -> ary
633 # ary.keep_if -> Enumerator
634 #
635 # Deletes every element of +self+ for which the given block evaluates to
636 # +false+.
637 #
638 # See also Array#select!
639 #
640 # If no block is given, an Enumerator is returned instead.
641 #
642 # a = [1, 2, 3, 4, 5]
643 # a.keep_if { |val| val > 3 } #=> [4, 5]
645 def keep_if(&block)
646 return to_enum :keep_if unless block_given?
648 idx = 0
649 len = self.size
650 while idx < self.size do
651 if block.call(self[idx])
652 idx += 1
653 else
654 self.delete_at(idx)
655 end
656 end
657 self
658 end
660 ##
661 # call-seq:
662 # ary.select! {|item| block } -> ary or nil
663 # ary.select! -> Enumerator
664 #
665 # Invokes the given block passing in successive elements from +self+,
666 # deleting elements for which the block returns a +false+ value.
667 #
668 # If changes were made, it will return +self+, otherwise it returns +nil+.
669 #
670 # See also Array#keep_if
671 #
672 # If no block is given, an Enumerator is returned instead.
674 def select!(&block)
675 return to_enum :select! unless block_given?
677 result = []
678 self.each do |x|
679 result << x if block.call(x)
680 end
681 return nil if self.size == result.size
682 self.replace(result)
683 end
684 end