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 



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

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 



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

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 



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

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) 


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

def empty?
  @size == 0
end

#find(key) ⇒ Object 



39
40
41
 
# File 'lib/data_structures/lru_cache.rb', line 39

def find(key)
  @hash[key]
end

#first ⇒ Object 



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

def first
  @linked_list.first
end

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


43
44
45
 
# File 'lib/data_structures/lru_cache.rb', line 43

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

#inspect ⇒ Object 



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

def inspect
  @linked_list.inspect
end

#last ⇒ Object 



35
36
37
 
# File 'lib/data_structures/lru_cache.rb', line 35

def last
  @linked_list.last
end

#length ⇒ Object 



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

def length
  @size
end

#prepend(key, val) ⇒ Object 



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

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 



99
100
101
102
103
104
105
106
107
108
 
# File 'lib/data_structures/lru_cache.rb', line 99

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

#to_s ⇒ Object 



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

def to_s
  @linked_list.to_s
end