Class: DS::Ring

Inherits:
CyclicList show all
Defined in:
lib/ds/lists/ring.rb

Overview

Ring - represent list which head is linked with tail.

Instance Attribute Summary

Attributes inherited from List

#head, #tail

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from CyclicList

#cycle_size

Methods inherited from List

#append, #each, #each_with_index, #empty?, #first, #initialize, #insert_after, #insert_before, #joint, #last, #looped?, #merge, #orderize, #prepend, #print, #remove, #remove!, #reverse!, #shift, #to_a, #zip?

Constructor Details

This class inherits a constructor from DS::List

Class Method Details

.from_array(arr) ⇒ Object

Creates ring from array.



7
8
9
10
11
12
13
 
# File 'lib/ds/lists/ring.rb', line 7

def self.from_array(arr)
  list = Ring.new(arr.shift)
  tail = list.head
  arr.each { |e| tail = tail.append(e) }
  tail.next = list.head
  list
end

Instance Method Details

#eliminate_by(k) ⇒ Object

Removes ring elements by k until there is only one element in list.



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/ds/lists/ring.rb', line 20

def eliminate_by(k)
  elem = self.head
  prev = elem

  k = k-1

  while prev != elem.next 

    k.times  do
      prev = elem
      elem = elem.next
    end

    prev.next = elem.next
    elem = prev.next
  end

  return prev.data

end

#length ⇒ Object 



15
16
17
 
# File 'lib/ds/lists/ring.rb', line 15

def length
  cycle_size
end