XEROX BOUNDARY 2 4 1 BOUNDARY 1 4 By: Mike Bird Support by: Greg Wexler (Wexler.pasa@Xerox.com) INTRODUCTION A "boundary" is defined by its left and bottom inclusive bounds and by its right and top exclusive bounds. Although equivalent to a "region" it is computationally more efficient in certain applications. For further efficiency, the datatype defined here includes a link field. This can significantly reduce CONS-ing. Create and release functions are provided which use a freelist. These can help to reduce garbage collection. If a boundary is not explicitly released it will become available for garbage collection in the usual way. After release a boundary should not be smashed. In particular, it should not be released again. The datatype is defined with POINTER fields rather than FIXP or SIGNEDWORD. This is computationally more efficient, especially in the important case of SMALLP values. The additional storage required for FIXP values is not significant for most applications. *** Wherever this document refers to a list of boundaries, this signifies linkage via the NEXT.BOUND field. BOUNDARY DATATYPE LEFT.BOUND POINTER BOTTOM.BOUND POINTER RIGHT.BOUND POINTER TOP.BOUND POINTER NEXT.BOUND POINTER BOUNDARY.CREATE(LEFT BOTTOM RIGHT [Function] TOP NEXT) Creates, initialises and returns a boundary. Uses a boundary from the freelist if possible. Fields whose values are omitted are initialised to NIL, not zero. BOUNDARY.DIFFERENCE(OUTER INNER) [Function] Returns a (possibly null) list of BOUNDARY's which together comprise the difference between the OUTER and INNER boundaries. *** Assumes no part of INNER is outside OUTER. BOUNDARY.FREELIST [Variable] The freelist of available boundaries. Initially NIL. BOUNDARY.INTERSECTION(X Y) [Openlambda] If X and Y have a non-empty intersection, the boundary of that intersection is returned. Otherwise NIL is returned. BOUNDARY.INTERSECTION*(X Y.LEFT Y.BOTTOM [Openlambda] Y.RIGHT Y.TOP) Version of BOUNDARY.INTERSECTION for use when one of the boundaries' bounds have already been unpacked from the boundary. BOUNDARY.INTERSECTION**(X.LEFT X.BOTTOM [Openlambda] X.RIGHT X.TOP Y.LEFT Y.BOTTOM Y.RIGHT Y.TOP) Version of BOUNDARY.INTERSECTION for use when both of the boundaries' bounds have already been unpacked. BOUNDARY.INTERSECTP(X Y) [Openlambda] Predicate for determining whether X and Y have a non-empty intersection. BOUNDARY.INTERSECTP*(X Y.LEFT Y.BOTTOM [Openlambda] Y.RIGHT Y.TOP) Version of BOUNDARY.INTERSECTP for use when one of the boundaries' bounds have already been unpacked from the boundary. BOUNDARY.INTERSECTP**(X.LEFT X.BOTTOM [Openlambda] X.RIGHT X.TOP Y.LEFT Y.BOTTOM Y.RIGHT Y.TOP) Version of BOUNDARY.INTERSECTP for use when both of the boundaries' bounds have already been unpacked. BOUNDARY.MERGE(OLD.BOUNDARIES NEW.BOUNDARIES) [Function] For each member, N, of NEW.BOUNDARIES: While N can be combined with any member, O, of OLD.BOUNDARIES to form a single equivalent boundary; N is smashed to produce the combined boundary and O is released. Finally N is pushed onto the OLD.BOUNDARIES list. *** Warning: Smashes NEW.BOUNDARIES. BOUNDARY.POP(STACK) [Macro] Returns the first boundary in STACK and changes STACK to refer to the next boundary. *** The STACK expression should be simple and have no side-effects. *** The NEXT.BOUND of the returned boundary is not nullified. BOUNDARY.PUSH(STACK ITEM) [Macro] Pushes the boundary ITEM onto the front of the list STACK and changes STACK to reference it. *** Both STACK and ITEM should be simple and have no side-effects. BOUNDARY.RELEASE(BOUNDARIES) [Function] The members of the specified list of boundaries are transferred to the freelist. This smashes their NEXT.BOUND links. *** To release a single boundary, NEXT.BOUND of BOUNDARIES must be null. BOUNDARY.UNION(X Y) [Openlambda] Returns the smallest BOUNDARY which contains the regions contained by the boundaries X and Y. BOUNDARY.UNION*(X Y.LEFT Y.BOTTOM [Openlambda] Y.RIGHT Y.TOP) Version of BOUNDARY.UNION for use when one of the boundaries' bounds have already been unpacked from the boundary. BOUNDARY.UNION**(X.LEFT X.BOTTOM [Openlambda] X.RIGHT X.TOP Y.LEFT Y.BOTTOM Y.RIGHT Y.TOP) Version of BOUNDARY.UNION for use when both of the boundaries' bounds have already been unpacked. (LIST ((PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC) STARTINGPAGE# 1) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD CENTERED) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (174 36 288 36) NIL) (HEADING NIL (HEADINGTYPE RUNNINGHEAD) (84 744 528 36) NIL) (TEXT NIL NIL (84 96 456 600) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD CENTERED) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (174 36 288 36) NIL) (HEADING NIL (HEADINGTYPE RUNNINGHEAD) (84 744 528 36) NIL) (TEXT NIL NIL (84 96 456 600) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC)) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD CENTERED) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC)) (174 36 288 36) NIL) (HEADING NIL (HEADINGTYPE RUNNINGHEAD) (84 744 528 36) NIL) (TEXT NIL NIL (84 96 456 600) NIL)))))(È(ŠŠ8(ŠŠ8DÈÈ PAGEHEADING RUNNINGHEAD(È(È 1`ì`hTERMINAL MODERN MODERNLOGOMODERN   HRULE.GETFNMODERN  HRULE.GETFNMODERN  HRULE.GETFNMODERN   HRULE.GETFNMODERN  HRULE.GETFNMODERN 0?<m"  1|06u(z'iI&x%g.'Ù&UE?]DwJ^!s b?¦zº