2e2v28/8202014_challenge_176_hard_spreadsheet_developer

gistfile1.php

<?php


/**
 * Class Cell
 * Converts string into col/row representation.
 */
class Cell {
    public $col = 0;
    public $row = 0;

    public function __construct($cell) {
        if (is_string($cell)) {
            $this->parseCellStr($cell);
        }
    }

    private function parseCellStr($cell) {
        if (preg_match('/([a-z]*)([0-9]*)/i', $cell, $match) == 1 && count($match) == 3) {
            $colTmp = $match[1];
            $rowTmp = $match[2];
            $this->parseColStr($colTmp);
            $this->parseRowStr($rowTmp);
            return;
        }
        throw new Exception('Illegal Cell string: ' . $cell);
    }

    private function parseColStr($str) {
        $str = strtoupper($str);
        $this->col = 0;
        $digits = strlen($str);
        for ($i = 0; $i < $digits; $i++) {
            $c = ord($str[$i]) - ord('A');
            $this->col += $c * pow(26, $digits - $i - 1);
        }
    }

    private function parseRowStr($original) {
        $this->row = (int)$original - 1;
    }
}

/**
 * Class CellSelection
 * Parses abstract selection string into single CellRange
 */
class CellSelection implements Countable {
    protected $cellRange = null;

    public function __construct($str) {
        $this->cellRange = new CellRange();

        $complements = explode('~', $str);
        $add = true;
        foreach ($complements as $complement) {
            if ($add) {
                $this->cellRange->addRange($this->parseChunk($complement));
                $add = false;
            } else {
                $this->cellRange->removeRange($this->parseChunk($complement));
                $add = true;
            }
        }
    }

    public function count() {
        return $this->cellRange->count();
    }

    public function __toString() {
        $s = $this->cellRange->count() . "\n";
        $s .= $this->cellRange;
        return $s;
    }

    public function apply($callable) {
        $this->cellRange->apply($callable);
    }

    protected function parseChunk($str) {
        $cellRange = new CellRange();
        $ranges = explode('&', $str);
        foreach ($ranges as $addRanges) {
            $cells = explode(':', $addRanges);
            if (count($cells) > 1) {
                $cellRange->addRange(CellRange::create(new Cell($cells[0]), new Cell($cells[1])));
            } else {
                $cellRange->addRange(CellRange::create(new Cell($cells[0])));
            }
        }
        return $cellRange;
    }
}

/**
 * Class CellRange
 * Hold collection of ColumnRanges and adds/removes other CellRange
 */
class CellRange implements Countable {
    private $columns = [];

    public static function create(Cell $startCell, Cell $endCell = null) {
        $cellRange = new CellRange();
        $cellRange->columns = ColumnRange::create($startCell, $endCell);
        return $cellRange;
    }

    public function count() {
        $count = 0;
        foreach ($this->columns as $colArray) {
            foreach ($colArray as $c) {
                $count += $c->count();
            }
        }
        return $count;
    }

    public function __toString() {
        $s = '';
        foreach ($this->columns as $colArray) {
            foreach ($colArray as $col) {
                $s .= $col;
            }
        }
        return $s;
    }

    public function apply($callable) {
        foreach ($this->columns as $colArray) {
            foreach ($colArray as $col) {
                $col->apply($callable);
            }
        }
    }

    public function addRange(CellRange $range) {
        foreach ($range->columns as $col => $r) {
            if (!isset($this->columns[$col])) {
                $this->columns[$col] = $r;
            } else {
                $newColumnRanges = new SplObjectStorage();
                foreach ($this->columns[$col] as $colRange) {
                    foreach ($r as $newRange) {
                        $ret = $colRange->addColumnRange($newRange);
                        if ($ret === false && !isset($newColumnRanges[$newRange])) {
                            $newColumnRanges[$newRange] = 1;
                        } else {
                            $newColumnRanges[$newRange] = 0;
                        }
                    }
                }

                foreach ($newColumnRanges as $newRange) {
                    if ($newColumnRanges[$newRange]) {
                        $this->columns[$col][] = $newRange;
                    }
                }
            }
        }
        $this->sort();
        $this->coalesce();
    }

