《プログラミングの基礎》はとても良い本です。
サンプルプログラムをReScriptで書いて、プログラミングの基礎とReScriptを学びます。
環境
- macOS Sonoma(バージョン 14.4.1)
- ReScript 11.1.0-rc.8
- @rescript/core 1.2.0
第23章
Heap.resi
type t<'a, 'b>
// 最小値を求める値が 'a 型で
// そのほかの付加情報が 'b 型であるヒープの型
exception Full
// insert したときにヒープが一杯だと raise される例外
exception Empty
// split_top したときにヒープが空だと raise される例外
let create : (int, 'a, 'b) => t<'a, 'b>
// 使い方：create size key value
// ヒープのサイズと 'a 型と 'b 型のダミーの値を受け取ったら
// 空のヒープを返す
type index_t
// ヒープの添字の型
let insert : (t<'a, 'b>, 'a, 'b) => (index_t, t<'a, 'b>)
// 使い方：insert heap key value
// ヒープに新しい要素を追加する
// これ以上、入らないときは Full を raise する
// ヒープは（破壊的に）書き変わる
let get : (t<'a, 'b>, index_t) => ('a, 'b)
// 使い方：get heap index
// ヒープの index 番目の要素を返す
// index が無効であれば Not_found を raise する
let set : (t<'a, 'b>, index_t, 'a, 'b) => t<'a, 'b>
// 使い方：set heap index key value
// ヒープの index 番目の値を更新したヒープを返す
// ヒープは（破壊的に）書き変わる
let split_top : t<'a, 'b> => (('a, 'b), t<'a, 'b>)
// 使い方：split_top heap
// 最小の値を持つものとそれを取り除いたヒープのペアを返す
// ヒープが空のときは Empty を raise する
// 最小の値を持つものの index は無効な値になる
// ヒープは（破壊的に）書き変わる
let length : t<'a, 'b> => int
// 使い方：length heap
// ヒープ中のデータの数を返す
Heap.res
// ヒープの添字の型。このモジュール内でしか変更はできない
type index_t = ref<int>
// 最小値を求める値が 'a 型でその他の付加情報が 'b 型であるヒープの型
type t<'a, 'b> = (ref<int>, array<(index_t, 'a, 'b)>)
// insert したときにヒープが一杯だと raise される例外
exception Full
// split_top したときにヒープが空だと raise される例外
exception Empty
// index_t 型を持つダミーの値
let example_index = ref(-1)
// 値が example_value と同じ型、付加情報が example_info と同じ型で
// 最大 max 個の要素を格納できるヒープを返す *)
let create = (max, example_value, example_info) =>
(ref(0), Array.make(~length=max, (example_index, example_value, example_info)))
// current_index と parent_index の要素を入れ換える
let swap = (array, current_index, parent_index) => {
let (index_ref_c, value_c, info_c) = Array.getUnsafe(array, current_index)
let (index_ref_p, value_p, info_p) = Array.getUnsafe(array, parent_index)
array[current_index] = (index_ref_p, value_p, info_p)
array[parent_index] = (index_ref_c, value_c, info_c)
index_ref_c := parent_index // 入れ換えにともなって index も付け変える
index_ref_p := current_index
()
}
// 下方向に向かってヒープの条件を満たすように要素の入れ換えを行う
let rec adjust_child = (num, array, current_index) =>
if current_index >= num {()}
else {
let (_, v, _) = Array.getUnsafe(array, current_index)
let child1_index = 2 * current_index + 1
let child2_index = child1_index + 1
if child1_index >= num {()}
else {
let (_, v1, _) = Array.getUnsafe(array, child1_index)
if child2_index >= num {
if v <= v1 {()}
else {
swap(array, current_index, child1_index)
adjust_child(num, array, child1_index)
}
}
else {
let (_, v2, _) = Array.getUnsafe(array, child2_index)
if v <= v1 && v <= v2 {()}
else if v1 < v2 {
swap(array, current_index, child1_index)
adjust_child(num, array, child1_index)
}
else {
swap(array, current_index, child2_index)
adjust_child(num, array, child2_index)
}
}
}
}
// 上方向に向かってヒープの条件を満たすように要素の入れ換えを行う
let rec adjust_parent = (array, current_index) =>
if current_index == 0 {()}
else {
let (_, value_c, _) = Array.getUnsafe(array, current_index)
let parent_index = (current_index - 1) / 2
let (_, value_p, _) = Array.getUnsafe(array, parent_index)
if value_c < value_p {
swap(array, current_index, parent_index)
adjust_parent(array, parent_index)
}
else {()}
}
// ヒープに新しい要素を追加する
// これ以上、入らないときは Full を raise する
// ヒープは（破壊的に）書き変わる
let insert = ((num_ref, array), v, info) =>
if num_ref.contents >= Array.length(array) {raise(Full)}
else {
let index = ref(num_ref.contents)
array[num_ref.contents] = (index, v, info)
adjust_parent(array, num_ref.contents)
num_ref := num_ref.contents + 1
(index, (num_ref, array))
}
// ヒープの !index_ref 番目の要素を返す
// index が無効であれば Not_found を raise する
let get = ((num_ref, array), index_ref) =>
if 0 <= index_ref.contents && index_ref.contents < num_ref.contents {
let (_, a, b) = Array.getUnsafe(array, index_ref.contents)
(a, b)
} else {raise(Not_found)}
// ヒープの !index_ref 番目の値を更新したヒープを返す
// ヒープは（破壊的に）書き変わる
let set = ((num_ref, array), index_ref, v, info) => {
let (_, v', _) = Array.getUnsafe(array, index_ref.contents)
array[index_ref.contents] = (index_ref, v, info)
if v < v' {adjust_parent(array, index_ref.contents)}
else {adjust_child(num_ref.contents, array, index_ref.contents)}
(num_ref, array)
}
// 最小の値を持つものとそれを取り除いたヒープのペアを返す
// 最小の値を持つものの index は無効な値になる
// ヒープが空のときは Empty を raise する
// ヒープは（破壊的に）書き変わる
let split_top = ((num_ref, array)) =>
if num_ref.contents == 0 {raise(Empty)}
else {
let (index_ref, v, info) = Array.getUnsafe(array, 0)
num_ref := num_ref.contents - 1 // 要素数をひとつ減らす
array[0] = Array.getUnsafe(array, num_ref.contents)
adjust_child(num_ref.contents, array, 0)
index_ref := -1 //取り出した先頭の要素の index_ref は無効にする
((v, info), (num_ref, array))
}
// ヒープ中のデータの数を返す
let length = ((num_ref, _)) => num_ref.contents
Ex23_2.res
// open Heap //Heap モジュールの定義
// 目的：受け取ったヒープの要素を小さい順に取り出してリストにして返す
// ここで lst はこれまでにヒープから取り出した要素のリスト
// extract_all_elements : ('a, unit) Heap.t -> 'a list -> 'a list
let rec extract_all_elements = (heap, lst) =>
try {
let ((a, ()), heap) = Heap.split_top(heap)
extract_all_elements(heap, list{a, ...lst})
} catch {
| Heap.Empty => lst
}
// 目的：受け取ったリストをヒープソートを使って大きい順に並べる
// heap_sort : 'a list -> 'a list
let heap_sort = (lst) => switch lst {
| list{} => list{}
| list{a, ..._} =>
let size = List.length(lst)
let heap =
Js.List.foldLeft(
(heap, x) => {
let (_, heap) = Heap.insert(heap, x, ())
heap
},
Heap.create(size, a, ()),
lst
)
extract_all_elements(heap, list{})
}
// テスト
Console.log(heap_sort(list{}) == list{})
Console.log(heap_sort(list{1}) == list{1})
Console.log(heap_sort(list{1, 2}) == list{2, 1})
Console.log(heap_sort(list{2, 1}) == list{2, 1})
Console.log(heap_sort(list{5, 3, 8, 1, 7, 4}) == list{8, 7, 5, 4, 3, 1})
Metro.res
type ekimei_t = {
kanji: string, // 漢字の駅名
kana: string, // 読み
romaji: string, // ローマ字
shozoku: string // 所属路線名
}
type ekikan_t = {
kiten: string, // 起点
shuten: string, // 終点
keiyu: string, // 経由路線名
kyori: float, // 距離
jikan: int, // 所要時間
}
let global_ekimei_list = list{
{kanji:"代々木上原", kana:"よよぎうえはら", romaji:"yoyogiuehara", shozoku:"千代田線"},
{kanji:"代々木公園", kana:"よよぎこうえん", romaji:"yoyogikouen", shozoku:"千代田線"},
{kanji:"明治神宮前", kana:"めいじじんぐうまえ", romaji:"meijijinguumae", shozoku:"千代田線"},
{kanji:"表参道", kana:"おもてさんどう", romaji:"omotesandou", shozoku:"千代田線"},
{kanji:"乃木坂", kana:"のぎざか", romaji:"nogizaka", shozoku:"千代田線"},
{kanji:"赤坂", kana:"あかさか", romaji:"akasaka", shozoku:"千代田線"},
{kanji:"国会議事堂前", kana:"こっかいぎじどうまえ", romaji:"kokkaigijidoumae", shozoku:"千代田線"},
{kanji:"霞ヶ関", kana:"かすみがせき", romaji:"kasumigaseki", shozoku:"千代田線"},
{kanji:"日比谷", kana:"ひびや", romaji:"hibiya", shozoku:"千代田線"},
{kanji:"二重橋前", kana:"にじゅうばしまえ", romaji:"nijuubasimae", shozoku:"千代田線"},
{kanji:"大手町", kana:"おおてまち", romaji:"otemachi", shozoku:"千代田線"},
{kanji:"新御茶ノ水", kana:"しんおちゃのみず", romaji:"shin-ochanomizu", shozoku:"千代田線"},
{kanji:"湯島", kana:"ゆしま", romaji:"yushima", shozoku:"千代田線"},
{kanji:"根津", kana:"ねづ", romaji:"nedu", shozoku:"千代田線"},
{kanji:"千駄木", kana:"せんだぎ", romaji:"sendagi", shozoku:"千代田線"},
{kanji:"西日暮里", kana:"にしにっぽり", romaji:"nishinippori", shozoku:"千代田線"},
{kanji:"町屋", kana:"まちや", romaji:"machiya", shozoku:"千代田線"},
{kanji:"北千住", kana:"きたせんじゅ", romaji:"kitasenjyu", shozoku:"千代田線"},
{kanji:"綾瀬", kana:"あやせ", romaji:"ayase", shozoku:"千代田線"},
{kanji:"北綾瀬", kana:"きたあやせ", romaji:"kitaayase", shozoku:"千代田線"},
{kanji:"浅草", kana:"あさくさ", romaji:"asakusa", shozoku:"銀座線"},
{kanji:"田原町", kana:"たわらまち", romaji:"tawaramachi", shozoku:"銀座線"},
{kanji:"稲荷町", kana:"いなりちょう", romaji:"inaricho", shozoku:"銀座線"},
{kanji:"上野", kana:"うえの", romaji:"ueno", shozoku:"銀座線"},
{kanji:"上野広小路", kana:"うえのひろこうじ", romaji:"uenohirokoji", shozoku:"銀座線"},
{kanji:"末広町", kana:"すえひろちょう", romaji:"suehirocho", shozoku:"銀座線"},
{kanji:"神田", kana:"かんだ", romaji:"kanda", shozoku:"銀座線"},
{kanji:"三越前", kana:"みつこしまえ", romaji:"mitsukoshimae", shozoku:"銀座線"},
{kanji:"日本橋", kana:"にほんばし", romaji:"nihonbashi", shozoku:"銀座線"},
{kanji:"京橋", kana:"きょうばし", romaji:"kyobashi", shozoku:"銀座線"},
{kanji:"銀座", kana:"ぎんざ", romaji:"ginza", shozoku:"銀座線"},
{kanji:"新橋", kana:"しんばし", romaji:"shinbashi", shozoku:"銀座線"},
{kanji:"虎ノ門", kana:"とらのもん", romaji:"toranomon", shozoku:"銀座線"},
{kanji:"溜池山王", kana:"ためいけさんのう", romaji:"tameikesannou", shozoku:"銀座線"},
{kanji:"赤坂見附", kana:"あかさかみつけ", romaji:"akasakamitsuke", shozoku:"銀座線"},
{kanji:"青山一丁目", kana:"あおやまいっちょうめ", romaji:"aoyamaicchome", shozoku:"銀座線"},
{kanji:"外苑前", kana:"がいえんまえ", romaji:"gaienmae", shozoku:"銀座線"},
{kanji:"表参道", kana:"おもてさんどう", romaji:"omotesando", shozoku:"銀座線"},
{kanji:"渋谷", kana:"しぶや", romaji:"shibuya", shozoku:"銀座線"},
{kanji:"渋谷", kana:"しぶや", romaji:"shibuya", shozoku:"半蔵門線"},
{kanji:"表参道", kana:"おもてさんどう", romaji:"omotesandou", shozoku:"半蔵門線"},
{kanji:"青山一丁目", kana:"あおやまいっちょうめ", romaji:"aoyama-itchome", shozoku:"半蔵門線"},
{kanji:"永田町", kana:"ながたちょう", romaji:"nagatacho", shozoku:"半蔵門線"},
{kanji:"半蔵門", kana:"はんぞうもん", romaji:"hanzomon", shozoku:"半蔵門線"},
{kanji:"九段下", kana:"くだんした", romaji:"kudanshita", shozoku:"半蔵門線"},
{kanji:"神保町", kana:"じんぼうちょう", romaji:"jinbocho", shozoku:"半蔵門線"},
{kanji:"大手町", kana:"おおてまち", romaji:"otemachi", shozoku:"半蔵門線"},
{kanji:"三越前", kana:"みつこしまえ", romaji:"mitsukoshimae", shozoku:"半蔵門線"},
{kanji:"水天宮前", kana:"すいてんぐうまえ", romaji:"suitengumae", shozoku:"半蔵門線"},
{kanji:"清澄白河", kana:"きよすみしらかわ", romaji:"kiyosumi-shirakawa", shozoku:"半蔵門線"},
{kanji:"住吉", kana:"すみよし", romaji:"sumiyoshi", shozoku:"半蔵門線"},
{kanji:"錦糸町", kana:"きんしちょう", romaji:"kinshicho", shozoku:"半蔵門線"},
{kanji:"押上", kana:"おしあげ", romaji:"oshiage", shozoku:"半蔵門線"},
{kanji:"中目黒", kana:"なかめぐろ", romaji:"nakameguro", shozoku:"日比谷線"},
{kanji:"恵比寿", kana:"えびす", romaji:"ebisu", shozoku:"日比谷線"},
{kanji:"広尾", kana:"ひろお", romaji:"hiro", shozoku:"日比谷線"},
{kanji:"六本木", kana:"ろっぽんぎ", romaji:"roppongi", shozoku:"日比谷線"},
{kanji:"神谷町", kana:"かみやちょう", romaji:"kamiyacho", shozoku:"日比谷線"},
{kanji:"霞ヶ関", kana:"かすみがせき", romaji:"kasumigaseki", shozoku:"日比谷線"},
{kanji:"日比谷", kana:"ひびや", romaji:"hibiya", shozoku:"日比谷線"},
{kanji:"銀座", kana:"ぎんざ", romaji:"ginza", shozoku:"日比谷線"},
{kanji:"東銀座", kana:"ひがしぎんざ", romaji:"higashiginza", shozoku:"日比谷線"},
{kanji:"築地", kana:"つきじ", romaji:"tsukiji", shozoku:"日比谷線"},
{kanji:"八丁堀", kana:"はっちょうぼり", romaji:"hacchobori", shozoku:"日比谷線"},
{kanji:"茅場町", kana:"かやばちょう", romaji:"kayabacho", shozoku:"日比谷線"},
{kanji:"人形町", kana:"にんぎょうちょう", romaji:"ningyomachi", shozoku:"日比谷線"},
{kanji:"小伝馬町", kana:"こでんまちょう", romaji:"kodemmacho", shozoku:"日比谷線"},
{kanji:"秋葉原", kana:"あきはばら", romaji:"akihabara", shozoku:"日比谷線"},
{kanji:"仲御徒町", kana:"なかおかちまち", romaji:"nakaokachimachi", shozoku:"日比谷線"},
{kanji:"上野", kana:"うえの", romaji:"ueno", shozoku:"日比谷線"},
{kanji:"入谷", kana:"いりや", romaji:"iriya", shozoku:"日比谷線"},
{kanji:"三ノ輪", kana:"みのわ", romaji:"minowa", shozoku:"日比谷線"},
{kanji:"南千住", kana:"みなみせんじゅ", romaji:"minamisenju", shozoku:"日比谷線"},
{kanji:"北千住", kana:"きたせんじゅ", romaji:"kitasenju", shozoku:"日比谷線"},
{kanji:"池袋", kana:"いけぶくろ", romaji:"ikebukuro", shozoku:"丸ノ内線"},
{kanji:"新大塚", kana:"しんおおつか", romaji:"shinotsuka", shozoku:"丸ノ内線"},
{kanji:"茗荷谷", kana:"みょうがだに", romaji:"myogadani", shozoku:"丸ノ内線"},
{kanji:"後楽園", kana:"こうらくえん", romaji:"korakuen", shozoku:"丸ノ内線"},
{kanji:"本郷三丁目", kana:"ほんごうさんちょうめ", romaji:"hongosanchome", shozoku:"丸ノ内線"},
{kanji:"御茶ノ水", kana:"おちゃのみず", romaji:"ochanomizu", shozoku:"丸ノ内線"},
{kanji:"淡路町", kana:"あわじちょう", romaji:"awajicho", shozoku:"丸ノ内線"},
{kanji:"大手町", kana:"おおてまち", romaji:"otemachi", shozoku:"丸ノ内線"},
{kanji:"東京", kana:"とうきょう", romaji:"tokyo", shozoku:"丸ノ内線"},
{kanji:"銀座", kana:"ぎんざ", romaji:"ginza", shozoku:"丸ノ内線"},
{kanji:"霞ヶ関", kana:"かすみがせき", romaji:"kasumigaseki", shozoku:"丸ノ内線"},
{kanji:"国会議事堂前", kana:"こっかいぎじどうまえ", romaji:"kokkaigijidomae", shozoku:"丸ノ内線"},
{kanji:"赤坂見附", kana:"あかさかみつけ", romaji:"akasakamitsuke", shozoku:"丸ノ内線"},
{kanji:"四ツ谷", kana:"よつや", romaji:"yotsuya", shozoku:"丸ノ内線"},
{kanji:"四谷三丁目", kana:"よつやさんちょうめ", romaji:"yotsuyasanchome", shozoku:"丸ノ内線"},
{kanji:"新宿御苑前", kana:"しんじゅくぎょえんまえ", romaji:"shinjuku-gyoemmae", shozoku:"丸ノ内線"},
{kanji:"新宿三丁目", kana:"しんじゅくさんちょうめ", romaji:"shinjuku-sanchome", shozoku:"丸ノ内線"},
{kanji:"新宿", kana:"しんじゅく", romaji:"shinjuku", shozoku:"丸ノ内線"},
{kanji:"西新宿", kana:"にししんじゅく", romaji:"nishi-shinjuku", shozoku:"丸ノ内線"},
{kanji:"中野坂上", kana:"なかのさかうえ", romaji:"nakano-sakaue", shozoku:"丸ノ内線"},
{kanji:"新中野", kana:"しんなかの", romaji:"shin-nakano", shozoku:"丸ノ内線"},
{kanji:"東高円寺", kana:"ひがしこうえんじ", romaji:"higashi-koenji", shozoku:"丸ノ内線"},
{kanji:"新高円寺", kana:"しんこうえんじ", romaji:"shin-koenji", shozoku:"丸ノ内線"},
{kanji:"南阿佐ヶ谷", kana:"みなみあさがや", romaji:"minami-asagaya", shozoku:"丸ノ内線"},
{kanji:"荻窪", kana:"おぎくぼ", romaji:"ogikubo", shozoku:"丸ノ内線"},
{kanji:"中野新橋", kana:"なかのしんばし", romaji:"nakano-shimbashi", shozoku:"丸ノ内線"},
{kanji:"中野富士見町", kana:"なかのふじみちょう", romaji:"nakano-fujimicho", shozoku:"丸ノ内線"},
{kanji:"方南町", kana:"ほうなんちょう", romaji:"honancho", shozoku:"丸ノ内線"},
{kanji:"四ツ谷", kana:"よつや", romaji:"yotsuya", shozoku:"南北線"},
{kanji:"永田町", kana:"ながたちょう", romaji:"nagatacho", shozoku:"南北線"},
{kanji:"溜池山王", kana:"ためいけさんのう", romaji:"tameikesanno", shozoku:"南北線"},
{kanji:"六本木一丁目", kana:"ろっぽんぎいっちょうめ", romaji:"roppongiitchome", shozoku:"南北線"},
{kanji:"麻布十番", kana:"あざぶじゅうばん", romaji:"azabujuban", shozoku:"南北線"},
{kanji:"白金高輪", kana:"しろかねたかなわ", romaji:"shirokanetakanawa", shozoku:"南北線"},
{kanji:"白金台", kana:"しろかねだい", romaji:"shirokanedai", shozoku:"南北線"},
{kanji:"目黒", kana:"めぐろ", romaji:"meguro", shozoku:"南北線"},
{kanji:"市ヶ谷", kana:"いちがや", romaji:"ichigaya", shozoku:"南北線"},
{kanji:"飯田橋", kana:"いいだばし", romaji:"idabashi", shozoku:"南北線"},
{kanji:"後楽園", kana:"こうらくえん", romaji:"korakuen", shozoku:"南北線"},
{kanji:"東大前", kana:"とうだいまえ", romaji:"todaimae", shozoku:"南北線"},
{kanji:"本駒込", kana:"ほんこまごめ", romaji:"honkomagome", shozoku:"南北線"},
{kanji:"駒込", kana:"こまごめ", romaji:"komagome", shozoku:"南北線"},
{kanji:"西ヶ原", kana:"にしがはら", romaji:"nishigahara", shozoku:"南北線"},
{kanji:"王子", kana:"おうじ", romaji:"oji", shozoku:"南北線"},
{kanji:"王子神谷", kana:"おうじかみや", romaji:"ojikamiya", shozoku:"南北線"},
{kanji:"志茂", kana:"しも", romaji:"shimo", shozoku:"南北線"},
{kanji:"赤羽岩淵", kana:"あかばねいわぶち", romaji:"akabaneiwabuchi", shozoku:"南北線"},
{kanji:"西船橋", kana:"にしふなばし", romaji:"nishi-funabashi", shozoku:"東西線"},
{kanji:"原木中山", kana:"ばらきなかやま", romaji:"baraki-nakayama", shozoku:"東西線"},
{kanji:"妙典", kana:"みょうでん", romaji:"myoden", shozoku:"東西線"},
{kanji:"行徳", kana:"ぎょうとく", romaji:"gyotoku", shozoku:"東西線"},
{kanji:"南行徳", kana:"みなみぎょうとく", romaji:"minami-gyotoku", shozoku:"東西線"},
{kanji:"浦安", kana:"うらやす", romaji:"urayasu", shozoku:"東西線"},
{kanji:"葛西", kana:"かさい", romaji:"kasai", shozoku:"東西線"},
{kanji:"西葛西", kana:"にしかさい", romaji:"nishi-kasai", shozoku:"東西線"},
{kanji:"南砂町", kana:"みなみすなまち", romaji:"minami-sunamachi", shozoku:"東西線"},
{kanji:"東陽町", kana:"とうようちょう", romaji:"touyoucho", shozoku:"東西線"},
{kanji:"木場", kana:"きば", romaji:"kiba", shozoku:"東西線"},
{kanji:"門前仲町", kana:"もんぜんなかちょう", romaji:"monzen-nakacho", shozoku:"東西線"},
{kanji:"茅場町", kana:"かやばちょう", romaji:"kayabacho", shozoku:"東西線"},
{kanji:"日本橋", kana:"にほんばし", romaji:"nihonbashi", shozoku:"東西線"},
{kanji:"大手町", kana:"おおてまち", romaji:"otemachi", shozoku:"東西線"},
{kanji:"竹橋", kana:"たけばし", romaji:"takebashi", shozoku:"東西線"},
{kanji:"九段下", kana:"くだんした", romaji:"kudanshita", shozoku:"東西線"},
{kanji:"飯田橋", kana:"いいだばし", romaji:"iidabashi", shozoku:"東西線"},
{kanji:"神楽坂", kana:"かぐらざか", romaji:"kagurazaka", shozoku:"東西線"},
{kanji:"早稲田", kana:"わせだ", romaji:"waseda", shozoku:"東西線"},
{kanji:"高田馬場", kana:"たかだのばば", romaji:"takadanobaba", shozoku:"東西線"},
{kanji:"落合", kana:"おちあい", romaji:"ochiai", shozoku:"東西線"},
{kanji:"中野", kana:"なかの", romaji:"nakano", shozoku:"東西線"},
{romaji:"shinkiba", kana:"しんきば", kanji:"新木場", shozoku:"有楽町線"},
{romaji:"tatsumi", kana:"たつみ", kanji:"辰巳", shozoku:"有楽町線"},
{romaji:"toyosu", kana:"とよす", kanji:"豊洲", shozoku:"有楽町線"},
{romaji:"tsukishima", kana:"つきしま", kanji:"月島", shozoku:"有楽町線"},
{romaji:"shintomityou", kana:"しんとみちょう", kanji:"新富町", shozoku:"有楽町線"},
{romaji:"ginzaittyoume", kana:"ぎんざいっちょうめ", kanji:"銀座一丁目", shozoku:"有楽町線"},
{romaji:"yuurakutyou", kana:"ゆうらくちょう", kanji:"有楽町", shozoku:"有楽町線"},
{romaji:"sakuradamon", kana:"さくらだもん", kanji:"桜田門", shozoku:"有楽町線"},
{romaji:"nagatacho", kana:"ながたちょう", kanji:"永田町", shozoku:"有楽町線"},
{romaji:"koujimachi", kana:"こうじまち", kanji:"麹町", shozoku:"有楽町線"},
{romaji:"ichigaya", kana:"いちがや", kanji:"市ヶ谷", shozoku:"有楽町線"},
{romaji:"iidabashi", kana:"いいだばし", kanji:"飯田橋", shozoku:"有楽町線"},
{kanji:"江戸川橋", kana:"えどがわばし", romaji:"edogawabasi", shozoku:"有楽町線"},
{kanji:"護国寺", kana:"ごこくじ", romaji:"gokokuji", shozoku:"有楽町線"},
{kanji:"東池袋", kana:"ひがしいけぶくろ", romaji:"higasiikebukuro", shozoku:"有楽町線"},
{kanji:"池袋", kana:"いけぶくろ", romaji:"ikebukuro", shozoku:"有楽町線"},
{kanji:"要町", kana:"かなめちょう", romaji:"kanametyou", shozoku:"有楽町線"},
{kanji:"千川", kana:"せんかわ", romaji:"senkawa", shozoku:"有楽町線"},
{kanji:"小竹向原", kana:"こたけむかいはら", romaji:"kotakemukaihara", shozoku:"有楽町線"},
{kanji:"氷川台", kana:"ひかわだい", romaji:"hikawadai", shozoku:"有楽町線"},
{kanji:"平和台", kana:"へいわだい", romaji:"heiwadai", shozoku:"有楽町線"},
{kanji:"営団赤塚", kana:"えいだんあかつか", romaji:"eidanakakuka", shozoku:"有楽町線"},
{kanji:"営団成増", kana:"えいだんなります", romaji:"eidannarimasu", shozoku:"有楽町線"},
{kanji:"和光市", kana:"わこうし", romaji:"wakousi", shozoku:"有楽町線"},
}
let global_ekikan_list = list{
{kiten:"代々木上原", shuten:"代々木公園", keiyu:"千代田線", kyori:1.0, jikan:2},
{kiten:"代々木公園", shuten:"明治神宮前", keiyu:"千代田線", kyori:1.2, jikan:2},
{kiten:"明治神宮前", shuten:"表参道", keiyu:"千代田線", kyori:0.9, jikan:2},
{kiten:"表参道", shuten:"乃木坂", keiyu:"千代田線", kyori:1.4, jikan:3},
{kiten:"乃木坂", shuten:"赤坂", keiyu:"千代田線", kyori:1.1, jikan:2},
{kiten:"赤坂", shuten:"国会議事堂前", keiyu:"千代田線", kyori:0.8, jikan:1},
{kiten:"国会議事堂前", shuten:"霞ヶ関", keiyu:"千代田線", kyori:0.7, jikan:1},
{kiten:"霞ヶ関", shuten:"日比谷", keiyu:"千代田線", kyori:1.2, jikan:2},
{kiten:"日比谷", shuten:"二重橋前", keiyu:"千代田線", kyori:0.7, jikan:1},
{kiten:"二重橋前", shuten:"大手町", keiyu:"千代田線", kyori:0.7, jikan:1},
{kiten:"大手町", shuten:"新御茶ノ水", keiyu:"千代田線", kyori:1.3, jikan:2},
{kiten:"新御茶ノ水", shuten:"湯島", keiyu:"千代田線", kyori:1.2, jikan:2},
{kiten:"湯島", shuten:"根津", keiyu:"千代田線", kyori:1.2, jikan:2},
{kiten:"根津", shuten:"千駄木", keiyu:"千代田線", kyori:1.0, jikan:2},
{kiten:"千駄木", shuten:"西日暮里", keiyu:"千代田線", kyori:0.9, jikan:1},
{kiten:"西日暮里", shuten:"町屋", keiyu:"千代田線", kyori:1.7, jikan:2},
{kiten:"町屋", shuten:"北千住", keiyu:"千代田線", kyori:2.6, jikan:3},
{kiten:"北千住", shuten:"綾瀬", keiyu:"千代田線", kyori:2.5, jikan:3},
{kiten:"綾瀬", shuten:"北綾瀬", keiyu:"千代田線", kyori:2.1, jikan:4},
{kiten:"浅草", shuten:"田原町", keiyu:"銀座線", kyori:0.8, jikan:2},
{kiten:"田原町", shuten:"稲荷町", keiyu:"銀座線", kyori:0.7, jikan:1},
{kiten:"稲荷町", shuten:"上野", keiyu:"銀座線", kyori:0.7, jikan:2},
{kiten:"上野", shuten:"上野広小路", keiyu:"銀座線", kyori:0.5, jikan:2},
{kiten:"上野広小路", shuten:"末広町", keiyu:"銀座線", kyori:0.6, jikan:1},
{kiten:"末広町", shuten:"神田", keiyu:"銀座線", kyori:1.1, jikan:2},
{kiten:"神田", shuten:"三越前", keiyu:"銀座線", kyori:0.7, jikan:1},
{kiten:"三越前", shuten:"日本橋", keiyu:"銀座線", kyori:0.6, jikan:2},
{kiten:"日本橋", shuten:"京橋", keiyu:"銀座線", kyori:0.7, jikan:2},
{kiten:"京橋", shuten:"銀座", keiyu:"銀座線", kyori:0.7, jikan:1},
{kiten:"銀座", shuten:"新橋", keiyu:"銀座線", kyori:0.9, jikan:2},
{kiten:"新橋", shuten:"虎ノ門", keiyu:"銀座線", kyori:0.8, jikan:2},
{kiten:"虎ノ門", shuten:"溜池山王", keiyu:"銀座線", kyori:0.6, jikan:2},
{kiten:"溜池山王", shuten:"赤坂見附", keiyu:"銀座線", kyori:0.9, jikan:2},
{kiten:"赤坂見附", shuten:"青山一丁目", keiyu:"銀座線", kyori:1.3, jikan:2},
{kiten:"青山一丁目", shuten:"外苑前", keiyu:"銀座線", kyori:0.7, jikan:2},
{kiten:"外苑前", shuten:"表参道", keiyu:"銀座線", kyori:0.7, jikan:1},
{kiten:"表参道", shuten:"渋谷", keiyu:"銀座線", kyori:1.3, jikan:1},
{kiten:"渋谷", shuten:"表参道", keiyu:"半蔵門線", kyori:1.3, jikan:2},
{kiten:"表参道", shuten:"青山一丁目", keiyu:"半蔵門線", kyori:1.4, jikan:2},
{kiten:"青山一丁目", shuten:"永田町", keiyu:"半蔵門線", kyori:1.3, jikan:2},
{kiten:"永田町", shuten:"半蔵門", keiyu:"半蔵門線", kyori:1.0, jikan:2},
{kiten:"半蔵門", shuten:"九段下", keiyu:"半蔵門線", kyori:1.6, jikan:2},
{kiten:"九段下", shuten:"神保町", keiyu:"半蔵門線", kyori:0.4, jikan:1},
{kiten:"神保町", shuten:"大手町", keiyu:"半蔵門線", kyori:1.7, jikan:3},
{kiten:"大手町", shuten:"三越前", keiyu:"半蔵門線", kyori:0.7, jikan:1},
{kiten:"三越前", shuten:"水天宮前", keiyu:"半蔵門線", kyori:1.3, jikan:2},
{kiten:"水天宮前", shuten:"清澄白河", keiyu:"半蔵門線", kyori:1.7, jikan:3},
{kiten:"清澄白河", shuten:"住吉", keiyu:"半蔵門線", kyori:1.9, jikan:3},
{kiten:"住吉", shuten:"錦糸町", keiyu:"半蔵門線", kyori:1., jikan:2},
{kiten:"錦糸町", shuten:"押上", keiyu:"半蔵門線", kyori:1.4, jikan:2},
{kiten:"中目黒", shuten:"恵比寿", keiyu:"日比谷線", kyori:1., jikan:2},
{kiten:"恵比寿", shuten:"広尾", keiyu:"日比谷線", kyori:1.5, jikan:3},
{kiten:"広尾", shuten:"六本木", keiyu:"日比谷線", kyori:1.7, jikan:3},
{kiten:"六本木", shuten:"神谷町", keiyu:"日比谷線", kyori:1.5, jikan:3},
{kiten:"神谷町", shuten:"霞ヶ関", keiyu:"日比谷線", kyori:1.3, jikan:2},
{kiten:"霞ヶ関", shuten:"日比谷", keiyu:"日比谷線", kyori:1.2, jikan:2},
{kiten:"日比谷", shuten:"銀座", keiyu:"日比谷線", kyori:0.4, jikan:1},
{kiten:"銀座", shuten:"東銀座", keiyu:"日比谷線", kyori:0.4, jikan:1},
{kiten:"東銀座", shuten:"築地", keiyu:"日比谷線", kyori:0.6, jikan:2},
{kiten:"築地", shuten:"八丁堀", keiyu:"日比谷線", kyori:1., jikan:2},
{kiten:"八丁堀", shuten:"茅場町", keiyu:"日比谷線", kyori:0.5, jikan:1},
{kiten:"茅場町", shuten:"人形町", keiyu:"日比谷線", kyori:0.9, jikan:2},
{kiten:"人形町", shuten:"小伝馬町", keiyu:"日比谷線", kyori:0.6, jikan:1},
{kiten:"小伝馬町", shuten:"秋葉原", keiyu:"日比谷線", kyori:0.9, jikan:2},
{kiten:"秋葉原", shuten:"仲御徒町", keiyu:"日比谷線", kyori:1., jikan:1},
{kiten:"仲御徒町", shuten:"上野", keiyu:"日比谷線", kyori:0.5, jikan:1},
{kiten:"上野", shuten:"入谷", keiyu:"日比谷線", kyori:1.2, jikan:2},
{kiten:"入谷", shuten:"三ノ輪", keiyu:"日比谷線", kyori:1.2, jikan:2},
{kiten:"三ノ輪", shuten:"南千住", keiyu:"日比谷線", kyori:0.8, jikan:2},
{kiten:"南千住", shuten:"北千住", keiyu:"日比谷線", kyori:1.8, jikan:3},
{kiten:"池袋", shuten:"新大塚", keiyu:"丸ノ内線", kyori:1.8, jikan:3},
{kiten:"新大塚", shuten:"茗荷谷", keiyu:"丸ノ内線", kyori:1.2, jikan:2},
{kiten:"茗荷谷", shuten:"後楽園", keiyu:"丸ノ内線", kyori:1.8, jikan:2},
{kiten:"後楽園", shuten:"本郷三丁目", keiyu:"丸ノ内線", kyori:0.8, jikan:1},
{kiten:"本郷三丁目", shuten:"御茶ノ水", keiyu:"丸ノ内線", kyori:0.8, jikan:1},
{kiten:"御茶ノ水", shuten:"淡路町", keiyu:"丸ノ内線", kyori:0.8, jikan:1},
{kiten:"淡路町", shuten:"大手町", keiyu:"丸ノ内線", kyori:0.9, jikan:2},
{kiten:"大手町", shuten:"東京", keiyu:"丸ノ内線", kyori:0.6, jikan:1},
{kiten:"東京", shuten:"銀座", keiyu:"丸ノ内線", kyori:1.1, jikan:2},
{kiten:"銀座", shuten:"霞ヶ関", keiyu:"丸ノ内線", kyori:1.0, jikan:2},
{kiten:"霞ヶ関", shuten:"国会議事堂前", keiyu:"丸ノ内線", kyori:0.7, jikan:1},
{kiten:"国会議事堂前", shuten:"赤坂見附", keiyu:"丸ノ内線", kyori:0.9, jikan:2},
{kiten:"赤坂見附", shuten:"四ツ谷", keiyu:"丸ノ内線", kyori:1.3, jikan:2},
{kiten:"四ツ谷", shuten:"四谷三丁目", keiyu:"丸ノ内線", kyori:1.0, jikan:2},
{kiten:"四谷三丁目", shuten:"新宿御苑前", keiyu:"丸ノ内線", kyori:0.9, jikan:1},
{kiten:"新宿御苑前", shuten:"新宿三丁目", keiyu:"丸ノ内線", kyori:0.7, jikan:1},
{kiten:"新宿三丁目", shuten:"新宿", keiyu:"丸ノ内線", kyori:0.3, jikan:1},
{kiten:"新宿", shuten:"西新宿", keiyu:"丸ノ内線", kyori:0.8, jikan:1},
{kiten:"西新宿", shuten:"中野坂上", keiyu:"丸ノ内線", kyori:1.1, jikan:2},
{kiten:"中野坂上", shuten:"新中野", keiyu:"丸ノ内線", kyori:1.1, jikan:2},
{kiten:"新中野", shuten:"東高円寺", keiyu:"丸ノ内線", kyori:1.0, jikan:1},
{kiten:"東高円寺", shuten:"新高円寺", keiyu:"丸ノ内線", kyori:0.9, jikan:1},
{kiten:"新高円寺", shuten:"南阿佐ヶ谷", keiyu:"丸ノ内線", kyori:1.2, jikan:2},
{kiten:"南阿佐ヶ谷", shuten:"荻窪", keiyu:"丸ノ内線", kyori:1.5, jikan:2},
{kiten:"中野坂上", shuten:"中野新橋", keiyu:"丸ノ内線", kyori:1.3, jikan:2},
{kiten:"中野新橋", shuten:"中野富士見町", keiyu:"丸ノ内線", kyori:0.6, jikan:1},
{kiten:"中野富士見町", shuten:"方南町", keiyu:"丸ノ内線", kyori:1.3, jikan:2},
{kiten:"市ヶ谷", shuten:"四ツ谷", keiyu:"南北線", kyori:1.0, jikan:2},
{kiten:"四ツ谷", shuten:"永田町", keiyu:"南北線", kyori:1.3, jikan:3},
{kiten:"永田町", shuten:"溜池山王", keiyu:"南北線", kyori:0.9, jikan:1},
{kiten:"溜池山王", shuten:"六本木一丁目", keiyu:"南北線", kyori:0.9, jikan:2},
{kiten:"六本木一丁目", shuten:"麻布十番", keiyu:"南北線", kyori:1.2, jikan:2},
{kiten:"麻布十番", shuten:"白金高輪", keiyu:"南北線", kyori:1.3, jikan:2},
{kiten:"白金高輪", shuten:"白金台", keiyu:"南北線", kyori:1.0, jikan:2},
{kiten:"白金台", shuten:"目黒", keiyu:"南北線", kyori:1.3, jikan:2},
{kiten:"市ヶ谷", shuten:"飯田橋", keiyu:"南北線", kyori:1.1 , jikan:2},
{kiten:"飯田橋", shuten:"後楽園", keiyu:"南北線", kyori:1.4 , jikan:2},
{kiten:"後楽園", shuten:"東大前", keiyu:"南北線", kyori:1.3 , jikan:3},
{kiten:"東大前", shuten:"本駒込", keiyu:"南北線", kyori:0.9 , jikan:2},
{kiten:"本駒込", shuten:"駒込", keiyu:"南北線", kyori:1.4, jikan:2},
{kiten:"駒込", shuten:"西ヶ原", keiyu:"南北線", kyori:1.4, jikan:2},
{kiten:"西ヶ原", shuten:"王子", keiyu:"南北線", kyori:1.0, jikan:2},
{kiten:"王子", shuten:"王子神谷", keiyu:"南北線", kyori:1.2, jikan:2},
{kiten:"王子神谷", shuten:"志茂", keiyu:"南北線", kyori:1.6, jikan:3},
{kiten:"志茂", shuten:"赤羽岩淵", keiyu:"南北線", kyori:1.1, jikan:2},
{kiten:"西船橋" , shuten:"原木中山", keiyu:"東西線", kyori:1.9, jikan:3},
{kiten:"原木中山", shuten:"妙典", keiyu:"東西線", kyori:2.1 , jikan:2},
{kiten:"妙典", shuten:"行徳", keiyu:"東西線", kyori:1.3 , jikan:2},
{kiten:"行徳", shuten:"南行徳", keiyu:"東西線", kyori:1.5 , jikan:2},
{kiten:"南行徳", shuten:"浦安" , keiyu:"東西線", kyori:1.2 , jikan:2},
{kiten:"浦安" , shuten:"葛西", keiyu:"東西線", kyori:1.9 , jikan:2},
{kiten:"葛西", shuten:"西葛西", keiyu:"東西線", kyori:1.2 , jikan:2},
{kiten:"西葛西", shuten:"南砂町", keiyu:"東西線", kyori:2.7 , jikan:2},
{kiten:"南砂町", shuten:"東陽町", keiyu:"東西線", kyori:1.2 , jikan:2},
{kiten:"東陽町", shuten:"木場" , keiyu:"東西線", kyori:0.9 , jikan:1},
{kiten:"木場", shuten:"門前仲町", keiyu:"東西線", kyori:1.1 , jikan:1},
{kiten:"門前仲町", shuten:"茅場町", keiyu:"東西線", kyori:1.8 , jikan:2},
{kiten:"茅場町", shuten:"日本橋", keiyu:"東西線", kyori:0.5 , jikan:1},
{kiten:"日本橋", shuten:"大手町", keiyu:"東西線", kyori:0.8 , jikan:1},
{kiten:"大手町", shuten:"竹橋", keiyu:"東西線", kyori:1.0, jikan:2},
{kiten:"竹橋", shuten:"九段下", keiyu:"東西線", kyori:1.0, jikan:1},
{kiten:"九段下", shuten:"飯田橋", keiyu:"東西線", kyori:0.7, jikan:1},
{kiten:"飯田橋", shuten:"神楽坂", keiyu:"東西線", kyori:1.2, jikan:2},
{kiten:"神楽坂", shuten:"早稲田", keiyu:"東西線", kyori:1.2, jikan:2},
{kiten:"早稲田", shuten:"高田馬場", keiyu:"東西線", kyori:1.7, jikan:3},
{kiten:"高田馬場", shuten:"落合", keiyu:"東西線", kyori:1.9, jikan:3},
{kiten:"落合", shuten:"中野", keiyu:"東西線", kyori:2.0, jikan:3},
{kiten:"新木場", shuten:"辰巳", keiyu:"有楽町線", kyori:1.5, jikan:2},
{kiten:"辰巳", shuten:"豊洲", keiyu:"有楽町線", kyori:1.7, jikan:2},
{kiten:"豊洲", shuten:"月島", keiyu:"有楽町線", kyori:1.4, jikan:2},
{kiten:"月島", shuten:"新富町", keiyu:"有楽町線", kyori:1.3, jikan:2},
{kiten:"新富町", shuten:"銀座一丁目", keiyu:"有楽町線", kyori:0.7, jikan:1},
{kiten:"銀座一丁目", shuten:"有楽町", keiyu:"有楽町線", kyori:0.5, jikan:1},
{kiten:"有楽町", shuten:"桜田門", keiyu:"有楽町線", kyori:1.0, jikan:1},
{kiten:"桜田門", shuten:"永田町", keiyu:"有楽町線", kyori:0.9, jikan:2},
{kiten:"永田町", shuten:"麹町", keiyu:"有楽町線", kyori:0.9, jikan:1},
{kiten:"麹町", shuten:"市ヶ谷", keiyu:"有楽町線", kyori:0.9, jikan:1},
{kiten:"市ヶ谷", shuten:"飯田橋", keiyu:"有楽町線", kyori:1.1, jikan:2},
{kiten:"飯田橋", shuten:"江戸川橋", keiyu:"有楽町線", kyori:1.6, jikan:3},
{kiten:"江戸川橋", shuten:"護国寺", keiyu:"有楽町線", kyori:1.3, jikan:2},
{kiten:"護国寺", shuten:"東池袋", keiyu:"有楽町線", kyori:1.1, jikan:2},
{kiten:"東池袋", shuten:"池袋", keiyu:"有楽町線", kyori:2.0, jikan:2},
{kiten:"池袋", shuten:"要町", keiyu:"有楽町線", kyori:1.2, jikan:2},
{kiten:"要町", shuten:"千川", keiyu:"有楽町線", kyori:1.0, jikan:1},
{kiten:"千川", shuten:"小竹向原", keiyu:"有楽町線", kyori:1.0, jikan:2},
{kiten:"小竹向原", shuten:"氷川台", keiyu:"有楽町線", kyori:1.5, jikan:2},
{kiten:"氷川台", shuten:"平和台", keiyu:"有楽町線", kyori:1.4, jikan:2},
{kiten:"平和台", shuten:"営団赤塚", keiyu:"有楽町線", kyori:1.8, jikan:2},
{kiten:"営団赤塚", shuten:"営団成増", keiyu:"有楽町線", kyori:1.5, jikan:2},
{kiten:"営団成増", shuten:"和光市", keiyu:"有楽町線", kyori:2.1, jikan:3},
}
Ex23_3.res
open Metro // global_ekimei_list, global_ekikan_list の定義
open RedBlack
// open Tree
//Tree モジュールを使う場合はこちらを使用する
// グラフの中の節（駅）を表す型
// ただし、ここでは dijkstra_main の結果を格納するためにしか使っていない
type eki_t = {
namae : string, // 駅名（漢字）
saitan_kyori : float, // 最短距離
temae_list : list<string> // 手前の駅名（漢字）のリスト
}
// 駅間情報を表す木の型。以下のコメントでは ekikan_tree_t と記述
// type ekikan_tree_t = (string, (string * float) list) Tree.t
// 目的：重複を取り除き、各点の接続情報を示す木 ekikan_tree を作る。
// 駅間情報のみから構築し、駅情報は使わない。
// make_ekikan_tree : ekikan_t list -> ekikan_tree_t
let make_ekikan_tree = (ekikan_list) => {
let insert = (ekikan_tree, kiten, shuten, kyori) => {
let lst = try {search(ekikan_tree, kiten)} catch {|Not_found => list{}}
insert(ekikan_tree, kiten, list{(shuten, kyori), ...lst})
}
let insert_ekikan = (ekikan_tree,
{kiten: k, shuten: s, keiyu: _, kyori: r, jikan: _}) =>
insert(insert(ekikan_tree, k, s, r), s, k, r)
Js.List.foldLeft(insert_ekikan, empty, ekikan_list)
}
// 未確定駅の情報を表すヒープの型。以下のコメントでは heap_t と記述
// type heap_t = (float, 最短距離
// string * 駅名
// string list * 手前リスト
// ) Heap.t *)
// 各駅のヒープ中の位置を表す木の型。以下のコメントでは index_tree_t と記述
// type index_tree_t = (string, index_t) Tree.t
// 目的：ekikan_tree から eki_heap と index_tree を作り、kiten を初期化する
// make_eki_heap_and_index_tree :
// string -> ekikan_tree_t -> heap_t * index_tree_t
let make_eki_heap_and_index_tree = (kiten, ekikan_tree) =>
traverse(
((eki_heap, index_tree), k, _) => {
let (index, heap) = Heap.insert(eki_heap,
if k == kiten {0.} else {Float.Constants.positiveInfinity},
(k, if k == kiten {list{k}} else {list{}}))
let index_tree' = insert(index_tree, k, index)
(heap, index_tree')
},
((Heap.create(length(ekikan_tree), 0., ("駅名", list{})), empty)),
ekikan_tree
)
// 目的：確定した駅に接続している駅の最短距離、手前リストを更新する
// koushin : string -> float -> string list ->
// heap_t -> ekikan_tree_t -> index_tree_t -> heap_t
let koushin = (pn, ps, pt, eki_heap, ekikan_tree, index_tree) => {
let lst = search(ekikan_tree, pn)
Js.List.foldLeft(
(eki_heap, (shuten, kyori)) => try {
let shuten_index = search(index_tree, shuten)
let (saitan_kyori, (n, _)) = Heap.get(eki_heap, shuten_index)
let new_saitan_kyori = ps +. kyori
if new_saitan_kyori <= saitan_kyori
{Heap.set(eki_heap, shuten_index, new_saitan_kyori, (n, list{n, ...pt}))}
else {eki_heap}
} catch {|Not_found => eki_heap},
eki_heap,
lst
)
}
// 目的：未確定駅のリストと駅間リストから、各駅への最短路を求める
// dijkstra_main : heap_t -> ekikan_tree_t -> index_tree_t -> eki_t list
let rec dijkstra_main = (eki_heap, ekikan_tree, index_tree) =>
if Heap.length(eki_heap) == 0 {list{}}
else {
let ((ps, (pn, pt)), rest_heap) = Heap.split_top(eki_heap)
let eki_heap2 = koushin(pn, ps, pt, rest_heap, ekikan_tree, index_tree)
list{{namae: pn, saitan_kyori: ps, temae_list: pt},
...dijkstra_main(eki_heap2, ekikan_tree, index_tree)}
}
// 駅名が見つからなかったことを示す例外
exception No_such_station(string)
// 目的：ローマ字の駅名を漢字に直す
// 見つからなかったら例外 No_such_station を起こす
// romaji_to_kanji : string -> ekimei_t list -> string
let rec romaji_to_kanji = (r0, ekimei_list) => switch ekimei_list {
| list{} => raise(No_such_station(r0))
| list{{kanji: k, kana: _, romaji: r, shozoku: _}, ...rest} =>
if r0 == r {k} else {romaji_to_kanji(r0, rest)}
}
// 目的：受け取った eki_list から shuten のレコードを探し出す
// find : string -> eki_t list -> eki_t
let rec find = (shuten, eki_list) => switch eki_list {
| list{} => {namae: "", saitan_kyori: Float.Constants.positiveInfinity, temae_list: list{}}
| list{{namae: n, saitan_kyori: s, temae_list: t}, ...rest} =>
if n == shuten {{namae: n, saitan_kyori: s, temae_list: t}} else {find(shuten, rest)}
}
// 目的：始点と終点を受け取ったら、最短路を求め、終点のレコードを返す
// dijkstra : string -> string -> eki_t
let dijkstra = (romaji_kiten, romaji_shuten) => {
let kiten = romaji_to_kanji(romaji_kiten, global_ekimei_list)
let shuten = romaji_to_kanji(romaji_shuten, global_ekimei_list)
let ekikan_tree = make_ekikan_tree(global_ekikan_list)
let (eki_heap, index_tree) =
make_eki_heap_and_index_tree(kiten, ekikan_tree)
let eki_list = dijkstra_main(eki_heap, ekikan_tree, index_tree)
find(shuten, eki_list)
}
// 目的：eki_t 型のレコードをきれいに表示する
// print_eki : eki_t -> unit
let print_eki = (eki) => switch eki {
| {namae: _, saitan_kyori: s, temae_list: lst} => switch lst {
| list{} => assert false // この場合は起こりえない
| list{a} => Console.log(a ++ "（" ++ Float.toString(s) ++ "km）")
| list{a, ...rest} => {Js.List.foldRight(
(b, ()) => Console.log(b ++ "、"),
rest,
()
)
Console.log(a ++ "（" ++ Float.toString(s) ++ "km）")
}
}
}
// メイン関数
// main : string -> string -> unit
let main = (romaji_kiten, romaji_shuten) => {
let eki = dijkstra(romaji_kiten, romaji_shuten)
print_eki(eki)
}
main("shibuya", "gokokuji")
main("myogadani", "meguro")
/*
main("shibuya", "gokokuji")
渋谷、表参道、青山一丁目、永田町、麹町、市ヶ谷、飯田橋、江戸川橋、護国寺、
（9.8km）
main("myogadani", "meguro")
茗荷谷、後楽園、飯田橋、市ヶ谷、麹町、永田町、溜池山王、六本木一丁目、 麻
布十番、白金高輪、白金台、目黒（12.7km）
*/
第24章
振り返り