lib/linked/list.rb in linked-0.3.1 vs lib/linked/list.rb in linked-0.4.0
- old
+ new
@@ -1,64 +1,35 @@
# frozen_string_literal: true
module Linked
# List
#
- # This module can be included in any class to give it list like behaviour.
- # Most importantly, the methods #head, #tail, #grow and #shrink are
- # implemented to comply with the requirements defined by Item.
- #
- # Example
- #
- # class ListLike
- # include Linked::List
- #
- # def initialize
- # super
- # ...
- #
- # A key implementation detail is the End-Of-List, or EOL object that sits
- # between the list and the actual list items. It provides separation between
- # the list and the actual list items.
+ # 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.
- module List
+ class List
include Enumerable
- # Private accessor method for the End-Of-List object.
- #
- # Returns a List::EOL object.
+ # 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.
- attr_reader :eol
- private :eol
+ def initialize
+ @_eol = EOL.new self
+ @_item_count = 0
- # Returns an object that responds to #next= and #prepend.
-
- alias head eol
-
- # Returns an object that responds to #prev= and #append.
-
- alias tail eol
-
- # Initializes the list by setting the two instance variable @item_count and
- # @eol. It is important that this method be called during the initialization
- # of the including class, and that the instance variables never be accessed
- # directly.
-
- def initialize(*)
- @eol = EOL.new list: self
- @item_count = 0
-
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.
def initialize_dup(source)
- @eol = EOL.new list: self
- @item_count = 0
+ @_eol = EOL.new self
+ @_item_count = 0
source.each_item { |item| push item.dup }
super
end
@@ -80,13 +51,29 @@
#
# Returns the first item in the list.
def item
raise NoMethodError if empty?
- eol.next
+ head.next
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.
+
+ def ==(other)
+ return false unless other.is_a? self.class
+ return false unless other.count == @_item_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.
#
@@ -99,13 +86,13 @@
# the list
def first(n = 1)
raise ArgumentError, 'n cannot be negative' if n < 0
- return first_item_after eol, n, count unless block_given?
+ return first_item_after head, n, count unless block_given?
- item = eol
+ item = head
items_left = count
items_left.times do
break if yield next_item = item.next
item = next_item
@@ -129,13 +116,13 @@
# the list
def last(n = 1)
raise ArgumentError, 'n cannot be negative' if n < 0
- return last_item_before eol, n, count unless block_given?
+ return last_item_before tail, n, count unless block_given?
- item = eol
+ item = tail
items_left = count
items_left.times do
break if yield prev_item = item.prev
item = prev_item
@@ -153,20 +140,20 @@
#
# Returns the number of items counted.
def count(*args)
if args.empty? && !block_given?
- @item_count
+ @_item_count
else
super
end
end
# Returns true if the list does not contain any items.
def empty?
- @item_count == 0
+ @_item_count == 0
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.
@@ -176,11 +163,11 @@
# object - the item to insert, or an arbitrary object.
#
# Returns self.
def push(object)
- eol.append object
+ tail.append object
self
end
alias << push
@@ -202,11 +189,11 @@
# object - the item to insert, or an arbitrary object.
#
# Returns self.
def unshift(object)
- eol.prepend object
+ head.prepend object
self
end
# Shift the first item off the list.
#
@@ -234,11 +221,11 @@
def each_item
return to_enum(__method__) { count } unless block_given?
return if empty?
- item = eol
+ item = head
loop { yield item = item.next }
end
alias each each_item
@@ -247,21 +234,21 @@
def reverse_each_item
return to_enum(__method__) { count } unless block_given?
return if empty?
- item = eol
+ 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).
def freeze
- eol.freeze
+ @_eol.freeze
each_item(&:freeze)
super
end
# Overrides the default inspect method to provide a more useful view of the
@@ -287,56 +274,64 @@
# 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 suport different Item types.
+ # This method can be overridden to support different Item types.
#
# args - any arguments will be passed on to Item.new.
#
# Returns a new 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.
#
# 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
+ @_item_count += n
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
+ @_item_count -= n
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
- head.send :next=, tail
- tail.send :prev=, head
-
- @item_count = 0
+ @_eol.send :reset
+ @_item_count = 0
end
- # Protected helper method that returns the first n items, starting just
+ # 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
@@ -349,14 +344,14 @@
# 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
- protected def first_item_after(item, n, items_left = @item_count)
+ 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.next!.nil?
+ return n > 1 ? [] : nil if item.last?
return item.next if n == 1
n = items_left if n > items_left
arr = Array.new n
@@ -364,11 +359,11 @@
arr
rescue StopIteration
arr.compact! || arr
end
- # Protected helper method that returns the last n items, ending just before
+ # 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
@@ -381,29 +376,21 @@
# 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
- protected def last_item_before(item, n, items_left = @item_count)
+ 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.prev!.nil?
+ 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
- end
-
- # This method is called whenever the module is included somewhere. In the
- # special case when List is included in an Item the #item method must be
- # changed to return self.
-
- def self.included(klass)
- klass.send(:define_method, :item) { self } if klass < Item
end
end
end