Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Page
Library
Module
Module type
Parameter
Class
Class type
Source
deque.ml
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
module Basic = struct type 'a t = { front: 'a list; rear: 'a list; } let empty: 'a t = {front = []; rear = [];} let push_front (e: 'a) (fifo: 'a t): 'a t = {fifo with front = e :: fifo.front} let push_rear (e: 'a) (fifo: 'a t): 'a t = {fifo with rear = e :: fifo.rear} let pop_front (fifo: 'a t): ('a * 'a t) option = match fifo.front with | hd :: front -> Some (hd, {fifo with front}) | [] -> match List.rev fifo.rear with | [] -> None | hd :: front -> Some (hd, {front; rear = []}) let prepend (fifo: 'a t) (lst: 'a list): 'a list = fifo.front @ List.rev_append fifo.rear lst end type 'a t = | Empty | Nonempty of 'a Basic.t * 'a let is_empty (f: 'a t): bool = match f with | Empty -> true | _ -> false let has_some (f: 'a t): bool = not (is_empty f) let empty: 'a t = Empty let push_front (e: 'a) (f: 'a t): 'a t = match f with | Empty -> Nonempty (Basic.empty, e) | Nonempty (lf, last) -> Nonempty (Basic.push_front e lf, last) let push_rear (e: 'a) (f: 'a t): 'a t = match f with | Empty -> Nonempty (Basic.empty, e) | Nonempty (lf, last) -> Nonempty (Basic.push_rear last lf, e) let pop_front (f: 'a t): ('a * 'a t) option = match f with | Empty -> None | Nonempty (lf, last) -> match Basic.pop_front lf with | None -> Some (last, empty) | Some (first, lf) -> Some (first, Nonempty (lf, last)) let update_first (f: 'a -> 'a) (fifo: 'a t): 'a t = match fifo with | Empty -> Empty | Nonempty (lf, last) -> match Basic.pop_front lf with | None -> Nonempty (lf, f last) | Some (first, lf) -> Nonempty (Basic.push_front (f first) lf, last) let update_last (f: 'a -> 'a) (fifo: 'a t): 'a t = match fifo with | Empty -> Empty | Nonempty (lf, last) -> Nonempty (lf, f last) let to_list (fifo: 'a t): 'a list = match fifo with | Empty -> [] | Nonempty (lf, last) -> Basic.prepend lf [last] (* ---------------------------------------------------------- *) (* Unit Tests *) (* ---------------------------------------------------------- *) let%test _ = to_list (empty |> push_rear 0 |> push_rear 1 |> push_rear 2) = [0; 1; 2] let%test _ = empty |> push_rear 0 |> pop_front = Some (0, empty) let%test _ = match empty |> push_rear 0 |> push_rear 1 |> update_first (fun _ -> 10) |> pop_front with | Some (10, fifo ) -> pop_front fifo = Some (1, empty) | _ -> false let%test _ = match empty |> push_rear 0 |> push_rear 1 |> update_last (fun _ -> 10) |> pop_front with | Some (0, fifo ) -> pop_front fifo = Some (10, empty) | _ -> false