/*
 * Copyright (C) 2019, Marc Strapetz <marc.strapetz@syntevo.com>
 * Copyright (C) 2019, Matthias Sohn <matthias.sohn@sap.com> and others
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Distribution License v. 1.0 which is available at
 * https://www.eclipse.org/org/documents/edl-v10.php.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 */
package org.eclipse.jgit.util;

import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import org.eclipse.jgit.annotations.NonNull;
import org.eclipse.jgit.internal.JGitText;

Simple limited size cache based on ConcurrentHashMap purging entries in LRU
order when reaching size limit
Type parameters:
<K> – 
           the type of keys maintained by this cache
<V> – 
           the type of mapped values
Since:
5.1.9/**
 * Simple limited size cache based on ConcurrentHashMap purging entries in LRU
 * order when reaching size limit
 *
 * @param <K>
 *            the type of keys maintained by this cache
 * @param <V>
 *            the type of mapped values
 *
 * @since 5.1.9
 */
public class SimpleLruCache<K, V> {

	private static class Entry<K, V> {

		private final K key;

		private final V value;

		// pseudo clock timestamp of the last access to this entry
		private volatile long lastAccessed;

		private long lastAccessedSorting;

		Entry(K key, V value, long lastAccessed) {
			this.key = key;
			this.value = value;
			this.lastAccessed = lastAccessed;
		}

		void copyAccessTime() {
			lastAccessedSorting = lastAccessed;
		}

		@SuppressWarnings("nls")
		@Override
		public String toString() {
			return "Entry [lastAccessed=" + lastAccessed + ", key=" + key
					+ ", value=" + value + "]";
		}
	}

	private Lock lock = new ReentrantLock();

	private Map<K, Entry<K,V>> map = new ConcurrentHashMap<>();

	private volatile int maximumSize;

	private int purgeSize;

	// pseudo clock to implement LRU order of access to entries
	private volatile long time = 0L;

	private static void checkPurgeFactor(float purgeFactor) {
		if (purgeFactor <= 0 || purgeFactor >= 1) {
			throw new IllegalArgumentException(
					MessageFormat.format(JGitText.get().invalidPurgeFactor,
							Float.valueOf(purgeFactor)));
		}
	}

