Generic BigList Utilities #7
Aliases: ghblu, biglist_utils
26 verbs · 13 properties · 0 children
Verbs
| Verb | Spec | Flags | Definer | Lines |
|---|---|---|---|---|
length | this none this | rxd | #7 | 2 |
find_nth | this none this | rxd | #7 | 2 |
find_ord | this none this | rxd | #7 | 4 |
set_nth | this none this | rxd | #7 | 8 |
kill | this none this | rxd | #7 | 7 |
insert_after insert_before | this none this | rxd | #7 | 22 |
extract_range | this none this | rxd | #7 | 2 |
delete_range | this none this | rxd | #7 | 6 |
keep_range | this none this | rxd | #7 | 6 |
insert_last | this none this | rxd | #7 | 33 |
start | this none this | rxd | #7 | 24 |
next | this none this | rxd | #7 | 20 |
_find_nth | this none this | rxd | #7 | 18 |
_find_ord | this none this | rxd | #7 | 25 |
_set_nth | this none this | rxd | #7 | 17 |
_skill | this none this | rxd | #7 | 21 |
_extract | this none this | rxd | #7 | 32 |
_merge | this none this | rxd | #7 | 16 |
_smerge | this none this | rxd | #7 | 47 |
_split | this none this | rxd | #7 | 67 |
_rmerge | this none this | rxd | #7 | 43 |
_scrunch | this none this | rxd | #7 | 13 |
_listfind_nth | this none this | rxd | #7 | 10 |
_insertfirst | this none this | rxd | #7 | 3 |
debug | this none this | rxd | #7 | 1 |
_call | this none this | rxd | #7 | 7 |
Properties
| Property | Definer | Flags | Owner | Value |
|---|---|---|---|---|
about | #7 | rc | #29 | list of 15{"Implementation notes", "--------------------", "Each biglist is actually a tree (a kind of B-tree, actually).", "The routines above pass around handles of the form", "", " {root_node, size, leftmost_ord}", "", "where root_node is the (string) name of a property that holds the root of the tree, size is the number of leaves in the tree, and leftmost_ord is the :_ord value of the leftmost element of the list (i.e., the leftmost leaf).", "Each node property has a value of the form ", "", " {height,list of subtrees}.", "", "where the each of the subtrees is itself a 3-element list as above unless", "the height is 0, in which case the subtrees are actually biglist elements of the arbitrary form determined by the home object.", "At every level, each node except the rightmost has between this.maxfanout/2 and this.maxfanout subtrees; the rightmost is allowed to have as few as 1 subtree."} |
maxfanout | #7 | rc | #29 | 7 |
help_msg | #72 | rc | #29 | list of 73{"Generic BigList Utilities", "----------------------------", "This is a package for maintaining huge persistent (sorted) lists in a format that is less likely to spam the server (which runs into a certain amount of trouble dealing with long ordinary lists --- btw we use `biglist' to refer to the huge data structure we're about to describe and `list' to refer to ordinary MOO lists {...}). The biglist in question lives on a particular object, to which we will refer in the discussion below as the `home' object, and its various elements appear as leaves of a tree whose nodes are kept in properties of the home object. It should be noted that the home object does not need to be (and in fact should *not* be) a descendant of this one; this object merely provides utilities for manipulating the properties on the home object that are used in a particular biglist manipulation. ", "", "All of the utilities below refer to `caller' to locate the home object. Thus verbs to manipulate a given biglist must be located on or inherited by its home object itself. The home object needs to define the following verbs", "", " :_make(@args) => new property on home object with value args", " :_kill(prop) delete a given property that was created by :_make", " :_get(prop) => home.prop", " :_put(prop,@args) set home.prop = args", " :_ord(element) given something that is of the form of a biglist element", " return the corresponding ordinal (for sorting purposes).", " If you never intend to use :find_ord, then this can be a ", " routine that always returns 0 or some other random value.", "", "See #5546 (Generic Biglist Resident) or $big_mail_recipient", "for examples.", "", "Those of the following routines that take a biglist argument are expecting", "either {} (empty biglist) or some biglist returned by one of the other routines", "", " :length(biglist) => length(biglist) (i.e., number of elements)", " :find_nth(biglist,n) => biglist[n]", " :find_ord(biglist,k,comp) => n where n is", " the largest such that home:(comp)(k,home:_ord(biglist[n])) is false, or", " the smallest such that home:(comp)(k,home:_ord(biglist[n+1])) is true.", " Always returns a value between 0 and length(biglist) inclusive.", " This assumes biglist to be sorted in order of increasing :_ord values ", " with respect to home:(comp)().", " Standard situation is :_ord returns a number and comp is a < verb.", "", " :start(biglist,s,e) => {biglist[s..?],@handle} or {}", " :next(@handle) => {biglist[?+1..??],@newhandle} or {}", " These two are used for iterating over a range of elements of a biglist", " The canonical incantation for doing", " for elt in (biglist[first..last])", " ...", " endfor", " is", " handle = :start(biglist,first,last);", " while(handle)", " for elt in (handle[1])", " ...", " endfor", " handle = :next(@listdelete(handle,1));", " endwhile", "", "The following all destructively modify their biglist argument(s) L (and M).", "", " :set_nth(L,n,value) => L[n] = value", " replaces the indicated element", "", " :insert_before(L,M,n) => {@L[1..n-1],@M,@L[n..length(L)]}", " :insert_after (L,M,n) => {@L[1..n], @M,@L[n+1..length(L)]}", " takes two distinct biglists, inserts one into the other at the given point", " returns the resulting consolidated biglist", "", " :extract_range(L,m,n) => {{@L[1..m-1],@L[n+1..]}, L[m..n]} ", " breaks the given biglist into two distinct biglists.", "", " :delete_range(L,m,n[,leafkiller]) => {@L[1..m-1],@L[n+1..]}", " :keep_range (L,m,n[,leafkiller]) => L[m..n]", " like extract_range only we destroy what we don't want.", "", " :insert_last(L,value) => {@L,value}", " inserts a new element at the end of biglist. ", " If find_ord is to continue to work properly, it is assumed that the ", " home:_ord(elt) is greater (comp-wise) than all of the :_ord values", " of elements currently in the biglist.", "", " :kill(L[,leafkiller]) ", " destroys all nodes used by biglist. ", " Calls home:leafkiller on each element."} |
aliases | #1 | r | #29 | {"ghblu", "biglist_utils"} |
description | #1 | rc | #29 | {"This is the Generic BigList Utilities utility package. See `help $biglist' for more details."} |
object_size | #1 | r | #29 | {23044, 1298433815} |
hidden_verbs | #1 | rc | #29 | <clear> |
phelp_msg | #1 | rc | #29 | <clear> |
weight | #1 | rc | #29 | <clear> |
owner_verbs | #1 | rc | #29 | <clear> |
plural_name | #1 | rc | #29 | <clear> |
client_image | #1 | rc | #29 | <clear> |
listening | #1 | rc | #29 | <clear> |
Ancestry
Ancestors (nearest first): #72 Generic Utilities Package → #1 root
Children: none
Call graph
Source
length
Referenced by
none
Source
1":length(tree) => number of leaves in tree."; 2return args[1] ? args[1][2] | 0;
find_nth
Referenced by
none
Source
1":find_nth(tree,n) => nth leaf of tree. Assumes n in [1..tree[2]]"; 2return this:_find_nth(caller, @args);
find_ord
Referenced by
none
Source
1":_find_ord(tree,n,comp) "; 2" => index of rightmost leaf for which :(comp)(n,:_ord(leaf)) is false."; 3"returns 0 if true for all leaves."; 4return args[1] ? this:_find_ord(caller, @args) | 0;
set_nth
Referenced by
none
Source
1":set_nth(tree,n,value) => tree"; 2"modifies tree so that nth leaf == value"; 3if (((n = args[2]) < 1) || ((!(tree = args[1])) || (tree[2] < n))) 4return E_RANGE; 5else 6this:_set_nth(caller, @args); 7return (n != 1) ? tree | listset(tree, caller:_ord(args[3]), 3); 8endif
kill
Referenced by
none
Source
1":kill(tree[,leafverb]) deletes tree and _kills all of the nodes that it uses."; 2"if leafverb is given, caller:leafverb is called on all leaves in tree."; 3if (tree = args[1]) 4lverb = {@args, ""}[2]; 5this:_skill(caller, (typeof(tree) == LIST) ? tree[1] | tree, lverb); 6endif 7"... otherwise nothing to do...";
insert_after insert_before
Referenced by
none
Source
1":insert_after(tree,subtree,n)"; 2":insert_before(tree,subtree,n)"; 3" inserts subtree after (before) the nth leaf of tree,"; 4" returning the resulting tree."; 5subtree = args[2]; 6if (tree = args[1]) 7if (subtree) 8where = args[3] - (verb == "insert_before"); 9if (where <= 0) 10return this:_merge(caller, subtree, tree); 11elseif (where >= tree[2]) 12return this:_merge(caller, tree, subtree); 13else 14s = this:_split(caller, caller:_get(tree[1])[1], where, tree); 15return this:_merge(caller, this:_merge(caller, s[1], subtree), s[2]); 16endif 17else 18return tree; 19endif 20else 21return subtree; 22endif
extract_range
Referenced by
none
Source
1":extract_range(tree,first,last) => {newtree,extraction}"; 2return this:_extract(caller, @args);
delete_range
Referenced by
none
Source
1":delete_range(tree,first,last[,leafkill]) => newtree"; 2extract = this:_extract(caller, @args); 3if (die = extract[2]) 4this:_skill(caller, die[1], {@args, ""}[4]); 5endif 6return extract[1];
keep_range
Referenced by
none
Source
1":keep_range(tree,first,last[,leafkill]) => range"; 2extract = this:_extract(caller, @args); 3if (die = extract[1]) 4this:_skill(caller, die[1], {@args, ""}[4]); 5endif 6return extract[2];
insert_last
Referenced by
none
Source
1":insert_last(tree,insert) => newtree"; 2"insert a new leaf to be inserted at the righthand end of the tree"; 3tree = args[1]; 4insert = args[2]; 5if (!tree) 6return {caller:_make(0, {insert}), 1, caller:_ord(insert)}; 7endif 8hgt = caller:_get(tree[1]); 9rspine = {{tree, plen = length(kids = hgt[2])}}; 10for i in [1..hgt[1]] 11parent = kids[plen]; 12kids = caller:_get(parent[1])[2]; 13plen = length(kids); 14rspine = {{parent, plen}, @rspine}; 15endfor 16iord = caller:_ord(insert); 17for h in [1..length(rspine)] 18"... tree is the plen'th (rightmost) child of parent..."; 19if (rspine[h][2] < this.maxfanout) 20parent = rspine[h][1]; 21hgp = caller:_get(parent[1]); 22caller:_put(parent[1], @listset(hgp, {@hgp[2], insert}, 2)); 23for p in (rspine[h + 1..length(rspine)]) 24rkid = listset(parent, parent[2] + 1, 2); 25parent = p[1]; 26hgp = caller:_get(parent[1]); 27caller:_put(parent[1], @listset(hgp, listset(hgp[2], rkid, p[2]), 2)); 28endfor 29return listset(tree, tree[2] + 1, 2); 30endif 31insert = {caller:_make(h - 1, {insert}), 1, iord}; 32endfor 33return {caller:_make(length(rspine), {tree, insert}), tree[2] + 1, tree[3]};
start
Referenced by
none
Source
1":start(tree,first,last) => {list of leaf nodes, @handle}"; 2"handle is of the form {{node,next,size}...}"; 3if (tree = args[1]) 4before = max(0, args[2] - 1); 5howmany = min(args[3], tree[2]) - before; 6if (howmany <= 0) 7return {}; 8else 9spine = {}; 10for h in [1..caller:_get(tree[1])[1]] 11ik = this:_listfind_nth(kids = caller:_get(tree[1])[2], before); 12newh = kids[ik[1]][2] - ik[2]; 13if (newh < howmany) 14spine = {{tree[1], ik[1] + 1, howmany - newh}, @spine}; 15howmany = newh; 16endif 17tree = kids[ik[1]]; 18before = ik[2]; 19endfor 20return {caller:_get(tree[1])[2][before + 1..before + howmany], @spine}; 21endif 22else 23return {}; 24endif
next
Referenced by
none
Source
1":next(@handle) => {list of more leaf nodes, @newhandle}"; 2if (args) 3spine = listdelete(args, 1); 4node = args[1][1]; 5n = args[1][2]; 6size = args[1][3]; 7for h in [1..caller:_get(node)[1]] 8nnode = caller:_get(node)[2][n]; 9if (size > nnode[2]) 10spine = {{node, n + 1, size - nnode[2]}, @spine}; 11size = nnode[2]; 12endif 13n = 1; 14node = nnode[1]; 15endfor 16test = caller:_get(node); 17return {test[2][n..size], @spine}; 18else 19return {}; 20endif
_find_nth
Referenced by
- #7:find_nth line 2:
this:_find_nth - #7:_find_nth line 12:
this:_find_nth
Source
1":_find_nth(home,tree,n) => nth leaf of tree."; 2"...Assumes n in [1..tree[2]]"; 3if (caller != this) 4return E_PERM; 5endif 6{home, tree, n} = args; 7if ((p = home:_get(tree[1]))[1]) 8for k in (p[2]) 9if (n > k[2]) 10n = n - k[2]; 11else 12return this:_find_nth(home, k, n); 13endif 14endfor 15return E_RANGE; 16else 17return p[2][n]; 18endif
_find_ord
Referenced by
- #7:find_ord line 4:
this:_find_ord - #7:_find_ord line 14:
this:_find_ord
Source
1":_find_ord(home,tree,n,less_than) "; 2" => index of rightmost leaf for which :(less_than)(n,:_ord(leaf)) is false."; 3"returns 0 if true for all leaves."; 4if (caller != this) 5return E_PERM; 6endif 7{home, tree, n, less_than} = args; 8if ((p = home:_get(tree[1]))[1]) 9sz = tree[2]; 10for i in [-length(p[2])..-1] 11k = p[2][-i]; 12sz = sz - k[2]; 13if (!this:_call(home, less_than, n, k[3])) 14return sz + this:_find_ord(home, k, n, less_than); 15endif 16endfor 17return 0; 18else 19for i in [1..r = length(p[2])] 20if (this:_call(home, less_than, n, home:_ord(p[2][i]))) 21return i - 1; 22endif 23endfor 24return r; 25endif
_set_nth
Referenced by
- #7:set_nth line 6:
this:_set_nth - #7:_set_nth line 9:
this:_set_nth
Source
1":_set_nth(home,tree,n,value) => tree[n] = value"; 2"Assumes n in [1..tree[2]]"; 3if (caller != this) 4return E_PERM; 5endif 6{home, tree, n, value} = args; 7if ((p = home:_get(tree[1]))[1]) 8ik = this:_listfind_nth(p[2], n - 1); 9this:_set_nth(home, p[2][ik[1]], ik[2] + 1, value); 10if (!ik[2]) 11p[2][ik[1]][3] = home:_ord(value); 12home:_put(tree[1], @p); 13endif 14else 15p[2][n] = value; 16home:_put(tree[1], @p); 17endif
_skill
Referenced by
- #7:kill line 5:
this:_skill - #7:delete_range line 4:
this:_skill - #7:keep_range line 4:
this:_skill - #7:_skill line 14:
this:_skill
Source
1":_skill(home,node,kill_leaf)"; 2"home:_kill's node and all descendants, home:(kill_leaf)'s all leaves"; 3if (caller != this) 4return E_PERM; 5endif 6{home, node, kill_leaf} = args; 7try 8{height, subtrees} = home:_get(node) || {0, {}}; 9except (E_PROPNF) 10return; 11endtry 12if (height) 13for kid in (subtrees) 14this:_skill(home, kid[1], kill_leaf); 15endfor 16elseif (kill_leaf) 17for kid in (subtrees) 18this:_call(home, kill_leaf, kid); 19endfor 20endif 21home:_kill(node);
_extract
Referenced by
- #7:extract_range line 2:
this:_extract - #7:delete_range line 2:
this:_extract - #7:keep_range line 2:
this:_extract
Source
1":_extract(home,tree,first,last) => {newtree,extraction}"; 2if (caller != this) 3return E_PERM; 4endif 5home = args[1]; 6if (!(tree = args[2])) 7return {{}, {}}; 8endif 9before = max(0, args[3] - 1); 10end = min(tree[2], args[4]); 11if ((end <= 0) || (before >= end)) 12return {tree, {}}; 13endif 14height = home:_get(tree[1])[1]; 15if (end < tree[2]) 16r = this:_split(home, height, end, tree); 17if (before) 18l = this:_split(home, height, before, r[1]); 19extract = l[2]; 20newtree = this:_merge(home, l[1], r[2]); 21else 22extract = r[1]; 23newtree = r[2]; 24endif 25elseif (before) 26l = this:_split(home, height, before, tree); 27extract = l[2]; 28newtree = l[1]; 29else 30return {{}, tree}; 31endif 32return {this:_scrunch(home, newtree), this:_scrunch(home, extract)};
_merge
Referenced by
- #7:insert_after line 10:
this:_merge - #7:insert_after line 12:
this:_merge - #7:insert_after line 15:
this:_merge - #7:insert_after line 15:
this:_merge - #7:_extract line 20:
this:_merge
Source
1"_merge(home,ltree,rtree) => newtree"; 2"assumes ltree and rtree to be nonempty."; 3if (caller != this) 4return E_PERM; 5endif 6{home, lnode, rnode} = args; 7lh = home:_get(lnode[1])[1]; 8rh = home:_get(rnode[1])[1]; 9if (lh > rh) 10return this:_rmerge(home, lnode, rnode); 11endif 12for h in [lh + 1..rh] 13lnode[1] = home:_make(h, {lnode}); 14endfor 15m = this:_smerge(home, rh, lnode, rnode); 16return (length(m) <= 1) ? m[1] | {home:_make(rh + 1, m), m[1][2] + m[2][2], m[1][3]};
_smerge
Referenced by
- #7:_merge line 15:
this:_smerge - #7:_smerge line 12:
this:_smerge - #7:_rmerge line 22:
this:_smerge
Source
1"_smerge(home, height, ltree, rtree) =>{ltree[,rtree]}"; 2"assumes ltree and rtree are at the given height."; 3"merges the trees if the combined number of children is <= maxfanout"; 4"otherwise returns two trees where ltree is guaranteed minfanout children and rtree is guaranteed the minimum of minfanout and however many children it started with."; 5if (caller != this) 6return E_PERM; 7endif 8{home, height, ltree, rtree} = args; 9llen = length(lkids = home:_get(ltree[1])[2]); 10rlen = length(rkids = home:_get(rtree[1])[2]); 11if (height) 12m = this:_smerge(home, height - 1, lkids[llen], rkids[1]); 13mlen = length(mkids = {@listdelete(lkids, llen), @m, @listdelete(rkids, 1)}); 14if (mlen <= this.maxfanout) 15home:_put(ltree[1], height, mkids); 16home:_kill(rtree[1]); 17ltree[2] = ltree[2] + rtree[2]; 18return {ltree}; 19else 20S = max(llen - 1, (mlen + 1) / 2); 21home:_put(ltree[1], height, mkids[1..S]); 22home:_put(rtree[1], height, mkids[S + 1..$]); 23xfer = -lkids[llen][2]; 24for k in (mkids[llen..S]) 25xfer = xfer + k[2]; 26endfor 27ltree[2] = ltree[2] + xfer; 28rtree[2] = rtree[2] - xfer; 29rtree[3] = mkids[S + 1][3]; 30return {ltree, rtree}; 31endif 32elseif ((llen * 2) >= this.maxfanout) 33return {ltree, rtree}; 34elseif (this.maxfanout < (llen + rlen)) 35T = ((rlen - llen) + 1) / 2; 36home:_put(ltree[1], 0, {@lkids, @rkids[1..T]}); 37home:_put(rtree[1], 0, rkids[T + 1..rlen]); 38ltree[2] = ltree[2] + T; 39rtree[2] = rtree[2] - T; 40rtree[3] = home:_ord(rkids[T + 1]); 41return {ltree, rtree}; 42else 43home:_put(ltree[1], 0, {@lkids, @rkids}); 44home:_kill(rtree[1]); 45ltree[2] = ltree[2] + rtree[2]; 46return {ltree}; 47endif
_split
Referenced by
- #7:insert_after line 14:
this:_split - #7:_extract line 16:
this:_split - #7:_extract line 18:
this:_split - #7:_extract line 26:
this:_split - #7:_split line 14:
this:_split
Source
1"_split(home, height,lmax,ltree[,@rtrees]}) => {ltree,[mtree,]@rtrees}"; 2"ltree is split after the lmax'th leaf, the righthand portion grafted onto the leftmost of the rtrees, if possible. Otherwise we create a new tree mtree, stealing from rtrees[1] if necessary."; 3"Assumes 1<=lmax<ltree[2]"; 4if (caller != this) 5return E_PERM; 6endif 7{home, height, lmax, ltree, @rtrees} = args; 8llen = length(lkids = home:_get(ltree[1])[2]); 9rlen = length(rkids = rtrees ? home:_get(rtrees[1][1])[2] | {}); 10if (height) 11ik = this:_listfind_nth(lkids, lmax); 12if (ik[2]) 13llast = ik[1]; 14m = this:_split(home, height - 1, ik[2], lkids[llast], @lkids[llast + 1..llen], @rkids); 15lkids[llast] = m[1]; 16mkids = listdelete(m, 1); 17else 18llast = ik[1] - 1; 19mkids = {@lkids[ik[1]..llen], @rkids}; 20endif 21home:_put(ltree[1], height, lkids[1..llast]); 22mlen = length(mkids); 23if ((((mlen - rlen) * 2) >= this.maxfanout) || (!rtrees)) 24"...residue left over from splitting ltree can stand by itself..."; 25return {listset(ltree, lmax, 2), {home:_make(height, mkids[1..mlen - rlen]), ltree[2] - lmax, mkids[1][3]}, @rtrees}; 26elseif (mlen <= this.maxfanout) 27"...residue left over from splitting ltree fits in rtrees[1]..."; 28home:_put(rtrees[1][1], height, mkids); 29rtrees[1][2] = (ltree[2] - lmax) + rtrees[1][2]; 30rtrees[1][3] = mkids[1][3]; 31return {listset(ltree, lmax, 2), @rtrees}; 32else 33"...need to steal from rtrees[1]..."; 34if (llast < llen) 35msize = ltree[2] - lmax; 36R = (mlen - rlen) + 1; 37else 38msize = 0; 39R = 1; 40endif 41for k in (mkids[R..mlen / 2]) 42msize = msize + k[2]; 43endfor 44home:_put(rtrees[1][1], height, mkids[(mlen / 2) + 1..mlen]); 45rtrees[1][2] = (rtrees[1][2] + ltree[2]) - (lmax + msize); 46rtrees[1][3] = mkids[(mlen / 2) + 1][3]; 47return {listset(ltree, lmax, 2), {home:_make(height, mkids[1..mlen / 2]), msize, mkids[1][3]}, @rtrees}; 48endif 49else 50home:_put(ltree[1], 0, lkids[1..lmax]); 51if ((((llen - lmax) * 2) >= this.maxfanout) || (!rtrees)) 52"...residue left over from splitting ltree can stand by itself..."; 53return {listset(ltree, lmax, 2), {home:_make(0, lkids[lmax + 1..llen]), llen - lmax, home:_ord(lkids[lmax + 1])}, @rtrees}; 54elseif ((mlen = (rlen + llen) - lmax) <= this.maxfanout) 55"...residue left over from splitting ltree fits in rtrees[1]..."; 56home:_put(rtrees[1][1], 0, {@lkids[lmax + 1..llen], @rkids}); 57rtrees[1][2] = mlen; 58rtrees[1][3] = home:_ord(lkids[lmax + 1]); 59return {listset(ltree, lmax, 2), @rtrees}; 60else 61"...need to steal from rtrees[1]..."; 62home:_put(rtrees[1][1], 0, rkids[(R = ((rlen - llen) + lmax) / 2) + 1..rlen]); 63rtrees[1][2] = (mlen + 1) / 2; 64rtrees[1][3] = home:_ord(rkids[R + 1]); 65return {listset(ltree, lmax, 2), {home:_make(0, {@lkids[lmax + 1..llen], @rkids[1..R]}), mlen / 2, home:_ord(lkids[lmax + 1])}, @rtrees}; 66endif 67endif
_rmerge
Referenced by
- #7:_merge line 10:
this:_rmerge
Source
1":_rmerge(home, tree, insertree) => newtree "; 2"(newtree is tree with insertree appended to the right)"; 3"insertree is assumed to be of height < tree"; 4if (caller != this) 5return E_PERM; 6endif 7{home, tree, insert} = args; 8if (!tree) 9return insert; 10elseif (!insert) 11return tree; 12endif 13iheight = home:_get(insert[1])[1]; 14rspine = {}; 15for i in [iheight + 1..home:_get(tree[1])[1]] 16kids = home:_get(tree[1])[2]; 17tlen = length(kids); 18rspine = {{tree, tlen}, @rspine}; 19tree = kids[tlen]; 20endfor 21isize = insert[2]; 22m = this:_smerge(home, iheight, tree, insert); 23for h in [1..length(rspine)] 24plen = rspine[h][2]; 25parent = rspine[h][1]; 26hgp = home:_get(parent[1]); 27if (((length(m) - 1) + plen) > this.maxfanout) 28home:_put(parent[1], @listset(hgp, listset(hgp[2], m[1], plen), 2)); 29parent[2] = (parent[2] + isize) - m[2][2]; 30m = {parent, listset(m[2], home:_make(h + iheight, {m[2]}), 1)}; 31else 32home:_put(parent[1], @listset(hgp, {@hgp[2][1..plen - 1], @m}, 2)); 33for p in (rspine[h + 1..length(rspine)]) 34parent[2] = parent[2] + isize; 35tree = parent; 36parent = p[1]; 37hgp = home:_get(parent[1]); 38home:_put(parent[1], @listset(hgp, listset(hgp[2], tree, p[2]), 2)); 39endfor 40return listset(parent, parent[2] + isize, 2); 41endif 42endfor 43return {home:_make((length(rspine) + iheight) + 1, m), m[1][2] + m[2][2], m[1][3]};
_scrunch
Referenced by
- #7:_extract line 32:
this:_scrunch - #7:_extract line 32:
this:_scrunch
Source
1":_scrunch(home,tree) => newtree"; 2"decapitates single-child nodes from the top of the tree, returns new root."; 3if (caller != this) 4return E_PERM; 5endif 6if (tree = args[2]) 7home = args[1]; 8while ((n = home:_get(tree[1]))[1] && (length(n[2]) == 1)) 9home:_kill(tree[1]); 10tree = n[2][1]; 11endwhile 12endif 13return tree;
_listfind_nth
Referenced by
- #7:start line 11:
this:_listfind_nth - #7:_set_nth line 8:
this:_listfind_nth - #7:_split line 11:
this:_listfind_nth
Source
1"_listfind_nth(nodelist,key) => {i,k} where i is the smallest i such that the sum of the first i elements of intlist is > key, and k==key - sum(first i-1 elements)."; 2"1 <= i <= length(intlist)+1"; 3{lst, key} = args; 4for i in [1..length(lst)] 5key = key - lst[i][2]; 6if (0 > key) 7return {i, key + lst[i][2]}; 8endif 9endfor 10return {length(lst) + 1, key};
_insertfirst
Referenced by
none
Source
1if (caller != this) 2return E_PERM; 3endif
debug
Referenced by
none
Source
1return $perm_utils:controls(caller_perms(), this) ? this:(args[1])(@listdelete(args, 1)) | E_PERM;
_call
Referenced by
- #7:_find_ord line 13:
this:_call - #7:_find_ord line 20:
this:_call - #7:_skill line 18:
this:_call
Source
1":_call(home,verb,@vargs) calls home:verb(@vargs) with $no_one's perms"; 2set_task_perms($no_one); 3if (caller != this) 4raise(E_PERM); 5endif 6{home, vb, @vargs} = args; 7return home:(vb)(@vargs);