走自己的路

路漫漫其修遠(yuǎn)兮，吾將上下而求索

BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

50 隨筆 :: 4 文章 :: 118 評論 :: 0 Trackbacks

<

2009年4月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

留言簿(7)

隨筆分類(81)

隨筆檔案(54)

文章分類

搜索

閱讀排行榜

評論排行榜

java實現(xiàn)的同步循環(huán)鏈表

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 叱咤紅人閱讀(539) 評論(0) 編輯收藏

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理

走自己的路

留言簿(7)

隨筆分類(81)

隨筆檔案(54)

文章分類

搜索

最新評論

閱讀排行榜

評論排行榜