Table of Contents

• Rectangles
• Rectangle Sets
• Yard
• Mpool
  • Input
• Utilities
• Index

Rectangles

<rectangle.h>=

#ifndef _rectangle_h_defined_
#define _rectangle_h_defined_

struct rectangle {

  unsigned x, y, h, w;


  // Return this rectangle's height.

     unsigned ht() const {
       return h;
       }


  // Return true iff the given rectangle extends this one.

     bool is_extended_by(const rectangle & r) const;


  // Return this rectangle's smallest x coordinate.

     unsigned min_x() const {
       return x;
       }


  // Return this rectangle's largest x coordinate.

     unsigned max_x() const {
       return x + w + (w ? -1 : 0);
       }


  // Return this rectangle's smallest y coordinate.

     unsigned min_y() const {
       return y;
       }


  // Return this rectangle's largest y coordinate.

     unsigned max_y() const {
       return y + h + (h ? -1 : 0);
       }


  // Return true iff this rectangle is larger (in area) than the given
  // rectangle.

     bool operator > (const rectangle & r) const;


  // Create a rectangle of the given size.

     rectangle(unsigned x, unsigned y, unsigned ht, unsigned wd)
       : x(x), y(y), h(ht), w(wd) { }


  // Create a default rectangle.

     rectangle()
       : x(0), y(0), h(0), w(0) { }


  // Return this rectangle's width.

     unsigned wd() const {
       return w;
       }
  };

#endif

<rectangle.cc>=

#include "rectangle.h"

bool rectangle::
is_extended_by(const rectangle & r) const {
  return (r.y ≤ y) ∧ (y + h ≤ r.y + r.h);
  }


bool rectangle::
operator > (const rectangle & r) const {
  return h*w > r.h*r.w;
  }


#ifdef TESTINGRECTANGLES

// gcc -o test-rectangles -DTESTINGRECTANGLES -ansi -pednatic -Wall -g rectangle.cc && ./test-rectangles

#include <cassert>

int main() {
  rectangle r1(0, 2, 3, 4);
  assert(r1.is_extended_by(r1));
  assert(not (r1 > r1));

  rectangle r2(0, 1, 3, 4);
  assert(not r2.is_extended_by(r1));
  assert(not r1.is_extended_by(r2));

  rectangle r3(0, 1, 5, 4);
  assert(r1.is_extended_by(r3));
  assert(not r3.is_extended_by(r1));
  assert(r3 > r2);
  assert(not (r2 > r3));
  }

#endif

Rectangle Sets

<rectangle-set.h>=

#ifndef _rectangle_set_h_defined_
#define _rectangle_set_h_defined_


#include "rectangle.h"
#include "rectangle-set.h"


class rectangle_set {

  public:

    // Return true iff there are more rectangles in the iteration sequence.

       bool more() const;


    // Return the next rectangle in the iteration sequence.

       const rectangle & next() const;


    // Assign the given rectangle set to this one.

       rectangle_set & operator = (const rectangle_set &);


    // Add the given rectangle to this rectangle set.

       void operator += (const rectangle & r);


    // Add the rectangles in the given set to this rectangle.

       void operator += (const rectangle_set & recs);


    // Return the first rectangle in the iteration sequence.

       const rectangle & start() const;


    // Create an initially empty rectangle set.

       explicit rectangle_set();


    // Create a rectangle set that's a copy of the given rectangle set.

       rectangle_set(const rectangle_set &);


    // Get rid of this rectangle set.

      ~rectangle_set();

  private:

    unsigned max, cnt;
    rectangle * rectangles;
    mutable unsigned cursor;

    void copy_rectangles(const rectangle_set &);
  };


#endif

<rectangle-set.cc>=

#include <cassert>
#include <cstring>
#include "rectangle-set.h"


void rectangle_set::
copy_rectangles(const rectangle_set & rs) {

  // Copy the given rectangle-set state into this one.

  rectangles = new rectangle[rs.max];
  cnt = rs.cnt;
  max = rs.max;
  memcpy(rectangles, rs.rectangles, sizeof(rectangle)*cnt);
  }


bool rectangle_set::
more() const {
  return cursor < cnt;
  }


const rectangle & rectangle_set::
next() const {
  if (cursor < cnt)
    cursor++;
  return rectangles[cursor];
  }


rectangle_set & rectangle_set::
operator = (const rectangle_set & r) {
  if (this ≠ &r) {
    delete [] rectangles;
    copy_rectangles(r);
    }
  return *this;
  }


void rectangle_set::
operator += (const rectangle & r) {
  assert(cnt < max);
  rectangles[cnt++] = r;
  }


void rectangle_set::
operator += (const rectangle_set & recs) {
  assert(cnt + recs.cnt < max);
  for (unsigned i = 0; i < recs.cnt; i++)
    rectangles[cnt++] = recs.rectangles[i];
  }


rectangle_set::
rectangle_set() 
  : max(100), cnt(0), rectangles(new rectangle[max]) {
  }


rectangle_set::
rectangle_set(const rectangle_set & rs) {
  copy_rectangles(rs);
  }


rectangle_set::
~rectangle_set() {
  delete [] rectangles;
  }


const rectangle & rectangle_set::
start() const {
  cursor = 0;
  return rectangles[0];
  }


#ifdef TESTINGRECTANGLESETS

// g++ -o test-rectanglesets -DTESTINGRECTANGLESETS -ansi -pedantic -Wall -g rectangle-set.cc rectangle.cc && ./test-rectanglesets

int main() {
  rectangle_set rs;
  rectangle r1(0, 1, 2, 3);
  assert(not rs.extends(r1));
  for (rectangle r = rs.start(); rs.more(); r = rs.next())
    assert(false);

  rs += r1;
  assert(rs.extends(r1));
  for (rectangle r = rs.start(); rs.more(); r = rs.next())
    assert(r.x == r1.x and r.y == r1.y and r.ht == r1.ht and r.wd == r1.wd);
  }

#endif

Yard

<yard.h>=

#ifndef _yard_h_defined_
#define _yard_h_defined_


#include "rectangle.h"
#include "rectangle-set.h"


class yard {

  public:

    // Add the given obstacle to this yard; throw an exception if the obstacle
    // excedes the yard boundries.

       void add_obstacle(const rectangle & r);


    // Return true iff there are more rectangle sets left in the iterator
    // sequence.

       bool more() const;


    // Set this yard equal to the given yard.

       yard & operator = (const yard &);


    // Return the next rectangle set the iterator sequence.

       rectangle_set next() const;


    // Return the first rectangle set in the iterator sequence.

       rectangle_set start() const;


    // Create a yard with the given dimensions.

       yard(const rectangle &);


    // Create a yard with the default dimensions.

       yard();


    // Create a yard equal to the given yard.

       yard(const yard &);


    // Get rid of this yard.

      ~yard();


  private:

    rectangle border;
    char **y;
    mutable unsigned cursor;

    rectangle_set get_band_rectangles(unsigned i) const;
    void free_yard();
    void init_yard(const rectangle &);
    void copy_yard(const yard &);
  };


#endif

<yard.cc>=

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


void yard::
add_obstacle(const rectangle & r) {

  if ((r.x + r.w > border.w) ∨ (r.y + r.h > border.h))
    throw std::string("Obstacle outside of yard boundry");

  unsigned 
    xmin = r.x,
    xmax = xmin + r.w,
    ymin = r.y,
    ymax = ymin + r.h;

  if (xmin > 0) xmin--;
  if (xmax < border.w) xmax++;
  if (ymin > 0) ymin--;
  if (ymax < border.h) ymax++;

  for (unsigned row = xmin; row < xmax; row++)
    for (unsigned col = ymin; col < ymax; col++)
      y[row][col] = 1;
  }


void yard:: 
copy_yard(const yard & y) {

  // Copy the state from the given yard to this one.

  init_yard(y.border);
  for (unsigned col = 0; col < y.border.w; col++)
    memcpy((this→y)[col], y.y[col], sizeof(char)*y.border.h);
  }


void yard:: 
free_yard() {

  // Free space allocated by this yard.

  for (unsigned i = 0; i < border.w; i++)
    delete [] y[i];
  delete [] y;
  }


rectangle_set yard::
get_band_rectangles(unsigned i) const {

  // Return the set of rectangles found in the yard column with the given
  // index.

  rectangle_set recs;

  if (i < border.w) {
    const char * const col = y[i];
    unsigned j = 0;

    while (true) {
      while ((j < border.h) and col[j]) j++;
      if (jhtml_symbol(ge)border.h) break;

      unsigned h = j + 1;
      while ((h < border.h) and not (col[h])) h++;
      recs += rectangle(i, j, h - j, 1);
      
      j = h;
      }
    }

  return recs;
  }


void yard::
init_yard(const rectangle & b) {

  // Initialize this yard using the given yard boundries.

  border = b;
  y = new char * [b.w];
  for (unsigned col = 0; col < b.w; col++) {
    y[col] = new char [b.h];
    memset(y[col], 0, sizeof(char)*b.h);
    }
  }


bool yard::
more() const {
  return cursor < border.w;
  }


rectangle_set yard::
next() const {
  return get_band_rectangles(++cursor);
  }


yard & yard::
operator = (const yard & y) {
  if (this ≠ &y) {
    free_yard();
    copy_yard(y);
    }
  return *this;
  }


rectangle_set yard::
start() const {
  cursor = 0;
  return get_band_rectangles(cursor);
  }


yard::
yard(const rectangle & b) { 
  init_yard(b);
  }


yard::
yard() : border(0, 0, 0, 0), y(0) {
  }


yard::
yard(const yard & y) {
  copy_yard(y);
  }


yard::
~yard() {
  free_yard();
  }


#ifdef TESTINGYARD

// g++ -DTESTINGYARD -g -o test-yard -ansi -pedantic -Wall yard.cc rectangle.cc rectangle-set.cc && ./test-yard

static void test(const yard & y) {
  unsigned i = 0;
  for (rectangle_set rs = y.start(); y.more(); rs = y.next()) {
    unsigned j = 0;
    for (rectangle r = rs.start(); rs.more(); r = rs.next()) {
      assert(((2 == r.y) ∧ (1 == r.h)) ∨ ((6 == r.y) ∧ (2 == r.h)));
      j++;
      }
    assert(2 == j);
    i++;
    }
  assert(10 == i);
  }


int main() {
  yard y(rectangle(0, 0, 10, 10));
  unsigned i = 0;
  for (rectangle_set rs = y.start(); y.more(); rs = y.next()) {
    unsigned j = 0;
    for (rectangle r = rs.start(); rs.more(); r = rs.next()) {
      assert((0 == r.y) ∧ (10 == r.h));
      j++;
      }
    assert(1 == j);
    i++;
    }
  assert(10 == i);

  y.add_obstacle(rectangle(0, 9, 1, 10));
  i = 0;
  for (rectangle_set rs = y.start(); y.more(); rs = y.next()) {
    unsigned j = 0;
    for (rectangle r = rs.start(); rs.more(); r = rs.next()) {
      assert((0 == r.y) ∧ (8 == r.h));
      j++;
      }
    assert(1 == j);
    i++;
    }
  assert(10 == i);

  y.add_obstacle(rectangle(1, 0, 1, 8));
  i = 0;
  for (rectangle_set rs = y.start(); y.more(); rs = y.next()) {
    unsigned j = 0;
    for (rectangle r = rs.start(); rs.more(); r = rs.next()) {
      assert((2 == r.y) ∧ (6 == r.h));
      j++;
      }
    assert(1 == j);
    i++;
    }
  assert(10 == i);

  y.add_obstacle(rectangle(1, 4, 1, 8));
  test(y);
  yard y2(y);
  test(y2);
  yard y3;
  y3 = y;
  test(y3);

  y.add_obstacle(rectangle(0, 0, 10, 10));
  i = 0;
  for (rectangle_set rs = y.start(); y.more(); rs = y.next()) {
    for (rectangle r = rs.start(); rs.more(); r = rs.next())
      assert(false);
    i++;
    }
  assert(10 == i);

  y = yard(rectangle(0, 0, 10, 10));
  y.add_obstacle(rectangle(0, 0, 5, 5));
  i = 0;
  for (rectangle_set rs = y.start(); y.more(); rs = y.next()) {
    unsigned j = 0;
    for (rectangle r = rs.start(); rs.more(); r = rs.next()) {
      assert(((6 == r.y) ∧ (4 == r.h)) ∨ ((0 == r.y) ∧ (10 == r.h)));
      j++;
      }
    assert(1 == j);
    i++;
    }
  assert(10 == i);
  }

