Class: Algorithmix::DataStructure::Generic::LinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmix/data_structure/generic/linked_list.rb

Defined Under Namespace

Classes: Iterator, Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(obj = nil, copy: false) ⇒ LinkedList

Creates a new linked list object.

Parameters:

  • obj (#to_a) (defaults to: nil) —

    any object which responds to to_a method

Raises:

  • ArgumentError if given object doesn’t respond to to_a method



16
17
18
19
20
21
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 16

def initialize(obj = nil, copy: false)
  @length = @size = 0
  @front = nil

  obj.nil? ? nil : from_obj(obj, copy)
end

Instance Attribute Details

#front ⇒ Object (readonly)

Returns the value of attribute front.



8
9
10
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 8

def front
  @front
end

#length ⇒ Object (readonly)

Returns the value of attribute length.



8
9
10
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 8

def length
  @length
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



8
9
10
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 8

def size
  @size
end

Instance Method Details

#!=(linked_list) ⇒ true, false

Compares contents of two linked lists.

Parameters:

Returns:

  • (true, false) —

    true if both lists are different, false otherwise

Raises:

  • ArgumentError if given object is not a linked_list



133
134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 133

def !=(linked_list)
  raise ArgumentError, "Undefined method LinkedList#!= for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  return true if @length != linked_list.length

  it = @front
  other_it = linked_list.front
  until it.nil?
    return true if it.value != other_it.value
    it = it.next_node
  end

  false
end

#&(linked_list) ⇒ LinkedList

Finds the intersection of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



247
248
249
250
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 247

def &(linked_list)
  raise ArgumentError, "Undefined method LinkedList#& for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  LinkedList.new(to_a.reverse & linked_list.to_a.reverse)
end

#+(linked_list) ⇒ LinkedList

Concatenates contents of self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



183
184
185
186
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 183

def +(linked_list)
  raise ArgumentError, "Undefined method LinkedList#+ for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  LinkedList.new(to_a.reverse + linked_list.to_a.reverse)
end

#-(linked_list) ⇒ LinkedList

Finds the difference of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



221
222
223
224
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 221

def -(linked_list)
  raise ArgumentError, "Undefined method LinkedList#- for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  LinkedList.new(to_a.reverse - linked_list.to_a.reverse)
end

#<=>(linked_list) ⇒ Object

Compares contents of two linked lists.

Parameters:

Returns:

  • -1 if content of the self object is greater than content of the second. 0 if contents are equal. 1 if content of the self object is less than content of the first.

Raises:

  • ArgumentError if given object is not a linked_list



161
162
163
164
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 161

def <=>(linked_list)
  raise ArgumentError, "Undefined method LinkedList#<=> for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  to_a <=> linked_list.to_a
end

#==(linked_list) ⇒ true, false

Compares contents of two linked lists.

Parameters:

Returns:

  • (true, false) —

    true if both lists are equal, false otherwise

Raises:

  • ArgumentError if given object is not a linked_list



108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 108

def ==(linked_list)
  raise ArgumentError, "Undefined method LinkedList#== for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  return false if @length != linked_list.length

  it = @front
  other_it = linked_list.front
  until it.nil?
    return false if it.value != other_it.value
    it = it.next_node
  end

  true
end

#>>(value) ⇒ Object

Inserts a new element at the beginning of the list.

Parameters:

  • value

Returns:

  • newly inserted element



48
49
50
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 48

def >>(value)
  push_front(value)
end

#^(linked_list) ⇒ LinkedList

Finds the symmetric_difference of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



299
300
301
302
303
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 299

def ^(linked_list)
  raise ArgumentError, "Undefined method LinkedList#^ for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self_a, linked_list_a = to_a.reverse, linked_list.to_a.reverse
  LinkedList.new((self_a | linked_list_a) - (self_a & linked_list_a))
end

#apply(&block) ⇒ LinkedList

Applies a function to each element of the list.

Parameters:

  • &block

Returns:



375
376
377
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 375

def apply(&block)
  map(&block)
end

#apply!(&block) ⇒ LinkedList

Applies a function to each element of the list.

Parameters:

  • &block

Returns:



380
381
382
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 380

def apply!(&block)
  map!(&block)
end

#assign(obj, copy: false) ⇒ LinkedList

Assigns a content of an object to content of the linked list, removing all previously inserted elements.

Parameters:

Returns:

Raises:

  • ArgumentError if given object doesn’t respond to to_a method



29
30
31
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 29

def assign(obj, copy: false)
  from_obj(obj, copy)
end

#clear ⇒ Object

Clears content of the list.



172
173
174
175
176
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 172

def clear
  @front = nil
  @length = @size = 0
  self
end

#concat(linked_list) ⇒ LinkedList

Concatenates contents of self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



189
190
191
192
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 189

def concat(linked_list)
  raise ArgumentError, "Undefined method LinkedList#concat for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self + linked_list
end

#concat!(linked_list) ⇒ LinkedList

Concatenates contents of self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



205
206
207
208
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 205

def concat!(linked_list)
  raise ArgumentError, "Undefined method LinkedList#concat! for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  from_obj(to_a.reverse + linked_list.to_a.reverse)
end

#diff?(linked_list) ⇒ true, false

Compares contents of two linked lists.

Parameters:

Returns:

  • (true, false) —

    true if both lists are different, false otherwise

Raises:

  • ArgumentError if given object is not a linked_list



148
149
150
151
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 148

def diff?(linked_list)
  raise ArgumentError, "Undefined method LinkedList#diff? for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self != linked_list
end

#difference(linked_list) ⇒ LinkedList

Finds the difference of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



227
228
229
230
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 227

def difference(linked_list)
  raise ArgumentError, "Undefined method LinkedList#difference for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self - linked_list
end

#difference!(linked_list) ⇒ LinkedList

Finds the difference of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



237
238
239
240
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 237

def difference!(linked_list)
  raise ArgumentError, "Undefined method LinkedList#difference! for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  from_obj(to_a.reverse - linked_list.to_a.reverse)
end

#empty? ⇒ Boolean

Returns true if there are no elements in the list.

Returns:

  • (Boolean) 


99
100
101
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 99

def empty?
  @front.nil?
end

#eql?(linked_list) ⇒ true, false

Compares contents of two linked lists.

Parameters:

Returns:

  • (true, false) —

    true if both lists are equal, false otherwise

Raises:

  • ArgumentError if given object is not a linked_list



123
124
125
126
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 123

def eql?(linked_list)
  raise ArgumentError, "Undefined method LinkedList#eql? for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self == linked_list
end

#erase_after(it) ⇒ Object

Removes the element after the position specified by the iterator.

Parameters:

Returns:

  • removed element

Raises:

  • ArgumentIterator, if given iterator doesn’t point to any element of the list.



87
88
89
90
91
92
93
94
95
96
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 87

def erase_after(it)
  raise ArgumentError, "Undefined method LinkedList#erase_after for #{it}:#{it.class}" unless it.is_a?(Iterator)
  raise ArgumentError, "Invalid iterator." unless !@front.nil? && it.current.id == @front.id
  raise OutOfBound, "There is no more elements" if it.current.next_node.nil?

  node = it.current.next_node
  it.current.send(:next_node=, it.current.next_node.next_node)
  @size = @length -= 1
  node.value
end

#filter(&block) ⇒ LinkedList

Filters elements of the list by given condition.

Parameters:

  • &block

Returns:



339
340
341
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 339

def filter(&block)
  select(&block)
end

#filter!(&block) ⇒ LinkedList

Filters elements of the list by given condition.

Parameters:

  • &block

Returns:



344
345
346
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 344

def filter!(&block)
  select!(&block)
end

#find_all(&block) ⇒ LinkedList

Filters elements of the list by given condition.

Parameters:

  • &block

Returns:



349
350
351
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 349

def find_all(&block)
  select(&block)
end

#find_all!(&block) ⇒ LinkedList

Filters elements of the list by given condition.

Parameters:

  • &block

Returns:



354
355
356
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 354

def find_all!(&block)
  select!(&block)
end

#insert_after(it, value) ⇒ Object

Inserts an element after the position specified by iterator.

Parameters:

  • it, —

    value [LinkedList::Iterator, #any]

Returns:

  • self object

Raises:

  • ArgumentError, if given iterator doesn’t point to any element of the list.



70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 70

def insert_after(it, value)
  raise ArgumentError, "Undefined method LinkedList#insert_after for #{it}:#{it.class}" unless it.is_a?(Iterator)
  raise ArgumentError, "Invalid iterator." unless !@front.nil? && it.current.id == @front.id

  tail = it.current.next_node
  it.current.send(:next_node=, Node.new(value, it.current, it.current.id))
  it.current.next_node.send(:next_node=, tail)
  @length = @size += 1
  
  it.next_node
end

#intersect(linked_list) ⇒ LinkedList

Finds the intersection of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



253
254
255
256
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 253

def intersect(linked_list)
  raise ArgumentError, "Undefined method LinkedList#intersect for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self & linked_list
end

#intersect!(linked_list) ⇒ LinkedList

Finds the intersection of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



263
264
265
266
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 263

def intersect!(linked_list)
  raise ArgumentError, "Undefined method LinkedList#intersect! for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  from_obj(to_a.reverse & linked_list.to_a.reverse)
end

#map(&block) ⇒ LinkedList

Applies a function to each element of the list.

Parameters:

  • &block

Returns:



362
363
364
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 362

def map(&block)
  LinkedList.new(to_a.reverse.map { |e| block.call(e) })
end

#map!(&block) ⇒ LinkedList

Applies a function to each element of the list.

Parameters:

  • &block

Returns:



370
371
372
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 370

def map!(&block)
  from_obj(to_a.reverse.map { |e| block.call(e) })
end

#merge(linked_list) ⇒ LinkedList

Concatenates contents of self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



195
196
197
198
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 195

def merge(linked_list)
  raise ArgumentError, "Undefined method LinkedList#merge for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self + linked_list
end

#merge!(linked_list) ⇒ LinkedList

Concatenates contents of self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



211
212
213
214
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 211

def merge!(linked_list)
  raise ArgumentError, "Undefined method LinkedList#merge! for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  from_obj(to_a.reverse + linked_list.to_a.reverse)
end

#pop_front ⇒ Object

Removes element at the beginning of the list.

Returns:

  • removed value

Raises:

  • Algorithmix::EmptyContainerError if the list is empty.



56
57
58
59
60
61
62
63
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 56

def pop_front
  raise EmptyContainerError, "The Linked list is empty." if @front.nil?

  value = @front.value
  @front = @front.next_node
  @length = @size -= 1
  value
end

#push_front(value) ⇒ Object

Inserts a new element at the beginning of the list.

Parameters:

  • value

Returns:

  • newly inserted element



37
38
39
40
41
42
43
44
45
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 37

def push_front(value)
  tail = @front
  rand_id = Random.new.rand((2**(0.size * 8 -2) -1) / 2)
  id = @front.nil? ? rand_id : @front.id
  @front = Node.new(value, tail, id)
  @length = @size += 1
  
  @front
end

#select(&block) ⇒ LinkedList

Filters elements of the list by given condition.

Parameters:

  • &block

Returns:



326
327
328
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 326

def select(&block)
  LinkedList.new(to_a.reverse.select { |e| block.call(e) })
end

#select!(&block) ⇒ LinkedList

Filters elements of the list by given condition.

Parameters:

  • &block

Returns:



334
335
336
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 334

def select!(&block)
  from_obj(to_a.reverse.select { |e| block.call(e) })
end

#symmetric_difference(linked_list) ⇒ LinkedList

Finds the symmetric_difference of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



306
307
308
309
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 306

def symmetric_difference(linked_list)
  raise ArgumentError, "Undefined method LinkedList#symmetric_difference for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self ^ linked_list
end

#symmetric_difference!(linked_list) ⇒ LinkedList

Finds the symmetric_difference of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



316
317
318
319
320
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 316

def symmetric_difference!(linked_list)
  raise ArgumentError, "Undefined method LinkedList#symmetric_difference! for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self_a, linked_list_a = to_a.reverse, linked_list.to_a.reverse
  from_obj((self_a | linked_list_a) - (self_a & linked_list_a))
end

#to_a ⇒ Object

Converts content of the list to an array.



167
168
169
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 167

def to_a
  convert
end

#union(linked_list) ⇒ LinkedList

Finds the union of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



279
280
281
282
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 279

def union(linked_list)
  raise ArgumentError, "Undefined method LinkedList#union for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  self | linked_list
end

#union!(linked_list) ⇒ LinkedList

Finds the union of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



289
290
291
292
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 289

def union!(linked_list)
  raise ArgumentError, "Undefined method LinkedList#union! for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  from_obj(to_a.reverse | linked_list.to_a.reverse)
end

#|(linked_list) ⇒ LinkedList

Finds the union of contents of the self object and linked_list given as argument.

Parameters:

  • linked_list (LinedList)

Returns:

Raises:

  • ArgumentError, if given object is not a linked list



273
274
275
276
 
# File 'lib/algorithmix/data_structure/generic/linked_list.rb', line 273

def |(linked_list)
  raise ArgumentError, "Undefined method LinkedList#| for #{linked_list}:#{linked_list.class}" unless linked_list.is_a?(LinkedList)
  LinkedList.new(to_a.reverse | linked_list.to_a.reverse)
end