Class: DS::List

Inherits:
Object
  • Object
show all
Includes:
Comparable, Enumerable
Defined in:
lib/ds/lists/list.rb

Overview

Implements simple list data structure.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*arr) ⇒ List

Creates new list.



12
13
14
15
16
17
 
# File 'lib/ds/lists/list.rb', line 12

def initialize(*arr)
  @size = 0
  @head = nil
  @tail = nil
  from_array(arr) if arr.any?
end

Instance Attribute Details

#head ⇒ Object

Returns the value of attribute head.



9
10
11
 
# File 'lib/ds/lists/list.rb', line 9

def head
  @head
end

#tail ⇒ Object

Returns the value of attribute tail.



9
10
11
 
# File 'lib/ds/lists/list.rb', line 9

def tail
  @tail
end

Instance Method Details

#<=>(other) ⇒ Object

Checks if two lists are equal



137
138
139
140
141
142
143
144
145
 
# File 'lib/ds/lists/list.rb', line 137

def <=>(other)
  a = head
  b = other.head
  while a && b && a.data == b.data
    a = a.next
    b = b.next
  end
  compare_list_elements(a, b)
end

#[](i, count = nil) ⇒ Object

Returns list element on given index.



94
95
96
97
98
99
100
101
102
103
 
# File 'lib/ds/lists/list.rb', line 94

def [](i, count = nil)
  return [] if count && count < 0
  i = (i...i + count) if count && count > 0
  case i
  when Integer
    at(i)
  when Range
    elements_in_range(i)
  end
end

#[]=(i, count = 1, val) ⇒ Object

Sets list element on given index.

Raises:



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/ds/lists/list.rb', line 106

def []=(i, count = 1, val)
  if i.is_a? Range
    index = i.first
    count = i.size
  else
    index = i
  end

  raise ListError, 'Ivalid count parameter' unless valid_count?(count, index)

  el = at(index)
  raise ListError, 'Element not found' unless el
  if val.is_a? Array
    replace(el, List.new(*val), count)
  else
    el.data = val
  end
end

#append(x) ⇒ Object Also known as: <<, push

Appends new element to list. Returns list tail



34
35
36
37
38
39
40
41
42
 
# File 'lib/ds/lists/list.rb', line 34

def append(x)
  if !empty?
    @tail = tail.append(x)
    increment_size
  else
    create_first(x)
  end
  @tail
end

#at(index) ⇒ Object

Returns list element on given index.



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/ds/lists/list.rb', line 77

def at(index)
  found = nil
  find_index = lambda do |element, i|
    if i == index
      found = element
      break
    end
  end
  if index >= 0
    each_with_index(&find_index)
  else
    reverse_each(&find_index)
  end
  found
end

#clear ⇒ Object

Clears list by reseting head and tail to nil



27
28
29
30
31
 
# File 'lib/ds/lists/list.rb', line 27

def clear
  @size = 0
  @head = nil
  @tail = nil
end

#clone ⇒ Object

Clones list



20
21
22
23
24
 
# File 'lib/ds/lists/list.rb', line 20

def clone
  list = self.class.new
  each { |e| list.append(e.data) }
  list
end

#concat(other) ⇒ Object

Appends one list to other



148
149
150
151
152
153
154
 
# File 'lib/ds/lists/list.rb', line 148

def concat(other)
  other.head.prev = tail
  tail.next = other.head
  self.tail = other.tail
  @size += other.size
  self
end

#cycle_size ⇒ Object

Returns cycle size or nil if list has no cycles



267
268
269
270
271
272
273
274
275
276
277
278
279
280
 
# File 'lib/ds/lists/list.rb', line 267

def cycle_size
  return unless looped?
  counter = 0
  start = joint
  if start
    counter = 1
    elem = start.next
    while elem != start
      elem = elem.next
      counter += 1
    end
  end
  counter
end

#each ⇒ Object

Default list iterator.



306
307
308
309
310
311
312
 
# File 'lib/ds/lists/list.rb', line 306

def each
  elem = head
  while elem
    yield elem
    elem = elem.next
  end
end

#empty? ⇒ Boolean

Checks if list is empty.

Returns:

  • (Boolean) 


216
217
218
 
# File 'lib/ds/lists/list.rb', line 216

def empty?
  @size.zero?
end

#first ⇒ Object

Returns first element of the list.



226
227
228
 
# File 'lib/ds/lists/list.rb', line 226

def first
  head.data
end

#get(x) ⇒ Object

Return ListElement if it is on list otherwise returns nil



64
65
66
67
68
 
# File 'lib/ds/lists/list.rb', line 64

def get(x)
  el = head
  el = el.next while el && el != x
  el
end

#get!(x) ⇒ Object

