<?php
/*! ------------------------------------------------------------------------ *
 *  Clasa PkInts (Packed Integers)
 *
 *  @Author: Dumitru Uzun (DUzun)
 *  @Web   : http://duzun.teologie.net/
 *
 *  Calsa PkInts este un container de numere intregi pastrate in forma binara.
 *  Scopul este pastrare si prelucrarea listelor foarte mari de numere intregi.
 *
 * Proprietatile de acces secvential (INT):
 *   current - elementul curent
 *   reset   - treci la primul element
 *   end     - treci la ultimul element
 *   next    - treci la urmatorul element
 *   prev    - treci la elementul precedent
 *
 *   first   - primul element, fara cursor
 *   last    - ultimul element, fara cursor
 *
 *   push($val) - ataseaza un numar intreg la sfarsitul listei
 *   pop()      - extrage ultimul intreg din lista
 *
 * Toate aceste functii returneaza numarul INT corespunzator pozitiei noi
 * sau FALSE, daca pozitia noua este invalida.
 *
 * Atentie: Aceste proprietati pot avea valoarea Booleana FALSE, dar de asemenea
 *          pot avea valoarea non-Booleana 0, care se evalueaza ca FALSE.
 *          Foloseste operatorul === pentru a testa valoarea acestor proprietati.
 *
 *  ------------------------------------------------------------------------ */

/*------------------------------------------------------------------------*/
include_once(dirname(__FILE__).DIRECTORY_SEPARATOR.'bin_lib.php');
/*------------------------------------------------------------------------*/

class PkInts
{
   public $data    = '';    // Un string ce contine lista de numere codificate binar
   public $changed = false; // Indica modul de salvare a datelor in fisier la distrugerea obiectului
   private $isz    = INT_SIZE_SHLS;
//    public $file_name;       // Numele fisierului ce reprezinta lista
//    public $cursor;          // Indexul elementului curent la parcurgere
//    public $file_size;  // Dimensiunea fisierului la deskidere
   /*------------------------------------------------------------------------*/
   function __construct($fn=false, $is_data=false)
   {
      if(func_num_args() > 2) $this->isz = (int)func_get_arg(2);
      if($fn || $is_data) $this->load($fn, $is_data);
   }

   function __destruct()
   {
      if($this->changed) $this->save(false, $this->changed>0);
   }

   /*! Valoarea string a obiectului este reprezentarea hexazecimala a datelor binare */
   function __toString()
   {
      return bin2hex($this->data);
   }
   /*------------------------------------------------------------------------*/
   /// Getters
   function __get($name)
   {
      $cn = "get_$name";
      if(method_exists($this, $cn)) return $this->$cn();
      return null; // no method
   }
   
   /// Setters
   function __set($name, $value)
   {
      $cn = "set_$name";
      if(method_exists($this, $cn)) return $this->$cn($value); // no method
      if(!isset($this->$name)) return $this->$name = $value; // protect private properties
      return null; // no method, no property
   }   
   /*------------------------------------------------------------------------*/
   /*!
    * Incarca continutul fisierului $fn in obiect.
    *
    * Daca $is_data == TRUE, $fn se atribuie obiectului ca string binar.
    *
    * @return: Nr de octeti cititi din fisier sau FALSE la eroare.
    */
   function load($fn, $is_data=false)
   {
      if(is_array($fn)) $this->set_ints($fn); else
      if($is_data)
      {
         if(is_string($fn))  $this->data = &$fn; else
         if(is_numeric($fn)) $this->set_len(1) && $this->set_int($fn, 0); else
                             $this->data = strval($fn);
      }
      else
      {
         if(!$fn) return false; // nu e specificat fisierul
         $this->file_name = $fn;
         $this->reload();
      }
      return strlen($this->data);
   }

   function reload()
   {
      if(!$this->file_name) return false; // nu e specificat fisierul
      if(!is_file($this->file_name)) $this->data = ''; else 
      $this->data      = file_get_contents($this->file_name);
      $this->file_size = strlen($this->data); // used by save()
      $this->changed   = 0;
      return $this->file_size;
   }
   /*------------------------------------------------------------------------*/
   /*!
    * Salveaza continutul binar al obiectului in fisierul $fn.
    *
    * Daca $fn nu e specificat, incearca sa foloseasca fisierului
    * de la apelul precedent la $this->load().
    *
    * Daca e specificat $append == TRUE, se adauga doar surplusul
    * din continutul obiectului fata de continutul fisierului.
    * In acest caz, daca fisierul e mai mare, se trunchiaza.
    *
    * @return: Nr de octeti scrisi in fisier sau FALSE la eroare.
    */
   function save($fn=false, $append=false)
   {
      if($fn===false) $fn = $this->file_name;
      if(!$fn) return false; // nu e specificat fisierul
      if( $append && is_file($fn) &&
          $this->file_size == ($fsz = filesize($fn)) ) // probabil fisierul nu a fost modificat de la ultima citire
      {
//       debug_("fsz: ".$fsz);
         $sz = $this->get_size();
         if($fsz < $sz)
         {
             $r = @file_put_contents($fn, substr($this->data, $fsz, $sz-$fsz), FILE_APPEND);
             if($r === false) return false;
             $this->file_size = $fsz + $r; // used on next save
         } else
         if($fsz > $sz)
         {
             $f = @fopen($fn, 'ab');
             if(!$f) return false; // nu pot deskide fisierul
             $r = ftruncate($f, $sz);
             fclose($f);
             if(!$r) return false; // nu s-a trunchiat fisierul
             $this->file_size = $sz; // used on next save
         }
      } else { // daca nu atasam, suprascriem
         $r = file_put_contents($fn, $this->data);
         if($r === false) return false;
         $this->file_size = $r; // used on next save
      }
      $this->changed = false;
      clearstatcache();
      return $r;
   }
   /*------------------------------------------------------------------------*/
   /*! @return: TRUE, daca continutul lipseste sau toti octetii sunt == 0 */
   public function is_null() { return $this->not_null() === false; }

