Skip to content

Instantly share code, notes, and snippets.

@Avaq
Last active February 16, 2019 21:23
Show Gist options
  • Save Avaq/cd43f49299e62d3ed2f012ef04d04a79 to your computer and use it in GitHub Desktop.
Save Avaq/cd43f49299e62d3ed2f012ef04d04a79 to your computer and use it in GitHub Desktop.
Nested Directory Structure in SQL
-- Create our directories table.
CREATE TABLE `directories` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) DEFAULT NULL,
`lft` int(11) NOT NULL,
`rgt` int(11) NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `directory_lft` (`lft`),
UNIQUE KEY `directory_rgt` (`rgt`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
-- A procedure for creating space in the directory tree.
CREATE PROCEDURE allocate_directory_space (IN position int(11), IN size int(11))
MODIFIES SQL DATA
BEGIN
DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
START TRANSACTION;
UPDATE `directories` SET `lft` = `lft` + size WHERE `lft` >= position ORDER BY `lft` DESC;
UPDATE `directories` SET `rgt` = `rgt` + size WHERE `rgt` >= position ORDER BY `rgt` DESC;
COMMIT;
END;
-- A procedure for removing space in the directory tree.
CREATE PROCEDURE deallocate_directory_space (IN position int(11), IN size int(11))
MODIFIES SQL DATA
BEGIN
DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
START TRANSACTION;
UPDATE `directories` SET `lft` = `lft` - size WHERE `lft` > position ORDER BY `lft` ASC;
UPDATE `directories` SET `rgt` = `rgt` - size WHERE `rgt` > position ORDER BY `rgt` ASC;
COMMIT;
END;
-- A procedure for moving trees into or next to other trees.
CREATE PROCEDURE move_directory_tree (
IN subject int(11),
IN mode enum('left','right','into'),
IN target int(11)
)
MODIFIES SQL DATA
BEGIN
DECLARE old_lft int(11);
DECLARE old_rgt int(11);
DECLARE new_lft int(11);
DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING BEGIN
ROLLBACK;
SELECT 0 AS `ok`, old_lft AS `lft`, old_rgt AS `rgt`;
END;
START TRANSACTION;
-- Query for the old left and right values.
SELECT `lft`, `rgt` INTO old_lft, old_rgt FROM `directories` WHERE `id` = subject;
-- Check if the move is valid.
IF target IN (SELECT `id` FROM `directories` WHERE `lft` >= old_lft AND `rgt` <= old_rgt) THEN
ROLLBACK;
SELECT 0 AS `ok`, old_lft AS `lft`, old_rgt AS `rgt`;
ELSE
-- Remove the directory we're moving by flipping it into negative space.
UPDATE `directories` SET `lft` = (0 - `lft`), `rgt` = (0 - `rgt`)
WHERE `lft` >= old_lft AND `rgt` <= old_rgt;
-- Remove the space we've created.
CALL deallocate_directory_space (old_lft, (old_rgt - old_lft) + 1);
-- Determine target position.
SELECT CASE mode
WHEN 'left' THEN `lft`
WHEN 'right' THEN `rgt` + 1
WHEN 'into' THEN `rgt`
END INTO new_lft FROM `directories` WHERE `id` = target;
-- Allocate space at target position.
CALL allocate_directory_space (new_lft, (old_rgt - old_lft) + 1);
-- Move the subject and all of its children into the allocated space.
UPDATE `directories`
SET `lft` = (0 - `lft` + (new_lft - old_lft)), `rgt` = (0 - `rgt` + (new_lft - old_lft))
WHERE `lft` < 0;
COMMIT;
SELECT 1 AS `ok`, new_lft AS `lft`, new_lft + (old_rgt - old_lft) AS `rgt`;
END IF;
END;
-- A procedure for creating a new directory with a parent.
CREATE PROCEDURE create_directory (IN new_name varchar(255), IN parent int(11))
MODIFIES SQL DATA
BEGIN
DECLARE position int(11);
DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
START TRANSACTION;
SELECT `rgt` INTO position FROM `directories` WHERE `id` = parent;
CALL allocate_directory_space (position, 2);
INSERT INTO `directories` (`name`, `lft`, `rgt`) VALUES (new_name, position, position + 1);
COMMIT;
SELECT LAST_INSERT_ID() AS `id`;
END;
-- A procedure for creating a new directory without parents.
CREATE PROCEDURE create_directory_tree (IN new_name varchar(255))
MODIFIES SQL DATA
BEGIN
INSERT INTO `directories` (`name`, `lft`, `rgt`)
SELECT new_name, IFNULL(MAX(`rgt`) + 1, 1), IFNULL(MAX(`rgt`) + 2, 2)
FROM `directories`;
SELECT LAST_INSERT_ID() AS `id`;
END;
-- A procedure for removing a directory and its descendants.
CREATE PROCEDURE delete_directory_tree (IN subject int(11))
MODIFIES SQL DATA
BEGIN
DECLARE old_lft int(11);
DECLARE old_rgt int(11);
DECLARE EXIT HANDLER FOR SQLEXCEPTION, SQLWARNING ROLLBACK;
START TRANSACTION;
SELECT `lft`, `rgt` INTO old_lft, old_rgt FROM `directories` WHERE `id` = subject;
DELETE FROM `directories` WHERE `lft` >= old_lft AND `rgt` <= old_rgt;
CALL deallocate_directory_space (old_lft, (old_rgt - old_lft) + 1);
COMMIT;
END;
-- Create our tags table.
CREATE TABLE tags (
id SERIAL NOT NULL,
name character varying(255) NOT NULL,
lft integer NOT NULL,
rgt integer NOT NULL,
PRIMARY KEY (id),
UNIQUE (lft) DEFERRABLE INITIALLY IMMEDIATE,
UNIQUE (rgt) DEFERRABLE INITIALLY IMMEDIATE
);
-- A function for creating space in the tag tree.
CREATE FUNCTION allocate_tag_space(pos integer, size integer) RETURNS void AS $$
BEGIN
SET CONSTRAINTS ALL DEFERRED;
UPDATE tags SET lft = lft + size WHERE lft >= pos;
UPDATE tags SET rgt = rgt + size WHERE rgt >= pos;
END;
$$ LANGUAGE PLPGSQL;
-- A function for removing space in the tag tree.
CREATE FUNCTION deallocate_tag_space(pos integer, size integer) RETURNS void AS $$
BEGIN
SET CONSTRAINTS ALL DEFERRED;
UPDATE tags SET lft = lft - size WHERE lft > pos;
UPDATE tags SET rgt = rgt - size WHERE rgt > pos;
END;
$$ LANGUAGE PLPGSQL;
-- A function for moving trees into or next to other trees.
CREATE TYPE move_tag_tree_mode AS ENUM ('left', 'right', 'into');
CREATE FUNCTION move_tag_tree(
subject tags.id%TYPE,
mode move_tag_tree_mode,
target tags.id%TYPE
) RETURNS void AS $$
DECLARE
old_lft tags.lft%TYPE;
old_rgt tags.rgt%TYPE;
new_lft tags.lft%TYPE;
BEGIN
-- Query for the old left and right values.
SELECT lft, rgt INTO old_lft, old_rgt FROM tags WHERE id = subject;
-- Check if the move is valid.
IF target IN (SELECT id FROM tags WHERE lft >= old_lft AND rgt <= old_rgt) THEN
RAISE EXCEPTION 'Attempt to move tree into itself';
END IF;
-- Remove the tag we're moving by flipping it into negative space.
UPDATE tags SET lft = (0 - lft), rgt = (0 - rgt)
WHERE lft >= old_lft AND rgt <= old_rgt;
-- Remove the space we've created.
PERFORM deallocate_tag_space (old_lft, (old_rgt - old_lft) + 1);
-- Determine target pos.
SELECT CASE mode
WHEN 'left' THEN lft
WHEN 'right' THEN rgt + 1
WHEN 'into' THEN rgt
END INTO new_lft FROM tags WHERE id = target;
-- Allocate space at target pos.
PERFORM allocate_tag_space (new_lft, (old_rgt - old_lft) + 1);
-- Move the subject and all of its children into the allocated space.
UPDATE tags
SET lft = (0 - lft + (new_lft - old_lft)), rgt = (0 - rgt + (new_lft - old_lft))
WHERE lft < 0;
END;
$$ LANGUAGE PLPGSQL;
-- A function for creating a new tag with a parent.
CREATE FUNCTION create_tag(new_name tags.name%TYPE, parent tags.id%TYPE) RETURNS tags.id%TYPE AS $$
DECLARE pos integer; last_insert_id tags.id%TYPE; BEGIN
SELECT rgt INTO pos FROM tags WHERE id = parent;
IF pos IS NULL THEN RAISE EXCEPTION 'Parent not found'; END IF;
PERFORM allocate_tag_space (pos, 2);
INSERT INTO tags (name, lft, rgt) VALUES (new_name, pos, pos + 1)
RETURNING id INTO last_insert_id;
RETURN last_insert_id;
END;
$$ LANGUAGE PLPGSQL;
-- A function for creating a new tag without parents.
CREATE FUNCTION create_tag_tree(new_name tags.name%TYPE) RETURNS tags.id%TYPE AS $$
DECLARE last_insert_id tags.id%TYPE; BEGIN
INSERT INTO tags (name, lft, rgt)
SELECT new_name, COALESCE(MAX(rgt) + 1, 1), COALESCE(MAX(rgt) + 2, 2)
FROM tags RETURNING id INTO last_insert_id;
RETURN last_insert_id;
END;
$$ LANGUAGE PLPGSQL;
-- A function for removing a tag and its descendants.
CREATE FUNCTION delete_tag_tree(subject tags.id%TYPE) RETURNS void AS $$
DECLARE old_lft tags.lft%TYPE; old_rgt tags.rgt%TYPE; BEGIN
SELECT lft, rgt INTO old_lft, old_rgt FROM tags WHERE id = subject;
DELETE FROM tags WHERE lft >= old_lft AND rgt <= old_rgt;
PERFORM deallocate_tag_space (old_lft, (old_rgt - old_lft) + 1);
END;
$$ LANGUAGE PLPGSQL;
// MySQLDir :: { id :: Number, name :: String, lft :: Number, rgt :: Number }
// Directory :: { id :: Number, name :: String, children :: Array Directory }
// unflatten :: Array MySQLDir -> Array Directory
const unflatten = directories => {
if (directories.length === 0) { return []; }
const head = directories[0];
const children = directories.filter(dir => dir.lft > head.lft && dir.rgt < head.rgt);
const remainder = directories.filter(dir => dir.lft > head.rgt);
return [{id: head.id, name: head.name, children: unflatten(children)}]
.concat(unflatten(remainder));
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment