type HashRing interface {
	PutNode(key string)
	DeleteNode(key string)
	FindNearNode(dataKey string ) string
	PrintRing()//输出节点在环上的分步-测试用
}
type HashRingVirtual interface {
	HashRing
	PutNodeExtend(nodeKey string ,virtualCount int )
}

//哈希算法-crc32(md5(key+md5(key)))
func getHashCode4KeyWithMd5(key string)uint32{
	var newKey=key+Md5([]byte(key))
	return getHashCode(newKey)
}
//哈希算法-crc32(md5(key))
func getHashCode(key string )uint32{
	return getCrcHash(Md5([]byte(key)))
}
//哈希算法-crc32(key)
func getCrcHash(key string)uint32{
	return crc32.ChecksumIEEE([]byte(key))
}

type SortArrayRingImpl struct {
	data []uint32
}
func(this *SortArrayRingImpl)Put(value uint32){
	if len(this.data)==0{
		this.data= append(this.data, value)
		return
	}
	findIndex:=this.findNearIndex(value)
	if findIndex==0{
		if value<=this.data[0]{//添加到头部
			this.insertBefore(value,0)
		}else{//添加到尾部
			this.insertBefore(value, len(this.data))
		}
	}else{//中间添加
		this.insertBefore(value,findIndex)
	}
}
func(this *SortArrayRingImpl)Delete(value uint32){
	if len(this.data)>0{
		index:=this.findNearIndex(value)
		if this.data[index]==value{
			this.data=deleteAt(this.data,index)
		}
	}
}
func (this *SortArrayRingImpl)findNearIndex(code uint32) int{
	keys:=this.data
	if len(keys)==0{
		return -1
	}
	if keys[0]>=code||keys[len(keys)-1]<code{
		return 0
	}
	if keys[len(keys)-1]==code{
		return len(keys)-1
	}
	var beginIndex=0
	var endIndex =len(keys)-1
	for endIndex-beginIndex>1{//二分查找
		middle:=int((endIndex+beginIndex)/2)
		if keys[middle]>code{
			endIndex =middle
			continue
		}
		if  keys[middle]==code{
			return middle
		}else{
			beginIndex=middle
		}
	}
	if keys[beginIndex]==code{
		return beginIndex
	}
	return endIndex
}

type SortArrayHashRing struct {
	keys map[uint32]string //反向索引，hashcode->key
	hashCodeRing SortArrayRing//排序队列实现数据环
	hashCodeFunc func(key string )uint32
}
func(hashRing *SortArrayHashRing)PutNode(key string){
	hashCode:=hashRing.getHashCode(key)
	hashRing.keys[hashCode]=key
	hashRing.hashCodeRing.Put(hashCode)
}
func (hashRing *SortArrayHashRing)DeleteNode(key string){
	code:=hashRing.getHashCode(key)
	if existKey,ok:=hashRing.keys[code];ok{
		if existKey==key{//find ，完全匹配，删除
			delete(hashRing.keys, code)//map中移除
			hashRing.hashCodeRing.Delete(code)//数据环移除
		}
	}
}
func (hashRing *SortArrayHashRing)FindNearNode(key string) string{
	code:=hashRing.getHashCode(key)
	findValue,find:=hashRing.hashCodeRing.FindNear(code)
	if find{
		return hashRing.keys[findValue]
	}else{
		return ""
	}
}

