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
|
signature MISC = sig
val inputLine: TextIO.instream -> string option
val sequenceFromRead: (TextIO.instream -> 'a option) -> TextIO.instream -> 'a Sequence.t
val sequenceLines: TextIO.instream -> string Sequence.t
val sortedDirectoryNoPrefix: string -> string list
val sortedDirectory: string -> string list
val substitute: (string * string) list -> string -> string option
val basenameWithoutExtension: string -> string
val split2: string -> (string * string) option
val longestCommonSubstring: string list -> string
end
structure Misc :> MISC = struct
fun |> (x, f) = f x
infix |>
fun \ f x y = f (x, y)
fun sequenceFromRead f ioc = Sequence.from (fn () => f ioc)
fun inputLine instream = case TextIO.inputLine instream of
NONE => NONE
| SOME x => SOME (String.substring (x, 0, size x - 1))
val sequenceLines = sequenceFromRead inputLine
fun sortedDirectoryNoPrefix d =
let
val h = OS.FileSys.openDir d
fun loop l =
case OS.FileSys.readDir h of
NONE => (
OS.FileSys.closeDir h
; ListMergeSort.sort (op >) l
) | SOME n => loop (
if String.sub (n, 0) = #"." then l
else n :: l
)
in
loop nil
end
fun sortedDirectory d =
map (\OS.Path.concat d) (sortedDirectoryNoPrefix d)
fun assoc list key =
case
List.find (fn (possibility, _) => possibility = key) list
of
NONE => NONE
| SOME (_, answer) => SOME answer
local
exception NotFound
in
fun substitute v s =
Substitution.substitute
(fn s => (case assoc v s of
NONE => raise NotFound
| SOME x => x
)) s
handle NotFound => NONE
end
fun basenameWithoutExtension s = OS.Path.base (OS.Path.file s)
local
fun index f (string, offset) =
let
val last = size string
fun loop i =
if i = last then ~1
else if f (String.sub (string, i)) then i
else loop (i + 1)
in
loop offset
end
in
val indexWhitespace = index Char.isSpace
val indexNonWhitespace = index (not o Char.isSpace)
end
fun split2 s =
let
val f1b = indexNonWhitespace (s, 0)
in
if f1b = ~1 then NONE
else let
val f1e = indexWhitespace (s, f1b + 1)
in
if f1e = ~1 then NONE
else let
val f2b = indexNonWhitespace (s, f1e + 1)
in
if f2b = ~1 then NONE
else let
val f2e = indexWhitespace (s, f2b + 1)
in
if f2e = ~1 then SOME (
substring (s, f1b, f1e - f1b)
, substring (s, f2b, size s - f2b)
) else if indexNonWhitespace (s, f2e + 1) = ~1 then
SOME (
substring (s, f1b, f1e - f1b)
, substring (s, f2b, f2e - f2b)
)
else NONE
end
end
end
end
fun longestCommonSubstring strings =
case
foldl (fn (a, b) => (case b of
NONE => SOME a
| SOME b => if size a < size b then SOME a else SOME b
)) NONE strings
of
NONE => ""
| SOME shortest => let
val minimumSize = size shortest
fun loop (size, offset) =
let
fun next () =
if size + offset = minimumSize then
loop (size - 1, 0)
else loop (size, offset + 1)
val sub = substring (shortest, offset, size)
in
if List.all (String.isSubstring sub) strings then sub
else next ()
end
in
loop (minimumSize, 0)
end
end
|
