lib/linked/list.rb in linked-0.4.0 vs lib/linked/list.rb in linked-0.5.1
- old
+ new
@@ -1,396 +1,219 @@
# frozen_string_literal: true
module Linked
- # List
+ # This class provides a way extend the regular chain of listable items with
+ # the concept of an empty chain.
#
- # This class implements a linked list. Most importantly, the methods #head,
- # #tail, #grow, #shrink and #create_item are implemented to comply with the
- # requirements defined by Listable.
-
+ # Lists are ment to behave more like arrays, and respond to many of the same
+ # methods.
class List
- include Enumerable
+ include ListEnumerable
+ include Util
- # Initializes the list. It is important that this method be called during
- # the initialization of the including class, and that the instance variables
- # @_item_count and @_eol never be accessed directly.
-
+ # Initializes the list.
def initialize
- @_eol = EOL.new self
- @_item_count = 0
-
+ reset_list
super
end
# When copying a list its entire item chain needs to be copied as well.
# Therefore #dup will be called on each of the original lists items, making
# this operation quite expensive.
-
+ #
+ # @param source [List] the list to copy.
def initialize_dup(source)
- @_eol = EOL.new self
- @_item_count = 0
+ reset_list
+ source.each_item { |item| push item.dup }
- source.each_item { |item| push item.dup }
-
super
end
- # Identity method that simply return the list. This method mirrors Item#list
- # and allows other methods that work on List objects to easily and
- # interchangebly accept both lists and items as arguments.
- #
- # Returns the list itself.
-
- def list
- self
- end
-
# Access the first item in the list. If the list is empty a NoMethodError
# will be raised. This mirrors the behaviour of Item#item and allows other
# methods that work on List objects to easily and interchangeably accept
# both lists and items as arguments.
#
- # Returns the first item in the list.
-
+ # @return [Listable] the first item in the list.
def item
raise NoMethodError if empty?
- head.next
+ @_chain
end
# Two lists are considered equal if the n:th item from each list are equal.
#
- # other - any object.
- #
- # Returns true if the given object is a list and the items are equal.
-
+ # @param other [Object] the object to compare with.
+ # @return [true] if the given object is a list and the items are equal.
+ # @return [false] otherwise.
def ==(other)
return false unless other.is_a? self.class
- return false unless other.count == @_item_count
+ return false unless other.count == count
other_items = other.each_item
each_item.all? { |item| item == other_items.next }
end
alias eql? ==
- # Access the first n item(s) in the list. If a block is given each item will
- # be yielded to it. The first item, starting from the first in the list, for
- # which the block returns true and the n - 1 items directly following it
- # will be returned.
- #
- # n - the number of items to return.
- #
- # Returns, for different values of n:
- # n == 0) nil
- # n == 1) an item if the list contains one, or nil
- # n > 1) an array of between 0 and n items, depending on how many are in
- # the list
-
- def first(n = 1)
- raise ArgumentError, 'n cannot be negative' if n < 0
-
- return first_item_after head, n, count unless block_given?
-
- item = head
- items_left = count
-
- items_left.times do
- break if yield next_item = item.next
- item = next_item
- items_left -= 1
- end
-
- first_item_after item, n, items_left
- end
-
- # Access the last n item(s) in the list. The items will retain thier order.
- # If a block is given each item, starting with the last in the list, will be
- # yielded to it. The first item for which the block returns true and the
- # n - 1 items directly preceding it will be returned.
- #
- # n - the number of items to return.
- #
- # Returns, for different values of n:
- # n == 0) nil
- # n == 1) an item if the list contains one, or nil
- # n > 1) an array of between 0 and n items, depending on how many are in
- # the list
-
- def last(n = 1)
- raise ArgumentError, 'n cannot be negative' if n < 0
-
- return last_item_before tail, n, count unless block_given?
-
- item = tail
- items_left = count
-
- items_left.times do
- break if yield prev_item = item.prev
- item = prev_item
- items_left -= 1
- end
-
- last_item_before item, n, items_left
- end
-
- # Overrides the Enumerable#count method when given no argument to provide a
- # fast item count. Instead of iterating over each item, the internal item
- # count is returned.
- #
- # args - see Enumerable#count
- #
- # Returns the number of items counted.
-
- def count(*args)
- if args.empty? && !block_given?
- @_item_count
- else
- super
- end
- end
-
- # Returns true if the list does not contain any items.
-
+ # @return [true] if the list does not contain any items.
+ # @return [false] otherwise.
def empty?
- @_item_count == 0
+ nil.eql? @_chain
end
# Insert an item at the end of the list. If the given object is not an
# object responding to #item it will be treated as a value. The value will
# be wraped in a new Item create by #create_item.
#
# See Item#append for more details.
#
- # object - the item to insert, or an arbitrary object.
- #
- # Returns self.
-
+ # @param object [#item, Object] the item to insert, or an arbitrary object.
+ # @return [self]
def push(object)
- tail.append object
+ item = coerce_item object
+
+ if empty?
+ @_chain = item
+ else
+ list_tail.append item
+ end
+
self
end
alias << push
# Pop the last item off the list.
#
- # Returns the last item in the list, or nil if the list is empty.
-
+ # @return [Listable, nil] the last item in the list, or nil if the list is
+ # empty.
def pop
return nil if empty?
- last.delete
+
+ if list_tail.first?
+ item = last
+ @_chain = nil
+ item
+ else
+ list_tail.delete
+ end
end
# Insert an item at the beginning of the list. If the given object is not an
# object responding to #item it will be treated as a value. The value will
# be wraped in a new Item create by #create_item.
#
# See Item#prepend for more details.
#
- # object - the item to insert, or an arbitrary object.
- #
- # Returns self.
-
+ # @param object [#item, Object] the item to insert, or an arbitrary object.
+ # @return [self]
def unshift(object)
- head.prepend object
+ item = coerce_item object
+ @_chain = empty? ? item.chain : @_chain.prepend(item)
+
self
end
# Shift the first item off the list.
#
- # Returns the first item in the list, or nil if the list is empty.
-
+ # @return [Listable, nil] the first item in the list, or nil if the list is
+ # empty.
def shift
return nil if empty?
- first.delete
+
+ if list_head.last?
+ item = @_chain
+ @_chain = nil
+ item
+ else
+ old_head = list_head
+ @_chain = list_head.next
+ old_head.delete
+ end
end
# Check if an item is in the list.
#
- # item - Item, or any object that may be in the list.
- #
- # Returns true if the given item is in the list, otherwise false.
-
+ # @param item [Object] any object that may be in the list.
+ # @return [true] if the given item is in the list.
+ # @return [false] otherwise.
def include?(item)
- item.in? self
- rescue NoMethodError
- false
+ return false if empty?
+ # TODO: This works fine, but looks wrong.
+ @_chain.in_chain? item
end
- # Iterates over each item in the list If a block is not given an enumerator
- # is returned.
-
- def each_item
- return to_enum(__method__) { count } unless block_given?
- return if empty?
-
- item = head
- loop { yield item = item.next }
- end
-
- alias each each_item
-
- # Iterates over each item in the list in reverse order. If a block is not
- # given an enumerator is returned.
-
- def reverse_each_item
- return to_enum(__method__) { count } unless block_given?
- return if empty?
-
- item = tail
- loop { yield item = item.prev }
- end
-
- alias reverse_each reverse_each_item
-
# Calls #freeze on all items in the list, as well as the head and the tail
# (eol).
-
+ #
+ # @return [self]
def freeze
- @_eol.freeze
each_item(&:freeze)
super
end
# Overrides the default inspect method to provide a more useful view of the
# list.
#
# Importantly this implementation supports nested lists and will return a
# tree like structure.
- def inspect(&block)
- # Get the parents inspect output
- res = [super]
+ def inspect_list(&block)
+ res = [block_given? ? yield(self) : object_identifier]
each_item do |item|
lines = item.inspect(&block).split "\n"
- res.push (item.last? ? '└─╴' : '├─╴') + lines.shift
+ res.push((item.last? ? '└─╴' : '├─╴') + lines.shift)
padding = item.last? ? ' ' : '│ '
lines.each { |line| res.push padding + line }
end
res.join("\n")
end
+ alias inspect inspect_list
+
# Protected factory method for creating items compatible with the list. This
# method is called whenever an arbitrary object is pushed or unshifted onto
# the list and need to be wraped inside an Item.
#
# This method can be overridden to support different Item types.
#
- # args - any arguments will be passed on to Item.new.
- #
- # Returns a new Item.
-
+ # @param args [Array<Object>] the arguments that are to be passed on to
+ # `Item.new`.
+ # @return [Item] a new `Listable` item.
protected def create_item(*args)
Item.new(*args)
end
- # Returns an object that responds to #next= and #prepend.
-
- protected def head
- @_eol
- end
-
- # Returns an object that responds to #prev= and #append.
-
- alias tail head
-
- # Internal method to grow the list with n elements. Never call this method
- # without also inserting the n elements.
+ # Takes an arbitrary object and coerces it into an item compliant with the
+ # list. If the object is already an item it will be used as is. Otherwise
+ # #create_item will be called with the object as an argument.
#
- # n - the number of items that has been/will be added to the list.
- #
- # Returns updated the item count.
-
- private def grow(n = 1)
- @_item_count += n
+ # @param [#item, Object] the object to coerce.
+ # @return [Listable] see `#create_item`.
+ private def coerce_item(object)
+ if object.respond_to? :item
+ object.item
+ else
+ create_item object
+ end
end
- # Internal method to shrink the list with n elements. Never call this method
- # without also deleting the n elements.
- #
- # n - the number of items that has been/will be removed from the list.
- #
- # Returns updated the item count.
-
- private def shrink(n = 1)
- @_item_count -= n
+ # Private method for clearing the list and bringing it to a pristine
+ # state.
+ private def reset_list
+ @_chain = nil
end
- # Private method to clear the list. Never call this method without also
- # modifying the items in the list, as this operation leavs them in an
- # inconsistant state. If the list items are kept, make sure to
- # a) clear the `prev` pointer of the first item and
- # b) clear the `next` pointer of the last item.
-
- private def clear
- @_eol.send :reset
- @_item_count = 0
+ # Returns the first item item in the list, or nil if empty.
+ private def list_head
+ @_chain
end
- # Private helper method that returns the first n items, starting just
- # after item, given that there are items_left items left. Knowing the exact
- # number of items left is not cruicial but does impact speed. The number
- # should not be lower than the actual ammount. The following must
- # hold for the output to be valid:
- # a) n > 0
- # b) there are at least items_left items left
- #
- # item - the Item just before the item to start from.
- # n - the number of items to return.
- # items_left - the number of items left.
- #
- # Returns, for different values of n:
- # n == 0) nil
- # n == 1) an item if items_left > 0 or nil
- # n > 1) an array of items if items_left > 0 or an empty array
-
- private def first_item_after(item, n, items_left = @_item_count)
- # Optimize for these cases
- return nil if n == 0
- return n > 1 ? [] : nil if item.last?
- return item.next if n == 1
-
- n = items_left if n > items_left
-
- arr = Array.new n
- n.times { |i| arr[i] = item = item.next }
- arr
- rescue StopIteration
- arr.compact! || arr
- end
-
- # Private helper method that returns the last n items, ending just before
- # item, given that there are items_left items left. Knowing the exact
- # number of items left is not cruicial but does impact speed. The number
- # should not be lower than the actual ammount. The following must hold for
- # the output to be valid:
- # a) n > 0
- # b) there are at least items_left items left
- #
- # item - the Item just after the item to start from.
- # n - the number of items to return.
- # items_left - the number of items left.
- #
- # Returns, for different values of n:
- # n == 0) nil
- # n == 1) an item if items_left > 0 or nil
- # n > 1) an array of items if items_left > 0 or an empty array
-
- private def last_item_before(item, n, items_left = @_item_count)
- # Optimize for these cases
- return nil if n == 0
- return n > 1 ? [] : nil if item.first?
- return item.prev if n == 1
-
- n = items_left if n > items_left
-
- arr = Array.new n
- (n - 1).downto(0) { |i| arr[i] = item = item.prev }
- arr
- rescue StopIteration
- arr.compact! || arr
+ # Returns an the last item in the list, or nil if empty.
+ private def list_tail
+ @_chain.last_in_chain
end
end
end