2002/03/21 01:19:33

[org.ibex.core.git] / src / org / xwt / Box.java

// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
package org.xwt;

import java.io.*;
import java.net.*;
import java.util.*;
import org.xwt.util.*;
import org.mozilla.javascript.*;

/**
 *  <p>
 *  Encapsulates the data for a single XWT box as well as all layout
 *  rendering logic.
 *  </p>
 *
 *  <p>
 *  This is the real meat of XWT. Part of its monolithic design is for
 *  performance reasons: deep inheritance heirarchies are slow, and
 *  neither javago nor GCJ can inline across class boundaries.
 *  </p>
 *
 *  <p>The rendering process consists of two phases:</p>
 *
 *  <ol><li> <b>Prerendering pipeline</b>: a set of methods that
 *           traverse the tree (DFS, postorder) immediately before
 *           rendering. These methods calculate the appropriate size
 *           and position for all boxes. If no changes requiring a
 *           re-prerender have been made to a box or any of its
 *           descendants, <tt>needs_prerender</tt> will be false, and the box
 *           and its descendants will be skipped.
 *
 *      <li> <b>Rendering pipeline</b>: a second set of methods that
 *           traverses the tree (DFS, preorder) and renders each Box
 *           onto the associated Surface. The render() method takes a
 *           region (x,y,w,h) as an argument, and will only render
 *           onto pixels within that region. Boxes which lie
 *           completely outside that region will be skipped.
 *  </ol>
 *
 *  <p>
 *  Either of these two phases may <i>abort</i> at any time by setting
 *  <tt>surface.abort</tt> to true. Currently, there are two reasons
 *  for aborting: a <tt>SizeChange</tt> or <tt>PosChange</tt> was
 *  triggered in the prerender phase (which ran scripts which modified
 *  the boxtree's composition, requiring another prerender pass), or
 *  else the user resized the surface. In either case, the
 *  [pre]rendering process is halted as soon as possible and
 *  re-started from the beginning.
 *  </p>
 *
 *  <p>Why are these done as seperate passes over the box tree?</p>
 * 
 *  <ol><li> Sometimes we need to make several trips through
 *           <tt>prerender()</tt?, as a result of <tt>SizeChange</tt>
 *           or <tt>PosChange</tt>. Calling <tt>prerender()</tt> is
 *           cheap; calling <tt>render()</tt> is expensive.
 *
 *      <li> Even if no <tt>SizeChange</tt> or <tt>PosChange</tt> traps are
 *           triggered, updates to the size and position of boxes in
 *           the prerender phase can cause additional regions to be
 *           added to the dirty list. If the prerender and render
 *           passes were integrated, this might cause some screen
 *           regions to be painted twice (or more) in a single pass,
 *           which hurts performance.
 *  </ol>
 *
 *  <p>
 *  A box's <tt>_cmin_*</tt> variables hold the minimum possible
 *  dimensions of this box, taking into account the size of its
 *  children (and their children). The cmin variables must be kept in
 *  sync with its other geometric properties and the geometric
 *  properties of its children at all times -- they are not
 *  periodically recomputed during the [pre]rendering process, as size
 *  and pos are. If any data changes which might invalidate the cmin,
 *  the method <tt>sync_cmin_to_children()</tt> must be invoked
 *  immediately.
 *  </p>
 *
 *  <p>
 *  A note on coordinates: the Box class represents regions
 *  internally as x,y,w,h tuples, even though the DoubleBuffer class
 *  uses x1,y1,x2,y2 tuples.
 * </p>
 */
public final class Box extends JSObject {


    // Static Data //////////////////////////////////////////////////////////////

    /** a pool of one-element Object[]'s */
    private static Queue singleObjects = new Queue(100);

    /** caches images, keyed on resource name or url */
    public static Hash pictureCache = new Hash();

    /** cache of border objects */
    static Hash bordercache = new Hash();

    /** stores image names, keyed on image object */
    static Hash imageToNameMap = new Hash();

    /** the empty object, used for get-traps */
    private static Object[] emptyobj = new Object[] { };


    // Instance Data: Templates ////////////////////////////////////////////////////////

    /** the unresolved name of the first template applied to this node [ignoring preapply's], or null if this template was specified anonymously */
    String templatename = null;

    /** the importlist which was used to resolve <tt>templatename</tt>, or null if this template was specified anonymously */
    String[] importlist = Template.defaultImportList;

    /** the template instance that resulted from resolving <tt>templatename</tt> using <tt>importlist</tt>, or the anonymous template applied */
    Template template = null;


    // Instance Data: Geometry ////////////////////////////////////////////////////////

    /** The number of elements in the geom array */
    public static final int NUMINTS = 10;

    /** The maximum <i>defined</i> width and height of this box */
    public static final int dmax = 0;     
    private short _dmax_0 = 0;
    private short _dmax_1 = 0;
    public final short dmax(int axis) { return axis == 0 ? _dmax_0 : _dmax_1; }

    /** The minimum <i>defined</i> width and height of this box */
    public static final int dmin = 1;     
    private short _dmin_0 = 0;
    private short _dmin_1 = 0;
    public final short dmin(int axis) { return axis == 0 ? _dmin_0 : _dmin_1; }
    
    /** The minimum <i>calculated</i> width and height of this box -- unlike dmin, this takes childrens' sizes into account */
    public static final int cmin = 2;     
    private short _cmin_0 = 0;
    private short _cmin_1 = 0;
    public final short cmin(int axis) { return axis == 0 ? _cmin_0 : _cmin_1; }

    /** The position of this box, relitave to the parent */
    public static final int abs = 3;      
    private short _abs_0 = 0;
    private short _abs_1 = 0;
    public final short abs(int axis) { return axis == 0 ? _abs_0 : _abs_1; }

    /** The absolute position of this box (ie relitave to the root); set by the parent */
    public static final int pos = 4;      
    private short _pos_0 = 0;
    private short _pos_1 = 0;
    public final short pos(int axis) { return axis == 0 ? _pos_0 : _pos_1; }

    /** The actual size of this box; set by the parent. */
    public static final int size = 5;     
    short _size_0 = 0;
    short _size_1 = 0;
    public final short size(int axis) { return axis == 0 ? _size_0 : _size_1; }

    /** The old actual absolute position of this box (ie relitave to the root) */
    public static final int oldpos = 6;   
    private short _oldpos_0 = 0;
    private short _oldpos_1 = 0;
    public final short oldpos(int axis) { return axis == 0 ? _oldpos_0 : _oldpos_1; }

    /** The old actual size of this box */
    public static final int oldsize = 7;  
    private short _oldsize_0 = 0;
    private short _oldsize_1 = 0;
    public final short oldsize(int axis) { return axis == 0 ? _oldsize_0 : _oldsize_1; }

    /** The padding along each edge for this box */
    public static final int pad = 8;      
    private short _pad_0 = 0;
    private short _pad_1 = 0;
    public final short pad(int axis) { return axis == 0 ? _pad_0 : _pad_1; }

    /** The dimensions of the text in this box */
    public static final int textdim = 9;
    private short _textdim_0 = 0;
    private short _textdim_1 = 0;
    public final short textdim(int axis) { return axis == 0 ? _textdim_0 : _textdim_1; }


