Skip to content

Commit 54de242

Browse files
author
Rong Huang
authored
Merge pull request onlyliuxin#24 from congcongcong250/master
60990377_liren: Final version with Test Cases
2 parents 83d2c9d + b9b061c commit 54de242

File tree

12 files changed

+607
-37
lines changed

12 files changed

+607
-37
lines changed

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/ArrayList.java

Lines changed: 19 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -22,46 +22,34 @@ public void add(Object o){
2222
}
2323

2424
public void add(int index, Object o){
25-
//Check Object class
26-
if(size >= 1){
27-
if(o.getClass() != elementData[0].getClass())
28-
throw new InputMismatchException("Index:"+index+" Size:"+size);
29-
}
30-
3125
//index Check
32-
if(index >= size || index < 0){
33-
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
34-
}
26+
checkIndex(index);
3527

3628
//check size limit
3729
if(size + 1 > elementData.length){
38-
Object oldData[] = elementData;
3930
int newlength = elementData.length * 3 / 2 + 1;
4031
elementData = Arrays.copyOf(elementData, newlength);
4132
}
4233

43-
for(int i = size-1; i >= index; i-- ){
34+
for(int i = ++size; i >= index; i-- ){
4435
elementData[i] = elementData[i-1];
4536
}
4637

4738
elementData[index] = o;
4839

40+
4941
}
5042

5143
public Object get(int index){
5244
//index Check
53-
if(index >= size || index < 0){
54-
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
55-
}
45+
checkIndex(index);
5646

5747
return elementData[index];
5848
}
5949

6050
public Object remove(int index){
6151
//index Check
62-
if(index >= size || index < 0){
63-
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
64-
}
52+
checkIndex(index);
6553

6654
Object old = elementData[index];
6755
for(int i = index; i < size-1 ; i++ ){
@@ -79,6 +67,18 @@ public Iterator iterator(){
7967
return new Itr();
8068
}
8169

70+
public void clear(){
71+
elementData = new Object[10];
72+
size = 0;
73+
}
74+
75+
private void checkIndex(int index){
76+
if(index >= size || index < 0){
77+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
78+
}
79+
}
80+
81+
8282
private class Itr implements Iterator{
8383
//index for next element to visit
8484
private int cursor = 0;
@@ -106,8 +106,8 @@ public void remove() {
106106
ArrayList.this.remove(--cursor);
107107

108108
}
109-
110-
111109
}
112110

111+
112+
113113
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/BinaryTreeNode.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,12 @@ public void setRight(BinaryTreeNode right) {
3737
this.right = right;
3838
}
3939

40+
public void destroy(){
41+
this.data = null;
42+
this.left = null;
43+
this.right = null;
44+
}
45+
4046
public BinaryTreeNode insert(Object o){
4147
//If is empty root
4248
if(data == null){

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/LinkedList.java

Lines changed: 37 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,7 @@ public class LinkedList implements List {
88
private int size;
99

1010
public LinkedList(){
11-
head.next = head;
12-
head.previous = head;
11+
head = new Node();
1312
size = 0;
1413
}
1514

@@ -19,9 +18,7 @@ public void add(Object o){
1918

2019
public void add(int index , Object o){
2120
//Check bound
22-
if(index >= size){
23-
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
24-
}
21+
checkIndex(index);
2522

2623
Node nx = this.find(index);
2724
Node pr = nx.previous;
@@ -33,17 +30,14 @@ public void add(int index , Object o){
3330

3431
public Object get(int index){
3532
//Check bound
36-
if(index >= size){
37-
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
38-
}
39-
return this.find(index);
33+
checkIndex(index);
34+
35+
return this.find(index).data;
4036
}
4137

4238
public Object remove(int index){
4339
//Check bound
44-
if(index >= size){
45-
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
46-
}
40+
checkIndex(index);
4741
Node rem = this.find(index);
4842

4943
Node pr = rem.previous;
@@ -88,6 +82,21 @@ public Object removeLast(){
8882
public Iterator iterator(){
8983
return new ListItr();
9084
}
85+
public void clear(){
86+
for (Node x = head; x != null; ) {
87+
Node next = x.next;
88+
x.data = null;
89+
x.next = null;
90+
x.previous = null;
91+
x = next;
92+
}
93+
}
94+
95+
private void checkIndex(int index){
96+
if(index >= size || index < 0){
97+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
98+
}
99+
}
91100

92101
private Node find(int index){
93102
Node tra = head;
@@ -98,7 +107,7 @@ private Node find(int index){
98107
tra = tra.next;
99108
}
100109
}else{
101-
for(int i = size; i >= index; i--){
110+
for(int i = size; i > index; i--){
102111
tra = tra.previous;
103112
}
104113
}
@@ -110,6 +119,12 @@ private static class Node{
110119
Node next;
111120
Node previous;
112121

122+
public Node(){
123+
data = null;
124+
next = this;
125+
previous = this;
126+
}
127+
113128
public Node(Object obj,Node pre, Node nx){
114129
data = obj;
115130
next = nx;
@@ -136,28 +151,32 @@ public boolean hasNext() {
136151

137152
@Override
138153
public Object next() {
154+
checkBound();
139155
Node re = cursor;
140156
cursor = cursor.next;
141157
nextIndex++;
142-
return re;
158+
return re.data;
143159
}
144160

145161
public Object previous() {
146162
Node re = cursor.previous.previous;
147163
cursor = cursor.previous;
148164
nextIndex--;
149-
return re;
165+
return re.data;
150166
}
151167

152168
@Override
153169
public void remove() {
154170
//Check bound
155-
if(nextIndex > size){
156-
throw new NoSuchElementException("Iterates to the end");
157-
}
171+
checkBound();
158172
LinkedList.this.remove(--nextIndex);
159173

160174
}
161175

176+
private void checkBound(){
177+
if(nextIndex >= size){
178+
throw new NoSuchElementException("Iterates to the end");
179+
}
180+
}
162181
}
163182
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/Queue.java

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,4 +27,8 @@ public boolean isEmpty(){
2727
public int size(){
2828
return elementData.size();
2929
}
30+
31+
public void clear(){
32+
elementData.clear();
33+
}
3034
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/Stack.java

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,4 +25,8 @@ public boolean isEmpty(){
2525
public int size(){
2626
return elementData.size();
2727
}
28+
29+
public void clear(){
30+
elementData.clear();
31+
}
2832
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basicTest/ArrayListTest.java

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
package com.github.congcongcong250.coding2017.basicTest;
2+
3+
import static org.junit.Assert.*;
4+
5+
import java.util.NoSuchElementException;
6+
7+
import org.junit.After;
8+
import org.junit.Before;
9+
import org.junit.Test;
10+
11+
import com.github.congcongcong250.coding2017.basic.ArrayList;
12+
import com.github.congcongcong250.coding2017.basic.Iterator;
13+
14+
public class ArrayListTest implements testCase {
15+
16+
ArrayList testlist = new ArrayList();
17+
18+
@Override
19+
@Before
20+
public void setUp() {
21+
22+
for(int i = 0; i < 30; i++){
23+
testlist.add(i);
24+
}
25+
}
26+
27+
@Override
28+
@After
29+
public void tearDown() {
30+
testlist.clear();
31+
}
32+
33+
@Override
34+
@Test
35+
public void testAdd() {
36+
37+
assertEquals(0,testlist.get(0));
38+
assertEquals(11,testlist.get(11));
39+
assertEquals(20,testlist.get(20));
40+
assertEquals(29,testlist.get(29));
41+
assertEquals(30,testlist.size());
42+
43+
testlist.add(20, 100);
44+
assertEquals(100,testlist.get(20));
45+
assertEquals(20,testlist.get(21));
46+
assertEquals(29,testlist.get(30));
47+
assertEquals(31,testlist.size());
48+
49+
}
50+
51+
@Override
52+
@Test
53+
public void testRemove() {
54+
55+
56+
assertEquals(6,testlist.get(6));
57+
assertEquals(30,testlist.size());
58+
testlist.remove(6);
59+
assertEquals(7,testlist.get(6));
60+
assertEquals(29,testlist.size());
61+
assertEquals(21,testlist.get(20));
62+
assertEquals(5,testlist.get(5));
63+
}
64+
65+
66+
@Test(expected=IndexOutOfBoundsException.class)
67+
public void testgetneg(){
68+
69+
ArrayList emptyList = new ArrayList();
70+
Object o = emptyList.get(-1);
71+
}
72+
73+
@Test(expected=IndexOutOfBoundsException.class)
74+
public void testgetout(){
75+
76+
Object o = testlist.get(31);
77+
}
78+
79+
@Test(expected=IndexOutOfBoundsException.class)
80+
public void testremoveExp(){
81+
Object o = testlist.remove(31);
82+
}
83+
84+
@Override
85+
@Test
86+
public void testFunctional() {
87+
Iterator itr = testlist.iterator();
88+
assertTrue(itr.hasNext());
89+
for(int i = 0; i < 20; i++){
90+
assertEquals(i, itr.next());
91+
}
92+
itr.remove();
93+
94+
assertTrue(itr.hasNext());
95+
assertEquals(20, itr.next());
96+
assertEquals(29, testlist.size());
97+
98+
for(int i = 21; i < 30; i++){
99+
assertEquals(i, itr.next());
100+
}
101+
assertFalse(itr.hasNext());
102+
103+
boolean hasExp = false;
104+
try{
105+
itr.next();
106+
}catch (NoSuchElementException e){
107+
hasExp = true;
108+
}
109+
assertTrue(hasExp);
110+
}
111+
112+
113+
114+
115+
}

0 commit comments

Comments
 (0)