Squeak-dev September 2002

squeak-dev@lists.squeakfoundation.org

165 participants
288 discussions

Start a nNew thread

None
by None 28 Sep '02

28 Sep '02

1 0

[FIX] SortedCollectionFix-sr v2
by Stephan Rudlof 28 Sep '02

28 Sep '02

" Change Set: SortedCollectionFix-sr v2 Date: 28 September 2002 Author: Stephan Rudlof This is an evolutionary fix/extension of SortedCollection: - >>copyFrom:to: should use the sortBlock of the receiver instead of the default nil sortBlock; - >>addLast: should be forbidden as >>addFirst is already; - >>addLastWithoutSorting has been introduced as 'private' method for constructing a copy by the newly introduced >>copyFrom:to:. - clients fixed, which have send >>addLast to SortedCollections before: - IndexFile>>readFrom:messageFile: has to be tested (see method comment), ideally by a Celeste maintainer, - Dictionary>>keysSortedSafely has been fixed (it could break the class invariant of SortedCollection, if its internal implementation would change) without a relevant performance loss; - class>>withAll:sortBlock: is a new 'instance creation' method. Rationale: I'm expecting an OrderedCollection, if I'm sending >>addLast:. ANSI v1.9 supports this view: it says, that >>addLast: behaves only to the protocol <OrderedCollection> and the protocol of <SortedCollection> does *not* conform to this protocol. >>addLast should always work for OrderedCollections, but it would only work in *rare* cases for SortedCollections. So I'm against making it work for these rare cases for SortedCollections. BTW: I'm not against introducing something like >>addAllProbablyPresorted:, but I don't do it here. Note: there are other changeset with SortedCollection fixes (dealing with e.g. >>addLast:), but they haven't reached Squeak3.2 yet. History: v2 : - no client has to call >>addLastWithoutSorting anymore, it is just a private method used by its own class now (in >>copyFrom:to:), - proposal of Richard added, cs comment changed and extended v1 : first version There is an interesting proposal of Richard A. O'Keefe, which hasn't been implemented yet (I have changed doublequotes to double doublequotes): --------------------------------------------------------------- I think it's time to talk about lazy data structures. We could add elements fast to SortedCollections like this. 1. The internal representation is an array partitioned thus: +----+------------+--------+----+ |1 |a z| x| n| +----+------------+--------+----+ elements 1..a-1 : all nil elements a..z : sorted according to sortBlock elements z+1..x : added elements not sorted yet elements x+1..n : all nil Where I have written ""a"" and ""x"" you should understand the existing instance variables of OrderedCollection (inherited by SortedCollection) being used instead; the ""z"" instance variable is new. 2. add: anItem ^super addLast: anItem addFirst: anItem self shouldNotImplement addLast: anItem self shouldNotImplement addAll: aCollection ^super addAllLast: aCollection addAllFirst: aCollection self shouldNotImplement addAllLast: aCollection self shouldNotImplement No, I'm not being inconsistent here. I'm saying ""let someone build a sorted collection in linear time if they can provide the elements in sorted order."" With this kind of implementation, #add: _is_ adequate for the job. 3. A strictly private method would exist: pvtEnsureAllSorted ""rather like current addAll:"" x = z ifTrue: [^array]. self pvtSortAddedElements. ""sorts z+1..x"" self pvtMerge. ""merges a..z with z+1..x"" z := x. ^array Ideally pvtSortAddedElements would use a method which is linear when the elements are sorted already; Dijkstra's smooth-sort is just one of many algorithms which are good at that, bottom-up natural merge is easier to understand and works very well in practice. Using bottom-up natural merge, if you add M elements to a Sorted Collection having N elements and then look at the result, the adds would cost O(M) time, pvtEnsureAllSorted would cost O(M) for pvtSortAddedElements and O(M+N) for pvtMerge, for a total O(N+M). Building an entire collection from N=0 would thus be O(M). 4. Other methods would call pvtEnsureAllSorted, e.g. at: index self assert: [index between: 1 and: x-a+1]. ^self pvtEnsureAllSorted at: index-a+1 do: aBlock self pvtEnsureAllSorted. ^super do: aBlock 5. Setting the sortblock would simply enlarge the unsorted area: sortBlock: aBlock sortBlock := aBlock ifNil: [nil] ifNotNil: [aBlock fixTemps]. z := a-1. This is the clean way to do it. The class invariant is weakened from ""the elements are always sorted"" to ""the elements are always sorted whenever anyone else looks; when noone else is looking they are in a convenient configuration for sorting."" From the outside, it looks as though the elements are always sorted. --------------------------------------------------------------- This may be an improvement to the current status. " -- Stephan Rudlof (sr(a)evolgo.de) "Genius doesn't work on an assembly line basis. You can't simply say, 'Today I will be brilliant.'" -- Kirk, "The Ultimate Computer", stardate 4731.3

1 0

Re: [FIX] SortedCollectionFix-sr
by Richard A. O'Keefe 28 Sep '02

28 Sep '02

- >>addLast: should be forbidden as >>addFirst is already; Why should addLast: or addFirst: be given a complete veto? Why not addFirst: anItem self isEmpty ifTrue: [^super addFirst: anItem]. (sortBlock ifNil: [anItem <= self first] ifNotNil: [sortBlock value: anItem value: self first] ) ifFalse: [ self error: 'new item would be out of order' ]. ^super addFirst: anItem. addLast: anItem self isEmpty ifTrue: [^super addLast: anItem]. (sortBlock ifNil: [self last <= anItem] ifNotNil: [sortBlock value: self last value: anItem] ) ifFalse: [ self error: 'new item would be out of order' ]. ^super addLast: anItem. This way we DON'T have to invent a new method to use when someone wants to build up a SortedCollection one element at a time and knows they can do it in the correct order, and we still don't allow these methods to spoil the order of the collection.

3 10

OT: An Udanax-Gold implimentation in Dolphin-ST
by Kevin Fisher 27 Sep '02

27 Sep '02

Hi folks: For any Xanadu fans out there, I just stumbled across this: http://www.night.dircon.co.uk/abora/index.html It is a preliminary implimentation of the Udanax-Gold specification in Dolphin Smalltalk (wonder how easy it would be to port to Squeak?). The fascinating part is the example--you can open an Ent Inspector on an example document "tree". It's nice to see some of this theory I've been reading about in actual practice! (sadly it is Windows-only :p, but neat nonetheless!)

3 4

Re: OOPSLA BOF scheduling
by Allen Wirfs-Brock 27 Sep '02

27 Sep '02

At 01:12 PM 9/26/2002 -0700, Avi Bryant wrote: >Will Camp Smalltalk definitely be set up somewhere (ie, in the exhibit >hall like last year) that an exhibits-only pass will get you into? If so, >maybe I'll cancel my registration... ;) > >Avi I can't comment on any individual's personal financial situation. However, broad application of this tactic could be very shortsighted. If OOPSLA continues to loose money (like I believe it did last year) then at some point ACM will discontinue it. If we want OOPSLA to continue as a venue for Squeak/Smalltalk activities then we need to support the conference by paying our way. Allen_Wirfs-Brock(a)Instantiations.com

3 2

Re: [FIX] SortedCollectionFix-sr
by Richard A. O'Keefe 27 Sep '02

27 Sep '02

