descend.sql

CREATE OR REPLACE FUNCTION descend(_root_id INT)
  RETURNS INT AS $$
DECLARE
  _count INT;
  _level INT;
  _matrix_degree BIGINT;
  _id INT;
  _type RECORD;
BEGIN
  SELECT t.* FROM matrix_node n JOIN matrix_type t ON n.type_id = t.id
    WHERE n.id = _root_id INTO _type;
  SELECT root_id, level, count(*) as count FROM matrix GROUP BY root_id, level
    HAVING count(*) < power(_type.degree, level);
  IF _level IS NOT NULL THEN
    SELECT min(id) FROM
      (
        SELECT id FROM matrix WHERE root_id = _root_id AND level = _level - 1
        EXCEPT
        SELECT parent_id FROM matrix WHERE root_id = _root_id AND level = _level
        GROUP BY parent_id HAVING count(*) >= _type.degree
      ) m
    INTO _id;
  ELSE
    SELECT max(level) FROM matrix WHERE root_id = _root_id INTO _level;
    SELECT min(id) FROM matrix WHERE root_id = _root_id AND level = _level INTO _id;
  END IF;
  RETURN _id;
END;
$$ LANGUAGE plpgsql STABLE;