Created
December 21, 2011 01:39
-
-
Save dtalley/1504149 to your computer and use it in GitHub Desktop.
PHP Data Tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| /** | |
| * Useful for keeping track of a tree-like | |
| * collection of data, for templates, API | |
| * returns, and accessing it with simple, | |
| * powerful paths, much like a file structure | |
| * or XPath. | |
| */ | |
| class DataTree { | |
| private $_elements = array(); | |
| private $_values = array(); | |
| private $_level = 0; | |
| function __construct( $level = 0 ) { | |
| $_level = $level; | |
| } | |
| function __destruct() {} | |
| /** | |
| * Create a valid path through this | |
| * DataTree object. If the path doesn't | |
| * already exist, create it. If the | |
| * destination node already exists, fork | |
| * the tree at that point and create a new | |
| * path. | |
| * @param $path The path string to create | |
| */ | |
| public function start( $path ) { | |
| //If $path is not a string, somebody screwed up | |
| if( !is_string( $path ) ) { | |
| return NULL; | |
| } | |
| //If $path is empty, we've arrived at our destination | |
| if( strlen( $path ) === 0 ) { | |
| return $this; | |
| } | |
| $this->parse( $path, $name, $filters ); | |
| //If the requested element doesn't exist, create it | |
| if( !isset( $this->_elements[$name] ) ) { | |
| $this->_elements[$name] = array(); | |
| } | |
| /** | |
| * If there's already a value with the specified | |
| * name, delete it, because it will be | |
| * inaccessible anyway. | |
| */ | |
| if( isset( $this->_values[$name] ) ) { | |
| trigger_error( | |
| "Overwrote data value with data element.", | |
| E_USER_WARNING | |
| ); | |
| unset( $this->_values[$name] ); | |
| } | |
| /** | |
| * If we're at our destination, we have to fork | |
| * the tree and create a new path. Otherwise, | |
| * if we're not at our destination but the | |
| * requested path doesn't exist, fork the tree | |
| * to create it. | |
| */ | |
| if( | |
| ( strlen( $path ) == 0 && $total_filters == 0 ) || | |
| count( $this->_elements[$name] ) == 0 | |
| ) { | |
| $this->_elements[$name][] = new DataTree( $this->_level+1 ); | |
| } | |
| $elements = $this->elements( $name, $filters ); | |
| $total = count( $elements ); | |
| return $elements[$total-1]->start( $path ); | |
| } | |
| /** | |
| * Store a value by name within this tree. | |
| */ | |
| public function store( $name, $value ) { | |
| //We can't store a value into nothingness | |
| if( !is_string( $name ) || !$name ) { | |
| return false; | |
| } | |
| /** | |
| * If the provided value is an instance of this | |
| * class, we should store it as an element | |
| * rather than as a value. | |
| */ | |
| if( | |
| is_object( $value ) && | |
| get_class( $value ) === get_class( $this ) | |
| ) { | |
| if( !isset( $this->_elements[$name] ) ) { | |
| $this->_elements[$name] = array(); | |
| } | |
| $this->_elements[$name][] = $value; | |
| } else { | |
| /** | |
| * If an element exists with this name, | |
| * this value would be inaccessible anyway, | |
| * so don't perform the store. | |
| */ | |
| if( isset( $this->_elements[$name] ) ) { | |
| return false; | |
| } | |
| $this->_values[$name] = $value; | |
| } | |
| return true; | |
| } | |
| /** | |
| * Get a value or tree object from within | |
| * this tree, as specified by a path. | |
| * @param $path The path to search for | |
| */ | |
| public function get( $path ) { | |
| //If $path is empty, we're at our destination | |
| if( strlen( $path ) == 0 ) { | |
| return $this; | |
| } | |
| $this->parse( $path, $name, $filters ); | |
| /** | |
| * First try to follow the requested path | |
| * via an element. | |
| */ | |
| if( isset( $this->_elements[$name] ) ) { | |
| $elements = $this->elements( $name, $filters ); | |
| $total = count( $elements ); | |
| if( $total > 0 ) { | |
| return $elements[$total-1]->get( $path ); | |
| } | |
| } else if( isset( $this->_values[$name] ) ) { | |
| return $this->_values[$name]; | |
| } | |
| return NULL; | |
| } | |
| /** | |
| * Count the number of elements that are | |
| * found at a specific path and return | |
| * that number. | |
| * @param $path The path to search for | |
| * @return int The number of elements | |
| * at the requested path destination | |
| */ | |
| public function count( $path ) { | |
| if( strlen( $path ) == 0 ) { | |
| return 0; | |
| } | |
| $this->parse( $path, $name, $filters ); | |
| if( isset( $this->_elements[$name] ) ) { | |
| $elements = $this->elements( $name, $filters ); | |
| $total = count( $elements ); | |
| //If we're at our destination node, return the count | |
| if( strlen( $path ) == 0 ) { | |
| return $total; | |
| } | |
| return $elements[$total-1]->count( $path ); | |
| } else if( isset( $this->_values[$name] ) ) { | |
| //If no element exists, but a value exists | |
| return 1; | |
| } | |
| return 0; | |
| } | |
| /** | |
| * Test this tree against the provided set of | |
| * filters. | |
| */ | |
| protected function match( array $filters ) { | |
| $test = array(); | |
| $operators = array(); | |
| foreach( $filters as $filter ) { | |
| if( is_array( $filter ) ) { | |
| $test[] = $this->match( $filter ); | |
| } else if( | |
| $filter === "and" || | |
| $filter === "or" | |
| ) { | |
| $operators[] = $filter; | |
| } else { | |
| $test[] = $this->test( $filter ); | |
| } | |
| } | |
| $total = count( $test ); | |
| $result = $test[0]; | |
| for( $i = 1; $i < $total; $i++ ) { | |
| if( $operators[$i-1] === "and" ) { | |
| $result = $result && $test[$i]; | |
| } else if( $operators[$i-1] === "or" ) { | |
| $result = $result || $test[$i]; | |
| } | |
| } | |
| return $result; | |
| } | |
| /** | |
| * Test a condition against this tree. | |
| * A condition is anything in the form: | |
| * path|operator|value, without the pipes. | |
| * For example: name=Fred. The value can also | |
| * be enclosed in single quotes, like: | |
| * name='Fred'. The operator can be any | |
| * equality or inequality operator. The | |
| * value can only be a string or a number. | |
| */ | |
| protected function test( $condition ) { | |
| $random = ""; | |
| while( strlen( $random ) < 7 ) { | |
| $random .= rand(0,9) . ""; | |
| } | |
| //This is to protect against escaped single quotes | |
| $condition = str_replace( "\\'", $random, $condition ); | |
| //Check if the value is enclosed by single quotes | |
| preg_match( "/'([^']*?)'/", $condition, $strings ); | |
| $string = isset( $strings[1] ) ? $strings[1] : false; | |
| /** | |
| * If it is, store the value inside the | |
| * quotes and replace it with a token | |
| * that we can replace again later. This | |
| * makes sure nothing inside the single | |
| * quotes messes with our string splitting | |
| * in a bit. | |
| */ | |
| if( $string !== false ) { | |
| $condition = str_replace( "'" . $string . "'", "[!!]", $condition ); | |
| $string = str_replace( $random, "'", $string ); | |
| } | |
| //Check for a valid operator | |
| preg_match( "/\s*(=|>|<|<=|>=)\s*/", $condition, $operators ); | |
| $operator = isset( $operators[1] ) ? trim( $operators[1] ) : false; | |
| //If a filter doesn't have an operator, what good is it? | |
| if( $operator === false ) { | |
| throw new Exception( | |
| "No operator found in filter '" . $condition . "'." | |
| ); | |
| } | |
| $split = preg_split( "/\s*(=|>|<|<=|>=)\s*/", $condition ); | |
| $path = $split[0]; | |
| $this->parse( $path, $name, $filters ); | |
| $value = $split[1]; | |
| //If we pulled out a string, inject it now | |
| if( $string ) { | |
| $value = str_replace( "[!!]", $string, $value ); | |
| } | |
| //If $path is null, we've reached the destination | |
| if( strlen( $path ) == 0 ) { | |
| //If the name can't be found, this can't be true | |
| if( !isset( $this->_values[$name] ) ) { | |
| return false; | |
| } | |
| $test = $this->_values[$name]; | |
| //If the value is a number, cast it for comparison | |
| if( !preg_match( "/[^0-9.]/", $value ) ) { | |
| if( strpos( ".", $value ) >= 0 ) { | |
| $value = (float)$value; | |
| } else { | |
| $value = (int)$value; | |
| } | |
| } | |
| if( $operator === "=" && $test == $value ) { | |
| return true; | |
| } else if( $operator === ">" && $test > $value ) { | |
| return true; | |
| } else if( $operator === "<" && $test < $value ) { | |
| return true; | |
| } else if( $operator === ">=" && $test >= $value ) { | |
| return true; | |
| } else if( $operator === "<=" && $test <= $value ) { | |
| return true; | |
| } | |
| return false; | |
| } else { | |
| if( isset( $this->_elements[$name] ) ) { | |
| $elements = $this->elements( $name, $filters ); | |
| $total = count( $elements ); | |
| if( $string ) { | |
| $value = "'" . $value . "'"; | |
| } | |
| return $elements[$total-1]->test( | |
| $path . " " . $operator . " " . $value | |
| ); | |
| } | |
| } | |
| return false; | |
| } | |
| private function elements( $name, $filters ) { | |
| if( !isset( $this->_elements[$name] ) ) { | |
| return array(); | |
| } | |
| $total = count( $this->_elements[$name] ); | |
| if( count( $filters ) > 0 ) { | |
| if( count( $filters ) == 1 ) { | |
| //If the filter is just a number, it's an index | |
| if( !preg_match( "/[^0-9]/", $filters[0] ) ) { | |
| $index = (int)$filters[0]; | |
| if( isset( $this->_elements[$name][$index] ) ) { | |
| return array( $this->_elements[$name][$index] ); | |
| } | |
| return NULL; | |
| } | |
| } | |
| $return = array(); | |
| for( $i = 0; $i < $total; $i++ ) { | |
| if( $this->_elements[$name][$i]->match( $filters ) ) { | |
| $return[] = $this->_elements[$name][$i]; | |
| } | |
| } | |
| return $return; | |
| } | |
| return $this->_elements[$name]; | |
| } | |
| /** | |
| * Parse through a path string and find the | |
| * immediate name, any filters that need to | |
| * be applied to the immediate name, and the | |
| * excess path once those elements are removed. | |
| * @param $path The path to parse | |
| * @param $name The immediate name that's pulled | |
| * from the path | |
| * @param $filters An array of filters that's | |
| * pulled from the end of the immediate name | |
| */ | |
| private function parse( &$path, &$name, &$filters ) { | |
| /** | |
| * Trim any excess forward slashes from the | |
| * beginning of the path string. They are not | |
| * needed. | |
| */ | |
| while( substr( $path, 0, 1 ) === "/" ) { | |
| $path = substr( $path, 1 ); | |
| } | |
| /** | |
| * Match any string with letters, numbers, *, _ and | |
| * - at the beginning of the path string. This | |
| * is the immediate name. | |
| */ | |
| preg_match( | |
| "/^([a-zA-Z0-9*_\-]+)/", | |
| $path, | |
| $matches | |
| ); | |
| $name = isset( $matches[1] ) ? $matches[1] : false; | |
| //If the name wasn't found, something is wrong with the path | |
| if( $name === false ) { | |
| throw new Exception( "Malformed path." ); | |
| } | |
| //Remove the extracted immediate name from the path string | |
| $path = preg_replace( "/" . $name . "/", "", $path, 1 ); | |
| $data = ""; | |
| /** | |
| * If the remaining path begins with a [ character, | |
| * then we have a filter to deal with. | |
| */ | |
| if( substr( $path, 0, 1 ) === "[" ) { | |
| /** | |
| * We match the content at the beginning of the | |
| * remaining path that's between a [ and a ], | |
| * proceeded by a / or the end of the path string | |
| */ | |
| preg_match( | |
| "/^\[(.+)\](\/|\$)/s", | |
| $path, | |
| $matches | |
| ); | |
| $data = isset( $matches[1] ) ? $matches[1] : false; | |
| /** | |
| * If the filter data isn't found, something is | |
| * wrong with the path string. | |
| */ | |
| if( $data === false ) { | |
| throw new Exception( "Malformed filter string." ); | |
| } | |
| } | |
| $filters = array(); | |
| if( strlen( $data ) > 0 ) { | |
| //Escape the filter data so it'll play nice with regexp | |
| $replace = str_replace( "(", "\(", $data ); | |
| $replace = str_replace( ")", "\)", $replace ); | |
| $replace = str_replace( "/", "\/", $replace ); | |
| $path = preg_replace( "/\[" . $replace . "\]/", "", $path, 1 ); | |
| preg_match_all( "/(\s+and|or\s+)/i", $data, $matches ); | |
| $split = preg_split( "/\s+and|or\s+/i", $data ); | |
| $total = count( $split ); | |
| $stack = array(); | |
| $level = 0; | |
| for( $i = 0; $i < $total; $i++ ) { | |
| $condition = trim( $split[$i] ); | |
| $open_count = substr_count( $condition, "(" ); | |
| $close_count = substr_count( $condition, ")" ); | |
| while( substr( $condition, 0, 1 ) == "(" ) { | |
| $stack[] = $filters; | |
| $filters = array(); | |
| $condition = substr( $condition, 1 ); | |
| $level++; | |
| } | |
| $use = $condition; | |
| if( $close_count > $open_count ) { | |
| for( $i = 0; $i < $close_count - $open_count; $i++ ) { | |
| $use = substr( $use, 0, strlen( $use ) - 1 ); | |
| } | |
| } | |
| $filters[] = $use; | |
| while( | |
| count( $stack ) > 0 && | |
| substr( $condition, -1, 1 ) == ")" | |
| ) { | |
| $new = array_pop( $stack ); | |
| $new[] = $filters; | |
| $filters = $new; | |
| $condition = substr( $condition, 0, strlen( $condition ) - 1 ); | |
| $level--; | |
| } | |
| if( $i < $total - 1 ) { | |
| $filters[] = trim( $matches[1][$i] ); | |
| } | |
| } | |
| } | |
| } //end parse | |
| } | |
| ?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment