走自己的路

路漫漫其修远兮，吾将上下而求索
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 4 文章 :: 118 评论 :: 0 Trackbacks
java实现的同步循环链表
public class CircularLinkedList<E> {
    private Entry<E> head;

    // Last element of the list. tail.next = head
    private Entry<E> tail;
    private Entry<E> next;
    private Entry<E> lastReturned;
    private int size = 0;

    /**
     * Class to hold the individual elements.
     * 
     * @param <E>
     */
    private static class Entry<E> {
        E element;

        Entry<E> next;

        Entry(E element, Entry<E> next) {
            this.element = element;
            this.next = next;
        }

        Entry(E element) {
            this.element = element;
        }
    }

    public CircularLinkedList() {
        head = tail = null;
    }

    @SuppressWarnings("unchecked")
    public CircularLinkedList(Collection<? extends E> c) {
        Object[] eles = c.toArray();
        int nums = eles.length;

        for (int i = 0; i < nums; i++) {
            this.add((E) eles[i]);
        }
    }

    /**
     * Circular iterator
     * 
     * @return
     */
    public synchronized E next() {
        if (head == null) {
            throw new NoSuchElementException();
        } else {
            // Entry<E> rtned = next;
            lastReturned = next;
            next = next.next;
            return lastReturned.element;
        }
    }

    public synchronized boolean hasNext() {
        return size > 0;
    }

    public synchronized boolean isEmpty() {
        return size <= 0;
    }

    /**
     * Remove obj from the circular linked list and return the removed object
     * 
     * @param obj
     * @return
     */
    public synchronized E remove(E obj) {
        if (head == null || tail == null)
            throw new NoSuchElementException();
        Entry<E> p = head, temp = head, found = null;

        if (head.element.equals(obj)) {
            if (head.next == head) {
                found = head;
                head = null;
                tail = null;
                size--;
                return found.element;
            } else {
                found = head;
                head = found.next;
                temp = tail;
            }
        } else {
            p = head.next;
            while (p != head) {
                if (p.element.equals(obj)) {
                    found = p;
                    break;
                }
                temp = p;
                p = p.next;
            }
            if (found == tail) {
                tail = temp;
            }
        }

        if (found == null) {
            throw new NoSuchElementException();
        }

        E result = found.element;
        temp.next = found.next;

        if (found == next) {
            next = found.next;
        }

        found.next = null;
        found.element = null;
        size--;
        return result;
    }
    
    /**
     * Contains the specified object or not
     * @param obj
     * @return
     */
    public synchronized boolean contains(E obj) {
        if (head == null || tail == null)
            return false;
        
        Entry<E> found = null;
        if (head.element.equals(obj)) {
            found = head;
        } else {
            Entry<E> p = head.next;
            while (p != head) {
                if (p.element.equals(obj)) {
                    found = p;
                    break;
                }
                p = p.next;
            }
        }
        if (found == null) {
            return false;
        }
        return true;
    }

    /**
     * Add obj to the circular linked list.
     * 
     * @param obj
     */
    public synchronized void add(E obj) {
        Entry<E> e = new Entry<E>(obj);
        if (head == null) {
            size++;
            head = e;
            head.next = head;
            tail = head;
            next = head;
            return;
        }
        if (lastReturned == tail) {
            next = e;
        }
        size++;
        tail.next = e;
        tail = e;
        tail.next = head;
    }

    /**
     * Size of the list.
     * 
     * @return
     */
    public synchronized int size() {
        return size;
    }

    /**
     * @return the head
     */
    public synchronized E getHead() {
        if (null == head) {
            throw new NoSuchElementException();
        }
        return head.element;
    }

    /**
     * @return the tail
     */
    public synchronized E getTail() {
        if (null == tail) {
            throw new NoSuchElementException();
        }
        return tail.element;
    }
}

