lqueue.erl

%% The contents of this file are subject to the Mozilla Public License
%% Version 1.1 (the "License"); you may not use this file except in
%% compliance with the License. You may obtain a copy of the License
%% at http://www.mozilla.org/MPL/
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and
%% limitations under the License.
%%
%% The Original Code is RabbitMQ.
%%
%% The Initial Developer of the Original Code is GoPivotal, Inc.
%% Copyright (c) 2011-2014 GoPivotal, Inc.  All rights reserved.
%%

-module(lqueue).

%% lqueue implements a subset of Erlang's queue module. lqueues
%% maintain their own length, so lqueue:len/1
%% is an O(1) operation, in contrast with queue:len/1 which is O(n).

-export([new/0, is_empty/ 1 , len/1 , in/2, in_r/ 2 , out/1 , out_r/1, join/ 2 ,
         foldl/ 3 , foldr/3 , from_list/1, to_list/ 1 , peek/1 , peek_r/1]).

-define(QUEUE, queue).

-ifdef(use_specs).

-export_type([?MODULE/ 0 ]).

-opaque(?MODULE() :: {non_neg_integer(), ?QUEUE :?QUEUE ()}).
-type(value()     :: any()).
-type(result()    :: 'empty' | {'value', value()}).

-spec(new/ 0        :: () -> ?MODULE()).
-spec(is_empty/ 1   :: (?MODULE ()) -> boolean()).
-spec(len/ 1        :: (?MODULE()) -> non_neg_integer()).
-spec(in/ 2         :: (value(), ?MODULE()) -> ?MODULE ()).
-spec(in_r/ 2       :: (value(), ?MODULE()) -> ?MODULE ()).
-spec(out/ 1        :: (?MODULE()) -> {result(), ?MODULE ()}).
-spec(out_r/ 1      :: (?MODULE ()) -> {result(), ?MODULE ()}).
-spec(join/ 2       :: (?MODULE (), ?MODULE()) -> ?MODULE ()).
-spec(foldl/ 3      :: (fun ((value(), B) -> B), B, ?MODULE()) -> B ).
-spec(foldr/ 3      :: (fun ((value(), B) -> B), B, ?MODULE()) -> B ).
-spec(from_list/ 1 :: ([value()]) -> ?MODULE()).
-spec(to_list/ 1    :: (?MODULE ()) -> [value()]).
-spec(peek/ 1       :: (?MODULE ()) -> result()).
-spec(peek_r/ 1     :: (?MODULE ()) -> result()).

-endif.

%% 创建一个新的队列，实际用的是OTP系统提供的queue队列模块(RabbitMQ系统实现的优化:将队列的长度保存在内存中，其他操作跟queue队列一样)
%% 此处lqueue只是对queue队列实现了一层封装
new() -> {0, ?QUEUE:new()}.


%% 判断队列是否为空
is_empty({0, _Q}) -> true;
is_empty(_)       -> false.


%% 向队列中插入元素(从队列的尾部插入元素)
in(V, {L, Q}) -> {L + 1, ?QUEUE:in( V , Q )}.


%% 向队列中插入元素(从队列的头部插入元素)
in_r(V, {L, Q}) -> {L + 1, ?QUEUE:in_r( V , Q )}.


%% 从队列中取出元素(从队列的头部取出元素)
out({0, _Q} = Q) -> {empty, Q };
out({L,  Q })     -> {Result, Q1 } = ?QUEUE :out(Q),
                              { Result , {L - 1, Q1}}.


%% 从队列中取出元素(从队列的尾部取出元素)
out_r({0, _Q} = Q) -> {empty, Q };
out_r({L,  Q })     -> {Result, Q1 } = ?QUEUE :out_r(Q),
                                { Result , {L - 1, Q1}}.


%% 将Q1和Q2队列合并在一起
join({L1, Q1}, {L2, Q2}) -> {L1 + L2, ?QUEUE:join( Q1 , Q2 )}.


%% 将队列中的元素转化为列表
to_list({_L, Q}) -> ?QUEUE:to_list( Q ).


%% 将列表中的元素组装为一个队列
from_list(L) -> {length( L ), ?QUEUE :from_list(L)}.


%% 对队列中的元素进程foldl操作(从队列的头部取出元素)
foldl(Fun, Init, Q) ->
       case out(Q ) of
            {empty, _Q }      -> Init;
            {{value, V }, Q1 } -> foldl( Fun , Fun (V, Init), Q1)
       end .


%% 对队列中的元素进程foldl操作(从队列的尾部取出元素)
foldr(Fun, Init, Q) ->
       case out_r(Q ) of
            {empty, _Q }      -> Init;
            {{value, V }, Q1 } -> foldr( Fun , Fun (V, Init), Q1)
       end .


%% 拿到队列的长度
len({L, _Q}) -> L.


%% 拿到队列中头部的元素，但是不将该元素从队列中取出
peek({ 0, _Q}) -> empty;
peek({_L,  Q }) -> ?QUEUE:peek( Q ).


%% 拿到队列中尾部的元素，但是不将该元素从队列中取出
peek_r({ 0, _Q}) -> empty;
peek_r({_L,  Q }) -> ?QUEUE:peek_r( Q ).