Why are there nils in the middle of the queue?
The obvious thing is to use a linked structure or one which has amortised constant time addition of elements, and simply count how many items have been added to the queue to limit its size.
On 9/18/08, Ian J Cottee icottee@bluefountain.com wrote:
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.
Ian _______________________________________________ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Hi
It's emulating a conveyor belt. The 10 elements are slots on the belt that a machine at one end can place items into. Every x seconds the belt moves on one step. If the first machine hasn't put an item in the slot, the slot is empty. At the other end, if the there's an item in the slot when it gets to the front of the queue - that's given to the next machine. So depending on what the loading machine is doing, you can end up with gaps on the belt.
However, as it's a simulation the user may wish to change the size of the belt - in which case I have to remove slots with nothing in them (I can't remove slots which do have items on them for obvious reasons).
On Thu, Sep 18, 2008 at 9:31 AM, Marcin Tustin mm3@zepler.net wrote:
Why are there nils in the middle of the queue?
The obvious thing is to use a linked structure or one which has amortised constant time addition of elements, and simply count how many items have been added to the queue to limit its size.
On 9/18/08, Ian J Cottee icottee@bluefountain.com wrote:
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.
Ian _______________________________________________ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Ah, that's a much better description. So you actually don't want to remove nils from the start, but simply remove enough until the size is small enough? Now that's simple:
belt size - desiredSize timesRepeat: [belt remove: nil ifAbsent: []].
And to answer Marcin's next question, yes, that would be O(m^2). It doesn't matter for Ian's purpose I think, but an O(n) version would be
toRemove := belt size - desiredSize. belt removeAllSuchThat: [:each | each == nil and: [(toRemove := toRemove-1) >= 0]].
... which is obviously less elegant ;)
- Bert -
Am 18.09.2008 um 10:49 schrieb Ian J Cottee:
Hi
It's emulating a conveyor belt. The 10 elements are slots on the belt that a machine at one end can place items into. Every x seconds the belt moves on one step. If the first machine hasn't put an item in the slot, the slot is empty. At the other end, if the there's an item in the slot when it gets to the front of the queue - that's given to the next machine. So depending on what the loading machine is doing, you can end up with gaps on the belt.
However, as it's a simulation the user may wish to change the size of the belt - in which case I have to remove slots with nothing in them (I can't remove slots which do have items on them for obvious reasons).
On 9/18/08, Ian J Cottee icottee@bluefountain.com wrote:
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.
Ian
Am 18.09.2008 um 11:40 schrieb Bert Freudenberg:
belt size - desiredSize timesRepeat: [belt remove: nil ifAbsent: []].
And to answer Marcin's next question, yes, that would be O(m^2).
Err, O(m*n). Need coffee.
- Bert -
A reply to everyone who replied. Many thanks indeed. I really appreciate it.
The first example below is perfect for me so far in the small number of unit tests I've written. I'll do some more tomorrow.
Now I just have to understand what it's doing ;)
Ian
PS My solution was about ten lines of code and very obviously procedural!
On Thu, Sep 18, 2008 at 10:40 AM, Bert Freudenberg bert@freudenbergs.de wrote:
Ah, that's a much better description. So you actually don't want to remove nils from the start, but simply remove enough until the size is small enough? Now that's simple:
belt size - desiredSize timesRepeat: [belt remove: nil ifAbsent: []].
And to answer Marcin's next question, yes, that would be O(m^2). It doesn't matter for Ian's purpose I think, but an O(n) version would be
toRemove := belt size - desiredSize. belt removeAllSuchThat: [:each | each == nil and: [(toRemove := toRemove-1)
= 0]].
... which is obviously less elegant ;)
- Bert -
Am 18.09.2008 um 10:49 schrieb Ian J Cottee:
Hi
It's emulating a conveyor belt. The 10 elements are slots on the belt that a machine at one end can place items into. Every x seconds the belt moves on one step. If the first machine hasn't put an item in the slot, the slot is empty. At the other end, if the there's an item in the slot when it gets to the front of the queue - that's given to the next machine. So depending on what the loading machine is doing, you can end up with gaps on the belt.
However, as it's a simulation the user may wish to change the size of the belt - in which case I have to remove slots with nothing in them (I can't remove slots which do have items on them for obvious reasons).
On 9/18/08, Ian J Cottee icottee@bluefountain.com wrote:
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.
Ian
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
beginners@lists.squeakfoundation.org