LFU Cache III

I have spent some time attempting to implement the LFU Cache using the Java language. Perhaps I should put some additional time but given that Java does not support pointers perhaps it would be a convenient point to switch to C / C++ to get this done. After that I will probably returns to Java and attempt to implement this algorithm.

I have enhanced some and added other methods to the DoubleLinkList class.

Following is a screen capture of the console from the Eclipse IDE:

DoubleLinkList <<< constructor

main <<< iNode: val: 0 next: null prev: null

main <<< iNode: val: 1 next: null prev: john.linked.list.Node@15db9742

main <<< iNode: val: 2 next: null prev: john.linked.list.Node@6d06d69c

main <<< iNode: val: 3 next: null prev: john.linked.list.Node@7852e922

main <<< iNode: val: 4 next: null prev: john.linked.list.Node@4e25154f

main <<< iNode: val: 5 next: null prev: john.linked.list.Node@70dea4e

main <<< iNode: val: 6 next: null prev: john.linked.list.Node@5c647e05

main <<< count: 7

main <<<  list: 0 1 2 3 4 5 6

main <<< peekHead: 0

main <<< peekTail: 6

main <<<      find(0): true

main <<<    delete(0): 0

main <<<        count: 6

main <<<         list: 1 2 3 4 5 6

main <<<      find(6): true

main <<<    delete(6): 6

main <<<        count: 5

main <<<         list: 1 2 3 4 5

main <<<      find(3): true

main <<<    delete(3): 3

main <<<        count: 4

main <<<         list: 1 2 4 5

main <<<   find(9999): false

main <<<        count: 4

main <<<         list: 1 2 4 5

main <<< isFull: false

main <<<  count: 5

main <<<   list: 1 11 2 4 5

main <<< isFull: false

main <<<  count: 6

main <<<   list: 1 11 2 33 4 5

main <<< isFull: false

main <<<  count: 7

main <<<   list: 1 11 2 33 4 5 66

main <<< isFull: false

main <<<  count: 8

main <<<   list: 0 1 11 2 33 4 5 66

main <<< isFull: false

main <<<  count: 9

main <<<   list: 0 1 11 2 33 4 5 55 66

main <<< isFull: false

main <<<  count: 10

main <<<   list: 0 1 11 2 33 34 4 5 55 66

main <<< val: 0 next: john.linked.list.Node@6d06d69c prev: null

main <<< val: 1 next: john.linked.list.Node@33909752 prev: john.linked.list.Node@55f96302

main <<< val: 11 next: john.linked.list.Node@7852e922 prev: john.linked.list.Node@6d06d69c

main <<< val: 2 next: john.linked.list.Node@3d4eac69 prev: john.linked.list.Node@33909752

main <<< val: 33 next: john.linked.list.Node@42a57993 prev: john.linked.list.Node@7852e922

main <<< val: 34 next: john.linked.list.Node@70dea4e prev: john.linked.list.Node@3d4eac69

main <<< val: 4 next: john.linked.list.Node@5c647e05 prev: john.linked.list.Node@42a57993

main <<< val: 5 next: john.linked.list.Node@75b84c92 prev: john.linked.list.Node@70dea4e

main <<< val: 55 next: john.linked.list.Node@6bc7c054 prev: john.linked.list.Node@5c647e05

main <<< val: 66 next: null prev: john.linked.list.Node@75b84c92

main << val: 66 next: null prev: john.linked.list.Node@75b84c92

main << val: 55 next: john.linked.list.Node@6bc7c054 prev: john.linked.list.Node@5c647e05

main << val: 5 next: john.linked.list.Node@75b84c92 prev: john.linked.list.Node@70dea4e

main << val: 4 next: john.linked.list.Node@5c647e05 prev: john.linked.list.Node@42a57993

main << val: 34 next: john.linked.list.Node@70dea4e prev: john.linked.list.Node@3d4eac69

main << val: 33 next: john.linked.list.Node@42a57993 prev: john.linked.list.Node@7852e922

main << val: 2 next: john.linked.list.Node@3d4eac69 prev: john.linked.list.Node@33909752

main << val: 11 next: john.linked.list.Node@7852e922 prev: john.linked.list.Node@6d06d69c

main << val: 1 next: john.linked.list.Node@33909752 prev: john.linked.list.Node@55f96302

main << val: 0 next: john.linked.list.Node@6d06d69c prev: null

main <<< dequeue: 0

main <<<   count: 9

main <<<    list: 1 11 2 33 34 4 5 55 66

main <<< dequeue: 1

main <<<   count: 8

main <<<    list: 11 2 33 34 4 5 55 66

main <<< dequeue: 11

main <<<   count: 7

main <<<    list: 2 33 34 4 5 55 66

main <<< dequeue: 2

main <<<   count: 6

