Would this be O(n^2) to remove all nils?
In any case, if this is a conveyor belt, then you should almost certainly be using a linke data structure, and iterate over the structure to delete the unwanted links.
On 9/18/08, Bert Freudenberg bert@freudenbergs.de wrote:
Am 18.09.2008 um 10:06 schrieb Ian J Cottee:
Hello all
I've got an OrderedCollection that is normally a fixed size (let's say 10 elements). Each element in the collection is another an object or nil. So for example, at a point in time it might look like
[nil, nil, Object, nil, Object, Object, nil, nil, Object, nil]
What I want is to be able to resize the collection. Making it bigger is no problem for me, I can just add nils to the end of the collection. Making it smaller is involving a little bit of pain. I can see ways of doing it but theyr'e not elegant and I'm sure there are cleaner ways of doing it. If I made the above queue smaller I'd basically remove the nils starting from the beginning. So a resize to size 7 would give me
[ Object, Object, Object, nil, nil, Object, nil]
i.e. the first three nils have been removed.
Does anybody have any comments on appropriate code to handle this? If not, I'll go with the ugly stuff but it would be nice to know the correct SmallTalk way.
Many thanks for any suggestions.
I guess it doesn't get much more elegant and efficient than
start := coll findFirst: [:each | each ~~ nil]. coll removeFirst: start-1.
... unless you add a specific method to OC.
- Bert -
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
At Thu, 18 Sep 2008 10:00:15 +0100, Marcin Tustin wrote:
Would this be O(n^2) to remove all nils?
Not in a way it matters. OrderedCollection moves items not eagarly.
In any case, if this is a conveyor belt, then you should almost certainly be using a linke data structure, and iterate over the structure to delete the unwanted links.
No in two reasons; 1) he wasn't talking about removing items in the middle and 2) OrderedCollection is usually more efficient than the naive LinkedList, as less dereferencing. (And, it could get more benefits from using array manipulation primitives like replaceFrom:to:, but it can't at least for addFirst:.)
-- Yoshiki
Am 18.09.2008 um 11:00 schrieb Marcin Tustin:
Would this be O(n^2) to remove all nils?
This only removes nils from the start. If n is the size of the collection and m the number of nils at its beginning then it's only O(m).
start := coll findFirst: [:each | each ~~ nil]. coll removeFirst: start-1.
- Bert -
beginners@lists.squeakfoundation.org