Skip to content

Commit dbd3902

Browse files
earlywusaearlywusa
committed
array list implementation and ut
1 parent 4dd5aae commit dbd3902

File tree

9 files changed

+334
-0
lines changed

9 files changed

+334
-0
lines changed

‎group17/1282579502/src/com/coding/basic/ArrayList.java

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
private Object[] elementData = new Object[8];
10+
11+
public int test = 10;
12+
13+
public void add(Object o){
14+
if(size + 1 >elementData.length){
15+
expand();
16+
}
17+
elementData[size] = o;
18+
size++;
19+
}
20+
/**
21+
* Parameters:
22+
* index index at which the specified element is to be inserted
23+
* element element to be inserted
24+
* Throws:
25+
* IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())
26+
*/
27+
28+
public void add(int index, Object o){
29+
if(index <0 || index > size()) throw new IndexOutOfBoundsException(index + ": Invalid Index");
30+
if(size()+1>elementData.length){
31+
expand();
32+
}
33+
if(index < size())
34+
System.arraycopy(elementData, index, elementData, index+1, size() - index);
35+
elementData[index] = o;
36+
size ++;
37+
}
38+
39+
public Object get(int index){
40+
if(index <0 || index >= size()) throw new ArrayIndexOutOfBoundsException(index + ": Invalid Index.");
41+
return elementData[index];
42+
}
43+
44+
public Object remove(int index) {
45+
if(index <0 || index >= size()) throw new ArrayIndexOutOfBoundsException(index + ": Invalid Index.");
46+
Object item = elementData[index];
47+
if(index<size())
48+
System.arraycopy(elementData, index, elementData, index-1, size-index);
49+
return item;
50+
}
51+
52+
public int size(){
53+
return size;
54+
}
55+
56+
public Iterator iterator(){
57+
return new ArrayListIterImpl(this);
58+
}
59+
60+
private void expand(){
61+
Object[] newArray = new Object[elementData.length * 2];
62+
System.arraycopy(elementData, 0, newArray, 0, size);
63+
elementData = newArray;
64+
}
65+
66+
private class ArrayListIterImpl implements Iterator{
67+
68+
ArrayList al = null;
69+
public ArrayListIterImpl(ArrayList al){
70+
this.al = al;
71+
}
72+
73+
@Override
74+
public boolean hasNext() {
75+
// TODO Auto-generated method stub
76+
return false;
77+
}
78+
79+
@Override
80+
public Object next() {
81+
// TODO Auto-generated method stub
82+
return null;
83+
}
84+
85+
}
86+
}

‎group17/1282579502/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Object data) {
13+
this.data = data;
14+
}
15+
public BinaryTreeNode getLeft() {
16+
return left;
17+
}
18+
public void setLeft(BinaryTreeNode left) {
19+
this.left = left;
20+
}
21+
public BinaryTreeNode getRight() {
22+
return right;
23+
}
24+
public void setRight(BinaryTreeNode right) {
25+
this.right = right;
26+
}
27+
28+
public BinaryTreeNode insert(Object o){
29+
return null;
30+
}
31+
32+
}

‎group17/1282579502/src/com/coding/basic/Iterator.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package com.coding.basic;
2+
3+
public interface Iterator {
4+
public boolean hasNext();
5+
public Object next();
6+
7+
}

‎group17/1282579502/src/com/coding/basic/LinkedList.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.coding.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;
6+
7+
public void add(Object o){
8+
9+
}
10+
public void add(int index , Object o){
11+
12+
}
13+
public Object get(int index){
14+
return null;
15+
}
16+
public Object remove(int index){
17+
return null;
18+
}
19+
20+
public int size(){
21+
return -1;
22+
}
23+
24+
public void addFirst(Object o){
25+
26+
}
27+
public void addLast(Object o){
28+
29+
}
30+
public Object removeFirst(){
31+
return null;
32+
}
33+
public Object removeLast(){
34+
return null;
35+
}
36+
public Iterator iterator(){
37+
return null;
38+
}
39+
40+
41+
private static class Node{
42+
Object data;
43+
Node next;
44+
45+
}
46+
}

‎group17/1282579502/src/com/coding/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.basic;
2+
3+
public interface List {
4+
public void add(Object o);
5+
public void add(int index, Object o);
6+
public Object get(int index);
7+
public Object remove(int index);
8+
public int size();
9+
}

‎group17/1282579502/src/com/coding/basic/Queue.java

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package com.coding.basic;
2+
3+
public class Queue {
4+
5+
public void enQueue(Object o){
6+
}
7+
8+
public Object deQueue(){
9+
return null;
10+
}
11+
12+
public boolean isEmpty(){
13+
return false;
14+
}
15+
16+
public int size(){
17+
return -1;
18+
}
19+
}

‎group17/1282579502/src/com/coding/basic/Stack.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.coding.basic;
2+
3+
public class Stack {
4+
private ArrayList elementData = new ArrayList();
5+
6+
public void push(Object o){
7+
}
8+
9+
public Object pop(){
10+
return null;
11+
}
12+
13+
public Object peek(){
14+
return null;
15+
}
16+
public boolean isEmpty(){
17+
return false;
18+
}
19+
public int size(){
20+
return -1;
21+
}
22+
}

‎group17/1282579502/src/com/coding/basic/ut/ArrayListTest.java

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package com.coding.basic.ut;
2+
3+
import static org.junit.Assert.*;
4+
5+
import java.lang.reflect.Field;
6+
7+
import org.junit.After;
8+
import org.junit.Before;
9+
import org.junit.Test;
10+
11+
import com.coding.basic.ArrayList;
12+
13+
public class ArrayListTest {
14+
15+
ArrayList target;
16+
Object[] elementDataField;
17+
@Before
18+
public void setUp() throws Exception {
19+
target = new ArrayList();
20+
/*
21+
* NOTE: getField only returns PUBLIC fields, getDeclaredField get all fields
22+
Field[] allFields = target.getClass().getFields();
23+
System.out.println("Get all fields");
24+
for(Field tmpf : allFields){
25+
System.out.println(tmpf.getName());
26+
}
27+
Field[] allDeclFields = target.getClass().getDeclaredFields();
28+
System.out.println("Get all declared fields");
29+
for(Field tmpf : allDeclFields){
30+
System.out.println(tmpf.getName());
31+
}
32+
*
33+
*/
34+
try {
35+
Field f = target.getClass().getDeclaredField("elementData");
36+
37+
f.setAccessible(true);
38+
if(f.getType().isArray()){
39+
elementDataField = (Object[]) f.get(target);
40+
}
41+
} catch (NoSuchFieldException e) {
42+
fail(e.getMessage());
43+
} catch (SecurityException e) {
44+
fail(e.getMessage());
45+
} catch (IllegalArgumentException e) {
46+
fail(e.getMessage());
47+
} catch (IllegalAccessException e) {
48+
fail(e.getMessage());
49+
}
50+
}
51+
52+
@After
53+
public void tearDown() throws Exception {
54+
}
55+
56+
@Test
57+
public void testAddObject() {
58+
Object item = new String("s1");
59+
target.add(item);
60+
assertEquals(item, elementDataField[0]);
61+
}
62+
63+
@Test
64+
public void testAddIndexObject() {
65+
//fail("Not yet implemented");
66+
Object item0 = new String("s0");
67+
target.add(0, item0);
68+
69+
Object item1 = new String("s1");
70+
target.add(0, item1);
71+
72+
assertEquals(item1, elementDataField[0]);
73+
assertEquals(item0, elementDataField[1]);
74+
}
75+
76+
@Test
77+
public void testGet() {
78+
//fail("Not yet implemented");
79+
}
80+
81+
@Test
82+
public void testRemove() {
83+
//fail("Not yet implemented");
84+
}
85+
86+
@Test
87+
public void testSize() {
88+
for(int i = 0; i<10; i++){
89+
Object item = String.valueOf(i);
90+
target.add(item);
91+
}
92+
assertEquals(10, target.size());
93+
}
94+
95+
@Test
96+
public void testIterator() {
97+
//fail("Not yet implemented");
98+
}
99+
100+
}

‎group17/1282579502/src/com/wusa/assignment1/TestDriver.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,24 @@
11
package com.wusa.assignment1;
22

3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
36
public class TestDriver {
47

58
public static void main(String[] args) {
69
// TODO Auto-generated method stub
710
System.out.println("Hello World");
811
System.out.println("hello back");
12+
13+
String[] old = new String[5];
14+
old[0] = "100";
15+
old[1] = "101";
16+
System.arraycopy(old, 0, old, 1, 1);
17+
System.out.println(Arrays.toString(old));
18+
19+
ArrayList al = new ArrayList();
20+
21+
922
}
1023

1124
}

0 commit comments

Comments
 (0)