	private static int purgeSize(int maxSize, float purgeFactor) {
		return (int) ((1 - purgeFactor) * maxSize);
	}

	
Create a new cache
Params:
maxSize – 
           maximum size of the cache, to reduce need for synchronization
           this is not a hard limit. The real size of the cache could be
           slightly above this maximum if multiple threads put new values
           concurrently
purgeFactor –  when the size of the map reaches maxSize the oldest entries will be purged to free up some space for new entries, purgeFactor is the fraction of maxSize to purge when this happens/**
	 * Create a new cache
	 *
	 * @param maxSize
	 *            maximum size of the cache, to reduce need for synchronization
	 *            this is not a hard limit. The real size of the cache could be
	 *            slightly above this maximum if multiple threads put new values
	 *            concurrently
	 * @param purgeFactor
	 *            when the size of the map reaches maxSize the oldest entries
	 *            will be purged to free up some space for new entries,
	 *            {@code purgeFactor} is the fraction of {@code maxSize} to
	 *            purge when this happens
	 */
	public SimpleLruCache(int maxSize, float purgeFactor) {
		checkPurgeFactor(purgeFactor);
		this.maximumSize = maxSize;
		this.purgeSize = purgeSize(maxSize, purgeFactor);
	}

	
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. 
 More formally, if this cache contains a mapping from a key k to a value v such that key.equals(k), then this method returns v; otherwise it returns null. (There can be at most one such mapping.) 
Params:
key – 
           the key
Throws:
NullPointerException – 
            if the specified key is null
Returns:
value mapped for this key, or null if no value is mapped/**
	 * Returns the value to which the specified key is mapped, or {@code null}
	 * if this map contains no mapping for the key.
	 *
	 * <p>
	 * More formally, if this cache contains a mapping from a key {@code k} to a
	 * value {@code v} such that {@code key.equals(k)}, then this method returns
	 * {@code v}; otherwise it returns {@code null}. (There can be at most one
	 * such mapping.)
	 *
	 * @param key
	 *            the key
	 *
	 * @throws NullPointerException
	 *             if the specified key is null
	 *
	 * @return value mapped for this key, or {@code null} if no value is mapped
	 */
	@SuppressWarnings("NonAtomicVolatileUpdate")
	public V get(Object key) {
		Entry<K, V> entry = map.get(key);
		if (entry != null) {
			entry.lastAccessed = tick();
			return entry.value;
		}
		return null;
	}

	
Maps the specified key to the specified value in this cache. Neither the
key nor the value can be null.
 The value can be retrieved by calling the get method with a key that is equal to the original key. 
Params:
key – 
           key with which the specified value is to be associated
value – 
           value to be associated with the specified key
Throws:
NullPointerException – 
            if the specified key or value is null
Returns:
the previous value associated with key, or null if there was no mapping for key/**
	 * Maps the specified key to the specified value in this cache. Neither the
	 * key nor the value can be null.
	 *
	 * <p>
	 * The value can be retrieved by calling the {@code get} method with a key
	 * that is equal to the original key.
	 *
	 * @param key
	 *            key with which the specified value is to be associated
	 * @param value
	 *            value to be associated with the specified key
	 * @return the previous value associated with {@code key}, or {@code null}
	 *         if there was no mapping for {@code key}
	 * @throws NullPointerException
	 *             if the specified key or value is null
	 */
	@SuppressWarnings("NonAtomicVolatileUpdate")
	public V put(@NonNull K key, @NonNull V value) {
		map.put(key, new Entry<>(key, value, tick()));
		if (map.size() > maximumSize) {
			purge();
		}
		return value;
	}

	@SuppressWarnings("NonAtomicVolatileUpdate")
	private long tick() {
		return ++time;
	}

	
Returns the current size of this cache
Returns:
the number of key-value mappings in this cache/**
	 * Returns the current size of this cache
	 *
	 * @return the number of key-value mappings in this cache
	 */
	public int size() {
		return map.size();
	}

	
Reconfigures the cache. If maxSize is reduced some entries will be purged. 
Params:
maxSize – 
           maximum size of the cache
purgeFactor –  when the size of the map reaches maxSize the oldest entries will be purged to free up some space for new entries, purgeFactor is the fraction of maxSize to purge when this happens/**
	 * Reconfigures the cache. If {@code maxSize} is reduced some entries will
	 * be purged.
	 *
	 * @param maxSize
	 *            maximum size of the cache
	 *
	 * @param purgeFactor
	 *            when the size of the map reaches maxSize the oldest entries
	 *            will be purged to free up some space for new entries,
	 *            {@code purgeFactor} is the fraction of {@code maxSize} to
	 *            purge when this happens
	 */
	public void configure(int maxSize, float purgeFactor) {
		lock.lock();
		try {
			checkPurgeFactor(purgeFactor);
			this.maximumSize = maxSize;
			this.purgeSize = purgeSize(maxSize, purgeFactor);
			if (map.size() >= maximumSize) {
				purge();
			}
		} finally {
			lock.unlock();
		}
	}

	private void purge() {
		// don't try to compete if another thread already has the lock
		if (lock.tryLock()) {
			try {
				List<Entry> entriesToPurge = new ArrayList<>(map.values());
				// copy access times to avoid other threads interfere with
				// sorting
				for (Entry e : entriesToPurge) {
					e.copyAccessTime();
				}
				Collections.sort(entriesToPurge,
						Comparator.comparingLong(o -> -o.lastAccessedSorting));
				for (int index = purgeSize; index < entriesToPurge
						.size(); index++) {
					map.remove(entriesToPurge.get(index).key);
				}
			} finally {
				lock.unlock();
			}
		}
	}
}