   /*! @return: Pozitia primului caracter nenul, sau FALSE daca nu exista */
   public function not_null($offset=0)
   {
      for($l=strlen($this->data); $offset<$l; $offset++) if($this->data[$offset] != NULL_CHAR) return $offset;
      return false;
   }

   /*! @return: Pozitia ultimului caracter nenul, sau FALSE daca nu exista */
   public function not_null_r($offset=-1)
   {
      if($l = strlen($this->data))
      {
         $dt = &$this->data;
         if($offset<0) $offset = $offset%$l+$l;
         if($offset+1<$l) $l = $offset+1;
         while($l--) if($dt[$l] != NULL_CHAR) return $l;
      }
      return false;
   }

   /// ~$this
   public function negate()
   {
      if($l = strlen($this->data)) {
         while($l--) $this->data[$l] = chr(~ord($this->data[$l]));
      } else $this->set_int(-1);
   }
   /*------------------------------------------------------------------------*/
   /// Insereaza sirul binar $val in pozitia $pos
   function ins_bin($pos, $val)
   {
      if($val)
      {
        $l = $this->get_size();
        if($pos < 0 ) $pos += $l; else
        if($pos > $l) $this->set_size($pos);
        if($pos < 0 ) return false;
        $this->data = substr($this->data, 0, $pos) . $val . substr($this->data, $pos);
        if($pos < $l) $this->changed = -1; else $this->changed |= 1;
      }
      return $this->get_size();
   }

   /// Elimina sirul binar de lungimea $sz din pozitia $pos
   function del_bin($pos, $sz)
   {
      $l = $this->get_size();
      if($pos < 0) $pos += $l;
      if($pos < 0) return false;
      if($pos+$sz > $l) $sz = $l-$pos;
      $this->data = substr_replace($this->data, '', $pos, $sz);
      $this->changed = -1;
      return $this->get_size();
   }
   /*------------------------------------------------------------------------*/
   /// Deplaseaza la stanga cu $nr_bits biti (shift left), in sensul scrierii numarului.
   /// Deplasarea nu e in sensul obisnuit, ca la numere de lungime fixa, si e cu crestere.
   function shl($nr_bits)
   {
      if(!$nr_bits) return ;                               // nu deplasam
      if($nr_bits<0) return $this->shr(-$nr_bits);
      $i = $this->not_null($i);                            // pozitia primului octet nenul
      if($i === false) return ;                            // nu avem ce deplasa, nu exista biti setati
      $l = $nr_bits >> 3;                                  // nr de octeti de deplasat
      $nr_bits &= 7;                                       // restul biti de deplasat
      $dt = &$this->data;
      if($l) $dt = str_repeat(NULL_CHAR, $l) . $dt;            // deplasam octetii
      if(!$nr_bits) return ;                               // nu sunt biti de deplasat
      $i += $l;                                            // noua pozitie a primului octet nenul
      $l = strlen($dt);
      $w = 0;
      // deplasarea bitilor se aplica octet cu octet, de aceea dureaza mult timp
      for(; $i<$l; $i++)
      {
         $b = ord($dt[$i]);
         if($b == 0 && $w == 0) continue;                  // oare se merita de examinat cazul intalnit foarte rar?
         $w |= $b << $nr_bits;                             // valoarea deplasata + transportul
         $dt[$i] = chr($w & BYTE_MASK);
         $w >>= 8;                                         // transportul operatiei
      }
      if($w) $dt .= chr($w);                               // transportul se adauga la coada
   }

