/*
 * 对从 from 开始，到 is 末尾的所有数据进行移动，以 to 为起点
 *
 * 假设 3 为 from , 2 为 to ，
 * 之前：
 *   | 1 | 2 | 3 | 4 |
 * 之后：
 *   | 1 | 3 | 4 | 4 |
 *
 * T = theta(n)
 */
static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;

    // 需要移动的元素个数
    uint32_t bytes = intrev32ifbe(is->length)-from; 

    // 数组内元素的编码方式
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        // 计算地址
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        // 需要移动的字节数
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }

    // 走你！
    memmove(dst,src,bytes);
}

/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/*
 * 把 value 从 intset 中移除
 *
 * 移除成功将 *success 设置为 1 ，失败则设置为 0 。
 *
 * T = O(n)
 */
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;

    if (valenc <= intrev32ifbe(is->encoding) && // 编码方式匹配
        intsetSearch(is,value,&pos))            // 将位置保存到 pos
    {
        uint32_t len = intrev32ifbe(is->length);

        /* We know we can delete */
        if (success) *success = 1;

        /* Overwrite value with tail and update length */
        // 如果 pos 不是 is 的最末尾，那么显式地删除它
        // （如果 pos = (len-1) ，那么紧缩空间时值就会自动被『抹除掉』）
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);

        // 紧缩空间，并更新数量计数器
        is = intsetResize(is,len-1);
        is->length = intrev32ifbe(len-1);
    }

    return is;
}

/*
 * 向前或向后移动指定索引范围内的数组元素
 *
 * 函数名中的MoveTail其实是一个有误导性的名字，这个函数可以向前或向后移动元素，而不仅仅是向后
 *
 * 在添加新元素到数组时，就需要进行向后移动，如果数组表示如下(?表示一个未设置新值的空间)：
 * | x | y | z | ? |
 *     |<----->|
 * 而新元素n的pos为1，那么数组将移动y和z两个元素
 * | x | y | y | z |
 *         |<----->|
 * 接着就可以将新元素n设置到pos上了：
 * | x | n | y | z |
 *
 * 当从数组中删除元素时，就需要进行向前移动，如果数组表示如下，并且b为要删除的目标：
 * | a | b | c | d |
 *         |<----->|
 * 那么程序就会移动b后的所有元素向前一个元素的位置，从而覆盖b的数据：
 * | a | c | d | d |
 *     |<----->
 * 最后，程序再从数组末尾删除一个元素的空间：
 * | a | c | d |
 * 这样就完成了删除操作。
 *
 * T = O(N)
 */
static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    // 要移动的元素个数
    uint32_t bytes = intrev32ifbe(is->length)-from;
    // 集合的编码方式
    uint32_t encoding = intrev32ifbe(is->encoding);

    // 根据不同的编码
    // src = (Enc_t*)is->contents+from记录移动开始的位置
    // dst = (Enc_t*)is_.contents+to记录移动结束的位置
    // bytes *= sizeof(Enc_t)计算一共要移动多少字节
    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }
    // 进行移动
    // T = O(N)
    memmove(dst,src,bytes);
}

/* Search for the position of "value".
 *
 * 在集合is的底层数组中查找值value所在的索引。
 *
 * Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset.
 *
 * 成功找到value时，函数返回1，并将*pos的值设为value所在的索引。
 *
 * Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted.
 *
 * 当在数组中没找到value时，返回0。
 * 并将*pos的值设为value可以插入到数组中的位置。
 *
 * T = O(logN)
 */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    // 处理is为空时的函数
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
    	// 因为底层数组是有序的，如果value比数组中最后一个值都要大
    	// 那么value肯定不存在于集合中，并且应该将value添加到底层数组的最末端
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        // 因为底层数组是有序的，如果value比数组中最前一个值都要小
        // 那么value肯定不存在于集合中，并且应该将它添加到底层数组的最前端
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    // 在有序数组中进行二分查找
    // T = O(logN)
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    // 检查是否已经找到了value
    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

static void checkConsistency(intset *is) {
    for (uint32_t i = 0; i < (intrev32ifbe(is->length)-1); i++) {
        uint32_t encoding = intrev32ifbe(is->encoding);

        if (encoding == INTSET_ENC_INT16) {
            int16_t *i16 = (int16_t*)is->contents;
            assert(i16[i] < i16[i+1]);
        } else if (encoding == INTSET_ENC_INT32) {
            int32_t *i32 = (int32_t*)is->contents;
            assert(i32[i] < i32[i+1]);
        } else {
            int64_t *i64 = (int64_t*)is->contents;
            assert(i64[i] < i64[i+1]);
        }
    }
}

