1 (* Copyright (C
) 1999-2006 Henry Cejtin
, Matthew Fluet
, Suresh
2 * Jagannathan
, and Stephen Weeks
.
4 * MLton is released under a BSD
-style license
.
5 * See the file MLton
-LICENSE for details
.
8 structure LinkedList
: LINKED_LIST
=
13 datatype 'a t
= T
of {elt
: 'a
,
14 next
: 'a t option ref
}
16 fun new elt
= T
{elt
= elt
,
19 fun cons (elt
, next
) = T
{elt
= elt
,
20 next
= ref (SOME next
)}
22 fun clearNext (T
{next
, ...}) = next
:= NONE
23 fun setNext (T
{next
, ...}, n
) = next
:= SOME n
27 fun loop (T
{elt
, next
}, ac
) =
33 | SOME n
=> loop (n
, ac
)
40 datatype 'a t
= T
of {first
: 'a Node
.t option ref
,
41 last
: 'a Node
.t option ref
}
43 fun invariant (T
{first
, last
}) =
44 case (!first
, !last
) of
46 |
(SOME _
, SOME (Node
.T
{next
, ...})) => not (isSome (!next
))
49 fun fold (T
{first
, ...}, ac
, f
) =
52 | SOME n
=> Node
.fold (n
, ac
, f
)
54 fun toList l
= rev (fold (l
, [], op ::))
56 fun layout layoutX l
= List.layout
layoutX (toList l
)
58 fun empty () = T
{first
= ref NONE
,
61 fun splice (T
{first
= f
, last
= l
}, T
{first
= f
', last
= l
'}): unit
=
64 |
(NONE
, _
) => (f
:= !f
'; l
:= !l
')
66 |
(SOME ln
, SOME f
'n
) =>
67 (Node
.setNext (ln
, f
'n
)
70 val ('a
, 'b
) unfoldr
: 'a
* ('a
-> ('b
* 'a
) option
) -> 'b t
=
77 fun loop (a
: 'a
, n
: 'b Node
.t
): 'b Node
.t
=
80 |
SOME (b
, a
) => loop (a
, Node
.cons (b
, n
))
81 val first
= loop (a
, last
)
83 T
{first
= ref (SOME first
),
84 last
= ref (SOME last
)}
87 val unfoldri
: int * 'a
* (int * 'a
-> 'b
* 'a
) -> 'b t
=
90 then Error
.bug
"LinkedList.unfoldri"
92 unfoldr ((n
- 1, a
), fn (i
, a
) =>
101 val ('a
, 'b
) unfold
: 'a
* ('a
-> ('b
* 'a
) option
) -> 'b t
=
107 val first
= Node
.new b
108 fun loop (a
: 'a
, n
: 'b Node
.t
): 'b Node
.t
=
114 val _
= Node
.setNext (n
, n
')
118 val last
= loop (a
, first
)
120 T
{first
= ref (SOME first
),
121 last
= ref (SOME last
)}
124 val unfoldi
: int * 'a
* (int * 'a
-> 'b
* 'a
) -> 'b t
=
127 then Error
.bug
"LinkedList.unfoldi"
129 unfold ((0, a
), fn (i
, a
) =>
133 val (b
, a
') = f (i
, a
)
135 SOME (b
, (i
+ 1, a
'))
138 fun reverse (ll
as T
{first
, last
}) =
141 else Out
.output (Out
.error
, "reverse 1\n")
145 |
SOME (n
as Node
.T
{next
, ...}) =>
150 val _
= Node
.clearNext n
151 fun loop (n
, n
' as Node
.T
{next
, ...}) =
154 val _
= next
:= SOME n
158 | SOME n
'' => loop (n
', n
'')
161 val _
= Ref
.swap (first
, last
)
167 else Out
.output (Out
.error
, "reverse 2\n"))
172 | x
:: l
=> SOME (x
, l
))