220 38517 <0c4b217f-7f50-478f-b82d-3931122fc543@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: joshua.r.marshall.1991@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding Sorting with suffix subordering for suffix arrays Date: Wed, 6 Jun 2018 04:03:17 -0700 (PDT) Lines: 84 Approved: news@gmane.org Message-ID: <0c4b217f-7f50-478f-b82d-3931122fc543@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_46960_1204789278.1528282997107" X-Trace: blaine.gmane.org 1528282872 10336 195.159.176.226 (6 Jun 2018 11:01:12 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 6 Jun 2018 11:01:12 +0000 (UTC) Cc: joshua.r.marshall.1991@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCFIZIPVQEORB5X633MAKGQEQPQUPLA@isocpp.org Wed Jun 06 13:01:08 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 1fQWBg-0002bd-8E for gclcip-std-proposals@m.gmane.org; Wed, 06 Jun 2018 13:01:08 +0200 Original-Received: by mail-yw0-f198.google.com with SMTP id s23-v6sf4200737ywg.21 for ; Wed, 06 Jun 2018 04:03:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc: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=eLW2KQKARG4CCQXtvQ/yzNm50daQB3E3WOp9zP6jNlM=; b=xMFfrvJA6eHlmWhDEw78VZmlmgY092redh2upEiJKP5tTs7ZerdWw7SCFjxgASQohm 8VqQlW6gE45oN/HOiAW15HW4UYZ5pERbSWe1cl/AwhyXYhVHP2ZpIRpaaVS2UIUAFncM /Vka37xTxIvkRGanMKlCWmItakwZX4zBvhAw5VjytJDwwV7iZT3oN76Rwl1dhR8HwrkG qqVhOmxnbuyaBtL9ZzgwEc2pcWMlWdBLew8uI/IONbxBywynG+/b52LY7qk/hlOOKROA vve7C9ucwuKD1O0C/DhtdkR7gcSXgDJT8H9S8Zt2IiDsGyB4Aanwwi6Cu4QpiY1cQLCE JUpg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc: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=eLW2KQKARG4CCQXtvQ/yzNm50daQB3E3WOp9zP6jNlM=; b=LimrCqLEw4fkKzO/BMHsqe5iYjXAWA2H6pzIAIcoEeM10/YdJstRJq818l7A+8bCIL FeuMLyfpnVaTtqLB4sgw/5h9rwNq9OAt1LoPP4UAeKfJQ49pUJhr5OsugeTcguNsFyjM puQVOfDdsdBgiVyhwnoNMXqX9VZ+GDXzYtkgO7a+GGSEDX4PAwbhm/wcSh/heJcNay1R UCJlJaFi1tG1VKgwroPzsR5bddRXSZLVThO9paZpsFhUhGEhWAOtLV/+e9b+CdovPG33 P3mbAtSLTbFd1O/kW7yb8URLB3oviqSI+5aNJglJelpxgMS/lbWYh3OR4jwaGsXd5Nr1 7K3g== 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:cc: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=eLW2KQKARG4CCQXtvQ/yzNm50daQB3E3WOp9zP6jNlM=; b=FXuo4LThgX0g+I1faOL5Q3DSMH+v/uIrFwoOpZaeqtSVUu+OUjVBeLmCy2qSGFwpT2 l+0c9dFlI9Jd3+aNE9TdRpORhmT9+rT/jLFkEthM39bYXETkTCkZog3ELH4mkWKi3CV4 J8ZbM9nDpG3gRlxrTQ2zG1hqOOROyftLzL5p2vjmZ5gm6A9WR69+q4VlTXBQhJaQnV75 idI7+u+bCjiBRQ+Zpo7aoRByONEb0Q8H2GyL/HIc+2J6fe126JsMOe07GrY78j36YooK PvgzsWFt5T9j1RmwMMaAjJM6cDAEUQEHvm4TUBSmOaEFJacFeo0vGJ9KaWRildj+Am8S aixQ== X-Gm-Message-State: APt69E1PwsKbh7bkxzzkUhnRCpQvUuTEGbJ+qAheQRw1LnpMDyksEC69 ot89qKP5XCoCp4rXWbFkNdOw/Q== X-Google-Smtp-Source: ADUXVKJl0VTxu2C4Mgg3mJbHjqKt7lYEJXYEPCKc2erlz7hcS7KBi5yxzQWet9GKCnhgxmnRdDSAtw== X-Received: by 2002:a25:7004:: with SMTP id l4-v6mr713158ybc.84.1528282999018; Wed, 06 Jun 2018 04:03:19 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a81:5383:: with SMTP id h125-v6ls4418330ywb.36.gmail; Wed, 06 Jun 2018 04:03:17 -0700 (PDT) X-Received: by 2002:a0d:df10:: with SMTP id i16-v6mr109651ywe.9.1528282997580; Wed, 06 Jun 2018 04:03:17 -0700 (PDT) In-Reply-To: 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:38517 Archived-At: ------=_Part_46960_1204789278.1528282997107 Content-Type: multipart/alternative; boundary="----=_Part_46961_1380035335.1528282997108" ------=_Part_46961_1380035335.1528282997108 Content-Type: text/plain; charset="UTF-8" If there is nothing more to say on this, I'll go ahead and add a proposal for the feature. On Monday, June 4, 2018 at 11:14:52 AM UTC-4, joshua.r.ma...@gmail.com wrote: > > 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/0c4b217f-7f50-478f-b82d-3931122fc543%40isocpp.org. ------=_Part_46961_1380035335.1528282997108 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
If there is nothing more to say on this, I'll go ahead= and add a proposal for the feature.

On Monday, June 4, 2018 at 11:1= 4:52 AM UTC-4, joshua.r.ma...@gmail.com wrote:
A more limited change to the sorts ma= de available is adding a discrete suffix array function.=C2=A0 For the unin= itiated, a suffix array is unlike a typical sorting algorithm in two respec= ts: the returned object is a sequence of indexes or reference into the orig= inal container, and in the case of ties, subordering is dictated by a compa= rison of each index's or reference's following value in the origina= l container with the terminal value being the global minimum value.

The two significant algorithms for generating suffix arra= ys 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 &g= t;
void get_suffix_array(_Bidirectional_Iterator begin, _Bid= irectional_Iterator end, _Output_Iterator out);

Th= is would have applications in compression, text searching, and sequence ali= gnment.

--
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/0c4b217f-7f50-478f-b82d-3931122fc543= %40isocpp.org.
------=_Part_46961_1380035335.1528282997108-- ------=_Part_46960_1204789278.1528282997107-- .