tree functions

CREATE PROCEDURAL LANGUAGE plpgsql;


SET search_path = public, pg_catalog;


CREATE FUNCTION bitfromint4(integer) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$
begin
    return $1::bit(32);
end;$_$;


ALTER FUNCTION public.bitfromint4(integer) OWNER TO smarlowe;


CREATE FUNCTION bittoint4(bit varying) RETURNS integer
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$
begin
    return "int4"($1);
end;$_$;


ALTER FUNCTION public.bittoint4(bit varying) OWNER TO smarlowe;


CREATE FUNCTION int_to_tree_key(integer) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$



declare
  p_intkey        alias for $1;
begin
  if p_intkey < 0 then
    raise exception 'int_to_tree_key: key must be a positive integer';
  end if;

  if p_intkey < 128 then
    return substring(bitfromint4(p_intkey), 25, 8);
  else
    return substring(bitfromint4(cast (-2^31 + p_intkey as int4)), 1, 32);
  end if;

end;$_$;


ALTER FUNCTION public.int_to_tree_key(integer) OWNER TO smarlowe;


CREATE FUNCTION tree_ancestor_key(bit varying, integer) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$


declare
  p_tree_key      alias for $1;
  p_level         alias for $2;
  v_level         integer default 0;
  v_pos           integer default 1;
begin

  if tree_level(p_tree_key) < p_level then
    raise exception 'tree_ancestor_key: key is at a level less than %', p_level;
  end if;

  while v_level < p_level loop
    v_level := v_level + 1;
    if substring(p_tree_key, v_pos, 1) = '1' then
      v_pos := v_pos + 32;
    else
      v_pos := v_pos + 8;
    end if;
  end loop;

  return substring(p_tree_key, 1, v_pos - 1);

end;$_$;


ALTER FUNCTION public.tree_ancestor_key(bit varying, integer) OWNER TO smarlowe;


CREATE FUNCTION tree_ancestor_keys(bit varying) RETURNS SETOF bit varying
    LANGUAGE sql IMMUTABLE STRICT
    AS $_$

  select tree_ancestor_keys($1, 1)

$_$;