   /// Deplaseaza la dreapta cu $nr_bits biti (shift right), in sensul scrierii numarului.
   /// Deplasarea nu e in sensul obisnuit, ca la numere de lungime fixa, si e cu micsorare.
   function shr($nr_bits)
   {
      if(!$nr_bits) return ;                        // nu deplasam
      if($nr_bits<0) return $this->shl(-$nr_bits);
      $l = $nr_bits >> 3;                           // nr de octeti de deplasat
      if($l) $this->data = substr($this->data, $l); // deplasam octetii
      $nr_bits &= 7;                                // restul biti de deplasat
      if(!$nr_bits) return ;                        // nu sunt biti de deplasat
      $l = $this->not_null_r();                     // pozitia ultimului octet nenul
      if($l === false) return ;                     // nu au mai ramas biti setati
      $dt = &$this->data;
      $w = 0;
      // deplasarea bitilor se aplica octet cu octet, de aceea dureaza mult timp
      do
      {
         $b = ord($dt[$l]);
         if($b == 0 && $w == 0) continue; // oare se merita de examinat cazul intalnit foarte rar?
         $w |= $b << (8 - $nr_bits) ;
         $dt[$l] = chr($w >> 8);
         $w <<= 8;                        // transportul operatiei
      } while($l--);
   }
   /*------------------------------------------------------------------------*/
   /*! Obtine dimensiunea in octeti a datelor */
   protected function get_size(){ return strlen($this->data); }

   /*! Seteaza dimensiunea in octeti a datelor.
    *  $ch este valoarea octetilor noi.
    */
   function set_size($sz, $ch = NULL_CHAR)
   {
      $l = $this->get_size();
      if($l < $sz)
      {
         $this->changed |= 1; // add new only
         if(!is_string($ch)) $ch = chr((int)$ch);
         $this->data .= str_repeat($ch, $sz - $l);
      }
      elseif($l > $sz)
      {
         $this->changed = -1; // rewrite all
         $this->data = substr($this->data, 0, $sz);
      }
      return $sz;
   }
   /*------------------------------------------------------------------------*/
   /// Obtine lungimea listei de numere intregi.
   function get_len()
   {
      return (strlen($this->data)+(1 << $this->isz)-1) >> $this->isz ;
   }

   /// Seteaza lungimea listei de nr intregi. Daca $length > $this->len, se adauga numarul $val.
   function set_len($len, $val=false)
   {
      if($val !== false)
      {
         $val = int2bs($val, 1 << $this->isz);
         return $this->set_size( $len << $this->isz, $val );
      } else
         return $this->set_size( $len << $this->isz );
   }
   /*------------------------------------------------------------------------*/
   /*! Citeste elementul nr $idx de string binar.
    *  Daca $idx < 0, se indexseaza de la sfarsit.
    */
   function get_bin($idx=0)
   {
      $l = $this->get_len();
      if(!$l) return false;
      if($idx<0) $idx += $l;
      if($idx<0 || $l<=$idx) return false;
      return substr($this->data, $idx << $this->isz, 1 << $this->isz);
   }

   /*! Scrie elementul nr $idx de string binar.
    *  Daca $idx < 0, se indexseaza de la sfarsit.
    */
   function set_bin($val, $idx=0)
   {
      $l = $this->get_len();
      if($idx<0) $idx = $l ? $idx%$l+$l: 0;
      if($idx>$l) $this->set_len($idx);
      $elem_size = 1 << $this->isz;

      $i = strlen($val);
      if($i < $elem_size) $val .= str_repeat(NULL_CHAR, $elem_size-$i); else
      if($i > $elem_size) $val = substr($val, 0, $elem_size);

      $i = $idx << $this->isz;
      if($idx < $l)
      {
         if($this->changed >= 0 && $val != substr($this->data, $i, $elem_size))
            $this->changed = -1;
         while($elem_size--) $this->data[$i+$elem_size] = $val[$elem_size];
      }
      else // if($idx >= $l)
      {
         $this->changed |= 1;
         $this->data .= $val;
      }

      return $val;
   }
   /*------------------------------------------------------------------------*/
   /*! Ataseaza $val la datele binare.
    *  @return: Pozitia $val.
    */
   function append_bin($val)
   {
      $sz = strlen($this->data);
      $this->data .= $val;
      $this->changed |= 1;
      return $sz; // pozitia de start a $val
   }
   /*------------------------------------------------------------------------*/
   /*! Elimina toate numerele egale cu $val din partea superioara a listei (de la coada)
    *  @return: Nr de elemente ramase in lista.
    */
   function ltrim($val)
   {
      $elem_size = 1 << $this->isz;
      $val       = int2bs($val, $elem_size);
      $l         = $this->set_size($this->get_len() << $this->isz);  // rodungim pana la dimensiunea de INT
      while($l > 0)
      {
        $l -= $elem_size;
        if($val != substr($this->data, $l, $elem_size))
        {
           $l = $this->set_size($l+$elem_size);
           return $l >> $this->isz;
        }
      }
      $this->data = ''; // trim all the INTs!
      return 0;
   }

