From 5177a1b50e47e7d62a66aba9565580af3abf15dd Mon Sep 17 00:00:00 2001 From: Florent Bruneau Date: Sun, 31 Aug 2008 21:34:46 +0200 Subject: [PATCH] More tools around PlIterator: -> iterator sorter: PlIteratorUtils::sort($it, $callback) -> iterator merger: PlIteratorUtils::merger(array($it1, $it2), $callback) Move usage of PlArrayIterator to PlIteratorUtils::fromArray($array). Signed-off-by: Florent Bruneau --- classes/plheap.php | 75 ++++++++++++ classes/pliterator.php | 14 +++ .../{plarrayiterator.php => pliteratorutils.php} | 132 +++++++++++++++++++++ 3 files changed, 221 insertions(+) create mode 100644 classes/plheap.php rename classes/{plarrayiterator.php => pliteratorutils.php} (51%) diff --git a/classes/plheap.php b/classes/plheap.php new file mode 100644 index 0000000..7848e9c --- /dev/null +++ b/classes/plheap.php @@ -0,0 +1,75 @@ +comparator = $comparator; + } + + public function pop() + { + if (empty($this->content)) { + return null; + } + return array_shift($this->content); + } + + public function push($elt) + { + $start = 0; + $end = count($this->content); + + while ($start < $end) { + $middle = floor(($start + $end) / 2); + $comp = call_user_func($this->comparator, $elt, $this->content[$middle]); + if ($comp < 0) { + $end = $middle; + } else if ($comp > 0) { + $start = $middle + 1; + } else { + array_splice($this->content, $middle, 0, array($elt)); + return; + } + } + array_splice($this->content, $start, 0, array($elt)); + } + + public function count() + { + return count($this->content); + } + + public function iterator() + { + return PlIterator::fromArray($this->content); + } +} + +// vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: +?> diff --git a/classes/pliterator.php b/classes/pliterator.php index 0b5f254..47f809f 100644 --- a/classes/pliterator.php +++ b/classes/pliterator.php @@ -19,11 +19,25 @@ * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * ***************************************************************************/ +/** An iterator. + */ interface PlIterator { + /** Fetch and return the next element of the iterator. + * If no more element is available, return null. + */ public function next(); + + /** Return the number of element of the iterator. + */ public function total(); + + /** True if the current element is the first element. + */ public function first(); + + /** True if the current element is the last element. + */ public function last(); } diff --git a/classes/plarrayiterator.php b/classes/pliteratorutils.php similarity index 51% rename from classes/plarrayiterator.php rename to classes/pliteratorutils.php index d249b8a..6d995a6 100644 --- a/classes/plarrayiterator.php +++ b/classes/pliteratorutils.php @@ -19,6 +19,51 @@ * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * ***************************************************************************/ +class PlIteratorUtils +{ + /** Build an iterator over an array. + * @param array The array. + * @param depth The depth of iteration. + * @return an iterator that return entries in the form + * array(key => array(0 => key_for_depth0 [, 1 => key_for_depths1, ...]), + * value => the value); + */ + public static function fromArray(array $array, $depth = 1) + { + return new PlArrayIterator($array, $depth); + } + + + /** Sort an iterator using the given sort callback. + * @param iterator The iterator to sort. + * @param callback The callback for comparison. + * @return a new iterator with the entries sorted. + */ + public static function sort(PlIterator $iterator, $callback) + { + $heap = new PlHeap($callback); + while ($item = $iterator->next()) { + $heap->push($item); + } + return $heap->iterator(); + } + + + /** Merge several iterator into a unique one. + * @param iterators Array of iterators. + * @param callback The callback for comparison. + * @param sorted Tell wether the iterators are already sorted using the given callback. + * @return an iterator. + */ + public static function merge(array $iterators, $callback, $sorted = true) + { + return new PlMergeIterator($iterators, $callback, $sorted); + } +} + + +/** Iterates over an array. + */ class PlArrayIterator implements PlIterator { private $array; @@ -121,5 +166,92 @@ class PlArrayIterator implements PlIterator } } + +/** Iterator that return the result of a merge of several iterators. + */ +class PlMergeIterator implements PlIterator +{ + /* The heap is field with entries with the form: + * array('it' => id of the iterator this entry come from, + * 'value' => value of the entry). + */ + private $heap; + private $preComputed = false; + private $comparator; + private $iterators; + private $_total; + private $pos; + + public function __construct(array $iterators, $callback, $sorted = true) + { + $this->heap = new PlHeap(array($this, 'compare')); + $this->_total = 0; + $this->comparator = $callback; + if ($sorted) { + $this->iterators = $iterators; + foreach ($this->iterators as $key => &$it) { + $this->_total += $it->total(); + $item = $it->next(); + if (!is_null($item)) { + $this->heap->push(array('it' => $key, 'value' => $item)); + } + } + } else { + $this->preComputed = true; + foreach ($iterators as $key => &$it) { + $this->_total += $it->total(); + while (!is_null($item = $it->next())) { + $this->heap->push(array('it' => $key, 'value' => $item)); + } + } + } + $this->pos = 0; + } + + /** Compare two entries of the heap using the comparator of the user. + */ + public function compare($a, $b) + { + $cp = call_user_func($this->comparator, $a['value'], $b['value']); + if ($cp == 0) { + return $a['it'] - $b['it']; + } + return $cp; + } + + public function total() + { + return $this->_total; + } + + public function next() + { + ++$this->pos; + $entry = $this->heap->pop(); + if (is_null($entry)) { + return null; + } + if ($this->preComputed) { + return $entry['value']; + } + $it = $entry['it']; + $item = $this->iterators[$it]->next(); + if (!is_null($item)) { + $this->heap->push(array('it' => $it, 'value' => $item)); + } + return $entry['value']; + } + + public function last() + { + return $this->heap->count() == 0; + } + + public function first() + { + return $this->pos == 1; + } +} + // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: ?> -- 2.1.4