public class RTree<T> {

    public enum SeedPicker {
        LINEAR, QUADRATIC
    }

    /**
     * 每个节点包含的最大entry数目
     */
    private final int M;

    /**
     * 每个节点包含的最小entry数目
     */
    private final int m;

    /**
     * 空间的维度,如平面则为2,空间点则为3
     */
    private final int D;

    private final float[] pointDims;

    private final SeedPicker seedPicker;

    /**
     * 根节点
     */
    private Node root;

    private volatile int size;

    /**
     * 构造默认R-Tree的参数
     * DEFAULT_M : M
     * DEFAULT_m : m
     * DEFAULT_D : D
     */
    private static final int DEFAULT_M = 50;
    private static final int DEFAULT_m = 2;
    private static final int DEFAULT_D = 2;

    /**
     * 创建一颗新的R-Tree
     * 
     * @param M maximum number of entries per node
     * @param m minimum number of entries per node (except for the root node)
     * @param D the number of dimensions of the RTree.
     */
    public RTree(int M, int m, int D, SeedPicker seedPicker) {
        assert (m <= (M / 2));
        this.D = D;
        this.M = M;
        this.m = m;
        this.seedPicker = seedPicker;
        pointDims = new float[D];
        root = buildRoot(true);
    }

    public RTree(int M, int m, int D) {
        this(M, m, D, SeedPicker.LINEAR);
    }

    /**
     * 使用默认参数构造一个R-Tree
     */
    public RTree() {
        this(DEFAULT_M, DEFAULT_m, DEFAULT_D, SeedPicker.LINEAR);
    }

    /**
     * 构造根节点
     *
     * @param asLeaf : 根节点是否为叶子节点
     * @return
     */
    private Node buildRoot(boolean asLeaf) {
        float[] initCoords = new float[D];
        float[] initDimensions = new float[D];
        for (int i = 0; i < this.D; i++) {
            initCoords[i] = (float) Math.sqrt(Float.MAX_VALUE);
            initDimensions[i] = -2.0f * (float) Math.sqrt(Float.MAX_VALUE);
        }
        return new Node(initCoords, initDimensions, asLeaf);
    }

    /**
     * getter
     */
    public int getMaxEntries() {
        return M;
    }

    public int getMinEntries() {
        return m;
    }

    public int getNumDims() {
        return D;
    }

    public int size() {
        return size;
    }

    /**
     * 在R-Tee中搜索和给定矩形有重叠(overlapping)的对象
     * 
     * @param coords 矩形的一个顶点(比如左上角)
     * @param dimensions 矩形长度.
     * 返回对象List,这些对象的最小边界矩形(MBR)和给定矩形重叠
     */
    public List<T> search(float[] coords, float[] dimensions) {
        assert (coords.length == D);
        assert (dimensions.length == D);

        LinkedList<T> results = new LinkedList<T>();
        search(coords, dimensions, root, results);

        return results;
    }

    private void search(float[] coords, float[] dimensions, Node n, LinkedList<T> results) {
        if (n.leaf) {
            for (Node e : n.children) {
                if (isOverlap(coords, dimensions, e.coords, e.dimensions)) {
                    results.add(((Entry) e).entry);
                }
            }
        } else {
            for (Node c : n.children) {
                if (isOverlap(coords, dimensions, c.coords, c.dimensions)) {
                    search(coords, dimensions, c, results); //继续在孩子节点中搜索
                }
            }
        }
    }

    /**
     * 删除R-Tree中在矩形rect内的数据entry
     * 
     * @param coords : 矩形的一个顶点(比如左上角)
     * @param dimensions : 矩形长度
     * @param entry : 待删除数据
     * 删除成功返回true
     */
    public boolean delete(float[] coords, float[] dimensions, T entry) {
        assert (coords.length == D);
        assert (dimensions.length == D);
        Node l = findLeaf(root, coords, dimensions, entry);
        if (l == null) {
            System.out.println("WTF?");
            findLeaf(root, coords, dimensions, entry);
        }
        assert (l != null) : "Could not find leaf for entry to delete";
        assert (l.leaf) : "Entry is not found at leaf?!?";
        ListIterator<Node> li = l.children.listIterator();
        T removed = null;
        while (li.hasNext()) {
            @SuppressWarnings("unchecked")
            Entry e = (Entry) li.next();
            if (e.entry.equals(entry)) {
                removed = e.entry;
                li.remove();
                break;
            }
        }
        if (removed != null) {
            condenseTree(l);
            size--;
        }
        if (size == 0) {
            root = buildRoot(true);
        }
        return (removed != null);
    }

    public boolean delete(float[] coords, T entry) {
        return delete(coords, pointDims, entry);
    }

    /**
     * 查找数据 entry 对应的叶子节点
     * @param n
     * @param coords
     * @param dimensions
     * @param entry
     * @return
     */
    private Node findLeaf(Node n, float[] coords, float[] dimensions, T entry) {
        if (n.leaf) {
            for (Node c : n.children) {
                if (((Entry) c).entry.equals(entry)) {
                    return n;
                }
            }
            return null;
        } else {
            for (Node c : n.children) {
                if (isOverlap(c.coords, c.dimensions, coords, dimensions)) {
                    Node result = findLeaf(c, coords, dimensions, entry);
                    if (result != null) {
                        return result;
                    }
                }
            }
            return null;
        }
    }

    /**
     * 压缩树
     * @param n
     */
    private void condenseTree(Node n) {
        Set<Node> q = new HashSet<Node>();
        while (n != root) {
            if (n.leaf && (n.children.size() < m)) {
                q.addAll(n.children);
                n.parent.children.remove(n);
            } else if (!n.leaf && (n.children.size() < m)) {
                // probably a more efficient way to do this...
                LinkedList<Node> toVisit = new LinkedList<Node>(n.children);
                while (!toVisit.isEmpty()) {
                    Node c = toVisit.pop();
                    if (c.leaf) {
                        q.addAll(c.children);
                    } else {
                        toVisit.addAll(c.children);
                    }
                }
                n.parent.children.remove(n);
            } else {
                tighten(n);
            }
            n = n.parent;
        }
        if (root.children.size() == 0) {
            root = buildRoot(true);
        } else if ((root.children.size() == 1) && (!root.leaf)) {
            root = root.children.get(0);
            root.parent = null;
        } else {
            tighten(root);
        }
        for (Node ne : q) {
            @SuppressWarnings("unchecked")
            Entry e = (Entry) ne;
            insert(e.coords, e.dimensions, e.entry);
        }
        size -= q.size();
    }

    /**
     * 清空整个R-Tree
     */
    public void clear() {
        root = buildRoot(true);
        //让GC做剩余的事情...
    }

    /**
     * 在RTree中插入数据entry, 和矩形匹配.
     * 
     * @param coords : 矩形的一个顶点(比如左上角)
     * @param dimensions : 矩形长度
     * @param entry : 待出入数据
     */
    public void insert(float[] coords, float[] dimensions, T entry) {
        assert (coords.length == D);
        assert (dimensions.length == D);
        Entry e = new Entry(coords, dimensions, entry);
        Node l = chooseLeaf(root, e);
        l.children.add(e);
        size++;
        e.parent = l;
        if (l.children.size() > M) {
            Node[] splits = splitNode(l);
            adjustTree(splits[0], splits[1]);
        } else {
            adjustTree(l, null);
        }
    }

    /**
     * Convenience method for inserting a point
     * 
     * @param coords
     * @param entry
     */
    public void insert(float[] coords, T entry) {
        insert(coords, pointDims, entry);
    }

    private void adjustTree(Node n, Node nn) {
        if (n == root) {
            if (nn != null) {
                // build new root and add children.
                root = buildRoot(false);
                root.children.add(n);
                n.parent = root;
                root.children.add(nn);
                nn.parent = root;
            }
            tighten(root);
            return;
        }
        tighten(n);
        if (nn != null) {
            tighten(nn);
            if (n.parent.children.size() > M) {
                Node[] splits = splitNode(n.parent);
                adjustTree(splits[0], splits[1]);
            }
        }
        if (n.parent != null) {
            adjustTree(n.parent, null);
        }
    }

