/// 添加或修改键值对，返回旧value
/// @param key key
/// @param value value
-(id)putWithKey:(nonnull id)key value:(nullable id)value{
    
    //扩容
    [self __reSize];
    
    NSUInteger index = [self __indexWithKey:key];
    
    //获取key对应的root节点
    LCHashMapNode * root = table[index];
    if (root == [NSNull null]) {
        root = [LCHashMapNode nodeWithKey:key value:value parent:nil];
        table[index] = root;
        self.size++;
        [self afterAdd:root];
        return nil;
    }
    
    
    LCHashMapNode * parent = root;
    LCHashMapNode * node   = root;
    
    LCCompareType type = LCCompareEqual;
    
    id k1 = key;
    NSUInteger h1 = [self __raodongHash:k1];
    LCHashMapNode* result = nil;
    BOOL searched = false;//是否已经遍历过这个key,避免每次循环都遍历
    do {
        //在此处记录父节点
        parent = node;
        
        id k2 = node.key;
        NSUInteger h2 = node.hash;
        
        //1、先比较哈希值
        if (h1<h2) {
            type = LCCompareLess;
        }else if(h1>h2){
            type = LCCompareGreater;
            
            
        //2、再比较是否相等
        }else if([k1 isEqual:k2]){
            /**
             重要注意：
             equal来确定是否相等
             compare是比较大小，compare的比较的结果是0，并不能确定k1 与 k2 相等。只能说明大小相等。
             比如两个兄弟，辈分相同，但并不是同一个人。
             
             equal 与 compare 一定要区别开来，一个是比较相等，一个是比较大小。
             */
            type = LCCompareEqual;
            
        //3、再比较是否有可比较性
        }else if(k1 && k2
                 && [k1 isMemberOfClass:k2]
                 && [k1 respondsToSelector:@selector(compare:)]
                 && (type = (LCCompareType)[k1 compare:k2])!= LCCompareEqual){
            /**
             k1、k2具有可比较性，能比较出大小，就按比较结果处理。但比较大小相等时，不能认定为k1 与 k2相等。
             */
            
            
        //4、能来到这里就是哈希值相等、不equal、不具备可比较性。已经比无可比了
        }else if(searched){
            //4-0、已经遍历过并且没有找到，直接比较内存地址
            
            //没有找到key对应的节点
//            NSString * kp1 = [NSString stringWithFormat:@"%p",k1];
//            NSString * kp2 = [NSString stringWithFormat:@"%p",k2];
//            type = (LCCompareType)[kp1 compare:kp2];
            
            //这里也可以选择一直向右，规则自己定
            type = LCCompareGreater;


        }else{
            /**
             以下几种情况都会来到此处：
             k1 = nil && k1!= nil;
             k1 !=nil && k2 = nil;
             k1 !=nil && k2!=nil; && k1与k2不是同类型
             k1 !=nil && k2!=nil; && k1与k2是同类型 && 不具备可比性
             k1 !=nil && k2!=nil; && k1与k2是同类型 && 具备可比性 && 大小相等
             */
            
            //4-1、先通过遍历节点，查看是否有相同的key
            if (
                ((node.right!=nil && (result = [self __Node:node.right key:k1])!=nil))
              ||((node.left !=nil && (result = [self __Node:node.left  key:k1])!=nil))
            ) {
                //在右侧或者左侧找到了相同的节点
                node = result;
                type = LCCompareEqual;
                searched = true;
                
                
                
            //4-2、所有情况都比较完了，只能用内存地址比较了
            }else{
                //没有找到key对应的节点
//                NSString * kp1 = [NSString stringWithFormat:@"%p",k1];
//                NSString * kp2 = [NSString stringWithFormat:@"%p",k2];
//                type = (LCCompareType)[kp1 compare:kp2];
                
                //这里也可以选择一直向右，规则自己定
                type = LCCompareGreater;
            }
        }
        
        
        switch (type) {
            case LCCompareLess:
                node = node.left;
                break;
            case LCCompareGreater:
                node = node.right;
                break;
            case LCCompareEqual:{
                id oldValue = node.value;
                node.key = key;
                node.value = value;
                return oldValue;
                break;
            }
            default:
                break;
        }
    }while (node);
    
    
    //如果能来到这里 node == nil; 所以应该在循环里记录下添加节点的父节点和比较结果
    LCHashMapNode * addNode =  [self creatNodeWithKey:key value:value parent:parent];
    
    if (type == LCCompareLess) {
        parent.left = addNode;
    }else if(type ==LCCompareGreater){
        parent.right = addNode;
    }else if(type == LCCompareEqual){
        
    }
    
    _size++;
    
    [self afterAdd:addNode];
    
    return nil;
}

/// 通过key找到对应的node节点
/// @param key key
-(LCHashMapNode*)__Node:(id)key{
    LCHashMapNode* root = table[[self __indexWithKey:key]];
    return root == [NSNull null]?nil: [self __Node:root key:key];
}




/// 从一棵树内找到key对应的节点（通过传入的节点和key，找到key对应的节点）
/// @param node 开始查找的节点
/// @param k1 key
-(LCHashMapNode*)__Node:(LCHashMapNode*)node key:(id)k1{
    
    NSUInteger h1 = [self __raodongHash:k1];
    
    //存储查找结果
    LCHashMapNode* result = nil;
    LCCompareType type = LCCompareEqual;
    while (node!=nil) {
        id k2 = node.key;
        NSUInteger h2 = node.hash;
        
        //1、先比较哈希值
        if (h1>h2) {
            node = node.right;
        }else if(h1<h2){
            node = node.left;
            
        //2、再比较是否相等
        }else if((k1 == nil && k2 == nil) || [k1 isEqual:k2]){
            //是否可以用下面写法代替
            //k1==nil?k2==nil:[k1 isEqual:k2];
            return node;
            
            
        //3、再看是否具有可比较性
        }else if(k1 && k2
                 && [k1 isMemberOfClass:k2]
                 && [k1 respondsToSelector:@selector(compare:)]
                 && (type = (LCCompareType)[k1 compare:k2]) != LCCompareEqual){
            
            node = (type == LCCompareGreater?node.right:node.left);
            
            
        //4、不具备可比较性（递归遍历）
        }else if(node.right!=nil && (result = [self __Node:node.right key:k1]) !=nil){
            //在右侧找到
            return result;
            
            
        }else if(node.left!=nil && (result = [self __Node:node.left key:k1]) !=nil){
            //在左侧找到
            return result;

        }else{
            //没有找到
            return nil;
        }
    }
    
    return nil;
}

-(void)__reSize{
    
    //装填因子<=0.75
    if(1.0 * self.size / table.count <= DEFAULT_LOAD_FACTOR) return;

    //保留旧的table
    NSMutableArray* oldTable = table;

    //扩容至以前的两倍
    NSUInteger newCapacity = oldTable.count<<1;
    table = [NSMutableArray arrayWithCapacity:newCapacity];
    for (int i=0; i<newCapacity; i++) {
        table[i] = [NSNull null];
    }
    
    NSLog(@"扩容至 %zd",table.count);

    queue<LCHashMapNode*> queueNode;

    for (int i = 0; i<oldTable.count; i++) {
        if(oldTable[i] == [NSNull null]) continue;

        queueNode.push(oldTable[i]);

        while (queueNode.size()) {
            LCHashMapNode* front = queueNode.front();
            queueNode.pop();

            if(front.left) queueNode.push(front.left);
            if(front.right) queueNode.push(front.right);

            //挪动代码得放到最后边
            [self __moveNode:front];
        }
    }
}


-(void)__moveNode:(LCHashMapNode*)newNode{
    
    //重置node
    newNode.parent = nil;
    newNode.left = nil;
    newNode.right = nil;
    newNode.color = RED;
    
    NSUInteger index = [self __indexWithNode:newNode];
    
    //获取对应的root节点
    LCHashMapNode * root = table[index];
    if (root == [NSNull null]) {
        root = newNode;
        table[index] = root;
        [self afterAdd:root];
        return;
    }
    
    
    LCHashMapNode * parent = root;
    LCHashMapNode * node   = root;
    
    LCCompareType type = LCCompareEqual;
    
    id k1 = newNode.key;
    NSUInteger h1 = [self __raodongHash:k1];

    do {
        //在此处记录父节点
        parent = node;
        
        id k2 = node.key;
        NSUInteger h2 = node.hash;
        
        //1、先比较哈希值
        if (h1<h2) {
            type = LCCompareLess;
        }else if(h1>h2){
            type = LCCompareGreater;
        }else if(k1 && k2
                 && [k1 isMemberOfClass:k2]
                 && [k1 respondsToSelector:@selector(compare:)]
                 && (type = (LCCompareType)[k1 compare:k2])!= LCCompareEqual){

            
        }else{
            type = LCCompareGreater;
        }
        
        /**
         为什么不需要equal判断和遍历，因为只是移动节点，肯定没有相同的节点存才
         */

        switch (type) {
            case LCCompareLess:
                node = node.left;
                break;
            case LCCompareGreater:
                node = node.right;
                break;
            default:
                break;
        }
    }while (node);
    
    
    //如果能来到这里 node == nil; 所以应该在循环里记录下添加节点的父节点和比较结果
    if (type == LCCompareLess) {
        parent.left = newNode;
    }else if(type ==LCCompareGreater){
        parent.right = newNode;
    }
        
    [self afterAdd:newNode];
}