//整数集合结构体

typedef struct intset {

    uint32_t encoding;  //编码格式，有如下三种格式，初始值默认为INTSET_ENC_INT16

    uint32_t length;    //集合元素数量

    int8_t contents[];  //保存元素的数组，元素类型并不一定是ini8_t类型，柔性数组不占intset结构体大小，并且数组中的元素从小到大排列。

} intset;               

#define INTSET_ENC_INT16 (sizeof(int16_t))   //16位，2个字节，表示范围-32,768~32,767

#define INTSET_ENC_INT32 (sizeof(int32_t))   //32位，4个字节，表示范围-2,147,483,648~2,147,483,647

#define INTSET_ENC_INT64 (sizeof(int64_t))   //64位，8个字节，表示范围-9,223,372,036,854,775,808~9,223,372,036,854,775,807

intset *intsetNew(void) {

    intset *is = zmalloc(sizeof(intset));//分配内存空间

    is->encoding = intrev32ifbe(INTSET_ENC_INT16);//设置默认编码格式INTSET_ENC_INT16

    is->length = ;//初始化length

    return is;

}

//添加元素

//输入参数*is为原整数集合

//value为要添加的元素

//*success为是否添加成功的标志量 ，1表示成功，0表示失败

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {

    //确定要添加的元素的编码格式

    uint8_t valenc = _intsetValueEncoding(value);

    uint32_t pos;

    //如果success没有初始值，则初始化为1

    if (success) *success = ;

   //如果新的编码格式大于现在的编码格式，则升级并添加元素

    if (valenc > intrev32ifbe(is->encoding)) {

        //调用另一个方法

        return intsetUpgradeAndAdd(is,value);

    } else {

        //如果编码格式不变，则调用查询方法

        //输入参数is为原整数集合

        //value为要添加的数据

        //pos为位置

        if (intsetSearch(is,value,&pos)) {//如果找到了，则直接返回，因为数据是不可重复的。

            if (success) *success = ;

            return is;

        }

        //设置length

        is = intsetResize(is,intrev32ifbe(is->length)+);

        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+);

    }

    //设置数据

    _intsetSet(is,pos,value);

    is->length = intrev32ifbe(intrev32ifbe(is->length)+);

    return is;

}

//#define INT8_MAX 127

//#define INT16_MAX 32767

//#define INT32_MAX 2147483647

//#define INT64_MAX 9223372036854775807LL

static uint8_t _intsetValueEncoding(int64_t v) {

    if (v < INT32_MIN || v > INT32_MAX)

        return INTSET_ENC_INT64;

    else if (v < INT16_MIN || v > INT16_MAX)

        return INTSET_ENC_INT32;

    else

        return INTSET_ENC_INT16;

}

//根据输入参数value的编码格式，对整数集合is的编码格式升级

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {

    //当前集合的编码格式

    uint8_t curenc = intrev32ifbe(is->encoding);

    //根据对value解析获取新的编码格式

    uint8_t newenc = _intsetValueEncoding(value);

    //获取集合元素数量

    int length = intrev32ifbe(is->length);

    //如果要添加的数据小于0，则prepend为1，否则为0

    int prepend = value <  ?  : ;

   //设置集合为新的编码格式，并根据编码格式重新设置内存

    is->encoding = intrev32ifbe(newenc);

    is = intsetResize(is,intrev32ifbe(is->length)+);

    //逐步循环，直到length小于0，挨个重新设置每个值，从后往前

    while(length--)

        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    //如果value为负数，则放在最前面

    if (prepend)

        _intsetSet(is,,value);

    else//如果value为整数，设置最末尾的元素为value

        _intsetSet(is,intrev32ifbe(is->length),value);

    //重新设置length

    is->length = intrev32ifbe(intrev32ifbe(is->length)+);

    return is;

}

//找到is集合中值为value的下标，返回1，并保存在pos中，没有找到返回0，并将pos设置为value可以插入到数组的位置

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {

    int min = , max = intrev32ifbe(is->length)-, mid = -;

    int64_t cur = -;

    //如果集合为空，那么位置pos为0

    if (intrev32ifbe(is->length) == ) {

        if (pos) *pos = ;

        return ;

    } else {

        //因为数据是有序集合，如果要添加的数据大于最后一个数字，那么直接把要添加的值放在最后即可，返回最大值下标

        if (value > _intsetGet(is,intrev32ifbe(is->length)-)) {

            if (pos) *pos = intrev32ifbe(is->length);

            return ;

        } else if (value < _intsetGet(is,)) { //如果这个数据小于数组下标为0的数据，即为最小值 ，返回0

            if (pos) *pos = ;

            return ;

        }

    }

    //有序集合采用二分法

    while(max >= min) {

        mid = ((unsigned int)min + (unsigned int)max) >> ;

        cur = _intsetGet(is,mid);

        if (value > cur) {

            min = mid+;

        } else if (value < cur) {

            max = mid-;

        } else {

            break;

        }

    }

    //确定找到

    if (value == cur) {

        if (pos) *pos = mid;//设置参数pos，返回1，即找到位置

        return ;

    } else {//如果没找到，则min和max相邻，随便设置都行，并返回0

        if (pos) *pos = min;

        return ;

    }

}