Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#8604 closed enhancement (fixed)

Add a class for factor-enumerable words

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-4.5.2
Component: combinatorics Keywords: Words, factors, enumeration
Cc: abmasse, jleroy Merged in: sage-4.5.2.alpha0
Authors: Sébastien Labbé Reviewers: Alexandre Blondin Massé
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Add a class for factor-enumerable words, i.e. having an algorithm that enumerates the factor of length n which includes finite words and some family of infinite words. The new file gathers methods (e.g. rauzy_graph) that depends only on the existence of such an algorithm.

It also adds some method about left,right and bi special words:

    sage: f = words.FibonacciWord()[:30]
    sage: f.number_of_left_special_factors(7)
    8

The new class Word_nfactor_enumerable inherits from the abstract Word_class and FiniteWord_class now inherits from this Word_nfactor_enumerable class. Later, inifinite words having a such an algorithm will inherit also from this new class (in some other ticket).

Attachments (2)

trac_8604_nfactor_enumerable-sl.patch (34.3 KB) - added by slabbe 7 years ago.
Depends on #8429.
trac_8604-corrections-sl.patch (6.4 KB) - added by slabbe 7 years ago.
Applies over the precedent patch

Download all attachments as: .zip

Change History (12)

comment:1 Changed 7 years ago by slabbe

  • Cc abmasse jleroy added
  • Status changed from new to needs_review

comment:2 follow-ups: Changed 7 years ago by abmasse

Very interesting ! I'll try to review this patch as soon as I have some time.

I took a quick look at it and I have a question, though. Why aren't the iterator functions (on the left special, bispecial and right special factor) public ? Since they are used only in the public functions that return the result as a list, I think it would be better either to make the iterator functions public, or to merge the two functions in one. Unless you've a reason to do so ?

comment:3 in reply to: ↑ 2 Changed 7 years ago by jleroy

Hi Sébastien.

I agree with Alex about the iterators on special factors. The only thing you need is the factor set to define them, right? I will try to review it next week but as I already know what are the functions it would probably be quick.

comment:4 in reply to: ↑ 2 ; follow-up: Changed 7 years ago by slabbe

Very interesting ! I'll try to review this patch as soon as I have some time.

Great!

I took a quick look at it and I have a question, though. Why aren't the iterator functions (on the left special, bispecial and right special factor) public ?

I would not say that they are not public since anybody can use it and access it with tab completion by adding the underscore first.

Well because many of the iterator functions are already hidden this way in sage words. We might want to change this convention. Or maybe, like factor_iterator, you think it would be more practicable if those were not hidden as well?

Since they are used only in the public functions that return the result as a list, I think it would be better either to make the iterator functions public, or to merge the two functions in one. Unless you've a reason to do so ?

I am against merging those two functions in one since both functions can be very usefull in different situations. The only question I see is (I don't like using the word public) :

Do we want the iterator functions of this patch to appear in the default listing of the tab completion on a word?

Sébastien

Changed 7 years ago by slabbe

Depends on #8429.

comment:5 Changed 7 years ago by slabbe

I just updated the patch. There was issue with the ordering of many list of factors. I added many sorted which should fix uniformize the results of doctests and not depend on the machine used anymore.

comment:6 in reply to: ↑ 4 Changed 7 years ago by abmasse

  • Status changed from needs_review to needs_work

Replying to slabbe:

Very interesting ! I'll try to review this patch as soon as I have some time.

Great!

I took a quick look at it and I have a question, though. Why aren't the iterator functions (on the left special, bispecial and right special factor) public ?

I would not say that they are not public since anybody can use it and access it with tab completion by adding the underscore first.

Well because many of the iterator functions are already hidden this way in sage words. We might want to change this convention. Or maybe, like factor_iterator, you think it would be more practicable if those were not hidden as well?

I understand your point, but I still think that since the class of factor-enumerable words was introduced in particular to deal with infinite words, one will probably need iterators to handle, say, left special factors. For instance, assume I want to enumerate all right special factors of a given Sturmian word. I'll need to use an iterator (the list won't be built since it's infinite). And I would like the function to appear when I hit TAB when calling a function on an infinite word.

What I suggest is to remove the underscore character in front of the iterators and even add a warning for the functions right_special_factors, etc. that tells the user that this function could not stop.

Since they are used only in the public functions that return the result as a list, I think it would be better either to make the iterator functions public, or to merge the two functions in one. Unless you've a reason to do so ?

I am against merging those two functions in one since both functions can be very usefull in different situations. The only question I see is (I don't like using the word public) :

I agree with you on this one, that was a bad idea.

Do we want the iterator functions of this patch to appear in the default listing of the tab completion on a word?

I say yes! I know one of your argument about that was that it would reduce the number of functions appearing when you hit TAB. On the other hand, there are not so many of them in the case of infinite words.

Sébastien

Changed 7 years ago by slabbe

Applies over the precedent patch

comment:7 Changed 7 years ago by slabbe

  • Authors set to Sébastien Labbé
  • Reviewers set to Alexandre Blondin Massé
  • Status changed from needs_work to needs_review

I agree with your suggestions. I changed the patch accordingly (see new patch attached).

Needs review!

comment:8 Changed 7 years ago by abmasse

  • Keywords Words factors enumeration added
  • Status changed from needs_review to positive_review

Hello, Sébastien and Julien !

Sorry about the delay, I've been very busy lately. I retested the patch on sage-4.4.3. All tests passed and the documentation built fine too. Therefore, I'm giving this patch a positive review.

comment:9 Changed 7 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:10 Changed 7 years ago by mpatel

Please see #9589 for doctest failures that may stem from this ticket.

Note: See TracTickets for help on using tickets.