Opened 8 years ago
Closed 8 years ago
#8232 closed defect (fixed)
cmp function for words is broken
Reported by: | slabbe | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3.3 |
Component: | combinatorics | Keywords: | |
Cc: | abmasse | Merged in: | sage-4.3.3.alpha1 |
Authors: | Sébastien Labbé | Reviewers: | Alexandre Blondin Massé |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As discussed on sage-combinat-devel, cmp is broken for words.
Amusant: this boils down to: sage: W = Words(['a','b','c']) sage: W('a') == W([]) True sage: W([]) == W('a') False
it causes problem else where :
sage: A = AlgebrasWithBasis(QQ).example(); A An example of an algebra with basis: the free algebra on the generators ('a', 'b', 'c') over Rational Field sage: [a,b,c] = A.algebra_generators() sage: a.is_one() True sage: b.is_one() True sage: c.is_one() True sage: A.one().is_one() True sage: (a+b).is_one() False sage: (a+A.one()).is_one() False
Attachments (1)
Change History (6)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
- Cc abmasse added
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
Hi, Sébastien !
I finally got some time to look at your patch and everything seems fine, code makes sense, documentation builds without warning and the bugs mentionned in the description are fixed.
The only observation I would make is that it seems costly to use all those try
and catch
blocks in the __cmp__(...)
function. Don't you think it may be better to use the izip_longest
function of the itertools
library, which fills the shortest iterator with a special character ? This way, you would only have to check if that character appear in self_it or in
other_it` to choose which one is the smallest w.r.t the lexicographic order.
comment:4 Changed 8 years ago by
- Reviewers set to Alexandre Blondin Massé
- Status changed from needs_review to positive_review
Never mind my last observation, it seems more complicated to use izip_longest
since you have to choose a different character from the one occurring in the compared words... and there is no clean way that comes up to me since the letters of word can be any object.
Anyway, the goal of the patch is reached, the documentation builds correctly, all tests pass, the bugs are fixed.
Positive review !
comment:5 Changed 8 years ago by
- Merged in set to sage-4.3.3.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
I just applied a patch which does the following things.
__cmp__
forWord_class
which was broken.__cmp__
fromFiniteWord_class
since the same function inWord_class
does the job anyway and in a cleaner way : it doesn't use the (useless?) coerce function. Surprinsingly, removing it makes it faster :NOTE : The difference between w and z above is that the parent of w is the alphabet of all python objects which uses the cmp of python to compare the letters whereas z compares its letters relatively to the order of the letters defined by its parent (here 0 < 1 but one could also say 1 < 0) which is slower.
__cmp__
was hidding one bug inlongest_common_prefix
. Indeed a doctest was passing while it wasn't supposed to: