封裝公司架構(gòu)類型的數(shù)據(jù)結(jié)構(gòu)(多叉樹)

在有些時候,需求中含有類似公司結(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)的父部門
}
類似:


image.png

整個的數(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)后的工具)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末干像,一起剝皮案震驚了整個濱河市本刽,隨后出現(xiàn)的幾起案子百炬,更是在濱河造成了極大的恐慌雪隧,老刑警劉巖蔽挠,帶你破解...
    沈念sama閱讀 206,723評論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件汇四,死亡現(xiàn)場離奇詭異踏烙,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)黔龟,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,485評論 2 382
  • 文/潘曉璐 我一進(jìn)店門妇智,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人氏身,你說我怎么就攤上這事巍棱。” “怎么了蛋欣?”我有些...
    開封第一講書人閱讀 152,998評論 0 344
  • 文/不壞的土叔 我叫張陵航徙,是天一觀的道長。 經(jīng)常有香客問我陷虎,道長到踏,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 55,323評論 1 279
  • 正文 為了忘掉前任尚猿,我火速辦了婚禮窝稿,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘凿掂。我一直安慰自己伴榔,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,355評論 5 374
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著踪少,像睡著了一般塘安。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上援奢,一...
    開封第一講書人閱讀 49,079評論 1 285
  • 那天兼犯,我揣著相機(jī)與錄音,去河邊找鬼萝究。 笑死免都,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的帆竹。 我是一名探鬼主播绕娘,決...
    沈念sama閱讀 38,389評論 3 400
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼栽连!你這毒婦竟也來了险领?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,019評論 0 259
  • 序言:老撾萬榮一對情侶失蹤秒紧,失蹤者是張志新(化名)和其女友劉穎绢陌,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體熔恢,經(jīng)...
    沈念sama閱讀 43,519評論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡脐湾,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,971評論 2 325
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了叙淌。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片秤掌。...
    茶點(diǎn)故事閱讀 38,100評論 1 333
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖鹰霍,靈堂內(nèi)的尸體忽然破棺而出闻鉴,到底是詐尸還是另有隱情,我是刑警寧澤茂洒,帶...
    沈念sama閱讀 33,738評論 4 324
  • 正文 年R本政府宣布孟岛,位于F島的核電站,受9級特大地震影響督勺,放射性物質(zhì)發(fā)生泄漏渠羞。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,293評論 3 307
  • 文/蒙蒙 一智哀、第九天 我趴在偏房一處隱蔽的房頂上張望堵未。 院中可真熱鬧,春花似錦盏触、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,289評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽雌芽。三九已至,卻和暖如春辨嗽,著一層夾襖步出監(jiān)牢的瞬間世落,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,517評論 1 262
  • 我被黑心中介騙來泰國打工糟需, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留屉佳,地道東北人。 一個月前我還...
    沈念sama閱讀 45,547評論 2 354
  • 正文 我出身青樓洲押,卻偏偏與公主長得像武花,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子杈帐,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,834評論 2 345

推薦閱讀更多精彩內(nèi)容