<?php

//Implementacja listy z wartownikiem
//Marek Rynarzewski
//www.algorytm.org

	//Wartownik
	class Wartownik
	{
		//poprzednik
		public $prev;
		//nastepnik
		public $next;

		//Utworz wartownika
		public function __construct()
		{
			$this->prev = $this;
			$this->next = $this;
		}
	}

	//Element to wartownik rozszerzony o wartosc klucza
	class Element extends Wartownik
	{
		//klucz
		public $key;
	}

	//Lista z wartownikiem
	class ListaZWartownikiem
	{
		//wartownik
		public $wartownik;

		//rozmiar listy
		private $rozmiar = 0;

		//Utworz liste
		public function __construct()
		{
			$this->wartownik = new Wartownik;
		}

		//Utworz element o zadanej wartosci klucza
		static public function przypisz($wartosc)
		{
			$elem = new Element;
			$elem->key = $wartosc;
			return $elem;
		}

		//Wstaw nowa wartosc do listy
		public function wstawWartosc($wartosc)
		{
			$elem = ListaZWartownikiem::przypisz($wartosc);
			$this->wstawElement($elem);
		}

		//Wstaw nowy element do Marek Rynarzewski
		public function wstawElement(Element $elem)
		{
			$elem->next = $this->wartownik->next;
			$this->wartownik->next->prev = $elem;
			$this->wartownik->next = $elem;
			$elem->prev = $this->wartownik;
			$this->rozmiar++;
		}

		//Szukaj zadanej wartosci w liscie
		public function szukaj($wartosc)
		{
			$x = $this->wartownik->next;
			while ($x != $this->wartownik and $x->key != $wartosc)
				$x = $x -> next;

			if ($x != $this->wartownik)
				return $x;

			return NULL;
		}

		//Usuwa element z listy
		public function usun(Element $elem)
		{
			$elem->prev->next = $elem->next;
			$elem->next->prev = $elem->prev;
			$this->rozmiar --;
		}

		//Wykonaj funkcje dla n pierwszych elementow listy
		public function dlaNPierwszych($n, $funkcja)
		{
			$x = $this->wartownik->next;
			while ($n > 0 and $x != $this->wartownik)
			{
				$funkcja($x);
				$x = $x -> next;
				$n --;
			}
		}

		//Wykonaj funkcje dla wszystkich elementow listy
		public function dlaWszystkich($funkcja)
		{
			$x = $this->wartownik->next;
			while ($x != $this->wartownik)
			{
				$funkcja($x);
				$x = $x -> next;
			}
		}

		//Przekonwertuj liste na tablice
		public function toArray()
		{
			$tablica = array();
			$x = $this->wartownik->next;
			while ($x != $this->wartownik)
			{
				$tablica[] = $x->key;
				$x = $x -> next;
			}
			return $tablica;
		}
	}
?>