min/max procedures for a single string

[nimitbhardwaj]

I was wandering around the issues, and got this #6312, as I googled the minimum string, I got lexicographical minimal string rotation algorithm, I think it can be handy sometimes and is a good way to provide functioning to min and max procedures for a single string.

Here I give the example of using it.

writeln(max("hello"));

its output will be lohel

similarly for

writeln(min("BCABDADAB"));

its output will be ABBCABDAD

which results the lexicographically maximum and minimum strings by rotating the string.

Moreover acts as a nice chapel algorithm design exercise.

[bradcray]

As a gut reaction, this seems like something I might considering supporting, but using a name other than max() and min() (unless there was a compelling precedent for doing so). Specifically, Chapel already supports a few min()/max() overloads—one flavor that returns the extreme value for a given type; another that returns the extreme value of its arguments. I worry that adding a third flavor that permutes its argument to get an extreme value would be a third / different flavor and add confusion (e.g., it begs the question for me whether "max(10)" should return the maximum integer that can be created from two 1's and a 0, but I don't want max on integers to do that).

Supporting this but calling it something else seems reasonable to me (though I don't have any uses for it in mind... so again, studying precedents set by other popular libraries might suggest doing it or not, depending on what is found).

[nimitbhardwaj]

Yes, i got it, adding third kind of overloading will result in adding the function for other types, but now I think we can create a new module for it, it will be something called StringAlgorithms,chpl or some other appropriate name, which will include useful string algorithms like it, along with string search like KMP, Z buffer, string search by dfa and others, whoes names at this point of time i dont know, but by reading them and understanding them, can be implemented. Hows this idea

[nimitbhardwaj]

String algorithms are sometimes useful, the information about them can be gathered from Geeksforgeeks and other sites regarding competitive coding.

[bradcray]

I'm not enough of a string expert myself to be able to anticipate what will or won't be useful, but I almost never object to people writing libraries for Chapel that they think will be useful. This might be a good package to add mason support for, e.g.?

[nimitbhardwaj]

I can't say when string algorithms be useful, I usually do competitive coding, using coding to solve problems, in this string algos are very important sometimes, like pattern search, tries used with string is useful with search engine, there are many occasions where these simple algorithms can be used, so at first, I saw the min/max function, I thought it can be useful to overload, but as I understand the deeper, I thought it would be useful for chapel to have fast algorithms which can manipulate strings.

[nimitbhardwaj]

For this Issue, I can help perhaps, I am a computer science student, and I like to code, I do competitive coding, so I am well known with basic algorithms and data structures, know how to use them properly, and many other concerns about them. So, @bradcray, I want you to please assign this issue to me, may be I can't do it, I want to work on make the module. In the mean time, I am also brushing up my concepts about compiler design, so that I could also code and understand the logic for the base of the compiler.

[aconsroe-hpe]

Reviewing this issue, I agree a least/greatest string rotation function would be handy. But looking at #6312 shows one barrier to implementing as a min/max overload and furthermore, I agree with @bradcray that the overload is not in line with other uses (both in Chapel and elsewhere).

Recommended action is to close this issue as it pertains to the min/max overload which I think is a no-go. And for reference the least/greatest string (or any sequence) rotation can be found in O(n) with Booth's algorithm. I think the best result would be to have that written in a generic fashion so it could handle strings, bytes, tuples, arrays, etc.

[ShreyasKhandekar]

The algorithms requested were implemented and added as a test in https://github.com/chapel-lang/chapel/pull/8500 but it use a naive O(n^2) implementation. whereas the comment above mentions Booth's algorithm which is O(n).

Furthermore, as the comment above prescribes, this issue should be closed since the overload is not in line with other uses of min/max