gistfile1.txt

SECTION "USER FRIENDLY MANUALS"

GET     "libhdr"



MANIFEST
{   entry_id        = 0 
    entry_dep       = 1
    entry_dsize     = 2
    entry_visited   = 3
    
    node_size
}



GLOBAL  
{   g.E : ug
    g.D 
    
    g.cis
    g.hFile
    
    g.entry_list
    g.sorted_list
    g.sorted_idx
    
    g.start_time
    g.stop_time
}


LET start() = VALOF
{   //do_file("progdata\t1.txt")
    //do_file("progdata\t2.txt")
    //do_file("progdata\t3.txt")
    //do_file("progdata\t4.txt")
    //do_file("progdata\t5.txt")
    //do_file("progdata\t6.txt")
    start_timer()
    do_file("progdata\ex.txt")
    stop_timer()
    writef("*n ex.txt time: %n*n", get_time_taken_ms())
    RESULTIS 0
}

AND do_file(fname) BE
{   LET str     = ?
    LET i       = ?
    LET a, b    = ?, ?
    
    set_infile(fname)
    IF NOT g.hFile  RETURN
    
    str := fread_line()
    IF NOT str      RETURN
    
    writef("*nSorting file %s*n", fname)
    
    trim(str)
    parse_num2(str, @g.E, @g.D)
    freevec(str)
    
    init_nodel()
    FOR i = 0 TO g.D-1 DO
    {   str := fread_line()
        IF NOT str BREAK
        
        trim(str)
        IF str%0 = 0 DO {   freevec(str)
                            LOOP
                        }
                        
        parse_num2(str, @a, @b)
        append_dep(g.entry_list!a, g.entry_list!b)
        freevec(str)
    }

    FOR i = 0 TO g.E-1 DO writef("*n %n,", g.entry_list!i!entry_id)
    FOR i = 0 TO g.E-1 DO
    {   LET j = ?
        FOR j = 0 TO g.entry_list!i!entry_dsize-1 DO
        writef("%n->%n,", g.entry_list!i!entry_id, g.entry_list!i!entry_dep!j!entry_id)
        writes("*n")
    }
    
    sort_dep()
    traverse()
    
    FOR i = 0 TO g.E-1 DO writef(" %n", g.sorted_list!i)
    writes("*n")
    
    clean_nodes()
    cls_infile()
}


AND traverse() BE
{   LET i = ?
    FOR i = 0 TO g.E-1 DO
    {   LET trav(node) BE
        {   LET j = ?
            FOR j = 0 TO node!entry_dsize-1 DO
            {   LET nptr = node!entry_dep!j
                IF nptr!entry_visited = TRUE RETURN
                g.sorted_list!g.sorted_idx := nptr!entry_id
                nptr!entry_visited := TRUE
                g.sorted_idx := g.sorted_idx + 1
                trav(nptr)          
            }
        }
        IF g.entry_list!i!entry_visited = TRUE LOOP
        
        g.sorted_list!g.sorted_idx := g.entry_list!i!entry_id
        g.sorted_idx := g.sorted_idx + 1 
        g.entry_list!i!entry_visited := TRUE
        
        IF g.entry_list!i!entry_dsize > 0 DO trav(g.entry_list!i)     
    }
}


/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////   NODE HANDLING
/////////////////////////////////////////////////////////////////////////////////////////

AND init_nodel() BE
{   LET i = ?
    g.entry_list := getvec(g.E)
    FOR i = 0 TO g.E-1 DO init_node(i)
    
    g.sorted_list:= getvec(g.E)
    g.sorted_idx := 0
}

AND init_node(idx) BE
{   g.entry_list!idx                := getvec(node_size)
    g.entry_list!idx!entry_id       := idx
    g.entry_list!idx!entry_dep      := 0
    g.entry_list!idx!entry_dsize    := 0
    g.entry_list!idx!entry_visited  := FALSE
}

AND clean_nodes() BE
{   LET i = ?
    FOR i = 0 TO g.E-1 DO
    {   freevec(g.entry_list!i!entry_dep)
        freevec(g.entry_list!i)
    }
    
    freevec(g.sorted_list)
}


AND append_dep(node, which) BE
//reallocing is gonna suck for speed
    TEST node!entry_dsize = 0 THEN
    {   node!entry_dep      := getvec(1)
        node!entry_dep!0    := which
        node!entry_dsize    := 1
    }
    ELSE
    {   LET tv  = ?
        LET i   = ?
        
        tv := getvec(node!entry_dsize + 1)
        FOR i = 0 TO node!entry_dsize-1 DO tv!i := node!entry_dep!i
        tv!(node!entry_dsize) := which
        
        freevec(node!entry_dep)
        
        node!entry_dep      := tv
        node!entry_dsize    := node!entry_dsize + 1
    }
    
    
