list-diff-detector.hpp File Reference

Go to the source code of this file.

Description

Compare two data sequences to find or describe differences.

The DiffDetector defined here takes snapshot(s) from a monitored generic data structure and generates a description of differences in a linearised list diff language. Once initiated, the investigation of the old and new sequence snapshot, combined with generation of a sequence of diff description verbs, proceeds demand driven. The client "takes" a DiffFrame, which acts as iterator to extract the diff progressively; when initiating such a diff generation process, a new baseline snapshot from the underlying data is taken to replace the old baseline.

List Diff Algorithm

A fundamental decision taken here is to process the differences in a stream processing fashion. This renders the usage of data index numbers undesirable. Moreover, we do not want to assume anything about the consumer; the diff might be transformed into a textual representation, or it may be applied to quite another target data structure.

The implementation is built using a simplistic method and is certainly far from optimal. For one, we're taking snapshots, and we're building an index table for each snapshot, in order to distinguish inserted and deleted elements from mismatches due to sequence re-ordering. And for the description of permutations, we use a processing pattern similar to insertion sort. This allows for a very simple generation mechanism, but requires the receiver of the diff to scan down into the remainder of the data to find and fetch elements out-of-order.

See also

diff-list-generation-test.cpp

DiffApplicationStrategy

ListDiffLanguage

Definition in file list-diff-detector.hpp.

#include "lib/diff/list-diff.hpp"
#include "lib/diff/index-table.hpp"
#include "lib/iter-adapter.hpp"
#include "lib/nocopy.hpp"
#include <utility>

Classes
class	DiffDetector< SEQ >
	Detect and describe changes in a monitored data sequence. More...
class	DiffDetector< SEQ >::DiffFrame
	A diff generation process is built on top of an "old" reference point and a "new" state of the underlying sequence. More...

Namespaces
	lib
	Implementation namespace for support and library code.