Skip to content

Commit 3eb1db4

Browse files
gqipangqipan
authored
Merge pull request onlyliuxin#2 from fenq/master
merge 395443277 assignment
2 parents ff0ad0e + beaf0d3 commit 3eb1db4

File tree

13 files changed

+809
-0
lines changed

13 files changed

+809
-0
lines changed

‎group11/395443277/data_structure/.gitignore

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
2+
3+
.metadata
4+
5+
bin/
6+
7+
tmp/
8+
9+
*.tmp
10+
11+
*.bak
12+
13+
*.swp
14+
15+
*~.nib
16+
17+
local.properties
18+
19+
.settings/
20+
21+
.loadpath
22+
23+
.recommenders
24+
25+
26+
27+
# Eclipse Core
28+
29+
.project
30+
31+
32+
33+
# External tool builders
34+
35+
.externalToolBuilders/
36+
37+
38+
39+
# Locally stored "Eclipse launch configurations"
40+
41+
*.launch
42+
43+
44+
45+
# PyDev specific (Python IDE for Eclipse)
46+
47+
*.pydevproject
48+
49+
50+
51+
# CDT-specific (C/C++ Development Tooling)
52+
53+
.cproject
54+
55+
56+
57+
# JDT-specific (Eclipse Java Development Tools)
58+
59+
.classpath
60+
61+
62+
63+
# Java annotation processor (APT)
64+
65+
.factorypath
66+
67+
68+
69+
# PDT-specific (PHP Development Tools)
70+
71+
.buildpath
72+
73+
74+
75+
# sbteclipse plugin
76+
77+
.target
78+
79+
80+
81+
# Tern plugin
82+
83+
.tern-project
84+
85+
86+
87+
# TeXlipse plugin
88+
89+
.texlipse
90+
91+
92+
93+
# STS (Spring Tool Suite)
94+
95+
.springBeans
96+
97+
98+
99+
# Code Recommenders
100+
101+
.recommenders/
102+
103+
104+
105+
# Scala IDE specific (Scala & Java development for Eclipse)
106+
107+
.cache-main
108+
109+
.scala_dependencies
110+
111+
.worksheet

‎group11/395443277/data_structure/src/com/coding/basic/ArrayList.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
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[4];
10+
11+
public void add(Object o){
12+
if (size == elementData.length) {
13+
// double size
14+
doubleSize();
15+
}
16+
17+
elementData[size] = o;
18+
size++;
19+
}
20+
21+
private void doubleSize() {
22+
elementData = Arrays.copyOf(elementData, elementData.length * 2);
23+
}
24+
25+
public void add(int index, Object o){
26+
// check size
27+
if (size == elementData.length) {
28+
doubleSize();
29+
}
30+
31+
//shift and add element
32+
System.arraycopy(elementData, index, elementData, index+1, size - index);
33+
elementData[index] = o;
34+
size++;
35+
}
36+
37+
public Object get(int index){
38+
return elementData[index];
39+
}
40+
41+
public Object remove(int index){
42+
if (size == 0) {
43+
return null;
44+
}
45+
46+
// remove element and shift
47+
Object target = elementData[index];
48+
System.arraycopy(elementData, index+1, elementData, index, size - index - 1);
49+
50+
// reset last element
51+
elementData[size-1] = null;
52+
size--;
53+
return target;
54+
}
55+
56+
public int size(){
57+
return size;
58+
}
59+
60+
public Iterator iterator (){
61+
return new SeqIterator();
62+
}
63+
64+
private class SeqIterator implements Iterator {
65+
int i = 0;
66+
67+
@Override
68+
public boolean hasNext() {
69+
return i < size;
70+
}
71+
72+
@Override
73+
public Object next() {
74+
if (!hasNext()) {
75+
return null;
76+
}
77+
return elementData[i++];
78+
}
79+
80+
}
81+
82+
}

‎group11/395443277/data_structure/src/com/coding/basic/ArrayListTest.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.coding.basic;
2+
3+
import static org.junit.Assert.*;
4+
5+
import org.junit.Test;
6+
7+
public class ArrayListTest {
8+
9+
@Test
10+
public void testAddObject() {
11+
ArrayList list = new ArrayList();
12+
list.add(5);
13+
assertEquals(5, list.get(0));
14+
15+
list.add(4);
16+
list.add(3);
17+
list.add(2);
18+
list.add(1);
19+
assertEquals(1, list.get(4));
20+
21+
// size equals to 5
22+
assertEquals(5, list.size());
23+
}
24+
25+
@Test
26+
public void testAddIntObject() {
27+
ArrayList list = new ArrayList();
28+
list.add(5);
29+
list.add(4);
30+
list.add(3);
31+
list.add(2);
32+
list.add(1);
33+
34+
// change position 2 element
35+
list.add(2, 10);
36+
37+
// pos 2 has 10
38+
assertEquals(10, list.get(2));
39+
40+
// last element is 1
41+
assertEquals(1, list.get(5));
42+
43+
// size is 6
44+
assertEquals(6, list.size());
45+
}
46+
47+
@Test
48+
public void testRemove() {
49+
ArrayList list = new ArrayList();
50+
list.add(5);
51+
list.add(4);
52+
list.add(3);
53+
list.add(2);
54+
list.add(1);
55+
56+
Object removed = list.remove(2);
57+
assertEquals(removed, 3);
58+
59+
assertEquals(2, list.get(2));
60+
assertEquals(4, list.size());
61+
assertEquals(null, list.get(4));
62+
63+
list.add(6);
64+
assertEquals(6, list.get(4));
65+
}
66+
67+
@Test
68+
public void testIterator() {
69+
ArrayList list = new ArrayList();
70+
list.add(5);
71+
list.add(4);
72+
list.add(3);
73+
list.add(2);
74+
list.add(1);
75+
76+
Iterator it = list.iterator();
77+
if(it.hasNext()) {
78+
assertEquals(5, it.next());
79+
assertEquals(4, it.next());
80+
}
81+
82+
}
83+
84+
}

‎group11/395443277/data_structure/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode implements Comparable<Object>{
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+
if (this.compareTo(o)==0) {
30+
return null;
31+
} else {
32+
// current value less than inserted value
33+
// go right
34+
if (this.compareTo(o)<0) {
35+
if (this.right == null) {
36+
BinaryTreeNode nd = new BinaryTreeNode();
37+
nd.setData(o);
38+
this.setRight(nd);
39+
} else {
40+
this.getRight().insert(o);
41+
}
42+
}
43+
// greater than
44+
// go left
45+
else if(this.compareTo(o)>0) {
46+
if (this.left == null) {
47+
BinaryTreeNode nd = new BinaryTreeNode();
48+
nd.setData(o);
49+
this.setLeft(nd);
50+
} else {
51+
this.getLeft().insert(o);
52+
}
53+
}
54+
}
55+
56+
return null;
57+
}
58+
59+
/**
60+
* oversimplified implementation: only allows int and string
61+
*/
62+
@Override
63+
public int compareTo(Object nd) throws ClassCastException{
64+
if (!(nd instanceof Object)) {
65+
throw new ClassCastException("An object expected.");
66+
}
67+
68+
if (nd instanceof String) {
69+
return ((String)this.data).compareTo((String) nd);
70+
} else {
71+
return ((int) this.data) -((int) nd);
72+
}
73+
}
74+
75+
}

‎group11/395443277/data_structure/src/com/coding/basic/BinaryTreeNodeTest.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.coding.basic;
2+
3+
import static org.junit.Assert.*;
4+
5+
import org.junit.Test;
6+
7+
public class BinaryTreeNodeTest {
8+
9+
@Test
10+
public void testInsert() {
11+
BinaryTreeNode root = new BinaryTreeNode();
12+
root.setData(3);
13+
14+
root.insert(2);
15+
BinaryTreeNode left = root.getLeft();
16+
assertEquals(2,left.getData());
17+
18+
root.insert(5);
19+
BinaryTreeNode right = root.getRight();
20+
assertEquals(5, right.getData());
21+
22+
root.insert(7);
23+
BinaryTreeNode rr = right.getRight();
24+
assertEquals(7, rr.getData());
25+
}
26+
27+
@Test
28+
public void testCompareTo() {
29+
BinaryTreeNode n1 = new BinaryTreeNode();
30+
n1.setData("abc");
31+
32+
assertEquals(true, n1.compareTo("cde")<0);
33+
34+
BinaryTreeNode n3 = new BinaryTreeNode();
35+
n3.setData(1);
36+
37+
assertEquals(true, n3.compareTo(2)<0);
38+
}
39+
40+
}

0 commit comments

Comments
 (0)