<?php

/**
 * 链表和数组的区别就是 数据是个有序的内存空间 链表是个无序的内存空间但是可以把有序的内存空间连续起来
 * 链表是一种代码的实现逻辑并不是底层的  链表每增加一个节点就会随机向内存申请一个内存地址  而数组是直接向内存申请一个有序内存空间
 *
 *  数组在操作 添加 修改 删除节点时候都是在整体移动 而链表不是 链表则是重新该表指针的指向 操作起来要比数组快
 *
 *查询的时间复杂度就没有数组那么快了   是不是要扫扫去全表 全部链表  必须要从链表的头部开始进行查找，一个一个去遍历，直到找到自己想要的元素
 * 类似于 for 循环全表查询时间复杂度 O(n)
 *
 *
 * 链表几个特性：
 *      头部指向第一个节点
 *  head
 *    |
 *  node  = {value,next} = first_node;
 *    |
 *  node = {value,next} = next_node;
 *    |
 *  node = {value,next} = next_node;
 *    |
 * node = {value,next} = last_node;  指向最后一个 null
 *    |
 *  null
 * 单链表
 *
 * 循环链表
 *
 *实在单项链表上面的升级 ，循环链表尾部不在指向null 而是指向头部指向的第一个节点  闭合形成了一个圆
 *
 *  head
 *    |
 *  node  = {value,next} = first_node;
 *    |
 *  node = {value,next} = next_node;
 *    |
 *  node = {value,next} = next_node;
 *    |
 * node = {value,next} = last_node;  指向最后一个 null
 *    |
 *  first_node
 *
 * 双向链表
 *
 *双向链表在单项链表的基础每个节点增加了指向上一个节点
 *
 *  *  head
 *    |
 *  node  = {value,next,prev} = first_node;
 *    |
 *  node = {value,next,prev} = next_node;
 *    |
 *  node = {value,next,prev} = next_node;
 *    |
 * node = {value,next,prev} = last_node;  指向最后一个 null
 *    |
 *  first_node
 *
 *
 * LRU的全称为Least Recently Used，它是一种内存数据淘汰算法
 * 类似于清理衣柜里面的衣服
 *
 * 分为三类
 *
 * old 衣服  不穿了
 * ing  已经不怎么穿的衣服
 * recently 衣服 常穿的衣服
 *
 *
 */


/**
 * 单项链表节点  没有索引位置这个说话 其实就是 每个自己的主要节点的信息 附加下一节点的地址
 *
 * 单向链表就是一个思想 算法 每个节点可以承载更多的信息 附加下一个节点信息
 */
class  Node {

    public ?string $selfInfo = null;
    public ?string $nodeId = null;//删除的时候使用
    public ?Node $nextNode = null;//存放下一个节点

    /**
     * Node constructor.
     * @param string $nodeId
     * @param string $selfInfo
     */
    public  function __construct(?string $nodeId, ?string $selfInfo)
    {
        $this->nodeId = $nodeId;
        $this->selfInfo = $selfInfo;
    }

    /**
     * @return Node
     */
    public function getNextNode(): ?Node
    {
        return $this->nextNode;
    }

    /**
     * @param Node $nextNode
     */
    public function setNextNode(?Node $nextNode): void
    {
        $this->nextNode = $nextNode;
    }

    /**
     * @return string
     */
    public function getSelfInfo(): string
    {
        return $this->selfInfo;
    }

    /**
     * @return sting|string
     */
    public function getNodeId()
    {
        return $this->nodeId;
    }

    /**
     * @param sting|string $nodeId
     */
    public function setNodeId($nodeId): void
    {
        $this->nodeId = $nodeId;
    }

}

/**
 * 链表列表
 */
class LinkList {

    /**
     * @var Node
     */
    protected  Node $head ; //虚拟节点头
    protected int  $size; //链表长度

    protected static  Node $lastNode;
    protected static  Node $firstNode;
    protected static int $count;

    public static $ins;

   static function getIns(...$arg):LinkList {
        if(empty(self::$ins)){
            self::$ins = new static();
        }
        return self::$ins;
    }

    /**构造函数
     * LinkList constructor.
     * @param string $type
     */
   public function  __construct(string $type)
   {
       $this->head = new Node("0","head");//初始化
       $this->size = 0;//链表长度刚开始是0
   }

   //

    public function add(Node $addNode):self {
          //判断头部有没有节点
         if(empty($this->head->getNextNode())) {
             $this->head->setNextNode($addNode);
             $this->size++;
             self::$lastNode = $addNode;
             return $this;
         }
        //头部有节点就开始有序往后添加
//        $curNode = $this->head;
//         while (!empty($curNode->getNextNode())){
//            $curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
//         }
//        $curNode->setNextNode($addNode);
 //       return $addNode;
         //这里可有优化一下 不用每次添加节点的时候都要重头遍历 时间复杂度太高了
        // 可以利用累的静态变量来存储最后一个节点
        // 这样在每次添加的时候就可以直接引用这里最后一个节点 就不用再从头遍历了
        self::$lastNode->setNextNode($addNode); //上一个最后节点指向新加的节点
        self::$lastNode=$addNode; //新加的节点就会变成最后一个节点
        return  $this;
    }

    /**
     * 实现有序链表
     * @param Node $addListNode
     * @return $this
     * @throws Exception
     */
    public function addList(Node $addListNode):self {
     //头部节点要是没有第一个节点就判断添加的节点是不是1
        if(empty($this->head->getNextNode())){
             if((int)$addListNode->getNodeId()>1)   {
                 throw  new Exception("添加节点的数量大于有序列表最大值".$this->head->getNodeId(),1000);
             }
        }

        $curNode = $this->head;
        while (!empty($curNode->getNextNode())) {
            // 判断当前已有的节点ID是否大于要加入的节点ID，如果大于则break
            $curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
            if((int)$curNode->getNodeId() >= (int)$addListNode->getNodeId())
            {
               throw  new Exception("添加节点的数量应该有序列表最大值".$curNode->getNodeId(),1000);
            }
        }

        if((int)$addListNode->getNodeId() > (int)$curNode->getNodeId()+1 ){
            throw  new Exception("添加".$addListNode->getNodeId()."节点的数量应该小于等于".((int)$curNode->getNodeId()+1),1000);
        }

        $curNode->setNextNode($addListNode);
        return  $this;
    }

    // 获取链表长度
    public function getLinkSize() {
        $curNode = $this->head;
        $num = 0;
        while(!empty($curNode->getNextNode())) {
            $num ++;
            $curNode = $curNode->getNextNode();
        }
        return $num;
    }

    /**
     * 添加循环链表
     * @param Node $cycleNode
     */
    public function  addCycleLink(Node $cycleNode):self {
        //空链表
        if(empty($this->head->getNextNode())){
            $cycleNode->setNextNode($this->head);
            $this->head->setNextNode($cycleNode);
            return $this;
        }

        //获取最后的节点最后的节点指向头部


    }

   public function update(int $index,Node $node){

   }

   public function delete(Node $delNode):self {

         $curNode = $this->head;
         while (!empty($curNode->getNextNode())){
            $curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
             //节点id 要是对上了就删除当前节点 为了保障链表的连续性 删除了当前节点的要把上个节点和删除后的下个节点老地址连接上
             //这里要有个注意的点进行修正 如果用当前节点进行删除的话 无法记录了上一个节点 所以这里要用当前节点的下一个节点进行比对 如果下一个节点对上上了 就直接修改下一个节点的指向
             if($curNode->getNextNode()->getNodeId() ==$delNode->getNodeId()){
                 if(empty($curNode->getNextNode()->getNextNode())){
                     //最后一个节点
                     $curNode->setNextNode(null);//连接删除节点的上一个节点和删除的下一个节点
                     $this->size--;
                     break;
                 }
                 $delNodeAfter = $curNode->getNextNode()->getNextNode();//记录要删除节点后的所有节点
                 $curNode->setNextNode($delNodeAfter);//连接删除节点的上一个节点和删除的下一个节点
                 break;
             }
         }
         return $this;
   }

   public function toString():self {
       $str = "head->";
       $curNode = $this->head;
       while (!empty($curNode->getNextNode())){
           $curNode = $curNode->getNextNode();//重置当前节点往下遍历 可以理解指针后移
           if(empty($curNode->getNextNode())){
               $str.=$curNode->getNodeId()."->end";
               break;
           }
           $str.=$curNode->getNodeId()."->";
       }
       echo $str. " size = ".$this->getLinkSize().PHP_EOL;
       return  $this;
   }

   public function search(Node $node):int
   {
       $index = 0;
        return $index;
   }

}
    (new linkList)
    ->add(new Node("1","1"))
    ->add(new Node("3","3"))
    ->add(new Node("4","4"))
    ->add(new Node("2","2"))
    ->toString()
    ->delete(new Node("2","2"))
    ->toString();

(new linkList)
    ->addList(new Node("1","1"))
    ->addList(new Node("2","2"))
    ->addList(new Node("3","3"))
    ->toString()
    ->addList(new Node("5","3"))
    ->toString();