/*
* cs_UniqueNameManager.h
*
*
* Copyright (c) 2005 Classical Software. All rights reserved.
*
* This software is released under the Creative Commons Attribution License, version 2.0
* http://creativecommons.org/licenses/by/2.0/legalcode
*/
#import "cs_Utils.h"
/*
* **************************************
* *
* cs_UniqueNamedObjectProtocol *
* *
* **************************************
*
* Objects (most of the time) should respond to this protocol.
*
* Groups of objects that are named usually maintain their own
* names (and so will already implement "-name" and "-setName:",
* but if for some reason they don't the cs_UniqueNameManager
* will save the names internally and can be queried with
* "-nameOfObject:". (In this case the caller needs to use
* "-setShouldStoreObjectNamesInManager: YES".)
*
* Objects MUST implement "-proposeNameForDetailLevel:existingNames:"
* which generates a new name at the given "level".
*/
@protocol cs_UniqueNamedObjectProtocol
- (NSString *) name;
- (void) setName: (NSString *) s;
- (NSString *) proposeNameForDetailLevel: (int) i existingNames: (NSSet *) s;
@end
/*
* **************************************
* *
* cs_UniqueNameManager *
* *
* **************************************
*/
@interface cs_UniqueNameManager: NSObject
{
NSMutableArray *all_objects_;
NSMutableSet *all_names_;
NSMutableDictionary *objects_grouped_by_name_;
NSMutableDictionary *names_by_object_;
BOOL needs_updating_;
BOOL should_store_object_names_in_manager_;
}
+ (void) produceNamesUsingObjects: (NSArray *) a;
+ (id) managerWithObjects: (NSArray *) a;
+ (id) manager;
- (NSMutableArray *) allObjects;
- (void) setAllObjects: (NSMutableArray *) a;
- (void) mergeObjects: (NSArray *) a;
- (NSMutableSet *) allNames;
- (void) setAllNames: (NSMutableSet *) s;
- (NSMutableDictionary *) objectsGroupedByName;
- (void) setObjectsGroupedByName: (NSMutableDictionary *) d;
- (NSMutableDictionary *) namesByObject;
- (void) setNamesByObject: (NSMutableDictionary *) d;
- (BOOL) needsUpdating;
- (void) setNeedsUpdating: (BOOL) b;
- (BOOL) shouldStoreObjectNamesInManager;
- (void) setShouldStoreObjectNamesInManager: (BOOL) b;
- (void) updateIfNeeded;
- (void) update;
- (void) groupObjectsByName;
- (void) calcUniqueNamesForObjects: (NSArray *) a;
- (NSString *) guaranteedNameOfObject: (id) o;
- (NSString *) nameOfObject: (id) o;
- (void) saveName: (NSString *) s forObject: (id) o;
- (NSString *) keyForObject: (id) o;
@end
cs_UniqueNameManager.m
/*
* cs_UniqueNameManager.m
*
* Given an set of objects (either initially or continually added/
* removed) a cs_UniqueNameManager manages the process of producing
* names for all objects such that they are unique across the entire
* set - that is, no two objects have the same name.
*
* Note that it does this by sending each object "-proposeNameForDetailLevel:existingNames:"
* to which the object responds with a new name for that "level".
*
* If the manager finds duplicate names at level 0 it starts over by
* asking each object to generate a name for level 1, and so on.
*
*
* Copyright (c) 2005 Classical Software. All rights reserved.
*
* This software is released under the Creative Commons Attribution License, version 2.0
* http://creativecommons.org/licenses/by/2.0/legalcode
*/
#import "cs_Error.h"
#import "cs_UniqueNameManager.h"
#import "cs_Utils.h"
/*
* -------------------------- D e b u g g i n g --------------------------
*/
//#define DBG__TELL_NAME_GENS
#ifdef DBG__TELL_NAME_GENS
#define DBG_TELL_START() printf("--- UniqNmGen --- %s\n", [[self description] lossyCString] );
#define DBG_TELL_GROUPED() printf(">>> grouped: %s\n", [[self description] lossyCString] );
#define DBG_TELL_RECALCD_GROUP(n) printf(">>> recalc'd '%s' grp %s\n", [n lossyCString], [[self description] lossyCString] )
#define DBG_TELL_RESULT() printf(">>> result: %s\n", [[self description] lossyCString] )
#else
#define DBG_TELL_START()
#define DBG_TELL_GROUPED()
#define DBG_TELL_RECALCD_GROUP(n)
#define DBG_TELL_RESULT()
#endif
/*
* -------------------------- e n d d e b u g --------------------------
*/
/*
* **********************************************************************************************
* *
* cs_UniqueNameManager *
* *
* **********************************************************************************************
*/
@implementation cs_UniqueNameManager
/*
* produceNamesUsingObjects:
*/
+ (void) produceNamesUsingObjects: (NSArray *) a
{
cs_UniqueNameManager *mgr = [self managerWithObjects: a];
[mgr update];
}
/*
* managerWithObjects:
*/
+ (id) managerWithObjects: (NSArray *) a
{
cs_UniqueNameManager *mgr = [self manager];
NSMutableArray *ma = (NSMutableArray *) a;
if( [ma isKindOfClass: [NSMutableArray class]] == NO )
ma = [NSMutableArray arrayWithObjects: a];
[mgr setAllObjects: ma];
return mgr;
}
/*
* manager
*/
+ (id) manager
{
return [[[self alloc] init] autorelease];
}
/*
* init
*/
- (id) init
{
if( (self = [super init]) )
{
[self setObjectsGroupedByName: [NSMutableDictionary dictionary]];
[self setAllNames: [NSMutableSet set ]];
[self setNamesByObject: [NSMutableDictionary dictionary]];
}
return self;
}
/*
* dealloc
*/
- (void) dealloc
{
[self setAllObjects: nil];
[self setObjectsGroupedByName: nil];
[self setAllNames: nil];
[self setNamesByObject: nil];
[super dealloc];
}
#pragma mark -
/*
* **********************************************************************************************
*/
/*
* allObjects
*/
- (NSMutableArray *) allObjects
{
return all_objects_;
}
/*
* setAllObjects:
*/
- (void) setAllObjects: (NSMutableArray *) d
{
if( all_objects_ != d )
{
[all_objects_ release];
all_objects_ = [d retain];
[self setNeedsUpdating: YES];
}
}
/*
* mergeObjects:
*/
- (void) mergeObjects: (NSArray *) new_objs
{
NSMutableArray *all = [self allObjects];
int started = [all count];
NSEnumerator *enumr = [new_objs objectEnumerator];
id obj;
while( (obj = [enumr nextObject]) )
{
if( [all containsObject: obj] == NO )
[all addObject: obj];
}
if( [all count] > started )
[self setNeedsUpdating: YES];
}
/*
* allNames
*
* Return: { "abc", "def", "g" }
*/
- (NSMutableSet *) allNames
{
return all_names_;
}
/*
* setAllNames:
*/
- (void) setAllNames: (NSMutableSet *) s
{
if( all_names_ != s )
{
[all_names_ release];
all_names_ = [s retain];
}
}
/*
* objectsGroupedByName
*
* Name Objects
* -------- -----------
* Return: dict { { "abc", [o1, o2] },
* { "def", [o3] },
* { "g", [o4, o5] }
* }
*/
- (NSMutableDictionary *) objectsGroupedByName
{
return objects_grouped_by_name_;
}
/*
* setObjectsGroupedByName:
*/
- (void) setObjectsGroupedByName: (NSMutableDictionary *) d
{
if( objects_grouped_by_name_ != d )
{
[objects_grouped_by_name_ release];
objects_grouped_by_name_ = [d retain];
}
}
/*
* namesByObject
*
* Name Objects
* -------- -----------
* Return: dict { { "abc", @"0x1234" },
* { "def", @"32456" },
* { "g", @"68793" }
* }
*/
- (NSMutableDictionary *) namesByObject
{
return names_by_object_;
}
/*
* setNamesByObject:
*/
- (void) setNamesByObject: (NSMutableDictionary *) d
{
if( names_by_object_ != d )
{
[names_by_object_ release];
names_by_object_ = [d retain];
}
}
/*
* needsUpdating
*/
- (BOOL) needsUpdating
{
return needs_updating_;
}
/*
* setNeedsUpdating:
*/
- (void) setNeedsUpdating: (BOOL) b
{
needs_updating_ = b;
}
/*
* shouldStoreObjectNamesInManager
*/
- (BOOL) shouldStoreObjectNamesInManager
{
return should_store_object_names_in_manager_;
}
/*
* setShouldStoreObjectNamesInManager:
*/
- (void) setShouldStoreObjectNamesInManager: (BOOL) b
{
should_store_object_names_in_manager_ = b;
}
#pragma mark -
/*
* **********************************************************************************************
*/
/*
* updateIfNeeded
*/
- (void) updateIfNeeded
{
if( [self needsUpdating] )
{
[self setNeedsUpdating: NO];
[self update];
}
}
/*
* update
*/
- (void) update
{
DBG_TELL_START();
[self groupObjectsByName];
DBG_TELL_GROUPED();
NSMutableDictionary *obj_groups = [self objectsGroupedByName];
NSEnumerator *enumr = [obj_groups keyEnumerator];
NSMutableSet *all_nms = [self allNames];
NSMutableArray *group;
NSString *nm;
while( (nm = [enumr nextObject]) )
{
/*
* Get the array of objects that all have this name:
*
* { "abc", [o1, o2] }
*/
group = [obj_groups objectForKey: nm];
/*
* Only one object in this group - and thus using this name?
*
* { "def", [o3] }
*/
if( [group count] == 1 )
{
id <cs_UniqueNamedObjectProtocol> obj = [group objectAtIndex: 0];
[self saveName: nm forObject: obj];
}
/*
* Several objects are using this name, so need to have
* them make new names for themselves.
*
* { "abc", [o1, o2] } -> { "abc #1", [o1] },
* { "abc #2", [o2] }
*/
else
{
[self calcUniqueNamesForObjects: group];
[obj_groups removeObjectForKey: nm];
[all_nms removeObject: nm];
DBG_TELL_RECALCD_GROUP( nm );
}
}
DBG_TELL_RESULT();
}
/*
* groupObjectsByName
*/
- (void) groupObjectsByName
{
NSMutableDictionary *obj_groups = [self objectsGroupedByName];
NSMutableArray *objs = [self allObjects];
NSEnumerator *enumr = [objs objectEnumerator];
NSMutableSet *all_nms = [self allNames];
NSMutableArray *a;
id <cs_UniqueNamedObjectProtocol> obj;
[obj_groups removeAllObjects];
[all_nms removeAllObjects];
while( (obj = [enumr nextObject]) )
{
NSString *nm = [self nameOfObject: obj];
if( nm == nil )
{
nm = [obj proposeNameForDetailLevel: 0 existingNames: nil];
[self saveName: nm forObject: obj];
}
[all_nms addObject: nm];
if( (a = [obj_groups objectForKey: nm]) == nil )
{
a = [NSMutableArray arrayWithObject: obj];
[obj_groups setObject: a forKey: nm];
}
else
[a addObject: obj];
}
}
/*
* calcUniqueNamesForObjects:
*/
- (void) calcUniqueNamesForObjects: (NSArray *) objs_with_same_nm
{
NSMutableDictionary *obj_groups = [self objectsGroupedByName];
NSMutableSet *all_nms = [self allNames];
NSMutableSet *new_nms = [NSMutableSet setWithCapacity: [objs_with_same_nm count]];
int lvl = 1;
NSString *nm;
int k, n;
NSMutableArray *a;
id <cs_UniqueNamedObjectProtocol> obj;
for(k=0,n=[objs_with_same_nm count]; k < n; k++)
{
obj = [objs_with_same_nm objectAtIndex: k];
nm = [obj proposeNameForDetailLevel: lvl existingNames: all_nms];
if( [all_nms member: nm] ) // this name already exists
{ //
lvl++; // then go to the next detail level
k = -1; // start over with the objs
[all_nms minusSet: new_nms]; //
[new_nms removeAllObjects]; // (clear prev produced labels)
}
else
{
[new_nms addObject: nm]; // brand new name, so remember it
[all_nms addObject: nm]; //
[self saveName: nm forObject: obj]; // let the obj keep it's copy, too
}
}
/*
* Now encorporate them back into the "all names" dict
*/
for(k=0; k < n; k++)
{
obj = [objs_with_same_nm objectAtIndex: k];
nm = [self nameOfObject: obj];
a = [NSMutableArray arrayWithObject: obj];
[obj_groups setObject: a forKey: nm];
}
}
#pragma mark -
/*
* **********************************************************************************************
*/
/*
* When saving object names ourself we use a dictionary,
* indexed by each object (actually a string containing
* it's address, e.g.: @"0x657498").
*
* Otherwise each object keeps it's own name.
*/
/*
* guaranteedNameOfObject:
*
* This object should have a name (it either keeps the name
* itself or we have a big table with the obj & it's name),
* but if somehow it doesn't we'll make up one.
*/
- (NSString *) guaranteedNameOfObject: (id) obj
{
NSString *nm = [self nameOfObject: obj];
if( [nm length] == 0 )
{
if( obj == nil )
nm = @"0x0";
else
nm = [NSString stringWithFormat: @"%@ %p", [obj class], obj];
}
return nm;
}
/*
* nameOfObject:
*/
- (NSString *) nameOfObject: (id) obj
{
NSString *nm = @"?";
if( [self shouldStoreObjectNamesInManager] ) // are we storing the names?
{
NSMutableDictionary *d = [self namesByObject]; // the get it
NSString *s = [self keyForObject: obj]; //
nm = [d objectForKey: s]; //
}
else if( [obj respondsToSelector: @selector( name )] ) // Nope, the obj SHOULD have it
{
nm = [obj name]; // they do, so get it
}
else // NO!
[self INTERNAL_ERROR: @"%@ %p does not respond to 'name' (obj=%@)", [obj class], obj, obj];
return nm;
}
/*
* saveName: forObject:
*/
- (void) saveName: (NSString *) nm
forObject: (id ) obj
{
if( [self shouldStoreObjectNamesInManager] ) // are we storing the names?
{
NSMutableDictionary *d = [self namesByObject]; // then save it away
NSString *s = [self keyForObject: obj];
[d setObject: nm forKey: s]; //
}
else if( [obj respondsToSelector: @selector( setName: )] ) // this obj SHOULD be saving it
{
[(id<cs_UniqueNamedObjectProtocol>)obj setName: nm];
}
else // they aren't, trouble
[self INTERNAL_ERROR: @"%@ %p does not respond to 'setName' (obj=%@)", [obj class], obj, obj];
}
/*
* keyForObject:
*
* Return a (simple) unique key for this object:
*
* "0x12345678" (it's address as a string)
*/
- (NSString *) keyForObject: (id) obj
{
return [NSString stringWithFormat: @"%p", obj];
}
#pragma mark -
/*
* **********************************************************************************************
*/
/*
* description
*/
- (NSString *) description
{
NSDictionary *obj_groups = [self objectsGroupedByName];
NSMutableString *s = [NSMutableString stringWithFormat: @"%@: %d groups", [self class], [obj_groups count]];
if( [self needsUpdating] )
[s appendString: @" (needs updating)"];
NSEnumerator *enumr = [obj_groups keyEnumerator];
int k = 0;
id obj;
NSString *nm;
[s appendFormat: @"\nGrp# Name"];
while( (nm = [enumr nextObject]) )
{
NSMutableArray *a = [obj_groups objectForKey: nm];
[s appendFormat: @"\n %2d ", k++];
if( [a count] == 1 )
{
obj = [a objectAtIndex: 0];
nm = [self nameOfObject: obj];
[s appendFormat: @"%@", nm];
}
else
{
int j, n;
for(j=0,n=[a count]; j < n; j++)
{
obj = [a objectAtIndex: j];
nm = [self nameOfObject: obj];
[s appendFormat: @"%s%@", j > 0 ? ", " : "", nm];
}
}
}
return s;
}
@end
home