I asked: > Why should addLast: or addFirst: be given a complete veto? and gave implementations of #addFirst: and #addLast: which complain only when the operation would violate the class invariant. Stephen Rudlof replied: The short answer ---------------- The current situation for SortedCollections - is inconsistent: >>addFirst: is forbidden, >>addLast: not; That was understood and assumed in my question. - semantically incorrect: using >>addLast: easily leads to a not sorted SortedCollection. That also was understood and assumed. My question is not "what is broken about the present situation", but "why not allow these operations to proceed whenever they can do so without breaking the class invariant?" To expand on this a little: why not give programmers a way to build a sorted collection in linear time when they are able to provide data in the right order? The longer answer ----------------- Prenote: your suggestion is *semantically* correct. But there are psychological/practical reasons against introducing it. Why does a programmer use #addLast:? He wants to build a Collection in an explicit order. Why does a programmer use a SortedCollection? He wants to have a Collection, which automatically ensures an order of added elements. There are several attitudes a class designer might take. The attitude I prefer is - operations should never be allowed to break class invariants - we should avoid introducing operations that often don't work - but when we are stuck with an operation that CAN be allowed to proceed some of the time we should not be strict bondage and discipline nannies and stop sensible programmers doing sensible things. The attitude here is - I am like God; I know exactly how programmers think and they mustn't. I can foresee every possible use and know which ones make sense. (OK, this is a caricature, but it is a recognisable one.) In this particular instance, it is possible for one and the same programmer, at a single instant in time, *BOTH* to want to build a collection in a particular order *AND* to want that collection to be a sorted collection. For example, support I have a sorted collection of numbers, call it "fred": fred := #(3 1 4 1 5 9 2 6 5) asSortedCollection. Now suppose I want to add 1 to every element. THIS IS AN ORDER-PRESERVING TRANSFORMATION. So jim := SortedCollection new. fred do: [:each | jim addLast: each + 1]. will do the job, IF I am allowed to use addLast: when it is safe. (Yes, I know I can do fred+1, but the result belongs to the wrong class.) Using >>addLast: for a SortedCollection means to try to give an explicit order to something, which has an automatically 'built in' one. This mostly is a programmer error. I am not sure how to interpret "mostly" here. If it is an empirical statement about how often it does happen, then I would be intrigued to know where the evidence came from. In the case where the two orders AGREE, which is the only case my versions of #addFirst: and #addLast: allow, it is not an error. In the case (of as far as I am aware completely unknown frequency) where the two orders do not agree, the error will still be reported. And it violates encapsulation: I have to know, which built in order the SortedCollection has, to use >>addLast: correctly along your suggestion. No, the sorting order of a sorted collection is part of its ***PUBLIC*** interface. Note that SortedCollection>>sortBlock is in the 'accessing' category, not the 'private' category. By using >>add: instead, there would be no problem. Yes there would. There would be an *EFFICIENCY* problem. Note that I too can claim a psychological reason why addLast: should be used in this case rather than add:. The reason is that in Set #add: means "add only if absent", whereas whenever addLast: is allowed it will make the collection one element bigger. So there remains the performance thing: using SortedCollection>>add: multiple times means, that each object has to be sorted in immediately. It is probably more performant to have a private add method, which just adds an element, while leaving the SortedCollection in an inconsistent state, and >>reSort it afterwards, when all elements have been added. "performant" is, to the best of my knowledge, not an English word. I certainly haven't been able to find it in any of the paper or electronic dictionaries I've just checked. Try "faster". That has been my idea of introducing the 'bypass' method for clients which really know about the internals. But the ordering used by a sorted collection is most definitely NOT a fact about its internals. It is in some respects the most public thing there is about such an object. Part of my point is that you don't *need* a bypass method when you have addLast: and could make it respect the class invariant. BTW: In the ANSI standard (revision 1.9) *protocol* <SortedCollection> doesn't conform to protocol <OrderedCollection>, which is the only one defining >>addFirst: and >>addLast:. This makes sense to me. The ANSI argument was shot down in smoke and billowing flames when I tried to apply it to #removeAll:, I don't see why it should have any greater force here. Nothing in the ANSI standard prevents you *adding* methods to standard classes; if it did, almost all of the methods in Object would have to find another home. Implementation notes -------------------- To the private SortedCollection>>addLastWithoutSorting: there could also be added - >>addWithoutSorting: and - >>addFirstWithoutSorting:; for - very few! - clients using the *internals*. After using one of these methods >>reSort should be called to ensure consistency. Note: I haven't proved the implicit assumption here, that >>reSort'ing an already sorted SortedCollection is faster than adding elements in arbitrary order. I suggest allowing methods to proceed that DON'T break the class invariant, and this is spurned as breaking encapsulation, even though the methods are concerned solely with matters in the public interface. Instead, as a better way, Rudlof proposes adding methods that DO break the class invariant, and DON'T offer any efficiency advantage. I think it's time to talk about lazy data structures. We could add elements fast to SortedCollections like this. 1. The internal representation is an array partitioned thus: +----+------------+--------+----+ |1 |a z| x| n| +----+------------+--------+----+ elements 1..a-1 : all nil elements a..z : sorted according to sortBlock elements z+1..x : added elements not sorted yet elements x+1..n : all nil Where I have written "a" and "x" you should understand the existing instance variables of OrderedCollection (inherited by SortedCollection) being used instead; the "z" instance variable is new. 2. add: anItem ^super addLast: anItem addFirst: anItem self shouldNotImplement addLast: anItem self shouldNotImplement addAll: aCollection ^super addAllLast: aCollection addAllFirst: aCollection self shouldNotImplement addAllLast: aCollection self shouldNotImplement No, I'm not being inconsistent here. I'm saying "let someone build a sorted collection in linear time if they can provide the elements in sorted order." With this kind of implementation, #add: _is_ adequate for the job. 3. A strictly private method would exist: pvtEnsureAllSorted "rather like current addAll:" x = z ifTrue: [^array]. self pvtSortAddedElements. "sorts z+1..x" self pvtMerge. "merges a..z with z+1..x" z := x. ^array Ideally pvtSortAddedElements would use a method which is linear when the elements are sorted already; Dijkstra's smooth-sort is just one of many algorithms which are good at that, bottom-up natural merge is easier to understand and works very well in practice. Using bottom-up natural merge, if you add M elements to a Sorted Collection having N elements and then look at the result, the adds would cost O(M) time, pvtEnsureAllSorted would cost O(M) for pvtSortAddedElements and O(M+N) for pvtMerge, for a total O(N+M). Building an entire collection from N=0 would thus be O(M). 4. Other methods would call pvtEnsureAllSorted, e.g. at: index self assert: [index between: 1 and: x-a+1]. ^self pvtEnsureAllSorted at: index-a+1 do: aBlock self pvtEnsureAllSorted. ^super do: aBlock 5. Setting the sortblock would simply enlarge the unsorted area: sortBlock: aBlock sortBlock := aBlock ifNil: [nil] ifNotNil: [aBlock fixTemps]. z := a-1. This is the clean way to do it. The class invariant is weakened from "the elements are always sorted" to "the elements are always sorted whenever anyone else looks; when noone else is looking they are in a convenient configuration for sorting." From the outside, it looks as though the elements are always sorted. While anyone's looking at SortedCollection, consider #(3 1 4 1 5 9 2 6 5 3 5) asSortedCollection reversed The result prints as a SortedCollection (9 6 5 5 5 4 3 3 2 1 1) but has sortBlock nil, so the order disagrees with the sortBlock. #reversed does make sense for SortedCollections; it ought to return a collection with the opposite comparison.

4 5

[Request] Auto scrolling squeak world (was [Enh]Auto Scroll)
by Torsten.Bergmann＠phaidros.com 27 Sep '02

27 Sep '02

Hi Torge and all, it works for me in a 3.2 alpha image 4913. Havent tested it in 3.3.alpha. It's nice - maybe we use it to solve a common problem: When one uses Squeak on a machine with 1024x768 and have some morph's at the bottom right corner of the screen he's/she's not able to access them on a machine with a smaller screen (800x600). It's the same problem if you work full screen with Squeak and change to the smaller window mode later. Maybe the standard world background is modified to have the AutoScroll functionality, so if we move the mouse to the squeak windows border region it is checked if the world is larger. What do you all think? Bye Torsten

3 2

RE: [FIX] SortedCollectionFix-sr
by Andreas Raab 27 Sep '02

27 Sep '02

PS: > if you want to > optimize then choose a central, high-level, intent revealing > place (such as, in fact, SortedCollection>>addAll:) and don't > ever have the client second-guessing the structure and > behavior of the object in question. A good example of what I mean can be found if you browse the implementors of #atAllPut: - it contains specific optimizations for polymorphic receivers and you simply can not get any faster by "client side optimizations" (e.g., writing out the loop or similar). But such a critical place has to be identified first and if everyone is "optimizing" the code locally you will never find the bottleneck to begin with. Cheers, - Andreas

2 1

Swiki rendering problems
by Christian EITNER 27 Sep '02

27 Sep '02

Hi all, I run a Swiki and have some problems with getting it to render. My Swiki's parent is refs which has no security profile. Since mine has to be protected a bit, I set standard rights to read only and added me as "Allow all". When I go to MySwiki/render and type in the password, there is an authorization error and nothing gets rendered. Okay, since refs renders I tried to temporarily remove the security profile from my Swiki and went to /render again. The strange thing that happens than is that somehow the rendering process seems to go round in a cycle, in the /rendered directory files appear and disappear, and it seems as if the process never could get past a certain page number. Hmm, I again reapplied and re-removed the security profile, this time I had to type in the Admin user:password combination, no complaints, but no rendering at all. Very strange. Is there some simple way to debug the Swiki while running, or should I tweak some XML file? Christian Austrian student in France/Switzerland

1 0

FW: wiki help needed
by Andreas Raab 27 Sep '02

27 Sep '02

Thought some people might be interested to help... -----Original Message----- From: Ralph Johnson [mailto:johnson@cs.uiuc.edu] Sent: Thursday, September 26, 2002 2:39 PM To: vwnc(a)cs.uiuc.edu Subject: wiki help needed I just noticed http://c2.com/cgi/wiki?TourBusStop and I wanted to put the VisualWorks wiki on it. In fact, there are probably quite a few Smalltalk wikis that could be on it, but I don't know which ones should be. Five minutes of thought told me that it would take an hour or two to do this right, and I don't have that time right now. I was about to write myself a todo note (realizing that I might never get around to it) when I thought of asking someone else to do it. Wiki being wiki, anybody can do this. Read, enjoy all the interesting wikis out there, and figure out the proper pages on Smalltalk wikis, linking them into the "tour routes". In fact, a couple of people can do this, though you should probably keep an eye out for others doing it and make sure you don't duplicate too much work. Thanks! -Ralph Johnson

1 0

← Newer
1
2
3
4
5
6
7
8
...
29
Older →

Jump to page: