Class: Linked::Item

Inherits:
Object
  • Object
show all
Defined in:
lib/linked/item.rb

Overview

Item

This class implements doubly linked list items, designed to work both on their own and as children of list.

+- - - +    +------+------+            +- - - +
| Head | <--| prev | next |--> ... --> | Tail |
+ - - -+    +------+------+            + - - -+

(optional) First Item N Items (optional)

An object is considered a list if it responds to #head, #tail, #grow and #shrink. The latter facilitate counting of the items and will be called everytime an item is appended, prepended or deleted. #head and #tail are expected to return two objects that, respectivly a) responds to #next= and #append, or #prev= and #prepend and b) returns true for #nil?.

Direct Known Subclasses

List::EOL

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value = nil, list: nil) ⇒ Item

Creates a new item. If a list is given the item will be considered a part of that list and appended to the end of it.

value - an arbitrary object to store with the item. list - an object responding to #head and #tail.

Returns a new Item.



49
50
51
52
53
54
55
56
57
58
 
# File 'lib/linked/item.rb', line 49

def initialize(value = nil, list: nil)
  @value = value
  @list = list
  if list
    list.tail.append self
  else
    @next = nil
    @prev = nil
  end
end

Instance Attribute Details

#list ⇒ Object

Access the list that the item is part of. If the item is not in a list a NoMethodError will be raised. This mirrors the behaviour of List#list and allows other methods that work on List objects to easily and interchangeably accept both lists and items as arguments.

Returns the list that the item is part of.

Raises:

  • (NoMethodError) 


92
93
94
95
 
# File 'lib/linked/item.rb', line 92

def list
  raise NoMethodError unless @list
  @list
end

#next ⇒ Object

Access the next item in the list. If this is the last one a StopIteration will be raised, so that items may be iterated over safely in a loop.

Example

loop do
  item = item.next
end

Returns the item that come after this.

Raises:

  • (StopIteration) 


143
144
145
146
 
# File 'lib/linked/item.rb', line 143

def next
  raise StopIteration if last?
  @next
end

#prev ⇒ Object Also known as: previous

Access the previous item in the list. If this is the first one a StopIteration will be raised, so that items may be iterated over safely in a loop.

Example

loop do
  item = item.prev
end

Returns the item that come before this.

Raises:

  • (StopIteration) 


168
169
170
171
 
# File 'lib/linked/item.rb', line 168

def prev
  raise StopIteration if first?
  @prev
end

#value ⇒ Object

The Item can hold an arbitrary object as its value and it will stay with the item.



33
34
35
 
# File 'lib/linked/item.rb', line 33

def value
  @value
end

Instance Method Details

#after ⇒ Object

Iterates over each item after this. If a block is not given an enumerator is returned.



358
359
360
361
362
363
364
365
366
367
368
 
# File 'lib/linked/item.rb', line 358

def after
  return to_enum(__callee__) unless block_given?
  return if last?

  item = self.next

  loop do
    yield item
    item = item.next
  end
end

#append(sibling) ⇒ Object

Inserts the given item between this one and the one after it (if any). If the given item is part of a chain, all items following it will be moved to this one, and added to the list if one is set.

Alternativly the argument can be an arbitrary object, in which case a new item will be created around it.

If this item is part of a list #grow will be called on it with the number of added items as an argument. Should it also be the last item #prev= will be called on the list tail.

sibling - the item to append, or an arbitrary object to be wraped in a new

item.

Returns the last item that was appended.



261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
 
# File 'lib/linked/item.rb', line 261

def append(sibling)
  if sibling.is_a? Item
    sibling.split
  else
    sibling = self.class.new sibling
  end

  sibling.prev = self
  after_sibling = @next
  @next = sibling

  count = 1 + loop.count do
    sibling.list = @list
    sibling = sibling.next
  end

  @list.send :grow, count if @list

  sibling.next = after_sibling
  after_sibling.prev = sibling if after_sibling
  sibling
end

#before ⇒ Object

Iterates over each item before this, in reverse order. If a block is not given an enumerator is returned.



343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/linked/item.rb', line 343

def before
  return to_enum(__callee__) unless block_given?
  return if first?

  item = self.prev

  loop do
    yield item
    item = item.prev
  end
end

#delete ⇒ Object

Remove an item from the chain. If this item is part of a list and is either first, last or both in that list, #next= and #prev= will be called on the list head and tail respectivly.

If this item is part of a list #shrink will be called on it.

Returns self.



331
332
333
334
335
336
337
338
 
# File 'lib/linked/item.rb', line 331

def delete
  @next.prev = @prev if @next
  @prev.next = @next if @prev
  @list.send :shrink if @list

  @next = @prev = @list = nil
  self
