Class: HashCache::LinkedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/hash_cache/linked_list.rb

Overview

This LinkedList class is unusual in that it gives direct access to its nodes. It trusts the user not to break it! The advantage is that outsiders with a node reference can reorder the list (eg, using #move_to_head) in O(1) time.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(item = nil) ⇒ LinkedList

Returns a new instance of LinkedList.



10
11
12
13
14
15
16
17
18
19
 
# File 'lib/hash_cache/linked_list.rb', line 10

def initialize(item = nil)
  if item
    Node.new(item).tap { |node|
      self.head   = self.tail = node
      self.length = 1
    }
  else
    self.length = 0
  end
end

Instance Attribute Details

#length ⇒ Object

Returns the value of attribute length.



8
9
10
 
# File 'lib/hash_cache/linked_list.rb', line 8

def length
  @length
end

Instance Method Details

#append(item) ⇒ Object 



29
30
31
32
33
34
35
36
 
# File 'lib/hash_cache/linked_list.rb', line 29

def append(item)
  return initialize(item) if empty?
  Node.new(item, left: tail).tap { |new_tail|
    tail.right = new_tail
    self.tail  = new_tail
    self.length = length + 1
  }
end

#each ⇒ Object 



21
22
23
24
25
26
27
 
# File 'lib/hash_cache/linked_list.rb', line 21

def each
  current = head
  while current do
    yield(current.value)
    current = current.right
  end
end

#empty? ⇒ Boolean Also known as: blank?

Returns:

  • (Boolean) 


73
74
75
 
# File 'lib/hash_cache/linked_list.rb', line 73

def empty?
  length == 0
end

#lpop ⇒ Object Also known as: shift 



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

def lpop
  head.tap {
    new_head      = head.right
    new_head.left = nil
    self.head     = new_head
    self.length = length - 1
  }
end

#move_to_head(node) ⇒ Object 



67
68
69
70
71
 
# File 'lib/hash_cache/linked_list.rb', line 67

def move_to_head(node)
  excise(node)
  node.right = head
  self.head  = node
end

#pop ⇒ Object 



48
49
50
51
52
53
54
55
 
# File 'lib/hash_cache/linked_list.rb', line 48

def pop
  tail.tap {
    new_tail       = tail.left
    new_tail.right = nil
    self.tail      = new_tail
    self.length = length - 1
  }
end

#prepend(item) ⇒ Object Also known as: unshift 



38
39
40
41
42
43
44
45
 
# File 'lib/hash_cache/linked_list.rb', line 38

def prepend(item)
  return initialize(item) if empty?
  Node.new(item, right: head).tap { |new_head|
    head.left = new_head
    self.head = new_head
    self.length = length + 1
  }
end

#presence ⇒ Object 



82
83
84
 
# File 'lib/hash_cache/linked_list.rb', line 82

def presence
  self if present?
end

#present? ⇒ Boolean

Returns:

  • (Boolean) 


79
80
81
 
# File 'lib/hash_cache/linked_list.rb', line 79

def present?
  !empty?
end