main <<<    list: 33 34 4 5 55 66

main <<< dequeue: 33

main <<<   count: 5

main <<<    list: 34 4 5 55 66

main <<< dequeue: 34

main <<<   count: 4

main <<<    list: 4 5 55 66

main <<< dequeue: 4

main <<<   count: 3

main <<<    list: 5 55 66

main <<< dequeue: 5

main <<<   count: 2

main <<<    list: 55 66

main <<< dequeue: 55

main <<<   count: 1

main <<<    list: 66

main <<< dequeue: 66

main <<<   count: 0

main <<<    list:

main <<<  count: 1

main <<<   list: 1

main <<<  count: 2

main <<<   list: 2 1

main <<<  count: 3

main <<<   list: 3 2 1

main <<<  count: 4

main <<<   list: 4 3 2 1

main <<<  count: 5

main <<<   list: 5 4 3 2 1

main <<<  count: 6

main <<<   list: 6 5 4 3 2 1

main <<<  count: 7

main <<<   list: 7 6 5 4 3 2 1

main <<< dequeue: 7

main <<<   count: 6

main <<<    list: 6 5 4 3 2 1

main <<< dequeue: 6

main <<<   count: 5

main <<<    list: 5 4 3 2 1

main <<< dequeue: 5

main <<<   count: 4

main <<<    list: 4 3 2 1

main <<< dequeue: 4

main <<<   count: 3

main <<<    list: 3 2 1

main <<< dequeue: 3

main <<<   count: 2

main <<<    list: 2 1

main <<< dequeue: 2

main <<<   count: 1

main <<<    list: 1

main <<< dequeue: 1

main <<<   count: 0

main <<<    list:

DoubleLinkList <<< constructor

main <<< w: name: 1 id: 1

main <<< w: name: 4 id: 2

main <<< w: name: 9 id: 3

main <<< widgets: name: 1 id: 1 name: 4 id: 2 name: 9 id: 3

main <<< w: name: widget_c id: -3

main <<< w: name: widget_b id: -2

main <<< w: name: widget_a id: -1

main <<< w: name: 1 id: 1

main <<< w: name: 4 id: 2

main <<< w: name: 9 id: 3

main <<< widgets: name: widget_c id: -3 name: widget_b id: -2 name: widget_a id: -1 name: 1 id: 1 name: 4 id: 2 name: 9 id: 3

Following is the test code that generated the output captured in the console:

package john.linked.list;

public class Solution {

/**

* Test code

*/

public static void main(String[] args) {

// **** constant(s) ****

final int MAX_COUNT = 7;

// **** instantiate a list of integers ****

//            SingleLinkList<Integer> list = new SingleLinkList<Integer>(MAX_COUNT * 2);

DoubleLinkList<Integer> list = new DoubleLinkList<Integer>(MAX_COUNT * 2);

// **** insert into list ****

Node<Integer> iNode = null;

for (int i = 0; i < MAX_COUNT; i++) {

iNode = list.enqueue(i);

System.out.println(“main <<< iNode: ” + iNode.genString());

}

System.out.println();

// **** string with list contents ****

System.out.println(“main <<< count: ” + list.getCount());

System.out.println(“main <<<  list: ” + list.toString());

System.out.println();

// **** peek into the queue ****

System.out.println(“main <<< peekHead: ” + list.peekHead());

System.out.println(“main <<< peekTail: ” + list.peekTail());

System.out.println();

// **** delete element(s) ****

boolean found = list.find(0);

System.out.println(“main <<<      find(0): ” + found);

System.out.println(“main <<<    delete(0): ” + list.delete(0));

System.out.println(“main <<<        count: ” + list.getCount());

System.out.println(“main <<<         list: ” + list.toString());

found = list.find(6);

System.out.println(“main <<<      find(6): ” + found);

System.out.println(“main <<<    delete(6): ” + list.delete(6));

System.out.println(“main <<<        count: ” + list.getCount());

System.out.println(“main <<<         list: ” + list.toString());

found = list.find(3);

System.out.println(“main <<<      find(3): ” + found);

System.out.println(“main <<<    delete(3): ” + list.delete(3));

System.out.println(“main <<<        count: ” + list.getCount());

System.out.println(“main <<<         list: ” + list.toString());

found = list.find(9999);

System.out.println(“main <<<   find(9999): ” + found);

if (found)

System.out.println(“main <<< delete(9999): ” + list.delete(9999));

// **** get element count ****

System.out.println(“main <<<        count: ” + list.getCount());

System.out.println(“main <<<         list: ” + list.toString());

System.out.println();

// **** insert AFTER ****

System.out.println(“main <<< isFull: ” + list.isFull());

list.insertAfter(1, 11);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

System.out.println(“main <<< isFull: ” + list.isFull());

list.insertAfter(2, 33);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

System.out.println(“main <<< isFull: ” + list.isFull());

list.insertAfter(5, 66);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

System.out.println();

// **** insert BEFORE ****

System.out.println(“main <<< isFull: ” + list.isFull());

list.insertBefore(1, 0);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

System.out.println(“main <<< isFull: ” + list.isFull());

list.insertBefore(66, 55);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

System.out.println(“main <<< isFull: ” + list.isFull());

list.insertBefore(4, 34);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

System.out.println();

// **** manually traverse list using next ****

for (Node<Integer> n = list.head; n != null; n = n.next) {

System.out.println(“main <<< ” + n.genString());

}

System.out.println();

// **** manually traverse list using prev ****

for (Node<Integer> p = list.tail; p != null; p = p.prev) {

System.out.println(“main << ” + p.genString());

}

System.out.println();

// **** dequeue ****

while (!list.isEmpty()) {

System.out.println(“main <<< dequeue: ” + list.dequeue());

System.out.println(“main <<<   count: ” + list.getCount());

System.out.println(“main <<<    list: ” + list.toString());

}

System.out.println();

// **** push ****

for (int i = 1; i <= MAX_COUNT; i++) {

list.push(i);

System.out.println(“main <<<  count: ” + list.getCount());

System.out.println(“main <<<   list: ” + list.toString());

}

System.out.println();

// **** dequeue ****

while (!list.isEmpty()) {

System.out.println(“main <<< dequeue: ” + list.dequeue());

System.out.println(“main <<<   count: ” + list.getCount());

System.out.println(“main <<<    list: ” + list.toString());

}

System.out.println();

// **** list of widgets ****

//            SingleLinkList<Widget> widgets = new SingleLinkList<Widget>(MAX_COUNT);

DoubleLinkList<Widget> widgets = new DoubleLinkList<Widget>(MAX_COUNT);

// **** add some widgets to the list ****

Node<Widget> wNode = null;

for (int i = 1; i <= 3; i++) {

Widget widget = new Widget(Integer.toString(i * i), i);

wNode = widgets.enqueue(widget);

}

// **** traverse list of widgets ****

for (Node<Widget> w = widgets.head; w != null; w = w.next) {

System.out.println(“main <<< w: ” + w.val.toString());

}

// **** display list of widgets ****

System.out.println(“main <<< widgets: ” + widgets.toString());

System.out.println();

// **** push new widgets before the head in the list ****

wNode = widgets.push(new Widget(“widget_a”, -1));

wNode = widgets.push(new Widget(“widget_b”, -2));

wNode = widgets.push(new Widget(“widget_c”, -3));

// **** traverse list of widgets ****

for (Node<Widget> w = widgets.head; w != null; w = w.next) {

System.out.println(“main <<< w: ” + w.val.toString());

}

// **** display list of widgets ****

System.out.println(“main <<< widgets: ” + widgets.toString());

}

}

Following is the code for the DoubleLinkList class:

package john.linked.list;

public class DoubleLinkList <T> {

// **** constants ****

final int MAX_NODES  = 8;

// **** members ****

Node<T>       head;

Node<T>       tail;

int           count;

int    maxCount;

/**

* Default constructor.

*/

public DoubleLinkList() {

System.out.println(“DoubleLinkList <<< constructor”);

// **** set members ****

this.head            = null;

this.tail            = null;

this.count           = 0;

this.maxCount = 0;

}

/**

* Constructor.

*/

public DoubleLinkList(int maxCount) {

System.out.println(“DoubleLinkList <<< constructor”);

// **** verify argument ****

if (maxCount < 0) {

throw new IllegalArgumentException(“DoubleLinkList <<< unexpected maxCount: ” + this.maxCount);

}

// **** set members ****

this.head            = null;

this.tail            = null;

this.count           = 0;

this.maxCount        = maxCount;

}

/**

* ENQUEUE a new element after the TAIL of the queue.

*/

public Node<T> enqueue(T val) {

// **** check if list is full ****

if ((this.maxCount != 0) && (this.count >= this.maxCount)) {

throw new ArrayStoreException(“enqueue <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);

}

// **** create a new node ****

Node<T> node = new Node<T>(val);

// **** insert node into empty queue ****

if (this.head == null) {

this.head = node;

this.tail = node;

this.count++;

}

// **** append node at the tail of the queue ****

else {

// **** current node points to previous tail node ****

node.prev            = this.tail;

// **** previous tail node points to new node ****

this.tail.next       = node;

// **** update queue fields ****

this.tail            = node;

this.count++;

}

// **** ****

return node;

}

/**

* Build string with elements in the list.

*/

public String toString() {

StringBuilder str = new StringBuilder();

// **** traverse list ****

for (Node<T> p = this.head; p != null; p = p.next) {

str.append(p.val.toString() + ” “);

}

// **** return string ****

return str.toString();

}

/**

* Peek HEAD of queue.

*/

public T peekHead() {

// **** check if queue is empty ****

if (count == 0) {

throw new IllegalArgumentException(“peekHead <<< unexpected count: ” + count);

}

// **** return value at head of queue ****

return (T)this.head.val;

}

/**

* Peek TAIL of queue.

*/

public T peekTail() {

// **** check if queue is empty ****

if (count == 0) {

throw new IllegalArgumentException(“peekTail <<< unexpected count: ” + count);

}

// **** return value at tail of queue ****

return (T)this.tail.val;

}

/**

* FIND element in queue.

*/

public boolean find(T val) {

// **** traverse queue ****

for (Node<T> p = this.head; p != null; p = p.next) {

if (p.val == val) {

return true;

}

}

// **** value not found ****

return false;

}

/**

* DELETE value from the queue.

*/

public T delete(T val) {

for (Node<T> p = this.head; p != null; p = p.next) {

// **** check if we need to delete this node ****

if (p.val == val) {

// **** delete head ****

if (this.head == p) {

this.head     = p.next;

p.next.prev = null;

}

// **** delete tail ****

else if(this.tail == p) {

this.tail     = p.prev;

p.prev.next = null;

}

// **** delete in between ****

else {

p.next.prev = p.prev;

p.prev.next = p.next;

}

// **** decrement count ****

this.count–;

// **** return value being deleted ****

return (T)p.val;

}

}

// **** ****

throw new IllegalArgumentException(“delete <<< val: ” + val + ” NOT in list”);

}

/**

* @return the count

*/

public int getCount() {

return this.count;

}

/**

* INSERT value AFTER specified one.

*/

public void insertAfter(T after, T val) {

// **** check if list is full ****

if ((this.maxCount != 0) && (this.count >= this.maxCount)) {

throw new ArrayStoreException(“insertAfter <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);

}

// **** inserting after tail ****

if (after == this.tail.val) {

enqueue(val);

return;

}

// **** ****

for (Node<T> p = this.head; p != null; p = p.next) {

if (p.val == after) {

Node<T> node = new Node<T>(val);

node.next            = p.next;

node.prev            = p;

p.next.prev   = node;

p.next                     = node;

this.count++;

return;

}

}

}

/**

* INSERT value BEFORE specified one.

*/

public void insertBefore(T before, T val) {

// **** check if list is full ****

if ((this.maxCount != 0) && (this.count >= this.maxCount)) {

throw new ArrayStoreException(“insertBefore <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);

}

// **** insert before head ****

if (head.val == before) {

Node<T> node = new Node<T>(val);

node.next            = this.head;

node.prev            = null;

this.head.prev       = node;

this.head            = node;

this.count++;

return;

}

// **** insert between ends ****

for (Node<T> p = this.head; p != null; p = p.next) {

if (p.val == before) {

Node<T> node = new Node<T>(val);

node.next            = p;

node.prev            = p.prev;

p.prev.next   = node;

p.prev               = node;

this.count++;

return;

}

}

}

/**

* Determine if the queue is EMPTY.

*/

public boolean isEmpty() {

return (this.count <= 0);

}

/**

* DEQUEUE a single element located at the HEAD of the queue.

*/

public T dequeue() {

// **** check if the queue is empty ****

if (this.head == null) {

return null;

}

// **** get value from head node ****

T val = this.head.val;

// **** decrement the queue count ****

this.count–;

// **** update fields in the queue ****

if (this.count == 0) {

this.head                  = null;

this.tail                  = null;

} else {

this.head.next.prev = null;

this.head                  = this.head.next;

}

// **** return the value removed from the queue ****

return val;

}

/**

* Determine if list is full.

*/

public boolean isFull() {

if (this.maxCount == 0) {

return false;

} else {

return (this.count >= this.maxCount);

}

}

/**

* PUSH element at HEAD of queue.

* Equivalent to push on a stack.

*/

public Node<T> push(T val) {

// **** check if list is full ****

if ((this.maxCount != 0) && (this.count >= this.maxCount)) {

throw new ArrayStoreException(“push <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);

}

// **** create a new node ****

Node<T> node = new Node<T>(val);

// **** insert node into empty queue ****

if (this.head == null) {

this.head = node;

this.tail = node;

this.count++;

}

// **** push node at head of queue ****

else {

// **** update node fields ****

node.next = this.head;

// **** update previous head field ****

this.head.prev = node;

// **** update queue fields ****

this.head = node;

this.count++;

}

// **** ****

return node;

}

}

On a following post I will develop the two equivalent classes for the linked lists. After they are tested I will then move to the implementation of the LFU Cache in C / C++.

If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *