Documentation
¶
Index ¶
- Constants
- type Cache
- type DLLNode
- type DoublyLinkedList
- type Error
- type Key
- type LRUCache
- func (lru *LRUCache) Capacity() int
- func (lru *LRUCache) Full() bool
- func (lru *LRUCache) GetElement(element interface{}) (string, error)
- func (lru *LRUCache) PrintCache()
- func (lru *LRUCache) PutElement(element interface{}) error
- func (lru *LRUCache) RemoveElement(element interface{}) error
- func (lru *LRUCache) Size() int
- type LinkedList
- type Node
- type SimpleKey
Constants ¶
const ( ErrElementDoesntExist = Error("element doesn't exist in the cache") ErrElementAlreadyExists = Error("element already exists in the cache") ErrCacheDoesntExist = Error("cache doesn't exist") )
Constant errors. Rule of thumb, all errors start with a small letter and end with no full stop.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache interface {
// GetElement gets the desired object from the cache.
// Getting the object makes it the most recently used object
// in the cache. This function must be implemented in O(1) complexity.
// If the object doesn't exist in the cache, an error is raised.
GetElement(element interface{}) (string, error)
// PutElement inserts an object into the cache.
// Putting the object makes it the most recently used object
// in the cache. This function must be implemented in O(1) complexity.
// If the object already exists in the cache, an error is raised.
PutElement(element interface{}) error
// Capacity returns the max capacity of the cache.
Capacity() int
// Size returns the number of elements currently in the cache.
Size() int
// Full checks whether the cache is full or not. It returns true if the
// cache is full.
Full() bool
// PrintCache prints the cache elements in the decreasing order
// or use frequency.
PrintCache()
}
Cache describes an entity of a cache.
type DLLNode ¶
DLLNode is the single entity of the doubly linked list.
type DoublyLinkedList ¶
type DoublyLinkedList struct {
Head Node
}
DoublyLinkedList implements LinkedList.
All nodes have a up and a down link except the head and the tail node.
func NewDoublyLinkedList ¶
func NewDoublyLinkedList() *DoublyLinkedList
NewDoublyLinkedList returns a new instance of an empty DoublyLinkedList.
func (*DoublyLinkedList) CreateNode ¶
func (dll *DoublyLinkedList) CreateNode() Node
CreateNode creates an empty node of the DLL with default values.
func (*DoublyLinkedList) DeleteNode ¶
func (dll *DoublyLinkedList) DeleteNode(node Node)
DeleteNode deletes the provided node.
func (*DoublyLinkedList) InsertNodeToLeft ¶
func (dll *DoublyLinkedList) InsertNodeToLeft(node Node, key Key)
InsertNodeToLeft inserts a node with given value to the left of the given node.
func (*DoublyLinkedList) InsertNodeToRight ¶
func (dll *DoublyLinkedList) InsertNodeToRight(node Node, key Key)
InsertNodeToRight inserts a node with the given value to the right of the given node.
func (*DoublyLinkedList) PrintLinkedList ¶
func (dll *DoublyLinkedList) PrintLinkedList()
PrintLinkedList prints the given linked list from head to tail order.
type LRUCache ¶
type LRUCache struct {
// contains filtered or unexported fields
}
LRUCache implements a cache. It uses a linked list as the primary data structure along with a hash-map for checking existance of an element in the cache.
The starting element in the linked list will always be the most recently used element in the cache and will be maintained that way by all the operating functions.
GetElement and PutElement inherently implement a method to rank the elements on the basis of frequency. This frequency based order is controlled by:
- Maintaining a logical order in the DLL - first element is MRU.
- At every insertion, the MRU is maintained at the Head of the DLL.
- After every access, the element is moved to the MRU position in the DLL.
- All insertions occur at the head of the DLL since this is the MRU position. This ensures that the LRU position is the tail.
The hash map maintains the existance of the element in the cache and the DLL is to maintain the frequency of the usage of the element.
func NewLRUCache ¶
NewLRUCache creates a new LRUCache of provided size.
func (*LRUCache) GetElement ¶
GetElement gets an element from the cache. It returns the associated data with the element with an error.
Whenever an element is retrieved from the cache, it's bumped to the MRU position in the DLL.
The element is removed from the map too because it might have stale node values.
Error is returned only if the element doesn't exist in the cache.
func (*LRUCache) PrintCache ¶
func (lru *LRUCache) PrintCache()
PrintCache prints the entire cache in decreasing order of frequency of usage.
func (*LRUCache) PutElement ¶
PutElement inserts an element in the cache. All insertions occur at the head node of the DLL.
Removal of the LRU is done my deleting the tail node, making place for a new node.
func (*LRUCache) RemoveElement ¶
RemoveElement deletes a node from the cache based on a key value If there are multiple nodes with the same value, the node that was most recently used will be removed.
type LinkedList ¶
type LinkedList interface {
// CreateNode creates a node with default values in it.
CreateNode() Node
// InsertNodeToLeft inserts a node to the left of the given node,
// with the key provided. It returns the pointer to the node
// inserted into the linked list.
InsertNodeToLeft(node Node, key Key)
// InsertNodeToRight inserts a node to the right of the given node,
// with the key provided. It returns the pointer to the node
// inserted tothe linked list.
InsertNodeToRight(node Node, key Key)
// DeleteNode deletes the node provided as the argument from the
// linked list.
DeleteNode(Node)
// PrintLinkedList prints the linked list from head to tail order.
PrintLinkedList()
}
LinkedList describes a linked list object.
type SimpleKey ¶
SimpleKey implements a Key interface.
func NewSimpleKey ¶
NewSimpleKey returns a new SimpleKey of the given value.
Source Files