-
Notifications
You must be signed in to change notification settings - Fork 81
/
dlist.ml
79 lines (62 loc) · 1.39 KB
/
dlist.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
[@@@part "1"];;
(* file: dlist.ml *)
open Core_kernel
type 'a element =
{ value : 'a;
mutable next : 'a element option;
mutable prev : 'a element option
}
type 'a t = 'a element option ref
[@@@part "2"];;
let create () = ref None
let is_empty t = !t = None
let value elt = elt.value
let first t = !t
let next elt = elt.next
let prev elt = elt.prev
[@@@part "3"];;
let insert_first t value =
let new_elt = { prev = None; next = !t; value } in
begin match !t with
| Some old_first -> old_first.prev <- Some new_elt
| None -> ()
end;
t := Some new_elt;
new_elt
[@@@part "4"];;
let insert_after elt value =
let new_elt = { value; prev = Some elt; next = elt.next } in
begin match elt.next with
| Some old_next -> old_next.prev <- Some new_elt
| None -> ()
end;
elt.next <- Some new_elt;
new_elt
[@@@part "5"];;
let remove t elt =
let { prev; next; _ } = elt in
begin match prev with
| Some prev -> prev.next <- next
| None -> t := next
end;
begin match next with
| Some next -> next.prev <- prev;
| None -> ()
end;
elt.prev <- None;
elt.next <- None
[@@@part "6"];;
let iter t ~f =
let rec loop = function
| None -> ()
| Some el -> f (value el); loop (next el)
in
loop !t
let find_el t ~f =
let rec loop = function
| None -> None
| Some elt ->
if f (value elt) then Some elt
else loop (next elt)
in
loop !t