OpenEuphoria

Pastey stables.e

• Posted by _tom (admin) Jun 24, 2020

--  stables.e : sorted tables 4.11
--  jiri babor 
--  jbabor@paradise.net.nz 
--  8 September 2002 
 
---------------------------------------------------------------- 
--  sorted tables using binary search 
--  single sequence scheme: {val1, ..valN, {key1, ..kN}} 
---------------------------------------------------------------- 
 
without warning 
without type_check 
 
global constant ET = {{}}               --  empty table 
 
global function tsort(sequence s) 
    --  shell sort table s by keys in ascending order 
 
    object t1i,t1j,t2i,t2j              -- temporary objects 
    sequence s1,s2 
    integer gap,j,first,last,n 
 
    n = length(s) 
    s1 = s[n] 
    s2 = s[1..n-1] 
    last = n-1 
    gap = floor(last / 3) + 1 
    while 1 do 
        first = gap + 1 
        for i = first to last do 
            t1i = s1[i] 
            t2i = s2[i] 
            j = i - gap 
            while 1 do 
                t1j = s1[j] 
                t2j = s2[j] 
                if compare(t1i, t1j) >= 0 then 
                    j += gap 
                    exit 
                end if 
                s1[j+gap] = t1j 
                s2[j+gap] = t2j 
                if j <= gap then 
                    exit 
                end if 
                j -= gap 
            end while 
            s1[j] = t1i 
            s2[j] = t2i 
        end for 
        if gap = 1 then 
            return s2 & {s1} 
        else 
            gap = floor(gap / 3) + 1 
        end if 
    end while 
end function -- tsort 
 
global function index(sequence table, object key) 
    --  binary search on a sorted sequence 
    --  modified Gabriel Boehme's code 
    -- return *key* index, or zero if key not found 
 
    sequence s 
    integer lo, hi, mid, c 
 
    lo = 1 
    hi = length(table) 
    s = table[hi] 
    hi -= 1 
 
    while lo <= hi do 
        mid = floor((lo + hi) / 2) 
        c = compare(key, s[mid]) 
        if    c < 0 then  -- key < s[mid] 
            hi = mid - 1 
        elsif c > 0 then  -- key > s[mid] 
            lo = mid + 1 
        else              -- key = s[mid] 
            return mid 
        end if 
    end while 
    return 0 
end function 
 
global function fetch(sequence table, object key) 
    -- return table item with indicated key 
    return table[index(table,key)] 
end function -- fetch 
 
global function set(sequence table, object key, object new_value) 
    -- replace specified table item with a new value 
    -- return modified table 
    table[index(table,key)] = new_value 
    return table 
end function -- set 
 
global function insert(sequence table, object key, object val) 
    -- insert new entry 
 
    sequence s 
 
    integer len,n,lo,hi,i,c 
 
    n = length(table) 
    if n = 1 then          -- empty table 
        return {val, {key}} 
    end if 
    s = table[n]           -- key sequence 
    hi = n-1 
    lo = 1 
    i = 1 
 
    if compare(key, s[1]) < 0 then 
        table[n] = prepend(table[n], key) 
        table = prepend(table, val) 
        return table 
    end if 
    while lo <= hi do 
        i = floor((lo + hi) / 2) 
        c = compare(key, s[i]) 
        if c < 0 then       -- key < s[i] 
            hi = i - 1 
        else                -- key > s[i] 
            lo = i + 1 
        end if 
    end while 
    len = n-1 
    s = append(s,0) 
    s[lo+1..n] = s[lo..len] 
    s[lo] = key 
    table[n] = s 
 
    table = append(table,0) 
    table[lo+1..n+1] = table[lo..n] 
    table[lo] = val 
    return table 
end function 
 
global function merge(sequence table1, sequence table2) 
    --  merge table1 and table2 
    integer m,n 
 
    m = length(table1) 
    n = length(table2) 
    return tsort(table1[1..m-1] & table2[1..n-1] & {table1[m] & table2[n]}) 
end function 
 
global function remove(sequence table, object key) 
    --  remove entry with the specified key from the table 
 
    integer i,n 
 
    i = index(table, key) 
    if i then 
        n = length(table) 
        table[n][i..n-2] = table[n][i+1..n-1] 
        table[n] = table[n][1..n-2] 
        table[i..n-1] = table[i+1..n] 
    end if 
    return table[1..n-1] 
end function -- remove 
 
global function dups(sequence s) 
    --  return sequence of duplicated keys 
 
    sequence d 
    integer n 
 
    d = {} 
    n = length(s) 
    s = s[n]            -- we are interested in keys only 
    if n > 2 then 
        for i=2 to n-1 do 
            if equal(s[i], s[i-1]) then 
                d = append(d, s[i]) 
            end if 
        end for 
    end if 
    return d 
end function