自学教程：C++ spListElementCreate函数代码示例

static bool testListInsertAfterCurrent() {	ASSERT_TRUE(SP_LIST_NULL_ARGUMENT == spListInsertAfterCurrent(NULL, NULL));	SPListElement e1 = spListElementCreate(1, 1.0);	SPListElement e2 = spListElementCreate(2, 2.0);	SPListElement e3 = spListElementCreate(3, 3.0);	SPListElement e4 = spListElementCreate(4, 4.0);	SPList list2 = quickList(3, e2, e3, e4);	ASSERT_TRUE(SP_LIST_NULL_ARGUMENT == spListInsertAfterCurrent(list2,NULL));	ASSERT_TRUE(SP_LIST_INVALID_CURRENT == spListInsertAfterCurrent(list2, e1));	spListGetFirst(list2);	spListGetNext(list2);	ASSERT_TRUE(SP_LIST_SUCCESS == spListInsertAfterCurrent(list2, e1));	ASSERT_TRUE(4 == spListGetSize(list2));	ASSERT_TRUE(spListElementCompare(e2, spListGetFirst(list2))==0);	ASSERT_TRUE(spListElementCompare(e3, spListGetNext(list2))==0);	ASSERT_TRUE(spListElementCompare(e1, spListGetNext(list2))==0);	ASSERT_TRUE(spListElementCompare(e4, spListGetNext(list2))==0);	ASSERT_TRUE(spListGetNext(list2) == NULL);	ASSERT_TRUE(spListGetNext(list2) == NULL);	spListDestroy(list2);	spListElementDestroy(e1);	spListElementDestroy(e2);	spListElementDestroy(e3);	spListElementDestroy(e4);	return true;}

static bool testListCopy() {	ASSERT_TRUE(spListCopy(NULL) == NULL);	SPList list = spListCreate();	SPList copy = spListCopy(list);	ASSERT_TRUE(copy != NULL);	ASSERT_TRUE(0 == spListGetSize(copy));	SPListElement e1 = spListElementCreate(1, 1.0);	SPListElement e2 = spListElementCreate(2, 2.0);	SPListElement e3 = spListElementCreate(3, 3.0);	SPListElement e4 = spListElementCreate(4, 4.0);	spListInsertFirst(list, e1);	ASSERT_TRUE(0 == spListGetSize(copy));	SPList list2 = quickList(4, e1, e2, e3, e4);	SPList copy2 = spListCopy(list2);	ASSERT_TRUE(4 == spListGetSize(copy2));	ASSERT_TRUE(spListElementCompare(e1, spListGetFirst(copy2)) == 0);	ASSERT_TRUE(spListElementCompare(e2, spListGetNext(copy2)) == 0);	ASSERT_TRUE(spListElementCompare(e3, spListGetNext(copy2)) == 0);	ASSERT_TRUE(spListElementCompare(e4, spListGetNext(copy2)) == 0);	ASSERT_TRUE(spListGetNext(copy2) == NULL);	spListDestroy(list);	spListDestroy(list2);	spListDestroy(copy);	spListDestroy(copy2);	spListElementDestroy(e1);	spListElementDestroy(e2);	spListElementDestroy(e3);	spListElementDestroy(e4);	return true;}

static bool testListForEach() {	SPListElement e1 = spListElementCreate(1, 1.0);	SPListElement e2 = spListElementCreate(2, 2.0);	SPListElement e3 = spListElementCreate(3, 3.0);	SPListElement e4 = spListElementCreate(4, 4.0);    SPListElement e5 = spListElementCreate(5, 5.0);	SPListElement arr[5] = {e1,e2,e3,e4,e5};	int i = 1;	SPList list = quickList(3, e2, e3, e4);	SP_LIST_FOREACH(SPListElement,e,list){		ASSERT_TRUE(spListElementCompare(e,arr[i]) == 0);		i++;	}

static bool testListGetPrevious() {	ASSERT_TRUE(spListGetNext(NULL) == NULL);	SPListElement e1 = spListElementCreate(1, 1.0);	SPListElement e2 = spListElementCreate(2, 2.0);	SPListElement e3 = spListElementCreate(3, 3.0);	SPListElement e4 = spListElementCreate(4, 4.0);	SPList list2 = quickList(4, e1, e2, e3, e4);	ASSERT_TRUE(spListGetPrevious(list2) == NULL);	spListDestroy(list2);	spListElementDestroy(e1);	spListElementDestroy(e2);	spListElementDestroy(e3);	spListElementDestroy(e4);	return true;}

static bool testIsElementGetValue() {	SPListElement element1 = spListElementCreate(1, 0.0);	SPListElement element2 = spListElementCreate(2, 1.0);	SPListElement element3 = spListElementCreate(3, 1.0);	SPListElement element4 = spListElementCreate(4, 2.0);	ASSERT_TRUE(spListElementGetValue(element1) == 0.0);	ASSERT_TRUE(spListElementGetValue(element2) == 1.0);	ASSERT_TRUE(spListElementGetValue(element3) == 1.0);	ASSERT_TRUE(spListElementGetValue(element4) == 2.0);	spListElementDestroy(element1);	spListElementDestroy(element2);	spListElementDestroy(element3);	spListElementDestroy(element4);	return true;}

static bool testElementGetIndex() {	SPListElement element1 = spListElementCreate(1, 0.0);	SPListElement element2 = spListElementCreate(2, 0.0);	SPListElement element3 = spListElementCreate(3, 1.0);	SPListElement element4 = spListElementCreate(4, 0.0);	ASSERT_TRUE(spListElementGetIndex(element1) == 1);	ASSERT_TRUE(spListElementGetIndex(element2) == 2);	ASSERT_TRUE(spListElementGetIndex(element3) == 3);	ASSERT_TRUE(spListElementGetIndex(element4) == 4);	ASSERT_TRUE(spListElementGetIndex(NULL) == -1);	spListElementDestroy(element1);	spListElementDestroy(element2);	spListElementDestroy(element3);	spListElementDestroy(element4);	return true;}

static bool bpqEmptyTest() {	SPBPQueue source, source2;	SPListElement e1;	source = NULL;	ASSERT_TRUE(spBPQueueIsEmpty(source) == true); // check edge case	source = spBPQueueCreate(maxSize);	ASSERT_TRUE(spBPQueueIsEmpty(source) == true); // check that new queue is empty	// insert a new element and check that not empty	e1 = spListElementCreate(1, 1.0);	source2 = quickQ(1, e1);	ASSERT_TRUE(spBPQueueIsEmpty(source2) == false);	// remove the element and check that empty	spBPQueueDequeue(source2);	ASSERT_TRUE(spBPQueueIsEmpty(source) == true);	// free memory	spBPQueueDestroy(source);	spBPQueueDestroy(source2);	spListElementDestroy(e1);	return true;}

static bool bpqGetMaxSizeTest() {	SPBPQueue source = NULL;	SPListElement e1;	ASSERT_TRUE(-1 == spBPQueueGetMaxSize(source)); //check edge case	// check that max size is always maxSize	source = quickQ(0);	ASSERT_TRUE(maxSize == spBPQueueGetMaxSize(source));	// insert a new element and check max size	e1 = spListElementCreate(1, 1.0);	spBPQueueEnqueue(source, e1);	ASSERT_TRUE(maxSize == spBPQueueGetMaxSize(source));	// insert another element and check max size	spListElementSetIndex(e1, 2);	spListElementSetValue(e1, 2.0);	spBPQueueEnqueue(source, e1);	ASSERT_TRUE(maxSize == spBPQueueGetMaxSize(source));	// remove an element and check max size	spBPQueueDequeue(source);	ASSERT_TRUE(maxSize == spBPQueueGetMaxSize(source));	// free memory	spBPQueueDestroy(source);	spListElementDestroy(e1);	return true;}

/** * internal help method to find the k nearest neighbors */void spKNNSearch(SPPoint queryFeature, const SPKDTreeNode node, SPBPQueue q){    SPListElement element;    int index, distance;    bool distanceFlag = false;    if(!node){        return;    }    if(node->dim==INVALID){				//** this is a leaf **//        index = spPointGetIndex(node->data);        distance = spPointL2SquaredDistance(queryFeature, node->data);        element = spListElementCreate(index, distance);        spBPQueueEnqueue(q, element);        spListElementDestroy(element);        return;    }    			//** go to the left sub tree **//    if(spPointGetAxisCoor(queryFeature, node->dim)<= node->val){        spKNNSearch(queryFeature, node->left, q);        distance = pow((spPointGetAxisCoor(queryFeature,        									node->dim) - node->val),2);        distanceFlag = distance < spBPQueueMaxValue(q);        if(!spBPQueueIsFull(q) || distanceFlag){            spKNNSearch(queryFeature, node->right, q);        }    }else{        spKNNSearch(queryFeature, node->right, q);        distance = pow((spPointGetAxisCoor(queryFeature,        									node->dim) - node->val),2);        distanceFlag = distance < spBPQueueMaxValue(q);        if(!spBPQueueIsFull(q) || distanceFlag){            spKNNSearch(queryFeature, node->left, q);        }    }    return;}

static bool testElementCompare() {	SPListElement element1 = spListElementCreate(1, 0.0);	SPListElement element2 = spListElementCreate(2, 0.0);	SPListElement element3 = spListElementCreate(1, 1.0);	SPListElement element4 = spListElementCreate(1, 0.0);	ASSERT_TRUE(spListElementCompare(element1, element1) == 0);	ASSERT_TRUE(spListElementCompare(element1, element2) < 0);	ASSERT_TRUE(spListElementCompare(element2, element1) > 0);	ASSERT_TRUE(spListElementCompare(element1, element3) < 0);	ASSERT_TRUE(spListElementCompare(element3, element1) > 0);	ASSERT_TRUE(spListElementCompare(element1, element4) == 0);	ASSERT_TRUE(spListElementCompare(element4, element1) == 0);	spListElementDestroy(element1);	spListElementDestroy(element2);	spListElementDestroy(element3);	spListElementDestroy(element4);	return true;}

static bool testListClear() {	SPListElement e1 = spListElementCreate(1, 1.0);	SPListElement e2 = spListElementCreate(2, 2.0);	SPListElement e3 = spListElementCreate(3, 3.0);	SPListElement e4 = spListElementCreate(4, 4.0);	SPList list2 = quickList(4, e1, e2, e3, e4);	ASSERT_TRUE(spListClear(list2) == SP_LIST_SUCCESS);	ASSERT_TRUE(0 == spListGetSize(list2));	SPList list = spListCreate();	spListClear(list);	ASSERT_TRUE(0 == spListGetSize(list));	spListDestroy(list);	spListDestroy(list2);	spListElementDestroy(e1);	spListElementDestroy(e2);	spListElementDestroy(e3);	spListElementDestroy(e4);	return true;}

/** * Allocates a Qnode in the memory. * * @param node to copy * @return * NULL in case allocation failure occurred * Otherwise, the new node is returned */ struct Qnode* newNode(int index, double value){     struct Qnode *res = (struct Qnode*)malloc(sizeof(struct Qnode));     if (!res){        return NULL;     }    res->element = spListElementCreate(index, value);    res->next=NULL;    return res; }

void SPKDTreeKNNRecursive(SPKDTreeNode treeNode, SPPoint p, SPBPQueue bpq, SP_KDTREE_MSG* msg){	SPListElement listElement;	SPPoint treePoint;	bool searchedLeft;	double dist;	if(bpq == NULL || treeNode == NULL)	{		*msg = SP_KDTREE_INVALID_ARGUMENT;		return;	}	// If treeNode is a leaf	if(treeNode->left == NULL && treeNode->right == NULL)	{		treePoint = *(treeNode->data);		listElement = spListElementCreate(spPointGetIndex(treePoint), spPointL2SquaredDistance(p, treePoint));		spBPQueueEnqueue(bpq, listElement);		spListElementDestroy(listElement);		*msg = SP_KDTREE_SUCCESS;		return;	}	// Turn to search the tree that would've contain the point p (if it was in the tree)	if(spPointGetAxisCoor(p, treeNode->dim) <= treeNode->val)	{		searchedLeft = true;		SPKDTreeKNNRecursive(treeNode->left, p, bpq, msg);		if (*msg != SP_KDTREE_SUCCESS)			return;	}	else	{		searchedLeft = false;		SPKDTreeKNNRecursive(treeNode->right, p, bpq, msg);		if (*msg != SP_KDTREE_SUCCESS)			return;	}	// dist = |treeNode.val - p[treeNode.dim]|	dist = treeNode->val - spPointGetAxisCoor(p, treeNode->dim);	if(dist < 0)		dist *= -1;	//dist *= dist;	if(!spBPQueueIsFull(bpq) || dist < spBPQueueMaxValue(bpq))	{		if(searchedLeft)			SPKDTreeKNNRecursive(treeNode->right, p, bpq, msg);		else			SPKDTreeKNNRecursive(treeNode->left, p, bpq, msg);	}	}

static bool testListGetLast() {	SPList list = spListCreate();	ASSERT_TRUE(spListGetLast(list) == NULL);	SPListElement e1 = spListElementCreate(1, 1.0);	SPListElement e2 = spListElementCreate(2, 2.0);	SPListElement e3 = spListElementCreate(3, 3.0);	SPListElement e4 = spListElementCreate(4, 4.0);	SPList list2 = quickList(4, e1, e2, e3, e4);	SPListElement last = spListGetLast(list2);	ASSERT_TRUE(spListElementCompare(e4, last) == 0);	ASSERT_TRUE(			spListElementCompare(last, spListGetLast(list2)) == 0					&& spListGetLast(list2) == last);	spListDestroy(list);	spListDestroy(list2);	spListElementDestroy(e1);	spListElementDestroy(e2);	spListElementDestroy(e3);	spListElementDestroy(e4);	return true;}

static bool bpqGetSizeTest() {	SPBPQueue source = NULL;	SPListElement e1, e;	ASSERT_TRUE(-1 == spBPQueueSize(source)); //check edge case	source = quickQ(0);	ASSERT_TRUE(0 == spBPQueueSize(source));	// insert a new element and check size	e1 = spListElementCreate(1, 1.0);	spBPQueueEnqueue(source, e1);	ASSERT_TRUE(1 == spBPQueueSize(source));	// make sure that inserting same element twice works	spListElementSetIndex(e1, 2);	spListElementSetValue(e1, 2.0);	spBPQueueEnqueue(source, e1);	ASSERT_TRUE(2 == spBPQueueSize(source));	// remove an element and check size	spBPQueueDequeue(source);	ASSERT_TRUE(1 == spBPQueueSize(source));	// insert more then maxSize elements and check that size is always less then maxSize	for (int i = 0; i < 2 * maxSize; i++) {		ASSERT_TRUE(spBPQueueSize(source) <= maxSize);		e = spListElementCreate(i, 1.0);		spBPQueueEnqueue(source, e);		spListElementDestroy(e);	}	// free memory	spBPQueueDestroy(source);	spListElementDestroy(e1);	return true;}

static bool testElementSetIndex() {	ASSERT_TRUE(spListElementGetIndex(NULL) == -1);	ASSERT_TRUE(spListElementSetIndex(NULL,-1) ==SP_ELEMENT_INVALID_ARGUMENT);	ASSERT_TRUE(spListElementSetIndex(NULL,1) ==SP_ELEMENT_INVALID_ARGUMENT);	ASSERT_TRUE(spListElementSetIndex(NULL,-1) ==SP_ELEMENT_INVALID_ARGUMENT);	SPListElement element = spListElementCreate(1, 0.0);	ASSERT_TRUE(			spListElementSetIndex(element, -1) == SP_ELEMENT_INVALID_ARGUMENT);	ASSERT_TRUE(spListElementGetIndex(element) == 1);	ASSERT_TRUE(spListElementSetIndex(element, 2) == SP_ELEMENT_SUCCESS);	ASSERT_TRUE(spListElementGetIndex(element) == 2);	spListElementDestroy(element);	return true;}

static bool testElementSetValue() {	ASSERT_TRUE(spListElementGetValue(NULL) == -1.0);	ASSERT_TRUE(spListElementSetValue(NULL,-1.0) ==SP_ELEMENT_INVALID_ARGUMENT);	ASSERT_TRUE(spListElementSetValue(NULL,1.0) ==SP_ELEMENT_INVALID_ARGUMENT);	ASSERT_TRUE(spListElementSetValue(NULL,-1.0) ==SP_ELEMENT_INVALID_ARGUMENT);	SPListElement element = spListElementCreate(1, 0.0);	ASSERT_TRUE(			spListElementSetValue(element, -1.0)					== SP_ELEMENT_INVALID_ARGUMENT);	ASSERT_TRUE(spListElementGetValue(element) == 0.0);	ASSERT_TRUE(spListElementSetValue(element, 1.0) == SP_ELEMENT_SUCCESS);	ASSERT_TRUE(spListElementGetValue(element) == 1.0);	spListElementDestroy(element);	return true;}

static bool testElementCopy() {	ASSERT_TRUE(spListElementCopy(NULL) == NULL);	SPListElement element = spListElementCreate(1, 0.0);	SPListElement elementCopy = spListElementCopy(element);	ASSERT_TRUE(elementCopy!=NULL);	ASSERT_TRUE(spListElementCompare(element, elementCopy) == 0);	ASSERT_TRUE(spListElementSetIndex(elementCopy, 2) == SP_ELEMENT_SUCCESS);	ASSERT_TRUE(spListElementCompare(element, elementCopy) < 0);	ASSERT_TRUE(spListElementGetIndex(elementCopy) == 2);	ASSERT_TRUE(spListElementGetIndex(element) == 1);	ASSERT_TRUE(spListElementSetValue(element, 1.0) == SP_ELEMENT_SUCCESS);	ASSERT_TRUE(spListElementCompare(element, elementCopy) > 0);	spListElementDestroy(element);	spListElementDestroy(elementCopy);	return true;}

static bool testListGetSize() {	SPList list = quickList(0);	ASSERT_TRUE(0 == spListGetSize(list));	SPListElement e1 = spListElementCreate(1, 1.0);	spListInsertFirst(list, e1);	ASSERT_TRUE(1 == spListGetSize(list));	spListElementSetIndex(e1, 2);	spListElementSetValue(e1, 2.0);	spListInsertFirst(list, e1);	ASSERT_TRUE(2 == spListGetSize(list));	spListGetFirst(list);	spListRemoveCurrent(list);	ASSERT_TRUE(1 == spListGetSize(list));	spListDestroy(list);	spListElementDestroy(e1);	return true;}

/** * Given a kd-tree and a point p, the function stores the nearest neighbors of p to bpq * * @param curr - the kd-tree containing the points * @param bpq - the bounded priority queue to store the nearest neighbors in * @param p - the point to find the nearest neighbors to * * does nothing if curr == NULL or bpq == NULL or p == NULL */void nearestNeighbors(KDTreeNode curr, SPBPQueue bpq, SPPoint p) {	SPListElement node;	SPPoint q;	bool isLeft;	double coorDis;	if (curr == NULL || bpq == NULL || p == NULL )		return;	q = curr->data;	/* Add the current point to the BPQ. Note that this is a no-op if the	 * point is not as good as the points we've seen so far.*/	if (curr->dim == -1) {		int index;		double dis;		index = spPointGetIndex(q);		dis = spPointL2SquaredDistance(p, curr->data);		node = spListElementCreate(index, dis);		spBPQueueEnqueue(bpq, node);		spListElementDestroy(node);		return;	}	/* Recursively search the half of the tree that contains the test point. */	if (spPointGetAxisCoor(p, curr->dim) <= curr->val) {		nearestNeighbors(curr->left, bpq, p);		isLeft = true;	} else {		nearestNeighbors(curr->right, bpq, p);		isLeft = false;	}	/* If the candidate hypersphere crosses this splitting plane, look on the	 * other side of the plane by examining the other subtree*/	coorDis = abs(spPointGetAxisCoor(p, curr->dim) - curr->val);	if (!spBPQueueIsFull(bpq) || coorDis*coorDis < spBPQueueMaxValue(bpq)) {		if (isLeft)			nearestNeighbors(curr->right, bpq, p);		else			nearestNeighbors(curr->left, bpq, p);	}}

static bool bpqFullTest() {	SPBPQueue source;	SPListElement e1;	source = NULL;	ASSERT_TRUE(spBPQueueIsFull(source) == false); // check edge case	source = spBPQueueCreate(maxSize);	// insert maxSize element and check that full at the end	while (spBPQueueSize(source) < maxSize) {		ASSERT_TRUE(spBPQueueIsFull(source) == false); // check that not full in the process		e1 = spListElementCreate(1, 1.0);		spBPQueueEnqueue(source, e1);		spListElementDestroy(e1);	}	ASSERT_TRUE(spBPQueueIsFull(source) == true);	// free memory	spBPQueueDestroy(source);	return true;}

static bool bpqDequeueTest() {	SPBPQueue source;	SPListElement e;	ASSERT_TRUE(SP_BPQUEUE_INVALID_ARGUMENT == spBPQueueDequeue(NULL)); // check edge case	source = spBPQueueCreate(maxSize);	ASSERT_TRUE(SP_BPQUEUE_INVALID_ARGUMENT == spBPQueueDequeue(source)); // check edge case	// insert maxSize elements, then remove them	for (int i = 0; i < maxSize; i++) {		e = spListElementCreate(i, (double) i);		spBPQueueEnqueue(source, e);		spListElementDestroy(e);	}	for (int i = 0; i < maxSize; i++) {		ASSERT_TRUE((int )spBPQueueMinValue(source) == i); // check that the minimum was removed on the last dequeue		ASSERT_TRUE(spBPQueueDequeue(source) == SP_BPQUEUE_SUCCESS); // check that dequeue succeeded	}	// free memory	spBPQueueDestroy(source);	return true;}

static bool bpqEnqueueTest() {	SPBPQueue source, source2;	SPListElement e, e1, e2, e3, e4, e5, peek, peekLast;	ASSERT_TRUE(SP_BPQUEUE_INVALID_ARGUMENT == spBPQueueEnqueue(NULL, NULL)); // check edge case	CREATE_4_ELEMENTS() // e1, e2, e3, e4	e5 = spListElementCreate(5, 4.0);	source = quickQ(3, e2, e1, e4);	ASSERT_TRUE(SP_BPQUEUE_SUCCESS == spBPQueueEnqueue(source, e3)); // check that enqueue succeeded	ASSERT_TRUE(SP_BPQUEUE_SUCCESS == spBPQueueEnqueue(source, e5));	ASSERT_TRUE(5 == spBPQueueSize(source));	// check that enqueue inserts in order	peek = spBPQueuePeek(source);	peekLast = spBPQueuePeekLast(source);	ASSERT_TRUE(spListElementCompare(e1, peek) == 0);	// make sure queue sorts by value and then by index	ASSERT_TRUE(spListElementCompare(e5, peekLast) == 0);	// e1, e2, e3, e4	DESTROY_4_ELEMENTS()	spListElementDestroy(e5);	// create new queue with maxSize	source2 = spBPQueueCreate(maxSize);	// insert 2*maxSize elements from lowest to highest value and check that min and max are correct	for (int i = 0; i < maxSize; i++) {		e = spListElementCreate(i, (double) i);		ASSERT_TRUE(SP_BPQUEUE_SUCCESS == spBPQueueEnqueue(source2, e));		spListElementDestroy(e);	}	for (int i = maxSize; i < 2 * maxSize; i++) {		e = spListElementCreate(i, (double) i);		ASSERT_TRUE(SP_BPQUEUE_FULL == spBPQueueEnqueue(source2, e)); // check full when inserting more then maxSize elements		spListElementDestroy(e);	}	ASSERT_TRUE(spBPQueueMinValue(source2) == 0.0);	// check that all elements with value too high are not in the queue	ASSERT_TRUE((int )spBPQueueMaxValue(source2) == maxSize - 1);	spBPQueueClear(source2);	// insert 2*maxSize elements from highest to lowest value and check that min and max are correct and same as before	for (int i = 2 * maxSize - 1; i >= 0; i--) {		e = spListElementCreate(i, (double) i);		spBPQueueEnqueue(source2, e);		spListElementDestroy(e);	}	// check min value is correct	ASSERT_TRUE(spBPQueueMinValue(source2) == 0.0);	ASSERT_TRUE((int )spBPQueueMaxValue(source2) == maxSize - 1);	// free memory	spBPQueueDestroy(source);	spBPQueueDestroy(source2);	spListElementDestroy(peek);	spListElementDestroy(peekLast);	return true;}

static bool testElementCreate() {	SPListElement e = spListElementCreate(1, 0.0);	ASSERT_TRUE(e!=NULL);	spListElementDestroy(e);	return true;}