    // Instance Data /////////////////////////////////////////////////////////////////

    /** This box's mouseinside property, as defined in the reference */
    boolean mouseinside = false;

    /** If redirect is enabled, this holds the Box redirected to */
    Box redirect = this;

    /** the Box's font -- you must call textupdate() after changing this */
    String font = Platform.getDefaultFont();

    /** The surface for us to render on; null if none; INVARIANT: surface == getParent().surface */
    Surface surface = null;

    /** Our alignment: top/left == -1, center == 0, bottom/right == +1 */
    byte align = 0;

    /** Our background image; to set this, use setImage() */
    public Picture image;

    /** The flex for this box */
    int flex = 1;

    /** The orientation, horizontal == 0, vertical == 1 */
    byte o = 0;

    /** The opposite of the orientation */
    byte xo = 1;

    /** The id of this Box */
    public String id = "";

    /** The text of this Box -- you must call textupdate() after changing this */
    String text = "";

    /** The color of the text in this Box in 00RRGGBB form -- default is black */
    int textcolor = 0xFF000000;

    /** The background color of this box in AARRGGBB form -- default is clear; alpha is all-or-nothing */
    int color = 0x00000000;

    /** Holds four "strip images" -- 0=top, 1=bottom, 2=left, 3=right, 4=all */
    Picture[] border = null;
        
    /**
     *  The dirty() method walks up the tree, clipping the region being dirtied to each parent -- if this value is less than or
     *  equal to surface.dirtiedTimeStamp, it means that the entire screen region covered by this box has been dirtied, so dirty()'s on
     *  children can short-circuit.
     */
    int dirtiedTimeStamp = 0;

    /** true iff the box's background image should be tiled */
    boolean tile = false;

    /** True iff the Box is invisible */
    public boolean invisible = false;

    /** If true, the Box will force its own size to the natural size of its background image */
    boolean sizetoimage = false;

    /** If true, the box will shrink to the smallest vertical size possible */
    boolean vshrink = false;

    /** If true, the box will shrink to the smallest horizontal size possible */
    boolean hshrink = false;

    /** If true, the box will be positioned absolutely */
    boolean absolute = false;

    /** True iff the Box must be run through the prerender() pipeline before render()ing;<br>
     *  INVARIANT: if (needs_prerender) then getParent().needs_prerender. **/
    boolean needs_prerender = true;

    /** The cursor for this Box -- only meaningful on the root Box */
    public String cursor = null;

    /** Any traps placed on this Box */
    public Hash traps = null;


    // Instance Data: IndexOf  ////////////////////////////////////////////////////////////

    /** The indexof() Function; created lazily */
    public Function indexof = null;
    public Function indexof() {
        if (indexof == null) indexof = new IndexOf();
        return indexof;
    }

    /** a trivial private class to serve as the box.indexof function object */
    private class IndexOf extends JSObject implements Function {
        public IndexOf() { this.setSeal(true); }
        public Scriptable construct(Context cx, Scriptable scope, java.lang.Object[] args) { return null; }
        public Object call(Context cx, Scriptable scope, Scriptable thisObj, java.lang.Object[] args) throws JavaScriptException {
            if (args == null || args.length != 1 || args[0] == null || !(args[0] instanceof Box)) return new Integer(-1);
            Box b = (Box)args[0];
            if (b.getParent() != Box.this) {
                if (redirect == null || redirect == Box.this) return new Integer(-1);
                return Box.this.redirect.indexof().call(cx, scope, thisObj, args);
            }
            return new Integer(b.getIndexInParent());
        }
    }


    // Methods which enforce/preserve invariants ////////////////////////////////////////////

    /** This method MUST be used to change geometry values -- it ensures that certain invariants are preserved. */
    public final void set(int which, int axis, int newvalue) { set(which, axis, (short)newvalue); }
    public final void set(int which, int axis, short newvalue) {

        // if this Box is the root of the Surface, notify the Surface of size changes
        if (getParent() == null && surface != null && which == size)
            surface._setSize(axis == 0 ? newvalue : size(0), axis == 1 ? newvalue : size(1));

        switch(which) {
        case dmin: if (dmin(axis) == newvalue) return; if (axis == 0) _dmin_0 = newvalue; else _dmin_1 = newvalue; break;
        case dmax: if (dmax(axis) == newvalue) return; if (axis == 0) _dmax_0 = newvalue; else _dmax_1 = newvalue; break;
        case cmin: if (cmin(axis) == newvalue) return; if (axis == 0) _cmin_0 = newvalue; else _cmin_1 = newvalue; break;
        case abs: if (abs(axis) == newvalue) return; if (axis == 0) _abs_0 = newvalue; else _abs_1 = newvalue; break;
        case pos: if (pos(axis) == newvalue) return; if (axis == 0) _pos_0 = newvalue; else _pos_1 = newvalue; break;
        case size: if (size(axis) == newvalue) return; if (axis == 0) _size_0 = newvalue; else _size_1 = newvalue; break;
        case oldpos: if (oldpos(axis) == newvalue) return; if (axis == 0) _oldpos_0 = newvalue; else _oldpos_1 = newvalue; break;
        case oldsize: if (oldsize(axis) == newvalue) return; if (axis == 0) _oldsize_0 = newvalue; else _oldsize_1 = newvalue; break;
        case pad: if (pad(axis) == newvalue) return; if (axis == 0) _pad_0 = newvalue; else _pad_1 = newvalue; break;
        case textdim: if (textdim(axis) == newvalue) return; if (axis == 0) _textdim_0 = newvalue; else _textdim_1 = newvalue; break;
        default: return;
        }

        // size must always agree with dmin/dmax
        if (which == dmin) set(size, axis, max(size(axis), newvalue));
        if (which == dmax) set(size, axis, min(size(axis), newvalue));

        // keep obedience to shrink directives
        if (which == cmin || which == textdim || which == pad || which == dmin)
            if ((hshrink && axis == 0) || (vshrink && axis == 1))
                set(dmax, axis, max(cmin(axis), (textdim(axis) + 2 * pad(axis)), dmin(axis)));

        // keep cmin in line with dmin/dmax/textdim
        if (which == dmax || which == dmin || which == textdim || which == pad || which == cmin)
            set(cmin, axis,
                max(
                    min(cmin(axis), dmax(axis)),
                    dmin(axis),
                    min(dmax(axis), textdim(axis) + 2 * pad(axis))
                    )
                );
        
        // if the pad changes, update cmin
        if (which == pad) sync_cmin_to_children();

        // if the cmin changes, we need to be re-prerendered
        if (which == cmin) mark_for_prerender(); 

        // if the absolute position of a box changes, its parent needs to be re-prerendered (to update the child's position)
        if (which == abs && getParent() != null) getParent().mark_for_prerender();

        // if our cmin changes, then our parent's needs to be recalculated
        if (getParent() != null && which == cmin) {
            mark_for_prerender();
            getParent().sync_cmin_to_children();
        }

    }

    /** Marks this node and all its ancestors so that they will be prerender()ed */
    public final void mark_for_prerender() {
        if (needs_prerender) return;
        needs_prerender = true;
        if (getParent() != null) getParent().mark_for_prerender();
    }

