Metadata-Version: 2.4
Name: patience_diff_algo
Version: 1.0.0
Summary: Patience Diff Algorithm - An implementation of Bram Cohen's diff algorithm
Home-page: https://github.com/joery0x3b800001/patience_diff
Author: Shaun Joe
Author-email: shaunjoeroy1234@gmail.com
License: GPLv2+
Project-URL: Bug Tracker, https://github.com/joery0x3b800001/patience_diff/issues
Project-URL: Source, https://github.com/joery0x3b800001/patience_diff
Keywords: diff algorithm patience sorting sequence
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Topic :: Utilities
Classifier: License :: OSI Approved :: GNU General Public License v2 or later (GPLv2+)
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.7
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Requires-Python: >=3.7
Description-Content-Type: text/markdown
License-File: LICENSE.md
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: keywords
Dynamic: license
Dynamic: license-file
Dynamic: project-url
Dynamic: requires-python
Dynamic: summary

# Patience Diff

A complete Python port of Bram Cohen's algorithm for computing efficient differences.

## Features

- Patience Sorting Algorithm: O(n log n)
- Semantic Cleanup: Removes spurious matches
- Multiple Output Formats: Blocks, hunks with context
- Myers Fallback: Simple diff for edge cases
- Type Hints: Full annotations for IDE support
- Well Tested: Comprehensive test suite

## Quick Start

```bash
make install  # Install in dev mode
make test     # Run tests
```

## License

GNU General Public License v2 or later

Original algorithm and OCaml implementation by Bram Cohen  
Copyright (C) 2005, 2006 Canonical Ltd  
Python port by Shaun Joe


## API Reference

### Core Functions

- `get_matching_blocks(transform, prev_array, next_array, big_enough=1)` - Find matching blocks
- `get_hunks(transform, prev_array, next_array, context=-1, big_enough=1)` - Generate hunks  
- `matches(prev_array, next_array)` - Get matching index pairs
- `match_ratio(prev_array, next_array)` - Calculate similarity ratio

### Data Types

- `Hunk` - Contiguous diff region with ranges
- `MatchingBlock` - Matching subsequence (prev_start, next_start, length)
- Range types: `Same`, `Prev`, `Next`, `Replace`


## Project Structure

```
src/                      # Python package (11 modules)
├── patience_diff.py      # Core algorithm (700+ lines)
├── plain_diff.py         # Myers fallback
├── hunk.py               # Hunk data structures
├── hunks.py              # Hunk utilities
├── matching_block.py     # Matching block type
├── range.py              # Range types
├── move_id.py            # Move identifiers
├── move_kind.py          # Move classification
├── patience_diff_intf.py # Interface definitions
├── patience_diff_lib.py  # Library exports
└── __init__.py           # Package initialization

test/                     # Test suite
├── test_limit_context.py
├── test_merge_diff.py
└── test_plain_diff_cutoff.py

Makefile                  # Build automation
setup.py                  # Package setup
pyproject.toml            # Build configuration
README.md
```


## Testing

All tests passing:

```bash
$ make test
test/test_limit_context.py PASSED
test/test_merge_diff.py PASSED
test/test_plain_diff_cutoff.py PASSED

============================  3 passed  ============================
```


## Algorithm

The Patience Diff algorithm works in several steps:

1. Identify unique elements (appearing exactly once in both sequences)
2. Build longest increasing subsequence (LIS) of unique matches using patience sorting
3. Recursively find matches in gaps between LIS elements
4. Remove spurious small matches ("semantic cleanup")
5. Merge adjacent blocks separated by identical elements
6. Convert matching blocks to hunks with Same/Prev/Next/Replace ranges


## References

- http://bazaar-vcs.org - Original implementation
- Eugene W. Myers: "An O(ND) Difference Algorithm and Its Variations"