#endif

Mpool

Input

<read input>= (U→)

try { y = read_yard(std::cin); }
catch (std::string emsg) {
  std::cerr << "! " + emsg + ".\n";
  exit(EXIT_FAILURE);
  }

<read procedures>= (U→) [D→]

static yard
read_yard(std::istream & in) {
  yard y = read_yard_dimension(in);
  read_obstacles(in, y);
  return y;
  }

Defines read_yard (links are to index).

<read procedures>+= (U→) [←D→]

static yard
read_yard_dimension(std::istream & is) {

  std::string str;
  if (not read_nonblank_string(is, str))
    throw std::string("No input found");

  std::istringstream iss(str);
  rectangle border;
  border.x = border.y = 0;
  if (not (iss >> border.h >> border.w))
    throw std::string("Error during yard-size read");

  char c;
  if (iss >> c)
    throw std::string("Junk at end of yard-size line");

  return yard(border);
  }

Defines read_yard_dimension (links are to index).

<read procedures>+= (U→) [←D→]

static void
read_obstacles(std::istream & is, yard & y) {

  std::string str;

  while (read_nonblank_string(is, str))
    y.add_obstacle(parse_rectangle(str));
  }

Defines read_obstacles (links are to index).

<read procedures>+= (U→) [←D→]

static rectangle
parse_rectangle(const std::string & str) {

  rectangle r;

  std::istringstream iss(str);
  if (not (iss >> r.x >> r.y >> r.h >> r.w))
    throw std::string("Error during obstacle read");

  char c;
  if (iss >> c)
    throw std::string("Junk at end of obstacle-definition line");

  return r;
  }

Defines parse_rectangle (links are to index).

<read procedures>+= (U→) [←D→]

static bool
read_nonblank_string(std::istream & is, std::string & str) {

  while (std::getline(is, str))
    if (not is_blank_string(str))
      return true;

  return false;
  }

Defines read_nonblank_string (links are to index).

<read procedures>+= (U→) [←D]

static bool
is_blank_string(const std::string & str) {

  for (unsigned i = 0; i < str.size(); i++)
      if (not isblank(str[i]))
        return false;

  return true;
  }

Defines is_blank_string (links are to index).

<mpool.cc>=

#include <iostream>
#include <string>
#include <cstdlib>
#include <sstream>
#include "rectangle.h"
#include "rectangle-set.h"
#include "yard.h"
#include "utils.h"


// Deja vu, c++ style.

   static yard read_yard(std::istream &);
   static yard read_yard_dimension(std::istream &);
   static rectangle mpool(const yard &);


int 
main() {
  yard y;

  <read input>

  const rectangle r = mpool(y);
  std::cout << r.x << " " << r.y << " " << r.h << " " << r.w << "\n";
  }


static rectangle
mpool(const yard & y) {

  rectangle max_rec;
  rectangle_set active_recs;
  
  for (rectangle_set band_recs = y.start(); y.more(); band_recs = y.next()) {
    rectangle_set new_active_recs;
    rectangle r;

    for (r = active_recs.start(); active_recs.more(); r = active_recs.next())
      new_active_recs += extended_rectangles(r, band_recs);

    for (r = band_recs.start(); band_recs.more(); r = band_recs.next()) 
      if (not covers_rectangle(new_active_recs, r))
        new_active_recs += r;

    active_recs = new_active_recs;
    
    for (r = active_recs.start(); active_recs.more(); r = active_recs.next())
      if (r > max_rec)
        max_rec = r;
    }

  return max_rec;
  }


<read procedures>

Utilities

<utils.cc>=

#include <algorithm>
#include "utils.h"


