Table of Contents

• The Problem
• The Algorithm
• The Program
  • Input
  • The Rectangle List
  • Rectangles
  • The Linked-List Link
• Index

I learned the importance of cycles in these kinds of problems while I was on a job interview at Bell Labs in Homdel. I was interviewing with a group working on something like VideoText, where I saw a demo showing how they could get hidden-rectangle elimination for free by drawing the rectangles in order of increasing level. I asked them what would happen if they tried to draw three simutaniously overlapping rectangles. They didn't know and the demo was canned, so we couldn't try it.

The Algorithm

A data structure for representing approximate levels needs to keep track of which rectangles are above others. This is easily done by, for example, storing rectangles in a sequence such that a rectangle earlier in the sequence either does not overlap or ovalaps above a rectangle later in the sequence.

A data structure for representing exact levels is more expensive than the approximate-level data structure, either in terms of time or space (or both). A rectangle's exact level depends on all the rectangles undeneath it; the data structure would need to either keep track of that information or else recompute it whenever rectangles move. In addition, a rectangle's exact level may have influence on the exact level of any rectangle that overlaps above it; this information too has to be kept or computed. In either case, the exact-level data structure requires either extensive cross linkage information among rectangles or expensive global overlap computations.

The Program

<main()>= (U->)

int main(void) {

  rectangle_list rectangles;
  int x1, y1, x2, y2;
  read_returns rr;

  while ((rr = read_data(cin, x1, y1, x2, y2)) != eof_read)
    if (rr == rectangle_read) {
      rectangle r(x1, y1, x2, y2);
      rectangles.insert(r);
      }
    else if (rr == slide_read)
      rectangles.slide(x1, y1, x2, y2);
    else {
      cerr << "Unknown read_data() return value in main().\n";
      return EXIT_FAILURE;
      }

  rectangles.print(cout);

  return EXIT_SUCCESS;
  }

Defines main (links are to index).

<main.cc>=

#include <iostream>
#include <stdlib.h>
#include "rectangle.h"
#include "rect-list.h"
#include "read.h"

<main()>

Defines main.cc (links are to index).

Input

<read.h>=

#ifndef _read_h_defined_
#define _read_h_defined_

#include <iostream>

enum read_returns {
  rectangle_read,
  slide_read,
  eof_read
  };

extern read_returns read_data(
  istream & in, int & x1, int & y1, int & x2, int & y2);

#endif

Defines read.h, read_returns (links are to index).

read_data() reads the next rectangle or move from the input stream in and, assuming there's something there, returns the four integers read in x1, y1, x2, and y2; the return value indicates what was read.

Using a string to read the x or -> requires a bit of care. Doing something like

int x1, y1, x2, y2;
string s;
cin >> x1 >> y1 >> s >> x2 >> y2;

<read an input spec>= (U->)

read_returns read_data(istream & in, int & x1, int & y1, int & x2, int & y2) {

  if (!read_int_pair(in, x1, y1)) return eof_read;
  
  char c;
  if (!(in >> c)) badeof("an arrow or an x");

  if (c == '-') {
    if (!(in.get(c))) badeof("an arrow");
    if (c != '>') badc(c, "an arrow");
    }
  else if (tolower(c) != 'x')
    badc(c, "an arrow or an x");

  if (!read_int_pair(in, x2, y2))
    badeof("the second pair of integers");

  return c == '>' ? slide_read : rectangle_read;
  }

Defines read_data (links are to index).

read_int_pair() reads a pair of integers from the input stream in, storing them in x and y. Return true if a pair was read, false otherwise; die on an error.

<read an integer pair>= (U->)

static bool read_int_pair(istream & in, int & x, int & y) {

  if (!read_an_int(in, x)) return false;
  if (!read_an_int(in, y)) badeof("the second of two integers");
  return true;
  }

Defines read_int_pair (links are to index).

read_an_int() reads an integer from the input stream in and stores it in i, returning true if an integer was read and false otherwise. It dies on an error.

<read an integer>= (U->)

static bool read_an_int(istream & in, int & i) {

  if (cin >> i) return true;
  if (cin.eof()) return false;

  if (cin.fail()) {
    char c;
    if (!(cin >> c)) c = '?';
    badc(c, "an integer");
    }

  cerr << "Unrecoverable input error during an integer read.\n";
  exit(EXIT_FAILURE);

  return false; 
  }

Defines read_an_int (links are to index).

A couple of helper routines to print an informative error message about incorrect input.

<input-error routines>= (U->)

static void badc(char c, const string & what) {
  cerr << "Unexpected character '" << c << "' while reading " << what << ".\n";
  exit(EXIT_FAILURE);
  }

static void badeof(const string & what) {
  cerr << "Unexpected end-of-file while reading " << what << ".\n";
  exit(EXIT_FAILURE);
  }

Defines badc, badeof (links are to index).

<read.cc>=

#include <string>
#include "read.h"

<input-error routines>

<read an integer>

<read an integer pair>

<read an input spec>

Defines read.cc (links are to index).

The Rectangle List

1. Create an empty rectangle list.

2. Insert rectangles into the list.

3. Print the rectangles in the list in order of increasing level.

4. Slide a rectangle in the list.

<rectangle list public routines>= (U->)

rectangle_list();
void insert(rectangle & r);
void print(ostream & out);
void slide(int x, int y, int delta_x, int delta_y);

The rectangle list is a doubly linked list because the code will need to traverse the list in both directions. The list uses both a dummy head and tail to avoid special cases in link-list operations.

<rectangle list private data structure>= (U->)

typedef list_link<rectangle> rl_link;
rl_link top, bottom;

Defines rl_link (links are to index).

A new rectangle list is empty, with the dummy head and tail pointing at each other.

<the rectangle list constructor>= (U->)

rectangle_list::rectangle_list() 
  : top(rectangle(), 0, 0), 
    bottom(rectangle(), 0, 0)
  { 
   top.next = &bottom;
   bottom.last = &top;
   top.last = bottom.next = 0;
  }

To insert the rectangle r into the list, just add it to the top of the list. This maintains the list invariant: because r is the first element in the list, it must preceede any other rectangle it overlaps. Also, because none of the other rectangles have changed relative position, the invariant still holds for them.

<insert a new rectangle>= (U->)

void rectangle_list::insert(rectangle & r) {
  new rl_link(r, &top, top.next);
  }

Defines insert (links are to index).

Because the rectangle list only indicates the rectangles' relative levels instead of their absolute levels, printing the list by level requires a little bit of work. First, the rectangles must be assigned their absolute levels; then the rectangles are printed out level by level starting from the lowest level.

Because none of the print routines change the retangles' relative order in the list, they preserve the list invariant.

<print the rectangle list>= (U->) [D->]

void rectangle_list::print(ostream & out) {

  const unsigned max_level = set_levels();

  for (unsigned i = 0; i <= max_level; i++)
    print_levels(out, i);
  }

Defines print (links are to index).

Determine the levels of the rectangles in the list; return the largest level found. This is an O(n²) algorithm, where n is the number of rectangles in the list, because any two rectangles in the list may overlap and so need to be checked. However, the list invariant does help a bit: for any rectangle r, it is only necessary to check the rectangles below r in the list, because only only those rectangles below r can possibly contribute to r's level.

<print the rectangle list>+= (U->) [<-D->]

unsigned rectangle_list::set_levels(void) {

  unsigned max_level = 0;

  for (rl_link * i = bottom.last; i != &top; i = i->last) {
    i->element.level = 0;
    for (rl_link * j = i->next; j != &bottom; j = j->next)
      if (j->element.overlapping(i->element))
        i->element.level = max(i->element.level, j->element.level + 1);
    max_level = max(max_level, i->element.level);
    }

  return max_level;
  }

Defines set_levels (links are to index).

Print to the stream out all the rectangles in the list at level l.

<print the rectangle list>+= (U->) [<-D]

void rectangle_list::print_levels(ostream & out, unsigned l) const {

  for (rl_link * i = bottom.last; i != &top; i = i->last) {
    rectangle & r = i->element;
    if (r.level == l) {
      r.print(out);
      out << "\n";
      }
    }
  }

Defines print_levels (links are to index).

Slide the topmost rectangle that encloses the point (x, y) by the amount (delta_x, delta_y); if no such rectangle exists, do nothing.

<slide a rectangle>= (U->) [D->]

void rectangle_list::slide(int x, int y, int delta_x, int delta_y) {

  rl_link * rp = enclosing(x, y);
  if (rp) {
    mark_overlapping(rp);
    rl_link * rp2 = extract_marked();
    assert(rp2 == rp);
    add(rp);
    rp->element.slide(delta_x, delta_y);
    }
  }

Defines slide (links are to index).

Mark in the rectangle list the transative closure of the rectangles overlapping above the rectangle contained in rp.

<slide a rectangle>+= (U->) [<-D->]

void rectangle_list::mark_overlapping(rl_link * rp) {

  assert(rp && (rp != &top) && (rp != &bottom));

  rp->element.marked = true;
  for (rl_link * i = rp->last; i != &top; i = i->last) {
    rectangle & r = i->element;
    for (rl_link * j = i->next; j != rp->next; j = j->next)
      if ((r.marked = j->element.marked && j->element.overlapping(r)))
        break;
    }

  for (rl_link * i = rp->next; i != &bottom; i = i->next)
    i->element.marked = false;
  }

Defines mark_overlapping (links are to index).

Remove all the marked rectangles from the rectangle list. The removed rectangles are linked into a list having the same relative order as the rectangle list; return a pointer to the bottom of the removed rectangle list.

<slide a rectangle>+= (U->) [<-D->]

rectangle_list::rl_link * rectangle_list::extract_marked(void) { 

  rectangle r;
  rl_link t(r, 0, 0);
  rl_link * tp = &t;
  rl_link * i = top.next;
  const rl_link * stop = &bottom;
  while (i != stop)
    if (i->element.marked) {
      rl_link * j = i;
      i = i->next;
      j->unlink();
      tp->next = j;
      j->last = tp;
      tp = j;
      }
    else
      i = i->next;

  t.next->last = 0;
  tp->next = 0;

  return tp;
  }

Defines extract_marked (links are to index).

Return a pointer to the highest-level rectangle in the list that contains the point (x, y). If no such rectangle exists, return 0.

<slide a rectangle>+= (U->) [<-D->]

rectangle_list::rl_link * rectangle_list::enclosing(int x, int y) const {

  for (rl_link * i = top.next; i != &bottom; i = i->next)
    if (i->element.contains(x, y)) return i;

  return 0;
  }

Defines enclosing (links are to index).

Add the list of rectangle links pointed to by rp at the head of the list.

<slide a rectangle>+= (U->) [<-D]

void rectangle_list::add(rl_link * rp) {

  assert(rp);

  top.next->last = rp;
  rp->next = top.next;
  for (top.next = rp; top.next->last; top.next = top.next->last) { }
  top.next->last = &top;
  }

Defines add (links are to index).

<rect-list.cc>=

#include <algorithm>
#include "rect-list.h"

<the rectangle list constructor>

<insert a new rectangle>

<print the rectangle list>

<slide a rectangle>

Defines rect-list.cc (links are to index).

<rect-list.h>=

#ifndef _rect_list_h_defined_
#define _rect_list_h_defined_

#include "link.h"
#include "rectangle.h"
#include <iostream>

class rectangle_list {

  public:

    <rectangle list public routines>

  private:

    <rectangle list private data structure>

    unsigned set_levels(void);
    void print_levels(ostream &, unsigned) const;
    rl_link * enclosing(int, int) const;
    void mark_overlapping(rl_link *);
    rl_link * extract_marked(void);
    void add(rl_link *);

  };

#endif

Defines rect-list.h (links are to index).

Rectangles

<rectangle public data>= (U->)

bool marked;
unsigned level;

A rectangle is defined by the endpoints of one of its diagonals. Zero-area rectangles aren't allowed, so die when attempting to construct one.

<the rectangle constructor>= (U->)

rectangle(int X1, int Y1, int X2, int Y2) : 
  marked(false), level(0), x1(X1), y1(Y1), x2(X2), y2(Y2) { 
    assert((x1 != x2) && (y1 != y2));
    }

Defines rectangle (links are to index).

The default rectangle constructor isn't necessary, but having one makes writing the rectangle-list code a bit simpler.

<the default rectangle constructor>= (U->)

rectangle() :
  marked(false), level(0), x1(0), y1(0), x2(1), y2(1) { }

Return true if and only if rectangle r overlaps with some part of this rectangle. Two rectangles overlap if and only if they overlap both along their x range and along their y range.

<the rectangle overlapping predicate>= (U->)

bool overlapping(const rectangle & r) const {
  return intervals_overlapping(r.x1, r.x2, x1, x2) && 
         intervals_overlapping(r.y1, r.y2, y1, y2);
  }

Defines overlapping (links are to index).

Return true if and only if this rectangle contains the point (x, y).

<the rectangle contains predicate>= (U->)

bool contains(int x, int y) const {
  return coordinate_in_range(x1, x, x2) && coordinate_in_range(y1, y, y2);
  }

Defines contains (links are to index).

Slide the rectangle by (x, y).

<the rectangle slide operator>= (U->)

void slide(int x, int y) {
  x1 += x;
  y1 += y;
  x2 += x;
  y2 += y;
  }

Defines slide (links are to index).

Print this rectangle to the stream out.

<the rectangle print operator>= (U->)

void print(ostream & out) const {
  out << x1 << " " << y1 << " x " << x2 << " " << y2;
  }

Defines print (links are to index).

Return true if and only if a is in the range (l, r).

<rectangle private routines>= (U->) [D->]

bool coordinate_in_range(int l, int a, int r) const {
  return (l < a) && (a < r);
  }

Defines coordinate_in_range (links are to index).

Return true if and only if the interval [x1, x2] overlaps with the interval (x3, x4).

<rectangle private routines>+= (U->) [<-D]

bool intervals_overlapping(int x1, int x2, int x3, int x4) const {
  return (max(x1, x2) > min(x3, x4)) && (min(x1, x2) < max(x3, x4));
  }

Defines interval_overlapping (links are to index).

<rectangle.h>=

#ifndef _rectangle_h_defined_
#define _rectangle_h_defined_

#include <algorithm>
#include <cassert>

class rectangle {

  public:

    <rectangle public data>

    <the rectangle constructor>

    <the default rectangle constructor>

    <the rectangle overlapping predicate>

    <the rectangle contains predicate>

    <the rectangle slide operator>

    <the rectangle print operator>

  private:

    int x1, y1, x2, y2;

    <rectangle private routines>
  };

#endif

Defines rectangle.h (links are to index).

The Linked-List Link

<link.h>=

#ifndef _link_h_defined_
#define _link_h_defined_

#include <cassert>

template<typename ElementType>
struct list_link {

  list_link<ElementType> * next;
  list_link<ElementType> * last;
  ElementType element;

  list_link(
    ElementType e, 
    list_link<ElementType> * before = 0,
    list_link<ElementType> * after = 0
    ) {
    element = e;

    if ((0 == before) && (0 == after)) 
      next = last = 0;
    else if (0 == before) {
      next = after;
      assert(0 == after->last);
      last = after->last;
      after->last = this;
      }
    else if (0 == after) {
      assert(0 == before->next);
      next = before->next;
      last = before;
      before->next = this;
      }
    else {
      next = after;
      last = before;
      assert((before == after->last) && (after == before->next));
      after->last = this;
      before->next = this;
      }
    }

 ~list_link() {
    if (next != 0) next->last = last;
    if (last != 0) last->next = next;
    }  

  void unlink(void) {
    assert(next && last);
    last->next = next;
    next->last = last;
    last = next = 0;
    }
  };

#endif

Defines link (links are to index).

Index

• <input-error routines>: D1, U2
• <insert a new rectangle>: D1, U2
• <link.h>: D1
• <main()>: D1, U2
• <main.cc>: D1
• <print the rectangle list>: D1, D2, D3, U4
• <read an input spec>: D1, U2
• <read an integer>: D1, U2
• <read an integer pair>: D1, U2
• <read.cc>: D1
• <read.h>: D1
• <rectangle list private data structure>: D1, U2
• <rectangle list public routines>: D1, U2
• <rectangle private routines>: D1, D2, U3
• <rectangle public data>: D1, U2
• <rectangle.h>: D1
• <rect-list.cc>: D1
• <rect-list.h>: D1
• <slide a rectangle>: D1, D2, D3, D4, D5, U6
• <the default rectangle constructor>: D1, U2
• <the rectangle constructor>: D1, U2
• <the rectangle contains predicate>: D1, U2
• <the rectangle list constructor>: D1, U2
• <the rectangle overlapping predicate>: D1, U2
• <the rectangle print operator>: D1, U2
• <the rectangle slide operator>: D1, U2

• add: U1, D2, U3
• badc: U1, U2, D3
• badeof: U1, U2, D3
• contains: U1, D2
• coordinate_in_range: U1, D2
• enclosing: U1, D2, U3
• extract_marked: U1, D2, U3
• insert: U1, U2, D3
• interval_overlapping: D1
• link: U1, D2
• main: D1
• main.cc: D1
• mark_overlapping: U1, D2, U3
• overlapping: U1, U2, D3
• print: U1, U2, D3, U4, D5
• print_levels: U1, D2, U3
• read_an_int: U1, D2
• read.cc: D1
• read_data: U1, U2, D3
• read.h: U1, D2, U3
• read_int_pair: U1, D2
• read_returns: U1, D2, U3
• rectangle: U1, U2, U3, U4, U5, U6, U7, U8, U9, U10, D11, U12, U13, U14
• rectangle.h: U1, U2, D3
• rect-list.cc: D1
• rect-list.h: U1, U2, D3
• rl_link: D1, U2, U3, U4, U5, U6, U7, U8, U9, U10
• set_levels: U1, D2, U3
• slide: U1, U2, D3, D4

This page last modified on 6 April 2001.