type SegmentHashRing struct {
	slotSize     uint32
	slotNodeMap  map[uint32]string //slot->nodekey
	nodeList     NodeList          //节点列表（按槽位多少升序排列）
	hashCodeFunc func(key string) uint32
}
func (this *SegmentHashRing)offerDataForNextNode() []uint32{
	//新节点添加时从现有节点列表中取槽位
	var offerData []uint32
	if len(this.nodeList)==0{//初始化全部槽位
		offerData =make([]uint32,0,this.slotSize)
		var i uint32
		for i=0;i<this.slotSize;i++{
			offerData=append(offerData, i)
		}
		return offerData
	}
	//计算新节点应该获取多少：新节点个数=总个数/（当前节点数+1） ，平均数等于新节点个数（有余数时部分节点会多）。
	newNodeSlotSize :=this.slotSize/ uint32(len(this.nodeList)+1)
	averageSlotSize:=newNodeSlotSize
	var offerTotal uint32 =0
	for i:=len(this.nodeList)-1;i>=0;i--{//出借从底部开始（底部节点个slot多）
		//逐个节点取-//每个节点给多少？  取小（当前节点个数-平均数   新节需要个数-已经分配个数）
		node:=this.nodeList[i]
		surplus:=node.size()-averageSlotSize//当前节点个数-平均数=本节点多余
		needs:=newNodeSlotSize-offerTotal//新节点还差个数
		if needs<=surplus{//差的个数小于多余的 给差的个数就行-够了。
			offerData=append(offerData,node.offer(needs)...)
			return offerData
		}else{
			offerData=append(offerData,node.offer(surplus)...)
			offerTotal+=surplus
		}
	}
	return offerData
}
func(this *SegmentHashRing)sendBackData(backData []uint32){
	//节点删除，将数据归还给剩下的节点。
	//如果没有节点，退出，一个节点，全部归还
	nodeSize:=len(this.nodeList)
	if nodeSize==0 {
		return
	}
	if nodeSize==1{
		this.sendBackToNode(this.nodeList[0],backData)
		return
	}
	totalBackCount :=len(backData)
	averageBackCound:=totalBackCount/nodeSize
	remainder:=totalBackCount%nodeSize
	currentIndex:=0
	haveBackCount:=0
	for i:=0;i<len(this.nodeList);i++{//归还从头部还，头部节点slot少
		if remainder>0{
			//归还 平均数+1
			backCount:=averageBackCound+1
			nextDataIndex:=currentIndex+backCount
			remainder=remainder-1
			haveBackCount=haveBackCount+backCount
			this.sendBackToNode( this.nodeList[i],backData[currentIndex:nextDataIndex])
		}else{
			backCount:=averageBackCound
			nextDataIndex:=currentIndex+backCount
			haveBackCount=haveBackCount+backCount
			this.sendBackToNode( this.nodeList[i],backData[currentIndex:nextDataIndex])
		}
		if haveBackCount== len(backData){//还完了
			return
		}
	}
}

func (this *SegmentHashRing)FindNearNode(key string) string{
	code:=this.getHashCode(key)
    slot:=code%this.slotSize
    nodeName,find:=this.slotNodeMap[slot]
    if find{
    	return nodeName
	}else{
		return ""
	}
}

type NodeManagerImpl struct {
	hashRing HashRing
	nodes map[string]Node
}
func(manager *NodeManagerImpl)PutNodeExtend(nodeKey string ,virtualCount int ){
	var node Node
	node.NodeIdentity=nodeKey
	node.VirtualCount=virtualCount
	manager.nodes[nodeKey]=node
	//manager.hashRing.Put(nodeKey)
	vNods:=manager.getVirtualNodes(nodeKey,virtualCount)
	for _,vNode:=range vNods{
		manager.hashRing.PutNode(vNode)
	}
}
func(manager *NodeManagerImpl)DeleteNode(nodeKey string ){
	if node, ok:=manager.nodes[nodeKey];ok{
		delete(manager.nodes,nodeKey)
		vNods:=manager.getVirtualNodes(nodeKey,node.VirtualCount)
		for _,vNode:=range vNods{
			manager.hashRing.DeleteNode(vNode)
		}
	}
}
func(manager *NodeManagerImpl)getVirtualNodes(nodeKey string ,virtualCount int) []string{
	var keys []string
	for i:=1;i<=virtualCount;i++ {
		var key string = nodeKey + "_" + strconv.Itoa(i)
		keys= append(keys, key)
	}
	return keys
}
func(manager *NodeManagerImpl)FindNearNode(dataKey  string) string{
	var nodeIdentityWithPrefix =manager.hashRing.FindNearNode(dataKey)
	if nodeIdentityWithPrefix!=""{
		s:=strings.Split(nodeIdentityWithPrefix,"_")
		return s[0]
	}else{
		return nodeIdentityWithPrefix//""
	}
}