Re: Newbie Question: implementing a stack
Sorry to jump in to this a little late, but a guy in our CocoaHeads
group wrote a framework as part of his Master's thesis work. It's a
datastructure framework and contains a bunch of datastructures not
available (publicly) in Cocoa, such as stacks, queues, dequeues, avl/
rb/aa-trees, treaps, etc. It's open sourced under the LGPL license,
and you can check it out of svn from our CocoaHeads page on it:
http://cocoaheads.byu.edu/code/CHDataStructures
Cheers,
Dave
On 19 Dec, 2008, at 12:22 PM, Steve Wetzel wrote:
Hi All,
I am new to this list and new to mac programming as well. I am
working on implementing a stack as a category of NSMutableArray. I
want this stack to be able to store objects. This is what I have so
far:
//
// Stack.h
// Stack implements a basic stack object in an NSMutableArray object.
#import Foundation/Foundation.h
@interface NSMutableArray (Stack)
-(void)push:(id)obj;//push obj of on the stack
-(id)pop; //pop top item off the
stack
-(id)peek; //look at the top item
on the stack
-(void)clear; //remove all objects from the
stack
-(NSUInteger)size; //return the number of items on
the stack
@end
//
// Stack.m
// Stack
#import Stack.h
@implementation NSMutableArray (Stack)
-(void)push:(id)obj
{
[self addObject:obj];
}
-(id)pop
{
id popedObj;
if([self count]) {
popedObj = [[[self lastObject] retain] autorelease];
[self removeLastObject];
} else {
popedObj = nil;
}
return popedObj;
}
-(id)peek; //look at the top item
on the stack
{
return [self lastObject];
}
-(void)clear; //remove all objects from the
stack
{
[self removeAllObjects];
}
-(NSUInteger)size; //return the number of items on
the stack
{
return [self count];
}
@end
My question involves storing objects on the stack. As I understand
it when I store an object on the stack, I am simply storing a
pointer to the object on the stack. If I create an NSString object
called foo and do the following:
NSString *foo = [[NSString alloc] initWithString:@foo text];
[FractionStack push:foo];
I have put a copy of the pointer to foo on the stack. If I now
change foo, the top element on the stack changes also. I do not
want this to happen but I am not sure as to the best approach to
make sure this does not happen.
Would it be best to copy the object to another object - say fooCopy
then push fooCopy on the stack? Or would it be better to copy the
object inside of the push method? And either way, I am struggling
with memory management. If I first copy foo to fooCopy before
placing it on the stack then I release fooCopy, will the element on
the stack still be able to reference it? do I need to retain it in
my push method?
Also, I am thinking I likely will need to release these objects when
I pop them and when I clear the stack. Is that correct?
I am really trying to get my head wrapped around this but I have
been struggling with this for some time. If, in addition to some
words of wisdom, you can point me in the direction of how I could
create a simple test of this in my code to work things out on my own
that would be appreciated also.
As I said I am new to this so if my post is not in keeping with the
way things work on this list please let me know.
Thanks in advance,
Steve
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/davedelong%40me.com
This email sent to davedel...@me.com
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On Dec 20, 2008, at Dec 20:12:08 AM, Graham Cox wrote: On 20 Dec 2008, at 4:52 pm, Graham Cox wrote: On 20 Dec 2008, at 3:15 pm, Steve Wetzel wrote: Regarding memory management - does it make more sense to copy the object to be pushed from within the Stack object rather then copying it externally before the push call? I am thinking that it does because then that object is encapsulated which is how a stack should really work. If I do this I realize I will need to implement a copy method within any object that I want to place on the stack if it does not already have one. My own view is that the stack object shouldn't copy the object. Of course, a very easy, and generally useful solution, is to provide two methods: - (void)push:(id) obj; - (void)pushCopy:(id) obj; G. I do see your point Graham but what I am trying to understand is how to work with the stack if I don't copy the object to put on it. If I simply push the pointer on the stack, it seems that I have to make a lot of objects in the code that handles the stack object. If I have an class MyObject I wish to push on the stack: MyObject *myObj1 = [[MyObject alloc] init]; MyObject *myObj2 = [[MyObject alloc] init]; ... MyObject *myObj10 = [[MyObject alloc] init]; [stack push:myObj1]; [stack push:myObj2]; ... [stack push:myObj10]; Each time I want to push a MyObject onto the stack I need to create a new MyObject. If I copy I can do: MyObject *myObj = [[MyObject alloc] init]; [stack push:myObj]; assign new attributes to myObj [stack push:myObj]; assign new attributes to myObj ... I guess can simply assign the pointer, but if I do, it seems to me I will need an NSMutableArray to hold myObj1... myObj10 (or more). If I do that, what benefit is the stack? Steve ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On 21 Dec 2008, at 10:52 am, Steve Wetzel wrote: I guess can simply assign the pointer, but if I do, it seems to me I will need an NSMutableArray to hold myObj1... myObj10 (or more). If I do that, what benefit is the stack? I don't really follow your argument. Presumably you decided you need a stack for some reason to do with your application's logic - so I can't answer what benefit is the stack? - that's up to you! A stack in general terms doesn't inherently copy items placed on it, there's nothing in the definition of 'stack' that implies a copy. It's just storage, with a LIFO semantic. I don't really see what creating objects has do with it - the stack is to do with organising objects, not creating them. --Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On Sat, Dec 20, 2008 at 6:52 PM, Steve Wetzel stevewet...@mac.com wrote: I do see your point Graham but what I am trying to understand is how to work with the stack if I don't copy the object to put on it. If I simply push the pointer on the stack, it seems that I have to make a lot of objects in the code that handles the stack object. If I have an class MyObject I wish to push on the stack: MyObject *myObj1 = [[MyObject alloc] init]; MyObject *myObj2 = [[MyObject alloc] init]; ... MyObject *myObj10 = [[MyObject alloc] init]; [stack push:myObj1]; [stack push:myObj2]; ... [stack push:myObj10]; Each time I want to push a MyObject onto the stack I need to create a new MyObject. If I copy I can do: MyObject *myObj = [[MyObject alloc] init]; [stack push:myObj]; assign new attributes to myObj [stack push:myObj]; assign new attributes to myObj ... I guess can simply assign the pointer, but if I do, it seems to me I will need an NSMutableArray to hold myObj1... myObj10 (or more). If I do that, what benefit is the stack? You're very confused. When you assign something new to myObj, you're only affecting that one pointer. You don't affect anything else that has a reference to the original object. For example: NSString *str = @hello; [stack push:str]; str = @world; [stack push:str]; Your stack now contains @hello and @world. It does not matter what its copying behavior is, this is *always* true. (Try it with an NSMutableArray and see; NSMutableArray does not copy the objects it receives.) When you write str = @world you just put a new address into the str pointer. But the stack isn't holding your str variable. It's simply holding the value that str held originally. So there's no problem. What copying saves you from is stuff like this: NSMutableString *str = [NSMutableString stringWithString:@hello]; [stack push:str]; [str setString:@world]; [stack push:str]; In this case the stack ends up holding two copies of a single mutable string which contains the text @world. Here we aren't mutating str, we're mutating the *object* that it points to. If the stack copied the object then we wouldn't mutate the copy and so the -setString: call wouldn't change its contents. This usually isn't much of a problem. And to the extent that it is, being able to push non-copyable objects or referenced mutable objects onto a stack will generally far outweigh them. Follow Cocoa's lead: with the exception of dictionary keys, Cocoa does not copy objects that are put into collections. Mike ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Newbie Question: implementing a stack
Hi All,
I am new to this list and new to mac programming as well. I am
working on implementing a stack as a category of NSMutableArray. I
want this stack to be able to store objects. This is what I have so
far:
//
// Stack.h
// Stack implements a basic stack object in an NSMutableArray object.
#import Foundation/Foundation.h
@interface NSMutableArray (Stack)
-(void)push:(id)obj;//push obj of on the stack
-(id)pop; //pop top item off the
stack
-(id)peek; //look at the top item
on the stack
-(void)clear; //remove all objects from the
stack
-(NSUInteger)size; //return the number of items on
the stack
@end
//
// Stack.m
// Stack
#import Stack.h
@implementation NSMutableArray (Stack)
-(void)push:(id)obj
{
[self addObject:obj];
}
-(id)pop
{
id popedObj;
if([self count]) {
popedObj = [[[self lastObject] retain] autorelease];
[self removeLastObject];
} else {
popedObj = nil;
}
return popedObj;
}
-(id)peek; //look at the top item
on the stack
{
return [self lastObject];
}
-(void)clear; //remove all objects from the
stack
{
[self removeAllObjects];
}
-(NSUInteger)size; //return the number of items on
the stack
{
return [self count];
}
@end
My question involves storing objects on the stack. As I understand it
when I store an object on the stack, I am simply storing a pointer to
the object on the stack. If I create an NSString object called foo
and do the following:
NSString *foo = [[NSString alloc] initWithString:@foo text];
[FractionStack push:foo];
I have put a copy of the pointer to foo on the stack. If I now change
foo, the top element on the stack changes also. I do not want this to
happen but I am not sure as to the best approach to make sure this
does not happen.
Would it be best to copy the object to another object - say fooCopy
then push fooCopy on the stack? Or would it be better to copy the
object inside of the push method? And either way, I am struggling
with memory management. If I first copy foo to fooCopy before placing
it on the stack then I release fooCopy, will the element on the stack
still be able to reference it? do I need to retain it in my push
method?
Also, I am thinking I likely will need to release these objects when I
pop them and when I clear the stack. Is that correct?
I am really trying to get my head wrapped around this but I have been
struggling with this for some time. If, in addition to some words of
wisdom, you can point me in the direction of how I could create a
simple test of this in my code to work things out on my own that would
be appreciated also.
As I said I am new to this so if my post is not in keeping with the
way things work on this list please let me know.
Thanks in advance,
Steve
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On Dec 19, 2008, at 1:22 PM, Steve Wetzel wrote: I am new to this list and new to mac programming as well. I am working on implementing a stack as a category of NSMutableArray. I want this stack to be able to store objects. This is what I have so far: // // Stack.h // Stack implements a basic stack object in an NSMutableArray object. #import Foundation/Foundation.h @interface NSMutableArray (Stack) -(void)push:(id)obj;//push obj of on the stack -(id)pop; //pop top item off the stack -(id)peek; //look at the top item on the stack -(void)clear; //remove all objects from the stack -(NSUInteger)size; //return the number of items on the stack @end If I were doing this, I would actually create an object (subclass of NSObject) that would contain an NSMutableArray as an attribute. That way, your API would be very clean. What you have above would allow users to call any of the NSArray* suite of APIs in addition to yours above. Sometimes too many APIs on an object can lead to issues. My question involves storing objects on the stack. As I understand it when I store an object on the stack, I am simply storing a pointer to the object on the stack. If I create an NSString object called foo and do the following: NSString *foo = [[NSString alloc] initWithString:@foo text]; [FractionStack push:foo]; I have put a copy of the pointer to foo on the stack. If I now change foo, the top element on the stack changes also. I do not want this to happen but I am not sure as to the best approach to make sure this does not happen. In this specific case, you cannot change foo since NSString is immutable. If you find yourself adding (pushing) items that are immutable, it would be best to make a copy or mutable copy as needed. Also, I am thinking I likely will need to release these objects when I pop them and when I clear the stack. Is that correct? Just read up more on the memory management rules. You can also decide on object-ownership rules. Typically, the container objects retain objects added to them. Then release them when removed. That's all you should be concerned about. It's then up to the original owner of the object to do the right thing. ___ Ricky A. Sharp mailto:rsh...@instantinteractive.com Instant Interactive(tm) http://www.instantinteractive.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On Dec 19, 2008, at Dec 19:6:31 PM, Ricky Sharp wrote: On Dec 19, 2008, at 1:22 PM, Steve Wetzel wrote: I am new to this list and new to mac programming as well. I am working on implementing a stack as a category of NSMutableArray. I want this stack to be able to store objects. This is what I have so far: // // Stack.h // Stack implements a basic stack object in an NSMutableArray object. #import Foundation/Foundation.h @interface NSMutableArray (Stack) -(void)push:(id)obj;//push obj of on the stack -(id)pop; //pop top item off the stack -(id)peek; //look at the top item on the stack -(void)clear; //remove all objects from the stack -(NSUInteger)size; //return the number of items on the stack @end If I were doing this, I would actually create an object (subclass of NSObject) that would contain an NSMutableArray as an attribute. That way, your API would be very clean. What you have above would allow users to call any of the NSArray* suite of APIs in addition to yours above. Sometimes too many APIs on an object can lead to issues. My question involves storing objects on the stack. As I understand it when I store an object on the stack, I am simply storing a pointer to the object on the stack. If I create an NSString object called foo and do the following: NSString *foo = [[NSString alloc] initWithString:@foo text]; [FractionStack push:foo]; I have put a copy of the pointer to foo on the stack. If I now change foo, the top element on the stack changes also. I do not want this to happen but I am not sure as to the best approach to make sure this does not happen. In this specific case, you cannot change foo since NSString is immutable. If you find yourself adding (pushing) items that are immutable, it would be best to make a copy or mutable copy as needed. Also, I am thinking I likely will need to release these objects when I pop them and when I clear the stack. Is that correct? Just read up more on the memory management rules. You can also decide on object-ownership rules. Typically, the container objects retain objects added to them. Then release them when removed. That's all you should be concerned about. It's then up to the original owner of the object to do the right thing. Ricky, thank you for the response. I think I agree with your answer on creating stack object, it makes sense. Also you confirmed my thoughts about memory management. Regarding memory management - does it make more sense to copy the object to be pushed from within the Stack object rather then copying it externally before the push call? I am thinking that it does because then that object is encapsulated which is how a stack should really work. If I do this I realize I will need to implement a copy method within any object that I want to place on the stack if it does not already have one. ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On 20 Dec 2008, at 3:15 pm, Steve Wetzel wrote: Regarding memory management - does it make more sense to copy the object to be pushed from within the Stack object rather then copying it externally before the push call? I am thinking that it does because then that object is encapsulated which is how a stack should really work. If I do this I realize I will need to implement a copy method within any object that I want to place on the stack if it does not already have one. My own view is that the stack object shouldn't copy the object. In your particular case you seem to want to push a copy of the object onto the stack, but in the general case, you wouldn't expect the stack to do this. In the interest of developing reusable code where possible, your stack object would be more reusable if it was dumber - i.e. it retained its objects and didn't copy them. If I had a stack object black box, pushed an object then later when I popped it I got back a different object (albeit one that was very similar) I'd be surprised by that, especially if I'd mutated it on purpose - all my changes would have evaporated. In your special case perform the copy outside the stack object, thus keeping the special case out of an otherwise reusable class. That said, over-generalising code prematurely is almost as bad as optimising code prematurely, so if you think you'll never have a use for a stack anywhere else except this one case, then by all means do the copy internally. hth, Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Newbie Question: implementing a stack
On 20 Dec 2008, at 4:52 pm, Graham Cox wrote: On 20 Dec 2008, at 3:15 pm, Steve Wetzel wrote: Regarding memory management - does it make more sense to copy the object to be pushed from within the Stack object rather then copying it externally before the push call? I am thinking that it does because then that object is encapsulated which is how a stack should really work. If I do this I realize I will need to implement a copy method within any object that I want to place on the stack if it does not already have one. My own view is that the stack object shouldn't copy the object. Of course, a very easy, and generally useful solution, is to provide two methods: - (void)push:(id) obj; - (void)pushCopy:(id) obj; G. ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
