220 38472 <57aff230-b879-4205-9cc6-dc3382c7d580@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: florian.csdt@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding Sorting with suffix subordering for suffix arrays Date: Mon, 4 Jun 2018 08:36:49 -0700 (PDT) Lines: 183 Approved: news@gmane.org Message-ID: <57aff230-b879-4205-9cc6-dc3382c7d580@isocpp.org> References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_19178_563515407.1528126609452" X-Trace: blaine.gmane.org 1528126485 11110 195.159.176.226 (4 Jun 2018 15:34:45 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 4 Jun 2018 15:34:45 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBC26HM4V3MIRBEVZ2XMAKGQEHCDJFBY@isocpp.org Mon Jun 04 17:34:41 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f198.google.com ([209.85.161.198]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fPrVI-0002mT-1K for gclcip-std-proposals@m.gmane.org; Mon, 04 Jun 2018 17:34:40 +0200 Original-Received: by mail-yw0-f198.google.com with SMTP id q66-v6sf4606506ywc.18 for ; Mon, 04 Jun 2018 08:36:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=pMUJld1N29uyIxwwMzfrSjqb0RzJk5bQWiQBwSB++MY=; b=RRS/K5A/RuKDKOK5a7f5RTnDHUjwbQwVDcetGHo1lRuOC+kzt5H6VB/akuCqs2Jzew A4NMHh8Ms0g2JpIo66NlW9/GNEKbHwlKpbCDOonaEDKEuE5DR/AGWc41y7Qa5QTNFSr2 GTKp3OAkNig32d++w/GRVg5B6i6ng8xDDL1kFtClC7R/8Xd02n2UZSgkD7Uz7+s+Wqui OWRlKWC4RfMOJI12fvH9SHVxdXOs3c16gH1LP6aoqZBRyLNdFN8eGOTVSz8UpcR9punH hSqwxBXzsDnpNJ8okUAhwFTdLmgT5e0tEdT7P3vvIfCc+PuaiLRVAvlBAlLwXEMdsmZK prsg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=pMUJld1N29uyIxwwMzfrSjqb0RzJk5bQWiQBwSB++MY=; b=R9delHGKNqEqQOPwbM+RjV3ZZ9bZaKmrJybqWC0gftNkYJJY4GuliMpt6CsrRbw4up /CTsny9L/J02f4R69ubhog7Vv45iaRpSCHFfDMk6fjdYr7RbqJ7HNEve02pHlK6UF/jg u0QD6RcRQBk7lsoe0sf1SS+Y58CVW21WKdhILyqfdKdF8P4ASVibro36X3SV9dTlKMUH 5Go/8XKAYK2+GjL9N9wBnFGRLCViAhAlAfqoDxV7iWeMX/wreFmLqFmL5cEcjhiKXsVk jmSr2NsMGfSwake8Fwr6MfuCiCgf2ju2DK8KZL9HtBr7lqN6sKJnotu+ICWslspqdrRM UkOQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=pMUJld1N29uyIxwwMzfrSjqb0RzJk5bQWiQBwSB++MY=; b=AIC8TxrLQdG/AxiHmLBgiX5Hb/9Ry3dHqnP9OEw+sEyPs+rGnyqSIm58N4wOe8H0W9 Q4wAsaLMlI0kQXPpU2aS/5bQ9ubqPko1cgVcJZykjzOnV1uMqpnBccrG77dkwdZMSljY O99BcFtnXB1Jo3ARDUzsWvHMVqZBTFNvKfw0pNHoEKTKUTAXOZoGa1G5wW+iAMrec8YZ XztPKUHCQtoTWaRlktBPSHTweW2+ORlWVlfGgk06XMGCmoqP5TSnuc63YkBHGmJRtAPF rlk7uG3PoD2VU9aIpSy7zZJvgRp058L3cz8pptiy0UW9Ig0LIK+BaYgmXLsgJgLf+n8I CH8g== X-Gm-Message-State: ALKqPwen+z4s1gCnXnU34jXnQP7fH+r7+sRZ090ZMylDlSYFvOoFaBS7 N2tgURmhAR6oWPmXRXa/NkDp7g== X-Google-Smtp-Source: ADUXVKIJzgXpVA1gqHIRenUwIiLXd0sTtLkt+V7AEMT0jK9pJb1hn7lzPcTX4OcP2hEktiPCKhJ4Yg== X-Received: by 2002:a81:ce06:: with SMTP id t6-v6mr4423429ywi.163.1528126611146; Mon, 04 Jun 2018 08:36:51 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a25:9305:: with SMTP id f5-v6ls9584473ybo.6.gmail; Mon, 04 Jun 2018 08:36:50 -0700 (PDT) X-Received: by 2002:a25:c782:: with SMTP id w124-v6mr979553ybe.11.1528126609915; Mon, 04 Jun 2018 08:36:49 -0700 (PDT) In-Reply-To: X-Original-Sender: florian.csdt@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:38472 Archived-At: ------=_Part_19178_563515407.1528126609452 Content-Type: multipart/alternative; boundary="----=_Part_19179_1736443434.1528126609452" ------=_Part_19179_1736443434.1528126609452 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I have the feeling we don't a new interface for that: template< typename RandomAccess_Iterator, typename Output_Iterator > void get_suffix_array(RandomAccess_Iterator begin, RandomAccess_Iterator en= d , Output_Iterator out_begin) { // few preparations const auto n =3D end - begin; auto out_end =3D out_begin + n; // actual work std::iota(out_begin, out_end, 0); std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return=20 begin[lhs] < begin[rhs]; }); } Would that be enough? Le lundi 4 juin 2018 17:14:52 UTC+2, joshua.r.ma...@gmail.com a =C3=A9crit = : > > A more limited change to the sorts made available is adding a discrete=20 > suffix array function. For the uninitiated, a suffix array is unlike a= =20 > typical sorting algorithm in two respects: the returned object is a=20 > sequence of indexes or reference into the original container, and in the= =20 > case of ties, subordering is dictated by a comparison of each index's or= =20 > reference's following value in the original container with the terminal= =20 > value being the global minimum value. > > The two significant algorithms for generating suffix arrays right now are= =20 > SACA-K and divsufsort. > > I think a good call interface for this would be as follows: > > template< typename _Bidirectional_Iterator, typename _Output_Iterator > > void get_suffix_array(_Bidirectional_Iterator begin,=20 > _Bidirectional_Iterator end, _Output_Iterator out); > > This would have applications in compression, text searching, and sequence= =20 > alignment. > --=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp= ..org/d/msgid/std-proposals/57aff230-b879-4205-9cc6-dc3382c7d580%40isocpp.or= g. ------=_Part_19179_1736443434.1528126609452 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I have the feeling we don't a new interface for that:<= br>
template&= lt; typename RandomAccess_Iterator, typename Output_Iterator >
void get_suffix_array(RandomAccess_Iterator begin, RandomAccess_Iterator end, Output_I= terator ou= t_begin) {
=
=C2=A0 =C2=A0// few prepa= rations
=C2=A0 =C2=A0= const auto n =3D end - begin;
=C2=A0 =C2=A0auto out_end =3D out_begin + n;

=C2=A0 =C2=A0 // actu= al work
=C2=A0 =C2=A0std::iota(out_= begin, out_end, 0);
=C2=A0 =C2=A0std::sort(out_= begin, out_end, [&begin](= auto lhs, auto rhs) { return begin[lhs] < begin[rhs]; });
}

Would that be enough?=

Le lundi 4 juin 2018 17:14:52 UTC+2, joshua.r.ma...@gmail.com a =C3= =A9crit=C2=A0:
A more limited change to the sorts made available is adding a discret= e suffix array function.=C2=A0 For the uninitiated, a suffix array is unlik= e a typical sorting algorithm in two respects: the returned object is a seq= uence of indexes or reference into the original container, and in the case = of ties, subordering is dictated by a comparison of each index's or ref= erence's following value in the original container with the terminal va= lue being the global minimum value.

The two signif= icant algorithms for generating suffix arrays right now are SACA-K and divs= ufsort.

I think a good call interface for this wou= ld be as follows:

template< typename _Bidirecti= onal_Iterator, typename _Output_Iterator >
void get_suffix_arr= ay(_Bidirectional_Iterator begin, _Bidirectional_Iterator end, _Output= _Iterator out);

This would have applications in co= mpression, text searching, and sequence alignment.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/57aff230-b879-4205-9cc6-dc3382c7d580= %40isocpp.org.
------=_Part_19179_1736443434.1528126609452-- ------=_Part_19178_563515407.1528126609452-- .