Source of rectangle.c

/* rectangle.c -- special rectangle support for gemsvnc */

/* See the  include file "rectangle.h" for additional documentation. */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rectangle.h"
#include "cmd_sockets.h"

/* stupidly, these are not defined elsewhere */

#define TRUE (!FALSE)                                            /* the true truth value is the logical opposite of false */
#define FALSE (0)                                                /* the false truth value */


/* min and max functions -- why aren't these built-in? */

static int min(int a, int b) {                                   /* the minimum of 2 integers */
  return a < b ? a : b;
}


static int max(int a, int b) {                                   /* the maximum of 2 integers */
  return a > b ? a : b;
}


/* Rectangle Methods */

rectangle* construct_rectangle(int ulx, int uly, int lrx, int lry, char* new_name) { /* construct a named rectangle with the
                                                                                        specified upper-left and lower-right
                                                                                        corners */

  rectangle* R = (rectangle*)malloc(sizeof(rectangle));          /* allocate the memory for it */
  int len = strlen(new_name);                                    /* how long is its name? */
  R->name = (char*)malloc(len + 1);                                      /* make room for its name */
  strcpy(R->name, new_name);                                     /* remember its name */

  R->next = R;                                                   /* make it live on a list of its own */
  R->prev = R;

  R->ul_x = ulx;                                                 /* initialize the corner coordinates */
  R->ul_y = uly;
  R->lr_x = lrx;
  R->lr_y = lry;

  return R;                                                      /* return the new rectangle */
}


void destruct_rectangle(rectangle* R) {                          /* destruct a rectangle */
  free(R->name);
  free(R);
}


void show_rectangle(rectangle* R) {                              /* show a rectangle in human readable form */
  printf("rectangle \"%s\" <#%x>  UL = (%d, %d)  LR = (%d, %d)\n", R->name, (int) R, R->ul_x, R->ul_y, R->lr_x, R->lr_y);
}


void insert_rectangle_before(rectangle* S, rectangle* R) {       /* insert R before S in the list S is on */
  rectangle* Q;
  if (S == NULL || R == NULL) {                                  /* do the rectangles S and R both exist? */
    return;                                                      /* no, do nothing */
  }
  Q = S->prev;                                                   /* get the predecessor of S */
  Q->next = R;                                                   /* not a degenerate case, insert R before S and after Q */
  R->prev = Q;
  R->next = S;
  S->prev = R;
}


void insert_rectangle_after(rectangle* S, rectangle* R) {        /* insert R after S in the list S is on */
  rectangle* Q;
  if (S == NULL || R == NULL) {                                  /* do the rectangles S and R both exist? */
    return;                                                      /* no, do nothing */
  }
  Q = S->next;                                                   /* get the successor of S */
  R->next = Q;                                                   /* not a degenerate case, insert R after S and before Q */
  S->next = R;
  R->prev = S;
  Q->prev = R;
}


void remove_rectangle_from_list(rectangle* R) {                  /* remove R from whatever list it might be on */
  rectangle* Q;                                                  /* next node after R */
  rectangle* S;                                                  /* prev node before R */

  if (R == NULL) {                                               /* is there a rectangle R, */
    return;                                                      /* no, do nothing */
  }

  /* NOTE:  This will do unnecessary but harmless work if R is on a list by itself. */

  S = (rectangle*)R->next;                                       /* point to nodes around this one */
  Q = (rectangle*)R->prev;

  S->prev = Q;                                                   /* remove R from the list */
  Q->next = S;

  R->prev = R;                                                   /* say R is on a list of its own */
  R->next = R;
}


rectangle* find_rectangle_on_list(rectangle* L, char* re) {      /* determine whether a rectangle is on a list L */
  static regex_t preg[4096];                                     /* compiled regular expression to match name */
  int errcode;
  rectangle* P;

  if (L == NULL || re == NULL || strlen(re) == 0) {              /* do both the list and the regular expression exist? */
    return NULL;                                                 /* no, say not found! */
  }

  errcode = regcomp(preg, re, 0);                                /* compile the regular expression */
  if (errcode != 0) {                                            /* any errors? */
    regfree(preg);                                               /* free the compiled expression */
    return NULL;                                                 /* yes, say not found! */
  }

  for (P = L->next; P != L; P = P->next) {                       /* traverse the list */
    if (regexec(preg, P->name, 0, NULL, 0) == 0) {               /* does the name match the regular expression? */
      regfree(preg);                                             /* yes, free the compiled expression */
      return P;                                                  /* return that rectangle! */
    }
  }
  regfree(preg);                                                 /* no match, free the compiled expression */
  return NULL;                                                   /* say we did not find it! */
}


int area(rectangle* R) {                                         /* return the area of a rectangle */
  int width = R->lr_x - R->ul_x;
  int height = R->lr_y - R->ul_y;
  return width*height;
}


int point_is_in_interval_P(int a, int b, int c) {                /* is b between a and c? */
  int lb = a <= b;
  int ub = b <= c;
  int ans = lb && ub;
  return ans;
}


int point_is_inside_rectangle_P(int x, int y, rectangle* R) {    /* is the point inside the rectangle? */
  int in_lr = point_is_in_interval_P(R->ul_x, x, R->lr_x);
  int in_tb = point_is_in_interval_P(R->ul_y, y, R->lr_y);
  int answer = in_lr && in_tb;
  return answer;
}


/* The list of rectangles has a rectangle as its list head.  This rectangle is the bounding-box for all the rectangles in the list.  */

