<?php

/* 
 * Przykładowy kod do książki: Algorytmy i struktury danych w języku PHP 7
 * 
 * Autor: Mizanur Rahman <mizanur.rahman@gmail.com>
 * 
 */


class ListNode {

   public $data = NULL;
   public $next = NULL;

   public function __construct(string $data = NULL) {
      $this->data = $data;
   }

}


class LinkedList implements Iterator {

   private $_firstNode = NULL;
   private $_totalNode = 0;
   private $_currentNode = NULL;
   private $_currentPosition = 0;

   public function insert(string $data = NULL) {
      $newNode = new ListNode($data);
      if ($this->_firstNode === NULL) {
         $this->_firstNode = &$newNode;
      } else {
         $currentNode = $this->_firstNode;
         while ($currentNode->next !== NULL) {
            $currentNode = $currentNode->next;
         }
         $currentNode->next = $newNode;
      }
      $this->_totalNode++;
      return TRUE;
   }

   public function insertAtFirst(string $data = NULL) {
      $newNode = new ListNode($data);
      if ($this->_firstNode === NULL) {
         $this->_firstNode = &$newNode;
      } else {
         $currentFirstNode = $this->_firstNode;
         $this->_firstNode = &$newNode;
         $newNode->next = $currentFirstNode;
      }
      $this->_totalNode++;
      return TRUE;
   }

   public function search(string $data = NULL) {
      if ($this->_totalNode) {
         $currentNode = $this->_firstNode;
         while ($currentNode !== NULL) {
            if ($currentNode->data === $data) {
               return $currentNode;
            }
            $currentNode = $currentNode->next;
         }
      }
      return FALSE;
   }

   public function insertBefore(string $data = NULL, string $query = NULL) {
      $newNode = new ListNode($data);

      if ($this->_firstNode) {
         $previous = NULL;
         $currentNode = $this->_firstNode;
         while ($currentNode !== NULL) {
            if ($currentNode->data === $query) {
               $newNode->next = $currentNode;
               $previous->next = $newNode;
               $this->_totalNode++;
               break;
            }
            $previous = $currentNode;
            $currentNode = $currentNode->next;
         }
      }
   }

   public function insertAfter(string $data = NULL, string $query = NULL) {
      $newNode = new ListNode($data);

      if ($this->_firstNode) {
         $nextNode = NULL;
         $currentNode = $this->_firstNode;
         while ($currentNode !== NULL) {
            if ($currentNode->data === $query) {
               if ($nextNode !== NULL) {
                  $newNode->next = $nextNode;
               }
               $currentNode->next = $newNode;
               $this->_totalNode++;
               break;
            }
            $currentNode = $currentNode->next;
            $nextNode = $currentNode->next;
         }
      }
   }

   public function deleteFirst() {
      if ($this->_firstNode !== NULL) {
         if ($this->_firstNode->next !== NULL) {
            $this->_firstNode = $this->_firstNode->next;
         } else {
            $this->_firstNode = NULL;
         }
         $this->_totalNode--;
         return TRUE;
      }
      return FALSE;
   }

   public function deleteLast() {
      if ($this->_firstNode !== NULL) {
         $currentNode = $this->_firstNode;
         if ($currentNode->next === NULL) {
            $this->_firstNode = NULL;
         } else {
            $previousNode = NULL;

            while ($currentNode->next !== NULL) {
               $previousNode = $currentNode;
               $currentNode = $currentNode->next;
            }

            $previousNode->next = NULL;
            $this->_totalNode--;
            return TRUE;
         }
      }
      return FALSE;
   }

   public function delete(string $query = NULL) {
      if ($this->_firstNode) {
         $previous = NULL;
         $currentNode = $this->_firstNode;
         while ($currentNode !== NULL) {
            if ($currentNode->data === $query) {
               if ($currentNode->next === NULL) {
                  $previous->next = NULL;
               } else {
                  $previous->next = $currentNode->next;
               }

               $this->_totalNode--;
               break;
            }
            $previous = $currentNode;
            $currentNode = $currentNode->next;
         }
      }
   }

   public function reverse() {
      if ($this->_firstNode !== NULL) {
         if ($this->_firstNode->next !== NULL) {
            $reversedList = NULL;
            $next = NULL;
            $currentNode = $this->_firstNode;
            while ($currentNode !== NULL) {
               $next = $currentNode->next;
               $currentNode->next = $reversedList;
               $reversedList = $currentNode;
               $currentNode = $next;
            }
            $this->_firstNode = $reversedList;
         }
      }
   }

   public function getNthNode(int $n = 0) {
      $count = 1;
      if ($this->_firstNode !== NULL && $n <= $this->_totalNode) {
         $currentNode = $this->_firstNode;
         while ($currentNode !== NULL) {
            if ($count === $n) {
               return $currentNode;
            }
            $count++;
            $currentNode = $currentNode->next;
         }
      }
   }

   public function display() {
      echo "Wszystkich elementów na liście: " . $this->_totalNode . "\n";
      $currentNode = $this->_firstNode;
      while ($currentNode !== NULL) {
         echo $currentNode->data . "\n";
         $currentNode = $currentNode->next;
      }
   }

   public function getSize() {
      return $this->_totalNode;
   }

   public function current() {
      return $this->_currentNode->data;
   }

   public function next() {
      $this->_currentPosition++;
      $this->_currentNode = $this->_currentNode->next;
   }

   public function key() {
      return $this->_currentPosition;
   }

   public function rewind() {
      $this->_currentPosition = 0;
      $this->_currentNode = $this->_firstNode;
   }

   public function valid() {
      return $this->_currentNode !== NULL;
   }

}


class DeQueue {

   private $limit;
   private $queue;

   public function __construct(int $limit = 20) {
      $this->limit = $limit;
      $this->queue = new LinkedList();
   }

   public function dequeueFromFront(): string {

      if ($this->isEmpty()) {
         throw new UnderflowException('Kolejka jest pusta');
      } else {
         $lastItem = $this->peekFront();
         $this->queue->deleteFirst();
         return $lastItem;
      }
   }

   public function dequeueFromBack(): string {

      if ($this->isEmpty()) {
         throw new UnderflowException('Kolejka jest pusta');
      } else {
         $lastItem = $this->peekBack();
         $this->queue->deleteLast();
         return $lastItem;
      }
   }

   public function enqueueAtBack(string $newItem) {
      if ($this->queue->getSize() < $this->limit) {
         $this->queue->insert($newItem);
      } else {
         throw new OverflowException('Kolejka jest pełna');
      }
   }

   public function enqueueAtFront(string $newItem) {
      if ($this->queue->getSize() < $this->limit) {
         $this->queue->insertAtFirst($newItem);
      } else {
         throw new OverflowException('Kolejka jest pełna');
      }
   }

   public function peekFront(): string {
      return $this->queue->getNthNode(1)->data;
   }

   public function peekBack(): string {
      return $this->queue->getNthNode($this->queue->getSize())->data;
   }

   public function isEmpty(): bool {
      return $this->queue->getSize() == 0;
   }

}


try {
   $agents = new DeQueue(10);
   $agents->enqueueAtFront("Franek");
   $agents->enqueueAtFront("Janek");
   $agents->enqueueAtBack("Krzysiek");
   $agents->enqueueAtBack("Adrian");
   $agents->enqueueAtFront("Michał");
   echo $agents->dequeueFromBack() . "\n";
   echo $agents->dequeueFromFront() . "\n";
   echo $agents->peekFront() . "\n";
} catch (Exception $e) {
   echo $e->getMessage();
}
