1 /**
  2  * potree.js 
  3  * http://potree.org
  4  *
  5  * Copyright 2012, Markus Sch�tz
  6  * Licensed under the GPL Version 2 or later.
  7  * - http://potree.org/wp/?page_id=7
  8  * - http://www.gnu.org/licenses/gpl-3.0.html
  9  *
 10  */
 11 
 12 /**
 13  * 
 14  * @param node
 15  * @class an item in the lru list. 
 16  */
 17 function LRUItem(node){
 18 	this.previous = null;
 19 	this.next = null;
 20 	this.node = node;
 21 }
 22 
 23 /**
 24  * 
 25  * @class A doubly-linked-list of the least recently used elements.
 26  */
 27 function LRU(){
 28 	// the least recently used item
 29 	this.first = null;
 30 	// the most recently used item
 31 	this.last = null;
 32 	// a list of all items in the lru list
 33 	this.items = new Object();
 34 	this.elements = 0;
 35 	this.byteSize = 0;
 36 }
 37 
 38 /**
 39  * number of elements in the list
 40  * 
 41  * @returns {Number}
 42  */
 43 LRU.prototype.size = function(){
 44 	return this.elements;
 45 };
 46 
 47 LRU.prototype.contains = function(node){
 48 	return this.items[node.id] == null;
 49 }
 50 
 51 /**
 52  * makes node the most recently used item. if the list does not contain node, it will be added.
 53  * 
 54  * @param node
 55  */
 56 LRU.prototype.touch = function(node){
 57 	if(this.items[node.id] == null){
 58 		// add to list
 59 		var item = new LRUItem(node);
 60 		item.previous = this.last;
 61 		this.last = item;
 62 		if(item.previous != null){
 63 			item.previous.next = item;
 64 		}
 65 		
 66 		this.items[node.id] = item;
 67 		this.elements++;
 68 		
 69 		if(this.first == null){
 70 			this.first = item;
 71 		}
 72 		this.byteSize += node.sizeInBytes();
 73 	}else{
 74 		// update in list
 75 		var item = this.items[node.id];
 76 		if(item.previous == null){
 77 			// handle touch on first element
 78 			if(item.next != null){
 79 				this.first = item.next;
 80 				this.first.previous = null;
 81 				item.previous = this.last;
 82 				item.next = null;
 83 				this.last = item;
 84 				item.previous.next = item;
 85 			}
 86 		}else if(item.next == null){
 87 			// handle touch on last element
 88 		}else{
 89 			// handle touch on any other element
 90 			item.previous.next = item.next;
 91 			item.next.previous = item.previous;
 92 			item.previous = this.last;
 93 			item.next = null;
 94 			this.last = item;
 95 			item.previous.next = item;
 96 		}
 97 		
 98 		
 99 	}
100 };
101 
102 /**
103  * removes the least recently used item from the list and returns it. 
104  * if the list was empty, null will be returned.
105  */
106 LRU.prototype.removeLRUItem = function removeLRUItem(){
107 	if(this.first == null){
108 		return null;
109 	}
110 	var lru = this.first;
111 
112 	// if the lru list contains at least 2 items, the item after the least recently used elemnt will be the new lru item. 
113 	if(lru.next != null){
114 		this.first = lru.next;
115 		this.first.previous = null;
116 	}else{
117 		this.first = null;
118 		this.last = null;
119 	}
120 	
121 	delete this.items[lru.node.id];
122 	this.elements--;
123 	this.byteSize -= lru.node.sizeInBytes();
124 	
125 //	Logger.info("removed node: " + lru.node.id);
126 	return lru.node;
127 };
128 
129 LRU.prototype.getLRUItem = function(){
130 	if(this.first == null){
131 		return null;
132 	}
133 	var lru = this.first;
134 	
135 	return lru.node;
136 }
137 
138 LRU.prototype.toString = function(){
139 	var string = "{ ";
140 	var curr = this.first;
141 	while(curr != null){
142 		string += curr.node.id;
143 		if(curr.next != null){
144 			string += ", ";
145 		}
146 		curr = curr.next;
147 	}
148 	string += "}";
149 	string += "(" + this.size() + ")";
150 	return string;
151 };
152