/****************************************************************************
**    File name:         AdjustByInsert.c
**    Description:    調整一個鏈表，使鏈表左側的數為奇數，右側的為偶數
**    Author:            Liu Qi, //
**    Version:        0.1
**    commnet:    
****************************************************************************/
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include "../sllist.h"

#define MAX_NUM 10


/*===========================================================================
**    Function name:        AdjustByInsert 
**    Parameter:            L:鏈表頭指針
**    Precondition:        NULL != L && NULL != L->Next
**    Description:        調整一個鏈表，使鏈表左側的數為奇數，右側的為偶數
算法：遍歷鏈表，若為奇數插入到L后面,時間復雜度O(n^2)
因為SLL_DeleteAt的時間復雜度也為O(n)
**    Return value:        void
**    Author:                Liu Qi, 2005/12/18
===========================================================================*/

void AdjustByInsert(List L)
{
    Position pos = L->Next;
    Position tmpPos;
    
    assert( (NULL != L) && (NULL != L->Next) ); 
    
    while (NULL != pos)
    {
        if ((pos->Element) % 2 != 0)    //為奇數
        {
            SLL_InsertAfter( pos->Element, L);
            tmpPos = pos;
            pos = SLL_NextPos(pos);
            SLL_DeleteAt(tmpPos, L);
        }
        else
        {
            pos = SLL_NextPos(pos);
        }
    }
}


/*===========================================================================
**    Function name:        AdjustBySwap 
**    Parameter:            L:鏈表頭指針
**    Precondition:        (NULL != L) && (NULL != L->Next)
**    Description:        調整一個鏈表，使鏈表左側的數為奇數，右側的為偶數
算法：通過交換來實現，使用兩個指針來遍歷鏈表，其中
一個指向偶數,時間復雜度O(n)

**    Return value:        void
**    Author:                Liu Qi, 2005/12/19
===========================================================================*/
void AdjustBySwap( List L)
{
    Position posEven = L->Next;
    Position pos = posEven->Next;
    ElemType tmp;
    
    assert( (NULL != L) && (NULL != L->Next) ); 
    
    for ( ; NULL != pos; pos = pos->Next)
    {
        if ( ((posEven->Element % 2) == 0) && ((pos->Element % 2) != 0) )
        {
            //swap
            tmp = pos->Element;
            pos->Element = posEven->Element;
            posEven->Element = tmp;
        }
        if ( ((posEven->Element % 2) != 0) )    //奇數，指向下一個
        {
            posEven = SLL_NextPos(posEven);
        }
    }
    
}





/*===========================================================================
**    Function name:        GetRandList
**    Parameter:            void
**    Precondition:        void
**    Description:        構造一個由隨機數組成的鏈表

**    Return value:        鏈表的頭節點指針
**    Author:                Liu Qi, 2005/12/18
===========================================================================*/

List GetRandList(void)
{
    int i;
    
    List L = SLL_Create();
    
    srand( (unsigned)time( NULL ) ); 
    for ( i = 0; i < MAX_NUM; i++)
    {
        SLL_PushFront(rand() % 10, L);
    }
    
    return L;
}



/*===========================================================================
**    Function name:        TestAdjustByInsert 
**    Parameter:            void
**    Precondition:        void
**    Description:        用于測試函數AdjustByInsert

**    Return value:        void
**    Author:                Liu Qi, 2005/12/19
===========================================================================*/
void TestAdjustByInsert( void )
{
    List L = GetRandList();
    SLL_PrintList(L);
    
    printf("\n");
    
    AdjustByInsert(L);
    SLL_PrintList(L);
    
    printf("\n");
    
    SLL_DeleteList(L);
    
}



/*===========================================================================
**    Function name:        TestAdjustBySwap
**    Parameter:            void    
**    Precondition:        void
**    Description:        測試函數AdjustBySwap

**    Return value:        
**    Author:                Liu Qi, 2005/12/19
===========================================================================*/
void TestAdjustBySwap( void )
{
    List L = GetRandList();
    SLL_PrintList(L);
    
    printf("\n");
    
    AdjustBySwap(L);
    SLL_PrintList(L);
    
    printf("\n");
    
    SLL_DeleteList(L);
}


int main(int argc, char *argv[])
{
    printf("TestAdjustByInsert:\n");
    TestAdjustByInsert();
    
    printf("TestAdjustBySwap:\n");
    TestAdjustBySwap();
    
    return 0;
}