%%% the module implement the LRU cache algorithm
%%% author cheng <litaocheng@gmail.com>
-module(lru_cache).
-author('<litaocheng@gmail.com>').
-vsn('0.1').

-export([new/1, get/2, insert/3, insert/4, size/1, max/1, hitrate/1, to_list/1]).
-export([test/0, test_1/0]).

-define(replaceFactor, 0.75).	%% the relacement factor, 
								%% when the (items number)/(max number) >= replaceFactor, the replacement occur
-record(item, {
				key,		%% the key
				expabs,		%% absolute expriation
				exprel,		%% relative expriation( sec )				
				lastaccess  %% the last accessed time
				}).		

-record(cache, {
				max,		%% max size
				repsize,	%% replacement size
				size = 0,	%% cureent size
				hits = 0,	%% hit count
				misses = 0,	%% miss count
				data,		%% use gb_trees save the key-value data
				items,      %% items list
				lastaccess,	%% the cache last accessed time
				callback = none	%% the callback fun when a element removed
				}).
				 
%% @type Cache() = #cache{}
%% @type key() = term()
%% @type value() = term()
%% @type item() = #item{}

%% @spec new(Max::integer()) -> Cache()
%% @doc creat a new cache which has the Max size element.
new(Max) when is_integer(Max) andalso Max > 0 ->
	#cache{ max = Max
	        , repsize = round(Max*?replaceFactor)
			, data = gb_trees:empty()
			, items = []
			, lastaccess = stamp()
			}.

%% @spec get(Key::key(), Cache::cache()) ->	{key, none, cache()} | {value, value(), cache()}
%% @doc get the value from the cache
get(Key, Cache) ->
    % check if the key exist
	case gb_trees:lookup(Key, Cache#cache.data) of
	    {value, Value} ->
			case lists:keysearch(Key, #item.key, Cache#cache.items) of
				{value, Item = #item{}} ->
					case is_expried(Item) of
						true ->	% expried
							% remove the item
							Cache2 = remove(Key, Cache),
							{key, none, Cache2};
						false ->					
							Item2 = Item#item{lastaccess = stamp()},
							%io:format("item2:~p~n", [Item2]),
							Items2 = lists:keyreplace(Key, #item.key, Cache#cache.items, Item2),
							Hits = Cache#cache.hits + 1,
							{value, Value, Cache#cache{hits = Hits, items=Items2}}
					end
			end;
		none ->
		    Miss = Cache#cache.misses + 1,
			{key, none, Cache#cache{misses=Miss}}
	end.

%% @spec insert(Key::key(), Value::term(), Cache::cache()) -> Cache()
%% @doc insert a new key value to cache
insert(Key, Value, Cache) ->
	Item = #item{key=Key},
	insert1(Key, Value, Item, Cache).

%% @spec insert(Key::key(), Value::term(), Ops::list(), Cache::cache()) -> Cache()
%% @doc insert a new key value to cache
insert(Key, Value, Ops, Cache) ->
	Item = parse_options(Ops),
	Item2 = Item#item{key=Key},
	insert1(Key, Value, Item2, Cache).

%% @spec remove(Key::key(), Cache::cache()) -> Cache()
%% @doc remove a key from cache
remove(Key, Cache) ->
    Items2 = lists:keydelete(Key, #item.key, Cache#cache.items),
	Callback = Cache#cache.callback,
	if 
	    Callback =:= none ->
		    Value = gb_trees:get(Key),
		    Callback(Key, Value);
		true ->	    	
		    ok
	end,
	Data2 = gb_trees:delete(Key, Cache#cache.data),
	Size2 = Cache#cache.size - 1,
	Cache#cache{size = Size2, data = Data2, items = Items2}.
		    				    

%% @spec size(Cache::cache()) -> integer()
%% @doc return the keys count in cache
size(Cache) ->
	Cache#cache.size.

%% @spec max(Cache::cache()) -> integer()
%% @doc return the max keys count in cache
max(Cache) ->
	Cache#cache.max.

%% @spec hitrate(Cache:cache()) -> float()
%% @doc return hit rate of cache
hitrate(Cache = #cache{}) ->
    Cache#cache.hits / (Cache#cache.hits + Cache#cache.misses).

%% @spec to_list(Cache::cache()) -> list()
%% @doc transform the cache items to list, just include the key and value
to_list(Cache) ->	
	gb_trees:to_list(Cache#cache.data).

%%
%%%internal
%%
insert1(Key, Value, Item = #item{}, Cache) ->
    %io:format("insert1: ~p~n", [Item]),
	Cache2 =
	if
		Cache#cache.size > 0 andalso Cache#cache.size =:= Cache#cache.max -> % has the max cache items
			replacement(Cache);
		true ->
			Cache
	end,

    % insert key value to gb_trees
	try gb_trees:insert(Key, Value, Cache2#cache.data) of
	    Data2 ->
		    Item2 = Item#item{lastaccess = stamp()},
		    Items2 = [Item2 | Cache2#cache.items],
		    S2 = Cache2#cache.size + 1,
			Cache#cache{size = S2, data = Data2, items = Items2, lastaccess = stamp()}
    catch
        error:{key_exists, _} ->
		    % update the item
			update_item(Key, Cache)
    end.

%% update existed item
update_item(Key, Cache) ->
    {value, Item} = lists:keysearch(Key, #item.key, Cache#cache.items),
	Item2 = Item#item{lastaccess = stamp()},
    Items2 = lists:keyreplace(Key, #item.key, Cache#cache.items, Item2),
	Cache#cache{items = Items2, lastaccess = stamp()}.

%% @doc parse the item options
parse_options(Ops) ->
	parse_options(Ops, #item{}).	

parse_options([], Item) ->
	Item;
parse_options([{expabs, V} | T], Item) ->
	parse_options(T, Item#item{expabs = V});
parse_options([{exprel, V} | T], Item) ->
	parse_options(T, Item#item{exprel = V}).

%% @doc decide if the item shold be expried based on its expriation options
is_expried(#item{expabs = undefined, exprel = undefined}) ->
	false;
is_expried(#item{expabs = E}) when E =/= undefined ->
	Now = stamp(),
	if
		E =< Now ->
			true;
		true ->
			false
	end;
is_expried(Item = #item{exprel = E}) when E =/= undefined ->
	NowSecs = datetime_to_seconds(stamp()),
	LastAccess = datetime_to_seconds(Item#item.lastaccess),
	if
		NowSecs - LastAccess >= E ->
			true;
		true ->
			false
	end.

%% replacement
replacement(Cache) ->
    % first remove the expired items
    Cache2 = remove_expired_items(Cache),
    S = lru_cache:size(Cache2),
    if
        S =< Cache2#cache.repsize ->
            Cache2;
        true ->
            replacement2(Cache2)			
    end.	

%% remove the expired items in cache
remove_expired_items(Cache) ->
    FunValid = fun(Elem) -> not is_expried(Elem) end,
    FunDel = fun(Elem = #item{key = Key}, Acc) -> 
	            case is_expried(Elem) of 
				    true ->
	    	            %io:format("delete: ~p, Tree:~p\n", [Key, Acc]),
					    gb_trees:delete(Key, Acc);
					false ->
					    Acc
				end
			end,
	{Items2, Data2} = filterfold(FunValid, FunDel, Cache#cache.data, Cache#cache.items),
	Cache#cache{size=length(Items2), data = Data2, items=Items2}.

%% remove the least recently items
replacement2(Cache = #cache{size=Size, repsize=RepSize, data=Data, items=Items}) ->
	Removed = Size - RepSize,
	if 
		Removed =< 0 ->
			Cache;
		true ->
			F = fun(Item1, Item2) ->
					Item1#item.lastaccess < Item2#item.lastaccess
				end,
			%io:format("List:~p~n", [Items]),
			Items2 = lists:sort(F, Items),
			%io:format("sorted:~p~n", [Items2]),
			{Items3, Data3} = remove_items(Removed, Items2, Data),
			%io:format("removed~n"),
			Cache#cache{size = RepSize, data = Data3, items = Items3}
	end.

%% remove the first N items in list and in gb_trees
remove_items(0, L, Data) ->
	{L, Data};
remove_items(_N, [], Data) ->
	{[], Data};
remove_items(N, [H = #item{key=Key}|T], Data) ->
    Data2 = gb_trees:delete(Key, Data),
	remove_items(N - 1, T, Data2).

%% lists method, combine filter and foldl
filterfold(PredF, PredA, Acc, List) when is_function(PredF, 1) andalso is_function(PredA, 2) ->
    filterfold(PredF, PredA, Acc, [], List).

filterfold(_PredF, _PredA, Acc, ListF, []) ->
    {lists:reverse(ListF), Acc};
filterfold(PredF, PredA, Acc, ListF, [E|T]) ->
    Acc2 = PredA(E, Acc),
    case PredF(E) of
        true ->
            filterfold(PredF, PredA, Acc2, [E | ListF], T);
	false ->
            filterfold(PredF, PredA, Acc2, ListF, T)   
    end.

stamp() ->
	calendar:universal_time().

%% datetime to seconds
datetime_to_seconds({Date, Time}) ->
	Days = calendar:date_to_gregorian_days(Date),
	Days * 86400 + calendar:time_to_seconds(Time).

test() ->
	Cache = new(5),
	5 = max(Cache),
	{key, none, Cache311} = lru_cache:get(1, Cache),
	Cache2 = insert(1, "1", Cache311),
	{value, "1", Cache111} = lru_cache:get(1, Cache2),
	Cache2 = insert(1, "1", Cache311),
	{value, "1", Cache111} = lru_cache:get(1, Cache2),
	Cache3 = lru_cache:insert(2, "2", Cache111),
	Cache4 = lru_cache:insert(3, "3", Cache3),
	Cache5 = lru_cache:insert(4, "4", Cache4),
	timer:sleep(1000),
	Cache6 = lru_cache:insert(5, "5", Cache5),
	[{1,"1"},{2,"2"},{3,"3"},{4,"4"},{5,"5"}] = lru_cache:to_list(Cache6),
	Cache7 = lru_cache:insert(6, "6", Cache6),
	[{2,"2"},{3,"3"},{4,"4"},{5,"5"}, {6, "6"}] = lru_cache:to_list(Cache7),
	Cache8 = lru_cache:insert(7, "7", [{exprel, 1}], Cache7),
	timer:sleep(1000),
	Cache9 = lru_cache:insert(8, "8", Cache8),
	io:format("cache:~p~n", [lru_cache:to_list(Cache9)]),
	{value, "3", Cache22}  = lru_cache:get(3, Cache9),
	Cache10 = lru_cache:insert(9, "9", Cache22),
	Cache11 = lru_cache:insert(10, "10", Cache10),
	timer:sleep(1000),
	{value, "3", Cache221}  = lru_cache:get(3, Cache11),
	Cache12 = lru_cache:insert(11, "11", Cache221),
	Cache13 = lru_cache:insert(12, "12", Cache12),
	io:format("cache:~p~n", [lru_cache:to_list(Cache13)]),
	P = Cache13#cache.hits / (Cache13#cache.hits + Cache13#cache.misses),
	io:format("cache: hits:~p misses:~p percent:~p~n", [Cache13#cache.hits, Cache13#cache.misses, P]),
	ok.

test_1() ->
    statistics(runtime),
	statistics(wall_clock),
	Cache = new(1024*32),
	Cache2 = add_key(1024*64, Cache),
	{_, Time1} = statistics(runtime),
	{_, Time2} = statistics(wall_clock),
	U1 = Time1,
	U2 = Time2,
	io:format("cache: hits:~p misses:~p~ntime=~p~n", [Cache2#cache.hits, Cache2#cache.misses, {U1, U2}]),
	ok.
	%lru_cache:to_list(Cache2).

add_key(0, Cache) ->
	Cache;
add_key(N, Cache) ->
	Cache2 = lru_cache:insert(N, integer_to_list(N), Cache),
	add_key(N-1, Cache2).