//an LFU cache

data CacheEntry {
	char key[]
	byte value[]
	int size

	int index
	int freq

	CacheEntry next
	CacheEntry prev

	CacheEntry ageNext
	CacheEntry agePrev
}

data CacheBucket {
	CacheEntry list
}

const int BUCKET_COUNT = 50
const int MAX_KEY_HASH = 10 //characters

const bool TRACE = true

component provides Cache requires io.Output out, data.IntUtil iu {

	CacheBucket buckets[]
	CacheEntry ageList
	CacheEntry ageListEnd
	Mutex lock = new Mutex()

	int maxSize
	int curSize

	int hash(char key[])
		{
		int result = key[0]
		for (int i = 0; i < key.arrayLength && i < MAX_KEY_HASH; i++)
			{
			result = result * key[i]
			}
		
		return result % BUCKET_COUNT
		}

	Cache:Cache(int max)
		{
		maxSize = max
		buckets = new CacheBucket[BUCKET_COUNT]
		for (int i = 0; i < buckets.arrayLength; i++)
			{
			buckets[i] = new CacheBucket()
			}
		}
	
	void Cache:setSize(int max)
		{
		maxSize = max
		evict(curSize)
		}
	
	CacheEntry find(char key[])
		{
		CacheEntry w = buckets[hash(key)].list

		while (w != null)
			{
			if (w.key == key)
				{
				return w
				}
			
			w = w.next
			}
		
		return null
		}
	
	void deleteItem(CacheEntry c)
		{
		curSize -= c.size

		if (ageList === c)
			{
			ageList = c.ageNext
			if (ageList != null)
				ageList.agePrev = null
				else
				ageListEnd = null
			}
			else if (ageListEnd === c)
			{
			ageListEnd = c.agePrev
			if (ageListEnd != null)
				ageListEnd.ageNext = null
				else
				ageList = null
			}
			else
			{
			c.agePrev.ageNext = c.ageNext
			c.ageNext.agePrev = c.agePrev
			}
		
		c.ageNext = null
		c.agePrev = null

		if (buckets[c.index].list === c)
			{
			buckets[c.index].list = c.next
			if (buckets[c.index].list != null)
				{
				buckets[c.index].list.prev = null
				}
			}
			else
			{
			c.prev.next = c.next
			if (c.next != null)
				{
				c.next.prev = c.prev
				}
			}
		
		c.next = null
		c.prev = null
		}
	
	void evict(int size)
		{
		while (size > maxSize)
			{
			CacheEntry c = ageListEnd

			if (TRACE) out.println("evi: $(c.key) with $(c.size) [total $(curSize-c.size) / $maxSize]")

			size -= c.size
			deleteItem(c)
			}
		}

	void Cache:put(char key[], byte value[])
		{
		int size = value.arrayLength
		mutex(lock)
			{
			if (size > maxSize) throw new Exception("item with key '$(key)' (size $size) is larger than maximum cache size ($maxSize)")
			
			//search for existing
			CacheEntry w = find(key)
			if (w != null)
				{
				deleteItem(w)
				}
			
			//eviction
			evict(curSize + size)

			//addition
			int index = hash(key)

			CacheEntry nce = new CacheEntry(key, value, size, index)

			CacheBucket bucket = buckets[index]
			nce.next = bucket.list
			if (bucket.list != null) bucket.list.prev = nce
			bucket.list = nce

			if (ageListEnd != null)
				{
				ageListEnd.ageNext = nce
				nce.agePrev = ageListEnd
				ageListEnd = nce
				}
				else
				{
				ageList = nce
				ageListEnd = nce
				}

			curSize += size

			if (TRACE) out.println("put: $(key) with $size [total $curSize / $maxSize]")
			}
		}
	
	void updateUse(CacheEntry w)
		{
		w.freq ++

		CacheEntry ceq = w.agePrev

		//move the item towards the front of the age list, if it has a higher frequency than anything before it
		if (ceq != null)
			{
			bool move = false

			while (ceq != null && ceq.freq < w.freq)
				{
				ceq = ceq.agePrev
				move = true
				}
			
			if (move)
				{
				//remove the item from its current position
				if (ageListEnd === w)
					{
					ageListEnd = w.agePrev
					ageListEnd.ageNext = null
					}
					else 
					{
					w.agePrev.ageNext = w.ageNext
					w.ageNext.agePrev = w.agePrev
					}
				
				w.ageNext = null
				w.agePrev = null

				//insert it into its new position
				if (ceq != null)
					{
					CacheEntry cnext = ceq.ageNext
					w.ageNext = cnext
					w.agePrev = ceq

					if (cnext != null) cnext.agePrev = w
					ceq.ageNext = w
					}
					else
					{
					w.ageNext = ageList
					ageList.agePrev = w
					ageList = w
					}
				}
			}
		}
	
	byte[] Cache:get(char key[])
		{
		mutex(lock)
			{
			CacheEntry w = find(key)

			if (w != null)
				{
				updateUse(w)
				return w.value
				}
			
			return null
			}
		}
	
	void Cache:delete(char key[])
		{
		mutex(lock)
			{
			CacheEntry w = find(key)
			if (w != null) deleteItem(w)
			}
		}
}