    /** Ensures that cmin is in sync with the cmin's of our children. This should be called whenever a child is added or
     *  removed, as well as when our pad is changed. */
    final void sync_cmin_to_children() {
        short co = (short)(2 * pad(o));
        short cxo = (short)(2 * pad(xo));
        
        for(Box bt = getChild(0); bt != null; bt = bt.nextSibling()) {
            if (bt.invisible || bt.absolute) continue;
            co += bt.cmin(o);
            cxo = (short)max(bt.cmin(xo) + 2 * pad(xo), cxo);
        }
        
        set(cmin, o, co);
        set(cmin, xo, cxo);
    }

    /** must be called after changes to <tt>image</tt> or <tt>border</tt> if sizetoimage is true */
    public void syncSizeToImage() {
        set(dmax, 0, (image == null ? 0 : image.getWidth()) + (border == null ? 0 : border[2].getWidth()) * 2);
        set(dmax, 1, (image == null ? 0 : image.getHeight()) + (border == null ? 0 : border[0].getHeight()) * 2);
        set(dmin, 0, (image == null ? 0 : image.getWidth()) + (border == null ? 0 : border[2].getWidth()) * 2);
        set(dmin, 1, (image == null ? 0 : image.getHeight()) + (border == null ? 0 : border[0].getHeight()) * 2);
    }

    /** This must be called when font or text is changed */
    void textupdate() {
        if (text.equals("")) {
            set(textdim, 0, 0);
            set(textdim, 1, 0);
        } else {
            XWF xwf = XWF.getXWF(font);
            if (xwf == null) {
                set(textdim, 0, Platform.stringWidth(font, text));
                set(textdim, 1, (Platform.getMaxAscent(font) + Platform.getMaxDescent(font)));
            } else {
                set(textdim, 0, xwf.stringWidth(text));
                set(textdim, 1, (xwf.getMaxAscent() + xwf.getMaxDescent()));
            }
        }
    }


    // Instance Methods /////////////////////////////////////////////////////////////////////

    /** Changes the Surface that this Box draws on. */    
    protected void setSurface(Surface newSurface) {
        if (surface == newSurface) return;
        mouseinside = false;
        if ((is_trapped("KeyPressed") || is_trapped("KeyReleased")) && surface != null)
            surface.keywatchers.removeElement(this);
        surface = newSurface;
        if ((is_trapped("KeyPressed") || is_trapped("KeyReleased")) && surface != null)
            surface.keywatchers.addElement(this);
        for(Box i = getChild(0); i != null; i = i.nextSibling()) i.setSurface(surface);
        if (numChildren() == 0) mark_for_prerender();
    }

    /** loads the image described by string str, possibly blocking for a network load */
    private static ImageDecoder getImage(String str) {
        ImageDecoder ret = null;
        boolean ispng = false;

        if (str.indexOf(':') == -1) {
            String s = str;
            byte[] b = Resources.getResource(Resources.resolve(s + ".png", null));
            if (b == null) return null;
            return PNG.decode(new ByteArrayInputStream(b), str);
            
        } else {
            Thread thread = Thread.currentThread();
            if (!(thread instanceof ThreadMessage)) {
                if (Log.on) Log.log(Box.class, "HTTP images can not be loaded from the foreground thread");
                return null;
            }
            ThreadMessage mythread = (ThreadMessage)thread;
            mythread.setPriority(Thread.MIN_PRIORITY);
            mythread.done.release();
            try {
                if (str.endsWith(".png")) ret = PNG.decode(Platform.urlToInputStream(new URL(str)), str);
                else ret = GIF.decode(Platform.urlToInputStream(new URL(str)), str);
                return ret;

            } catch (IOException e) {
                if (Log.on) Log.log(Box.class, "error while trying to load an image from " + str);
                if (Log.on) Log.log(Box.class, e);
                return null;

            } finally {
                MessageQueue.add(mythread);
                mythread.setPriority(Thread.NORM_PRIORITY);
                mythread.go.block();
            }
        }
    }

    /** gets an Image using getImage(), adds it to the cache, and creates a Picture from it */
    public static Picture getPicture(String os) {
        Picture ret = null;
        ret = (Picture)pictureCache.get(os);
        if (ret != null) return ret;
        ImageDecoder id = getImage(os);
        if (id == null) return null;
        ret = Platform.createPicture(id);
        pictureCache.put(os, ret);
        imageToNameMap.put(ret, os);
        return ret;
    }

