Tree Identifier Search - Query Logic - PHP

Question

Tree Identifier Search - Query Logic - PHP

I have the following folder table:

id name childOf ------------------------ 1 A 0 2 B 1 3 C 0 4 D 3 5 E 2 6 F 5

This forms a tree:

 A -B --E ---F C -D

I allow the drag and drop of folders, but you need to prevent the drag and drop of folders into your own subfolders.

eg. DB is fine, DE is fine, BF is not normal as it drags it to its tree, but FB is fine because it drags it up the tree.

QUESTION: If the user selects B and tries to drag it to F, how can I prevent this?

I am looking for logic, how to say it, and then encode it, that from B to F is not normal, but F to B.

+7

php

Darren sweeney October 8th. '13 at 9:10

source share

11 answers

tsdtsdtsd · Answer 1 · 2013-10-16T16:55:58+0000

With your current database schema, I only see a variant of several select statements. You will need to check up or down the tree until you hit the root or the last child (as in response to nietonfirs).

For myself, I will add a fourth column to the table containing the full path:

 id name childOf pathToFolder ---------------------------------- 1 A 0 ,1, 2 B 1 ,1,2, 3 C 0 ,1,3, 4 D 3 ,1,3,4, 5 E 2 ,1,2,5, 6 F 5 ,1,2,5,6,

There are several ways to use this new data. One way: if someone wants to move B, get a list of valid destinations: SELECT id FROM folders WHERE pathToFolder NOT LIKE ',1,2,%'

These operations are not the fastest, but very convenient.

guessimtoolate · Answer 2 · 2013-10-16T16:32:56+0000

I assume that there will be a method that will take the identifiers of both the target and the target (or entire data objects, whatever) and check whether the target is in the destination path or not. If so, then the method will return false or throw exceptions, otherwise it will return true. This method can be introduced into your directory by copying the code stream as a control structure.

Personally for hierarchical data structures, I would include it as a nested set . This can be a problem for setting up and fixing a nested set can be tedious, but I find it very convenient for checking relationships between nodes and getting whole subtrees.

