// "static void main" must be defined in a public class.
public class Main {
    
    public static void main(String[] args) {
        List<INode> nodeList = new ArrayList<>();
        nodeList.add(new Node("1"));
        nodeList.add(new Node("2"));
        nodeList.add(new Node("3"));
        nodeList.add(new Node("4"));
        nodeList.add(new Node("5"));
        nodeList.add(new Node("6"));
        nodeList.add(new Node("7"));
        nodeList.add(new Node("8"));
        nodeList.add(new Node("9"));
        nodeList.add(new Node("10"));
        IConsistentHash hash = new ConsistentHash(nodeList);
        System.out.println(hash);
        
        // 测试
        Map<String, Integer> testMap = new HashMap<>();
        Random rand = new Random();
        for (int i = 0; i < 1000000; i++) {
            INode node = hash.selectNode(rand.nextInt(Integer.MAX_VALUE));
            if (!testMap.containsKey(node.getId())) {
                testMap.put(node.getId(), 1);
            } else {
                testMap.put(node.getId(), testMap.get(node.getId()) + 1);
            }
        }
        System.out.println(testMap);
        
        // 计算标准差
        int sum = 0;
        for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
            sum += entry.getValue();
        }
        double average = sum / testMap.size();
        int total = 0;
        for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
            total += (entry.getValue() - average) * (entry.getValue() - average);
        }
        double standardDeviation = Math.sqrt(total / testMap.size());
        System.out.println(standardDeviation);
    }
}
interface INode {
    String getId();
}
class Node implements INode {
    private String id;
        
    public Node(String id) {
        this.id = id;
    }
        
    public String getId() {
        return id;
    }
    public void setId(String id) {
        this.id = id;
    }
    public String toString() {
        return id;
    }
}
class NodeWrapper implements INode {
    private INode node;
    
    public NodeWrapper(INode node) {
        this.node = node;
    }
    
    public String getId() {
        return this.node.getId();
    }
    public String toString() {
        return getId();
    }
}
interface IConsistentHash {
    void addNode(INode node);
    void deleteNode(INode node);
    INode selectNode(Integer key);
}
class ConsistentHash implements IConsistentHash {
    private static final int VIRTUAL_NODE_COUNT = 100;
    private static final int CIRCLE_LENGTH = Integer.MAX_VALUE;
    private List<INode> nodeList;
    // 存储每个节点在哈希环上对应的位置
    private Map<INode, Integer> nodeIndexMap = new HashMap<>();
    // 存储位置与节点的映射关系
    private Map<Integer, INode> nodeMap = new TreeMap<>();
    // 存储节点与虚拟节点的映射关系
    private Map<INode, List<INode>> virtualNodeMap = new HashMap<>();
    
    public ConsistentHash(List<INode> nodeList) {
        this.nodeList = nodeList;
        for (INode node : this.nodeList) {
            doAddNode(node);
        }
        
        // System.out.println(nodeIndexMap);
        // System.out.println(nodeMap);
        // System.out.println(virtualNodeMap);
    }
    
    public void addNode(INode node) {
        this.nodeList.add(node);
        doAddNode(node);
    }
    
    public void deleteNode(INode node) {
        this.nodeList.remove(node);
        
        List<INode> virtualNodeList = virtualNodeMap.get(node);
        for (INode vNode : virtualNodeList) {
            deleteNodeFromCircle(vNode);
        }
        virtualNodeMap.remove(node);
        deleteNodeFromCircle(node);
    }
    
    public INode selectNode(Integer key) {
        Integer index = hash(key);
        Integer minIndex = Integer.MAX_VALUE;
        for (Map.Entry<Integer, INode> entry : nodeMap.entrySet()) {
            if (entry.getKey() >= index) {
                return entry.getValue();
            }
            if (minIndex > entry.getKey()) {
                minIndex = entry.getKey();
            }
        }
        return nodeMap.get(minIndex);
    }
    
    private void doAddNode(INode node) {
        List<INode> virtualNodeList = new ArrayList<>();
        for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
            INode vNode = new NodeWrapper(node);
            virtualNodeList.add(vNode);
            
            addNodeToCircle(vNode);
        }
        virtualNodeMap.put(node, virtualNodeList);
        addNodeToCircle(node); 
    }
    
    private void addNodeToCircle(INode node) {
        Integer index = hash(node);
        
        nodeIndexMap.put(node, index);
        nodeMap.put(index, node);
    }
    
    private void deleteNodeFromCircle(INode node) {
        Integer index = nodeIndexMap.get(node);
        nodeMap.remove(index);
        nodeIndexMap.remove(node);
    }
    
    private Integer hash(Object obj) {
       return obj.hashCode() % CIRCLE_LENGTH;
    }
}