@protocol LCGraphProtocol <NSObject>


/// 获取边的数量
-(int)edgesSize;


/// 获取顶点的数量
-(int)verticesSize;


/// 添加顶点
/// @param v 顶点
-(void)addVertex:(id)v;


/// 添加边
/// @param from 起始顶点
/// @param to 到达顶点
-(void)addEdgeFrom:(id)from to:(id)to;


/// 添加边
/// @param from 起始顶点
/// @param to 到达顶点
/// @param weight 权重
-(void)addEdgeFrom:(id)from to:(id)to weight:(id)weight;


/// 移除顶点
/// @param v 顶点
-(void)removeVertex:(id)v;


/// 移除边
/// @param from 起始顶点
/// @param to 到达顶点
-(void)removeEdgeFrom:(id)from to:(id)to;

@end

@interface LCVertex:NSObject
@property(nonatomic,strong)id value;                //顶点值
@property(nonatomic,strong)NSMutableSet * outEdges; //出度边集合
@property(nonatomic,strong)NSMutableSet * inEdges;  //入度边集合
+(instancetype)vertexWithValue:(id)value;
@end

@implementation LCVertex

+(instancetype)vertexWithValue:(id)value{
    LCVertex * vertex = [[LCVertex alloc] init];
    vertex.value = value;
    vertex.outEdges = [NSMutableSet set];
    vertex.inEdges  = [NSMutableSet set];
    return vertex;
}

-(BOOL)isEqual:(id)object{
    LCVertex* vertex = (LCVertex*)object;
    return [self.value isEqual:vertex.value];
}

-(NSString *)description{
    return self.value?[self.value description]:nil;
}

@end

@interface LCEdge : NSObject
@property(nonatomic,strong)id weight;       //权重
@property(nonatomic,  weak)LCVertex* from;  //起始顶点
@property(nonatomic,  weak)LCVertex* to;    //到达顶点
+(instancetype)edgeWithForm:(LCVertex*)from to:(LCVertex*)to;
@end

@implementation LCEdge

+(instancetype)edgeWithForm:(LCVertex *)from to:(LCVertex *)to{
    LCEdge * edge = [[LCEdge alloc] init];
    edge.from = from;
    edge.to = to;
    return edge;
}


-(BOOL)isEqual:(id)object{
    //自定义相等规则
    LCEdge * edge = (LCEdge*)object;
    return [self.from isEqual:edge.from] && [self.to isEqual:edge.to];
}

-(NSUInteger)hash{
    //要确保相等的两个对象的hash值是相等的
    //from.hash 跟 to.hash 计算得到 LCEdge的hash
    return self.from.hash*31 + self.to.hash;
}

-(NSString *)description{
    NSString* from = [NSString stringWithFormat:@"from=%@",self.from];
    NSString* to   = [NSString stringWithFormat:@"to=%@"  ,self.to];
    NSString* weight = [NSString stringWithFormat:@"weight=%@",self.weight];
    return [NSString stringWithFormat:@"%@,%@,%@",from,to,weight];
}

@end

@interface LCListGraph()
@property(nonatomic,strong)NSMutableDictionary* vertics;    //顶点
@property(nonatomic,strong)NSMutableSet* edges;             //边
@end

@implementation LCListGraph

#pragma mark - Set/Get

-(NSMutableDictionary *)vertics{
    if (_vertics == nil) {
        _vertics = [NSMutableDictionary dictionary];
    }
    return _vertics;
}


-(NSMutableSet *)edges{
    if (_edges == nil) {
        _edges = [NSMutableSet set];
    }
    return _edges;
}

#pragma mark - <LCGraphProtocol>

/// 获取边的数量
-(int)edgesSize{
    return (int)self.edges.count;
}


/// 获取顶点的数量
-(int)verticesSize{
    return (int)self.vertics.allKeys.count;
}


/// 添加顶点
/// @param v 顶点
-(void)addVertex:(id)v{
    if([self __verticsGetKey:v]) return;
    [self __verticsPutKey:v value:[LCVertex vertexWithValue:v]];
}


/// 添加边
/// @param from 起始顶点
/// @param to 到达顶点
-(void)addEdgeFrom:(id)from to:(id)to{
    [self addEdgeFrom:from to:to weight:nil];
}


/// 添加边
/// @param from 起始顶点
/// @param to 到达顶点
/// @param weight 权重
-(void)addEdgeFrom:(id)from to:(id)to weight:(nullable id)weight{
    
    //fromVertex
    LCVertex* fromVertex = [self __verticsGetKey:from];
    if (fromVertex == nil) {
        fromVertex = [LCVertex vertexWithValue:from];
        [self __verticsPutKey:from value:fromVertex];
    }
    
    //toVertex
    LCVertex* toVertex = [self __verticsGetKey:to];
    if (toVertex == nil) {
        toVertex = [LCVertex vertexWithValue:to];
        [self __verticsPutKey:to value:toVertex];
    }
    
    
    /**
     edge创建
     
     重要：
     set 的实现应该是哈希表，
     hash表操作的时候会调用被添加对象的hash、equal方法(哈希表原理)
     通过自实现被添加对象的hash方法，equal方法可以决定添加进set内的对象是否是同一对象
     */
    LCEdge * edge = [LCEdge edgeWithForm:fromVertex to:toVertex];
    edge.weight = weight;
    if ([fromVertex.outEdges containsObject:edge]) {
        [fromVertex.outEdges removeObject:edge];
        [toVertex.inEdges removeObject:edge];
        [self.edges removeObject:edge];
    }
    
    [fromVertex.outEdges addObject:edge];
    [toVertex.inEdges addObject:edge];
    [self.edges addObject:edge];
}


/// 移除顶点
/// @param v 顶点
-(void)removeVertex:(id)v{
    LCVertex * vertex = [self __verticsGetKey:v];
    if (vertex == nil) return;
    
    //移除顶点
    [self __verticsRemoveKey:v];
    
    
    //移除顶点的outEdges(一边遍历一边删除，需要用迭代器)
    NSEnumerator * outEnumerator = [vertex.outEdges objectEnumerator];
    LCEdge* outEdge;
    while ((outEdge = outEnumerator.nextObject)) {
        [vertex.outEdges removeObject:outEdge];
        [outEdge.to.inEdges removeObject:outEdge];
        [self.edges removeObject:outEdge];
    }

    
    //移除顶点的inedges(一边遍历一边删除，需要用迭代器)
    NSEnumerator * inEnumerator = [vertex.inEdges objectEnumerator];
    LCEdge* inEdge;
    while ((inEdge = inEnumerator.nextObject)) {
        [vertex.inEdges removeObject:inEdge];
        [inEdge.from.outEdges removeObject:inEdge];
        [self.edges removeObject:inEdge];
    }
}


/// 移除边
/// @param from 起始顶点
/// @param to 到达顶点
-(void)removeEdgeFrom:(id)from to:(id)to{
    LCVertex * fromVertex = [self __verticsGetKey:from];
    if (fromVertex == nil) return;
    
    LCVertex * toVertex = [self __verticsGetKey:to];
    if (toVertex == nil) return;
    

    LCEdge * edge = [LCEdge edgeWithForm:fromVertex to:toVertex];
    if ([fromVertex.outEdges containsObject:edge]) {
        [fromVertex.outEdges removeObject:edge];
        [toVertex.inEdges removeObject:edge];
        [self.edges removeObject:edge];
    }
}


#pragma mark - 内部方法

-(id)__verticsGetKey:(id)key{
    NSString* keyHash = [NSString stringWithFormat:@"%ld",[key hash]];
    return [self.vertics objectForKey:keyHash];
}

-(void)__verticsRemoveKey:(id)key{
    NSString* keyHash = [NSString stringWithFormat:@"%ld",[key hash]];
    [self.vertics removeObjectForKey:keyHash];
}


-(void)__verticsPutKey:(id)key value:(id)vertex{
    NSString* keyHash = [NSString stringWithFormat:@"%ld",[key hash]];
    [self.vertics setObject:vertex forKey:keyHash];
}






-(void)print{
    NSLog(@"[顶点]:%d 个-------------------",[self verticesSize]);
  
    
    [self.vertics enumerateKeysAndObjectsUsingBlock:^(NSString* key, LCVertex*  obj, BOOL * _Nonnull stop) {
        NSLog(@"");
        NSLog(@"%@",obj.value);
        NSLog(@"out-----------");
        NSLog(@"%@",obj.outEdges);
        NSLog(@"in-----------");
        NSLog(@"%@",obj.inEdges);
        NSLog(@"");
    }];
    
    
    NSLog(@"[边]:%d 条-------------------",[self edgesSize]);
    [self.edges enumerateObjectsUsingBlock:^(LCEdge*  obj, BOOL * _Nonnull stop) {
        NSLog(@"%@",obj);
    }];
     
    NSLog(@"");
}


@end