/***

Domains and functions for representing and manipulating a nested interval
hierarchy based on work by Vadim Tropashko in
"Trees in SQL: Nested Sets and Materialized Path"
http://www.dbazine.com/tropashko4.shtml
and "Relocating Subtrees in Nested Intervals Model"
http://www.dbazine.com/tropashko5.shtml

Ported to PostgreSQL by Michael Glaesemann

Requires PL/pgSQL and instr functions, which are featured in the 
PostgreSQL 7.4 Documentation in the Porting from Oracle PL/SQL appendix
http://www.postgresql.org/docs/7.4/static/plpgsql-porting.html#PLPGSQL-PORTING-APPENDIX

NOTE: There is a mistake in the functions as they are. The datatypes of 
the parameters in the three-term instr function must be changed from 
instr(varchar,varchar,varchar) to instr(varchar,varchar,integer) 
for these functions to work.

Includes pow2(), an integer power of two function written by Manfred Koizar
http://archives.postgresql.org/pgsql-general/2004-03/msg00931.php

***/
begin;

create domain ni_path as 
    text
    not null
    check (value ~ '^([1-9]\\d*)(\\.[1-9]\\d*)*$');


create function ni_x_numer (
      integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
    begin
        -- add one to the numerator so the numerator becomes 2x
        ret_numer := numer + 1;
        ret_denom := denom * 2;
        -- reduce to simplest form
        while floor(ret_numer / 2.0) = ret_numer / 2.0 loop
            ret_numer := ret_numer / 2;
            ret_denom := ret_denom / 2;
        end loop;
        return ret_numer;
    end;
    ';

create function ni_x_denom (
      integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
    begin
        ret_numer := numer + 1;
        ret_denom := denom * 2;
        while floor(ret_numer / 2.0) = ret_numer / 2.0 loop
            ret_numer := ret_numer / 2;
            ret_denom := ret_denom / 2;
        end loop;
        return ret_denom;
    end;
    ';

create function ni_y_numer (
      integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
    begin
        ret_numer := ni_x_numer(numer,denom);
        ret_denom := ni_x_denom(numer,denom);
        while ret_denom < denom loop
            ret_numer := ret_numer * 2;
            ret_denom := ret_denom * 2;
        end loop;
        ret_numer = numer - ret_numer;
        -- reduce to simplest form
        while floor(ret_numer / 2.0) = ret_numer / 2.0 loop
            ret_numer = ret_numer / 2;
            ret_denom = ret_denom / 2;
        end loop;
        return ret_numer;
    end;
    ';

create function ni_y_denom (
      integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
    begin
        ret_numer := ni_x_numer(numer,denom);
        ret_denom := ni_x_denom(numer,denom);
        while ret_denom < denom loop
            ret_numer := ret_numer * 2;
            ret_denom := ret_denom * 2;
        end loop;
        ret_numer = numer - ret_numer;
        while floor(ret_numer / 2.0) = ret_numer / 2.0 loop
            ret_numer = ret_numer / 2;
            ret_denom = ret_denom / 2;
        end loop;
        return ret_denom;
    end;
    ';

create function pow2(bigint) 
    returns bigint 
    language plpgsql as '
    declare
        e bigint;
        ret bigint;
    begin
        e := $1;
        if (e < 0) then
            raise exception ''2 ^ % does not fit into a bigint'', e;
        end if;
        if (e > 62) then
            raise exception ''2 ^ % does not fit into a bigint'', e;
        end if;
        ret = 1;
        while (e > 0) loop
            ret = 2 * ret;
            e = e - 1;
        end loop;
        return ret;
    end;
';

create function ni_child_numer (
      integer -- numer
    , integer -- denom
    , integer -- child
    ) returns integer 
    language plpgsql as '
        declare
            numer alias for $1;
            denom alias for $2;
            child alias for $3;
        begin
            return numer * pow2(child) + 3 - pow2(child);
        end;
    ';

create function ni_child_denom (
      integer -- numer
    , integer -- denom
    , integer -- child
    ) returns integer 
    language plpgsql as '
        declare
            numer alias for $1;
            denom alias for $2;
            child alias for $3;
        begin
            return denom * pow2(child);
        end;
    ';


create function ni_parent_numer (
      integer -- numer
    , integer -- denom
    ) returns integer 
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
    begin
        -- special case where node is the root
        if numer = 3 then
            return null;
        end if;
        ret_numer := (numer - 1) / 2 ;
        ret_denom := denom / 2 ;
        while floor (( ret_numer - 1) / 4.0) = (ret_numer - 1) / 4.0 loop
            ret_numer := (ret_numer + 1) / 2;
            ret_denom := ret_denom / 2;
        end loop;
        return ret_numer;
    end;
    ';
    
create function ni_parent_denom (
      integer -- numer
    , integer -- denom
    ) returns integer 
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
    begin
        if numer = 3 then
            return null;
        end if;
        ret_numer := (numer - 1) / 2 ;
        ret_denom := denom / 2 ;
        while floor (( ret_numer - 1) / 4.0) = (ret_numer - 1) / 4.0 loop
            ret_numer := (ret_numer + 1) / 2;
            ret_denom := ret_denom / 2;
        end loop;
        return ret_denom;
    end;
    ';
    
create function ni_sibling_number (
    integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        ret_numer integer;
        ret_denom integer;
        ret integer;
    begin
        ret_numer := (numer - 1) / 2;
        ret_denom := denom / 2;
        ret := 1;
        
        while floor ((ret_numer - 1) / 4.0) = (ret_numer - 1) / 4.0 loop
            if ret_numer = 1 and ret_denom = 1 then
                return ret;
            end if;
            ret_numer := (ret_numer + 1) / 2;
            ret_denom := ret_denom / 2;
            ret := ret + 1;
        end loop;
        return ret;
    end;
    ';

create function ni_path_inner (
      integer -- numer
    , integer -- denom
    ) returns text 
    language plpgsql as '
    declare
        numer alias for $1;
        denom alias for $2;
        path_string text;
    begin
        if numer is null then
            return '''';
        end if;
        return 
            ni_path_inner(
                ni_parent_numer(numer,denom)
                , ni_parent_denom(numer,denom)
                )
            || ''.'' 
            || ni_sibling_number(numer,denom)
            ;
    end;
    ';

create function ni_path (
      integer -- numer
    , integer -- denom
    ) returns ni_path
    language sql as '
    select substr(ni_path_inner($1,$2),2,length(ni_path_inner($1,$2)) - 1)::ni_path
    ';

create function ni_path_numer (
    ni_path -- x.x.x path notation
    ) returns integer
    language plpgsql as '
    declare 
        path alias for $1;
        numer integer;
        denom integer;
        postfix text;
        sibling text;
    begin
        numer := 1;
        denom := 1;
        postfix := ''.'' || path || ''.'';
        
        while length(postfix) > 1 loop
            sibling := substr(
                    postfix
                    , 2
                    , instr(postfix,''.'',2) - 2
                );
            postfix := substr(
                    postfix
                    , instr (postfix, ''.'', 2)
                    , length(postfix) - instr(postfix,''.'',2) + 1
                );
            numer := ni_child_numer(
                        numer
                        , denom
                        , to_number(
                            sibling
                            , repeat(''9'',length(sibling))
                            )::integer
                        );
            denom := ni_child_denom(
                          numer
                        , denom
                        , to_number(
                              sibling
                            , repeat(''9'',length(sibling))
                            )::integer
                        );
        end loop;
        return numer;
    end;
    ';

create function ni_path_denom (
    ni_path -- x.x.x path notation
    ) returns integer
    language plpgsql as '
    declare 
        path alias for $1;
        numer integer;
        denom integer;
        postfix text;
        sibling text;
    begin
        numer := 1;
        denom := 1;
        postfix := ''.'' || path || ''.'';
        
        while length(postfix) > 1 loop
            sibling := substr(
                      postfix
                    , 2
                    , instr(postfix,''.'',2) - 2
                );
            postfix := substr(
                      postfix
                    , instr (postfix, ''.'', 2)
                    , length(postfix) - instr(postfix,''.'',2) + 1
                );
            numer := ni_child_numer(
                          numer
                        , denom
                        , to_number(
                            sibling
                            , repeat(''9'',length(sibling))
                            )::integer
                        );
            denom := ni_child_denom(
                        numer
                        , denom
                        , to_number(
                            sibling
                            , repeat(''9'',length(sibling))
                            )::integer
                        );
        end loop;
        return denom;
    end;
    ';

create function ni_distance (
      integer -- numer_1
    , integer -- denom_1
    , integer -- numer_2
    , integer -- denom_2
    ) returns integer
    language plpgsql as '
    declare
        numer_1 alias for $1;
        denom_1 alias for $2;
        numer_2 alias for $3;
        denom_2 alias for $4;
    begin
        if numer_1 is null then
            return -999999;
        end if;
        -- check if they are the same point
        if numer_1 = numer_2 
            and denom_1 = denom_2 then
            return 0;
        end if;
        return 1 + ni_distance (
            ni_parent_numer(numer_1, denom_1)
            , ni_parent_denom(numer_1, denom_1)
            , numer_2
            , denom_2);
    end;
    ';



create function ni_reroot_numer (
      integer  -- $1 old_numer
    , integer  -- $2 old_denom
    
    , integer  -- $3 old_root_numer
    , integer  -- $4 old_root_denom
    
    , integer  -- $5 new_root_numer
    , integer  -- $6 new_root_denom
    ) returns integer
    stable
    language sql as '
    select ni_path_numer (
        ni_path($5,$6) || substr(
            ni_path($1,$2)
            , length(ni_path($3,$4)) + 1
            , length(ni_path($1,$2)) - length(ni_path($3,$4))
            )
        );
    ';

create function ni_reroot_denom (
      integer  -- $1 old_numer
    , integer  -- $2 old_denom
    
    , integer  -- $3 old_root_numer
    , integer  -- $4 old_root_denom
    
    , integer  -- $5 new_root_numer
    , integer  -- $6 new_root_demon
    ) returns integer
    stable
    language sql as '
    select ni_path_denom (
        ni_path($5,$6) || substr(
            ni_path($1,$2)
            , length(ni_path($3,$4)) + 1
            , length(ni_path($1,$2)) - length(ni_path($3,$4))
            )
        );
    ';

create function ni_normalize_numer (
      integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
    numer alias for $1;
    denom alias for $2;
    ret_numer integer;
    ret_denom integer;
    begin
        ret_numer := numer;
        ret_denom := denom;
        while floor (ret_numer / 2.0) = ret_numer / 2.0 loop
            ret_numer := ret_numer / 2;
            ret_denom := ret_denom / 2;
        end loop;
        return ret_numer;
    end;
    ';

create function ni_normalize_denom (
      integer -- numer
    , integer -- denom
    ) returns integer
    language plpgsql as '
    declare
    numer alias for $1;
    denom alias for $2;
    ret_numer integer;
    ret_denom integer;
    begin
        ret_numer := numer;
        ret_denom := denom;
        while floor (ret_numer / 2.0) = ret_numer / 2.0 loop
            ret_numer := ret_numer / 2;
            ret_denom := ret_denom / 2;
        end loop;
        return ret_denom;
    end;
    ';

create function ni_new_numer (
      integer -- old_numer
    , integer -- old_denom

    , integer -- old_origin_numer
    , integer -- old_origin_denom

    , integer -- new_origin_numer
    , integer -- new_origin_denom
    ) returns integer
    language plpgsql as '
    declare
        old_numer alias for $1;
        old_denom alias for $2;

        old_origin_numer alias for $3;
        old_origin_denom alias for $4;

        new_origin_numer alias for $5;
        new_origin_denom alias for $6;

        zoom_factor integer;

        ret_numer integer;
        ret_denom integer;

        ret_numer_temp integer;
    begin
        -- old is the old_origin
        if old_numer = old_origin_numer
            and old_denom = old_origin_denom
            then
            return new_origin_numer;
        end if;
        
        if old_origin_denom < new_origin_denom then
            zoom_factor := new_origin_denom / old_origin_denom;
                new_origin_denom
                , old_origin_denom
                , zoom_factor;
            ret_numer   := old_numer 
                    - old_origin_numer * old_denom / old_origin_denom;
            ret_denom   := old_denom * zoom_factor;
        else
            zoom_factor := old_origin_denom / new_origin_denom;
            ret_numer   := (old_numer 
                    - old_origin_numer * old_denom / old_origin_denom
                            ) * zoom_factor;
            ret_denom   := old_denom;
        end if;
        ret_numer_temp := ret_numer;
        ret_numer := ni_normalize_numer (ret_numer_temp, ret_denom);
        ret_denom := ni_normalize_denom (ret_numer_temp, ret_denom);
        if ret_denom < new_origin_denom then
            ret_numer := new_origin_numer 
                + ret_numer * new_origin_denom / ret_denom;
            ret_denom := new_origin_denom;
        else
            ret_numer := ret_numer 
                + new_origin_numer * ret_denom / new_origin_denom;
        end if;
        ret_numer_temp := ret_numer;
        ret_numer := ni_normalize_numer (ret_numer_temp, ret_denom);
        ret_denom := ni_normalize_denom (ret_numer_temp, ret_denom);
        
        return ret_numer;
    end;
    ';

create function ni_new_denom (
      integer -- old_numer
    , integer -- old_denom

    , integer -- old_origin_numer
    , integer -- old_origin_denom

    , integer -- new_origin_numer
    , integer -- new_origin_denom
    ) returns integer
    language plpgsql as '
    declare
        old_numer alias for $1;
        old_denom alias for $2;

        old_origin_numer alias for $3;
        old_origin_denom alias for $4;

        new_origin_numer alias for $5;
        new_origin_denom alias for $6;

        zoom_factor integer;

        ret_numer integer;
        ret_denom integer;
        
        ret_numer_temp integer;
    begin
        -- old is the old_origin
        if old_numer = old_origin_numer
            and old_denom = old_origin_denom
            then
            return new_origin_denom;
        end if;
        
        if old_origin_denom < new_origin_denom then
            zoom_factor := new_origin_denom / old_origin_denom;
            ret_numer   := old_numer 
                    - old_origin_numer * old_denom / old_origin_denom;
            ret_denom   := old_denom * zoom_factor;
        else
            zoom_factor := old_origin_denom / new_origin_denom;
            ret_numer   := (old_numer 
                    - old_origin_numer * old_denom / old_origin_denom
                            ) * zoom_factor;
            ret_denom   := old_denom;
        end if;
        ret_numer_temp := ret_numer;
        ret_numer := ni_normalize_numer (ret_numer_temp, ret_denom);
        ret_denom := ni_normalize_denom (ret_numer_temp, ret_denom);
        if ret_denom < new_origin_denom then
            ret_numer := new_origin_numer 
                + ret_numer * new_origin_denom / ret_denom;
            ret_denom := new_origin_denom;
        else
            ret_numer := ret_numer 
                + new_origin_numer * ret_denom / new_origin_denom;
        end if;
        ret_numer_temp := ret_numer;
        ret_numer := ni_normalize_numer (ret_numer_temp, ret_denom);
        ret_denom := ni_normalize_denom (ret_numer_temp, ret_denom);
        
        return ret_denom;
    end;
    ';

commit;