Gecko [ fernandoquevedodop.com ]

Name	Size	Permission
cmaps	[ DIR ]	drwxr-xr-x
help	[ DIR ]	drwxr-xr-x
rline	[ DIR ]	drwxr-xr-x
scripts	[ DIR ]	drwxr-xr-x
arrayfuns.sl	1.85 KB	-rw-r--r--
autoload.sl	460 B	-rw-r--r--
base64.sl	19 B	-rw-r--r--
chksum.sl	1.58 KB	-rw-r--r--
cmdopt.sl	7.58 KB	-rw-r--r--
csv.sl	16.35 KB	-rw-r--r--
fcntl.sl	35 B	-rw-r--r--
fork.sl	17 B	-rw-r--r--
fswalk.sl	2.36 KB	-rw-r--r--
glob.sl	2.42 KB	-rw-r--r--
histogram.sl	2.98 KB	-rw-r--r--
iconv.sl	35 B	-rw-r--r--
json.sl	5.97 KB	-rw-r--r--
listfuns.sl	3.04 KB	-rw-r--r--
onig.sl	17 B	-rw-r--r--
pcre.sl	1.21 KB	-rw-r--r--
png.sl	4.02 KB	-rw-r--r--
print.sl	7.61 KB	-rw-r--r--
process.sl	9.83 KB	-rw-r--r--
profile.sl	19.88 KB	-rw-r--r--
rand.sl	4.28 KB	-rw-r--r--
readascii.sl	5.24 KB	-rw-r--r--
require.sl	1.27 KB	-rw-r--r--
select.sl	37 B	-rw-r--r--
setfuns.sl	4.8 KB	-rw-r--r--
sldb.sl	2.11 KB	-rw-r--r--
sldbcore.sl	18.1 KB	-rw-r--r--
sldbsock.sl	7.43 KB	-rw-r--r--
slshhelp.sl	536 B	-rw-r--r--
slshrl.sl	9.23 KB	-rw-r--r--
slsmg.sl	35 B	-rw-r--r--
socket.sl	151 B	-rw-r--r--
stats.sl	15.07 KB	-rw-r--r--
stkcheck.sl	2.62 KB	-rw-r--r--
structfuns.sl	2.05 KB	-rw-r--r--
sysconf.sl	20 B	-rw-r--r--
termios.sl	39 B	-rw-r--r--
varray.sl	37 B	-rw-r--r--
zlib.sl	2.93 KB	-rw-r--r--

Code Editor : listfuns.sl

% Copyright (C) 2012-2017,2018 John E. Davis
%
% This file is part of the S-Lang Library and may be distributed under the
% terms of the GNU General Public License.  See the file COPYING for
% more information.
%---------------------------------------------------------------------------
require ("arrayfuns");

private define user_sort_cmp (cd, i, j)
{
   variable list = cd.list;
   return (@cd.cmp) (list[i], list[j]);
}

private define default_sort_cmp (list, i, j)
{
   if (list[i] > list[j]) return 1;
   if (list[i] == list[j]) return 0;
   return -1;
}

define list_sort (list)
{
   variable dir = qualifier ("dir", 1);
   variable cmp = qualifier ("cmp");

variable n = length (list);
   variable i;
   if (cmp == NULL)
     i = array_sort (list, &default_sort_cmp, n; dir=dir);
   else
     i = array_sort (struct {list=list, cmp=cmp}, &user_sort_cmp, n; dir=dir);

variable inplace = qualifier ("inplace", 0);
   if (inplace == 0)
     return i;

rearrange (list, i);
}

% Heap Implementation

private define heap_length (h)
{
   return length (h.list);
}

private define upheap (list, k, cmp)
{
   variable obj = list[k];
   variable k2 = (k-1)/2;
   while (k && (@cmp)(obj,list[k2]) > 0)
     {
	list[k] = list[k2];
	k = k2;
	k2 = (k-1)/2;
     }
   list[k] = obj;
}

private define downheap (list, k, cmp)
{
   variable obj = list[k];
   variable n = length(list), n2 = n/2;
   n--;
%           0
%       1       2
%   3     4    5     6
% 7  8   9 10 11 12 13 14 
   while (k < n2)
     {
	variable j = 2*k + 1;
	if ((j < n)
	    && ((@cmp)(list[j], list[j+1]) < 0))
	  j++;
	if ((@cmp)(obj, list[j]) >= 0)
	  break;
	list[k] = list[j];
	k = j;
     }
   list[k] = obj;
}

private define heap_add (h, obj)
{
   variable list = h.list;
   list_append (list, obj);
   upheap (list, length(list)-1, h.cmp);
}

private define heap_pop (h)
{
   variable list = h.list;
   variable obj = list[0];
   variable last = list_pop(list, -1);
   if (length (list))
     {
	list[0] = last;
	downheap (list, 0, h.cmp);
     }
   return obj;
}

private define heap_peek (h)
{
   return h.list[0];
}

private define default_heap_cmp (a, b)
{
   if (a > b) return 1;
   if (a < b) return -1;
   return 0;
}

private define default_heap_cmp_rev (a, b)
{
   if (a > b) return -1;
   if (a < b) return 1;
   return 0;
}

define heap_new ()
{
   if (_NARGS == 0)
     usage (`
h = new_heap (list; cmp=&cmpfun, dir=val);
len = h.length();
h.add (item);
top = h.remove();
top = h.peek ();
`
	    );

variable list = ();
   variable cmp = qualifier ("cmp");
   variable dir = qualifier ("dir", -1);

% The conventional interpretation of a heap is that the largest
   % element is at the root, and smaller ones below.  For this reason,
   % dir=-1 (ascending order) is the default for sorting.
   list_sort (list; cmp=cmp, dir=dir, inplace);

if (cmp == NULL)
     {
	cmp = (dir <= 0) ? &default_heap_cmp : &default_heap_cmp_rev;
     }

variable h = struct
     {
	list = list,
	cmp = cmp,
	length = &heap_length,
	add = &heap_add,
	remove = &heap_pop,
	peek = &heap_peek,
     };
   return h;
}

${this.title}

Code Editor : listfuns.sl