class Algorithmix::DataStructure::Generic::LinkedList
Attributes
Public Class Methods
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
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
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
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
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
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
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
(see push_front
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 48 def >>(value) push_front(value) end
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
(see map
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 375 def apply(&block) map(&block) end
(see map!
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 380 def apply!(&block) map!(&block) end
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
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
(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
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
(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
(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
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
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
(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
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
(see select
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 339 def filter(&block) select(&block) end
(see select!
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 344 def filter!(&block) select!(&block) end
(see select
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 349 def find_all(&block) select(&block) end
(see select!
)
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 354 def find_all!(&block) select!(&block) end
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
(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
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
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
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
(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
(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
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
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
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
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
(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
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
Converts content of the list to an array.
# File lib/algorithmix/data_structure/generic/linked_list.rb, line 167 def to_a convert end
(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
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
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
# 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
# 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