    /** Sets the image; argument should be a fully qualified s name or an URL */
    void setImage(String s) {
        if ((s == null && image == null) || (s != null && image != null && s.equals(imageToNameMap.get(image)))) return;
        if (s == null || s.equals("")) {
            image = null;
            if (sizetoimage) syncSizeToImage();
            dirty();
        } else {
            image = getPicture(s);
            if (image == null) {
                if (Log.on) Log.log(Box.class, "unable to load image " + s + " at " +
                                    Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
                return;
            }
            if (sizetoimage) syncSizeToImage();
            dirty();
        }
    }
    
    /** Sets the border; argument should be a fully qualified resource name or an URL */
    void setBorder(String s) {
        if ((s == null && border == null) || (s != null && border != null && s.equals(imageToNameMap.get(border)))) return;
        if (s == null || s.equals("")) {
            border = null;
            if (sizetoimage) syncSizeToImage();
            dirty();

        } else {
            border = (Picture[])bordercache.get(s);
            if (border == null) {
                ImageDecoder id = getImage(s);
                if (id == null) {
                    if (Log.on) Log.log(this, "unable to load border image " + s + " at " +
                                    Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
                    return;
                }
                int[] data = id.getData();
                int w = id.getWidth();
                int h = id.getHeight();
                int hpad = w / 2;
                int vpad = h / 2;

                int[][] dat = new int[4][];
                dat[0] = new int[100 * vpad];
                dat[1] = new int[100 * vpad];
                dat[2] = new int[100 * hpad];
                dat[3] = new int[100 * hpad];

                for(int i=0; i<100; i++) {
                    for(int j=0; j<vpad; j++) {
                        dat[0][i + j * 100] = data[hpad + j * w];
                        dat[1][i + (vpad - j - 1) * 100] = data[hpad + (h - j - 1) * w];
                    }
                    for(int j=0; j<hpad; j++) {
                        dat[2][j + i * hpad] = data[j + vpad * w];
                        dat[3][hpad - j - 1 + i * hpad] = data[w - j - 1 + vpad * w];
                    }
                }

                border = new Picture[5];
                border[0] = Platform.createPicture(dat[0], 100, vpad);
                border[1] = Platform.createPicture(dat[1], 100, vpad);
                border[2] = Platform.createPicture(dat[2], hpad, 100);
                border[3] = Platform.createPicture(dat[3], hpad, 100);
                border[4] = (Picture)pictureCache.get(s);
                if (border[4] == null) {
                    border[4] = Platform.createPicture(data, w, h);
                    pictureCache.put(s, border[4]);
                    imageToNameMap.put(border[4], s);
                }
                bordercache.put(s, border);
            }
            if (sizetoimage) syncSizeToImage();
            dirty();
        }
    }

    /** returns true if the property has a trap on it */
    boolean is_trapped(String property) {
        if (traps == null) {
            return false;
        } else {
            Object gc = traps.get(property);
            return (gc != null &&
                    !(gc instanceof org.mozilla.javascript.Undefined) &&
                    gc != org.mozilla.javascript.Scriptable.NOT_FOUND);
        }
    }
    
    /** Adds the node's current actual geometry to the Surface's dirty list */
    void dirty() {
        dirty(pos(0), pos(1), size(0), size(1));
        if (surface != null) dirtiedTimeStamp = surface.dirtiedTimeStamp + 1;
    }

    /** Adds the intersection of (x,y,w,h) and the node's current actual geometry to the Surface's dirty list */
    final void dirty(int x, int y, int w, int h) {
        for(Box cur = this; cur != null; cur = cur.getParent()) {
            if (surface != null && cur.dirtiedTimeStamp > surface.dirtiedTimeStamp && cur.dirtiedTimeStamp < Integer.MAX_VALUE - 1) return;
            w = min(x + w, cur.pos(0) + cur.size(0)) - max(x, cur.pos(0));
            h = min(y + h, cur.pos(1) + cur.size(1)) - max(y, cur.pos(1));
            x = max(x, cur.pos(0));
            y = max(y, cur.pos(1));
            if (w <= 0 || h <= 0) return;
        }
        if (surface != null) surface.dirty(x, y, w, h);
    }

    /**
     *  Given an old and new mouse position, this will update <tt>mouseinside</tt> and check
     *  to see if this node requires any Enter, Leave, or Move notifications.
     *
     *  @param forceleave set to true by the box's parent if the mouse is inside an older
     *                    sibling, which is covering up this box.
     */
    void Move(int oldmousex, int oldmousey, int mousex, int mousey) { Move(oldmousex, oldmousey, mousex, mousey, false); }
    void Move(int oldmousex, int oldmousey, int mousex, int mousey, boolean forceleave) {

        boolean wasinside = mouseinside;
        boolean isinside = !invisible && inside(mousex, mousey) && !forceleave;
        mouseinside = isinside;

        if (!wasinside && !isinside) return;
        
        if (!wasinside && isinside && is_trapped("Enter")) put("Enter", null, this);
        else if (wasinside && !isinside && is_trapped("Leave")) put("Leave", null, this);
        else if (wasinside && isinside && (mousex != oldmousex || mousey != oldmousey) && is_trapped("Move")) put("Move", null, this);

        if (isinside && cursor != null && surface != null) surface.cursor = cursor;

        // if the mouse has moved into our padding region, it is considered 'outside' all our children
        if (!(mousex >= pos(0) + pad(0) && mousey >= pos(1) + pad(1) &&
              mousex < pos(0) + size(0) - pad(0) && mousey < pos(1) + size(1) + pad(1))) forceleave = true;

        for(Box b = getChild(numChildren() - 1); b != null; b = b.prevSibling()) {
            b.Move(oldmousex, oldmousey, mousex, mousey, forceleave);
            if (b.inside(mousex, mousey)) forceleave = true;
        }
    }

    /** creates a new box from an anonymous template; <tt>ids</tt> is passed through to Template.apply() */
    Box(Template anonymous, Vec pboxes, Vec ptemplates) {
        super(true);
        set(dmax, 0, Short.MAX_VALUE);
        set(dmax, 1, Short.MAX_VALUE);
        template = anonymous;
        template.apply(this, pboxes, ptemplates);
        templatename = null;
        importlist = null;
    }

    /** creates a new box from an unresolved templatename and an importlist; use "box" for an untemplatized box */
    public Box(String templatename, String[] importlist) {
        super(true);
        set(dmax, 0, Short.MAX_VALUE);
        set(dmax, 1, Short.MAX_VALUE);
        this.importlist = importlist;
        template = "box".equals(templatename) ? null : Template.getTemplate(templatename, importlist);
        this.templatename = templatename;
        if (template != null) {
            template.apply(this, null, null);
            if (redirect == this && !"self".equals(template.redirect)) redirect = null;
        }
    }
    

    // Prerendering Pipeline ///////////////////////////////////////////////////////////////

    /** Checks if the Box's size has changed, dirties it if necessary, and makes sure childrens' sizes are up to date */
    void prerender() {

        if (getParent() == null) {
            set(pos, 0, 0);
            set(pos, 1, 0);
        }

        if (pos(0) != oldpos(0) || pos(1) != oldpos(1) || size(0) != oldsize(0) || size(1) != oldsize(1)) {
            needs_prerender = true;
            check_geometry_changes();
        }

        if (!needs_prerender) return; 
        needs_prerender = false;
        if (numChildren() == 0) return;

        int sumchildren = sizeChildren();
        positionChildren(pos(o) + pad(o) + max(0, size(o) - 2 * pad(o) - sumchildren) / 2);

        for(Box b = getChild(0); b != null; b = b.nextSibling()) {
            b.prerender();
            if (surface.abort) {
                mark_for_prerender();
                return;
            }
        }
    }

    /** if the size or position of a box has changed, dirty() the appropriate regions and possibly send Enter/Leave/SizeChange/PosChange */
    private void check_geometry_changes() {

        // FASTPATH: if we haven't moved position (just changed size), and we're not a stretched image:
        if (oldpos(0) == pos(0) && oldpos(1) == pos(1) && (image == null || tile)) {
            
            int bw = border == null ? 0 : border[2].getWidth();
            int bh = border == null ? 0 : border[0].getHeight();
            
            // dirty only the *change* in the area we cover, both on ourselves and on our parent
            for(Box cur = this; cur != null && (cur == this || cur == this.getParent()); cur = cur.getParent()) {
                cur.dirty(pos(0) + min(oldsize(0) - bw, size(0) - bw),
                          pos(1),
                          Math.abs(oldsize(0) - size(0)) + bw,
                          max(oldsize(1), size(1)));
                cur.dirty(pos(0),
                          pos(1) + min(oldsize(1) - bh, size(1) - bh),
                          max(oldsize(0), size(0)),
                          Math.abs(oldsize(1) - size(1)) + bh);
            }
            
        // SLOWPATH: dirty ourselves, as well as our former position on our parent
        } else {
            dirty();
            if (getParent() != null) getParent().dirty(oldpos(0), oldpos(1), oldsize(0), oldsize(1));
            
        }
        
        boolean sizechange = false;
        boolean poschange = false;
        if ((oldsize(0) != size(0) || oldsize(1) != size(1)) && is_trapped("SizeChange")) sizechange = true;
        if ((oldpos(0) != pos(0) || oldpos(1) != pos(1)) && is_trapped("PosChange")) poschange = true;
        
        set(oldsize, 0, size(0));
        set(oldsize, 1, size(1));
        set(oldpos, 0, pos(0));
        set(oldpos, 1, pos(1));

        if (sizechange || poschange)
            if (surface.sizePosChangesSinceLastRender++ > 500) {
                if (Log.on) Log.log(this, "Warning, more than 500 SizeChange/PosChange traps triggered since last complete render");
                try {
                    Trap t = sizechange ? Trap.getTrap(this, "SizeChange") : Trap.getTrap(this, "PosChange");
                    InterpretedFunction f = (InterpretedFunction)t.f;
                    if (Log.on) Log.log(this, "Current trap is at " + f.getSourceName() + ":" + f.getLineNumbers()[0]);
                } catch (Throwable t) { }
            }

        if (sizechange) put("SizeChange", null, Boolean.TRUE);
        if (poschange) put("PosChange", null, Boolean.TRUE);
        if (sizechange || poschange) {
            surface.abort = true;
            return;
        }
    }
    

    /** sets our childrens' sizes */
    int sizeChildren() {

        // Set sizes along minor axis, as well as sizes for absolute-positioned children
        for(Box bt = getChild(0); bt != null; bt = bt.nextSibling()) {
            if (bt.invisible) continue;
            if (bt.absolute) {
                bt.set(size, o, max(bt.cmin(o), min(size(o) - bt.abs(o) - pad(o), bt.dmax(o))));
                bt.set(size, xo, max(bt.cmin(xo), min(size(xo) - bt.abs(xo) - pad(xo), bt.dmax(xo))));
            } else if (xo == 0 && bt.hshrink || xo == 1 && bt.vshrink) {
                bt.set(size, xo, bt.cmin(xo));
            } else {
                bt.set(size, xo, bound(bt.cmin(xo), size(xo) - 2 * pad(xo), bt.dmax(xo)));
            }
        }

        // the ideal size of our children, along our own major axis
        int goal = (o == 0 && hshrink) || (o == 1 && vshrink) ? cmin(o) - 2 * pad(o) : size(o) - 2 * pad(o);

        // the current sum of the sizes of all children
        int total = 0;

        // each box is set to bound(box.cmin, box.flex * factor, box.dmax)
        int factor = 0;

        // Algorithm: we set the sizes of all boxes to bound(cmin, flex * factor, dmax) for some global value
        //            'factor'. We figure out what 'factor' should be by starting at zero, and slowly increasing
        //            it. After each pass, 'factor' is set to the smaller of two values: ((goal - total) /
        //            remaining_flex) or the next largest value of factor which will cause some box to exceed its
        //            cmin or dmax (thereby changing remaining_flex).

        while(true) {
            total = 0;

            // the sum of the flexes of all boxes which are not pegged at either cmin or dmax
            int remaining_flex = 0;

            // this is the next largest value of factor at which some box exceeds its cmin/dmax
            int nextjoint = Integer.MAX_VALUE;
            
            for(Box bt = getChild(0); bt != null; bt = bt.nextSibling()) {
                if (bt.absolute || bt.invisible) continue;

                bt.set(size, o, bound(bt.cmin(o), factor * bt.flex, bt.dmax(o)));
                total += bt.size(o);

                if (factor * bt.flex < bt.cmin(o) && bt.size(o) == bt.cmin(o)) {
                    nextjoint = min(nextjoint, divide_round_up(bt.cmin(o), bt.flex));

                } else if (bt.size(o) < bt.dmax(o)) {
                    remaining_flex += bt.flex;
                    nextjoint = min(nextjoint, divide_round_up(bt.dmax(o), bt.flex));

                }
            }

            if (remaining_flex == 0) {
                if (nextjoint <= factor) break;
                factor = nextjoint;
            } else {
                factor = min((goal - total + factor * remaining_flex) / remaining_flex, nextjoint);
            }

            if (goal - total <= remaining_flex) break;
        }

        // arbitrarily distribute out any leftovers resulting from rounding errors
        int last = 0;
        while(goal > total && total != last) {
            last = total;
            for(Box bt = getChild(0); bt != null; bt = bt.nextSibling()) {
                int newsize = bound(bt.cmin(o), bt.size(o) + 1, bt.dmax(o));
                total += newsize - bt.size(o);
                bt.set(size, o, newsize);
            }
        }

        return total;
    }
    
    /** positions this Box's children; cur is the starting position along this' major axis */
    void positionChildren(int cur) {
        for(Box bt = getChild(0); bt != null; bt = bt.nextSibling()) {
            if (bt.invisible) continue;
            if (bt.absolute) {
                bt.set(pos, 0, pos(0) + bt.abs(0));
                bt.set(pos, 1, pos(1) + bt.abs(1));
            } else {
                bt.set(pos, xo, pos(xo) + pad(xo) + max(0, ((size(xo) - 2 * pad(xo) - bt.size(xo)) * (bt.align + 1)) / 2));
                bt.set(pos, o, cur);
                bt.set(abs, 0, bt.pos(0) - pos(0));
                bt.set(abs, 1, bt.pos(1) - pos(1));
                cur += bt.size(o);
            }
        }
    }


    // Rendering Pipeline /////////////////////////////////////////////////////////////////////

    /** Renders self and children within the specified region. All rendering operations are clipped to xIn,yIn,wIn,hIn */
    void render(int xIn, int yIn, int wIn, int hIn, DoubleBuffer buf) {
        dirtiedTimeStamp = surface.dirtiedTimeStamp;
        if (surface.abort || invisible) return;

        // intersect the x,y,w,h rendering window with ourselves; quit if it's empty
        int x = max(xIn, getParent() == null ? 0 : pos(0));
        int y = max(yIn, getParent() == null ? 0 : pos(1));
        int w = min(xIn + wIn, (getParent() == null ? 0 : pos(0)) + size(0)) - x;
        int h = min(yIn + hIn, (getParent() == null ? 0 : pos(1)) + size(1)) - y;
        if (w <= 0 || h <= 0) return;

        if (border != null) renderBorder(x, y, w, h, buf);

        if ((color & 0xFF000000) != 0x00000000 || getParent() == null) {
            int bw = border == null ? 0 : border[2].getWidth();
            int bh = border == null ? 0 : border[0].getHeight();
            buf.setClip(0, 0, buf.getWidth(), buf.getHeight());
            buf.fillRect(max(x, pos(0) + bw),
                         max(y, pos(1) + bh),
                         min(x + w, pos(0) + size(0) - bw),
                         min(y + h, pos(1) + size(1) - bh),
                         (color & 0xFF000000) != 0 ? color : SpecialBoxProperty.lightGray);
        }

        if (image != null) {
            if (tile) renderTiledImage(x, y, w, h, buf);
            else renderStretchedImage(x, y, w, h, buf);
        }

        if (text != null && !text.equals("")) renderText(x, y, w, h, buf);

        // now subtract the pad region from the clip region before proceeding
        int x2 = max(x, pos(0) + pad(0));
        int y2 = max(y, pos(1) + pad(1));
        int w2 = min(x + w, pos(0) + size(0) - pad(0)) - x2;
        int h2 = min(y + h, pos(1) + size(1) - pad(1)) - y2;

        for(Box b = getChild(0); b != null; b = b.nextSibling())
            b.render(x2, y2, w2, h2, buf);   
    }

    private void renderBorder(int x, int y, int w, int h, DoubleBuffer buf) {
        int bw = border[4].getWidth();
        int bh = border[4].getHeight();
        buf.setClip(x, y, w + x, h + y);

        if ((color & 0xFF000000) != 0xFF000000) {

            // if the color is null, we have to be very careful about drawing the corners
            if (Log.verbose) Log.log(this, "WARNING: (color == null && border != null) on box with border " + imageToNameMap.get(border[4]));

            // upper left corner
            buf.drawPicture(border[4],
                            pos(0), pos(1), pos(0) + bw / 2, pos(1) + bh / 2,
                            0, 0, bw / 2, bh / 2);
            
            // upper right corner
            buf.drawPicture(border[4],
                            pos(0) + size(0) - bw / 2, pos(1), pos(0) + size(0), pos(1) + bh / 2,
                            bw - bw / 2, 0, bw, bh / 2);

            // lower left corner
            buf.drawPicture(border[4],
                            pos(0), pos(1) + size(1) - bh / 2, pos(0) + bw / 2, pos(1) + size(1),
                            0, bh - bh / 2, bw / 2, bh);

            // lower right corner
            buf.drawPicture(border[4],
                            pos(0) + size(0) - bw / 2, pos(1) + size(1) - bh / 2, pos(0) + size(0), pos(1) + size(1),
                            bw - bw / 2, bh - bh / 2, bw, bh);

        } else {
            buf.drawPicture(border[4], pos(0), pos(1));                                // upper left corner
            buf.drawPicture(border[4], pos(0) + size(0) - bw, pos(1));                 // upper right corner
            buf.drawPicture(border[4], pos(0), pos(1) + size(1) - bh);                 // lower left corner
            buf.drawPicture(border[4], pos(0) + size(0) - bw, pos(1) + size(1) - bh);  // lower right corner                                     

        }

        // top and bottom edges
        buf.setClip(max(x, pos(0) + bw / 2), y, min(x + w, pos(0) + size(0) - bw / 2), h + y);
        for(int i = max(x, pos(0) + bw / 2); i + 100 < min(x + w, pos(0) + size(0) - bw / 2); i += 100) {
            buf.drawPicture(border[0], i, pos(1));
            buf.drawPicture(border[1], i, pos(1) + size(1) - bh / 2);
        }
        buf.drawPicture(border[0], min(x + w, pos(0) + size(0) - bw / 2) - 100, pos(1));
        buf.drawPicture(border[1], min(x + w, pos(0) + size(0) - bw / 2) - 100, pos(1) + size(1) - bh / 2);

        // left and right edges
        buf.setClip(x, max(y, pos(1) + bh / 2), w + x, min(y + h, pos(1) + size(1) - bh / 2));
        for(int i = max(y, pos(1) + bh / 2); i + 100 < min(y + h, pos(1) + size(1) - bh / 2); i += 100) {
            buf.drawPicture(border[2], pos(0), i);
            buf.drawPicture(border[3], pos(0) + size(0) - bw / 2, i);
        }
        buf.drawPicture(border[2], pos(0), min(y + h, pos(1) + size(1) - bh / 2) - 100);
        buf.drawPicture(border[3], pos(0) + size(0) - bw / 2, min(y + h, pos(1) + size(1) - bh / 2) - 100);

        buf.setClip(0, 0, buf.getWidth(), buf.getHeight());
    }

    void renderStretchedImage(int x, int y, int w, int h, DoubleBuffer buf) {
        buf.setClip(x, y, w + x, h + y);
        int bw = border == null ? 0 : border[4].getHeight();
        int bh = border == null ? 0 : border[4].getWidth();
        buf.drawPicture(image,
                        pos(0) + bw / 2,
                        pos(1) + bh / 2,
                        pos(0) + size(0) - bw / 2,
                        pos(1) + size(1) - bh / 2,
                        0, 0, image.getWidth(), image.getHeight());
        buf.setClip(0, 0, buf.getWidth(), buf.getHeight());
    }

    void renderTiledImage(int x, int y, int w, int h, DoubleBuffer buf) {
        int iw = image.getWidth();
        int ih = image.getHeight();
        int bh = border == null ? 0 : border[4].getWidth();
        int bw = border == null ? 0 : border[4].getHeight();

        for(int i=(x - pos(0) - bw)/iw; i <= (x + w - pos(0) - bw)/iw; i++) {
            for(int j=(y - pos(1) - bh)/ih; j<= (y + h - pos(1) - bh)/ih; j++) {
                
                int dx1 = max(i * iw + pos(0), x);
                int dy1 = max(j * ih + pos(1), y);
                int dx2 = min((i+1) * iw + pos(0), x + w);
                int dy2 = min((j+1) * ih + pos(1), y + h);
                
                int sx1 = dx1 - (i*iw) - pos(0);
                int sy1 = dy1 - (j*ih) - pos(1);
                int sx2 = dx2 - (i*iw) - pos(0);
                int sy2 = dy2 - (j*ih) - pos(1);

                if (dx2 - dx1 > 0 && dy2 - dy1 > 0 && sx2 - sx1 > 0 && sy2 - sy1 > 0)
                    buf.drawPicture(image, dx1, dy1, dx2, dy2, sx1, sy1, sx2, sy2);
            }
        }

    }

    void renderText(int x, int y, int w, int h, DoubleBuffer buf) {

        if ((textcolor & 0xFF000000) == 0x00000000) return;
        buf.setClip(x, y, w + x, h + y);

        XWF xwf = XWF.getXWF(font);
        if (xwf != null) {
            xwf.drawString(buf, text,
                           pos(0) + pad(0),
                           pos(1) + pad(1) + xwf.getMaxAscent() - 1,
                           textcolor);
        } else {
            buf.drawString(font, text,
                           pos(0) + pad(0),
                           pos(1) + pad(1) + Platform.getMaxAscent(font) - 1,
                           textcolor);
        }

        buf.setClip(0, 0, buf.getWidth(), buf.getHeight());
        
        int i=0; while(i<font.length() && !Character.isDigit(font.charAt(i))) i++;

        if (font.lastIndexOf('d') > i) {
            for(int j = pos(0) + pad(0); j < pos(0) + pad(0) + textdim(0); j += 2)
                buf.fillRect(j, pos(1) + pad(1) + (xwf == null ? Platform.getMaxAscent(font) : xwf.getMaxAscent()) + 3,
                             j + 1, pos(1) + pad(1) + (xwf == null ? Platform.getMaxAscent(font) : xwf.getMaxAscent()) + 3 + 1,
                             textcolor);

        } else if (font.lastIndexOf('u') > i) {
            buf.fillRect(pos(0) + pad(0),
                        pos(1) + pad(1) + (xwf == null ? Platform.getMaxAscent(font) : xwf.getMaxAscent()) + 3,
                        pos(0) + pad(0) + textdim(0),
                        pos(1) + pad(1) + (xwf == null ? Platform.getMaxAscent(font) : xwf.getMaxAscent()) + 3 + 1,
                        textcolor);
        }

    }


    // Methods to implement org.mozilla.javascript.Scriptable //////////////////////////////////////

    /** Returns the i_th child */
    public Object get(int i, Scriptable start) {
        if (redirect == null) return null;
        if (redirect != this) return redirect.get(i, start);
        return i >= numChildren() ? null : getChild(i);
    }

    /**
     *  Inserts value as child i; calls remove() if necessary.
     *  This method handles "reinserting" one of your children properly.
     *  INVARIANT: after completion, getChild(min(i, numChildren())) == newnode
     *  WARNING: O(n) runtime, unless i == numChildren()
     */
    public void put(int i, Scriptable start, Object value) {
        if (value == null) {
            if (i > 0 && i < numChildren()) getChild(i).remove();
            return;
        }
        if (value instanceof RootProxy) {
            if (Log.on) Log.log(this, "attempt to reparent a box via its proxy object at " +
                                Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
            return;
        } else if (!(value instanceof Box)) {
            if (Log.on) Log.log(this, "attempt to set a numerical property on a box to anything other than a box at " +
                                Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
            return;
        }
        Box newnode = (Box)value;
        if (redirect == null) {
            if (Log.on) Log.log(this, "attempt to add a child to a node with a null redirect at " + 
                                Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
            return;
        } else if (redirect != this) redirect.put(i, null, newnode);
        else {
            if (numKids > 15 && children == null) convert_to_array();
            if (newnode.parent != null) newnode.remove();
            newnode.parent = this;
            
            if (children == null) {
                if (firstKid == null) {
                    firstKid = newnode;
                    newnode.prevSibling = newnode;
                    newnode.nextSibling = newnode;
                } else if (i >= numKids) {
                    newnode.prevSibling = firstKid.prevSibling;
                    newnode.nextSibling = firstKid;
                    firstKid.prevSibling.nextSibling = newnode;
                    firstKid.prevSibling = newnode;
                } else {
                    Box cur = firstKid;
                    for(int j=0; j<i; j++) cur = cur.nextSibling;
                    newnode.prevSibling = cur.prevSibling;
                    newnode.nextSibling = cur;
                    cur.prevSibling.nextSibling = newnode;
                    cur.prevSibling = newnode;
                    if (i == 0) firstKid = newnode;
                }
                numKids++;
                
            } else {
                if (i >= children.size()) {
                    newnode.indexInParent = children.size();
                    children.addElement(newnode);
                } else {
                    children.insertElementAt(newnode, i);
                    for(int j=i; j<children.size(); j++)
                        getChild(j).indexInParent = j;
                }
            }
            newnode.setSurface(surface);

            // need both of these in case child was already uncalc'ed
            newnode.mark_for_prerender();
            mark_for_prerender(); 

            newnode.dirty();
            sync_cmin_to_children();
        }

        // note that JavaScript box[0] will invoke put(int i), not put(String s)
        put("0", null, newnode);
    }
    
    public Object get(String name, Scriptable start) { return get(name, start, false); }
    public Object get(String name, Scriptable start, boolean ignoretraps) {

        if (name == null || name.equals("")) return null;

        // hack since Rhino needs to be able to grab these functions to create new objects
        if (name.equals("Object")) return JSObject.defaultObjects.get("Object", null);
        if (name.equals("Array")) return JSObject.defaultObjects.get("Array", null);
        if (name.equals("Function")) return JSObject.defaultObjects.get("Function", null);
        if (name.equals("TypeError")) return JSObject.defaultObjects.get("TypeError", null);

        // See if we're reading back the function value of a trap
        if (name.charAt(0) == '_') {
            if (name.charAt(1) == '_') name = name.substring(2);
            else name = name.substring(1);
            Trap t = Trap.getTrap(this, name);
            return t == null ? null : t.f;
        }
        
        // See if we're triggering a trap
        Trap t = traps == null || ignoretraps ? null : (Trap)traps.get(name);
        if (t != null && t.isreadtrap) return t.perform(emptyobj);

        // Check for a special handler
        SpecialBoxProperty gph = (SpecialBoxProperty)SpecialBoxProperty.specialBoxProperties.get(name);
        if (gph != null) return gph.get(this);

        return super.get(name, start);
    }

    /** indicate that we don't want JSObject trying to handle these */
    public boolean has(String name, Scriptable start) {
        if (name.equals("")) return false;
        if (traps != null && traps.get(name) != null) return true;
        if (name.charAt(0) == '_') return true;
        if (SpecialBoxProperty.specialBoxProperties.get(name) != null) return true;
        if (name.equals("Function") || name.equals("Array") || name.equals("Object") || name.equals("TypeError")) return true;
        return super.has(name, start);
    }

    public void put(String name, Scriptable start, Object value) { put(name, start, value, false, null); }
    public void put(String name, Scriptable start, Object value, boolean ignoretraps) { put(name, start, value, ignoretraps, null); }

    /**
     *  Scriptable.put()
     *  @param ignoretraps if set, no traps will be triggered (set when 'cascade' reaches the bottom of the trap stack)
     *  @param rp if this put is being performed via a root proxy, rp is the root proxy.
     */
    public void put(String name, Scriptable start, Object value, boolean ignoretraps, RootProxy rp) {
        if (name == null) return;
        if (name.startsWith("xwt_")) {
            if (Log.on) Log.log(this, "attempt to set reserved property " + name + " at " +
                                Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
            return;
        }

        if (!ignoretraps && traps != null) {
            Trap t = (Trap)traps.get(name);
            if (t != null) {
                Object[] arg = (Object[])singleObjects.remove(false);
                if (arg == null) arg = new Object[] { value };
                else arg[0] = value;
                t.perform(arg);
                arg[0] = null;
                singleObjects.append(arg);
                return;
            }
        }

        // don't want to really cascade down to the box on this one
        if (name.equals("0")) return;

        SpecialBoxProperty gph = (SpecialBoxProperty)SpecialBoxProperty.specialBoxProperties.get(name);
        if (gph != null) {
            gph.put(name, this, value);
            return;
        }

        if (name.charAt(0) == '_') {
            if (value != null && !(value instanceof Function)) {
                if (Log.on) Log.log(this, "attempt to put a non-function value to " + name + " at " + 
                                    Context.enter().interpreterSourceFile + ":" + Context.enter().interpreterLine);
            } else if (name.charAt(1) == '_') {
                name = name.substring(2).intern();
                Trap t = Trap.getTrap(this, name);
                if (t != null) t.delete();
                if (value != null) Trap.addTrap(this, name, ((Function)value), true, rp);
            } else {
                name = name.substring(1).intern();
                Trap t = Trap.getTrap(this, name);
                if (t != null) t.delete();
                if (value != null) Trap.addTrap(this, name, ((Function)value), false, rp);
            }
            return;
        }

        if (ignoretraps) {
            // traps always cascade to the global property, not the local one
            putGlobally(name, start, value);
        } else {
            super.put(name, start, value);
        }

        // a bit of a hack, since titlebar is the only 'special' property stored in JSObject
        if (getParent() == null && surface != null) {
            if (name.equals("titlebar")) surface.setTitleBarText(value.toString());
            if (name.equals("icon")) {
                Picture pic = Box.getPicture(value.toString());
                if (pic != null) surface.setIcon(pic);
                else if (Log.on) Log.log(this, "unable to load icon " + value);
            }
        }
    }

    /** the <tt>delete</tt> keyword is not valid in XWT scripts */
    public void delete(int i) { }


    // Tree Manipulation /////////////////////////////////////////////////////////////////////

    /** The parent of this node */
    private Box parent = null;
    
    // Variables used in Vector mode */
    /** INVARIANT: if (parent != null) parent.children.elementAt(indexInParent) == this */
    private int indexInParent;
    private Vec children = null;

    // Variables used in linked-list mode
    private int numKids = 0;
    private Box nextSibling = null;
    private Box prevSibling = null;
    private Box firstKid = null;
    
    // when we get more than 15 children, we switch to array-mode
    private void convert_to_array() {
        children = new Vec(numKids);
        Box cur = firstKid;
        do {
            children.addElement(cur);
            cur.indexInParent = children.size() - 1;
            cur = cur.nextSibling;
        } while (cur != firstKid);
    }
    
    /** remove this node from its parent; INVARIANT: whenever the parent of a node is changed, remove() gets called. */
    public void remove() {
        if (parent == null) {
            if (surface != null) surface.dispose();
            return;
        }
        Box oldparent = getParent();
        if (oldparent == null) return;
        mark_for_prerender();
        dirty();
        mouseinside = false;

        if (parent.children != null) {
            parent.children.removeElementAt(indexInParent);
            for(int j=indexInParent; j<parent.children.size(); j++)
                (parent.getChild(j)).indexInParent = j;

        } else {
            if (parent.firstKid == this) {
                if (nextSibling == this) parent.firstKid = null;
                else parent.firstKid = nextSibling;
            }
            parent.numKids--;
            prevSibling.nextSibling = nextSibling;
            nextSibling.prevSibling = prevSibling;
            prevSibling = null;
            nextSibling = null;
        }
        parent = null;

        if (oldparent != null) oldparent.sync_cmin_to_children();
        setSurface(null);

        // note that JavaScript box[0] will invoke put(int i), not put(String s)
        if (oldparent != null) oldparent.put("0", null, this);
    }

    /** returns our next sibling (parent[ourindex + 1]) */
    public final Box nextSibling() {
        if (parent == null) return null;
        if (parent.children == null) {
            if (nextSibling == parent.firstKid) return null;
            return nextSibling;
        } else {
            if (indexInParent >= parent.children.size() - 1) return null;
            return (Box)parent.children.elementAt(indexInParent + 1);
        }
    }
    
    /** returns our next sibling (parent[ourindex + 1]) */
    public final Box prevSibling() {
        if (parent == null) return null;
        if (parent.children == null) {
            if (this == parent.firstKid) return null;
            return prevSibling;
        } else {
            if (indexInParent == 0) return null;
            return (Box)parent.children.elementAt(indexInParent - 1);
        }
    }
    
    /** Returns the parent of this node */
    public Box getParent() { return parent; }
    
    /** Returns ith child */
    public Box getChild(int i) {
        if (children == null) {
            if (firstKid == null) return null;
            if (i >= numKids) return null;
            if (i == numKids - 1) return firstKid.prevSibling;
            Box cur = firstKid;
            for(int j=0; j<i; j++) cur = cur.nextSibling;
            return cur;
        } else {
            if (i >= children.size() || i < 0) return null;
            return (Box)children.elementAt(i);
        }
    }
    
    /** Returns the number of children */
    public int numChildren() {
        if (children == null) {
            if (firstKid == null) return 0;
            int i=1;
            for(Box cur = firstKid.nextSibling; cur != firstKid; i++) cur = cur.nextSibling;
            return i;
        } else {
            return children.size();
        }
    }
    
    /** Returns our index in our parent */
    public int getIndexInParent() {
        if (parent == null) return 0;
        if (parent.children == null) {
            int i = 0;
            for(Box cur = this; cur != parent.firstKid; i++) cur = cur.prevSibling;
            return i;
        } else {
            return indexInParent;
        }
    }

    /** returns the root of the surface that this box belongs to */
    public final Box getRoot() {
        if (getParent() == null && surface != null) return this;
        if (getParent() == null) return null;
        return getParent().getRoot();
    }


    // Root Proxy ///////////////////////////////////////////////////////////////////////////////

    RootProxy myproxy = null;
    public Scriptable getRootProxy() {
        if (myproxy == null) myproxy = new RootProxy(this);
        return myproxy;
    }

    private static class RootProxy implements Scriptable {

        Box box;
        RootProxy(Box b) { this.box = b; }

        public void delete(String name) { box.delete(name); }
        public Scriptable getParentScope() { return box.getParentScope(); }
        public void setParentScope(Scriptable p) { box.setParentScope(p); }
        public boolean hasInstance(Scriptable value) { return box.hasInstance(value); }
        public Scriptable getPrototype() { return box.getPrototype(); }
        public void setPrototype(Scriptable p) { box.setPrototype(p); }
        public void delete(int i) { box.delete(i); }
        public String getClassName() { return box.getClassName(); }
        public Object getDefaultValue(Class hint) { return box.getDefaultValue(hint); }

        public void put(int i, Scriptable start, Object value) { if (value != null) box.put(i, start, value); }
        public Object get(String name, Scriptable start) { return box.get(name, start); }
        public Object get(int i, Scriptable start) { return null; }

        public void put(String name, Scriptable start, Object value) { box.put(name, start, value, false, this); }
        public boolean has(String name, Scriptable start) { return box.has(name, start); }
        public boolean has(int i, Scriptable start) { return box.has(i, start); }
        public Object[] getIds() { return box.getIds(); }

    }


    // Trivial Helper Methods (should be inlined) /////////////////////////////////////////

    /** helper, included in this class so it can be inlined */
    static final int min(int a, int b) {
        if (a<b) return a;
        else return b;
    }
    
    /** helper, included in this class so it can be inlined */
    static final double min(double a, double b) {
        if (a<b) return a;
        else return b;
    }
    
    /** helper, included in this class so it can be inlined */
    static final int max(int a, int b) {
        if (a>b) return a;
        else return b;
    }
    
    /** helper, included in this class so it can be inlined */
    static final int min(int a, int b, int c) {
        if (a<=b && a<=c) return a;
        else if (b<=c && b<=a) return b;
        else return c;
    }
    
    /** helper, included in this class so it can be inlined */
    static final int max(int a, int b, int c) {
        if (a>=b && a>=c) return a;
        else if (b>=c && b>=a) return b;
        else return c;
    }
    
    /** helper, included in this class so it can be inlined */
    static final int bound(int a, int b, int c) {
        if (c < b) return c;
        if (a > b) return a;
        return b;
    }

    /** returns numerator/denominator, but rounds <i>up</i> instead of down */
    static final int divide_round_up(int numerator, int denominator) {
        int ret = numerator / denominator;
        if (ret * denominator < numerator) return ret + 1;
        return ret;
    }

    /** Simple helper function to determine if the point x,y falls within this node's actual current geometry */
    boolean inside(int x, int y) {
        if (invisible) return false;
        return (x >= pos(0) && y >= pos(1) && x < pos(0) + size(0) && y < pos(1) + size(1));
    }
    
    /** figures out what box in this subtree of the Box owns the pixel at x,y relitave to the Surface
     *
     *  IMPORTANT: this method gets called from the event-queueing thread, since we need to determine which box is
     *             underneath the mouse as early as possible. Because of this, we have to do some extra checks, as the
     *             Box tree may be in flux.
     */
    Box whoIs(int x, int y) {
        if (invisible) return null;
        if (!inside(x,y)) return getParent() == null ? this : null;

        // We do this because whoIs is unsynchronized (for
        // speed), yet is sometimes called while the structure of the
        // Box is in flux.
        for(int i=numChildren() - 1; i>=0; i--) {

            Box child = getChild(i);
            if (child == null) continue;

            Box bt = child.whoIs(x,y);
            if (bt != null) return bt;
        }
        return this;
    }
    
}