/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
        let head = null
        let nowNode = null 
        let list1pointer = list1;
        let list2pointer = list2;
		// 兩兩比較
        if(list1 === null && list2 === null) return head
        if(list1 === null && list2 !== null) return list2
        if(list1 !== null && list2 === null) return list1
        
  
        // 決定 head
        // 因為當你選擇了 list1pointer 作為頭節點後，你應該：
            // 移動 list1pointer 指針：list1pointer = list1pointer.next
            // 設定 nowNode 為當前的尾節點：nowNode = head
        if(list1pointer.val <= list2pointer.val ){
            head = list1pointer
            list1pointer = list1pointer.next
        }else{
             head = list2pointer
             list2pointer = list2pointer.next
        }
        nowNode = head

        //進入迴圈檢查
        while(list1pointer !== null && list2pointer !== null){
            if(list1pointer.val <= list2pointer.val){
                nowNode.next =  list1pointer
                list1pointer = list1pointer.next
            }else {
                nowNode.next =  list2pointer
                // 移動指針
                list2pointer = list2pointer.next
            }
            nowNode = nowNode.next;
        }
        // 最後要再檢查。其中一不為 null 
        if(list1pointer !== null){
            nowNode.next = list1pointer
        }else{
            nowNode.next = list2pointer
        }

        return head
    
};

// 排序工具
export function sortListDataBySeqNo(listData: ListData[]): ListData[] {
  return [...listData].sort((a, b) => {
    const aSeqNo = a.seqNo || 0;
    const bSeqNo = b.seqNo || 0;
    return aSeqNo - bSeqNo;
  });
}

 export function calculateInsertStrategy(
  existingListData: ListData[],
  afterListDataId: string
): {
  insertSeqNo: number;
  affectedListData: ListData[];
  updateOperations: Array<{ listDataId: string; newSeqNo: number }>;
} {
  const sortedListData = sortListDataBySeqNo(existingListData);
  const afterIndex = sortedListData.findIndex(data => data.id === afterListDataId);

  if (afterIndex === -1) {
    throw new Error('afterListDataId not found');
  }

  // 關鍵：插入點的 seqNo + 1
  const insertSeqNo = sortedListData[afterIndex].seqNo! + 1;
  // 只影響插入點之後的項目
  const affectedListData = sortedListData.slice(afterIndex + 1);

  // 產生更新操作清單
  const updateOperations = affectedListData.map(data => ({
    listDataId: data.id,
    newSeqNo: data.seqNo! + 1
  }));

  return { insertSeqNo, affectedListData, updateOperations };
}

export async function executeSeqNoUpdates(
  transaction: Transaction,
  operations: Array<{ listDataId: string; newSeqNo: number }>
): Promise<void> {
  for (const operation of operations) {
    // 更新每個受影響的項目
    const listDataRef = adminDb.collection('listData').doc(operation.listDataId);
    transaction.update(listDataRef, {
      seqNo: operation.newSeqNo,
      updatedAt: new Date()
    });
  }
}

  // POST /api/v1/listData
 export async function POST(req: Request) {
  // ... 驗證邏輯

  if (afterListDataId) {
    try {
      // 步驟1: 計算最小更新策略
      const { updateOperations, insertSeqNo } =
        calculateInsertStrategy(existingListData, afterListDataId);

      // 步驟2: Transaction 執行
      const result = await adminDb.runTransaction(async (transaction) => {
        await executeSeqNoUpdates(transaction, updateOperations);

        // 插入新項目
        const listDataRef = adminDb.collection('listData').doc();
        transaction.set(listDataRef, {
          ...newListData,
          seqNo: insertSeqNo
        });

        return { id: listDataRef.id, seqNo: insertSeqNo };
      });

      return NextResponse.json(result, { status: 201 });
    } catch (error) {
      if (error.message === 'afterListDataId not found') {
        return NextResponse.json({ message: 'afterListDataId not found' }, { status: 404 });
      }
      throw error;
    }
  }
}

function dfs(node) {
  if (node === null) return baseValue;
  const left = dfs(node.left);
  const right = dfs(node.right);
  return combine(left, right, node);
}

let result = 0;
let pathDepth = 0;

function traverse(node) {
  if (node === null) return;

  pathDepth++; // 遞迴深入，深度 +1
  if (node.left === null && node.right === null) {
    result = Math.max(result, pathDepth); // 若為葉子，更新最大深度
  }

  traverse(node.left);
  traverse(node.right);

  pathDepth--; // 回歸
}

var slidingWindow = function(s) {
    // 使用合適的資料結構記錄視窗中的資料，根據具體題目變通。
    // 例如：記錄字元出現的次數，或累加窗口內元素的和。
    let window = {};  

    let left = 0, right = 0;
    while (right < s.length) {
        // 取出將要加入視窗的字元
        let c = s[right];
        right++;  // 擴大窗口

        // 更新窗口內資料
        // 例如：window[c] = (window[c] || 0) + 1;
        // 根據具體題目邏輯進行更新

        // *** Debug 輸出位置 *** 
        // console.log("窗口: [%d, %d)", left, right);

        // 當窗口不再滿足題目要求時，收縮窗口
        while (/* 判斷窗口需要收縮的條件 */) {
            // 取得將要移除的字元（為使變數名稱更具描述性可用 removedChar）
            let removedChar = s[left];
            left++;  // 縮小窗口

            // 更新移除字元對窗口資料的影響
            // 例如：if (window[removedChar] ...) { ... }
        }
    }
};