Модуль Diffing_with_keys

module Diffing_with_keys: sig .. end

При вычислении разницы между списками, в которых у каждого элемента есть уникальный ключ, можно уточнить патч изменений, добавив два составных перемещения: обмены и перемещения.

Swap меняют местами два элемента. Стоимость Swap равна 2 * change - epsilon. Move меняют положение одного элемента. Стоимость Move равна delete + addition - epsilon.

Если стоимость delete + addition больше change, то при таких конкретных весах оптимальный патч с Swap и Move можно напрямую и быстро вычислить на основе исходного оптимального патча.

type 'a with_pos = {

	`pos : int;`
	`data : 'a;`

}

val with_pos : 'a list -> 'a with_pos list

type ('l, 'r, 'diff) mismatch =

|

Name of {





pos : int;






got : string;






expected : string;






types_match : bool;




}

|

Type of {





pos : int;






got : 'l;






expected : 'r;






reason : 'diff;




}

type ('l, 'r, 'diff) change =

| Change of ('l, 'r, 'diff) mismatch

|

Swap of {





pos : int * int;






first : string;






last : string;




}

|

Move of {





name : string;






got : int;






expected : int;




}

|

Insert of {





pos : int;






insert : 'r;




}

|

Delete of {





pos : int;






delete : 'l;




}

Эта специализированная версия изменений вводит два составных изменения: Move и Swap

val prefix : ('l, 'r, 'diff) change Format_doc.printer

module Define: functor (D : Diffing.Defs  with type eq := unit) -> sig .. end