Module: Linked::List

Includes:
Enumerable
Defined in:
lib/linked/list.rb,
lib/linked/list/eol.rb

Overview

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.

Defined Under Namespace

Classes: EOL

Instance Method Summary collapse

Instance Method Details

#count(*args) ⇒ Object

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.



156
157
158
159
160
161
162
 
# File 'lib/linked/list.rb', line 156

def count(*args)
  if args.empty? && !block_given?
    @item_count
  else
    super
  end
end

#each_item(reverse: false, &block) ⇒ Object Also known as: each

Iterates over each item in the list, either in normal or reverse order. If a block is not given an enumerator is returned.

reverse - flips the iteration order if true. Note that this option is

depricated and will be removed in the next major release.



238
239
240
241
242
243
244
245
 
# File 'lib/linked/list.rb', line 238

def each_item(reverse: false, &block)
  if reverse
    warn '[DEPRECATION] the option `reverse: true` will be removed in a future release. Please call `reverse_each_item` instead.'
    eol.before(&block)
  else
    eol.after(&block)
  end
end

#empty? ⇒ Boolean

Returns true if the list does not contain any items.

Returns:

  • (Boolean) 


166
167
168
 
# File 'lib/linked/list.rb', line 166

def empty?
  @item_count == 0
end

#first(n = 1) ⇒ Object

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

Raises:

  • (ArgumentError) 


101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/linked/list.rb', line 101

def first(n = 1)
  raise ArgumentError, 'n cannot be negative' if n < 0

  return first_item_after eol, n, count unless block_given?

  item = eol
  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

#freeze ⇒ Object

Calls #freeze on all items in the list, as well as the head and the tail (eol).



261
262
263
264
265
 
# File 'lib/linked/list.rb', line 261

def freeze
  eol.freeze
  each_item(&:freeze)
  super
end

#include?(item) ⇒ Boolean

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.

Returns:

  • (Boolean) 


226
227
228
229
230
 
# File 'lib/linked/list.rb', line 226

def include?(item)
  item.in? self
rescue NoMethodError
  false
end

#initialize ⇒ Object

Initializes the list by setting the two instance variable @item_count and of the including class, and that the instance variables never be accessed directly.



46
47
48
49
50
51
 
# File 'lib/linked/list.rb', line 46

def initialize(*)
  @eol = EOL.new list: self
  @item_count = 0

  super
end

#initialize_dup(source) ⇒ Object

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.



57
58
59
60
61
62
63
64
 
# File 'lib/linked/list.rb', line 57

def initialize_dup(source)
  @eol = EOL.new list: self
  @item_count = 0

  source.each_item { |item| push item.dup  }

  super
end

#inspect(&block) ⇒ Object

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.



273
274
275
276
277
278
279
280
281
282
283
284
285
286
 
# File 'lib/linked/list.rb', line 273

def inspect(&block)
  # Get the parents inspect output
  res = [super]

  each_item do |item|
    lines = item.inspect(&block).split "\n"

    res.push (item.last? ? '└─╴' : '├─╴') + lines.shift
    padding = item.last? ? '   ' : '│  '
    lines.each { |line| res.push padding + line }
  end

  res.join("\n")
end

#item ⇒ Object

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.

Raises:

  • (NoMethodError) 


83
84
85
86
 
# File 'lib/linked/list.rb', line 83

def item
  raise NoMethodError if empty?
  eol.next
end

#last(n = 1) ⇒ Object

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

Raises:

  • (ArgumentError) 


131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/linked/list.rb', line 131

def last(n = 1)
  raise ArgumentError, 'n cannot be negative' if n < 0

  return last_item_before eol, n, count unless block_given?

  item = eol
  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

#list ⇒ Object

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.



72
73
74
 
# File 'lib/linked/list.rb', line 72

def list
  self
end

#pop ⇒ Object

Pop the last item off the list.

Returns the last item in the list, or nil if the list is empty.



191
192
193
194
 
# File 'lib/linked/list.rb', line 191

def pop
  return nil if empty?
  last.delete
end

#push(item) ⇒ Object Also known as: <<

Insert an item at the end of the list. If the given object is not an Item, or a decendant of Item, it will be treated as a value. Depending on the state of the list the value will be a) wraped in a new instance of Item if the list is empty or b) wraped in an object of the same class as the last item in the list.

item - the item to insert, or an arbitrary value.

Returns self.



180
181
182
183
 
# File 'lib/linked/list.rb', line 180

def push(item)
  eol.append item
  self
end

#reverse_each_item(&block) ⇒ Object Also known as: reverse_each

Iterates over each item in the list in reverse order. If a block is not given an enumerator is returned.



252
253
254
 
# File 'lib/linked/list.rb', line 252

def reverse_each_item(&block)
  eol.before(&block)
end

#shift ⇒ Object

Shift the first item off the list.

Returns the first item in the list, or nil if the list is empty.



215
216
217
218
 
# File 'lib/linked/list.rb', line 215

def shift
  return nil if empty?
  first.delete
end

#unshift(item) ⇒ Object

Insert an item at the beginning of the list. If the given object is not an Item, or a decendant of Item, it will be treated as a value. Depending on the state of the list the value will be a) wraped in a new instance of Item if the list is empty or b) wraped in an object of the same class as the last item in the list.

item - the item to insert, or an arbitrary value.

Returns self.



206
207
208
209
 
# File 'lib/linked/list.rb', line 206

def unshift(item)
  eol.prepend item
  self
end