Finding IDs down a tree - query logic - PHP

Question

I have the following table folders:

  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 am allowing drag and drop of the folders but need to prevent folders being dragged down into their own subfolders.

E.g. D to B is ok, D to E is ok, B to F is not ok as its dragging into its own tree, but F to B is ok as its dragging UP the tree.

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

I am looking for logic, how would one say it, and then code it, that B to F is not ok but F to B is.

Answer 1

With your current DB schema I see only the option of multiple select statements. You would have to check upwards or downwards the tree until you hit the root or the last child (like in nietonfirs answer).

I for myself would 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 is, if someone wants to move B, get a list of valid destinations: SELECT id FROM folders WHERE pathToFolder NOT LIKE ',1,2,%'

These kind of operations are not the fastest but very handy.

Answer 2

I suppose there'd be a method that would take ids of both target and destination (or whole data objects, whatever), and check if target is in destinations path or not. If it is, then the method would return false or throw an exceptions, else it would return true. That method could be introduced to your directory copying code flow as a control structure.

Personally, for hierarchical data structures I'd go with implementing it as a nested set. It can be a hassle to set-up and fixing nested set can get tedious, but I find it very convinient for checking relations 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 will probably not fit your domain model, so never mind them.