Robert Fraser:
> It's a good feature to have (I wouldn't consider a list class complete without it), it just shouldn't be abused.

Its code:

final Ref nth (int n) {
    auto p = this;
    for (int i; i < n; ++i)
        p = p.next;
    return p;
}

If the usage patterns show this is positive, then a static pointer/index pair may be added, that keeps the last accessed pointer/index, this may speed up things if the items are accessed sequentially, or even if they are accessed with some several forward skips, avoiding starting from the beginning each time :-)

Bye,
bearophile

On Wed, 27 Aug 2008 21:23:53 +0400, bearophile <bearophileHUGS@lycos.com> wrote:

> Robert Fraser:
>> It's a good feature to have (I wouldn't consider a list class complete
>> without it), it just shouldn't be abused.
>
> Its code:
>
> final Ref nth (int n) {
>     auto p = this;
>     for (int i; i < n; ++i)
>         p = p.next;
>     return p;
> }
>
> If the usage patterns show this is positive, then a static pointer/index pair may be added, that keeps the last accessed pointer/index, this may speed up things if the items are accessed sequentially, or even if they are accessed with some several forward skips, avoiding starting from the beginning each time :-)
>
> Bye,
> bearophile

I believe this breaks encapsulation, unless an iterator is returned and passed as a start. Find is a better name for such operation.

Denis Koroskin:
> I believe this breaks encapsulation,

You may be right, I'm learning such thematic still. Can you explain why do you think it breaks information hiding? The two static variables are inside the method, and they can't be seen from outside.

Bye and thank you,
bearophile

"Denis Koroskin" <2korden@gmail.com> wrote in message news:op.ugj2yeu0o7cclz@proton.creatstudio.intranet...
> On Wed, 27 Aug 2008 21:23:53 +0400, bearophile <bearophileHUGS@lycos.com> wrote:
>
>> Robert Fraser:
>>> It's a good feature to have (I wouldn't consider a list class complete without it), it just shouldn't be abused.
>>
>> Its code:
>>
>> final Ref nth (int n) {
>>     auto p = this;
>>     for (int i; i < n; ++i)
>>         p = p.next;
>>     return p;
>> }
>>
>> If the usage patterns show this is positive, then a static pointer/index pair may be added, that keeps the last accessed pointer/index, this may speed up things if the items are accessed sequentially, or even if they are accessed with some several forward skips, avoiding starting from the beginning each time :-)
>>
>> Bye,
>> bearophile
>
> I believe this breaks encapsulation, unless an iterator is returned and passed as a start. Find is a better name for such operation.

The way I see it, encapsulation is all about the black box idea. And the only things you can see from outside the black box are the inputs and outputs. So, if encapsulation is desired, things like "Indexing" and "Find" should be considered black boxes (ie, encapsulation). And if "Indexing" and "Find" are black boxes, that means as defining them purely in terms of the relationship between their input and output. So this is how I consider them to be defined:

Indexing: Return the element at position N.
Find: Return the position of the element that is equal (value-equal or
identity-equal, depending on the find) to X .

So if there's a function that returns the element at position N and you call it "find" just because of the *internal implementation* of the function is an incrementing loop, I consider that to be both a violation of encapsulation (because the name has been chosen based on the inner workings of the function, not it's input-output relationship) and a violation of the definitions.

On Wed, 27 Aug 2008 17:08:47 -0400, Nick Sabalausky wrote:

> The way I see it, encapsulation is all about the black box idea. And the only things you can see from outside the black box are the inputs and outputs.

Well said.

> Indexing: Return the element at position N.
> Find: Return the position of the element that is equal (value-equal or
> identity-equal, depending on the find) to X .

Exactly.

> So if there's a function that returns the element at position N and you call it "find" just because of the *internal implementation* of the function is an incrementing loop, I consider that to be both a violation of encapsulation (because the name has been chosen based on the inner workings of the function, not it's input-output relationship) and a violation of the definitions.

Not to mention just plain confusing.

-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell

Derek Parnell Wrote:

> On Wed, 27 Aug 2008 17:08:47 -0400, Nick Sabalausky wrote:
> 
> > The way I see it, encapsulation is all about the black box idea. And the only things you can see from outside the black box are the inputs and outputs.
> 
> Well said.

I am sorry I will say my opinion. This sounds good but is simplistic. Black box is good in principle. But it assume you found right interface for the black box. If you define bad interface you have a bad black box. Also please remember that iterator is black box also. But it defines right interface.

> > Indexing: Return the element at position N.
> > Find: Return the position of the element that is equal (value-equal or
> > identity-equal, depending on the find) to X .
> 
> Exactly.
> 
> > So if there's a function that returns the element at position N and you call it "find" just because of the *internal implementation* of the function is an incrementing loop, I consider that to be both a violation of encapsulation (because the name has been chosen based on the inner workings of the function, not it's input-output relationship) and a violation of the definitions.
> 
> Not to mention just plain confusing.

I am confused to. Why is making [] do find good and making find do [] wrong? How do you make decision? To me it looks the opposite way. Because find is less demanding contract than []. In design a stronger contract can replace a weaker contract. Not the inverse. Thank you, Dee Girl

Dee Girl wrote:
> I am confused to. Why is making [] do find good and making find do [] wrong? How do you make decision? To me it looks the opposite way. Because find is less demanding contract than []. In design a stronger contract can replace a weaker contract. Not the inverse. Thank you, Dee Girl