   function ltrim_byte($val)
   {
      $val = chr((int)$val & BYTE_MASK);
      $l = $this->get_size();
      while($l--) if($val != $this->data[$l])
         return $this->set_size($l+1); // Atentie! NU e lungimea liste, ci a datelor
      $this->data = ''; // trim all the bytes!
      return 0;
   }
   /*------------------------------------------------------------------------*/
    function cmp_bin($i, $j)
    {
       $s = 1 << $this->isz;
       return strcmp(strrev(substr($this->data, $i, $s)),
                     strrev(substr($this->data, $j, $s)));
    }

    function swap_bin($i, $j) // ??? nu seteaza flagul $changed !
    {
       $sz = 1 << $this->isz;
       while($sz--) { $ch = $this->data[$i+$sz]; $this->data[$i+$sz] = $this->data[$j+$sz]; $this->data[$j+$sz] = $ch; }
    }
   /*------------------------------------------------------------------------*/
   /*! Obtine numarul INT de pe pozitia $idx.
    *  Daca $idx < 0, se indexseaza de la sfarsit.
    */
   function get_int($idx=0)
   {
      $l = $this->get_len();
      if($l <= $idx) return false;
      if($idx < 0) {
         $idx += $l;
         if($idx < 0) return false;
      }
      return $this->get_int_s($idx);
   }

   function get_int_($idx=0)
   {
      return binstr2int($this->data, $idx << $this->isz, 1 << $this->isz);
   }

   /// Obtine numarul INT de pe pozitia $idx, pastrand semnul numarului.
   function get_int_s($idx=0)
   {
      return bs2int(substr($this->data, $idx << $this->isz, 1 << $this->isz));
   }

   /*! Seteaza numarul $val pe pozitia $idx.
    *  Daca $idx < 0, se indexseaza de la sfarsit.
    */
   function set_int($val, $idx=0)
   {
      $b = int2bs($val, 1 << $this->isz);
      $this->set_bin($b, $idx); // se foloseste set_bin() pentru setarea $this->changed
      return $val;
   }
   /*------------------------------------------------------------------------*/
   /*!
    * Ataseaza un numar intreg la lista.
    * @return: Numarul de elemente INT.
    */
   function push($val)
   {
      return $this->append_bin(int2bs($val, 1 << $this->isz)) >> $this->isz;
   }

   /*! Extrage ultimul intreg din lista.
    *  @return: Ultimul element sau FALSE, daca lista e goala
    */
   function pop()
   {
      $l = strlen($this->data);
      if(!$l) return false;
      $l = (($l-1) >> $this->isz) << $this->isz;
      $r = binstr2int($this->data, $l, $this->isz);
      $this->data = substr($this->data, 0, $l);
      $this->changed = -1;
      return $r;
   }

   /*!
    * Ataseaza un octet la datele listei.
    * $val este valoarea octetului.
    * @return: Pozitia $val.
    */
   function push_byte($val)
   {
      return $this->append_bin(chr($val));
   }

   /*! Extrage ultimul octet din datele listei.
    *  @return: Valoarea ultimului octet sau FALSE, daca datele lipsesc
    */
   function pop_byte()
   {
      $l = strlen($this->data);
      if(!$l) return false;
      $r = ord($this->data[$l-1]);
      $this->data = substr($this->data, 0, $l-1);
      $this->changed = -1;
      return $r;
   }
   /*------------------------------------------------------------------------*/
   /*! Obtine octetul de pe pozitia $idx.
    *  Daca $idx < 0, se indexseaza de la sfarsit.
    */
   function get_byte($idx=0)
   {
      $b = $this->data[$idx]; // string in PHP verifica daca $idx < strlen($this->data)
      if($b === '') return 0;
      return ord($b);
   }

   /*! Seteaza octetul $val pe pozitia $idx.
    *  Daca $idx < 0, se indexseaza de la sfarsit.
    */
   function set_byte($val, $idx=0)
   {
      $val = chr($val[0]);
      $l = $this->get_size();
      if($idx<0) { if( ($idx += $l) < 0) return false; } else
      if($idx>=$l) $l = $this->set_size($idx+1);
      if(!$this->changed) $this->changed = $val !== $this->data[$idx];
      $this->data[$idx] = $val;
      return $val;
   }
   /*------------------------------------------------------------------------*/
   /// Obtine reprezentarea secventei de biti a datelor in ordinea in care sunt in memorie
   protected function get_bits()
   {
      $l = strlen($this->data);
      if(!$l) return ''; else
      {
         $r = '';
         for($i=0; $i<$l; $i++)
         {
            $b = ord($this->data[$i]);
            for($j=0; $j<8; $j++) { $r .= 1 & $b; $b >>= 1; }
            $r .= ' ';
         }
         return $r;
      }
   }

   /// Transforma reprezentarea binara a datelor in insasi valoarea binara
   protected function set_bits($val)
   {
      $val = str_replace(' ', '', $val);
      $i   = strlen($val);
      $r   = $i &  7;  // restul impartirii la 8
      $q   = $i & ~7;  // $i - $r
      $dt  = &$this->data;
      $dt  = '';
      for($i=0; $i<$q; $i+=8) {
         $b = 0;
         for($j=$i+7; $j>=$i; $j--) {
            $b <<= 1;
            $b |= $val[$j] != '0';
         }
         $dt .= chr($b);
      }
      if($r) {
        $i = $q + $r;
        $b = 0;
        while($i-->$q) {
           $b <<= 1;
           $b |= $val[$i] != '0';
        }
        $dt .= chr($b);
      }
      return $this->get_bits();
   }
   /*------------------------------------------------------------------------*/
   /*! @return: Lista de numere intregi corespunzatoare continutului binar al obiectului
    */
   protected function get_ints()
   {
      $l = $this->get_size();
      $r = array();
      $s = 1 << $this->isz;
      for($i=0; $i<$l; $i+=$s) $r[$i] = binstr2int($this->data, $i, $s);
      return $r;
   }

   /*! Atribuie obiectului o lista de numere intregi.
    *  @return: Dimensiunea datelor binare in octeti
    */
   protected function set_ints($array)
   {
      $this->data = '';  // pentru orice eventualitate, eliberam memoria
      $s = 1 << $this->isz;
      foreach($array as &$i) $i = int2bs((int)$i, $s);
      $this->data = implode('', $array);
      $this->changed = -1; // salveaza toata lista la distrugere
      return strlen($this->data);
   }
   /*------------------------------------------------------------------------*/
   /*!
    * Extrage o parte din numerele INT.
    *
    * $offset: Daca $offset este ne-negativ, secventa va incepe cu acea pozitie.
    *          Daca $offset este negativ, secventa va incepe cu atat de la sfarsitul listei.
    *
    * $length: Daca e dat si e pozitiv, atunci secventa va contine atatea elemente.
    *          Daca e dat si e negativ, atunci secventa se va opri cu atatea elemente
    *          de la sfarsitul listei.
    *          Daca este omis, atunci secventa va contine tot de la $offset pana la
    *          sfarsitul listei.
    *
    * @return: array(INT, INT, ...)
    */
   function slice($offset /*[, $length]*/)
   {
      $l = $this->get_len();
      if(!$l || $l <= $offset) return array();
      if($offset<0) $offset = $offset % $l + $l;
      if(func_num_args() > 1)
      {
         $len = func_get_arg(1);
         if($len < 0) $len += $l; else   // $len < 0
         {
            if($len==0) return array();
            $len += $offset;             // $len >= 0
            if($len > $l) $len = $l;
         }
      }
      else $len = $l;
      $r = array();
      $s = 1 << $this->isz;
      for($i=$offset; $i<$len; $i++) $r[$i] = binstr2int($this->data, $i << $this->isz, $s);
      return $r;
   }
   /*------------------------------------------------------------------------*/
   /*!
    * Returneaza lista de numere separate prin $sep ca text.
    *
    * $offset: Daca $offset este ne-negativ, secventa va incepe cu acea pozitie.
    *          Daca $offset este negativ, secventa va incepe cu atat de la sfarsitul listei.
    *
    * $len:    Daca e dat si e pozitiv, atunci secventa va contine atatea elemente.
    *          Daca e dat si e negativ, atunci secventa se va opri cu atatea elemente
    *          de la sfarsitul listei.
    *          Daca este omis, atunci secventa va contine tot de la $offset pana la
    *          sfarsitul listei.
    *
    * @return: INT$sepINT$sep...INT)
    */
   function implode($sep='|', $offset=0/*[, $len]*/)
   {
      $l = $this->get_len();
      if(!$l || $l <= $offset) return false;
      if($offset<0) $offset = $offset % $l + $l;
      if(func_num_args() > 2) {
         $len = func_get_arg(2);
         if($len < 0) $len += $l; else {  // $len < 0
            if($len==0) return false;
            $len += $offset;             // $len >= 0
            if($len > $l) $len = $l;
         }
      }
      else $len = $l;
      $r = '';
      $s =  1 << $this->isz;
      $offset <<= $this->isz;
      $len    <<= $this->isz;
      $i = $offset;
      for(;;) {
        $r .= binstr2int($this->data, $i, $s);
        if(($i += $s) >= $len) break;
        $r .= $sep;
      }
      return $r;
   }
   /*------------------------------------------------------------------------*/
   /// Afiseaza lista de numere folosind separatorul $sep.
   function print_($sep=', ')
   {
      $l = $this->get_size();
      $s = 1 << $this->isz;
      $l -= $s;
      for($idx=0; $idx < $l; $idx += $s)
         echo binstr2int($this->data, $idx, $s) . $sep;
      if($l>$s) echo binstr2int($this->data, $idx, $s);
   }
   /// Afiseaza lista de numere folosind separatorul $sep.
   function print_s($sep=', ')
   {
      $l = $this->get_size();
      $s = 1 << $this->isz;
      $l -= $s;
      for($idx=0; $idx < $l; $idx += $s)
         echo bs2int(substr($this->data, $idx, $s)) . $sep;
      if($l>$s) echo bs2int(substr($this->data, $idx, $s));
   }
   /*------------------------------------------------------------------------*/
   function get_first()     { return $this->get_int(0); }
   function set_first($val) { return $this->set_int($val, 0); }
   function get_last()      { return $this->get_int($this->get_len()-1); }
   function set_last($val)  { return $this->set_int($val, $this->get_len()-1); }

   function get_current()     { return (int)$this->cursor<0 ? false : $this->get_int((int)$this->cursor); }
   function set_current($val) { return (int)$this->cursor<0 ? false : $this->set_int($val, (int)$this->cursor); }

   function get_reset()       { return $this->get_int($this->cursor = 0); }
   function set_reset($val)   { return $this->set_int($val, $this->cursor = 0); }

   function get_end()
   {
      $l = $this->get_len();
      $this->cursor = $l-1;
      if(!$l) return false;
      return $this->get_int($this->cursor);
   }
   function set_end($val)
   {
      $l = $this->get_len();
      $this->cursor = $l-1;
      return $this->set_int($val, $this->cursor);
   }

   function get_prev()
   {
      $this->cursor--;
      if($this->cursor >= 0)
         return $this->get_int((int)$this->cursor);
      $this->cursor++;
      return false;
   }
   function set_prev($val)
   {
      $this->cursor--;
      if($this->cursor >= 0)
         return $this->set_int($val, (int)$this->cursor);
      $this->cursor++;
      return false;
   }

   function get_next()
   {
      $this->cursor++;
      if($this->cursor < $this->get_len())
          return $this->get_int($this->cursor);
      $this->cursor--;
      return false;
   }
   function set_next($val)
   {
      $this->cursor++;
      return $this->set_int($val, (int)$this->cursor);
   }

   /*!
    * @return: Perechea curenta de keie si valoare din lista de INT si avanseaza cursorul intern.
    */
   function get_each()
   {
      if($this->cursor >= $this->get_len()) return false;
      $this->cursor++;
      $r = array($this->cursor, $this->get_int((int)$this->cursor));
      $r['key'] = $r[0];
      $r['value'] = $r[1];
      return $r;
   }
   function set_each($val)
   {
      if(is_array($val))
      {
         $this->cursor = isset($val['key']) ? $val['key'] : $val[0];
         $val = isset($val['value']) ? (int)$val['value'] : (int)$val[1];
         $this->cursor++;
         return $this->set_int($val, (int)$this->cursor-1);
      }
      $this->cursor++;
      return $this->set_int($val, (int)$this->cursor);
   }
   /*------------------------------------------------------------------------*/
   /*!
    *  Parcurge lista de numere si cauta elementul cu valoare minima.
    *  @return: array(pos, val), sau FALSE, daca lista e vida.
    *  Nota: Gaseste prima aparitie a elementului minim.
    */
   function min()
   {
      $l = $this->get_len();
      if(!$l) return false;
      $m = $this->get_int_(0);
      $p = 0;
      for($i=1; $i<$l; $i++)
      {
        $v = $this->get_int_($i);
        if($v < $m) { $m = $v; $p = $i; }
      }
      return array($p, $m); // pozitia si valoarea
   }
   /*!
    *  Parcurge lista de numere si cauta elementul cu valoare maxima.
    *  @return: array(pos, val), sau FALSE, daca lista e vida.
    *  Nota: Gaseste ultima aparitie a elementului maxim.
    */
   function max()
   {
      $l = $this->get_len();
      if(!$l) return false;
      $l--;
      $m = $this->get_int_($l);
      $p = $l;
      while($l--)
      {
        $v = $this->get_int_($l);
        if($v > $m) { $m = $v; $p = $l; }
      }
      return array($p, $m); // pozitia si valoarea
   }
   function min_pos() { if($v = $this->min()) return $v[0]; return false; }
   function max_pos() { if($v = $this->max()) return $v[0]; return false; }
   function min_val()
   {
      if( !($l = $this->get_len()) ) return false;
      $m = $this->get_int_(0);
      for($i=1; $i<$l; $i++) if(($v = $this->get_int_($i)) < $m) $m = $v;
      return $m;
   }
   function max_val()
   {
      if( !($l = $this->get_len()) ) return false;
      $l--;
      $m = $this->get_int_($l);
      while($l--) if(($v = $this->get_int_($l)) > $m) $m = $v;
      return $m;
   }
   /*------------------------------------------------------------------------*/
   /*!
    * Cauta $nr in lista interna de nr prime.
    * Returneaza pozitia din lista, sau false, daca nu-l gaseste.
    *
    * O($nr)
    *
    * Daca lista e sortata, folositi $this->search() in loc pentru performanta.
    *
    * Atentie!
    *   Primul nr din lista e pe pozitia 0 !== false
    */
    function find($nr, $offset=0)
    {
       $l = $this->get_size();
       if(!$l) return false;        // lista e vida
       $s = 1 << $this->isz;
       $offset <<= $this->isz;
       $nr = int2bs($nr, $s);
       $s--;
       for(;;)
       {
         $offset = strpos($this->data, $nr, $offset);
         if( $offset === false ) return false; // not found
         if( !($offset & $s) )   return $offset >> $this->isz;
       }
    }
   /*------------------------------------------------------------------------*/
   /*!
    * Cauta $nr in lista interna de nr prime. (Binary search)
    * Returneaza pozitia din lista, sau false, daca nu-l gaseste.
    *
    * Lista trebuie sa fie sortata crescator,
    * in caz contrar rezultatul se considera nedefinit.
    * Pentru a cauta un element in lista nesortata, folositi $this->find()
    *
    * O(log($nr))
    *
    * Atentie!
    *   Primul nr din lista e pe pozitia 0 !== false
    */
    function search($nr, $b=0)
    {
       $l = $this->get_size();
       if(!$l) return false;        // lista e vida
       $b <<= $this->isz;
       if($b >= $l) return false;   // cautare in afara listei
       // Algoritmul injumatatirii.
       $s = 1 << $this->isz;
       $nr = strrev(int2bs($nr, $s));
       $e = $l-$s;
       do {
          $p  = (($e + $b) >> 1); // calcularea pivotului
          $p &= ~($s-1);          // adjustarea pivotului pe dimensiunea INT
          $cmp = strcmp($nr, strrev(substr($this->data, $p, $s)));
          if( $cmp < 0 ) { $e = $p - $s; } else // $this->get_int($p) <= $nr
          if( $cmp > 0 ) { $b = $p + $s; } else // $nr <= $this->get_int($p)
          return $p >> $this->isz;              // $this->get_int($p) <= $nr && $nr <= $this->get_int($p)
       } while( $b <= $e )
       ;
       return false;
    }

