/*
说明:程序实现二维数组中插入列、插入行、交换两个指定位置的元素，并输出指定位置元素的变化轨迹作者:socrates日期:2014-08-17
*/

#include "stdafx.h"
#include <stdlib.h> 
#include <assert.h>

/*二维数组最大行数和列数*/
#define MAX_ROW_NUM (9)
#define MAX_COL_NUM (9)

/*二维数组中各元素位置信息*/
typedef struct _PathNode
{
    int x;  /*行*/
    int y;  /*列*/
}Node;

/*各元素内容(表示位置轨迹的链表)*/
typedef struct _PathNodeList
{
    Node node;
    _PathNodeList *pNext;
}PathNodeList;

/*表示二维数组有效的行列数*/
typedef struct _CurRowColNum
{
    int iArrayRow;
    int iArrayCol;
}CurRowColNum;

/*二维数组行列数*/
static CurRowColNum g_stRowColNum = {0};

/*二维数组定义*/
PathNodeList* g_pGrid[MAX_ROW_NUM][MAX_COL_NUM];

/*错误码*/
enum _RetCode
{
    ERR = -1, /*失败*/
    OK = 0    /*成功*/
}RETCODE;

/*设置当前数组行列数*/
void SetRowAndColNum(int iRow, int iCol)
{
    g_stRowColNum.iArrayRow = iRow;
    g_stRowColNum.iArrayCol = iCol;
}

/*获取数组行列数*/
CurRowColNum getRowAndColNum()
{
    return g_stRowColNum;
}

/*创建轨迹链表，不带头结点*/
int CreatePathNodelist(PathNodeList *&pList, Node *pPathNode)
{
    if (NULL == pPathNode)
    {
        return ERR;
    }
    
    pList = (PathNodeList *)malloc(sizeof(PathNodeList));
    if (NULL == pList)
    {
        return ERR;
    }
    pList->node.x = pPathNode->x;
    pList->node.y = pPathNode->y;
    pList->pNext = NULL;
    
    return OK;
}

/*销毁轨迹链表*/
int DestoryPathNodelist(PathNodeList *pList)
{
    if (NULL == pList)
    {
        return ERR;
    }
    
    PathNodeList *p = pList;
    while (NULL != p->pNext)
    {
        p = p->pNext;
        free(pList);
        pList = p;
    }    
    free(pList);
    pList = NULL;

    return OK;
}

/*向轨迹链表中插入当前结点所在位置*/
int InsertPathNodeList(PathNodeList *pPathNodeList, Node *pPathNode)
{
    if ((NULL == pPathNodeList)
        || (NULL == pPathNode))
    {
        return ERR;
    }
    
    PathNodeList *pNewPathNode = (PathNodeList *)malloc(sizeof(PathNodeList));
    if (NULL == pPathNode)
    {
        return ERR;
    }
    
    pNewPathNode->node.x = pPathNode->x;
    pNewPathNode->node.y = pPathNode->y;
    pNewPathNode->pNext = NULL;
    
    PathNodeList *p = pPathNodeList;
    while (NULL != p->pNext)
    {
        p = p->pNext;
    }
    
    p->pNext = pNewPathNode;
    
    return OK;
}

/*初始化二维数组*/
int InitGrid(int iXNum, int iYNum)
{  
    if ((iXNum < 0) || (iXNum > MAX_ROW_NUM))
    {
        return ERR;
    }

    if ((iYNum < 0) || (iYNum > MAX_COL_NUM))
    {
        return ERR;
    }

    /*存储数组行列个数*/
    SetRowAndColNum(iXNum, iYNum);

    /*数组中的每个元素均建立一个以应的链表存放其运行轨迹，
    没有初始化元素默认为NULL*/
    for (int i = 0; i < iXNum; i++)
    {
        for (int j = 0; j < iYNum; j++)
        {
            Node node = {0};
            node.x = i;
            node.y = j;
            
            if (OK != CreatePathNodelist(g_pGrid[i][j], &node))
            {
                return ERR;
            }
        }
    }
    
    return OK;
}

/*销毁二维数组*/
int DestoryGrid()
{
    CurRowColNum stcurRowColNum = getRowAndColNum();
    for (int i = 0; i < stcurRowColNum.iArrayRow; i++)
    {
        for (int j = 0; j < stcurRowColNum.iArrayCol; j++)
        {
            if (OK != DestoryPathNodelist(g_pGrid[i][j]))
            {
                continue;
            }
        }
    }

    return OK;
}

/*获取元素当前所在位置*/
Node *GetCurPostion(PathNodeList *pPathList)
{
    if (NULL == pPathList)
    {
        return NULL;
    }

    PathNodeList *p = pPathList;

    /*链表的最后一个结点表示当前位置*/
    while(NULL != p->pNext)
    {
        p = p->pNext;
    }

    return &(p->node);
}

/*交换两个结点的位置*/
int SwapNode(Node aNode, Node bNode)
{   

    Node *paNode = GetCurPostion(g_pGrid[aNode.x][aNode.y]);
    Node *pbNode = GetCurPostion(g_pGrid[bNode.x][bNode.y]);

    /*将b结点的当前位置插入到a结点链表中*/    
    if (OK != InsertPathNodeList(g_pGrid[aNode.x][aNode.y], pbNode))
    {
        return ERR;
    }
    
    /*将a结点的当前位置插入到b结点链表中*/  
    if (OK != InsertPathNodeList(g_pGrid[bNode.x][bNode.y], paNode))
    {
        return ERR;
    }

    /*交换a、b两个结点*/
    PathNodeList *pTmp = NULL;
    pTmp = g_pGrid[aNode.x][aNode.y];
    g_pGrid[aNode.x][aNode.y] = g_pGrid[bNode.x][bNode.y];
    g_pGrid[bNode.x][bNode.y] = pTmp;

    return OK;
}

/*向数组中没有使用的行插入元素*/
int insertToEmptyRow(int iRow)
{
    CurRowColNum stcurRowColNum = getRowAndColNum();
    
    for (int j = 0; j < stcurRowColNum.iArrayCol; j++)
    {
        Node node = {0};
        node.x = iRow;
        node.y = j;
             
        if (OK != CreatePathNodelist(g_pGrid[iRow][j], &node))
        {
            return ERR;
        }
    }  
    
    return OK;
}

/*向二维数组插入一行*/
int insertRowtoGrid(int iInsertRow)
{
    if (MAX_ROW_NUM <= iInsertRow)
    {
        return ERR;
    }

    CurRowColNum stcurRowColNum = getRowAndColNum();

    /*插入数组中的无效行，直接插入，而向已有行中间插入，需要从前
    向后两两交换行元素的位置*/
    if (iInsertRow >= stcurRowColNum.iArrayRow)
    {
        if (OK != insertToEmptyRow(iInsertRow))
        {
            return ERR;
        }
    }
    else
    {
        /*先将新行插入第一个无效行中*/
        if (OK != insertToEmptyRow(stcurRowColNum.iArrayRow))
        {
            return ERR;
        }  

        /*从刚插入的新行开始，按行两两交换，直到把插入的行
        置换到参数指定的位置*/
        for (int i = stcurRowColNum.iArrayRow; i > iInsertRow; i--)
        {
            for (int j = 0; j < stcurRowColNum.iArrayCol; j++)
            {
                Node curNode;
                Node nextNode;

                curNode.x = i - 1;
                curNode.y = j;

                nextNode.x = i;
                nextNode.y = j;
                
                if (OK != SwapNode(curNode, nextNode))
                {
                    return ERR;
                }                
            }
        }
            
    }

    /*数组有效行数加1*/
    SetRowAndColNum(stcurRowColNum.iArrayRow + 1, stcurRowColNum.iArrayCol);
    
    return OK;
}

/*获取二维数组中指定结点的运动轨迹*/
int GetNodePath(Node pathNode, PathNodeList **pPathList)
{    
    CurRowColNum stcurRowColNum = getRowAndColNum();
    if ((pathNode.x < 0) 
        || (pathNode.x >= stcurRowColNum.iArrayRow))
    {
        *pPathList = NULL;
        return ERR;
    }

    if ((pathNode.y < 0) 
        || (pathNode.y >= stcurRowColNum.iArrayCol))
    {
        *pPathList = NULL;
        return ERR;
    }

    *pPathList = g_pGrid[pathNode.x][pathNode.y];
    return OK;

}

/*向数组中没有使用的列插入元素*/
int insertToEmptyCol(int iCol)
{
    CurRowColNum stcurRowColNum = getRowAndColNum();
    
    for (int i = 0; i < stcurRowColNum.iArrayRow; i++)
    {
        Node node = {0};
        node.x = i;
        node.y = iCol;
             
        if (OK != CreatePathNodelist(g_pGrid[i][iCol], &node))
        {
            return ERR;
        }
    } 
    
    return OK;
}

/*向二维数组插入一列*/
int insertColtoGrid(int iInsertCol)
{
    if (MAX_COL_NUM <= iInsertCol)
    {
        return ERR;
    }

    CurRowColNum stcurRowColNum = getRowAndColNum();

    /*插入数组中的无效列，直接插入，而向已有列中间插入，需要从前
    向后两两交换列元素的位置*/
    if (iInsertCol >= stcurRowColNum.iArrayCol)
    {
        if (OK != insertToEmptyCol(iInsertCol))
        {
            return ERR;
        }
    }
    else
    {
        /*先将新行插入第一个无效列中*/
        if (OK != insertToEmptyCol(stcurRowColNum.iArrayCol))
        {
            return ERR;
        }  

        /*从刚插入的新列开始，按列两两交换，直到把插入的列
        置换到参数指定的位置*/
        for (int j = stcurRowColNum.iArrayCol; j > iInsertCol; j--)
        {
            for (int i = 0; i < stcurRowColNum.iArrayRow; i++)
            {
                Node curNode;
                Node nextNode;

                curNode.x = i;
                curNode.y = j - 1;

                nextNode.x = i;
                nextNode.y = j;
                
                if (OK != SwapNode(curNode, nextNode))
                {
                    return ERR;
                }                
            }
        }
            
    }

    /*数组有效列数加1*/
    SetRowAndColNum(stcurRowColNum.iArrayRow, stcurRowColNum.iArrayCol + 1);
    
    return OK;
}


/*测试代码*/
int main(int argc, char* argv[])
{
    assert(OK == InitGrid(5, 5));
    
    PathNodeList *pList = NULL;
    Node node;
    node.x = 3;
    node.y = 4;

    Node node1;
    node1.x = 1;
    node1.y = 1;

    Node node2;
    node2.x = 4;
    node2.y = 4;

    assert(OK == SwapNode(node, node1));
    assert(OK == insertRowtoGrid(1));
    assert(OK == insertColtoGrid(3));
    
    assert(OK == GetNodePath(node2, &pList));

    PathNodeList *p = pList;
    while (NULL != p)
    {
        printf("(%d\t%d)\n", p->node.x, p->node.y);
        p = p->pNext;
    }

    assert(OK == DestoryGrid());
    return 0;
}