走自己的路

路漫漫其修远兮,吾将上下而求索

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 4 文章 :: 118 评论 :: 0 Trackbacks
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 叱咤红人 阅读(433) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: