November 05, 2006
Bill Baxter wrote:
> Bill Baxter wrote:
>> Sean Kelly wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> Still, I think it's useful to have in an iterator, so perhaps something roughly like this:
>>>>
>>>> interface Iterator(T)
>>>> {
>>>>     T val();
>>>>     T next();
>>>>     bool hasNext();
>>>> }
>>>
>>>
>>>
>>> Err... this doesn't work for an iterator returned for an empty container.  
>>
>>
>> It's fine if you define the behavior to be that you have to call next() once to get the first value.  So for iteration idiom becomes:
>>
>> T v;
>> while(c.hasNext()) )
>> {
>> }
> 
> ....another victem of Ctrl+Enter....
> 
> while(c.hasNext())
> {
>    T v = c.next();
> }
> 
> I think an alias for T also needs to be a part of the definition of the iterator.  Like  alias T value_type.

I don't think it's necessary, but it may be convenient.  For example, this should work:

typeof(c.next());

but that obviously requires an instance of the iterator.  And it's perhaps a bit confusing.

> Also would do you do a mutating iteration over collections of basic value types (eg floats), structs, and classes?  I.e. if you want to do something like:
> 
> while(c.hasNext())
> {
>    T v = c.next();
>    v += 2;
> }
> where T could be float, struct, or class.  Ok, class case is fine, but the other two aren't clear to me.  Mutable iterator over structs could maybe return a pointer to each struct.  Basic value type, I'm not sure.  Just woke up though... maybe it's obvious and my head just isn't working yet.

Yeah, perhaps returning a pointer is better.  The lack of reference types in D can make things like this a bit awkward.
November 05, 2006
Sean Kelly wrote:
> Bill Baxter wrote:
> 
>> Sean Kelly wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> Still, I think it's useful to have in an iterator, so perhaps something roughly like this:
>>>>
>>>> interface Iterator(T)
>>>> {
>>>>     T val();
>>>>     T next();
>>>>     bool hasNext();
>>>> }
>>>
>>>
>>>
>>> Err... this doesn't work for an iterator returned for an empty container.  
>>
>>
>> It's fine if you define the behavior to be that you have to call next() once to get the first value.  So for iteration idiom becomes:
>>
>> T v;
>> while(c.hasNext()) )
>> {
>> }
> 
> 
> Yup, but this seems confusing with the presence of val() methods.

I'm not sold on val() yet.  :-)

--bb
November 06, 2006
Bill Baxter wrote:
> Sean Kelly wrote:
>> Bill Baxter wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> Sean Kelly wrote:
>>>>
>>>>> Still, I think it's useful to have in an iterator, so perhaps something roughly like this:
>>>>>
>>>>> interface Iterator(T)
>>>>> {
>>>>>     T val();
>>>>>     T next();
>>>>>     bool hasNext();
>>>>> }
>>>>
>>>>
>>>>
>>>> Err... this doesn't work for an iterator returned for an empty container.  
>>>
>>>
>>> It's fine if you define the behavior to be that you have to call next() once to get the first value.  So for iteration idiom becomes:
>>>
>>> T v;
>>> while(c.hasNext()) )
>>> {
>>> }
>>
>>
>> Yup, but this seems confusing with the presence of val() methods.
> 
> I'm not sold on val() yet.  :-)
> 
> --bb

For what it's worth, C# implements it like this:

    public interface IEnumerator
    {
	public bool MoveNext();
	public object Current { get; }
	public void Reset();
    }

It seems that MoveNext() must be called before Current becomes valid (assuming that there are any items in the collection).  If Current is accessed without having an object to return, it throws an exception.  So a while loop might look like:

    while (e.MoveNext())
    {
        object obj = e.Current;
        Console.WriteLine(obj);
    }

C#'s foreach loop also works with IEnumerator, as:

    foreach (object obj in c)
    {
        Console.WriteLine(obj);
    }

where c is an object that implements the IEnumerable interface, which has a single GetEnumerator() method.

I'm not suggesting that D do the same thing as C#, but I thought that some of the above might be relevant to this discussion.

-Dave
November 06, 2006
Sean Kelly wrote:
> Walter Bright wrote:
> 
>> Sean Kelly wrote:
>>
>>> I think I agree, but for the sake of argument, how would D handle 'find'  operations on sequences that don't support opIndex?  At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms.  Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach.  Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice.  I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it.
>>
>>
>> I think the target types will have to support opIndex or opSlice.
> 
> 
> Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators.
> 
> For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N.  By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N).  In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets.
> 
> In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead.  With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees?  The complexity for such an operation would be M(log(M)) + N(log(N)).
> 
>  From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used.  What alternatives do we have?  So far, iterator variants are all I've been able to come up with.
> 
> 
> Sean

I have created a monster!!!


// a class that can iterate over it's contents and another
// iterator's contents in order

class Foo
{

	// return an iterator
 int delegate(int delegate(inout U))
       opApplyWith(int delegate(inout U) t)
 {
	// make a class to form delegate
  auto ret = new class
  {
	// context
   int delegate(inout U) t;

	// iterator
   int ret(int delegate(inout U) dg)
   {
    int i=0;
	// loop on other
    foreach(inout U u, t)
    {
	// sub loop on self
     while(i<sortedUs.length && sortedUs[i] < u)
      if(int r = dg(sortedUs[i++])) return r;
     if(int r = dg(u)) return r;
    }

   }
  };
	// set context
  ret.t = t;
	// return it
  return &ret.ret;
 }

	// loop on self only
 int opApply(int delegate(inout U) dg)
 {
  foreach(inout U u, sortedUs)
  {
   if(int r = dg(sortedUs[i++])) return r;
  }
 }

	// data for class
 U[] sortedUs;
}

	// use it.
int main()
{
 Foo f1, f2;
 foreach(U u; f1.opApplyWith(&f2.opApply))
 {
  use(u);
 }
}
November 06, 2006
BCS wrote:

> I have created a monster!!!

Sure!  Why not?
opApplyWith is surely no less useful than opApplyReverse. ;-)
Oh, but we probably need opApplyWithReverse now too.  :-)

--bb
November 07, 2006
Bill Baxter wrote:
> BCS wrote:
> 
>> I have created a monster!!!
> 
> 
> Sure!  Why not?
> opApplyWith is surely no less useful than opApplyReverse. ;-)
> Oh, but we probably need opApplyWithReverse now too.  :-)
> 
> --bb


Ahh. Err. I wasn't suggesting that foreach_with() be added, it just looked like a good name. I could have named it "Bob" and it would still do what I was intending but then no one would known right off what it is supposed to do.

The though is that making some sort of delegate/thunk/closure as an iterator can provide a lot of different iteration type patterns.
7 8 9 10 11 12 13 14 15 16 17
Next ›   Last »