------=_Part_500_486599972.1467118351452
Content-Type: multipart/alternative;
 boundary="----=_Part_501_987269427.1467118351453"

------=_Part_501_987269427.1467118351453
Content-Type: text/plain; charset=UTF-8


Hi folks

It would be great to have general binary search tool on a general predicate
rather than on value like for the lower_bound.
I would put it to std::find_if family of functions.
Am I missing something or is something like this already in standard?

/*

Definition:
UnaryPredicate is called  PartitionedUnaryPredicate  iff

this condition holds:

for all it1,it2  if p(*it1) is false  and  p(*it2) is true  implies
it1<it2

(all false indices precede all true indices)

find_if_partitioned returns the lowest iterator it for which p(*it) is true
or last if no such iterator it exist.
generalization of lower_bound
logarithmic complexity, binary search
*/

template<class ForwardIt, class T, class PartitionedUnaryPredicate>
ForwardIt find_if_partitioned(ForwardIt first, ForwardIt last,
PartitionedUnaryPredicate p)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first,last);

    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (p(*it))
            count = step
        else
        {
            first = ++it;
            count -= step + 1;
        }

    }
    return first;
}

I welcome early feedback, please.
Any opinions?

--
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/1812ee73-c9df-4cf5-a1fa-3800d16c5eff%40isocpp.org.

------=_Part_501_987269427.1467118351453
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br>Hi folks<br><br>It would be great to have general bina=
ry search tool on a general predicate rather than on value like for the low=
er_bound. <br>I would put it to std::find_if family of functions.<br>Am I m=
issing something or is something like this already in standard?<br><br>/*<b=
r><br>Definition:<br>UnaryPredicate is called=C2=A0 PartitionedUnaryPredica=
te=C2=A0 iff<br><br>this condition holds:<br><br>for all it1,it2=C2=A0 if p=
(*it1) is false=C2=A0 and=C2=A0 p(*it2) is true=C2=A0 implies =C2=A0 it1&lt=
;it2<br><br>(all false indices precede all true indices) <br><br>find_if_pa=
rtitioned returns the lowest iterator it for which p(*it) is true or last i=
f no such iterator it exist.<br>generalization of lower_bound<br>logarithmi=
c complexity, binary search<br>*/<br><br>template&lt;class ForwardIt, class=
 T, class PartitionedUnaryPredicate&gt;<br>ForwardIt find_if_partitioned(Fo=
rwardIt first, ForwardIt last, PartitionedUnaryPredicate p)<br>{<br>=C2=A0=
=C2=A0=C2=A0 ForwardIt it;<br>=C2=A0=C2=A0=C2=A0 typename std::iterator_tra=
its&lt;ForwardIt&gt;::difference_type count, step;<br>=C2=A0=C2=A0=C2=A0 co=
unt =3D std::distance(first,last);<br>=C2=A0<br>=C2=A0=C2=A0=C2=A0 while (c=
ount &gt; 0) {<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 it =3D first;<=
br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 step =3D count / 2;<br>=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 std::advance(it, step);<br>=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if (p(*it))<br>=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 count =3D step<br>=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 else<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 {<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 first =3D ++it;<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 count -=3D step + 1;<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 }<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <br>=C2=A0 =C2=A0=
 }<br>=C2=A0=C2=A0=C2=A0 return first;<br>}<br><br>I welcome early feedback=
, please.<br>Any opinions?<br><br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/1812ee73-c9df-4cf5-a1fa-3800d16c5eff%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/1812ee73-c9df-4cf5-a1fa-3800d16c5eff=
%40isocpp.org</a>.<br />

------=_Part_501_987269427.1467118351453--

------=_Part_500_486599972.1467118351452--

.

On 2016/06/28 21:52 +0900, Marian Klein wrote:
> It would be great to have general binary search tool on a general predicate
> rather than on value like for the lower_bound.
> I would put it to std::find_if family of functions.
> Am I missing something or is something like this already in standard?

std::partition_point?
https://www.google.com/search?q=std%3A%3Apartition_point

--
k_satoda

--
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/1ac61486-8976-10ed-db9f-ff680dcdac1d%40f2.dion.ne.jp.

.

thanks. I suspected I am missing something.
I really somehow never noticed this powerful function.



On 28 June 2016 at 17:45, Kazutoshi Satoda <k_satoda@f2.dion.ne.jp> wrote:
> On 2016/06/28 21:52 +0900, Marian Klein wrote:
>> It would be great to have general binary search tool on a general predicate
>> rather than on value like for the lower_bound.
>> I would put it to std::find_if family of functions.
>> Am I missing something or is something like this already in standard?
>
> std::partition_point?
> https://www.google.com/search?q=std%3A%3Apartition_point
>
> --
> k_satoda
>
> --
> 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/1ac61486-8976-10ed-db9f-ff680dcdac1d%40f2.dion.ne.jp.

--
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/CAA0DKYq5rX-KGFb%2B97xQm9Va8omr%3Dh-6v0duyEng_yYpQsZAzQ%40mail.gmail.com.

.

Hi Kazutoshi

I have a related questions. Sometimes problems are expressed via
indiced rather than pointers or iterators.

I would like to wrap std::partition_point  like this:

template <class indexT, class UnaryPredicate>
indexT partition_point_index(indexT first,indexT last,UnaryPredicate
p)  //true,true,true,false,false...
{
 return *std::partition_point(
IndexForwardIterator<indexT>(first),IndexForwardIterator<indexT>(last),p);
}

where IndexForwardIterator is Iterator wrapper around index.

template <class T>
struct IndexForwardIterator
{
  typedef std::forward_iterator_tag iterator_category;
//Iterator concept
  typedef T value_type;
  typedef T difference_type;
  typedef T pointer;
  typedef T& reference;
  IndexForwardIterator(const IndexForwardIterator& other):val(other.val) {}
  IndexForwardIterator& operator =(const IndexForwardIterator& other){
val=other.val; return *this;}
  //void swap(const IndexForwardIterator& other) ; //default swap should work
//EqualityComparable
  bool operator ==( const IndexForwardIterator& other) { return
val==other.val; }
//Input Iterator
  bool operator !=( const IndexForwardIterator& other) { return
val!=other.val; }
  T& operator* () { return val; }
//  T* operator-> () { return pData; } //?
  IndexForwardIterator& operator ++() { ++val; return *this; }
  IndexForwardIterator operator ++(int) { T tmp=val;val++; return
IndexForwardIterator(tmp);}
  //*i++
  //Default Constructible
  IndexForwardIterator():val(0) {};
  IndexForwardIterator(T val0):val(val0) {};

  T val;
};

I don't really would like to always define this Iterator wrapper. Is
it something similar in standard?

What is the standard or recommended technique to convert between
indices and iterators?

 Marian


On 28 June 2016 at 20:30, Marian Klein <mkleinsoft@gmail.com> wrote:
> thanks. I suspected I am missing something.
> I really somehow never noticed this powerful function.
>
>
>
> On 28 June 2016 at 17:45, Kazutoshi Satoda <k_satoda@f2.dion.ne.jp> wrote:
>> On 2016/06/28 21:52 +0900, Marian Klein wrote:
>>> It would be great to have general binary search tool on a general predicate
>>> rather than on value like for the lower_bound.
>>> I would put it to std::find_if family of functions.
>>> Am I missing something or is something like this already in standard?
>>
>> std::partition_point?
>> https://www.google.com/search?q=std%3A%3Apartition_point
>>
>> --
>> k_satoda
>>
>> --
>> 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/1ac61486-8976-10ed-db9f-ff680dcdac1d%40f2.dion.ne.jp.

--
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/CAA0DKYoFUoKFeAhdCqsinKgZJb-xN8v%3DhnBkjsgLspBA-PY4%2BA%40mail.gmail.com.

.

On 2016/06/29 6:07 +0900, Marian Klein wrote:
> I would like to wrap std::partition_point  like this:
>
> template <class indexT, class UnaryPredicate>
> indexT partition_point_index(indexT first,indexT last,UnaryPredicate
> p)  //true,true,true,false,false...
> {
>  return *std::partition_point(
> IndexForwardIterator<indexT>(first),IndexForwardIterator<indexT>(last),p);
> }
>
> where IndexForwardIterator is Iterator wrapper around index.
....
> What is the standard or recommended technique to convert between
> indices and iterators?

boost::counting_iterator?
http://www.boost.org/doc/libs/release/libs/iterator/doc/counting_iterator.html

I looked for a proposal (to the standard) which has something like this,
but there seems no such proposal.

--
k_satoda

--
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/4722655e-6063-a8fb-9768-8b76cdf5ec58%40f2.dion.ne.jp.

.