Module: Linked::Listable

Extended by:
Forwardable
Includes:
Mutable
Included in:
Item
Defined in:
lib/linked/listable.rb

Overview

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).

Instance Method Summary collapse

Methods included from Mutable

#append, #delete, #delete_after, #delete_before, #prepend

Instance Method Details

#after ⇒ Object

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.



190
191
192
193
194
195
196
197
198
199
200
 
# 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

#before ⇒ Object

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.



173
174
175
176
177
178
179
180
181
182
183
 
# 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

#in_chain?(other) ⇒ true, false Also known as: ===

Check if this object is in a chain.

Parameters:

  • other (Object) —

    the object to check.

Returns:

  • (true) —

    if this object is in the same chain as the given one.

  • (false) —

    otherwise.



126
127
128
129
 
# 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

#initialize ⇒ Object

Creates a new item. Always make a call to super whenever overriding this method in an including class.



46
47
48
49
 
# File 'lib/linked/listable.rb', line 46

def initialize(*)
  reset_item
  super
end

#initialize_copy ⇒ Listable

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.

Returns:



55
56
57
58
 
# File 'lib/linked/listable.rb', line 55

def initialize_copy(*)
  reset_item
  super
end

#inspect ⇒ String

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.

Returns:

  • (String) —

    a string representation of the object.



256
257
258
 
# File 'lib/linked/listable.rb', line 256

def inspect
  block_given? ? yield(self) : object_identifier
end

#item ⇒ Listable

Identity method that simply return the item. This method mirrors List#item and allows other methods that work on Item objects to easily and interchangebly accept both lists and items as arguments.

Returns:



65
66
67
 
# File 'lib/linked/listable.rb', line 65

def item
  self
end

#next ⇒ Listable

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

Returns:

  • (Listable) —

    the item that come after this.

Raises:

  • (StopIteration) —

    if this item is the last in the chain.



144
145
146
147
 
# File 'lib/linked/listable.rb', line 144

def next
  raise StopIteration if chain_tail?
  @_next
end

#prev ⇒ Listable Also known as: previous

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

Returns:

  • (Listable) —

    the item that come before this.

Raises:

  • (StopIteration) —

    if this item is the first in the chain.



161
162
163
164
 
# File 'lib/linked/listable.rb', line 161

def prev
  raise StopIteration if chain_head?
  @_prev
end

#take(n) ⇒ Array<Listable>

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.

Parameters:

  • n (Integer) —

    the number of items to take.

Returns:

  • (Array<Listable>) —

    an array containing the taken items.

Raises:

  • (ArgumentError) —

    if n is not an integer.



218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# 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