ALTER FUNCTION public.tree_ancestor_keys(bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_ancestor_keys(bit varying, integer) RETURNS SETOF bit varying
    LANGUAGE sql IMMUTABLE STRICT
    AS $_$
  select tree_ancestor_key($1, $2)
  union
  select tree_ancestor_keys($1, $2 + 1)
  where $2 < tree_level($1)
$_$;


ALTER FUNCTION public.tree_ancestor_keys(bit varying, integer) OWNER TO smarlowe;


CREATE FUNCTION tree_ancestor_p(bit varying, bit varying) RETURNS boolean
    LANGUAGE plpgsql IMMUTABLE
    AS $_$
declare
  p_potential_ancestor      alias for $1;
  p_potential_child         alias for $2;
begin
  return position(p_potential_ancestor in p_potential_child) = 1;
end;$_$;


ALTER FUNCTION public.tree_ancestor_p(bit varying, bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_increment_key(bit varying) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE
    AS $_$
declare
    p_child_sort_key                alias for $1;
    v_child_sort_key                integer;
begin
    if p_child_sort_key is null then
        v_child_sort_key := 0;
    else
        v_child_sort_key := tree_leaf_key_to_int(p_child_sort_key) + 1;
    end if;

    return int_to_tree_key(v_child_sort_key);
end;$_$;


ALTER FUNCTION public.tree_increment_key(bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_key_to_int(bit varying, integer) RETURNS integer
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$


declare
  p_tree_key      alias for $1;
  p_level         alias for $2;
  v_level         integer default 0;
  v_parent_pos    integer default 1;
  v_pos           integer default 1;
begin

  -- Find the right key first
  while v_pos < length(p_tree_key) and v_level < p_level loop
    v_parent_pos := v_pos;
    v_level := v_level + 1;
    if substring(p_tree_key, v_pos, 1) = '1' then
      v_pos := v_pos + 32;
    else
      v_pos := v_pos + 8;
    end if;
  end loop;

  if v_level < p_level then
    raise exception 'tree_key_to_int: key is at a level less than %', p_level;
  end if;

  if substring(p_tree_key, v_parent_pos, 1) = '1' then
    return bittoint4(substring(p_tree_key, v_parent_pos + 1, 31));
  else
    return bittoint4(substring(p_tree_key, v_parent_pos, 8));
  end if;

end;$_$;


ALTER FUNCTION public.tree_key_to_int(bit varying, integer) OWNER TO smarlowe;


CREATE FUNCTION tree_leaf_key_to_int(bit varying) RETURNS integer
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$


declare
  p_tree_key      alias for $1;
  v_leaf_pos      integer default 1;
  v_pos           integer default 1;
begin

  -- Find the leaf key first
  while v_pos < length(p_tree_key) loop
    v_leaf_pos := v_pos;
    if substring(p_tree_key, v_pos, 1) = '1' then
      v_pos := v_pos + 32;
    else
      v_pos := v_pos + 8;
    end if;
  end loop;

  if substring(p_tree_key, v_leaf_pos, 1) = '1' then
    return bittoint4(substring(p_tree_key, v_leaf_pos + 1, 31));
  else
    return bittoint4(substring(p_tree_key, v_leaf_pos, 8));
  end if;

end;$_$;


ALTER FUNCTION public.tree_leaf_key_to_int(bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_left(bit varying) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE
    AS $_$


declare
  key      alias for $1;
begin
  if key is null then
    return 'X00'::varbit;
  else
    return key || 'X00'::varbit;
  end if;
end;$_$;


ALTER FUNCTION public.tree_left(bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_level(bit varying) RETURNS integer
    LANGUAGE plpgsql IMMUTABLE
    AS $_$


declare
  p_tree_key           alias for $1;
  v_pos                integer;
  v_level              integer;

begin

  if p_tree_key is null then
    return 0;
  end if;

  v_pos := 1;
  v_level := 0;

  while v_pos <= length(p_tree_key) loop
    v_level := v_level + 1;
    if substring(p_tree_key, v_pos, 1) = '1' then
      v_pos := v_pos + 32;
    else
      v_pos := v_pos + 8;
    end if;
  end loop;

  return v_level;
end;$_$;


ALTER FUNCTION public.tree_level(bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_next_key(bit varying, integer) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE
    AS $_$
declare
  p_parent_key      alias for $1;
  p_child_value     alias for $2;
  v_child_value     integer;
begin

  if p_child_value is null then
    v_child_value := 0;
  else
    v_child_value := p_child_value + 1;
  end if;

  if p_parent_key is null then
    return int_to_tree_key(v_child_value);
  else
    return p_parent_key || int_to_tree_key(v_child_value);
  end if;

end;$_$;


ALTER FUNCTION public.tree_next_key(bit varying, integer) OWNER TO smarlowe;


CREATE FUNCTION tree_right(bit varying) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE
    AS $_$


declare
  key      alias for $1;
begin
  if key is null then
    return 'XFFFFFFFF'::varbit;
  else
    return key || 'XFFFFFFFF'::varbit;
  end if;
end;$_$;


ALTER FUNCTION public.tree_right(bit varying) OWNER TO smarlowe;


CREATE FUNCTION tree_root_key(bit varying) RETURNS bit varying
    LANGUAGE plpgsql IMMUTABLE STRICT
    AS $_$


declare
  p_tree_key      alias for $1;
begin

  if substring(p_tree_key, 1, 1) = '1' then
      return substring(p_tree_key, 1, 32);
  else
      return substring(p_tree_key, 1, 8);
  end if;

end;$_$;


ALTER FUNCTION public.tree_root_key(bit varying) OWNER TO smarlowe;


REVOKE ALL ON SCHEMA public FROM PUBLIC;
REVOKE ALL ON SCHEMA public FROM postgres;
GRANT ALL ON SCHEMA public TO postgres;
GRANT ALL ON SCHEMA public TO PUBLIC;