//给定元素个数len，重新分配intset的内存
static intset *intsetResize(intset *is, uint32_t len) {
    //算出contents中len个元素的字节数
	uint32_t size = len*intrev32ifbe(is->encoding);
    //重新分配内存
	is = zrealloc(is,sizeof(intset)+size);
    return is;
}

/*
 * 将 is 中位置 pos 的值保存到 *value 当中，并返回 1 。
 * 
 * 如果 pos 超过 is 的元素数量(out of range)，那么返回 0 。
 *
 * T = theta(1)
 */
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) {
    if (pos < intrev32ifbe(is->length)) {
        *value = _intsetGet(is,pos);
        return 1;
    }
    return 0;
}

void intsetRepr(intset *is) {
    int i;
    for (i = 0; i < intrev32ifbe(is->length); i++) {
        printf("%lld\n", (uint64_t)_intsetGet(is,i));
    }
    printf("\n");
}

/* Determine whether a value belongs to this set
 *
 * 检查给定值value是否是集合中的元素，
 *
 * 是返回1，不是返回0。
 *
 * T = O(logN)
 */
uint8_t intsetFind(intset *is, int64_t value) {
	// 计算value的编码
    uint8_t valenc = _intsetValueEncoding(value);
    // 如果value的编码大于集合的当前编码，那么value一定不存在于集合
    // 当value的编码小于等于集合的当前编码时，才再使用intsetSearch进行查找
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

/*
 * 查找 value 在 is 中的索引
 *
 * 查找成功时，将索引保存到 pos ，并返回 1 。
 * 查找失败时，返回 0 ，并将 value 可以插入的索引保存到 pos 。
 *
 * T = O(lg N)
 */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0,
        max = intrev32ifbe(is->length)-1,
        mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
        // is 为空时，总是查找失败
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            // 值比 is 中的最后一个值(所有元素中的最大值)要大
            // 那么这个值应该插入到 is 最后
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            // value 作为新的最小值，插入到 is 最前
            if (pos) *pos = 0;
            return 0;
        }
    }

    // 在 is 元素数组中进行二分查找 
    while(max >= min) {
        mid = (min+max)/2;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted.
 *
 * 在intset中找到value所在位置。
 * 如果找到就返回1并且将pos的值设为value所在位置
 * 如果没找到就返回0并且将pos的值设为value应该插入的位置
 * */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
    	//空集时直接返回0
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
        	//整数集为有序集，最后一个元素为最大的数，比它还大则说明value不在集合中
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
        	//第一个元素为最小值，比它小则说明value不在集合中
            if (pos) *pos = 0;
            return 0;
        }
    }

    //使用二分法查找元素
    while(max >= min) {
        mid = (min+max)/2;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
    	//找到元素，将pos设为mid
        if (pos) *pos = mid;
        return 1;
    } else {
    	//没找到元素，将pos设为min即该插入得位置
        if (pos) *pos = min;
        return 0;
    }
}

/* Resize the intset
 *
 * 调整整数集合的内存空间大小
 *
 * 如果调整后的大小要比集合原来的大小要大，那么集合中原有元素的值不会被改变。
 *
 * 返回值：调整大小后的整数集合
 *
 * T = O(N)
 */
static intset *intsetResize(intset *is, uint32_t len) {
	// 计算数组的空间大小
    uint32_t size = len*intrev32ifbe(is->encoding);
    // 根据空间大小，重新分配空间
    // 注意这里使用的是zrealloc，所以如果新空间大小比原来的空间大小要搭，那么数组原有的数据会被保留
    is = zrealloc(is,sizeof(intset)+size);
    return is;
}

/*
*
* 添加 value 并升级编码类型
*
*/
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);                   // 设置 new encoding
    is = intsetResize(is,intrev32ifbe(is->length)+1);      // 重新分配内存

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */

	// 从后往前移动 
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
	// 插入 val
    if (prepend)                  // value < 0 在 beginning 处插入
        _intsetSet(is,0,value);
    else                          // value > 0 在 end 处插入  
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

//更新整数集得编码，使编码升级为更大的整数并插入给定的值。
//注意value的值一定是比整数集的数都大或者都小，这样才有升级编码的意义
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    //将整数集的编码更新为新的编码后调用intsetResize重新分配内存
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    //调用_intsetGetEncoded(is,length,curenc)以旧的编码从整数集中取到数，设置到新的位置
    //从后往前进行操作，这样才不会覆盖掉原来的数值。
    //当value为负数是，prepend为1,这样第一个元素的位置就是value的，因为它一定是最小的值
    //当value非负，prepend为0,这样最后一个元素的位置就是value的，因为它一定是最大的值
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);

    // value<0 头插，value>0 尾插
    int prepend = value < 0 ? 1 : 0;

    // realloc
    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    // 逆向处理，防止数据被覆盖，一般的插入排序步骤
    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    // value<0 放在集合开头，否则放在集合末尾。
    // 因为，此函数是对整数所占内存进行升级，意味着 value 不是在集合中最大就是最小！
    /* Set the value at the beginning or the end. */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);

    // 更新 set size
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/*
 * 创建一个空的 intset
 *
 * T = theta(1)
 */
intset *intsetNew(void) {

    intset *is = zmalloc(sizeof(intset));

    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;

    return is;
}

/* Create an empty intset.
 *
 * 创建并返回一个新的空整数集合
 *
 * T = O(1)
 */
intset *intsetNew(void) {
	// 为整数集合结构分配空间
    intset *is = zmalloc(sizeof(intset));
    // 设置初始编码
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    // 初始化元素数量
    is->length = 0;
    return is;
}

/* Upgrades the intset to a larger encoding and inserts the given integer.
 *
 * 根据值value所使用的编码方式，对整数集合的编码进行升级，并将值value添加到升级后的整数集合中。
 *
 * 返回值：添加新元素之后的整数集合
 *
 * T = O(N)
 */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
	// 当前的编码方式
    uint8_t curenc = intrev32ifbe(is->encoding);
    // 新值所需的编码方式
    uint8_t newenc = _intsetValueEncoding(value);
    // 当前集合的元素数量
    int length = intrev32ifbe(is->length);
    // 根据value的值，决定是将它添加到底层数组的最前端还是最后端
    // 注意，因为value的编码比集合原有的其他元素的编码都要大
    // 所以value要么大于集合中的所有元素，要么小于集合中的所有元素
    // 因此，value只能添加到底层数组的最前端或最后端
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // 更新集合的编码方式
    is->encoding = intrev32ifbe(newenc);
    // 根据新编码对集合(的底层数组)进行空间调整
    // T = O(N)
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    // 根据集合原来的编码方式，从底层数组中取出集合元素
    // 然后再将元素以新编码的方式添加到集合中
    // 当完成了这个步骤以后，集合中所有原有的元素就完成了从旧编码到新编码的转换
    // 因为新分配的空间都放在数组的后端，所以程序先从后端向前端移动元素
    // 举个例子，假设原来有curenc编码的三个元素，它们在数组中排列如下：
    // | x | y | z |
    // 当程序对数组进行重分配之后，数组就被扩容了(符合?表示未使用的内存)：
    // | x | y | z | ? | ? | ? |
    // 这时程序从数组后端开始，重新插入元素：
    // | x | y | z | ? | z | ? |
    // | x | y |   y   | z | ? |
    // |   x   |   y   | z | ? |
    // 最后，程序可以将新元素添加到最后?号标示的位置中：
    // | x | y | z | new |
    // 上面演示的是新元素比原来的所有元素都打的情况，也即是prepend==0
    // 当新元素比原来的所有元素都小时(prepent==1)，调整的过程如下：
    // | x | y | z | ? | ? | ? |
    // | x | y | z | ? | ? | z |
    // | x | y | z | ? | y | z |
    // | x | y |   x   | y | z |
    // 当添加新键时，原本的| x | y |的数据将被新值代替
    // | new | x | y | z |
    // T = O(N)
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    // 设置新值，根据prepend的值来决定是添加到数组头还是数组尾
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 更新整数集合的元素数量
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    // 集合为空
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        // value 比最大元素还大
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        // value 比最小元素还小
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    // 二分查找
    while(max >= min) {
        mid = (min+max)/2;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}