    public function removeRange(CellRange $range) {
        foreach ($range->columns as $col => $r) {
            if (!isset($this->columns[$col])) {
                // nothing to remove
            } else {
                $newColumnRanges = new SplObjectStorage();
                foreach ($this->columns[$col] as $colRange) {
                    foreach ($r as $newRange) {
                        $ret = $colRange->removeColumnRange($newRange);
                        if (is_array($ret)) {
                            foreach ($ret as $keep) {
                                $newColumnRanges->attach($keep);
                            }
                        } else if (is_object($ret)) {
                            $newColumnRanges->attach($ret);
                        }
                    }
                }
                $this->columns[$col] = [];
                foreach ($newColumnRanges as $newRange) {
                    $this->columns[$col][] = $newRange;
                }
            }
        }
        $this->sort();
        $this->coalesce();
    }

    protected function sort() {
        ksort($this->columns);
        foreach ($this->columns as &$values) {
            usort($values, array('ColumnRange', 'compareRange'));
        }
    }

    protected function coalesce() {
        foreach ($this->columns as $col => &$array) {
            if (is_array($array) && count($array) > 1) {
                for ($i = 0; $i < count($array) - 1; $i++) {
                    $tmp = $array[$i];
                    $ret = $tmp->addColumnRange($array[$i+1]);
                    if ($ret) {
                        array_splice($array, $i, 1);
                        return $this->coalesce();
                    }
                }
            }
        }
    }
}

/**
 * Class ColumnRange
 * A single ColumnRange is continuous and will modify itself based on adding and removing other ColumnRanges
 */
class ColumnRange implements Countable {
    protected $col = 0;
    protected $startRow = 0;
    protected $endRow = 0;

    /**
     * @param Cell $startCell
     * @param Cell $endCell
     * @return array|ColumnRange
     */
    public static function create(Cell $startCell, Cell $endCell = null) {
        if (!$endCell) {
            return [ $startCell->col => [ new ColumnRange($startCell) ] ];
        }

        $startCol = min($startCell->col, $endCell->col);
        $endCol = max($startCell->col, $endCell->col);

        $startRow = min($startCell->row, $endCell->row);
        $endRow = max($startCell->row, $endCell->row);
        $out = [];
        for ($i = $startCol; $i <= $endCol; $i++) {
            $t = new ColumnRange();
            $t->col = $i;
            $t->startRow = $startRow;
            $t->endRow = $endRow;
            $out[$i] = [$t];
        }

        return $out;
    }

    public function __construct(Cell $startCell = null, Cell $endCell = null) {
        if (!$startCell) {
            return $this;
        }

        if (!$endCell) {
            $this->col = $startCell->col;
            $this->startRow = $startCell->row;
            $this->endRow = $startCell->row;
            return $this;
        }

        if ($startCell->col != $endCell->col) {
            throw new Exception('ColumnRange must only contain single column cells.');
        }
        $this->startRow = min($startCell->row, $endCell->row);
        $this->endRow = max($startCell->row, $endCell->row);
        return $this;
    }

    public function count() {
        return $this->endRow - $this->startRow + 1;
    }

    public function __toString() {
        $s = '';
        for ($i = $this->startRow; $i <= $this->endRow; $i++) {
            $s .= $this->col . ', ' . $i . "\n";
        }
        return $s;
    }

    public function apply($callable) {
        for ($i = $this->startRow; $i <= $this->endRow; $i++) {
            $callable( $this->col , $i );
        }
    }

    /**
     * Returns ColumnRange if single range describes the combined range.
     * Returns false if non overlapping ranges (distinct ranges)
     *
     * Explicitly does not check for the same columns
     *
     * @param ColumnRange $range
     */
    public function addColumnRange(ColumnRange $range) {
        // non overlapping
        if ( ($this->endRow < $range->startRow - 1) || ($this->startRow - 1 > $range->endRow) ) {
            return false;
        }

        $this->startRow = min($this->startRow, $range->startRow);
        $this->endRow = max($this->endRow, $range->endRow);
        return $this;
    }

    /**
     * Returns false if removal completely overlaps original range
     * Returns ColumnRange if removal modifies range.
     * Returns Array<ColumnRange> if removal creates two ranges
     *
     * Explicitly does not check for identical
     *
     * @param ColumnRange $range
     */
    public function removeColumnRange(ColumnRange $range) {
        // completely overlaps
        if ($this->startRow >= $range->startRow && $this->endRow <= $range->endRow) {
            return false;
        }

        // non-overlapping
        if ($this->endRow < $range->startRow || $this->startRow > $range->endRow) {
            return $this;
        }

        // partial overlap from bottom
        if ($this->startRow >= $range->startRow) {
            $this->startRow = $range->endRow + 1;
            return $this;
        }

        // partial overlap from top
        if ($this->endRow <= $range->endRow) {
            $this->endRow = $range->startRow - 1;
            return $this;
        }

        // completely contained!
        $clone = clone $this;
        $this->endRow = $range->startRow -1;
        $clone->startRow = $range->endRow + 1;
        return [$this, $clone];
    }

    public static function compareRange(ColumnRange $a, ColumnRange $b) {
        if ($a->startRow < $b->startRow) {
            return -1;
        }
        return 1;
    }
}


/**
 * Class Spreadsheet
 * Stores data cells, and executes statements to read/update the data-structure.
 */
class Spreadsheet {
    private $data = [];

    /**
     * @param $op 
     * @return $this
     */
    public function execute($op) {
        $op = explode('=', $op);
        if (count($op) > 1) {
            $this->set($op[0], $op[1]);
            return $this;
        }

        $selection = new CellSelection($op[0]);
        if ($selection->count() == 1) {
            $selection->apply(function($col, $row) {
                echo $this->getCell($col, $row) . "\n";
            });
        } else  {
            $selection->apply(function($col, $row) {
                echo '(' . $col . ', ' . $row .') = ' . $this->getCell($col, $row) . "\n";
            });
        }

        return $this;
    }

    /**
     * Parses rvalue from string
     */
    public function evaluate($str) {
        if (is_numeric($str)) {
            return (double)$str;
        }

        if (stripos($str, 'sum') === 0) {
            $str = trim(substr($str, 3), '()');
            $sum = 0;
            $selection = new CellSelection($str);
            $selection->apply(function($col,$row) use (&$sum){
                $tmp = $this->getCell($col,$row);
                if ($tmp !== null) { $sum += $tmp; }
            });
            return $sum;
        }

        if (stripos($str, 'product') === 0) {
            $str = trim(substr($str, 7), '()');
            $prod = 0;
            $selection = new CellSelection($str);
            $selection->apply(function($col,$row) use (&$prod){
                $tmp = $this->getCell($col,$row);
                if ($tmp !== null) { $prod *= $tmp; }
            });
            return $prod;
        }

        if (stripos($str, 'average') === 0) {
            // note that the 'selection' count can differ from actual count because
            // unassigned cells will not be averaged in.
            $str = trim(substr($str, 7), '()');
            $sum = 0;
            $count = 0;
            $selection = new CellSelection($str);
            $selection->apply(function($col,$row) use (&$sum, &$count){
                $tmp = $this->getCell($col,$row);
                if ($tmp !== null) { $sum += $tmp; $count++; }
            });
            return ($sum / $count);
        }

        if ( ( $pos = stripos($str, '^') ) > 0) {
            $l = substr($str, 0, $pos);
            $r = substr($str, $pos + 1);
            return pow($this->evaluate($l), $this->evaluate($r));
        }

        if ( ( $pos = stripos($str, '/') ) > 0) {
            $l = substr($str, 0, $pos);
            $r = substr($str, $pos + 1);
            return ($this->evaluate($l) / $this->evaluate($r));
        }

        if ( ( $pos = stripos($str, '*') ) > 0) {
            $l = substr($str, 0, $pos);
            $r = substr($str, $pos + 1);
            return ($this->evaluate($l) * $this->evaluate($r));
        }

        if ( ( $pos = stripos($str, '-', 1) ) > 0) {
            $l = substr($str, 0, $pos);
            $r = substr($str, $pos);
            return ($this->evaluate($l) + $this->evaluate($r));
        }

        if ( ( $pos = stripos($str, '+', 1) ) > 0) {
            $l = substr($str, 0, $pos);
            $r = substr($str, $pos + 1);
            return ($this->evaluate($l) + $this->evaluate($r));
        }

        if ( ( $pos = stripos($str, '-') ) === 0) {
            $l = substr($str, 1);
            return -1 * $this->evaluate($l);
        }

        if ( ( $pos = stripos($str, '+') ) === 0) {
            $l = substr($str, 1);
            return $this->evaluate($l);
        }

        $cell = new Cell($str);
        return $this->getCell($cell->col, $cell->row);
    }

    public function getCell($col, $row) {
        if (isset($this->data[$col]) && isset($this->data[$col][$row])) {
            return $this->data[$col][$row];
        }
        return null;
    }

    public function setCell($col, $row, $val) {
        $this->data[$col][$row] = $val;
        return $this;
    }

    public function set($lvalue, $rvalue) {
        $rvalue = $this->evaluate($rvalue);
        $lvalueRange = new CellSelection($lvalue);
        $lvalueRange->apply(function($col,$row) use ($rvalue) {
            $this->setCell($col, $row, $rvalue);
        });
        return $this;
    }
}