Add computation of longest commons extensions in a word

[enadeau]

Add two methods to compute the longest commons extensions in forward and backward direction in a word.

Component: combinatorics

Keywords: words, days88, IMA coding sprints

Author: Émile Nadeau

Branch/Commit: 7ee5699

Reviewer: Travis Scrimshaw, Franco Saliola

Issue created by migration from https://trac.sagemath.org/ticket/23131

[enadeau]

Branch: u/enadeau/add_computation_of_longest_commons_extensions_in_a_word

[enadeau]

New commits:

182d7d3

Trac #23131: Add methods to compute longest common extension in words.

[enadeau]

Commit: 182d7d3

[tscrim]

comment:4

You should put spaces between your operators (e.g., =, ==, +=, etc.) and after commas to be PEP8 compliant. You should make your variables in code format in your doc, e.g., ``y``. Also, do these changes in your methods:

-        INPUTS:
{        INPUT:
 
-            x,y - positions in self
+        - ``x``, ``y`` -- positions in ``self``
 
-        EXAMPLES:
+        EXAMPLES::

[sagetrac-git]

Changed commit from 182d7d3 to 788470c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

788470c

Trac #23131: Correct code and doc formating

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

adae40d

Trac #23131: Correct formating of code and doctest

[sagetrac-git]

Changed commit from 788470c to adae40d

[tscrim]

comment:7

Three additional comments, but once addressed, then this will be ready for a positive review.

• Translation needed le -> the.
• - ``x``, ``y`` - positions in ``self`` should be - ``x``, ``y`` -- positions in ``self`` in longest_backward_extension.
• I think if x and y are invalid positions, then the method should raise a ValueError instead of returning 0 as it is invalid input.

[sagetrac-git]

Changed commit from adae40d to c992563

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c992563

Trac #23131: Minor correction and add a valueError for invalid

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed branch from u/enadeau/add_computation_of_longest_commons_extensions_in_a_word to public/combinat/words/longest_common_extension-23131

[tscrim]

Changed commit from c992563 to 8d3d3fa

[tscrim]

comment:9

I have made a last few little changes to the doc and made the doctests pass (specifically, indices are 0-based). If you agree with my changes, then positive review.

---

New commits:

52ff453	Merge branch 'u/enadeau/add_computation_of_longest_commons_extensions_in_a_word' of trac.sagemath.org:sage into public/combinat/words/longest_common_extension-23131
8d3d3fa	Some last little doc fixes.

[kevindilks]

comment:10

Would it be worth the effort to modify the code to allow negative positions, indicating distance from the end of the word (the way that Python lists work) ?

[tscrim]

comment:11

I think that would complicate things, but I don't have uses for this code, so I have fundamentally no position on the matter. However, it would be consistent with words, e.g., w[-1] gets the last letter.

[tscrim]

Changed keywords from words to words, days88, IMA coding sprints

[kevindilks]

comment:13

if not (abs(x) < length and abs(y) < length):
            raise ValueError("x and y must be valid positions in self")
if x<0:
    x=length-x
if y<0:
    y=length-y

should work, right?

[kevindilks]

Changed keywords from words, days88, IMA coding sprints to words

[tscrim]

Changed keywords from words to words, days88, IMA coding sprints

[tscrim]

comment:14

No, you need -len(w):

sage: w = Word('123')
sage: w[-3]
'1'

So you need to be slightly more careful.

[kevindilks]

comment:15

if not (-length<= x < length and -length <= y < length):
            raise ValueError("x and y must be valid positions in self")
if x<0:
    x=length-x
if y<0:
    y=length-y

should work, right?

[tscrim]

comment:16

I think that should work.

[sagetrac-git]

Changed commit from 8d3d3fa to d17e0c8

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d17e0c8

Merge branch 'public/combinat/words/longest_common_extension-23131' of git://trac.sagemath.org/sage into t/23131/public/combinat/words/longest_common_extension-23131

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7ee5699

trac 23131: allow negative positions

[sagetrac-git]

Changed commit from d17e0c8 to 7ee5699

[saliola]

comment:19

I implemented Kevin's suggestion (except that I used x = length + x instead of x = length - x since x is negative in this case). If you are OK with my changes, then set this to positive review.

[tscrim]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Franco Saliola

[tscrim]

comment:20

LGTM.

[vbraun]

Changed branch from public/combinat/words/longest_common_extension-23131 to 7ee5699