   /*!
    * Cauta cel mai mic nr din lista mai mare sau egal cu $nr.
    * Daca exista, returneaza pozitia lui.
    * Daca nu exista, returneaza FALSE.
    */
   function search_ceil($nr, $b=0)
   {
       $l = $this->get_size();
       if(!$l) return false;        // lista e vida
       $b <<= $this->isz;
       if($b >= $l) return false;   // cautare in afara listei

       // Algoritmul injumatatirii, cu un mic specific.
       $s = 1 << $this->isz;
       $nr = strrev(int2bs($nr, $s));
       $e = $l-$s;
       do
       {
          $p  = (($e + $b) >> 1) & ~($s-1); // calcularea pivotului
          $cmp = strcmp($nr, strrev(substr($this->data, $p, $s)));
          if( $cmp < 0 ) $e = $p - $s; else
          {
            if( $cmp == 0 ) return $p >> $this->isz;
            $p += $s;
            if( 0 < strcmp($nr, strrev(substr($this->data, $p, $s))) ) $b = $p; else
            return $p >> $this->isz;
          }
       } while( $b <= $e )
       ;
       return false;
   }

   /*!
    * Cauta cel mai mare nr din lista mai mic sau egal cu $nr
    * Daca exista, returneaza pozitia lui.
    * Daca nu exista, returneaza pozitia ultimului element.
    */
   function search_floor($nr, $b=0)
   {
       $l = $this->get_size();
       if(!$l) return false;        // lista e vida
       $b <<= $this->isz;
       if($b >= $l) return false;   // cautare in afara listei

       // Algoritmul injumatatirii, cu un mic specific.
       $s = 1 << $this->isz;
       $nr = strrev(int2bs($nr, $s));
       $e = $l-$s;
       do
       {
          $p  = (($e + $b) >> 1) & ~($s-1); // calcularea pivotului
          $cmp = strcmp($nr, strrev(substr($this->data, $p, $s)));
          if( $cmp < 0 ) $e = $p - $s; else
          {
            if( $cmp == 0 ) return $p >> $this->isz;
            $cmp = strcmp($nr, strrev(substr($this->data, $p+$s, $s)));
            if( $cmp > 0 ) $b = $p + $s; else
            {
              if( $cmp == 0 ) $p += $s;
              return $p >> $this->isz;
            }
          }
       } while( $b <= $e )
       ;
       return ($l-1) >> $this->isz; // pozitia ultimului element din lista.
   }
   /*------------------------------------------------------------------------*/
    function swap($i, $j)
    {
       $sz = 1 << $this->isz;
       $i <<= $this->isz;
       $j <<= $this->isz;

       while($sz--)
       {
         $ch = $this->data[$i+$sz];
         $this->data[$i+$sz] = $this->data[$j+$sz];
         $this->data[$j+$sz] = $ch;
       }
    }
   /*------------------------------------------------------------------------*/
    /*! Compara numerele de pe pozitia $i si $j.
     *  @return: <0, 0 sau >0, corespunzator pentru <, == sau >
     */
    function cmp_int($i, $j)
    {
       $s = 1 << $this->isz;
       return strcmp(strrev(substr($this->data, $i << $this->isz, $s)),
                     strrev(substr($this->data, $j << $this->isz, $s)));
    }
   /*------------------------------------------------------------------------*/
    /*! Sorteaza lista de numere folosind algoritmul Quick Sort.
     *
     *  Daca $sort_dir >= 0, se sorteaza crescator.
     *  Daca $sort_dir <  0, se sorteaza descrescator.
     */
    function sort($sort_dir=1)
    {
      $l = $this->get_len();
      if(func_num_args()>1) {
         $b = func_get_arg(0);
         $e = func_num_args()>2 ? func_get_arg(0) : $l-1;
      } else {
         $b = 0;
         $e = $l-1;
      }
      global $qs_cals;
      $qs_cals = 0;
      $this->sorted = $sort_dir;
      $ch = $this->changed;
      $this->changed = 0;
      $this->qsort_($b <<= $this->isz, $e <<= $this->isz);
      $r = $this->changed;
      $this->changed = $ch | ($this->changed ? -1 : 0);
      return $r;
    }

