PM Pseudocode

If you're having trouble understanding this, be sure to check the on-line PM lectures.

class PMQuadtree {
   class Node; // define this yourself; superclass for Gray and Black;
              // evan used an interface, but this is pseuedocode.

   White SingletonWhiteNode = new White();

   class Gray extends Node {
      Node[] children;
      Rectangle[] regions; // a gray node is a partition
                    //into 4 regions; these rects are those regions

      // parameters here are stuff like the geometry you're adding 
      //and any other info you need on the stack

      Node add(Geometry g, ...) {
         if (g intersects regions[0]) children[0] = children[0].add(...)
         ...
         if (g intersects regions[3]) children[3] = children[3].add(...)
      }

      Node remove(Geometry g, ...) {
         if (g intersects regions[0]) children[0] = children[0].remove(...);
         ...
         if (g intersects regions[3]) children[3] = children[3].remove(...);
         if (all children are white) return SingletonWhiteNode;
         if (three children white, one child black) return the black child;
         if (not all children are gray) {
            Black b = new Black;
            add all geometry in this subtree into b;
            if (b is valid) return b;
            else {
               // this gray is still necessary, so keep it in the tree
               return this;
            }
         }
      }
   }

   class Black extends Node {
      List geometry;
      Node add(Geometry g, ...) {
         add g to geometry
         if (this node is valid) return this;
         else return partition(...);
      }

      Node remove(Geometry g, ...) {
         remove g from geometry
         if (geometry is empty) return SingletonWhiteNode;
            else return this;
      }

      Node partition(...) {
         Gray g = new Gray(...);
         for each item i in geometry {
            g.add(i);
         }
         return g;
      }
   }

   class White extends Node {
      Node add(Geometry g, ...) {
         return new Black(g);
      }

      Node remove(...) { error }
   }
}