    private Node[] splitNode(Node n) {
        // TODO: this class probably calls "tighten" a little too often.
        // For instance the call at the end of the "while (!cc.isEmpty())" loop
        // could be modified and inlined because it's only adjusting for the addition
        // of a single node. Left as-is for now for readability.
        @SuppressWarnings("unchecked")
        Node[] nn = new RTree.Node[] { n, new Node(n.coords, n.dimensions, n.leaf) };
        nn[1].parent = n.parent;
        if (nn[1].parent != null) {
            nn[1].parent.children.add(nn[1]);
        }
        LinkedList<Node> cc = new LinkedList<Node>(n.children);
        n.children.clear();
        Node[] ss = seedPicker == SeedPicker.LINEAR ? lPickSeeds(cc) : qPickSeeds(cc);
        nn[0].children.add(ss[0]);
        nn[1].children.add(ss[1]);
        tighten(nn);
        while (!cc.isEmpty()) {
            if ((nn[0].children.size() >= m) && (nn[1].children.size() + cc.size() == m)) {
                nn[1].children.addAll(cc);
                cc.clear();
                tighten(nn); // Not sure this is required.
                return nn;
            } else if ((nn[1].children.size() >= m) && (nn[0].children.size() + cc.size() == m)) {
                nn[0].children.addAll(cc);
                cc.clear();
                tighten(nn); // Not sure this is required.
                return nn;
            }
            Node c = seedPicker == SeedPicker.LINEAR ? lPickNext(cc) : qPickNext(cc, nn);
            Node preferred;
            float e0 = getRequiredExpansion(nn[0].coords, nn[0].dimensions, c);
            float e1 = getRequiredExpansion(nn[1].coords, nn[1].dimensions, c);
            if (e0 < e1) {
                preferred = nn[0];
            } else if (e0 > e1) {
                preferred = nn[1];
            } else {
                float a0 = getArea(nn[0].dimensions);
                float a1 = getArea(nn[1].dimensions);
                if (a0 < a1) {
                    preferred = nn[0];
                } else if (e0 > a1) {
                    preferred = nn[1];
                } else {
                    if (nn[0].children.size() < nn[1].children.size()) {
                        preferred = nn[0];
                    } else if (nn[0].children.size() > nn[1].children.size()) {
                        preferred = nn[1];
                    } else {
                        preferred = nn[(int) Math.round(Math.random())];
                    }
                }
            }
            preferred.children.add(c);
            tighten(preferred);
        }
        return nn;
    }

    // Implementation of Quadratic PickSeeds
    private RTree<T>.Node[] qPickSeeds(LinkedList<Node> nn) {
        @SuppressWarnings("unchecked")
        RTree<T>.Node[] bestPair = new RTree.Node[2];
        float maxWaste = -1.0f * Float.MAX_VALUE;
        for (Node n1 : nn) {
            for (Node n2 : nn) {
                if (n1 == n2)
                    continue;
                float n1a = getArea(n1.dimensions);
                float n2a = getArea(n2.dimensions);
                float ja = 1.0f;
                for (int i = 0; i < D; i++) {
                    float jc0 = Math.min(n1.coords[i], n2.coords[i]);
                    float jc1 = Math.max(n1.coords[i] + n1.dimensions[i], n2.coords[i] + n2.dimensions[i]);
                    ja *= (jc1 - jc0);
                }
                float waste = ja - n1a - n2a;
                if (waste > maxWaste) {
                    maxWaste = waste;
                    bestPair[0] = n1;
                    bestPair[1] = n2;
                }
            }
        }
        nn.remove(bestPair[0]);
        nn.remove(bestPair[1]);
        return bestPair;
    }

    /**
     * Implementation of QuadraticPickNext
     * 
     * @param cc the children to be divided between the new nodes, one item will be removed from this list.
     * @param nn the candidate nodes for the children to be added to.
     */
    private Node qPickNext(LinkedList<Node> cc, Node[] nn) {
        float maxDiff = -1.0f * Float.MAX_VALUE;
        Node nextC = null;
        for (Node c : cc) {
            float n0Exp = getRequiredExpansion(nn[0].coords, nn[0].dimensions, c);
            float n1Exp = getRequiredExpansion(nn[1].coords, nn[1].dimensions, c);
            float diff = Math.abs(n1Exp - n0Exp);
            if (diff > maxDiff) {
                maxDiff = diff;
                nextC = c;
            }
        }
        assert (nextC != null) : "No node selected from qPickNext";
        cc.remove(nextC);
        return nextC;
    }

    // Implementation of LinearPickSeeds
    private RTree<T>.Node[] lPickSeeds(LinkedList<Node> nn) {
        @SuppressWarnings("unchecked")
        RTree<T>.Node[] bestPair = new RTree.Node[2];
        boolean foundBestPair = false;
        float bestSep = 0.0f;
        for (int i = 0; i < D; i++) {
            float dimLb = Float.MAX_VALUE, dimMinUb = Float.MAX_VALUE;
            float dimUb = -1.0f * Float.MAX_VALUE, dimMaxLb = -1.0f * Float.MAX_VALUE;
            Node nMaxLb = null, nMinUb = null;
            for (Node n : nn) {
                if (n.coords[i] < dimLb) {
                    dimLb = n.coords[i];
                }
                if (n.dimensions[i] + n.coords[i] > dimUb) {
                    dimUb = n.dimensions[i] + n.coords[i];
                }
                if (n.coords[i] > dimMaxLb) {
                    dimMaxLb = n.coords[i];
                    nMaxLb = n;
                }
                if (n.dimensions[i] + n.coords[i] < dimMinUb) {
                    dimMinUb = n.dimensions[i] + n.coords[i];
                    nMinUb = n;
                }
            }
            float sep = (nMaxLb == nMinUb) ? -1.0f : Math.abs((dimMinUb - dimMaxLb) / (dimUb - dimLb));
            if (sep >= bestSep) {
                bestPair[0] = nMaxLb;
                bestPair[1] = nMinUb;
                bestSep = sep;
                foundBestPair = true;
            }
        }
        // In the degenerate case where all points are the same, the above
        // algorithm does not find a best pair. Just pick the first 2
        // children.
        if (!foundBestPair) {
            bestPair = new RTree.Node[] { nn.get(0), nn.get(1) };
        }
        nn.remove(bestPair[0]);
        nn.remove(bestPair[1]);
        return bestPair;
    }

    /**
     * Implementation of LinearPickNext
     * 
     * @param cc the children to be divided between the new nodes, one item will be removed from this list.
     */
    private Node lPickNext(LinkedList<Node> cc) {
        return cc.pop();
    }

    private void tighten(Node... nodes) {
        assert (nodes.length >= 1) : "Pass some nodes to tighten!";
        for (Node n : nodes) {
            assert (n.children.size() > 0) : "tighten() called on empty node!";
            float[] minCoords = new float[D];
            float[] maxCoords = new float[D];
            for (int i = 0; i < D; i++) {
                minCoords[i] = Float.MAX_VALUE;
                maxCoords[i] = Float.MIN_VALUE;

                for (Node c : n.children) {
                    // we may have bulk-added a bunch of children to a node (eg. in
                    // splitNode)
                    // so here we just enforce the child->parent relationship.
                    c.parent = n;
                    if (c.coords[i] < minCoords[i]) {
                        minCoords[i] = c.coords[i];
                    }
                    if ((c.coords[i] + c.dimensions[i]) > maxCoords[i]) {
                        maxCoords[i] = (c.coords[i] + c.dimensions[i]);
                    }
                }
            }
            for (int i = 0; i < D; i++) {
                // Convert max coords to dimensions
                maxCoords[i] -= minCoords[i];
            }
            System.arraycopy(minCoords, 0, n.coords, 0, D);
            System.arraycopy(maxCoords, 0, n.dimensions, 0, D);
        }
    }

    private RTree<T>.Node chooseLeaf(RTree<T>.Node n, RTree<T>.Entry e) {
        if (n.leaf) {
            return n;
        }
        float minInc = Float.MAX_VALUE;
        Node next = null;
        for (RTree<T>.Node c : n.children) {
            float inc = getRequiredExpansion(c.coords, c.dimensions, e);
            if (inc < minInc) {
                minInc = inc;
                next = c;
            } else if (inc == minInc) {
                float curArea = 1.0f;
                float thisArea = 1.0f;
                for (int i = 0; i < c.dimensions.length; i++) {
                    curArea *= next.dimensions[i];
                    thisArea *= c.dimensions[i];
                }
                if (thisArea < curArea) {
                    next = c;
                }
            }
        }
        return chooseLeaf(next, e);
    }

    /**
     * Returns the increase in area necessary for the given rectangle to cover the given entry.
     */
    private float getRequiredExpansion(float[] coords, float[] dimensions, Node e) {
        float area = getArea(dimensions);
        float[] deltas = new float[dimensions.length];
        for (int i = 0; i < deltas.length; i++) {
            if (coords[i] + dimensions[i] < e.coords[i] + e.dimensions[i]) {
                deltas[i] = e.coords[i] + e.dimensions[i] - coords[i] - dimensions[i];
            } else if (coords[i] + dimensions[i] > e.coords[i] + e.dimensions[i]) {
                deltas[i] = coords[i] - e.coords[i];
            }
        }
        float expanded = 1.0f;
        for (int i = 0; i < dimensions.length; i++) {
            expanded *= dimensions[i] + deltas[i];
        }
        return (expanded - area);
    }

    private float getArea(float[] dimensions) {
        float area = 1.0f;
        for (int i = 0; i < dimensions.length; i++) {
            area *= dimensions[i];
        }
        return area;
    }

    private boolean isOverlap(float[] scoords, float[] sdimensions, float[] coords, float[] dimensions) {
        final float FUDGE_FACTOR = 1.001f;
        for (int i = 0; i < scoords.length; i++) {
            boolean overlapInThisDimension = false;
            if (scoords[i] == coords[i]) {
                overlapInThisDimension = true;
            } else if (scoords[i] < coords[i]) {
                if (scoords[i] + FUDGE_FACTOR * sdimensions[i] >= coords[i]) {
                    overlapInThisDimension = true;
                }
            } else if (scoords[i] > coords[i]) {
                if (coords[i] + FUDGE_FACTOR * dimensions[i] >= scoords[i]) {
                    overlapInThisDimension = true;
                }
            }
            if (!overlapInThisDimension) {
                return false;
            }
        }
        return true;
    }

    /**
     * 节点
     */
    private class Node {
        /**
         * 高维矩形的一个定点,如左下角
         */
        final float[] coords;

        /**
         * 矩形的长度
         */
        final float[] dimensions;

        /**
         * 孩子节点
         */
        final LinkedList<Node> children;

        /**
         * 是否为叶子节点
         */
        final boolean leaf;

        /**
         * 父亲节点
         */
        Node parent;

        private Node(float[] coords, float[] dimensions, boolean leaf) {
            this.coords = new float[coords.length];
            this.dimensions = new float[dimensions.length];
            System.arraycopy(coords, 0, this.coords, 0, coords.length);
            System.arraycopy(dimensions, 0, this.dimensions, 0, dimensions.length);
            this.leaf = leaf;
            children = new LinkedList<Node>();
        }
    }

    /**
     * 实体,代表一个数据项
     * 注意:不是叶子节点,其父亲才是叶子节点
     */
    private class Entry extends Node {
        /**
         * 数据
         */
        final T entry;

        public Entry(float[] coords, float[] dimensions, T entry) {
            super(coords, dimensions, true);
            this.entry = entry;
        }

        public String toString() {
            return "Entry: " + entry;
        }
    }
}

http://sourceforge.net/projects/huhamhirehosts/files/

synchronized (vector) {
        for (Integer item : vector){
            doSomething(item);
        }
    }

public V putIfAbsent(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, true);
    }

public boolean remove(Object key, Object value) {
        int hash = hash(key.hashCode());
        if (value == null)
            return false;
        return segmentFor(hash).remove(key, hash, value) != null;
}

//只有当key匹配某一个值才取代
public V replace(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).replace(key, hash, value);
}

//只有当key和oldValue匹配的时候才替换
public boolean replace(K key, V oldValue, V newValue) {
        if (oldValue == null || newValue == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).replace(key, hash, oldValue, newValue);
}

boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;

E poll(long timeout, TimeUnit unit) throws InterruptedException;

public class FileCrawler implements Runnable {
    private final BlockingQueue<File> fileQueue;
    private final File root;

    public FileCrawler(BlockingQueue<File> fileQueue, File root) {
        this.fileQueue = fileQueue;
        this.root = root;
    }

    @Override
    public void run() {
        try {
            crawl(root);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    private void crawl(File root) throws InterruptedException {
        File[] files = root.listFiles();
        if (files != null && files.length > 0) {
            for (File file : files) {
                if (file.isDirectory())
                    crawl(file);
                else if (alreadyIndexed(file) == false)
                    fileQueue.put(file);
            }
        }
    }

    private boolean alreadyIndexed(File file) {
        //TODO
        return false;
    }
}

public class FileIndexer implements Runnable {

    private final BlockingQueue<File> fileQueue;

    public FileIndexer(BlockingQueue<File> fileQueue) {
        this.fileQueue = fileQueue;
    }

    @Override
    public void run() {
        try {
            while (true)
                index(fileQueue.take());
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    private void index(File file) {
        //TODO : do index
    }
}

public class CrawlAndIndex {
    public static void main(String[] args) {
        final int MAX_QUEUE_SIZE = 1024;
        final int INDEXER_COUNT = 100;

        final File[] roots = getFiles();

        BlockingQueue<File> fileQueue = new LinkedBlockingDeque<File>(MAX_QUEUE_SIZE);

        for (File file : roots)
            new Thread(new FileCrawler(fileQueue, file)).start();

        for(int i=0; i<INDEXER_COUNT; i++)
            new Thread(new FileIndexer(fileQueue)).start();

    }

    private static File[] getFiles() {
        //TODO
        return null;
    }
}

public class TaskRunnable implements Runnable {

    private final BlockingQueue<Task> taskQueue;

    public TaskRunnable(BlockingQueue<Task> taskQueue) {
        this.taskQueue = taskQueue;
    }

    @Override
    public void run() {
        try {
            while (true)
                process(taskQueue.take());
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt(); //恢复中断状态
        }
    }
}

public long timeTasks(int nThreads, final Runnable task) throws InterruptedException {
        final CountDownLatch endGate = new CountDownLatch(nThreads);

        for (int i = 0; i < nThreads; i++) {
            Thread t = new Thread() {
                @Override
                public void run() {
                    try {
                        task.run();
                    } finally {
                        endGate.countDown();
                    }
                }
            };
            t.start();
        }

        long start = System.nanoTime();
        endGate.await();
        long end = System.nanoTime();
        System.out.println("All Job Finish, use time(nano) = " + (end - start));

        return end - start;
    }

    public void doTask() throws InterruptedException{
        timeTasks(10, new Runnable() {
            @Override
            public void run() {
                try {
                    Thread.sleep((long) (1000 * Math.random()));
                    System.out.println("Finished.");
                } catch (InterruptedException e) {
                }
            }
        });
    }

public class Preload {
    private final FutureTask<BigDecimal> futureTask = new FutureTask<BigDecimal>(new Callable<BigDecimal>() {
        @Override
        public BigDecimal call() throws Exception {
            return timeConsumingWork();
        }
    });

    private final Thread thread = new Thread(futureTask);

    public void start() {
        thread.start();
    }

    private BigDecimal get(){
        try{
            return futureTask.get();    //获取数据
        }catch(ExecutionException e){
            Throwable cause = e.getCause();
            //处理各种原因的异常
            return null;
        }catch (InterruptedException e){
            return null;
        }
    }

    /**
     * 耗时的计算
     * 
     * @return
     */
    private BigDecimal timeConsumingWork() {
        // TODO
        return null;
    }
}

public class BoundedHashSet<T> {
    private final Set<T> set;
    private final Semaphore sem;

    public BoundedHashSet(int bound) {
        this.set = Collections.synchronizedSet(new HashSet<T>());
        sem = new Semaphore(bound);
    }

    public boolean add(T o) throws InterruptedException {
        sem.acquire();  //获得许可
        boolean added = false;

        try {
            added = set.add(o);
            return added;
        }finally {
            if(!added)
                sem.release();
        }
    }

    public boolean remove(Object o){
        boolean removed = set.remove(o);
        if(removed)
            sem.release();  //将许可放回资源池
        return removed;
    }
}

public interface Computable<A, V> {
    V compute(A arg) throws InterruptedException;
}

public class Memoizer<A, V> implements Computable<A, V> {

    private final ConcurrentHashMap<A, Future<V>> cache = new ConcurrentHashMap<A, Future<V>>();

    private final Computable<A, V> c;

    public Memoizer(Computable<A, V> c) {
        this.c = c;
    }

    @Override
    public V compute(final A arg) throws InterruptedException {
        while (true) {
            Future<V> f = cache.get(arg);
            if(f == null){
                Callable<V> eval = new Callable<V>() {
                    @Override
                    public V call() throws Exception {
                        return c.compute(arg);
                    }
                };

                FutureTask<V> ft = new FutureTask<V>(eval);
                f = cache.putIfAbsent(arg, ft);

                if(f == null){
                    f = ft;
                    ft.run();
                }
            }
            try{
                return f.get();
            }catch (CancellationException e){
                cache.remove(arg, f);
            }catch (ExecutionException e){
                //TODO:根据 e.getCause() 处理
            }
        }
    }
}

public class PersonSet {
    private final Set<Person> mySet = new HashSet<Person>();

    public synchronized void addPerson(Person p){
        mySet.add(p);
    }

    public synchronized boolean containPerson(Person p){
        return mySet.contains(p);
    }
}

Collections.synchronizedList(arrayList);
Collections.synchronizedMap(hashMap);
Collections.synchronizedSet(hashSet);

class SynchronizedCollection<E> implements Collection<E>, Serializable {
    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize
    ...
    public boolean add(E e) {
        synchronized(mutex) {return c.add(e);}
    }
    ...

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...

    public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
    }
}

static class UnmodifiableList<E> extends UnmodifiableCollection<E>
                      implements List<E> {
        static final long serialVersionUID = -283967356065247728L;
    final List<? extends E> list;
    ...
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }
}

static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize
    ...
}

static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {
        static final long serialVersionUID = -7754090372962971524L;

    final List<E> list;

    public E get(int index) {
        synchronized(mutex) {return list.get(index);}
        }
    public E set(int index, E element) {
        synchronized(mutex) {return list.set(index, element);}
    }
}

public class ListHelper<E> {
    public List<E> list = Collections.synchronizedList(new ArrayList<E>());

    public boolean putIfAbsent(E x){
        synchronized (list) {
            boolean absent = !list.contains(x);
            if(absent)
                list.add(x);

            return absent;
        }
    }
}

public class ImprovedList<T> implements List<T> {
    private final List<T> list;

    public ImprovedList(List<T> list){
        this.list = list;
    }

    public synchronized boolean putIfAbsent(T x){
        boolean absent = !list.contains(x);
        if(absent)
            list.add(x);
        return absent;
    }

    @Override
    public synchronized void clear() {
        list.clear();
    }
    //其他list方法的代理
}

0 2
6 67
43 71
39 107
189 140

36.2215

T(n) = 2T(n/2) + O(n),即T(n)=O(nlogn)