Return ListElement if it is on list or raises error

Raises:



71
72
73
74
 
# File 'lib/ds/lists/list.rb', line 71

def get!(x)
  found = get(x)
  raise ListError, 'Element not found' unless found
end

#insert_after(x, rel) ⇒ Object

Inserts element x after another element.



157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/ds/lists/list.rb', line 157

def insert_after(x, rel)
  x = ListElement.new(x)

  el = rel
  nxt = el.next
  x.next = nxt
  nxt.prev = x if nxt
  el.next = x
  x.prev = el
  self.tail = x if x.nil?

  increment_size

  self
end

#insert_before(x, rel) ⇒ Object

Inserts element x before another element.



174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/ds/lists/list.rb', line 174

def insert_before(x, rel)
  if rel == head
    unshift(x)
  else
    x = ListElement.new(x)

    prev = rel.prev
    prev.next = x
    x.prev = prev
    x.next = rel
    rel.prev = x
  end
  increment_size
  self
end

#joint ⇒ Object

Returns joint element if exists, otherwise returns nil.



243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
# File 'lib/ds/lists/list.rb', line 243

def joint
  elem = head
  elem2 = elem.next

  while elem && elem2

    # traversing by 1
    elem = elem.next

    # traversing by 2
    elem2 = elem2.next
    elem2 = elem2.next if elem2

    return elem if elem2.equal? elem
  end
  nil
end

#last ⇒ Object

Returns last element of the list.



221
222
223
 
# File 'lib/ds/lists/list.rb', line 221

def last
  tail.data
end

#length ⇒ Object Also known as: size

Returns length of the list.



231
232
233
 
# File 'lib/ds/lists/list.rb', line 231

def length
  @size
end

#looped? ⇒ Boolean

Returns true if list has cycle.

Returns:

  • (Boolean) 


262
263
264
 
# File 'lib/ds/lists/list.rb', line 262

def looped?
  !joint.nil?
end

#pop ⇒ Object

Removes last element from list.



211
212
213
 
# File 'lib/ds/lists/list.rb', line 211

def pop
  remove(tail).data
end

#remove(x) ⇒ Object

Removes element x from list.



191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 
# File 'lib/ds/lists/list.rb', line 191

def remove(x)
  if x == head
    self.head = head.next
    x.next = nil
    head.prev = nil if head
  else
    nxt = x.next
    prev = x.prev
    prev.next = nxt
    nxt.prev = prev if nxt
    x.next = nil
    x.prev = nil

    self.tail = prev if nxt.nil?
  end
  decrement_size
  x
end

#replace(el, list, count = 1) ⇒ Object

Replaces list elements with other list



126
127
128
129
130
131
132
133
134
 
# File 'lib/ds/lists/list.rb', line 126

def replace(el, list, count = 1)
  if el.head?
    replace_head(el, list, count)
  elsif el.tail?
    replace_tail(el, list, count)
  else
    replace_inside(el, list, count)
  end
end

#reverse! ⇒ Object

Reverses list.



283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
 
# File 'lib/ds/lists/list.rb', line 283

def reverse!
  @tail = head
  prev = head
  elem = prev.next
  prev.next = nil
  while elem
    nxt = elem.next
    elem.next = prev
    prev.prev = elem
    prev = elem
    elem = nxt
  end

  @head = prev
  self
end

#reverse_each ⇒ Object

Reverse list iterator.



315
316
317
318
319
320
321
322
323
 
# File 'lib/ds/lists/list.rb', line 315

def reverse_each
  elem = tail
  i = 0
  while elem
    i -= 1
    yield elem, i
    elem = elem.prev
  end
end

#shift ⇒ Object

Removes list head.

Raises:



58
59
60
61
 
# File 'lib/ds/lists/list.rb', line 58

def shift
  raise ListError, 'List already empty' if empty?
  remove(head).data
end

#to_a ⇒ Object

Converts list to array.



301
302
303
 
# File 'lib/ds/lists/list.rb', line 301

def to_a
  map(&:data)
end

#to_s ⇒ Object 



325
326
327
 
# File 'lib/ds/lists/list.rb', line 325

def to_s
  to_a.join('=')
end

#unshift(x) ⇒ Object

Prepends new element to list. Returns list head



48
49
50
51
52
53
54
55
 
# File 'lib/ds/lists/list.rb', line 48

def unshift(x)
  el = ListElement.new(x)
  el.next = @head
  @head.prev = el if @head

  increment_size
  @head = el
end

#zip?(other) ⇒ Boolean

Checks if list is linked at the end with other list.

Returns:

  • (Boolean) 


238
239
240
 
# File 'lib/ds/lists/list.rb', line 238

def zip?(other)
  tail.equal? other.tail
end