Test:
@RunWith(JDaveRunner.class)
public class CircularLinkedListSpec extends
        Specification<CircularLinkedList<String>> {

    public class EmptyCLL {
        private CircularLinkedList<String> cll;

        public CircularLinkedList<String> create() {
            return this.cll = new CircularLinkedList<String>();
        }

        public void getHead() {
            specify(new Block() {
                public void run() throws Throwable {
                    cll.getHead();
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }

        public void getTail() {
            specify(new Block() {
                public void run() throws Throwable {
                    cll.getTail();
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }

        public void size() {
            specify(cll.size(), must.equal(0));
        }

        public void next() {
            specify(new Block() {
                public void run() throws Throwable {
                    cll.next();
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }

        public void remove() {
            specify(new Block() {
                public void run() throws Throwable {
                    cll.remove("gavin");
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }

        public void add() {
            this.cll.add("gavin");
            specify(cll.size(), 1);
            specify(cll.getHead(), "gavin");
            specify(cll.getTail(), "gavin");
        }
    }

    public class OnlyHeadCLL {
        private CircularLinkedList<String> cll;

        public CircularLinkedList<String> create() {
            List<String> list = new ArrayList<String>();
            list.add("gavin");
            return this.cll = new CircularLinkedList<String>(list);
        }

        public void getHead() {
            specify(cll.getHead(), must.equal("gavin"));
        }

        public void getTail() {
            specify(cll.getHead(), must.equal("gavin"));
        }

        public void size() {
            specify(cll.size(), must.equal(1));
        }

        public void next() {
            String current = cll.next();
            specify(current, must.equal("gavin"));
        }

        public void remove() {
            String removed = cll.remove("gavin");
            specify(removed, "gavin");
            specify(cll.size(), must.equal(0));
            specify(new Block() {
                public void run() throws Throwable {
                    cll.getHead();
                }
            }, must.raiseExactly(NoSuchElementException.class));
            specify(new Block() {
                public void run() throws Throwable {
                    cll.getTail();
                }
            }, must.raiseExactly(NoSuchElementException.class));
            specify(new Block() {
                public void run() throws Throwable {
                    cll.next();
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }

        public void removeTwice() {
            String removed = cll.remove("gavin");
            specify(removed, "gavin");
            specify(cll.size(), must.equal(0));
            specify(new Block() {
                public void run() throws Throwable {
                    cll.remove("gavin");
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }

        public void add() {
            this.cll.add("afka");
            specify(cll.size(), must.equal(2));
            specify(cll.getHead(), "gavin");
            specify(cll.getTail(), "afka");
        }

    }

    public class NormalCLL {
        private CircularLinkedList<String> cll;

        public CircularLinkedList<String> create() {
            List<String> list = new ArrayList<String>();
            list.add("gavin");
            list.add("afka");
            list.add("eddie");
            return this.cll = new CircularLinkedList<String>(list);
        }
        public void add() {
            specify(cll.size(), 3);
            specify(this.cll.getHead(), "gavin");
            specify(this.cll.getTail(), "eddie");
            this.cll.add("rex");
            specify(cll.size(), 4);
            specify(this.cll.getHead(), "gavin");
            specify(this.cll.getTail(), "rex");
        }

        public void remove() {
            specify(cll.size(), 3);
            this.cll.remove("afka");
            specify(cll.size(), 2);
            specify(this.cll.getHead(), "gavin");
            specify(this.cll.getTail(), "eddie");
        }

        public void removeHead() {
            specify(cll.size(), 3);
            this.cll.remove("gavin");
            specify(cll.size(), 2);
            specify(this.cll.getHead(), "afka");
        }

        public void removeTail() {
            specify(cll.size(), 3);
            this.cll.remove("eddie");
            specify(cll.size(), 2);
            specify(this.cll.getTail(), "afka");
        }

        public void removeNotExist() {
            specify(new Block() {
                public void run() throws Throwable {
                    cll.remove("rex");
                }
            }, must.raiseExactly(NoSuchElementException.class));
        }
    }

    public class Iteration {
        private CircularLinkedList<String> cll;

        public CircularLinkedList<String> create() {
            List<String> list = new ArrayList<String>();
            list.add("gavin");
            list.add("afka");
            list.add("eddie");
            return this.cll = new CircularLinkedList<String>(list);
        }
        
        public void next() {
            String step1 = this.cll.next();
            specify(3, cll.size());
            specify(step1, "gavin");
            specify(cll.getHead(), "gavin");
            specify(cll.getTail(), "eddie");
        }
        
        public void addWhenNext() {
            String step1 = this.cll.next();
            specify(step1, "gavin");
            String step2 = this.cll.next();
            specify(step2, "afka");
            this.cll.add("rex");
            String step3 = this.cll.next();
            specify(step3, "eddie");
            specify(cll.getTail(), "rex");
            String step4 = this.cll.next();
            specify(step4, "rex");
            specify(cll.getTail(), "rex");
            specify(cll.getHead(), "gavin");
        }
        
        public void removeSubWhenNext() {
            String step1 = this.cll.next();
            specify(step1, "gavin");
            this.cll.remove("eddie");
            specify(this.cll.next(), "afka");
            specify(this.cll.next(), "gavin");
        }
        
        public void removePreWhenNext() {
            specify(this.cll.next(), "gavin");
            specify(this.cll.next(), "afka");
            this.cll.remove("gavin");
            specify(this.cll.next(), "eddie");
            specify(this.cll.next(), "afka");
        }
        
        public void nextIsJustRemoved() {
            String step1 = this.cll.next();
            specify(step1, "gavin");
            this.cll.remove("afka");
            String step2 = this.cll.next();
            specify(step2, "eddie");
        }
        
        public void nextIsJustAdded() {
            String step1 = this.cll.next();
            specify(step1, "gavin");
            String step2 = this.cll.next();
            specify(step2, "afka");
            String step3 = this.cll.next();
            specify(step3, "eddie");
            specify(cll.getTail(), "eddie");
            this.cll.add("rex");
            String step4 = this.cll.next();
            specify(step4, "rex");
            specify(cll.getTail(), "rex");
            specify(cll.getHead(), "gavin");
        }
        
        public void iterationCycle() {
            specify(3, cll.size());
            specify(this.cll.next(), "gavin");
            specify(this.cll.next(), "afka");
            specify(this.cll.next(), "eddie");
            specify(this.cll.next(), "gavin");
            specify(cll.getHead(), "gavin");
            specify(cll.getTail(), "eddie");
        }
    }
}


posted on 2009-04-01 12:42 叱咤红人 阅读(527) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。
网站导航: