EMAN2
grid_queue.cpp
Go to the documentation of this file.
00001 // Copyright (C) 2005-2008 Washington University in St Louis, Baylor College of Medicine.  All rights reserved
00002 // Author:        Tao Ju, Refactored by Sasakthi S. Abeysinghe (sasakthi@gmail.com)
00003 // Description:   Grid queue
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                 /* Naive bubble sort */
00023                 void GridQueue::sort( int eles ) {
00024                         //printf("Sorting elements with descending scores...\n") ;
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                         /* Debugging
00060                         pre = head ;
00061                         while ( pre != NULL )
00062                         {
00063                                 printf("%d ", pre->score ) ;
00064                                 pre = pre->next ;
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                 /* Switching two elements */
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                 }