Class: DS::List

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

Overview

Implements simple list data structure.

Direct Known Subclasses

CyclicList

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(x = nil) ⇒ List

Creates new list.



11
12
13
14
 
# File 'lib/ds/lists/list.rb', line 11

def initialize(x=nil)
  @head = ListElement.new(x)
  @tail = @head
end

Instance Attribute Details

#head ⇒ Object

Returns the value of attribute head.



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

def head
  @head
end

#tail ⇒ Object

Returns the value of attribute tail.



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

def tail
  @tail
end

Class Method Details

.from_array(arr) ⇒ Object

Creates list from array.



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

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

Instance Method Details

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

Appends new element to list.



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

def append(x)
  last_elem = self.tail
  if !empty?
    @tail = last_elem.append(x)
  else
    @head = ListElement.new(x)
    @tail = @head
  end
end

#each ⇒ Object

Default list iterator.



284
285
286
287
288
289
290
 
# File 'lib/ds/lists/list.rb', line 284

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

#each_with_index ⇒ Object 



292
293
294
295
296
297
298
299
300
 
# File 'lib/ds/lists/list.rb', line 292

def each_with_index
  elem = @head
  i = 0
  while elem
    yield elem,i
    elem = elem.next
    i = i + 1
  end
end

#empty? ⇒ Boolean

Checks if list is empty.

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/ds/lists/list.rb', line 119

def empty?
  head.data.nil?
end

#first ⇒ Object 



128
129
130
 
# File 'lib/ds/lists/list.rb', line 128

def first
  head.data
end

#insert_after(x, rel) ⇒ Object

Inserts element x after another element.



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/ds/lists/list.rb', line 72

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

  el = head
  while el and el != rel
    el = el.next
  end

  raise "Element not found" unless el

  x.next = el.next
  el.next = x

  if x.tail?
    self.tail = x
  end
end

#insert_before(x, rel) ⇒ Object

Inserts element x before another element.



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
 
# File 'lib/ds/lists/list.rb', line 91

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

  #inserting at the beginnig of the list 
  if rel == head
    x.next = head
    self.head = x

  #inserting in the tail of the list
  else
    el = head
    prev = head
    while el and el != rel
      prev = el
      el = el.next
    end

    if el.nil?
      raise "List element not found"
    else
      prev.next = x
      x.next = el
    end
  end
end

#joint ⇒ Object

Returns joint element if exists, otherwise returns nil.



143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/ds/lists/list.rb', line 143

def joint
  elem = head
  elem2 = elem.next

  while elem and elem2

    #traversing by 1
    elem = elem.next

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

    if elem2.equal? elem
      return elem
    end
  end

  nil
end

#last ⇒ Object

Returns last element of the list.



124
125
126
 
# File 'lib/ds/lists/list.rb', line 124

def last
  tail.data
end

#length ⇒ Object

Returns length of the list.



133
134
135
 
# File 'lib/ds/lists/list.rb', line 133

def length
  count
end

#looped? ⇒ Boolean

Returns true if list has cycle.

Returns:

  • (Boolean) 


165
166
167
 
# File 'lib/ds/lists/list.rb', line 165

def looped?
  !!joint
end

#merge(other) ⇒ Object

Merge list with other list.



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
 
# File 'lib/ds/lists/list.rb', line 223

def merge(other)

  a = self.head
  b = other.head

  if a.data < b.data
    result = List.new(a.data)
    a = a.next
  else
    result = List.new(b.data)
    b = b.next
  end

  while a and b
    if a.data < b.data
      result.append(a.data)
      a = a.next
    else
      result.append(b.data)
      b = b.next
    end
  end
  if !b
    result.tail.next = a
    result.tail = self.tail
  elsif !a
    result.tail.next = b
    result.tail = other.tail
  end
  result
end

#orderize ⇒ Object

Orderize list by evaluating block. Block should evaluate to one of these values: 1,0,-1 (same as Comparable).



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
 
# File 'lib/ds/lists/list.rb', line 172

def orderize

  zero = List.new
  plus = List.new
  minus = List.new

  el = self.head

  while el
    case yield el.data
    when 0
      zero_tail = zero.append(el.data)
    when 1
      plus_tail = plus.append(el.data)
    when -1
      minus_tail = minus.append(el.data)
    end

    el = el.next
  end

  minus_tail.next = zero.head
  zero_tail.next = plus.head
  return minus
end

#prepend(x) ⇒ Object

Prepends new element to list.



39
40
41
42
43
 
# File 'lib/ds/lists/list.rb', line 39

def prepend(x)
  el = ListElement.new(x)
  el.next = @head
  @head = el
end

#print ⇒ Object

Prints list.



274
275
276
 
# File 'lib/ds/lists/list.rb', line 274

def print
  each { |e| p }
end

#remove(x) ⇒ Object

Removes element x from list.



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/ds/lists/list.rb', line 46

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

    el = head
    while el and el != x
      prev = el 
      el = el.next
    end

    raise "Element not found" unless el

    prev.next = el.next
    el.next = nil
  end
  x
end

#remove!(other) ⇒ Object

Removes elements that exists on the other list.



200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/ds/lists/list.rb', line 200

def remove!(other)
  a = head
  b = other.head

  while a and b

    while a.data < b.data
      prev = a
      a = a.next
    end

    while b.data < a.data
      b = b.next
    end

    a = a.next
    prev.next = a
    b = b.next
  end
  self
end

#reverse! ⇒ Object

Reverses list.



256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
 
# File 'lib/ds/lists/list.rb', line 256

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

  @head = prev
  self

end

#shift ⇒ Object

Removes list head.



67
68
69
 
# File 'lib/ds/lists/list.rb', line 67

def shift
  remove(head).data
end

#to_a ⇒ Object

Converts list to array.



279
280
281
 
# File 'lib/ds/lists/list.rb', line 279

def to_a
  map { |e| e}
end

#zip?(other) ⇒ Boolean

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

Returns:

  • (Boolean) 


138
139
140
 
# File 'lib/ds/lists/list.rb', line 138

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