class Algorithmix::DataStructure::Generic::LinkedList

Attributes

front[R]
length[R]
size[R]

Public Class Methods

new(obj = nil, copy: false) click to toggle source

Creates a new linked list object.

@param obj [#to_a] any object which responds to to_a method @kwarg copy [true, false] If specified with true it will copy the given object. By default is set to false. @raise ArgumentError if given object doesn't respond to to_a method @return [LinkedList] a newly created linked list

# 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

Public Instance Methods

!=(linked_list) click to toggle source

Compares contents of two linked lists.

@param linked_list [LinkedList] @raise ArgumentError if given object is not a linked_list @return [true, false] true if both lists are different, false otherwise

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] a new linked list

# 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) click to toggle source

Concatenates contents of self object and linked_list given as argument.

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] a new linked list

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] a new linked list

# 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) click to toggle source

Compares contents of two linked lists.

@param linked_list [LinkedList] @raise ArgumentError if given object is not a linked_list @return

-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.
# 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) click to toggle source

Compares contents of two linked lists.

@param linked_list [LinkedList] @raise ArgumentError if given object is not a linked_list @return [true, false] true if both lists are equal, false otherwise

# 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) click to toggle source

(see push_front)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 48
def >>(value)
  push_front(value)
end
^(linked_list) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] a new linked list

# 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) click to toggle source

(see map)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 375
def apply(&block)
  map(&block)
end
apply!(&block) click to toggle source

(see map!)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 380
def apply!(&block)
  map!(&block)
end
assign(obj, copy: false) click to toggle source

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

@param obj [#to_a] @kwarg copy [true, false] If specified with true it will copy the given object. By default is set to false. @raise ArgumentError if given object doesn't respond to to_a method @return [LinkedList] self object

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 29
def assign(obj, copy: false)
  from_obj(obj, copy)
end
clear() click to toggle source

Clears content of the list.

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 172
def clear
  @front = nil
  @length = @size = 0
  self
end
concat(linked_list) click to toggle source

(see +)

# 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) click to toggle source

Concatenates contents of self object and linked_list given as argument.

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] self object

# 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) click to toggle source

(see #!=)

# 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) click to toggle source

(see -)

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] self object

# 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?() click to toggle source

Returns true if there are no elements in the list.

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 99
def empty?
  @front.nil?
end
eql?(linked_list) click to toggle source

(see #==)

# 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) click to toggle source

Removes the element after the position specified by the iterator.

@param it @raise ArgumentIterator, if given iterator doesn't point to any element of the list. @return removed element

# 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) click to toggle source

(see select)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 339
def filter(&block)
  select(&block)
end
filter!(&block) click to toggle source

(see select!)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 344
def filter!(&block)
  select!(&block)
end
find_all(&block) click to toggle source

(see select)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 349
def find_all(&block)
  select(&block)
end
find_all!(&block) click to toggle source

(see select!)

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 354
def find_all!(&block)
  select!(&block)
end
insert_after(it, value) click to toggle source

Inserts an element after the position specified by iterator.

@param it, value [LinkedList::Iterator, any] @raise ArgumentError, if given iterator doesn't point to any element of the list. @return self object

# 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) click to toggle source

(see #&)

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] self object

# 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) click to toggle source

Applies a function to each element of the list.

@param &block @return [LinkedList] a new linked_list

# 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) click to toggle source

Applies a function to each element of the list.

@param &block @return [LinkedList] self object

# 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) click to toggle source

(see +)

# 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) click to toggle source

(see concat)

# 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() click to toggle source

Removes element at the beginning of the list.

@raise Algorithmix::EmptyContainerError if the list is empty. @return removed value

# 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) click to toggle source

Inserts a new element at the beginning of the list.

@param value @return newly inserted element

# 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) click to toggle source

Filters elements of the list by given condition.

@param &block @return [LinkedList] a new linked list

# 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) click to toggle source

Filters elements of the list by given condition.

@param &block @return [LinkedList] self object

# 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) click to toggle source

(see #^)

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] self object

# 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() click to toggle source

Converts content of the list to an array.

# File lib/algorithmix/data_structure/generic/linked_list.rb, line 167
def to_a
  convert
end
union(linked_list) click to toggle source

(see #|)

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] self object

# 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) click to toggle source

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

@param linked_list [LinedList] @raise ArgumentError, if given object is not a linked list @return [LinkedList] a new linked list

# 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

Private Instance Methods

convert() click to toggle source
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 434
def convert
  result = []
  it = @front
  until it.nil?
    result << it.value
    it = it.next_node
  end

  result
end
from_obj(obj, copy=false) click to toggle source
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 445
def from_obj(obj, copy=false)
  raise ArgumentError, "Undefined method #to_a for #{obj}:{obj.class}" unless obj.respond_to?(:to_a)

  @front = nil
  rand_id = Random.new.rand((2**(0.size * 8 -2) -1) / 2)
  obj.to_a.each do |e|
    tail = @front
    @front = Node.new(copy ? e.dup : e, tail, rand_id)
  end
  @length = @size = obj.to_a.length
  self
end