end

#first? ⇒ Boolean

Check if this is the first item in the list. It is crucial that tail#nil? returns true for the first item to be identified correctly.

Returns true if no item come before this one.

Returns:

  • (Boolean) 


110
111
112
 
# File 'lib/linked/item.rb', line 110

def first?
  @prev.nil?
end

#freeze ⇒ Object

Freezes the value, as well as making the list item itself immutable.



372
373
374
375
 
# File 'lib/linked/item.rb', line 372

def freeze
  value.freeze
  super
end

#in?(list) ⇒ Boolean

Check if the item is in the given list.

list - any object.

Returns true if the item is part of the given list.

Returns:

  • (Boolean) 


129
130
131
 
# File 'lib/linked/item.rb', line 129

def in?(list)
  @list.equal? list
end

#in_list? ⇒ Boolean

Check it the item is part of a list.

Returns true if the item is in a list.

Returns:

  • (Boolean) 


101
102
103
 
# File 'lib/linked/item.rb', line 101

def in_list?
  @list ? true : false
end

#initialize_dup(source) ⇒ Object

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 a new Item.



65
66
67
68
69
70
71
72
73
 
# File 'lib/linked/item.rb', line 65

def initialize_dup(source)
  @next = @prev = @list = nil
  @value = begin
             source.value.dup
           rescue TypeError
             source.value
           end
  super
end

#inspect ⇒ Object

The default #inspect method becomes very cluttered the moment you start liking objects together. This implementation fixes that and only shows the class name, object id and value (if set).



381
382
383
384
385
386
 
# File 'lib/linked/item.rb', line 381

def inspect
  return yield self if block_given?

  output = format '%s:0x%0x', self.class.name, object_id
  value ? output + " value=#{value.inspect}" : output
end

#item ⇒ Object

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 the item itself.



81
82
83
 
# File 'lib/linked/item.rb', line 81

def item
  self
end

#last? ⇒ Boolean

Check if this is the last item in the list. It is crucial that head#nil? returns true for the last item to be identified correctly.

Returns true if no item come after this one.

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/linked/item.rb', line 119

def last?
  @next.nil?
end

#next! ⇒ Object

Unsafe accessor of the next item in the list. It is preferable to use #next.

Returns the item that come after this, or nil if this is the last one.



153
154
155
 
# File 'lib/linked/item.rb', line 153

def next!
  @next
end

#prepend(sibling) ⇒ Object

Inserts the given item between this one and the one before it (if any). If the given item is part of a chain, all items preceeding it will be moved to this one, and added to the list if one is set.

Alternativly the argument can be an arbitrary object, in which case a new item will be created around it.

If this item is part of a list #grow will be called on it with the number of added items as an argument. Should it also be the first item #next= will be called on the list head.

sibling - the item to prepend. or an arbitrary object to be wraped in a

new item.

Returns the last item that was prepended.



300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'lib/linked/item.rb', line 300

def prepend(sibling)
  if sibling.is_a? Item
    sibling.split after: true
  else
    sibling = self.class.new sibling
  end

  sibling.next = self
  before_sibling = @prev
  @prev = sibling

  count = 1 + loop.count do
    sibling.list = @list
    sibling = sibling.prev
  end

  @list.send :grow, count if @list

  sibling.prev = before_sibling
  before_sibling.next = sibling if before_sibling
  sibling
end

#prev! ⇒ Object Also known as: previous!

Unsafe accessor of the previous item in the list. It is preferable to use #prev.

Returns the item that come before this, or nil if this is the first one.



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

def prev!
  @prev
end

#split(after: false) ⇒ Object

Split the chain of items in two. If the chain belongs to a list this item and all that stay connected to it will continue to belong to it, while the rest are removed from it.

By default all items followng this one will be kept together, but if given the argument after: true, the split will instead happen after this item and it will instead be kept with those before it.

Example

item_b.split(after: false) => ~item_a~ |> item_b     item_c
item_b.split(after: true)  =>  item_a     item_b <| ~item_c~

after - determine wheter to split the chain before or after this item.

Returns self.



203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
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
 
# File 'lib/linked/item.rb', line 203

def split after: false
  if after
    unless last?
      if @list
        item = self
        count = 1 + loop.count do
          item = item.next
          item.list = nil
        end

        tail = @list.tail
        tail.prev = self
        @next = tail
        @list.shrink count
      else
        @next.prev = nil
        @next = nil
      end
    end
  else
    unless first?
      if @list
        item = self
        count = 1 + loop.count do
          item = item.prev
          item.list = nil
        end

        head = @list.head
        head.next = self
        @prev = head
        @list.shrink count
      else
        @prev.next = nil
        @prev = nil
      end
    end
  end

  self
end