00001
00002
00003
00004
00005 #include "grid_queue.h"
00006 using namespace wustl_mm::SkeletonMaker;
00007
00008 GridQueue::GridQueue( ) {
00009 head = NULL ;
00010 tail = NULL ;
00011 numEles = 0 ;
00012 }
00013
00014 gridQueueEle* GridQueue::getHead( ) {
00015 return head ;
00016 }
00017
00018 int GridQueue::getNumElements( ) {
00019 return numEles ;
00020 }
00021
00022
00023 void GridQueue::sort( int eles ) {
00024
00025 gridQueueEle* pre ;
00026 gridQueueEle* e1 ;
00027 gridQueueEle* e2 ;
00028
00029 for ( int i = eles - 1 ; i > 0 ; i -- )
00030 {
00031 pre = NULL ;
00032 e1 = head ;
00033 e2 = e1->next ;
00034
00035 for ( int j = 0 ; j < i ; j ++ )
00036 {
00037 if ( e1->score < e2->score )
00038 {
00039 swapEle( pre, e1, e2 ) ;
00040 }
00041 else if ( e1->score == e2->score && rand() < RAND_MAX / 2)
00042 {
00043 swapEle( pre, e1, e2 ) ;
00044 }
00045
00046 if ( pre == NULL )
00047 {
00048 pre = head ;
00049 }
00050 else
00051 {
00052 pre = pre->next;
00053 }
00054 e1 = pre->next ;
00055 e2 = e1->next ;
00056 }
00057 }
00058
00059
00060
00061
00062
00063
00064
00065
00066 }
00067
00068
00069 void GridQueue::pushQueue( int xx, int yy, int zz ) {
00070 gridQueueEle* ele = new gridQueueEle ;
00071 ele->x = xx ;
00072 ele->y = yy ;
00073 ele->z = zz ;
00074 ele->score = 0 ;
00075 ele->next = NULL ;
00076 if ( head == NULL )
00077 {
00078 head = ele ;
00079 }
00080 else
00081 {
00082 tail->next = ele ;
00083 }
00084 tail = ele ;
00085 numEles ++ ;
00086 }
00087
00088 int GridQueue::popQueue( int& xx, int& yy, int& zz ) {
00089 if ( head == NULL )
00090 {
00091 return 0 ;
00092 }
00093
00094 xx = head->x ;
00095 yy = head->y ;
00096 zz = head->z ;
00097
00098 gridQueueEle* temp = head ;
00099 head = head->next ;
00100 delete temp ;
00101
00102 if ( head == NULL )
00103 {
00104 tail = NULL ;
00105 }
00106 numEles -- ;
00107
00108 return 1 ;
00109 }
00110
00111
00112 void GridQueue::swapEle( gridQueueEle* pre, gridQueueEle* e1, gridQueueEle* e2 )
00113 {
00114 if ( pre != NULL )
00115 {
00116 e1->next = e2->next ;
00117 e2->next = pre->next ;
00118 pre->next = e2 ;
00119
00120 if ( tail == e2 )
00121 {
00122 tail = e1 ;
00123 }
00124 }
00125 else
00126 {
00127 e1->next = e2->next ;
00128 e2->next = e1 ;
00129 head = e2 ;
00130
00131 if ( tail == e2 )
00132 {
00133 tail = e1 ;
00134 }
00135 }
00136 }