inline bool 
covers_rectangle(const rectangle & r1, const rectangle & r2) {

  // Return true iff r1 covers r2.

  return (r1.min_y() ≤ r2.min_y()) ∧ (r2.max_y() ≤ r1.max_y());
  }


bool 
covers_rectangle(const rectangle_set & rs, const rectangle & r) {
  for (rectangle r1 = rs.start(); rs.more(); r1 = rs.next()) {
    if (covers_rectangle(r1, r))
      return true;
    }
  return false;
  }


static bool
extend_rectangle(const rectangle & r1, const rectangle & r2, rectangle & r3) {

  if ((r1.min_y() > r2.max_y()) ∨ (r1.max_y() < r2.min_y()))
    return false;

  const unsigned y = std::max(r1.min_y(), r2.min_y());
  r3 = rectangle(r1.min_x(), y, 
                 std::min(r1.max_y(), r2.max_y()) - y + 1, r1.wd() + 1);

  return true;
  }


rectangle_set
extended_rectangles(const rectangle & r, const rectangle_set & recs) {

  rectangle_set new_recs;

  for (rectangle r2 = recs.start(); recs.more(); r2 = recs.next()) {
    rectangle r3;
    if (extend_rectangle(r, r2, r3))
      new_recs += r3;
    }

  return new_recs;
  }


#ifdef TESTINGUTILS

// g++ -o test-utils -g -ansi -pedantic -Wall -DTESTINGUTILS utils.cc rectangle-set.cc rectangle.cc && ./test-utils

#include <cassert>

static bool
operator == (const rectangle & r1, const rectangle & r2) {
  return (r1.x == r2.x) ∧ (r1.y == r2.y) ∧ (r1.h == r2.h) ∧ (r1.w == r2.w);
  }

static void
test_extend_rectangle() {
  rectangle r(0, 5, 3, 1), r2;
  assert(not extend_rectangle(r, rectangle(0, 8, 1, 1), r2));
  assert(extend_rectangle(r, rectangle(0, 7, 1, 1), r2) and
         (r2 == rectangle(0, 7, 1, 2)));
  assert(extend_rectangle(r, rectangle(0, 6, 1, 1), r2) and
         (r2 == rectangle(0, 6, 1, 2)));
  assert(extend_rectangle(r, rectangle(0, 5, 1, 1), r2) and
         (r2 == rectangle(0, 5, 1, 2)));
  assert(not extend_rectangle(r, rectangle(0, 4, 1, 1), r2));

  assert(not extend_rectangle(r, rectangle(0, 8, 2, 1), r2));
  assert(extend_rectangle(r, rectangle(0, 7, 2, 1), r2) and
         (r2 == rectangle(0, 7, 1, 2)));
  assert(extend_rectangle(r, rectangle(0, 6, 2, 1), r2) and
         (r2 == rectangle(0, 6, 2, 2)));
  assert(extend_rectangle(r, rectangle(0, 5, 2, 1), r2) and
         (r2 == rectangle(0, 5, 2, 2)));
  assert(extend_rectangle(r, rectangle(0, 4, 2, 1), r2) and
         (r2 == rectangle(0, 5, 1, 2)));
  assert(not extend_rectangle(r, rectangle(0, 3, 2, 1), r2));

  assert(not extend_rectangle(r, rectangle(0, 8, 3, 1), r2));
  assert(extend_rectangle(r, rectangle(0, 7, 3, 1), r2) and
         (r2 == rectangle(0, 7, 1, 2)));
  assert(extend_rectangle(r, rectangle(0, 6, 3, 1), r2) and
         (r2 == rectangle(0, 6, 2, 2)));
  assert(extend_rectangle(r, rectangle(0, 5, 3, 1), r2) and
         (r2 == rectangle(0, 5, 3, 2)));
  assert(extend_rectangle(r, rectangle(0, 4, 3, 1), r2) and
         (r2 == rectangle(0, 5, 2, 2)));
  assert(extend_rectangle(r, rectangle(0, 3, 3, 1), r2) and
         (r2 == rectangle(0, 5, 1, 2)));
  assert(not extend_rectangle(r, rectangle(0, 2, 3, 1), r2));

  assert(not extend_rectangle(r, rectangle(0, 8, 4, 1), r2));
  assert(extend_rectangle(r, rectangle(0, 7, 4, 1), r2) and
         (r2 == rectangle(0, 7, 1, 2)));
  assert(extend_rectangle(r, rectangle(0, 6, 4, 1), r2) and
         (r2 == rectangle(0, 6, 2, 2)));
  assert(extend_rectangle(r, rectangle(0, 5, 4, 1), r2) and
         (r2 == rectangle(0, 5, 3, 2)));
  assert(extend_rectangle(r, rectangle(0, 4, 4, 1), r2) and
         (r2 == rectangle(0, 5, 3, 2)));
  assert(extend_rectangle(r, rectangle(0, 3, 4, 1), r2) and
         (r2 == rectangle(0, 5, 2, 2)));
  assert(extend_rectangle(r, rectangle(0, 2, 4, 1), r2) and
         (r2 == rectangle(0, 5, 1, 2)));
  assert(not extend_rectangle(r, rectangle(0, 1, 4, 1), r2));
  }

static void
test_covers_rectangle() {
  rectangle r(0, 5, 3, 1);
  assert(not covers_rectangle(r, rectangle(0, 8, 1, 1)));
  assert(covers_rectangle(r, rectangle(0, 7, 1, 1)));
  assert(covers_rectangle(r, rectangle(0, 6, 1, 1)));
  assert(covers_rectangle(r, rectangle(0, 5, 1, 1)));
  assert(not covers_rectangle(r, rectangle(0, 4, 1, 1)));

  assert(not covers_rectangle(r, rectangle(0, 8, 2, 1)));
  assert(not covers_rectangle(r, rectangle(0, 7, 2, 1)));
  assert(covers_rectangle(r, rectangle(0, 6, 2, 1)));
  assert(covers_rectangle(r, rectangle(0, 5, 2, 1)));
  assert(not covers_rectangle(r, rectangle(0, 4, 2, 1)));
  assert(not covers_rectangle(r, rectangle(0, 3, 2, 1)));

  assert(not covers_rectangle(r, rectangle(0, 8, 3, 1)));
  assert(not covers_rectangle(r, rectangle(0, 7, 3, 1)));
  assert(not covers_rectangle(r, rectangle(0, 6, 3, 1)));
  assert(covers_rectangle(r, rectangle(0, 5, 3, 1)));
  assert(not covers_rectangle(r, rectangle(0, 4, 3, 1)));
  assert(not covers_rectangle(r, rectangle(0, 3, 3, 1)));
  assert(not covers_rectangle(r, rectangle(0, 2, 3, 1)));

  assert(not covers_rectangle(r, rectangle(0, 8, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 7, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 6, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 5, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 4, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 3, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 2, 4, 1)));
  assert(not covers_rectangle(r, rectangle(0, 1, 4, 1)));
  }

int main() {
  test_extend_rectangle();
  test_covers_rectangle();
  }

#endif

<utils.h>=

#ifndef _utils_h_defined_
#define _utils_h_defined_

#include "rectangle-set.h"
#include "rectangle.h"

// Split the given rectangle according to the given rectangle set; return a set
// of the split rectangles.  The assumption is that r will be split into at
// least once.

   extern rectangle_set extended_rectangles(
     const rectangle &, const rectangle_set &);

// Return true iff the given rectangle is covered by one of the rectangles in
// the given rectangle set.

   extern bool covers_rectangle(const rectangle_set &, const rectangle &);

#endif

Index

• <mpool.cc>: D1
• <rectangle-set.cc>: D1
• <rectangle-set.h>: D1
• <rectangle.cc>: D1
• <rectangle.h>: D1
• <utils.cc>: D1
• <utils.h>: D1
• <yard.cc>: D1
• <yard.h>: D1
• <read input>: D1, U2
• <read procedures>: D1, D2, D3, D4, D5, D6, U7

• is_blank_string: U1, D2
• parse_rectangle: U1, D2
• read_nonblank_string: U1, U2, D3
• read_obstacles: U1, D2
• read_yard: U1, D2, U3
• read_yard_dimension: U1, D2, U3