Why Strings as Classes?

[Robert Fraser]

superdan wrote:
> Christopher Wright Wrote:
> 
>> superdan wrote:
>>>> class LinkedList(T)
>>>> {
>>>> 	Node!(T) head;
>>>>
>>>> 	/** Gets the ith item of the list. Throws: SIGSEGV if i >= length of 
>>>> the list. Time complexity: O(N) for a list of length N. This operation 
>>>> is provided for completeness and not recommended for frequent use in 
>>>> large lists. */
>>>> 	T opIndex(int i)
>>>> 	{
>>>> 		auto current = head;
>>>> 		while (i)
>>>> 		{
>>>> 			current = current.next;
>>>> 		}
>>>> 		return current.value;
>>>> 	}
>>>> }
>>> oopsies. houston we got a problem here. problem is all that pluggable sort business works only if it can count on a constant time opIndex. why? because sort has right in its spec that it takes o(n log n) time. if u pass LinkedList to it you obtain a nonsensical design that compiles but runs afoul of the spec. because with that opIndex sort will run in quadratic time and no amount of commentin' is gonna save it from that.
>> WRONG!
>> Those sorting algorithms are correct. Their runtime is now O(n^2 log n) 
>> for this linked list.
> 
> you got the wrong definition of correct. sort became a non-scalable algo from a scalable algo. whacha gonna say next. bubble sort is viable?!?

No, YOU got the wrong definition of correct. "Correct" and "scalabale" 
are different words. As are "correct" and "viable". In Java, I've been 
known to index into linked lists... usually ones with ~5 elements, but 
I've done it.

>>> this design is a stillborn.
>>>
>>> what needs done is to allow different kinds of containers implement different interfaces. in fact a better way to factor things is via iterators, as stl has shown.
>> You didn't ask for an O(1) opIndex on a linked list. You asked for a 
>> correct opIndex on a linked list.
> 
> the correct opIndex runs in o(1).

No, the SCALABLE opIndex runs in O(1). The CORRECT opIndex can run in 
O(n^n) and still be correct.

>> Any sorting algorithm you name that 
>> would work on an array would also work on this linked list. Admittedly, 
>> insertion sort would be much faster than qsort, but if your library 
>> provides that, you, knowing that you are using a linked list, would 
>> choose the insertion sort algorithm.
> 
> no. the initial idea was for a design that allows that cool mixing and matching gig thru interfaces without knowing what is where. but ur design leads to a lot of unworkable mixing and matching.

Again, WORKABLE, just not SCALABLE. You should wrap your head around 
this concept, since it's been around for about 30 years now.

> it is a stillborn design.

Tell that to Java, the world's most used programming language for new 
projects. Or C#, the world's fastest growing programming language. Or 
Tango, one of D's standard libraries.

> my point was opIndex should not be written for a list to begin with.

Yes it should be. Here's a fairly good example: Say you have a GUI 
control that displays a list and allows the user to insert or remove 
items from the list. It also allows the user to double-click on an item 
at a given position. Looking up what position maps to what item is an 
opIndex. Would this problem be better solved using an array (Vector)? 
Maybe. Luckily, if you used a List interface throughout your code, you 
can change one line, and it'll work wither way.

> wrong. you only need to define your abstract types appropriately. e.g. stl defines forward and random iterators. a forward iterators has ++ but no []. random iterator has both. so a random iterator can be substituted for a forward iterator. but not the other way. bottom line, sort won't compile on a forward iterator. your design allowed it to compile. which makes the design wrong.

STL happens to be one design and one world-view. It's a good one, but 
it's not the only one. My main problem with the STL is that it takes 
longer to learn than the Java/.NET standard libraries -- and thus the 
cost of a programmer who knows it is higher. But there are language 
considerations in there too, and this is a topic for another day.

> btw my respect for tango improved when i found no opIndex in their list container.

http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/LinkSeq.d#L176