在有些時候,需求中含有類似公司結(jié)構(gòu)的內(nèi)容,本身就是個多叉樹的結(jié)構(gòu),在交互過程中,遍歷查找的效率低下,然后就想了一下用字典樹的結(jié)構(gòu)去封裝,但是又存在一個問題,就是樹必須有唯一一個根節(jié)點(diǎn),如果有多家公司同屬一家公司,這些公司之間都是獨(dú)立的,沒有母公司的話,字典樹就不太適合了,然后就考慮一下,可不可以結(jié)合字典樹及哈希表的優(yōu)點(diǎn),生成一個可用的公司結(jié)構(gòu)類型的工具呢?在這種情況下,思慮后,寫出了以下代碼.(以下是修改后的,之前用的是Map,后來實(shí)際用起來,取出來的同級部門無序,改用數(shù)組,并增加了一些公開方法).
外層類:
{
Array<Node> _rootMap;
Map<ID,Node> _allNode;
}
節(jié)點(diǎn)類:
{
Obj element; //模型
String id; //模型id
Array<Node> arr; //模型對應(yīng)的子部門
__weak Node parentNode; //模型對應(yīng)的父部門
}
類似:
整個的數(shù)據(jù)結(jié)構(gòu):
_rootMap:存儲著所有公司的節(jié)點(diǎn),也就是根節(jié)點(diǎn),每個節(jié)點(diǎn)對應(yīng)一家公司,該公司節(jié)點(diǎn)Node下又存在子部門的Arr,并用弱引用指向父節(jié)點(diǎn),整個過程下去,一個完整的關(guān)系結(jié)構(gòu)就建好了
_allNode:保存著所有中間產(chǎn)生的節(jié)點(diǎn),并用ID作為key,這樣是為了快速查找到某個模型對應(yīng)的節(jié)點(diǎn),輔助用
為了讓其變得更通用,通過協(xié)議的方式,讓外部傳本身id和父id字段.
這樣整個數(shù)據(jù)結(jié)構(gòu)的查找速度超快
上面是整個的思路和結(jié)構(gòu),下面上代碼
公開的類及API
/*
針對組織架構(gòu)類型的數(shù)據(jù)結(jié)構(gòu)
注意事項(xiàng):
a.所有部門的id唯一
b.最頂層部門的parentID必須相同,可以都為nil
c.模型需要實(shí)現(xiàn)GYJDepartmentMapProtocal協(xié)議
1.使用方式
例子:針對這種類型的數(shù)據(jù)
{
"departments":[
{
"parentID":null,
"id":"oi12",
"info":"部門信息1"
},
{
"parentID":"oi12",
"id":"oias2",
"info":"部門信息2"
},
{
"parentID":"oi12",
"id":"oi2d2",
"info":"部門信息3"
},....
]
}
@interface Model:NSObject <GYJDepartmentMapProtocal>
@property(nonatomic,copy)NSString *parentID;
@property(nonatomic,copy)NSString *id;
.
.
.
部門的其他屬性
@end
@implementation Model
- (NSString *)nodeId
{
return self.id;
}
- (NSString *)nodeParentId
{
return self.parentID
}
@end
工具類代碼
@protocol GYJDepartmentMapProtocal <NSObject>
@required
//本身的id
- (NSString *)nodeId;
//父部門的id
- (NSString *)nodeParentId;
@end
@interface GYJDepartmentMap : NSObject
//添加元素
- (void)addElements:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements;
//返回當(dāng)前id的所有子id的元素
- (NSMutableArray *)children:(NSObject<GYJDepartmentMapProtocal>*)element;
//獲取父部門
- (NSObject<GYJDepartmentMapProtocal>*)parent:(NSObject<GYJDepartmentMapProtocal>*)element;
//返回兄弟部門
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)brothers:(NSObject<GYJDepartmentMapProtocal>*)element;
//返回所有的一級部門
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)roots;
//根據(jù)當(dāng)前對象,對象的層級關(guān)系 祖父部門->....->父部門->當(dāng)前部門
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)relationShipByElements:(NSObject<GYJDepartmentMapProtocal>*)element;
//所有的節(jié)點(diǎn)內(nèi)容
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*> *)allElements;
//清空保存的內(nèi)容
- (void)clear;
@end
內(nèi)部實(shí)現(xiàn)
#import "GYJDepartmentMap.h"
#import "GYJQueue.h"
#pragma mark 節(jié)點(diǎn)類
//節(jié)點(diǎn)
@interface GYJMultiwayNode : NSObject
@property(nonatomic,strong)NSObject<GYJDepartmentMapProtocal> *element; //存儲的單個模型對象
@property(nonatomic,copy)NSString *myId; //模型對象本身的部門id
@property(nonatomic,strong)NSMutableArray<GYJMultiwayNode *> *arr; //存儲所有的子部門
@property(nonatomic,weak)GYJMultiwayNode *parent; //父部門的節(jié)點(diǎn)
- (instancetype)initWithElement:(NSObject<GYJDepartmentMapProtocal> *)element myId:(NSString *)myId parent:(nullable GYJMultiwayNode *)parent;
@end
@implementation GYJMultiwayNode
- (instancetype)initWithElement:(NSObject<GYJDepartmentMapProtocal> *)element myId:(NSString *)myId parent:(nullable GYJMultiwayNode *)parent
{
if (self = [super init]) {
_element = element;
_myId = myId;
_parent = parent;
_arr = [[NSMutableArray alloc]init];
}
return self;
}
@end
#pragma mark 關(guān)系類
@interface GYJDepartmentMap ()
//存儲所有根部門的數(shù)組(內(nèi)部是多層關(guān)系結(jié)構(gòu))
@property(nonatomic,strong)NSMutableArray<GYJMultiwayNode *> *rootDic;
//存儲所有的部門(存儲單個部門),維護(hù)的一個字典,快速根據(jù)id查找對應(yīng)的node
@property(nonatomic,strong)NSMutableDictionary<NSString *,GYJMultiwayNode *> *allNodes;
@end
@implementation GYJDepartmentMap
- (instancetype)init
{
if (self = [super init]) {
_rootDic = [[NSMutableArray alloc]init];
_allNodes = [[NSMutableDictionary alloc]init];
}
return self;
}
//添加元素
- (void)addElements:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements
{
if(elements == nil || elements.count == 0) return;
NSString *rootId = [self searchRootParentID:elements];
//創(chuàng)建數(shù)組(存儲的為0,1) 標(biāo)記已用的對象,將OC的字符串比較轉(zhuǎn)化為數(shù)值的直接比較,減少msgSend的函數(shù)調(diào)用
int *markArr = (int *)malloc(sizeof(int) * elements.count);
//數(shù)組內(nèi)容初始化為0
memset(markArr, 0, sizeof(int)*elements.count);
//獲取到所有的根節(jié)點(diǎn)
NSArray<NSObject<GYJDepartmentMapProtocal>*> *tmp = [self searchAllRoot:elements byRootId:rootId markArr:markArr];
//存儲第一層的數(shù)據(jù)
[self addNodeToRoot:tmp];
//存儲后面的數(shù)據(jù)
[self addOthersNode:elements markArr:markArr];
free(markArr);
}
- (void)addOthersNode:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements markArr:(int *)markArr{
GYJQueue *queue = [[GYJQueue alloc]init]; //創(chuàng)建隊列
for (NSInteger i = 0; i < _rootDic.count; i++) {
GYJMultiwayNode *node = _rootDic[i];
[queue enterQueue:node];
}
while (![queue isEmpty]) {
GYJMultiwayNode *node = (GYJMultiwayNode *)[queue outQueue]; //隊列出隊
for (int i = 0; i<elements.count; i++) {
if(*(markArr+i) == 1) continue;
NSObject<GYJDepartmentMapProtocal>*element = elements[i];
if ([node.myId isEqualToString:[element nodeParentId]]) {
GYJMultiwayNode *childNode = [[GYJMultiwayNode alloc]initWithElement:element myId:[element nodeId] parent:node];
[queue enterQueue:childNode];
[node.arr addObject:childNode];
[_allNodes setValue:childNode forKey:childNode.myId];
*(markArr+i) = 1;
}
}
}
}
- (void)addNodeToRoot:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)rootElements {
if (rootElements==nil || rootElements.count==0) return;
for (NSInteger i = 0; i < rootElements.count; i++) {
NSObject<GYJDepartmentMapProtocal>*cur = rootElements[i];
GYJMultiwayNode *node = [[GYJMultiwayNode alloc]initWithElement:cur myId:[cur nodeId] parent:nil];
[_rootDic addObject:node];
[_allNodes setValue:node forKey:[cur nodeId]];
}
}
//查找所有根部門的父id,可以為空
- (nullable NSString *)searchRootParentID:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements
{
//找出其中一個根部門,獲取不存在的parentId
NSObject<GYJDepartmentMapProtocal> *tmpElemnt = elements[0];
mark:
for (int i = 0; i<elements.count; i++) {
NSObject<GYJDepartmentMapProtocal> *element = elements[i];
if ([[tmpElemnt nodeParentId] isEqualToString:[element nodeId]]) {
tmpElemnt = element;
goto mark;
}
}
return [tmpElemnt nodeParentId];
}
//查找統(tǒng)一的根部門
- (NSArray *)searchAllRoot:(NSArray<NSObject<GYJDepartmentMapProtocal>*> *)elements byRootId:(nullable NSString *)rootId markArr:(int *)markArr
{
NSMutableArray<NSObject<GYJDepartmentMapProtocal>*> *tmp = [[NSMutableArray alloc]init];
for (int i = 0; i<elements.count; i++) {
NSObject<GYJDepartmentMapProtocal> *element = elements[i];
if (rootId==nil && [element nodeParentId]==nil) {
[tmp addObject:element];
*(markArr+i) = 1;
}
if (rootId!=nil && [rootId isEqualToString:[element nodeParentId]]) {
[tmp addObject:element];
*(markArr+i) = 1;
}
}
return tmp.copy;
}
//返回當(dāng)前id的所有子id的元素
- (NSMutableArray *)children:(NSObject<GYJDepartmentMapProtocal>*)element
{
if (element == nil) return nil;
NSMutableArray *marr = [NSMutableArray array];
GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
for (NSInteger i = 0; i<node.arr.count; i++) {
GYJMultiwayNode *childNode = node.arr[i];
[marr addObject:childNode.element];
}
return marr;
}
//獲取父部門
- (NSObject<GYJDepartmentMapProtocal>*)parent:(NSObject<GYJDepartmentMapProtocal>*)element
{
if (element == nil) return nil;
GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
return node.parent==nil?nil:node.parent.element;
}
//返回根部門
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)roots
{
NSMutableArray *marr = [[NSMutableArray alloc]init];
for (NSInteger i = 0; i < _rootDic.count; i++) {
GYJMultiwayNode *node = _rootDic[i];
[marr addObject:node.element];
}
return marr;
}
//根據(jù)當(dāng)前元素返回對應(yīng)的部門node
- (GYJMultiwayNode *)nodeSearchByID:(NSString *)ID{
if (ID == nil) return nil;
if ([_allNodes.allKeys containsObject:ID]) {
return [_allNodes valueForKey:ID];
}
return nil;
}
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)relationShipByElements:(NSObject<GYJDepartmentMapProtocal>*)element
{
if (element==nil) return @[].mutableCopy;
GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
if (node==nil) return @[].mutableCopy;
NSMutableArray *marr = [[NSMutableArray alloc]init];
while (node.parent!=nil) {
[marr insertObject:node.element atIndex:0];
node = node.parent;
}
[marr addObject:element];
return marr;
}
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*> *)allElements{
NSMutableArray *marr = [[NSMutableArray alloc]init];
[_allNodes.allKeys enumerateObjectsUsingBlock:^(NSString * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
[marr addObject:[_allNodes valueForKey:obj].element];
}];
return marr;
}
//返回兄弟部門
- (NSMutableArray<NSObject<GYJDepartmentMapProtocal>*>*)brothers:(NSObject<GYJDepartmentMapProtocal>*)element{
GYJMultiwayNode *node = [self nodeSearchByID:[element nodeId]];
if (node.parent == nil) {
return [self roots];
}
GYJMultiwayNode *parent = node.parent;
NSMutableArray *marr = [[NSMutableArray alloc]init];
[parent.arr enumerateObjectsUsingBlock:^(GYJMultiwayNode * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
[marr addObject:obj.element];
}];
return marr;
}
//清空保存的內(nèi)容
- (void)clear
{
[_rootDic removeAllObjects];
[_allNodes removeAllObjects];
}
@end
下面是使用工具類驗(yàn)證效果的測試代碼
@class DepartmentModel;
@interface RootModel : NSObject
@property(nonatomic,copy)NSString *requestReceiveTime;
@property(nonatomic,copy)NSString *timeConsuming;
@property(nonatomic,strong)NSArray<DepartmentModel *> *resultContent;
+ (NSDictionary *)returnFalseData;//測試數(shù)據(jù)
@end
@interface DepartmentModel : NSObject<GYJDepartmentMapProtocal>
@property(nonatomic,copy)NSString *id;
@property(nonatomic,copy)NSString *parentId;
@property(nonatomic,copy)NSString *name;
@property(nonatomic,copy)NSString *isAll;
@property(nonatomic,copy)NSString *isChoose;
@end
#import "RootModel.h"
@implementation RootModel
//YYModel 容器屬性 需要實(shí)現(xiàn)的api
+ (nullable NSDictionary<NSString *, id> *)modelContainerPropertyGenericClass{
return @{@"resultContent":[DepartmentModel class]};
}
//返回測試數(shù)據(jù)
+ (NSDictionary *)returnFalseData
{
NSString *path = [[NSBundle mainBundle] pathForResource:@"departmentData.json" ofType:nil];
NSString *jsonStr = [[NSString alloc]initWithContentsOfFile:path encoding:NSUTF8StringEncoding error:0];
NSData *data = [jsonStr dataUsingEncoding:NSUTF8StringEncoding];
NSDictionary *dic = [NSJSONSerialization JSONObjectWithData:data options:0 error:nil];
return dic;
}
@end
@implementation DepartmentModel
//本身的id
- (NSString *)nodeId{
return _id;
}
//父部門的id
- (NSString *)nodeParentId{
return _parentId;
}
//為了打印時不打印地址,重寫這個方法,打印出模型信息
- (NSString *)description
{
return [NSString stringWithFormat:@"部門名:%@ ID:%@ 父ID:%@", _name,_id,_parentId];
}
@end
測試代碼:
//獲取測試數(shù)據(jù)
NSDictionary *dic = [RootModel returnFalseData];
RootModel *model = [RootModel yy_modelWithDictionary:dic];
NSArray<DepartmentModel *>* departments = model.resultContent;
//創(chuàng)建數(shù)據(jù)結(jié)構(gòu),并將數(shù)據(jù)建立關(guān)系
GYJDepartmentMap *map = [[GYJDepartmentMap alloc]init];
[map addElements:departments]; //DepartmentModel需要實(shí)現(xiàn) GYJDepartmentMapProtocal協(xié)議,關(guān)系的建立需要傳本身id和父id
//測試代碼
NSArray *roots = [map roots]; //獲取所有的父部門
NSLog(@"0.根部門%@",roots);
NSInteger index = arc4random_uniform(100)%roots.count;
NSLog(@"1.當(dāng)前父部門%@",roots[index]);
NSArray *children = [map children:roots[index]];
NSLog(@"1.對應(yīng)父部門的子部門%@",children);
for (NSInteger i = 0; i<departments.count; i++) {
DepartmentModel *model = departments[I];
if ([model.id isEqualToString:@"yuangong2"]) {
NSArray *relationShip = [map relationShipByElements:model];
NSLog(@"relationShip:%@",relationShip);
}
}
打印結(jié)果
2022-06-15 16:51:53.269550+0800 CompleteBinaryTree[34023:1107423] 0.根部門(
"\U90e8\U95e8\U540d:\U516c\U53f81 ID:gongsi1 \U7236ID:(null)",
"\U90e8\U95e8\U540d:\U516c\U53f82 ID:gongsi2 \U7236ID:(null)"
)
2022-06-15 16:51:53.269981+0800 CompleteBinaryTree[34023:1107423] 1.當(dāng)前父部門部門名:公司1 ID:gongsi1 父ID:(null)
2022-06-15 16:51:53.270420+0800 CompleteBinaryTree[34023:1107423] 1.對應(yīng)父部門的子部門(
"\U90e8\U95e8\U540d:\U8d22\U52a11 ID:caiwu1 \U7236ID:gongsi1",
"\U90e8\U95e8\U540d:\U7814\U53d11 ID:yanfa1 \U7236ID:gongsi1"
)
2022-06-15 16:51:53.270754+0800 CompleteBinaryTree[34023:1107423] relationShip:(
"\U90e8\U95e8\U540d:\U751f\U4ea7\U90e8 ID:shengchang2 \U7236ID:gongsi2",
"\U90e8\U95e8\U540d:\U751f\U4ea7\U7ecf\U7406 ID:jingli_shengchang \U7236ID:shengchang2",
"\U90e8\U95e8\U540d:\U64cd\U4f5c\U54582 ID:yuangong2 \U7236ID:jingli_shengchang",
"\U90e8\U95e8\U540d:\U64cd\U4f5c\U54582 ID:yuangong2 \U7236ID:jingli_shengchang"
)
內(nèi)容打印正確,并且我一個一個查看了map的結(jié)構(gòu),也是正確的,可放心使用(已經(jīng)在項(xiàng)目中用到了的,這個還是改進(jìn)后的工具)