Here's a PHPUnit test with a partial and somewhat naive implementation of my idea:

 <?php ini_set('display_errors', 1); ini_set('display_startup_errors', 1); error_reporting(-1); require 'vendor/autoload.php'; class ParentingSucks { public $data = array(); public function isAllowed($targetId, $destId) { $target = $this->getById($targetId); $dest = $this->getById($destId); $parent = $this->getById($dest['childOf']); $isAllowed = true; while ($parent) { if ($parent['id'] == $targetId) { $isAllowed = false; break; } $parent = $this->getById($parent['childOf']); } return $isAllowed; } public function getById($id) { if (isset($this->data[$id])) { return $this->data[$id]; } return array(); } } class HowIMetYourParentDir extends PHPUnit_Framework_TestCase { /** * @test * @dataProvider generate */ public function droppingOnParentNotAllowed($data, $target, $dest, $outcome) { $stub = $this->getMock('ParentingSucks', null); $stub->data = $data; $result = $stub->isAllowed($target, $dest); $this->assertEquals($result, $outcome, 'Oh no!'); } public function generate() { $fakeData = array( 1 => array('id' => 1, 'name' => 'A', 'childOf' => 0), 2 => array('id' => 2, 'name' => 'B', 'childOf' => 1), 3 => array('id' => 3, 'name' => 'C', 'childOf' => 0), 4 => array('id' => 4, 'name' => 'D', 'childOf' => 3), 5 => array('id' => 5, 'name' => 'E', 'childOf' => 2), 6 => array('id' => 6, 'name' => 'F', 'childOf' => 5), ); return array( array( $fakeData, 2, // target 6, // dest false, // outcome ), array( $fakeData, 4, 2, true, ), array( $fakeData, 4, 2, true, ), array( $fakeData, 3, 4, false, ), ); } } false, // outcome ), array( $fakeData, 4, 2, true, ), array( $fakeData, 4, 2, true, ), array( $fakeData, 3, 4, false, ), ); } }

Variable / function / class names are probably not suitable for your domain model, so ignore them.

siergiej · Answer 3 · 2013-10-16T17:11:28+0000

You have several options:

With your current tree structure, you can iterate recursively (or using the stack) over the parents of the element you are adding; If one of the parents is equal to the element being added, just return an error. You can also do this check in javascript to provide a better user experience (why even allow dragging and dropping an item to your own child :)); However, this approach may be a little slow with really big trees, but the records are really cheap.
You could simplify the work with your tree by reworking your tree structure with a nested set; I will not go into details about nested sets, as you can read them on this page: About nested sets . Instead, I will give you a brief idea of what is possible with nested sets. First, your table will look like this:

  id name lft rgt
     ---------------------------
     1 A 1 8
     2 B 2 7
     5 E 3 6
     6 F 4 5
     3 C 9 12
     4 D 10 11

It may seem strange at first sight, but don't worry about it for now.

With this, you can easily check if one node is the parent of another: $static->lft > $appended->lft && $static->rgt < $appended->rgt , and if true, then $appended is the parent of $static and you may throw an error;

You need:

return all parents of this node? Select WHERE lft < $node->lft and rgt > $node->rgt ;
get all descendants? Select WHERE lft > $node->lft and rgt < $node->rgt
to return all brothers and sisters? Add an extra level column and it's easy-peasy

But wait wait wait, How to insert a new node into this structure? you can ask. Fortunately, there is no need to reinvent the wheel, as nested sets are quite popular. You can use an implementation like this: https://github.com/riquito/Baobab/ and just focus on your application;

Check out some examples from the repo: https://github.com/riquito/Baobab/blob/master/src/examples/animals.php

 $root_id=$tree->appendChild(NULL,array("name"=>'Animals')); $vertebrates_id = $tree->appendChild($root_id,array("name"=>"Vertebrates")); $invertebrates_id = $tree->appendChild($root_id,array("name"=>"Invertebrates"));

As you can see, you do not need to touch the lft or rgt , as someone has already written this part for you. If you use Propel or Doctrine, it's still simpler, since they support nested sets.

geomagas · Answer 4 · 2013-10-23T07:10:47+0000

The logic is pretty simple:

The folder f can be dragged to the target folder t if and only if f<>t and f not an ancestor of t .

Since the question is marked as php and no RDBMS is specified, I will assume that your folders live in the php array, as shown below:

 $namespace=array( 1=>array('name'=>'A','parent'=>0), 2=>array('name'=>'B','parent'=>1), 3=>array('name'=>'C','parent'=>0), 4=>array('name'=>'D','parent'=>3), 5=>array('name'=>'E','parent'=>2), 6=>array('name'=>'F','parent'=>5), );

To decide if $f ancestor of $t , we need to start at $t and go up the tree until (1) we find $f or (2) we remove the root (and not root, since in your space names have several roots). Therefore, consider the following function:

 function is_ancestor($f,$t) { global $namespace; $are_equal=($f==$t); $t_parent=$namespace[$t]['parent']; $is_root=!isset($namespace[$t_parent]); return $are_equal || (!$is_root && is_ancestor($f,$t_parent)); }

I think it's pretty simple. Two things: (1), apparently, the parameters are the identifiers of the folder, and (2) despite the name, the function checks not only if $f is the ancestor of $t , but also if they are equal.

You can see the whole concept in action, this php script .

nietonfir · Answer 5 · 2013-10-08T09:13:42+0000

Just check your parents until you get to your root folder? In pseudo code

 // targetFolder is the target folder where the folder is going to be moved // while sourceFolder is the folder that moved. parents = targetFolder.getParents(); if (parents.contains(sourceFolder)) { // don't allow the operation }

rafalio · Answer 6 · 2013-10-16T16:25:12+0000

A suboptimal way is to simply compute all subfolders of a given folder, and then check if the target folder is part of them. It might look like this:

 getSubfolders(folder): oneLevelDeepSubfolders = subfolders with child-of field == folder.id allSubfolders = [] for subfolder in oneLevelDeepFolders: allSubfolders += getSubfolders(subfolder); return allSubfolders;

Then just check if your destination folder is in the getSubfolders folder (folder).

You might want to speed this up by creating another table that pre-computes the relationships of the subfolders for an arbitrary depth, so you don't have to recursively compute it every time you need it.

Süha Boncukçu · Answer 7 · 2013-10-21T23:04:03+0000

This question reminds me of things in my language classes. So I come up with this solution: Let me build your tree in an imaginary way. I will say R for root (id: 0) and -1 for the end.

 R:AC A:B B:E E:F F:-1 C:D D:-1

But this is not enough if we want to do something quickly. Add them too:

 R:BC R:EC R:FC R:BD R:ED R:FD

Let me arrange things for you:

 R:AC R:AD *I added this one R:BC R:EC R:FC R:BD R:ED R:FD R:A * this one too R:C * this one too A:B B:E E:F C:D F:-1 D:-1

That should be enough. So you said

eg. DB is fine, DE is fine, BF is not normal as it drags it to its tree, but FB is fine because it drags it up the tree.

Let's see D in B ok? We have to check it from right to left. Where is d Oh yes, there you are. R: BD! So, is it ok if they are together? Yes, everything is in order. D to E? R: ED! Yes, that’s normal too. B to F? Let's see BF together ... no huh? So, B on the right side ... is A: B, so let him check AR: A! boom! IN

It was just an offer to look for things differently. This can be done in different perspectives. But I really think that using such a grammar of the language will help. It can be created on the air or depending on the situation, it can be made in the form of a map file. But the complexity in many situations is very low. Good luck finding the best solution!

botenvouwer · Answer 8 · 2013-10-22T07:08:03+0000

I do not understand your problem. The algorithm is very simple.

Each time your PHP is called, you first check to see if the folder is a subfolder of the target folder. Now in your case this will not work. You should not use a numeric identifier to save the folders and files that should be used, since all operating systems use the file path.

Similar:

 url type description ------------------------------------------------- ROOT/folder 2 Image folder... ROOT/hallo 1 Hallo directory.. ROOT/hallo/subfolder 1 I am a sub dir..

Now you only need one column, but it will be a full text index. If you want to check if the folder is a parent of your own subfolder, you simply check the URL.

As when drawing ROOT/hallo To ROOT/hallo/subfolder you simply do this:

ROOT / hallo = 10 characters

ROOT / hallo / subfolder = 20 characters

 <?php $selected_folder = 'ROOT/hallo'; $subject_folder = 'ROOT/hallo/subfolder'; $length = strlen($selected_folder); if($selected_folder != substr($subject_folder,0,$length)){ echo 'go'; } else{ echo 'Can not relocate folder to its own subfolder'; } ?>

sumit · Answer 9 · 2013-10-22T13:51:41+0000

Since the question is tagged by PHP and you are talking about drag and drop, you will need classes to represent the tree behavior in PHP as well as in javascript

for PHP, I would suggest that you go through the implementation of the TreeBehavior class of the cake-php framework, which adds tree behavior to any model and expects you to have the table structure proposed by Adam.

for Javascript implementation, I noticed that the YUI tree module

implements trees for javascript

there is another library that possibly supports drag and drop, find here

I hope this helps you.

dododo · Answer 10 · 2013-10-23T12:10:07+0000

You can check the destination path. If one of the parent nodes is the source of the node, the chain will be broken and display an error. For example:

 <?php define("ROOT_NODE_ID",0); function getChildOf($nodeId){ // some code to get id value of parent node and assign it to $parentId return $parentId; } $sourceId = 2; // Node B $destinationId = 6; // Node F $error = false; $tmpParentId = getChildOf( $destinationId ); while($tmpParentId != ROOT_NODE_ID){ if($tmpParentId == $sourceId ){ $error=true; break; } $tmpParentId = getChildOf( $tmpParentId ); }

This method allows you to use indexes with integer values and NOT use row functions. String functions can significantly slow down work with fields of type int. You can also save this table structure without any changes.

Lalbhusan yadav · Answer 11 · 2013-10-23T13:25:25+0000

Create two functions and get all the best parents of each of the identifiers, i.e. from B to A and similarly to F, return the parent of F to c to it and store the identifiers in two different arrays. Now check if something is spread in two arrays or not. If general cn drag else cannot be dragged

Tree Identifier Search - Query Logic - PHP

More articles: