module Linked::Listable
The listable item is the foundational element of the linked list. Each link in the chain knows what comes both before and after, as well as which elements are in the beginning and end of the chain. This information can be used to iterate over the chained elements.
Internally each listable item stores three pointers: one to the head of the chain and two for the previous and next items respectivly. The head of the chain uses the head pointer to store how many elements are currently in the chain, for fast access. Furthermore it uses its pointer to the previous element to keep track of the last element of the chain.
In pracitce this means that some operations are fast, or computationally cheap, while other are more expensive. The follwing actions are fast:
1) Accessing the previous and next item. 2) Accessing the first and last element of the chain. 3) Calculating the length of the chain. 4) Appending items. 5) Deleting any item but the first one.
On the flip side, the following are the expensive operations:
1) Prepending items. 2) Deleting the first item. 3) Splitting the chain.
Notation¶ ↑
Some methods operate on chains of items, and to describe the effects of an operation the following syntax is used.
A A <> B (i) (ii)
Single items are denoted with capital letters (i), while chains are written as multiple connected items (ii).
Public Class Methods
Creates a new item. Always make a call to super whenever overriding this method in an including class.
# File lib/linked/listable.rb, line 46 def initialize(*) reset_item super end
Public Instance Methods
Iterates over each item after this. If a block is not given an enumerator is returned.
Note that raising a StopIteraion inside the block will cause the loop to silently stop the iteration early.
# File lib/linked/listable.rb, line 190 def after return to_enum(__callee__) unless block_given? return if chain_tail? item = self.next loop do yield item item = item.next end end
Iterates over each item before this, in reverse order. If a block is not given an enumerator is returned.
Note that raising a StopIteraion inside the block will cause the loop to silently stop the iteration early.
# File lib/linked/listable.rb, line 173 def before return to_enum(__callee__) unless block_given? return if chain_head? item = prev loop do yield item item = item.prev end end
Check if this object is in a chain.
@param other [Object] the object to check. @return [true] if this object is in the same chain as the given one. @return [false] otherwise.
# File lib/linked/listable.rb, line 126 def in_chain?(other) return false unless other.is_a? Listable chain_head.equal? other.chain_head end
Calling dup on an item returns a copy that is no longer connected to the original item chain, or the list. The value will also be copied.
@return [Listable] a new Listable
.
# File lib/linked/listable.rb, line 55 def initialize_copy(*) reset_item super end
Due to the nature of listable objects the default inspect
method is problematic. This basic replacement includes only the class name and the object id.
@return [String] a string representation of the object.
# File lib/linked/listable.rb, line 256 def inspect block_given? ? yield(self) : object_identifier end
Access the next item in the chain. If this is the last one a StopIteration will be raised, so that items may be iterated over safely in a loop.
Usage¶ ↑
loop do item = item.next end
@raise [StopIteration] if this item is the last in the chain.
@return [Listable] the item that come after this.
# File lib/linked/listable.rb, line 144 def next raise StopIteration if chain_tail? @_next end
Access the previous item in the chain. If this is the first one a StopIteration will be raised, so that items may be iterated over safely in a loop.
Usage¶ ↑
loop do item = item.prev end
@raise [StopIteration] if this item is the first in the chain.
@return [Listable] the item that come before this.
# File lib/linked/listable.rb, line 161 def prev raise StopIteration if chain_head? @_prev end
Take n items and put them into a sorted array. If n is positive the array will include this item, as well the n - 1 items following it in the chain. If n is negative the items will be taken from before this item instead.
If there are less than n - 1 items before/after this the resulting array will contain less than n items.
@raise [ArgumentError] if `n` is not an integer.
@param n [Integer] the number of items to take. @return [Array<Listable>] an array containing the taken items.
# File lib/linked/listable.rb, line 218 def take(n) raise ArgumentError, 'n must be an integer' unless n.is_a? Integer # Optimize for the most simple cases return [self] if n == 1 || n == -1 return [] if n.zero? n_abs = n.abs res = Array.new n_abs if n.positive? res[0] = self enum = after iter = 1.upto(n_abs - 1) else res[n_abs - 1] = self enum = before iter = (n_abs - 2).downto 0 end iter.each { |i| res[i] = enum.next } res rescue StopIteration res.compact! res end
Protected Instance Methods
Returns the first item in the chain. Note that the implementation of this method is protected and publicly accessible through its aliases first_in_chain
and chain
.
@return [Listable] the first item in the chain.
# File lib/linked/listable.rb, line 98 def chain_head chain_head? ? self : chain_head! end
Protected, unsafe accessor of the first item in the chain. It is preferable to use first.
Returns the first item in the chain, or the chain item count if this is the first one.
# File lib/linked/listable.rb, line 297 def chain_head! @_chain_head end
Returns the last item in the chain. Note that the implementation of this method is protected and publicly accessible through its aliases last_in_chain
.
@return [Listable] the last item in the chain.
# File lib/linked/listable.rb, line 110 def chain_tail chain_tail? ? self : chain_head.prev! end
Protected factory method for creating items compatible with this listable item. This method is called whenever an arbitrary object is appended or prepended onto this item and need to be wraped/converted.
This method can be overridden to support different behaviours.
args - any arguments will be passed on to .new.
Must return a new Listable
object.
# File lib/linked/listable.rb, line 271 def create_item(*args) self.class.new(*args) end
Protected unsafe accessor of the next item in the chain. It is preferable to use next
, possibly in conjunction with last?.
Returns the item that come after this, or nil if this is the last one.
# File lib/linked/listable.rb, line 279 def next! @_next end
Protected, unsafe accessor of the previous item in the chain. It is preferable to use prev
, possibly in conjunction with first?.
Returns the item that come before this, or the last item in the chain if this is the first one.
# File lib/linked/listable.rb, line 288 def prev! @_prev end
Private Instance Methods
Convert the given object to a listable item. If the object responds to item
the result of that call is returned. Otherwise a new item is created using create_item
.
@param other [Object] the object to coerce. @return [Listable] a listable item.
# File lib/linked/listable.rb, line 309 def coerce(other) if other.respond_to? :item other.item else create_item other end end
Reset the fields of the item to their initial state. This leaves the item in a consistent state as a single item chain.
Only call this method on items that are disconnected from their siblings. Otherwise the original chain (if any) will be left in an inconsistent state.
@return [self]
# File lib/linked/listable.rb, line 325 def reset_item @_chain_head = 1 @_next = nil @_prev = self end