220 38471 article Path: news.gmane.org!.POSTED!not-for-mail From: joshua.r.marshall.1991@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Adding Sorting with suffix subordering for suffix arrays Date: Mon, 4 Jun 2018 08:14:52 -0700 (PDT) Lines: 73 Approved: news@gmane.org Message-ID: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_33593_124879047.1528125292355" X-Trace: blaine.gmane.org 1528125169 6629 195.159.176.226 (4 Jun 2018 15:12:49 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 4 Jun 2018 15:12:49 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCFIZIPVQEORB3NO2XMAKGQEWVO7UFA@isocpp.org Mon Jun 04 17:12:45 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f200.google.com ([209.85.161.200]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fPrA3-0001bY-BL for gclcip-std-proposals@m.gmane.org; Mon, 04 Jun 2018 17:12:43 +0200 Original-Received: by mail-yw0-f200.google.com with SMTP id s12-v6sf23392220ywl.13 for ; Mon, 04 Jun 2018 08:14:54 -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:subject:mime-version:x-original-sender :reply-to:precedence:mailing-list:list-id:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=ryI8SLRueq78QIMuGzU4ztphB5iiIgxmX7xz/OXDDs4=; b=ohEjtcse1r7gS4GqQZyIg0r2Gog0uD6GaUUsX/IfckHvkMddevLdXqeXRusLBYffeG xpoSCxkmpVfx2YV9kHWpKeAHQNfwB9aSjrH2uu7oaNZNBvl8q9Jxhf/TiIOYCd+v9gxg nyFfMEpdycqfG2q20nGor390w1P3D2rwxeInpjErOTyh+tzBmO6hujiGj8PfRQ2lvTo/ jWISHsUFeGqg/0Lgm3QRGW1ak0ZfQn8ir23vcp6KZjaT4/rvFR60pgtk4S715ICCc6RM 3+mr+Qwhq9zUbcY2tmqSuB3t2l4ArJr0C9+SeU5i4IREp5soyVn3Rsit+xw/mlNdZMDS xGhA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:subject:mime-version:x-original-sender :reply-to:precedence:mailing-list:list-id:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=ryI8SLRueq78QIMuGzU4ztphB5iiIgxmX7xz/OXDDs4=; b=iK44GmvQP3mgpbyJJT/TJNZqsIzCnygT0K5daqD0szn/w1PhGWH8RRPSomcwd6hWKh GQfXEOe3ilIPRMfzs4610BAF8prcJErf10wrH7yC6UYNRiRRA1WRp8UapagSwvwLI419 3aa7gcBlXttjotAxtnef5lF54/JeAHNUSg2yljjUPY9K8GentEMAngcJTwb4uqujziDU KELNtoy7Q2/2+XeXosODPb431XcBDKYbWyn5TyRIDFL2LgTGoje22qDCcY5NlF73RN6U y8XFH1jcl0SSLkvB/TTe/yXhKu4YVmv6/yuilUIhQBLg2wrYIBslp1NtHUEeq3aJpV+0 zs7g== 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: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=ryI8SLRueq78QIMuGzU4ztphB5iiIgxmX7xz/OXDDs4=; b=JMUs9hN8vrHXcig27tbGIraioDTKkc8OKud7iIutGxr1TE/O3vMBkLQPYKUoCRX5hE Q09qFjvOA8miRFfw4saRl9rmXUe2ejeQKpk5Ap5nvKwsZBERMtR+V4glkX/UkBf9MjE8 nsg1zBtzXzLu1UR3++z9Y+qVZz/YFfFp6SlWAiLKsKgQbJluKoGDJ5Ghf6/dmtCKbPOJ vQgTzpQxqDdH3S+hNh1QziQIeG6i8Ew3nVbFaB9vnVH523DMrmyBCavaKOb0+40P+Mrc 84Ek9EElP9PIdNpqa9PQqcZxQYfHcFpnzSxsc+qvfSIu1+zmbxfTDQSvhrw+68JWFBbs +SJA== X-Gm-Message-State: ALKqPwcm2j7b+VUYPbx1p8bdu5MURHZmN89j9JiY1cKaZlNWvyoPp/02 6/XUqMcEWE7abXVanR5QDwcYuw== X-Google-Smtp-Source: ADUXVKLS4jNJcTl1aOIICLzqHQ6XMp1BAlKNeYFL3/Wy/YhiQBP+FVSX93pgZiHyswR2Fkc5Cmag2g== X-Received: by 2002:a81:ed0:: with SMTP id 199-v6mr6062495ywo.52.1528125294178; Mon, 04 Jun 2018 08:14:54 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a81:5383:: with SMTP id h125-v6ls3692943ywb.36.gmail; Mon, 04 Jun 2018 08:14:53 -0700 (PDT) X-Received: by 2002:a0d:cb58:: with SMTP id n85-v6mr922906ywd.5.1528125292894; Mon, 04 Jun 2018 08:14:52 -0700 (PDT) X-Original-Sender: joshua.r.marshall.1991@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:38471 Archived-At: ------=_Part_33593_124879047.1528125292355 Content-Type: multipart/alternative; boundary="----=_Part_33594_1438869695.1528125292356" ------=_Part_33594_1438869695.1528125292356 Content-Type: text/plain; charset="UTF-8" A more limited change to the sorts made available is adding a discrete suffix array function. For the uninitiated, a suffix array is unlike a typical sorting algorithm in two respects: the returned object is a sequence 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 reference's following value in the original container with the terminal value being the global minimum value. The two significant algorithms for generating suffix arrays right now are 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, _Bidirectional_Iterator end, _Output_Iterator out); This would have applications in compression, text searching, and sequence alignment. -- 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 email 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/da9287b6-3218-445a-b079-6b9bf37f4060%40isocpp.org. ------=_Part_33594_1438869695.1528125292356 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
A more limited change to the sorts made available is = adding a discrete suffix array function.=C2=A0 For the uninitiated, a suffi= x array is unlike a typical sorting algorithm in two respects: the returned= object is a sequence of indexes or reference into the original container, = and in the case of ties, subordering is dictated by a comparison of each in= dex's or reference's following value in the original container with= the terminal value being the global minimum value.

The two significant algorithms for generating suffix arrays right now are= SACA-K and divsufsort.

I think a good call interf= ace for this would be as follows:

template< typ= ename _Bidirectional_Iterator, typename _Output_Iterator >
voi= d get_suffix_array(_Bidirectional_Iterator begin, _Bidirectional_Iterator e= nd, _Output_Iterator out);

This would have applica= tions in compression, 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/da9287b6-3218-445a-b079-6b9bf37f4060= %40isocpp.org.
------=_Part_33594_1438869695.1528125292356-- ------=_Part_33593_124879047.1528125292355-- .