Skip to content

Commit 1595986

Browse files
guodongymguodongym
authored
Merge pull request onlyliuxin#9 from onlyLYJ/master
hope no surprise this time
2 parents 80f24b9 + 3ea180f commit 1595986

20 files changed

+1535
-0
lines changed

‎group12/382266293/.classpath

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
5+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
6+
<classpathentry kind="output" path="bin"/>
7+
</classpath>

‎group12/382266293/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group12/382266293/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>382266293Learning</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group12/382266293/src/Collection/AbstractList.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package Collection;
2+
3+
public abstract class AbstractList<E> implements List<E> {
4+
5+
protected static final String PREFIX = "[";
6+
protected static final String SUFFIX = "]";
7+
protected static final String SEPERATOR = ", ";
8+
protected static final int MAX_SIZE = Integer.MAX_VALUE/3;
9+
10+
protected void checkIndex(int i) {
11+
if( i < 0 || i > Math.min(size(), MAX_SIZE))
12+
throw new IndexOutOfBoundsException("Size :" + size()+", Index: " + i);
13+
}
14+
15+
public boolean isEmpty() {
16+
return size() == 0;
17+
}
18+
19+
20+
public int indexOf(E e) {
21+
for (int i = 0; i < size()-1; i++) {
22+
if (get(i).equals(e))
23+
return i;
24+
}
25+
return -1;
26+
}
27+
28+
protected abstract Iterator<E> iterator();
29+
30+
@Override
31+
public String toString() {
32+
StringBuilder sb = new StringBuilder();
33+
sb.append(PREFIX);
34+
for (int i = 0; i < size(); i++) {
35+
sb.append(get(i));
36+
if (i < size()-1)
37+
sb.append(SEPERATOR);
38+
}
39+
sb.append(SUFFIX);
40+
return sb.toString();
41+
}
42+
43+
}

‎group12/382266293/src/Collection/Concrete/ArrayList.java

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
package Collection.Concrete;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
import Collection.AbstractList;
7+
import Collection.Iterator;
8+
9+
public class ArrayList<E> extends AbstractList<E> {
10+
11+
private E[] elements;
12+
private int size;
13+
private static final int INITIAL_SIZE = 16;
14+
15+
16+
public ArrayList() {
17+
elements = (E[]) new Object[INITIAL_SIZE];
18+
size = 0;
19+
}
20+
21+
@Override
22+
public void add(E e) {
23+
checkCapacity();
24+
elements[size++] = e;
25+
}
26+
27+
private void checkCapacity() {
28+
if (size >= MAX_SIZE)
29+
throw new IndexOutOfBoundsException("Reached max size");
30+
31+
if (elements.length - size < INITIAL_SIZE)
32+
grow();
33+
}
34+
35+
synchronized private void grow() {
36+
37+
int newCapacity = size * 2;
38+
newCapacity = (newCapacity < 0 || newCapacity - MAX_SIZE > 0) ? MAX_SIZE : newCapacity;
39+
E[] target = (E[]) new Object[newCapacity];
40+
System.arraycopy(elements, 0, target, 0, size);
41+
elements = target;
42+
43+
}
44+
45+
public void add(int index, E e) {
46+
checkCapacity();
47+
if (index == size) {
48+
add(e);
49+
return;
50+
}
51+
checkIndex(index);
52+
synchronized (this) {
53+
System.arraycopy(elements, index, elements, index+1, size-index+1);
54+
elements[index] = e;
55+
size++;
56+
}
57+
}
58+
59+
@Override
60+
public E get(int index) {
61+
checkIndex(index);
62+
return elements[index];
63+
}
64+
65+
66+
public E getLast() {
67+
return get(size-1);
68+
}
69+
70+
public void addLast(E e) {
71+
add(e);
72+
}
73+
74+
public E removeLast() {
75+
return elements[--size];
76+
}
77+
78+
public E remove(int index) {
79+
checkIndex(index);
80+
E result = elements[index];
81+
synchronized (this) {
82+
System.arraycopy(elements, index+1, elements, index, size-index-1);
83+
elements[--size] = null;
84+
}
85+
return result;
86+
}
87+
88+
@Override
89+
public int size() {
90+
return size;
91+
}
92+
93+
94+
@Override
95+
public int hashCode() {
96+
final int prime = 31;
97+
int result = 1;
98+
result = prime * result + Arrays.hashCode(elements);
99+
result = prime * result + size;
100+
return result;
101+
}
102+
103+
@Override
104+
public boolean equals(Object obj) {
105+
if (this == obj)
106+
return true;
107+
if (obj == null)
108+
return false;
109+
if (getClass() != obj.getClass())
110+
return false;
111+
ArrayList other = (ArrayList) obj;
112+
if (!Arrays.equals(elements, other.elements))
113+
return false;
114+
if (size != other.size)
115+
return false;
116+
return true;
117+
}
118+
119+
public Iterator<E> iterator(){
120+
return new ArrayListIterator<E>(this);
121+
}
122+
123+
private class ArrayListIterator<E> implements Iterator<E> {
124+
125+
private ArrayList<E> myArrayList;
126+
private int pos;
127+
128+
public ArrayListIterator(ArrayList<E> arrayList) {
129+
myArrayList = arrayList;
130+
pos = 0;
131+
}
132+
133+
@Override
134+
public boolean hasNext() {
135+
return pos < size;
136+
}
137+
138+
@Override
139+
public E next() {
140+
if (hasNext())
141+
return (E) elements[pos++];
142+
throw new NoSuchElementException();
143+
}
144+
}
145+
146+
147+
148+
}

‎group12/382266293/src/Collection/Concrete/BinaryTreeNode.java

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
package Collection.Concrete;
2+
3+
public class BinaryTreeNode<E extends Comparable<E>> {
4+
5+
private E data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
private int size;
9+
private ArrayList<E> myList;
10+
11+
12+
13+
public BinaryTreeNode() {
14+
this.data = null;
15+
this.left = null;
16+
this.right = null;
17+
}
18+
19+
public BinaryTreeNode(E data) {
20+
this.data = data;
21+
this.left = null;
22+
this.right = null;
23+
}
24+
25+
public boolean isEmpty() {
26+
return data == null;
27+
}
28+
29+
public int size() {
30+
return size;
31+
}
32+
33+
public BinaryTreeNode<E> insert(E o) {
34+
BinaryTreeNode<E> res;
35+
if (isEmpty()) {
36+
data = o;
37+
size++;
38+
return this;
39+
} else {
40+
BinaryTreeNode<E> p = this;
41+
res = new BinaryTreeNode<E>(o);
42+
while (true) {
43+
if (res.getData().compareTo(p.getData()) < 0) {
44+
if (p.left == null) {
45+
p.setLeft(res);
46+
break;
47+
}
48+
p = p.left;
49+
} else if (res.getData().compareTo(p.getData()) > 0) {
50+
if (p.right == null) {
51+
p.setRight(res);
52+
break;
53+
}
54+
p = p.right;
55+
} else {
56+
return null;
57+
}
58+
}
59+
size++;
60+
}
61+
return res;
62+
}
63+
64+
65+
66+
public ArrayList<E> preOrderTraversal(BinaryTreeNode<E> node) {
67+
68+
if (node != null) {
69+
preOrderTraversal(node.left);
70+
myList.add(node.data);
71+
preOrderTraversal(node.right);
72+
}
73+
return myList;
74+
}
75+
76+
@Override
77+
public String toString() {
78+
myList = new ArrayList<E>();
79+
return preOrderTraversal(this).toString();
80+
}
81+
82+
public E getData() {
83+
return data;
84+
}
85+
public void setData(E data) {
86+
this.data = data;
87+
}
88+
public BinaryTreeNode getLeft() {
89+
return left;
90+
}
91+
public void setLeft(BinaryTreeNode left) {
92+
this.left = left;
93+
}
94+
public BinaryTreeNode getRight() {
95+
return right;
96+
}
97+
public void setRight(BinaryTreeNode right) {
98+
this.right = right;
99+
}
100+
101+
@Override
102+
public int hashCode() {
103+
final int prime = 31;
104+
int result = 1;
105+
result = prime * result + ((data == null) ? 0 : data.hashCode());
106+
return result;
107+
}
108+
109+
@Override
110+
public boolean equals(Object obj) {
111+
if (this == obj)
112+
return true;
113+
if (obj == null)
114+
return false;
115+
if (getClass() != obj.getClass())
116+
return false;
117+
BinaryTreeNode other = (BinaryTreeNode) obj;
118+
if (data == null) {
119+
if (other.data != null)
120+
return false;
121+
} else if (!data.equals(other.data))
122+
return false;
123+
return true;
124+
}
125+
126+
}

0 commit comments

Comments
 (0)