AND sort_dep() BE
{   LET i, j = ?, ?
    FOR i = 0 TO g.E-1 DO
    {   LET tv = getvec(g.entry_list!i!entry_dsize)
        merge_sort(g.entry_list!i!entry_dep, tv, g.entry_list!i!entry_dsize)
        freevec(tv)
    }
}

AND merge_sort(o, t, sz) BE merge_split(o, t, 0, sz)

AND merge_split(o, t, b, e) BE
{   LET m = ?
    IF (e - b) < 2 RETURN
    
    m := b + e / 2
    merge_split(o, t, b, m)
    merge_split(o, t, m, e)
    merge_merge(o, t, b, m, e)
    copy_vec(o, t, b, e)
}

AND merge_merge(o, t, b, m, e) BE
{   LET ib, im = b, m
    LET i = ?
    FOR i = b TO e-1 DO
    {   TEST ib < m & im >= e | o!ib < o!im
        THEN { t!i := o!ib; ib := ib + 1 }
        ELSE { t!i := o!im; im := im + 1 }
    }
}

AND copy_vec(o, t, b, e) BE
{   LET i = ?
    FOR i = b TO e-1 DO o!i := t!i
}



/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////   FILE IO
/////////////////////////////////////////////////////////////////////////////////////////

//Swap existing stream with a new one
// 
AND set_infile(filename) = VALOF 
{   g.hFile := findinput(filename)
    IF g.hFile DO
    {   g.cis := input()
        selectinput(g.hFile)
    }
    RESULTIS g.hFile    
}

//close file and return input to previous stream
AND cls_infile()    BE
{   IF g.hFile DO
    {   endread()
        selectinput(g.cis)
        g.hFile := 0
    }
}

AND fread_line()   = VALOF
{   LET ch = ?
    LET buf, out, nr = 0, 0, 0
    IF g.cis = input() RESULTIS 0   //we don't want this stream
    buf := getvec(64) //255 chars
    
    {   ch := rdch()
        TEST ch ~= endstreamch & ch ~= '*n' THEN
        {   buf%nr := ch
            nr := nr + 1
        //    writef("*n %c %n ", ch, nr)
        }
        ELSE BREAK
        
    }   REPEAT
    
    IF nr > 0 DO
    {   LET i = 1
        out := getvec(nr/bytesperword + 1)
        out%0 := nr
        {   out%i := buf%(i-1)
            i := i + 1
        }   REPEATWHILE i <= nr
    }
    
    freevec(buf)
    RESULTIS out
}

AND parse_num2(str, a, b) BE
{   IF str%0 ~= 0 DO
    {   
        LET str2int(s, i) BE    //whoops, could have used str2numb or string_to_number
        {   LET n,k = s%0, 1
            LET ch = s%n
            !i := 0
            
            {   ch      := ch - '0'
                !i      := !i + ch * k
                n, k    := n - 1, k * 10
                ch      := s%n
            }   REPEATWHILE n > 0
        }
        
        LET buf     = VEC 10
        LET p, i    = 0, ?
        
        UNTIL str%(p+1) = ' '   DO  p := p + 1
        FOR i = 0 TO p BY 1     DO  buf%(i+1) := str%(i+1)
        
        buf%0 := p
        str2int(buf, a)
        
        i := p + 2
        p := 1
        {   buf%p := str%i
            p, i := p + 1, i + 1
        }   REPEATUNTIL i = str%0 + 1
        
        buf%0 := p-1
        str2int(buf, b)
    }
}

AND trim(str) BE
{   LET f, r, i, p = ?, ?, ?, 1
    IF str%0 = 0 RETURN
    r := str%0 + 2
    f := 0
    
    {   f := f + 1
    }   REPEATUNTIL f = r | str%f ~= ' '  

    IF f = r DO
    {   str%0 := 0
        RETURN
    }

    {   r := r - 1
    }   REPEATUNTIL r = f | str%r ~= ' '

    FOR i = f TO r DO
    {   str%p := str%i
        p := p + 1
    }

    str%0 := r - f
}



AND start_timer()           BE g.start_time := sys(Sys_cputime)
AND stop_timer()            BE g.stop_time  := sys(Sys_cputime)
AND get_time_taken_ms()     = g.stop_time - g.start_time   
AND get_time_taken_sec()    = (g.stop_time - g.start_time) / 1000