|
|
Baner
Lista
|
Conținut
PkInts.phpx /*! ------------------------------------------------------------------------ * * 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; }Aici acumulez programe şi algoritmi interesanti alcătuiţi de mine (cu mici excepţii) pe parcursul studierii unor limbaje de programare. Cea mai mare parte din ele sunt realizate în Pascal. Nu am scopul creării unui curs specializat sau a descrierii detaliate a anumitor limbaje, ci doar prezint informaţii utile, plus ceva exemple interesante...
Răsfoitorul de fișiere (File Browser):Codul sursă al programelor este organizat în mape şi fişiere. Paginile care conțin cod sursă de programe de regulă au un răsfoitor de fișiere în partea stangă a paginii reprezentat de un bloc cu titlul „File Browser”. Pentru a vizualiza un program sau conţinutul unei mape, faceţi click pe numele fişierului / mapei. Dacă fişierul nu este textual, el se va descărca automat, iar dacă este textual, conținutul lui se va afișa într-un bloc pe centrul paginii. Pentru a descărca un fişier, faceţi click pe dimensiunea (size) lui.
Căutare
|
Limba / Language
Login
Submenu
|