'From Squeak3.2alpha of 1 November 2001 [latest update: #4646] on 28 January 2002 at 9:32:18 am'! "Change Set: topologicalSort-hg Date: 17 December 2001 Author: Henrik Gedenryd Published in 3.3a as 4685topologicalSort-hg.cs This adds topological sorting capabilities to SortedCollection, with no claims to great efficiency (and simplifies some code in the same class). Best used with aCollection topologicallySortedUsing: sortBlock A topological sort arranges items according to a partial order, i.e., when some pairs of items do not have any comparison. A new Boolean methods, ==> (implicature, a.k.a. if...then...) is helpful for defining such relationships. Example: aString topologicallySortedUsing: [:a :b | (a isUppercase == b isUppercase) ==> [a <= b]] This only specifies an alphabetical order between letters of the same case, try e.g. ('ThisIsMyString' topologicallySortedUsing: [:a :b | a isUppercase == b isUppercase ==> [a <= b]]) as: String Note that an ordinary sort will do this incorrectly: ('ThisIsMyString' asSortedCollection: [:a :b | a isUppercase == b isUppercase ==> [a <= b]]) as: String "! !Boolean methodsFor: 'logical operations' stamp: 'hg 1/2/2002 13:57'! ==> aBlock "this is logical implicature, a ==> b, also known as b iff a (if and only if)" ^self not or: [aBlock value]! ! !Collection methodsFor: 'converting' stamp: 'hg 12/26/2001 23:53'! topologicallySortedUsing: aSortBlock "Answer a SortedCollection whose elements are the elements of the receiver, but topologically sorted. The topological order is defined by the argument, aSortBlock." | aSortedCollection | aSortedCollection _ SortedCollection new: self size. aSortedCollection sortBlock: aSortBlock. self do: [:each | aSortedCollection addLast: each]. "avoids sorting" ^ aSortedCollection sortTopologically ! ! !SortedCollection methodsFor: 'private' stamp: 'hg 12/17/2001 19:30'! should: a precede: b ^sortBlock ifNil: [a <= b] ifNotNil: [sortBlock value: a value: b] ! ! !SortedCollection methodsFor: 'private' stamp: 'hg 12/17/2001 20:22'! sort: i to: j "Sort elements i through j of self to be nondescending according to sortBlock." | di dij dj tt ij k l n | "The prefix d means the data at that index." (n _ j + 1 - i) <= 1 ifTrue: [^self]. "Nothing to sort." "Sort di,dj." di _ array at: i. dj _ array at: j. (self should: di precede: dj) ifFalse: [array swap: i with: j. tt _ di. di _ dj. dj _ tt]. n > 2 ifTrue: "More than two elements." [ij _ (i + j) // 2. "ij is the midpoint of i and j." dij _ array at: ij. "Sort di,dij,dj. Make dij be their median." (self should: di precede: dij) ifTrue: [(self should: dij precede: dj) ifFalse: [array swap: j with: ij. dij _ dj]] ifFalse: [array swap: i with: ij. dij _ di]. n > 3 ifTrue: "More than three elements." ["Find k>i and l