Basic wreath-product ordering implemented

[mikolajpabiszczak]

Ad #21 I know that I named it in a weird way, but this is the name that occurs in Sims. Please say if you prefer WreathOrder.

[codecov-commenter]

Codecov Report

Merging #31 into master will increase coverage by 1.58%. The diff coverage is 92.22%.

@@            Coverage Diff             @@
##           master      #31      +/-   ##
==========================================
+ Coverage   90.53%   92.11%   +1.58%     
==========================================
  Files          10       10              
  Lines         560      571      +11     
==========================================
+ Hits          507      526      +19     
+ Misses         53       45       -8     

Flag	Coverage Δ
#unittests	92.11% <92.22%> (+1.58%)	:arrow_up:

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
src/orderings.jl	84.37% <81.81%> (+2.55%)	:arrow_up:
src/rewriting.jl	90.56% <83.33%> (+3.89%)	:arrow_up:
src/abstract_words.jl	93.33% <100.00%> (ø)
src/alphabets.jl	76.56% <100.00%> (+0.37%)	:arrow_up:
src/automata.jl	88.81% <100.00%> (+5.71%)	:arrow_up:
src/bufferwords.jl	98.90% <100.00%> (-0.06%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 3e7c4b4...57020be. Read the comment docs.

[kalmarek]

WreathOrder would be better ;)

[mikolajpabiszczak]

Yes, I know it does, will have to look at it closer. I will apply your suggestions till Sunday morning.

[mikolajpabiszczak]

@kalmarek: I saw you already added tests for WreathOrder at some earlier stage. I made them workable by uncommenting etc.

[mikolajpabiszczak]

Frankly, I don't know how to shave allocations in head().

[kalmarek]

probably by avoiding the head completely: Sims describes an algorithm that runs in O(length(w)) time for producing the sequences. But we don't need the sequences if e.g. the degree of initial words could order them, or the left end;

One possible way is to do this by recursion, i.e. generate the next elements in the sequence only when necessary

[mikolajpabiszczak]

Ok, so I written it in the different way. It still allocates, but it allocates half of what it used to allocate.

I also checked the resulting RewritingSystem obtained by our implementation for the example 5.5 and two rules are slightly different. I am not sure if this is an error in the book or we have some deeper problem. (Note that this was also the case in the former implementation of WreathOrder, the one using head).