Choosing the data structure used is never the job of the code you're giving the data to. It's the job of whatever creates the data structure. By giving two functions where the only difference is performance guarantees, you're allowing the called code to determine what data structures it accepts, not based on the operations the structure supports, but based on the performance of those data structures.

D's standard arrays are a bad example of this: since they're built in, everyone uses them, so it's difficult to replace them with a linked list or something else. The effect is more pronounced with associative arrays, since there isn't as much choice in lists as in dictionaries. But they're so damn useful, and the syntax is hard to match.

Christopher Wright Wrote:

> Dee Girl wrote:
> > I am confused to. Why is making [] do find good and making find do [] wrong? How do you make decision? To me it looks the opposite way. Because find is less demanding contract than []. In design a stronger contract can replace a weaker contract. Not the inverse. Thank you, Dee Girl
> 
> Choosing the data structure used is never the job of the code you're giving the data to.

Yes. But code should refuse data if data does not respect an interface.

I think binary_search never should work on list. It does really bad thing when linear search is the correct thing. Do you think it should?

> It's the job of whatever creates the data structure. By giving two functions where the only difference is performance guarantees, you're allowing the called code to determine what data structures it accepts, not based on the operations the structure supports, but based on the performance of those data structures.

I do not think there is anything wrong. And for me performance and complexity is very different words. Performance is like dmd -O -release against dmd -debug. Or asm implementation of function. Complexity is very different thing and essential for algorithm.

> D's standard arrays are a bad example of this: since they're built in, everyone uses them, so it's difficult to replace them with a linked list or something else. The effect is more pronounced with associative arrays, since there isn't as much choice in lists as in dictionaries. But they're so damn useful, and the syntax is hard to match.

I hope Walter adds new data structure that work with std.algorithm. I am not sure. But I think std.algorithm is make so it works with other types. Not only arrays.

Dee Girl Wrote:

> Christopher Wright Wrote:
> 
> > Dee Girl wrote:
> > > I am confused to. Why is making [] do find good and making find do [] wrong? How do you make decision? To me it looks the opposite way. Because find is less demanding contract than []. In design a stronger contract can replace a weaker contract. Not the inverse. Thank you, Dee Girl
> > 
> > Choosing the data structure used is never the job of the code you're giving the data to.
> 
> Yes. But code should refuse data if data does not respect an interface.
> 
> I think binary_search never should work on list. It does really bad thing when linear search is the correct thing. Do you think it should?
> 
> > It's the job of whatever creates the data structure. By giving two functions where the only difference is performance guarantees, you're allowing the called code to determine what data structures it accepts, not based on the operations the structure supports, but based on the performance of those data structures.
> 
> I do not think there is anything wrong. And for me performance and complexity is very different words. Performance is like dmd -O -release against dmd -debug. Or asm implementation of function. Complexity is very different thing and essential for algorithm.

cool. dee there's two things u said i like. one was the contract view of complexity guarantee. after all o(n) is a weaker guarantee than o(1). and heck nobody complain if someone comes with sort that works in o(n log log n). so there's some sort of complexity hierarchy. never thot of it that way. that's as cool as the other side of the pillow.

2nd thing i liked was the performance vs. complexity contrast. linear search in ruby has less performance than linear search in d. but both have the same complexity. that's universal. spot on girl. good food for thot while i get drunk at tgiw. thanx.

Dee Girl wrote:
> Christopher Wright Wrote:
> 
>> Dee Girl wrote:
>>> I am confused to. Why is making [] do find good and making find do [] wrong? How do you make decision? To me it looks the opposite way. Because find is less demanding contract than []. In design a stronger contract can replace a weaker contract. Not the inverse. Thank you, Dee Girl
>> Choosing the data structure used is never the job of the code you're giving the data to.
> 
> Yes. But code should refuse data if data does not respect an interface.

Correct. The question is whether you should make asymptotic complexity part of the interface. If you do, that hurts when you want to optimize for a common case but still allow some inefficient operations.

If you want to define some empty interfaces, such as:
interface IFastIndexList : IList {}

These would allow you to do things like:
bool containsSorted (IList list, Object element)
{
	auto fast = cast(IFastIndexList)list;
	if (fast) return (binarySearch(list, element) >= 0);
	// default implementation here
}

However, your library should not have any publicly exposed operations that only take IFastIndexList, and it's silly to define different functions for indexing in an IFastIndexList versus an IList.

> I think binary_search never should work on list. It does really bad thing when linear search is the correct thing. Do you think it should?

I think it should work, since the data structure implements the necessary operations. I think no sensible programmer should use it.

>> It's the job of whatever creates the data structure. By giving two functions where the only difference is performance guarantees, you're allowing the called code to determine what data structures it accepts, not based on the operations the structure supports, but based on the performance of those data structures.
> 
> I do not think there is anything wrong. And for me performance and complexity is very different words. Performance is like dmd -O -release against dmd -debug. Or asm implementation of function. Complexity is very different thing and essential for algorithm.
> 
>> D's standard arrays are a bad example of this: since they're built in, everyone uses them, so it's difficult to replace them with a linked list or something else. The effect is more pronounced with associative arrays, since there isn't as much choice in lists as in dictionaries. But they're so damn useful, and the syntax is hard to match.
> 
> I hope Walter adds new data structure that work with std.algorithm. I am not sure. But I think std.algorithm is make so it works with other types. Not only arrays. 

You can do that with templates. If you want to use classes with inheritance, or interfaces, you can no longer use templates.