Class: DLinked::CacheList

Inherits:
List
  • Object
show all
Defined in:
lib/d_linked/cache_list.rb

Overview

A specialized doubly linked list for managing keys in a Least Recently Used (LRU) cache.

This class extends List by integrating a ‘Hash` map (`@lru_nodes`) to provide **O(1)** time complexity for all critical cache operations: adding, accessing (touching), evicting, and removing keys.

The list maintains items in order from Most Recently Used (MRU) at the head to Least Recently Used (LRU) at the tail.

Examples:

Implementing a simple LRU Cache

class MyLRUCache
  def initialize(capacity)
    @capacity = capacity
    @list = DLinked::CacheList.new
    @data = {}
  end

  def get(key)
    return nil unless @data.key?(key)
    @list.move_to_head_by_key(key) # Mark as recently used
    @data[key]
  end

  def set(key, value)
    if @data.key?(key)
      @list.move_to_head_by_key(key)
    else
      @list.prepend_key(key, value)
      evict if @list.size > @capacity
    end
    @data[key] = value
  end

  private

  def evict
    lru_key = @list.pop_key
    @data.delete(lru_key)
  end
end

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Attributes inherited from List

#size

Instance Method Summary collapse

Methods inherited from List

#+, #[], #[]=, #append, #concat, #delete, #each, #empty?, #first, #index, #insert, #last, #pop, #prepend, #reverse_each, #shift, #slice, #slice!, #to_a, #to_s

Constructor Details

#initialize ⇒ CacheList

Initializes a new, empty ‘CacheList`.



67
68
69
70
 
# File 'lib/d_linked/cache_list.rb', line 67

def initialize
  super
  @lru_nodes = {}
end

Instance Attribute Details

#lru_nodes ⇒ Object (readonly)

Returns the value of attribute lru_nodes.



64
65
66
 
# File 'lib/d_linked/cache_list.rb', line 64

def lru_nodes
  @lru_nodes
end

Instance Method Details

#clear ⇒ self

Clears the list and the internal key map.

This is an **O(1)** operation.

Returns:

  • (self) 


162
163
164
165
 
# File 'lib/d_linked/cache_list.rb', line 162

def clear
  @lru_nodes.clear
  super
end

#move_to_head_by_key(key) ⇒ true, false

Moves an existing key from its current position to the head (making it the MRU item). This is a core “touch” operation for an LRU cache.

This is an **O(1)** operation.

Examples:

lru = DLinked::CacheList.new
lru.prepend_key(:a, 1)
lru.prepend_key(:b, 2) # List order: [:b, :a]
lru.move_to_head_by_key(:a) # "touch" :a
lru.to_a # => [1, 2] (node values), key order is now [:a, :b]

Parameters:

  • key (Object) —

    The key of the item to move.

Returns:

  • (true, false) —

    ‘true` if the move was successful, `false` if the key was not found.



129
130
131
132
133
134
135
 
# File 'lib/d_linked/cache_list.rb', line 129

def move_to_head_by_key(key)
  node = @lru_nodes[key]
  return false unless node

  _move_to_head(node)
  true
end

#pop_key ⇒ Object?

Removes the Least Recently Used (LRU) item from the tail of the list.

This is an **O(1)** operation.

Examples:

lru = DLinked::CacheList.new
lru.prepend_key(:a, 1)
lru.prepend_key(:b, 2) # List is now [:b, :a]
lru.pop_key # => :a

Returns:

  • (Object, nil) —

    The key of the removed LRU item, or ‘nil` if the list is empty.



107
108
109
110
111
112
113
 
# File 'lib/d_linked/cache_list.rb', line 107

def pop_key
  node = list_pop_logic
  return nil unless node

  @lru_nodes.delete(node.key)
  node.key
end

#prepend_key(key, value) ⇒ true

Adds a new key-value pair to the head of the list (making it the MRU item).

This is an **O(1)** operation.

Examples:

lru = DLinked::CacheList.new
lru.prepend_key(:a, 1)
lru.to_a # => [1]

Parameters:

  • key (Object) —

    The cache key.

  • value (Object) —

    The value to store in the list node.

Returns:

  • (true) —

    ‘true` on successful insertion.

Raises:

  • (RuntimeError) —

    If the key already exists.



87
88
89
90
91
92
93
94
 
# File 'lib/d_linked/cache_list.rb', line 87

def prepend_key(key, value)
  raise "Key #{key} already exists in the LRU list." if @lru_nodes.key?(key)

  node = Node.new(value, nil, @head, key)
  list_prepend_logic(node) # Use base class's logic
  @lru_nodes[key] = node
  true
end

#remove_by_key(key) ⇒ true, false

Removes an item from the list and map by its key.

This is an **O(1)** operation.

Examples:

lru = DLinked::CacheList.new
lru.prepend_key(:a, 1)
lru.remove_by_key(:a) # => true
lru.empty? # => true

Parameters:

  • key (Object) —

    The key of the item to remove.

Returns:

  • (true, false) —

    ‘true` if removed, `false` if the key was not found.



149
150
151
152
153
154
155
 
# File 'lib/d_linked/cache_list.rb', line 149

def remove_by_key(key)
  node = @lru_nodes.delete(key)
  return false unless node

  _remove_node(node)
  true
end