[phobos] [D-Programming-Language/phobos] 4c9c85: Modified Levenshtein distance()

[GitHub via phobos]

  Branch: refs/heads/master
  Home:   https://github.com/D-Programming-Language/phobos
  Commit: 4c9c85c183ab9d58914cb7870e12ef4f886ca9d4
      https://github.com/D-Programming-Language/phobos/commit/4c9c85c183ab9d58914cb7870e12ef4f886ca9d4
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Modified Levenshtein distance()

Modified the implementation of Levenshtein distance so that it now uses O(n) memory but retains the same time complexity. However, does not work with path().


  Commit: 3a8743343922dc21659bc475a2b46602458c00c1
      https://github.com/D-Programming-Language/phobos/commit/3a8743343922dc21659bc475a2b46602458c00c1
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Modified Levenshtein distance()

Modified the implementation of Levenshtein distance so that it now uses O(n) memory but retains the same time complexity. However, does not work with path().


  Commit: 7f5aff56934d2985e36065688b42523fd3251566
      https://github.com/D-Programming-Language/phobos/commit/7f5aff56934d2985e36065688b42523fd3251566
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Fixed formatting

Moved all braces so that they are on their own lines and removed the trailing whitespace after function declaration;


  Commit: a9ae1023a2912c48ecce8d743c5ba221254fa5a3
      https://github.com/D-Programming-Language/phobos/commit/a9ae1023a2912c48ecce8d743c5ba221254fa5a3
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Moved previous distance() implementation

Moved to be a private method and only expose new more memory efficient
distance(). This is done because we need the old implementation for
path(). Modified levenshteinDistanceAndPath() to use the old distance()
to reflect this.


  Commit: 0d0a2c030895bae19b90e2897137d8ae478fa48d
      https://github.com/D-Programming-Language/phobos/commit/0d0a2c030895bae19b90e2897137d8ae478fa48d
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Refactored, added unit tests and removed opIndex.

Moved checks for which Range is longer to levenshteinDistance() method.

Reverted to implementation found in original distance() with regards to
using front/popFront instead of opIndex.

Fixed formatting of return statement.

Added two unit tests for levenshteinDistance().

Credit to @Poita.


  Commit: 3e037f463ee31fd50f0803ccdb0911d40c52a0c8
      https://github.com/D-Programming-Language/phobos/commit/3e037f463ee31fd50f0803ccdb0911d40c52a0c8
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Refactored distance() and corrected path()

Refactored distacen() so that it now accepts the lengths of the ranges
because we already calculate these in levenshteinDistance().

Altered ss in distance() and tt in distanceWithPath().

Moved popFront()’s to after their final usage to handle transitive
ranges.

Corrected path() so that it calls distanceWithPath() instead of
distance().


  Commit: 5102e9e273d471908afd53e0472985a7eaf208e3
      https://github.com/D-Programming-Language/phobos/commit/5102e9e273d471908afd53e0472985a7eaf208e3
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Removed calls to matrix() in distance()

Since _matrix is now a single dimension matrix, calls to matrix() have
been removed and replaced with direct access equivalents.


  Commit: 4beda7da9c3b3a2c4311f6bb31c669686e709614
      https://github.com/D-Programming-Language/phobos/commit/4beda7da9c3b3a2c4311f6bb31c669686e709614
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Changed the implementation of distance() so that it uses the memory inefficient version to prevent breakage in the API. Efficient version has been moved to distanceLowMem() in the struct and is called internally by levenshteinDistance()


  Commit: 0a7d2c9b1025b8c2d3dd928441a645f66541a146
      https://github.com/D-Programming-Language/phobos/commit/0a7d2c9b1025b8c2d3dd928441a645f66541a146
  Author: James Carr <jc3212 at ic.ac.uk>
  Date:   2014-07-13 (Sun, 13 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Removed the accidental semicolon


  Commit: 1f4c14a0679ce19b4fa3ba2f9164559b87503cab
      https://github.com/D-Programming-Language/phobos/commit/1f4c14a0679ce19b4fa3ba2f9164559b87503cab
  Author: Dmitry Olshansky <dmitry.olsh at gmail.com>
  Date:   2014-07-17 (Thu, 17 Jul 2014)

  Changed paths:
    M std/algorithm.d

  Log Message:
  -----------
  Merge pull request #2195 from JamesDavidCarr/master

Changed distance() to be more memory efficient based on email from mailing list.


Compare: https://github.com/D-Programming-Language/phobos/compare/6d5ab305b939...1f4c14a0679c