rectangle* construct_empty_list_of_rectangles(char* name) {      /* construct the list head for a list of rectangles, initially
                                                                    empty */

  rectangle* head = construct_rectangle(INT_MAX, INT_MAX, INT_MIN, INT_MIN, name); /* make a rectangle with an impossible bounding box */

  /* If p0 is the upper-left corner, and p1 is the lower-right corner, then no point can ever be in that rectangle. */

  return head;                                                   /* return the new list head */
}


void update_bounding_box(rectangle* L, rectangle* R) {           /* update bounding box in list head L to included rectangle R */
  L->ul_x = min(L->ul_x, R->ul_x);                               /* upper left corner */
  L->ul_y = min(L->ul_y, R->ul_y);

  L->lr_x = max(L->lr_x, R->lr_x);                               /* lower right corner */
  L->lr_y = max(L->lr_y, R->lr_y);
}


void add_rectangle_to_list(rectangle* L, rectangle* R) {         /* add a rectangle to a list of rectangles. */
  insert_rectangle_after(L, R);                                  /* put it there */
  update_bounding_box(L, R);                                     /* update bounding box */
  return;
}


rectangle* remove_named_rectangle_from_list(rectangle* L, char* name) { /* remove a rectangle with the same corners */
  rectangle* R = find_rectangle_on_list(L, name);                /* try to find the named rectangle on the list */
  rectangle* S;

  if (R != NULL) {                                               /* find one? */
    remove_rectangle_from_list(R);                               /* yes, remove it from the list */

    /* Now we must determine if the bounding box needs to be contracted.  If any of the 4 coordinates of the deleted rectangle,
       ur.x, ur.y, lr.x, and lr.y, match the corresponding coordinate of the bounding box exactly, then we need to recompute the
       bounding box. */

    if ( L->ul_x == R->ul_x                                      /* do any of the coordinates match exactly? */
         || L->ul_y == R->ul_y
         || L->lr_x == R->lr_x
         || L->lr_y == R->lr_y ) {

      L->ul_x = INT_MAX;                                         /* reset bounding box to impossible */
      L->ul_y = INT_MAX;
      L->lr_x = INT_MIN;
      L->lr_y = INT_MIN;

      for (S = L->next; S != L; S = S->next) {                   /* yes, for each rectangle remaining on the list */
        update_bounding_box(L, S);                               /* update the bounding box to include that rectangle */
      }
    }
  }
  return R;                                                      /* return what we found */
}


void destroy_named_rectangle_on_list(rectangle* L, char* name) { /* search and destroy a named rectangle */
  rectangle* S = remove_named_rectangle_from_list(L, name);      /* search for it */
  if (S != NULL) {                                               /* found it? */
    destruct_rectangle(S);                                       /* yes, get rid of it */
  }
}


/* The iterator over lists of rectangles. 
   Usage:

    rectangle* list;
    rectangle* R;
    state_rectangle_list_iterator* context;

    for (R = initial_rectangle_list_iterator(list, &context);
         continue_rectangle_list_iterator(&context);
         R = next_rectangle_list_iterator(&context)) {
         do_something(R);
    }
*/   

rectangle* initial_rectangle_list_iterator(rectangle* list, state_rectangle_list_iterator** context) { /* initialize an iterator */
  *context = (state_rectangle_list_iterator*)malloc(sizeof(state_rectangle_list_iterator)); /* allocate a context save area */
  (*context)->head = list;                                       /* remember termination point */
  (*context)->current = list->next;                              /* initialize first item */
  return (*context)->current;                                    /* return first item */
}

int continue_rectangle_list_iterator(state_rectangle_list_iterator** context) { /* test an iterator for non-completion */
  if ((*context)->current == (*context)->head) {                 /* are we done? */
    free(*context);                                              /* yes, release the context save area */
    return FALSE;                                                /* say not to continue */
  } else {
    return TRUE;                                                 /* no, not done, say to continue */
  }
}

rectangle* next_rectangle_list_iterator(state_rectangle_list_iterator** context) { /* get the next item */
  (*context)->current = ((*context)->current)->next;             /* update to point to next item */
  return (*context)->current;                                    /* return next item */
}


void reposition_rectangle_on_list(rectangle* list, rectangle* r, int ulx, int uly, int lrx, int lry) {
  state_rectangle_list_iterator* context;

  r->ul_x = ulx;                                                 /* put rectangle at new place on screen */
  r->ul_y = uly;
  r->lr_x = lrx;
  r->lr_y = lry;

  list->ul_x = INT_MAX;                                          /* reset bounding box to impossible */
  list->ul_y = INT_MAX;
  list->lr_x = INT_MIN;
  list->lr_y = INT_MIN;
  
  for (r = initial_rectangle_list_iterator(list, &context);      /* re-compute the bounding box */
       continue_rectangle_list_iterator(&context);
       r = next_rectangle_list_iterator(&context)) {
    update_bounding_box(list, r);
  }
}


rectangle* intersection_of_2_rectangles(rectangle* R1, rectangle* R2, char* name) {
  int ulx = max(R1->ul_x, R2->ul_x);                             /* compute coordinates of intersection rectangle */
  int uly = max(R1->ul_y, R2->ul_y);
  int lrx = min(R1->lr_x, R2->lr_x);
  int lry = min(R1->lr_y, R2->lr_y);

  if (ulx > lrx                                                  /* do the rectangles actually intersect? */
      || uly > lry) {

    return NULL;                                                 /* no, return no rectangle */

  } else {

    return construct_rectangle(ulx, uly, lrx, lry, name);        /* yes, return the rectangle of intersection */
  }
}