asg/cstitch.h

   1 /************************************************************
   2 **
   3 **       COPYRIGHT (C) 1993 UNIVERSITY OF PITTSBURGH
   4 **       COPYRIGHT (C) 1996 GANNON UNIVERSITY
   5 **                  ALL RIGHTS RESERVED
   6 **
   7 **        This software is distributed on an as-is basis
   8 **        with no warranty implied or intended.  No author
   9 **        or distributor takes responsibility to anyone
  10 **        regarding its use of or suitability.
  11 **
  12 **        The software may be distributed and modified
  13 **        freely for academic and other non-commercial
  14 **        use but may NOT be utilized or included in whole
  15 **        or part within any commercial product.
  16 **
  17 **        This copyright notice must remain on all copies
  18 **        and modified versions of this software.
  19 **
  20 ************************************************************/
  21
  22
  23 /* file cstitch.h */
  24 /* ------------------------------------------------------------------------
  25  * Common definitions for Corner Stiching (see Osterhout '84 DAC paper)  1/90 stf
  26  *
  27  * ------------------------------------------------------------------------
  28  */
  29 /*
  30  */
  31
  32 /* These have different values from xcircuit.h, so undefine them for ASG */
  33 #undef RIGHT
  34 #undef TOP
  35
  36 #define LEFT 0
  37 #define TOP 1           /* Used to define the desired side in neighbor finding */
  38 #define UP 1
  39 #define RIGHT 2
  40 #define BOTTOM 3
  41 #define DOWN 3
  42
  43 #define FURTHER 2
  44 #define CLOSER -2
  45
  46 /*---------------------------------------------------------------
  47  * Templates for corner-stiched data-structures and operations.
  48  *---------------------------------------------------------------
  49  */
  50
  51 typedef struct tile_struct tile;        /* the basic cs element */
  52 typedef struct tile_list tilist;        /* list of tile structure pointers */
  53
  54
  55 struct tile_struct
  56 /* tiles are rectangles at a given location, with corner pointers to the adjacent
  57  * tiles.  If a corner pointer is NULL, this indicates that the given tile is on the
  58  * edge of its respective universe. */
  59 {
  60
  61     int x_pos, y_pos;           /* lower left cartesian coordinates (bl,lb)*/
  62     int x_len, y_len;           /* relative upper rh coordinates (rt,tr) */
  63     int *this;                  /* contents of the rectangle */
  64     tile *bl, *lb;              /* lower-left (lower left side & bottom) stitches */
  65     tile *rt, *tr;              /* upper-right (top & side) stitches */
  66 };
  67
  68 struct tile_list
  69 /* Used to maintain lists of tiles */
  70 {
  71     tile *this;
  72     tilist *next;
  73 };
  74
  75 /*------------------------------------------------------------------------ */
  76 /* function specifications : */
  77 /*------------------------------------------------------------------------ */
  78 extern tile *create_tile();
  79 /*    int xsize, ysize, *what, xorg, yorg;   /* Create a tile from scratch */
  80
  81 /*------------------------------------------------------------------------ */
  82 extern tile *copy_tile();
  83 /*    tile *t;              /* return a unique copy of the given tile <t>. */
  84
  85 /*------------------------------------------------------------------------ */
  86 extern tile *hmerge_tile();
  87 /*    tile *t;    /* Check <t> for merger with its current right-hand neighbor.
  88                      If a merger is appropriate, then nuke the neighbor and
  89                      expand <t>, returning <t>. */
  90
  91 /*------------------------------------------------------------------------ */
  92 extern tile *vmerge_tile();
  93 /*    tile *t;    /* Check <t> for merger with its current upward neighbor.
  94                      If a merger is appropriate, then nuke the neighbor and
  95                      expand <t>, returning <t>. */
  96
  97 /*------------------------------------------------------------------------ */
  98 extern tile *locate();
  99 /*    tile *start;   /* locate the tile containing the point (x,y) given a <start> tile.
 100  *    int x, y;         NOTE:  This is slightly different from the algorithm in [Ost84].
 101  *                      This arranges tiles such that the top and right edges contain points,
 102  *                      whereas the left and bottom edges do not. */
 103
 104 /*------------------------------------------------------------------------ */
 105 extern tilist *list_neighbors();
 106 /*    tile *who;
 107  *    int side; /* {TOP, BOTTOM, LEFT, RIGHT } */
 108 /* create a list of pointers for all of the neighboring tiles on the given side */
 109
 110 /*------------------------------------------------------------------------ */
 111 extern tile *area_search();
 112 /*    tile *start;                      /* a starting tile
 113  *    int xorg, yorg, xsize, ysize;     /* defines the area of interest
 114  * This returns a pointer to the first 'used' tile in the given area.  If none are found,
 115  *then NULL is returned. */
 116
 117 /*------------------------------------------------------------------------ */
 118 extern void null();
 119 /*    tile *t;          ...DO NOTHING...        */
 120 /*------------------------------------------------------------------------ */
 121 extern int containsp();
 122 /*    tile *t;  return TRUE if the given tile contains the given (x,y) point.
 123  *    int x, y; NOTE: This definition arranges the tiles st a tile contains all of the
 124  *              points on its top and right edges. */
 125
 126 /*------------------------------------------------------------------------ */
 127 extern tile *insert_tile();
 128 /*    tile *start;                      a starting tile
 129  *    int xorg, yorg, xsize, ysize;     defines the area of interest
 130  *    int *what;                                contents of the new tile
 131
 132  * This returns a pointer to a newly-created tile of the given size, at the
 133  * given position if one can be made.  Otherwise NULL is returned. */
 134
 135 /*------------------------------------------------------------------------ */
 136 extern tile *angled_tile_insertion();
 137 /*    tile *start;       the starting (reference) tile */
 138 /*    int anchX, anchY;  XY origin of axis of motion (anchor point).
 139 /*    int delX, delY;    slope+dir of the axis of motion (line along which the new tile moves) */
 140 /*    int pivX, pivY;    the pivot point of the <new> tile. (relative to (0,0),
 141                          (sizeX, sizeY) */
 142 /*    int sizeX, sizeY;  defines the size of the tile to be installed */
 143 /*    int *box;          contents of the <new> tile.  Referenced to (0,0). */
 144
 145 /* This returns a pointer to a newly-created tile of the given size, at some position
 146  * lying along the line given by the slope <delY>/<delX> and the point (<anchX>,<anchY>).
 147  * The point (<pivX>, <pivY>) is the point within the new tile that lies on this line.
 148  * The coordinate reference for the block being inserted is (0,0), whereas that for the
 149  * for the tile(s) is the same as that for the tile <start>.
 150  * The new tile is placed as close to the given anchor point as possible. */
 151
 152 /*------------------------------------------------------------------------ */
 153 tile *angled_group_tile_insertion();
 154 /*    tile *start;       the starting (reference) tile */
 155 /*    int anchX, anchY;  origin of axis of motion (anchor pnt) in <start>'s tile space */
 156 /*    int delX, delY;    slope+dir of the axis of motion (line along which tiles move) */
 157 /*    int pivX, pivY;    the pivot point of the <new> tile set. (relative to (0,0)) */
 158 /*    int *orgX, *orgY;  The solution found for this tile set. */
 159 /*    tilist *tlist;     list of tiles to be inserted into <start>'s tile space */
 160
 161 /* This returns a pointer to one of a set of newly-created tiles, created by adding
 162  * all of the tiles on <tlist> to the tile space defined by <start>.  They are added
 163  * at some position lying along a line given at an angle defined by <ydir>/<xdir>.
 164  * The position closest to the anchor point is selected. */
 165
 166 /*------------------------------------------------------------------------*/
 167 extern tile *delete_tile();
 168 /*    tile *deadTile;   This functions removes <t> fromthe set of tiles, performing
 169                         all of the necessary mergers, etc..     */
 170     /* NOTE:  This function depends upon the notion that the upper and right
 171      *        border of a tile are included in the tile, but not the lower &
 172      *        left sides.                                                       */
 173
 174 /*------------------------------------------------------------------------ */
 175 extern int clean_up_neighbors();
 176 /*    tile *who;        /* See that all of <who>'s neighbors point to him. */
 177
 178 /*------------------------------------------------------------------------ */
 179 extern tilist *translate_origin();
 180 /*    tilist *tl;       list of tiles to modify */
 181 /*    int x, y;         what to add to each x_pos, y_pos */
 182
 183 /*------------------------------------------------------------------------ */
 184 tilist *allspace();
 185 /*    tile *t;          Some tile in area to search */
 186 /*    tilist **tl;      Where to list the located tiles */
 187
 188 /*------------------------------------------------------------------------ */
 189 extern tilist *freespace();
 190 /*    tile *t;           Some tile in area to search */
 191 /*    tilist **tl         Where to list the empty tiles */
 192
 193 /*  Form a list of all tiles within the area containing <t> that have
 194     no valid <this> entry: */
 195
 196 /*------------------------------------------------------------------------ */
 197 extern tilist *nonFreespace();
 198 /*    tile *t;          Some tile in area to search */
 199 /*    tilist **tl               Where to list the used tiles */
 200
 201 /*------------------------------------------------------------------------ */
 202 extern tilist *area_enumerate();
 203 /*    tile *t;                  */
 204 /*    tilist **soFar;           */
 205 /*    int (*filterFn)();        given a tile, returns TRUE if the tile is to be listed */
 206 /*    int xorg, yorg;           Origin of area of interest (AOI) */
 207 /*    int xext, yext;           Extent of area of interest */
 208
 209 /* Return a list containing all tiles within the AOI: */
 210
 211 /*------------------------------------------------------------------------ */
 212 extern tilist *enumerate();
 213 /*    tile *t;                  */
 214 /*    tilist **soFar;           */
 215 /*    int (*filterFn)();        given a tile, returns TRUE if the tile is to be listed */
 216
 217 /* Return a list containing all tiles to the right or below the given tile: */
 218
 219 /*------------------------------------------------------------------------ */
 220 extern void reset_boundaries();
 221 /*    tile *root;                       tile in affected tilespace*/
 222 /*    int x1, y1, x2, y2;               llhc and urhc of new space dimensions */
 223 /* This will reset the boundaries of the tilespace containing <root> to the
 224    given dimensions, as long as no tiles are removed.  Otherwise, the
 225    smallest size is set. */
 226
 227 /*------------------------------------------------------------------------ */
 228 extern void determine_bounding_box();
 229 /*    tile *root;                  tile in affected tilespace*/
 230 /*    int x1, y1, x2, y2;          llhc and urhc of new (min)space dimensions */
 231 /* Determine the min. bounding box that will contain all of the filled
 232    tiles within the tile-space defined by <root>.
 233    NOTE: This is a destructive routine, in that the BB for <root> remains
 234    set to the minimum discovered.  */
 235
 236 /*------------------------------------------------------------------------ */
 237 extern tile *find_ULHC();
 238 /*    tile *t;          Where to start looking */
 239 /* Find the upper-left-hand corner tile in the space containing <t>. */
 240
 241 /*------------------------------------------------------------------------ */
 242 extern tile *find_LRHC();
 243 /*    tile *t;          Where to start looking */
 244 /* Find the lower-right-hand corner tile in the space containing <t>. */
 245
 246 /*------------------------------------------------------------------------ */
 247 extern tilist *find_all_tiles_along_line();
 248 /*    tile *start;              Tile in which to start looking */
 249 /*    int srcX, srcY;           Point on line (in start?) */
 250 /*    int delX, delY;           Slope of line */
 251 /*    tilist **soFar;           Where to list the tiles found */
 252
 253 /* This function walks down the given line, and adds each tile it encounters to
 254    the list returned. */
 255
 256 /*------------------------------------------------------------------------ */
 257 /*extern tilist *find_all_tiles_along_swath();
 258 /*    tile *start;              Tile in which to start looking */
 259 /*    int srcX, srcY;           Center Point on line (in start?) */
 260 /*    int delX, delY;           Slope of line */
 261 /*    int width, length;        Width & Length of swath being checked */
 262 /*    tilist **soFar;           Where to list the tiles found */
 263
 264 /* This function walks down the given line, and adds each tile it encounters to
 265    the list returned.    A tile is encountered if it touches the given swath at
 266    any point.
 267  */
 268
 269 /*------------------------------------------------------------------------ */
 270 extern tile *first_noncontiguous_full_tile();
 271 /*     tilist *tlist;           list to look in. */
 272
 273 /*------------------------------------------------------------------------ */
 274 extern tile *best_tile_in_space();
 275 /*    tile *t;                  some tile in the desired tile space */
 276 /*    int (*filterFn)();        returns TRUE if <t1> is better than <t2>. */
 277
 278     /* This returns the best filled tile in the given tile space. */
 279
 280 /*------------------------------------------------------------------------ */
 281 extern int adjacent_tiles_p();
 282 /*      tile *t1, *t2;   */
 283 /* Return TRUE iff t1 & t2 share a common edge */
 284
 285 /*------------------------------------------------------------------------ */
 286 extern int most_right();
 287 /*    tile *t1, t2;     */
 288 /* given two tiles, return TRUE if the right-edge of <t1> is further to
 289    the right than the right edge of <t2>:       */
 290
 291 /*------------------------------------------------------------------------ */
 292 extern int most_left();
 293 /*    tile *t1, t2;     */
 294
 295 /* given two tiles, return TRUE if the left edge of <t1> is further to
 296    the left than the left edge of <t2>: */
 297 /*------------------------------------------------------------------------ */
 298 extern int most_up();
 299 /*    tile *t1, t2;     */
 300
 301 /* given two tiles, return TRUE if the top-edge of <t1> is further up
 302    than the top edge of <t2>:   */
 303
 304 /*------------------------------------------------------------------------ */
 305 extern int most_down();
 306 /*    tile *t1, t2;     */
 307
 308 /* given two tiles, return TRUE if the bottom-edge of <t1> is further
 309    down than the bottom edge of <t2>:   */
 310
 311 /*------------------------------------------------------------------------ */
 312 extern void ps_print_tile_space();
 313 /*    tile *t;              A tile within the tilespace to be printed. */
 314 /*    FILE *f;              Where to print the stuff to */
 315 /*    int (*ps_printFn)();  given a file followed by a tile, print post-script code to
 316                             represent the contents of the tile.  Should be able to
 317                             handle NULL. */
 318 /*    int edgesP;           if == TRUE, the PS code for the tile borders is made */
 319
 320
 321
 322 /*-- Managing Internal Data: ---------------------------------------------- */
 323 /* THESE FUNCTIONS NEED TO BE DEFINED!  Without them, the program will not link.
 324  * They allow for the corner-stitching routines to apply to more-than just simple
 325  * contents.
 326 /*------------------------------------------------------------------------ */
 327
 328 /*------------------------------------------------------------------------ */
 329 extern void (*manage_contents__hmerge)();
 330 /* tile *left;      This is the tile that will remain, with the contents of <right>.
 331  * tile *right;     This is the tile to be nuked (just before modifications happen) */
 332
 333 /*------------------------------------------------------------------------ */
 334 extern void (*manage_contents__vmerge)();
 335 /* tile *bottom;  This is the tile that will remain, with the contents of <top>.
 336  * tile *top;     This is the tile to be nuked (just before modifications happen) */
 337
 338 /*------------------------------------------------------------------------ */
 339 extern void (*manage_contents__hsplit)();
 340 /* tile *left;      This is the parent tile after mods.
 341  * tile *right;     This is the resulting child tile (created from <left>) */
 342
 343 /*------------------------------------------------------------------------ */
 344 extern void (*manage_contents__vsplit)();
 345 /* tile *top;     This is the parent tile (after mods) */
 346 /* tile *bottom;  This is the resulting child tile created from <top>. */
 347
 348 /*------------------------------------------------------------------------ */
 349 extern void (*manage_contents__dead_tile)();
 350 /* tile *old;  This is the tile that was just wasted;  Its neighbors are correct,
 351                and may be searched for info concerning content information. */
 352 /*------------------------------------------------------------------------ */
 353 extern int (*solidp)();
 354 /*    tile *t;   return TRUE iff tile t is used. */
 355 /*------------------------------------------------------------------------ */
 356 extern int (*contents_equivalentp)();
 357 /*    tile *t1, *t2;    TRUE iff tiles <t1> & <t2> have the same color */
 358 /*------------------------------------------------------------------------ */
 359 extern void (*insert_contents)();
 360 /*    tile *t;   Return the pointer to the proper contents for the given tile, */
 361 /*    module *m; given that <m> is being inserted into the tile <t>.           */
 362
 363 /*------------------------------------------------------------------------ */
 364 /* The standard assignments for these are as follows:                    */
 365
 366 extern int std_solidp();                        /* return TRUE iff tile t is used. */
 367 /*    tile *t;          */
 368
 369 extern void std_insert_contents();               /* Make the standard assignment for
 370 /*    tile *t;                                      tile contents (add <w> to <t>)
 371       int *w;           */
 372
 373 extern int std_contents_equivalentp();          /* Return TRUE if the tiles are of the
 374 /*    tile *t1, *t2;                               same color */
 375
 376 extern void null();                             /* Do nothing */
 377 /*    tile *t;          */
 378
 379
 380
 381
 382
 383
 384 /*---------------------------------------------------------------
 385  * END OF FILE
 386  *---------------------------------------------------------------
 387  */