学步园

-module(exam).
-compile(export_all).

%1杨辉三角
start(N) when is_integer(N) ->
        print(N,1,1).

%C表示行数
%LC表示C对应的list
print(N,1,_) ->
        io:format("~p~n",[[1]]),
        print(N,2,1);
print(N,2,_) ->
        io:format("~p~n",[[1,1]]),
        print(N,3,[1,1]);
%Lc_minus_1 表示C-1行的list
print(N,C,Lc_minus_1) ->
    if
        C =:= (N + 1) ->
            ok;
        true    ->
            LC = get_increment(C,Lc_minus_1,[1]),
            io:format("~p~n",[LC]),
            print(N,C+1,LC)
    end.

%L 是 N-1行 的列表
%Result结果是 N行 的列表
get_increment(N,L,Result) ->
    Len = length(Result), 
    if
        Len =:= N-1 -> [1|Result];
        true ->
            get_increment(N,L,[lists:nth(Len,L) + lists:nth(Len+1,L) | Result])
    end.


%2 选择排序
select_sort(L) ->
    select_sort_impl(L,[]).

select_sort_impl([],_) ->
    io:format("~n");
select_sort_impl(L,Result) ->
    {Pos,Value} = get_min(L),
    L_new = lists:sublist(L,Pos-1) ++ lists:sublist(L,Pos+1,length(L)-Pos+1),
    Result_new = Result ++ [Value],
    io:format("~p~n",[Result_new ++ L_new]),
    select_sort_impl(L_new,Result_new).

get_min([]) ->
    error;
get_min(L) ->
    %第一次取第一个元素为初始最小值
    get_min_impl(L,1,1,lists:nth(1,L)).

%获得list最小元素的{位置，值}
%Idx 表示遍历到当前list的第几个
get_min_impl([],_,Pos,Value) ->
    {Pos,Value};
get_min_impl(L,Idx,Pos,Value) ->
    [H|T] = L,
    if
        H < Value ->
            get_min_impl(T,Idx+1,Idx,H);
        true      ->
            get_min_impl(T,Idx+1,Pos,Value)
    end.

%3
%交集
insect(L1,L2) ->
    lists:sort(insect_impl(lists:sort(L1),lists:sort(L2),[])).

insect_impl(L1,L2,Result) ->
    if
        L1 =:= [];
        L2 =:= [] ->
            Result;
        true ->
            [H1|T1] = L1,
            [H2|T2] = L2,
            if
                H1 =:= H2 ->
                    insect_impl(T1,T2,[H1|Result]);
                H1 <   H2 ->
                    %pass H1
                    insect_impl(T1,L2,Result);
                true      ->
                    %pass H2
                    insect_impl(L1,T2,Result)
            end
    end.

%并集
union(L1,L2) ->
    lists:sort(union_impl(lists:sort(L1),lists:sort(L2),[])).
union_impl(L1,L2,Result) ->
    if
        L1 =:= [] ->
            [L2|Result];
        L2 =:= [] ->
            [L1|Result];
        true ->
            [H1|T1] = L1,
            [H2|T2] = L2,
            if
                H1 =:= H2 ->
                    insect_impl(T1,T2,[H1|Result]);
                true      ->
                    insect_impl(T1,T2,[H1|[H2|Result]])
            end
    end.

%4
start(Alg, CacheSize) ->
    case Alg of 
        lru ->
            lru(CacheSize);
        lfu ->
            lfu(CacheSize)
    end.

lru(CacheSize) ->
    {ok,S} = file:open("production-build00-2-4K.req",[read]),
    lru_impl(S,CacheSize,[]),
    file:close(S),
    ok.
    
lru_impl(S,CacheSize,Cache) ->
    R = file:read_line(S),
    if
        R == eof ->
            ok;
        true    ->
            {ok,Line_} = R,
            %删除\n
            Line = string:sub_string(Line_,1,length(Line_)-1),
            [_,_,Id] = string:tokens(Line," "),

            case lists:member(Id,Cache) of 
                true ->
                    Cache_new = Cache;
                false ->
                    Len = length(Cache),
                    if
                        Len < CacheSize ->
                            Cache_new = [Id|Cache];
                        true            ->
                            %lru
                            Cache_new = [Id|lists:sublist(Cache,CacheSize-1)]
                    end
            end,
            io:format("LRU Cache:~p~n",[Cache]),
            lru_impl(S,CacheSize,Cache_new)
   end.

lfu(CacheSize) ->
    {ok,S} = file:open("production-build00-2-4K.req",[read]),
    lfu_impl(S,CacheSize,[]),
    file:close(S),
    ok.

lfu_impl(S,CacheSize,Cache) ->
    R = file:read_line(S),
    if
        R == eof ->
            ok;
        true    ->
            {ok,Line_} = R,
            %删除\n
            Line = string:sub_string(Line_,1,length(Line_)-1),
            [_,_,Id] = string:tokens(Line," "),

            %tuple格式{id,count}
            Tuple = lists:keyfind(Id,1,Cache),
            if
                %不存在Id
                Tuple =:= false ->
                    Len = length(Cache),
                    if
                        Len < CacheSize ->
                            Cache_new = [{Id,1}|Cache];
                        true            ->
                            %lfu
                            %按count升序排列
                            [_|Cache_sorted_tail] = lists:keysort(2,Cache),
                            Cache_new = [{Id,1}|Cache_sorted_tail]
                    end;
                %存在id，count+1
                true ->
                     {_,Count} = Tuple,
                     Cache_new = lists:keystore(Id,1,Cache,{Id,Count+1})
            end,
            io:format("LFU Cache:~p~n",[Cache_new]),
            lfu_impl(S,CacheSize,Cache_new)
   end.