Class: LRUCache

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures/lru_cache.rb

Instance Method Summary collapse

Constructor Details

#initialize(max_size) ⇒ LRUCache

Returns a new instance of LRUCache.



4
5
6
7
8
9
 
# File 'lib/data_structures/lru_cache.rb', line 4

def initialize(max_size)
  @max_size = max_size
  @size = 0
  @hash = {}
  @linked_list = LinkedList.new
end

Instance Method Details

#add_after_key(ref_key, key, val) ⇒ Object 



61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/data_structures/lru_cache.rb', line 61

def add_after_key(ref_key, key, val)
  node = @linked_list.add_after_key(ref_key, key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:first)
  else
    @size += 1
  end

  node
end

#add_before_key(ref_key, key, val) ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/data_structures/lru_cache.rb', line 74

def add_before_key(ref_key, key, val)
  node = @linked_list.add_before_key(ref_key, key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:last)
  else
    @size += 1
  end

  node
end

#append(key, val) ⇒ Object 



35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/data_structures/lru_cache.rb', line 35

def append(key, val)
  node = @linked_list.append(key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:first)
  else
    @size += 1
  end

  node
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


15
16
17
 
# File 'lib/data_structures/lru_cache.rb', line 15

def empty?
  @size == 0
end

#find(key) ⇒ Object 



27
28
29
 
# File 'lib/data_structures/lru_cache.rb', line 27

def find(key)
  @hash[key]
end

#first ⇒ Object 



19
20
21
 
# File 'lib/data_structures/lru_cache.rb', line 19

def first
  @linked_list.first
end

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


31
32
33
 
# File 'lib/data_structures/lru_cache.rb', line 31

def include?(key)
  @hash.has_key?(key)
end

#last ⇒ Object 



23
24
25
 
# File 'lib/data_structures/lru_cache.rb', line 23

def last
  @linked_list.last
end

#prepend(key, val) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/data_structures/lru_cache.rb', line 48

def prepend(key, val)
  node = @linked_list.prepend(key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:last)
  else
    @size += 1
  end

  node
end

#remove(key) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
 
# File 'lib/data_structures/lru_cache.rb', line 87

def remove(key)
  node = self.find(key)
  return nil if node.nil?

  @linked_list.remove(key)
  @hash.delete(key)
  @size -= 1

  node
end

#to_a ⇒ Object 



11
12
13
 
# File 'lib/data_structures/lru_cache.rb', line 11

def to_a
  @linked_list.to_a
end