双向循环队列-php实现历史记录的前进后退等功能
<?php include 'debug.php'; /** * 历史记录操作类 * 传入或者构造一个数组。形如: array( 'history_num'=>20, //队列节点总共个数 'first'=>0, //起始位置,从0开始。数组索引值 'last'=>0, //终点位置,从0开始。 'back'=>0, //从first位置倒退了多少步,差值。 'history'=>array( //数组,存放操作队列。 array('path'=>'D:/'), array('path'=>'D:/www/'), array('path'=>'E:/'), array('path'=>'/home/') …… ) ) */ class history{ var $history_num; var $first; var $last; var $back; var $history=array(); function __construct($array=array(),$num=12){ if (!$array) {//数组为空.构造一个循环队列。 $history=array(); for ($i=0; $i < $num; $i++) { array_push($history,array('path'=>'')); } $array=array( 'history_num'=>$num, 'first'=>0,//起始位置 'last'=>0,//终点位置 'back'=>0, 'history'=>$history ); } $this->history_num=$array['history_num']; $this->first=$array['first']; $this->last=$array['last']; $this->back=$array['back']; $this->history=$array['history']; } function nextNum($i,$n=1){//环路下n一个值。和时钟环路类似。 return ($i+$n)<$this->history_num ? ($i+$n):($i+$n-$this->history_num); } function prevNum($i,$n=1){//环路上一个值i。回退N个位置。 return ($i-$n)>=0 ? ($i-$n) : ($i-$n+$this->history_num); } function minus($i,$j){//顺时针两点只差,i-j return ($i > $j) ? ($i - $j):($i-$j+$this->history_num); } function getHistory(){//返回数组,用于保存或者序列化操作。 return array( 'history_num'=> $this->history_num, 'first' => $this->first, 'last' => $this->last, 'back' => $this->back, 'history' => $this->history ); } function add($path){ if ($this->back!=0) {//有后退操作记录的情况下,进行插入。 $this->goedit($path); return; } if ($this->history[0]['path']=='') {//刚构造,不用加一.首位不前移 $this->history[$this->first]['path']=$path; return; }else{ $this->first=$this->nextNum($this->first);//首位前移 $this->history[$this->first]['path']=$path; } if ($this->first==$this->last) {//起始位置与终止位置相遇 $this->last=$this->nextNum($this->last);//末尾位置前移。 } } function goback(){//返回从first后退N步的地址。 $this->back+=1; //最大后退步数为起点到终点之差(顺时针之差) $mins=$this->minus($this->first,$this->last); if ($this->back >= $mins) {//退到最后点 $this->back=$mins; } $pos=$this->prevNum($this->first,$this->back); return $this->history[$pos]['path']; } function gonext(){//从first后退N步的地方前进一步。 $this->back-=1; if ($this->back<0) {//退到最后点 $this->back=0; } return $this->history[$this->prevNum($this->first,$this->back)]['path']; } function goedit($path){//后退到某个点,没有前进而是修改。则firs值为最后的值。 $pos=$this->minus($this->first,$this->back); $pos=$this->nextNum($pos);//下一个 $this->history[$pos]['path']=$path; $this->first=$pos; $this->back=0; } //是否可以后退 function isback(){ if ($this->back < $this->minus($this->first,$this->last)) { return ture; } return false; } //是否可以前进 function isnext(){ if ($this->back>0) { return true; } return false; } } //测试