    // Aceasta functie se foloseste de catre sort()
    private function qsort_($b, $e)
    {
      if($b >= $e) return ;
      global $qs_cals;  $qs_cals++;
      // Functia se apeleaza de log($n) ori, unde $n este nr de elemente de sortat.
      // log(1000) = 10; log(1000000) = 20; log(1000000000) = 30; ...
      $q = 1 << $this->isz;
      $p = (($b+$e) >> 1) & ~($q-1);
//       for($i=$b; $i<$e; $i+=$q)
      $i = $b;
      $j = $e;
      for(;;) { // comparatia s-ar putea face intr-o functie speciala, dar pu viteza o lasam aici
        while( ($r = strcmp(strrev(substr($this->data, $i, $q)), strrev(substr($this->data, $p, $q)))) &&
               (($r ^ $this->sorted) & INT_SIGN) ) $i += $q;
        while( ($r = strcmp(strrev(substr($this->data, $p, $q)), strrev(substr($this->data, $j, $q)))) &&
               (($r ^ $this->sorted) & INT_SIGN) ) $j -= $q;
        if ($i <= $j) $this->swap_bin($i, $j); else break;
        $i += $q;
        $j -= $q;
        $this->changed++;
//         if($this->changed >> 8) $this->save();
      }
      unset($p); unset($q); unset($r); // eliberam cat mai curant memoria (cauza - recursie)
      $this->qsort_($b, $j);
      unset($b); unset($j); // eliberam cat mai curant memoria (cauza - recursie)
      $this->qsort_($i, $e);
    }
   /*------------------------------------------------------------------------*/
    function sort1($sort_dir=1)
    {
      $l = $this->get_len();
      if(func_num_args()>1) {
         $b = func_get_arg(0);
         $e = func_num_args()>2 ? func_get_arg(0) : $l-1;
      } else {
         $b = 0;
         $e = $l-1;
      }
      global $qs_cals;
      $qs_cals = 0;
      $this->sorted = $sort_dir;
      $ch = $this->changed;
      $this->changed = 0;
      $this->qsort_($b <<= $this->isz, $e <<= $this->isz);
      $r = $this->changed;
      $this->changed = $ch | ($this->changed ? -1 : 0);
      return $r;
    }
    private function qsort1_($b, $e)
    {
      if($b >= $e) return ;
      global $qs_cals;  $qs_cals++;
      // Functia se apeleaza de log($n) ori, unde $n este nr de elemente de sortat.
      // log(1000) = 10; log(1000000) = 20; log(1000000000) = 30; ...
      $i = $b;
      $j = $e;
      $q = 1 << $this->isz;
      $p = (($b+$e) >> 1) & ~($q-1);
      for(;;) { // comparatia s-ar putea face intr-o functie speciala, dar pu viteza o lasam aici
        while( ($r = strcmp(strrev(substr($this->data, $i, $q)), strrev(substr($this->data, $p, $q)))) &&
               (($r ^ $this->sorted) & INT_SIGN) ) $i += $q;
        while( ($r = strcmp(strrev(substr($this->data, $p, $q)), strrev(substr($this->data, $j, $q)))) &&
               (($r ^ $this->sorted) & INT_SIGN) ) $j -= $q;
        if ($i <= $j) $this->swap_bin($i, $j); else break;
        $i += $q;
        $j -= $q;
        $this->changed++;
//         if($this->changed >> 8) $this->save();
      }
      unset($p); unset($q); unset($r); // eliberam cat mai curant memoria (cauza - recursie)
      $this->qsort_($b, $j);
      unset($b); unset($j); // eliberam cat mai curant memoria (cauza - recursie)
      $this->qsort_($i, $e);
    }
   /*------------------------------------------------------------------------*/
}

// Nu se recomanda folosirea acestor functii pentru liste mari!
function binstr2ints($str) { $o=new PkInts($str, true); return $o->ints; }
function ints2binstr($array) { $o = new PkInts(); $o->ints = $array; return $o->data; }

?>