测试用例结果展示
覆盖率
变异得分
测试注意点
- 从SplayTree测起，然后再测SubSplayTree，因为前者调用后者。
- SplaySubTree的remove方法大部分内容需要通过反射才能测到。
- value和index在SplayTree当中都不是唯一的。一个index可能对应多个value。
不足之处
- 没考虑到异常怎么接住。
- 对SplayTree这个数据结构的理解还很浅显。
测试文件MyTest.java
package net.mooctest;
import static org.junit.Assert.*;
import java.lang.reflect.Field;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
public class MyTest {
private Integer valArr[];
private Integer remArr[];
private Integer conArr[];
private SplayTree<Integer> splayTree;
private int howmanynumbers;
private int removeCnt;
private int containsCnt;
@Before
public void initializeValArr() {
this.howmanynumbers = 100;
this.removeCnt = 0;
this.containsCnt = 0;
valArr = new Integer[howmanynumbers];
remArr = new Integer[howmanynumbers/7+1];
conArr = new Integer[howmanynumbers/9+1];
for(int i=0;i<this.howmanynumbers;i++) {
int val = (int)(Math.random()*100);
// System.out.println(val);
valArr[i] = val;
if(i%7==0) {
remArr[this.removeCnt++] = val;
}
if(i%9==0) {
conArr[this.containsCnt++] = val;
}
}
}
@Test
public void testMain() {
SplayTree.main(null);
}
// 测试remove和contains
@Test
public void test001() {
splayTree = new SplayTree<Integer>();
for(int i=0;i<this.howmanynumbers;i++) {
splayTree.add(valArr[i]);
assertNull(splayTree.root.join(splayTree.root));
}
assertNotNull(splayTree.root.add(null));
assertEquals(howmanynumbers, splayTree.size());
for(int i=0;i<this.removeCnt;i++) {
int valToRemove = remArr[i];
assertTrue(splayTree.contains(valToRemove));
splayTree.remove(valToRemove);
}
assertEquals(howmanynumbers-removeCnt, splayTree.size());
for(int i=0;i<this.containsCnt;i++) {
int valToVarify = conArr[i];
assertTrue(splayTree.contains(valToVarify));
}
}
// 测试remove和contains
@Test
public void test002() {
splayTree = new SplayTree<Integer>();
for(int i=0;i<this.howmanynumbers;i++) {
splayTree.add(valArr[i]);
assertNull(splayTree.root.split(splayTree.root.getData()));
}
assertEquals(howmanynumbers, splayTree.size());
for(int i=0;i<this.removeCnt;i++) {
int valToRemove = remArr[i];
assertTrue(splayTree.contains(valToRemove));
splayTree.remove(valToRemove);
}
assertEquals(howmanynumbers-removeCnt, splayTree.size());
for(int i=0;i<this.containsCnt;i++) {
int valToVarify = conArr[i];
assertTrue(splayTree.contains(valToVarify));
}
}
// 测试get和indexOf
// 不能再用随机生成的数据，因为随机数据很可能重复
@Test
public void test003() {
splayTree = new SplayTree<Integer>();
for(int i=0;i<this.howmanynumbers;i++) {
splayTree.add(i*17);
}
assertEquals(howmanynumbers, splayTree.size());
long idxArr[] = new long[howmanynumbers];
for(int i=0;i<splayTree.size();i++) {
idxArr[i] = splayTree.indexOf(i*17);
}
for(int i=0;i<splayTree.size();i++) {
assertEquals(i*17, (int)splayTree.get(idxArr[i]));
}
assertNull(splayTree.get(-1));
assertNull(splayTree.get(splayTree.size()+1));
}
//测试toString()
@Test
public void test004() {
int primeArr[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
};
splayTree = new SplayTree<Integer>();
for(int i=0;i<primeArr.length;i++) {
splayTree.add(primeArr[i]);
}
// System.out.println(splayTree.toString());
// String expectedStr = " data=2 left= null right null sz=1 cnt=1\n";
// assertEquals(expectedStr, splayTree.toString());
String expectedStr = " data=71 left=67 right null sz=20 cnt=1\n" +
" data=67 left=61 right null sz=19 cnt=1\n" +
" data=61 left=59 right null sz=18 cnt=1\n" +
" data=59 left=53 right null sz=17 cnt=1\n" +
" data=53 left=47 right null sz=16 cnt=1\n" +
" data=47 left=43 right null sz=15 cnt=1\n" +
" data=43 left=41 right null sz=14 cnt=1\n" +
" data=41 left=37 right null sz=13 cnt=1\n" +
" data=37 left=31 right null sz=12 cnt=1\n" +
" data=31 left=29 right null sz=11 cnt=1\n" +
" data=29 left=23 right null sz=10 cnt=1\n" +
" data=23 left=19 right null sz=9 cnt=1\n" +
" data=19 left=17 right null sz=8 cnt=1\n" +
" data=17 left=13 right null sz=7 cnt=1\n" +
" data=13 left=11 right null sz=6 cnt=1\n" +
" data=11 left=7 right null sz=5 cnt=1\n" +
" data=7 left=5 right null sz=4 cnt=1\n" +
" data=5 left=3 right null sz=3 cnt=1\n" +
" data=3 left=2 right null sz=2 cnt=1\n" +
" data=2 left= null right null sz=1 cnt=1\n";
assertEquals(expectedStr, splayTree.toString());
}
//测试SplaySubTree--find
@Test(timeout=4000)
public void test005() {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(null);
assertNull(splaySubTree.find(1));
int primeArr[] = {
2, 41, 5, 7, 67, 23, 11, 17, 19
};
for(int i=0;i<primeArr.length;i++) {
splaySubTree = splaySubTree.add(primeArr[i]);
}
// System.out.println(splaySubTree.toString());
assertNull(splaySubTree.find(20));
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test006() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(0);
int primeArr[] = {
2, 41, 5, 7, 23, 11, 67, 17, 19
};
System.out.println(primeArr.length);
for(int i=0;i<primeArr.length;i++) {
splaySubTree = splaySubTree.add(primeArr[i]);
}
assertNotNull(splaySubTree.remove(20));
assertEquals(primeArr.length+1,splaySubTree.remove(null).size());
// 获取 SplaySubTree<Integer> 的 Class 对象
Class<?> splaySubTreeClass = splaySubTree.getClass();
// 获取私有属性 count 的 Field 对象
Field countField = splaySubTreeClass.getDeclaredField("count");
// 设置私有属性 count 的可访问性
countField.setAccessible(true);
splaySubTree = splaySubTree.remove(7);
// 访问私有属性 count 的值
int countValue = (int) countField.get(splaySubTree);
// System.out.println("countValue: " + countValue);
assertEquals(0, countValue);
// System.out.println(splaySubTree.toString());
splaySubTree = splaySubTree.remove(7);
countValue = (int) countField.get(splaySubTree);
// System.out.println("countValue: " + countValue);
assertEquals(-1, countValue);
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test007() {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(1);
splaySubTree.remove(1);
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test008() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(1);
// 获取 SplaySubTree<Integer> 的 Class 对象
Class<?> splaySubTreeClass = splaySubTree.getClass();
// 获取私有属性 count 的 Field 对象
Field leftField = splaySubTreeClass.getDeclaredField("left");
// 设置私有属性 count 的可访问性
leftField.setAccessible(true);
SplaySubTree<Integer> splaySubTree2 = new SplaySubTree<Integer>(2);
leftField.set(splaySubTree,splaySubTree2);
splaySubTree.remove(1);
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test009() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(1);
// 获取 SplaySubTree<Integer> 的 Class 对象
Class<?> splaySubTreeClass = splaySubTree.getClass();
// 获取私有属性 count 的 Field 对象
Field rightField = splaySubTreeClass.getDeclaredField("right");
// 设置私有属性 count 的可访问性
rightField.setAccessible(true);
SplaySubTree<Integer> splaySubTree2 = new SplaySubTree<Integer>(2);
rightField.set(splaySubTree,splaySubTree2);
splaySubTree.remove(1);
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test0010() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(1);
// 获取 SplaySubTree<Integer> 的 Class 对象
Class<?> splaySubTreeClass = splaySubTree.getClass();
// 获取私有属性 count 的 Field 对象
Field leftField = splaySubTreeClass.getDeclaredField("left");
Field parentField = splaySubTreeClass.getDeclaredField("parent");
// 设置私有属性 count 的可访问性
leftField.setAccessible(true);
parentField.setAccessible(true);
SplaySubTree<Integer> splaySubTree2 = new SplaySubTree<Integer>(2);
leftField.set(splaySubTree,splaySubTree2);
SplaySubTree<Integer> splaySubTree3 = new SplaySubTree<Integer>(3);
parentField.set(splaySubTree,splaySubTree3);
splaySubTree.remove(1);
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test0011() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(1);
// 获取 SplaySubTree<Integer> 的 Class 对象
Class<?> splaySubTreeClass = splaySubTree.getClass();
// 获取私有属性 count 的 Field 对象
Field rightField = splaySubTreeClass.getDeclaredField("right");
Field parentField = splaySubTreeClass.getDeclaredField("parent");
// 设置私有属性 count 的可访问性
rightField.setAccessible(true);
parentField.setAccessible(true);
SplaySubTree<Integer> splaySubTree2 = new SplaySubTree<Integer>(2);
rightField.set(splaySubTree,splaySubTree2);
SplaySubTree<Integer> splaySubTree3 = new SplaySubTree<Integer>(3);
parentField.set(splaySubTree,splaySubTree3);
splaySubTree.remove(1);
}
//测试SplaySubTree--remove
@Test(timeout=4000)
public void test0012() throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException, NullPointerException {
SplaySubTree<Integer> splaySubTree = new SplaySubTree<Integer>(1);
// 获取 SplaySubTree<Integer> 的 Class 对象
Class<?> splaySubTreeClass = splaySubTree.getClass();
// 获取私有属性 count 的 Field 对象
Field rightField = splaySubTreeClass.getDeclaredField("right");
Field leftField = splaySubTreeClass.getDeclaredField("left");
// 设置私有属性 count 的可访问性
rightField.setAccessible(true);
leftField.setAccessible(true);
SplaySubTree<Integer> splaySubTree2 = new SplaySubTree<Integer>(2);
rightField.set(splaySubTree,splaySubTree2);
SplaySubTree<Integer> splaySubTree3 = new SplaySubTree<Integer>(3);
leftField.set(splaySubTree,splaySubTree3);
String expectedStr = " data=1 left=3 right=2 sz=1 cnt=1\n" +
" data=3 left= null right null sz=1 cnt=1\n" +
" data=2 left= null right null sz=1 cnt=1\n";
assertEquals(expectedStr, splaySubTree.toString());
}
}
被测文件(1/2)SplayTree.java
package net.mooctest;
import java.util.Arrays;
public class SplayTree <T extends Comparable<T>> {
SplaySubTree<T> root;
public SplayTree(){
root = new SplaySubTree<T>(null);
}
/**
* @param index - of the node to search for.
* @return - null if index<=0 or index>=size otherwise SubTree at index.
*/
public T get(long index) {
SplaySubTree<T> cT = root.get(index);
if(cT==null)return null;
cT.splay();
root = cT;
return cT.getData();
}
/**
* @return - the number of nodes in the tree.
*/
public long size() { return root.size();}
/**
* @param node - to search for.
* @return - the index of node. All nodes are ordered according to the compareTo(T) method.
*
*/
public long indexOf(T node) {
long index = root.indexOf(node);
get(index);
return index;
}
/**
* @param node - is added to the tree.
* If node is null tree is unchanged.
*/
public void add(T node) {
root = root.add(node);
}
/**
* @param node - is removed from the tree.
* If node is null tree is unchanged.
*/
public void remove(T node) {
root = root.remove(node);
}
/**
* @param node
* @return
*/
public boolean contains(T node) {
SplaySubTree<T> temp = root.find(node);
if(temp!=null){
temp.splay();
root = temp;
}
return temp != null;
}
@Override
public String toString(){
return root.toString();
}
public static void main(String[] args) {
SplayTree<Integer> test = new SplayTree<Integer>();
int howmanynumbers = 10000;
for (int i = 0; i < howmanynumbers; i++) {
int val = (int)(Math.random()*100);
test.add(val);
}
System.out.println(test);
}
}
被测文件(2/2)SubSplayTree.java
package net.mooctest;
public class SplaySubTree<T extends Comparable<T>> {
private T data;
private SplaySubTree<T> left, right, parent;
private long size; // number of nodes in tree
private int count;
/**
* @param node
* - If node==null then size will be 0 otherwise node will be in the
* tree and size will be 1
*/
public SplaySubTree(T node) {
data = node;
if (node != null) {
size = count = 1;
}
}
public String toString() {
String lft = "";
String rght = "";
String myData = " data=" + data;
if (left != null) {
myData += " left=" + left.data;
lft = left.toString();
} else {
myData += " left= null";
}
if (right != null) {
myData += " right=" + right.data;
rght = right.toString();
} else {
myData += " right null";
}
myData += " sz="+size + " cnt="+count;
return myData + "\n" + lft + rght;
}
public T getData() {
return data;
}
/**
* @param index
* - of the node to search for.
* @return - null if index<=0 or index>=size otherwise SubTree at index.
*/
public SplaySubTree<T> get(long index) {
if (index > size || index < 0)
return null;
long cS = 1;
SplaySubTree<T> cT = this;
if (cT.left != null)
cS += cT.left.size;
while (cS != index) {
if (cS > index) {
cS--;
cT = cT.left;
if (cT != null && cT.right != null)
cS -= cT.right.size;
} else {
cS++;
cT = cT.right;
if (cT != null && cT.left != null)
cS += cT.left.size;
}
}
return cT;
}
/**
* @return - the number of nodes in the tree.
*/
public long size() {
return size;
}
/**
* @param node
* - to search for.
* @return - the index of node. All nodes are ordered according to the
* compareTo(T) method.
*
*/
public long indexOf(T node) {
if (node == null)
return -1;
long cI = 1;
SplaySubTree<T> cT = this;
if (cT.left != null)
cI += cT.left.size;
while (!cT.data.equals(node)) {
if (cT.data.compareTo(node) > 0) {
cI--;
cT = cT.left;
if (cT != null && cT.right != null)
cI -= cT.right.size;
} else {
cI++;
cT = cT.right;
if (cT != null && cT.left != null)
cI += cT.left.size;
}
if (cT == null)
return -1;
}
return cI;
}
/**
* @param node
* - is added to the tree. If node is null tree is unchanged.
* @return - New root of the tree.
*/
public SplaySubTree<T> add(T node) {
if (node == null)
return this;
if (this.data == null)
return new SplaySubTree<T>(node);
SplaySubTree<T> current = this;
SplaySubTree<T> child = null;
if (this.data.compareTo(node) < 0)
child = this.right;
else if(this.data.compareTo(node)>0)
child = this.left;
while (child != null && current.data.compareTo(node)!=0) {
current = child;
if (current.data.compareTo(node) < 0)
child = current.right;
else if(current.data.compareTo(node)>0)
child = current.left;
}
SplaySubTree<T> newNode = new SplaySubTree<T>(node);
if (current.data.compareTo(node) < 0) {
current.right = newNode;
} else if(current.data.compareTo(node)>0){
current.left = newNode;
}else {
current.size++;
current.count++;
newNode = current;
current = newNode.parent;
}
newNode.parent = current;
if (newNode.splay())
return newNode;
return this;
}
/**
* @param node
* - is removed from the tree. If node is null tree is unchanged.
* @return - New root of the tree.
*/
public SplaySubTree<T> remove(T node) {
if (node == null)
return this;
SplaySubTree<T> x = find(node);
if (x == null)
return this;
if(x.data.equals(node)) {
x.count--;
x.size--;
if(size>0) {
x.splay();
return x;
}
}
// To delete a node x:
// if x has no children remove it.
if (x.left == null && x.right == null) {
if (x.parent != null) {
if (x.parent.left == x) {
parent.left = null;
} else
parent.right = null;
} else
return new SplaySubTree(null);
}
// if x has one child remove x, and put the child in place of x
if (x.left == null) {
if (x.parent != null) {
if (x.parent.left == x) {
parent.left = x.right;
x.right.parent = parent;
x = x.right;
} else {
parent.right = x.right;
x.right.parent = parent;
x = x.right;
}
} else {
x.right.parent = null;
return x.right;
}
} else if (x.right == null) {
if (x.parent != null) {
if (x.parent.left == x) {
parent.left = x.left;
x.left.parent = parent;
x = x.left;
} else {
parent.right = x.left;
x.left.parent = parent;
x = x.left;
}
} else {
x.left.parent = null;
return x.left;
}
} else {
// if x has two children, swap its value with that of
// the rightmost node of its left sub tree
SplaySubTree<T> rmc = x.left;
while (rmc.right != null)
rmc = rmc.right;
x.data = rmc.data;
// Then remove that node instead.
rmc.left.parent = rmc.parent;
if (rmc.parent == x) {
x.left = rmc.left;
} else {
rmc.parent.right = rmc.left;
}
x = rmc;
}
// After deletion, splay the parent of the removed node to the top of
// the tree.
x.splay();
return x;
}
/**
* @param other
* @return
*/
public SplaySubTree<T> join(SplaySubTree<T> other) {
return null;
}
/**
* @param node
* @return
*/
public SplaySubTree<T> split(T node) {
return null;
}
/**
* @param node
* @return
*/
public SplaySubTree<T> find(T node) {
SplaySubTree<T> current = this;
if (this.data == null)
return null;
while (current != null) {
if (node.equals(current.data))
return current;
if (node.compareTo(current.data) < 0)
current = current.left;
else
current = current.right;
}
return current;
}
/**
* Assuming this node is an interior or leaf node of a larger tree this method
* moves this node up to the root balancing the tree in the process
*/
public boolean splay() {
while (this.parent != null) {
SplaySubTree<T> p = this.parent;
SplaySubTree<T> g = p.parent;
if (g == null && this == p.left) {
zig();
} else if (g == null && this == p.right) {
zag();
} else if (p.left == this && g.left == p) {
zigzig();
} else if (p.right == this && g.right == p) {
zagzag();
} else if (p.right == this && g.left == p) {
zigzag();
} else {
zagzig();
}
}
return true;
}
/**
* This is a helper method used in the splay() operation
*/
private void zig() {
SplaySubTree<T> b = this.right;
SplaySubTree<T> p = this.parent;
this.right = p;
p.parent = this;
p.left = b;
if (b != null)
b.parent = p;
this.parent = null;
p.size = p.count;
if (p.right != null)
p.size += p.right.size;
if (b != null)
p.size += b.size;
this.size = p.size + this.count;
if (this.left != null)
this.size += this.left.size;
}
/**
* This is a helper method used in the splay() operation
*/
private void zag() {
SplaySubTree<T> b = this.left;
SplaySubTree<T> p = this.parent;
this.left = p;
p.parent = this;
p.right = b;
if (b != null)
b.parent = p;
this.parent = null;
p.size = p.count;
if (b != null)
p.size += b.size;
if (p.left != null)
p.size += p.left.size;
this.size = p.size + this.count;
if (this.right != null)
this.size += this.right.size;
}
/**
* This is a helper method used by zigzig, zagzag, zigzag, zagzig This "fixes"
* the great grandparent
*/
private void fixGG(SplaySubTree<T> g) {
SplaySubTree<T> gg = g.parent;
if (gg != null) {
if (g == gg.left)
gg.left = this;
if (g == gg.right)
gg.right = this;
}
this.parent = gg;
// might need to update size
}
/**
* This is a helper method used in the splay() operation
*/
private void zigzig() {
SplaySubTree<T> g = parent.parent;
SplaySubTree<T> b = this.right;
SplaySubTree<T> p = this.parent;
SplaySubTree<T> c = p.right;
fixGG(g);
if (b != null)
b.parent = p;
p.left = b;
if (c != null)
c.parent = g;
g.left = c;
g.parent = p;
p.right = g;
p.parent = this;
this.right = p;
g.size = g.count;
if (c != null)
g.size += c.size;
if (g.right != null)
g.size += g.right.size;
p.size = p.count;
if (g != null)
p.size += g.size;
if (b != null)
p.size += b.size;
this.size = p.size + this.count;
if (this.left != null)
this.size += this.left.size;
}
/**
* This is a helper method used in the splay() operation
*/
private void zagzag() {
SplaySubTree<T> g = parent.parent;
SplaySubTree<T> b = this.left;
SplaySubTree<T> p = this.parent;
SplaySubTree<T> c = p.left;
fixGG(g);
if (b != null)
b.parent = p;
// above line throws java.lang.NullPointerException
p.right = b;
if (c != null)
c.parent = g;
g.right = c;
g.parent = p;
p.left = g;
p.parent = this;
this.left = p;
g.size = g.count;
if (g.left != null)
g.size += g.left.size;
if (c != null)
g.size += c.size;
p.size = g.size + p.count;
if (b != null)
p.size += b.size;
this.size = p.size + this.count;
if (this.right != null)
this.size += this.right.size;
}
/**
* This is a helper method used in the splay() operation
*/
private void zigzag() {
SplaySubTree<T> g = parent.parent;
SplaySubTree<T> b = this.left;
SplaySubTree<T> p = this.parent;
SplaySubTree<T> c = this.right;
fixGG(g);
if (b != null)
b.parent = p;
p.right = b;
if (c != null)
c.parent = g;
g.left = c;
p.parent = this;
this.left = p;
g.parent = this;
this.right = g;
g.size = g.count;
if (g.right != null)
g.size += g.right.size;
if (c != null)
g.size += c.size;
p.size = p.count;
if (p.left != null)
p.size += p.left.size;
if (b != null)
p.size += b.size;
this.size = g.size + p.size + this.count;
}
/**
* This is a helper method used in the splay() operation
*/
private void zagzig() {
SplaySubTree<T> g = parent.parent;
SplaySubTree<T> b = this.right;
SplaySubTree<T> p = this.parent;
SplaySubTree<T> c = this.left;
fixGG(g);
if (b != null)
b.parent = p;
p.left = b;
if (c != null)
c.parent = g;
g.right = c;
p.parent = this;
this.right = p;
g.parent = this;
this.left = g;
g.size = g.count;
if (g.left != null)
g.size += g.left.size;
if (c != null)
g.size += c.size;
p.size = p.count;
if (p.right != null)
p.size += p.right.size;
if (b != null)
p.size += b.size;
this.size = g.size + p.size + this.count;
}
}
![[西湖论剑 2022]real_ez_node](https://img-blog.csdnimg.cn/f2f2440106c046e59fe55dfce7e937ac.png)
![【蓝桥每日一题]-快速幂，倍增，滑动窗口（保姆级教程 篇1） #麦森数 #青蛙跳](https://img-blog.csdnimg.cn/550e34936324463ea1c1b964065b7854.png)
