\documentclass{article}
\usepackage{fullpage}

\begin{document}


\title{CMSC 420 Project--Spring, 2003\\Version 2.02}

\date{Last Modified \today}
\author{ The BIG 420 project.
  \footnote{Participation in this project may prove HAZARDOUS 
  to your health. Unfortunately, failure to participate early 
  and often will definitely have an adverse effect upon your GPA. 
  Take my advice. Start now, because you're already behind. If 
  you don't believe me, ask someone who took this course last semester.}}
\maketitle

\bigskip

\section{General description}
  The primary motivation of this project is of course to get you to build and
  make use of data structures, and to take a look at benefits and shortcomings for each one.
  
  The TA's motivation though is to be able to make pretty pictures with some rudimentary
  drawing primitives.  In project one we'll have you keep track of named dots (of various sizes
  and colors) and analyze and update those dots via a kd tree.  Should be fun ;)

  In future parts of the project we will replace some data structures to examine
  performance tradeoffs.  In particular you can probably expect to see the prof's old
  time favorite the PM1 quadtree, and the TA's favorite the B+ tree.  

  \subsection{Part 1: SkipList and KD Tree}

    This section describes the first portion of the project, comprising development
    of a command line interpreter, a basic data dictionary and the kd
    tree.

    \subsubsection{CMSC420: Introduction to Command Parsing, 
                where nothing could possiblie go wrong.}
      
      You are all blessed with a professor with a Ph.D. in fault tolerance.  
      Because of this you will be expected to develop fault tolerant programs.  This means
      bounds checking for input numbers and checking a number of possible error conditions
      for each command.  It also means that your parser should never fail or crash because
      of a malformed command.  

      A really useful command interpreter would give useful error messages about commands, 
      such as ``wrong number of arguments'', or ``invalid argument type'', or even better
      ``second argument was int, expected string''.  For our purposes it will be sufficient to
      print a single error message regardless of the error:

\begin{verbatim}
        *****
        Error: Invalid Command.
\end{verbatim}

      Note the standard asterisks are printed.  Do not echo the erroneous command.

      Your parser must completely ignore blank lines.  For all other lines which are not
      fully formed and correct commands you must print the above error.  

      As with other parts of the project, your command parser will be tested separately
      from the remaining requirements of the project.  So if you can't get a fully 
      error checking parser you will not be hurt on the other parts of the project.  You may
      assume that for commands other than error checking all commands will be upper case
      and there will be no spaces within a command.  There will be no blank lines and all 
      commands will be valid.  

      A working parser cannot make any of those assumptions.  Commands should be correctly
      interpreted regardless of case (ie. CREATE\_DOT and creaTe\_DOT should both be
      interpreted as the CREATE\_DOT command).  Blank lines should be completely ignored  
      (in particular do not print extraneous ``*****''s).  Whitespace in general should 
      be ignored when parsing with one exception- any string (command name, dot name,
      or string arguement like the colors ``RED'' ``BLUE'', etc) cannot contain internal spaces.
      So a command like create\_dot(foo bar, 5,6, BLUE) should be flagged as invalid.

      

    \subsubsection{Comments on java}

      This semester all projects are to be written in java.
      The version on the detective cluster is 1.4 and can be downloaded at:

      http://java.sun.com/j2se/1.4/download.html

      The online version of the documentation is at 

      http://java.sun.com/j2se/1.4/docs/api/index.html

      I highly recommend you download the java sdk and do most of your work from
      home, if nothing else this will lighten the load on the now overworked dc
      machines ;)  They can be very slow around lower level project due dates ;) 
      Of course as in most cs classes your projects will be
      compiled and run on the detective cluster machines (dc.umd.edu), so you
      should check to be sure your projects work there.  However, there should
      not be any portability issues as long as you develop with the correct java
      version.

      I've heard good things about Borland's free jbuilder (registration
      required); You may wish to look into that. 

      While you are permitted to use any java drawing facility you are comfortable with,
      a simple drawing package is available on the class web page.  It is this package that
      will be most readily supported by the TA's should any problems arise.  The package
      'Canvas.java' provides a simple class which allows drawing of circles , squares,
      lines, captions, and other simple primitives in a java jframe.

    \subsubsection{SkipList.java}
      Another first for this semester is a requirement that some of your data structure code
      implement a standard interface.  This will allow the TA to include your data structure
      in his own code.  
      All of your dictionary classes this semester (currently a skiplist, and 
      later a 2-3 or bplus tree) will implement java's sortedmap interface specified at:

      http://java.sun.com/j2se/1.4/docs/api/java/util/SortedMap.html

      You may of course have any number of other public functions which you find useful 
      for your project.  [edit: I won't change this so late, but I recommend that you *do
      not* add extra public functions so that your class stays interchangeable with TreeMap]

      As the TA implements this interface with own skiplist he may reduce this requirement
      by allowing you to skip some of the interface requirements.  [edit: see the news group
      for functions which you may skip] If that happens I still think
      it would be a very beneficial exercise to implement the entire interface.

      The class must be named SkipList.java (note the case) and be located in a package called 
      cmsc420.  For a tutorial on packages see:

      http://java.sun.com/docs/books/tutorial/java/interpack/

    \subsubsection{KD Tree- order 2}
      Unlike with the skiplist you are free to implement the kd tree any way you like with
      no particular interface.  I will though recommend the use of java's point classes 
      (point2d) which will allow you to easily make use of java's geometric algorithms later
      on.  I would also suggest that you generally try to follow the java Collection interface.
      Standards are good things ;)

      Examining the command decoder, pay particular attention to the MAP\_ALL() function,
      which represents to the most common historical use of a kd tree.  The primary purpose
      of the kd tree is to perform 'orthogonal range search' (ie. the rectangle search in
      the command decoder), which with a balanced tree has guaranteed O(sqrt(n)+k) run time, 
      where k is the number
      of elements actually found.  You'll note that you can count the number of points without
      actually visiting them all in O(sqrt(n)) time.  
                             
    \subsubsection{Part 1 Command Specification\label{cs1}}
   
      You will build a command decoder with a small set of commands; you 
      will expand it later to accommodate commands required for future parts.

      The following is a list of commands you should support for part 1 and a description of
      the output you should give for each one.  Note that for all functions, you should 
      print \verb|''*****\n''| followed by a \verb|'' ==> ``| and an echo of the command given.  
      For instance, the entire valid output to CLEAR\_ALL() is 

\begin{verbatim}
*****
 ==> CLEAR_ALL()
All structures are cleared.
\end{verbatim}

      The sample output should make this clear.  This is done to negate the
      effects of input redirection and to assist in grading.
      Note that although it is done in the samples that will appear later, 
      you are not required to reformat the original command 
      (fixing spacing, for instance) in any way.


      The definitions below will use the following standard BNF definitions. 

\begin{verbatim}
          <dotlist>:=<dot><nl><dotlist>|<dot><nl>
          <dot>:= <name> at (<int>,<int>) color:<color>
          <color>:= RED|GREEN|BLUE|BLACK|WHITE
          <DNE>:=Error: The specified dot does not exist.<nl> 
\end{verbatim}
      Whenever a <double> appears(not in this part, but it will come up later), it means a floating
      point decimal number printed with exactly three digits after the decimal place 
      (including trailing zeros as necessary).

      Also, when looking at the list of errors, eg.

\begin{verbatim}
     <error>:= <DNE>|<NR>|<AI>|<DC>|<NZ>
\end{verbatim}

      the leftmost applicable error should always be the one printed.  
        

      \begin{description}

        \item [CREATE\_DOT(name, x, y, radius, color)] creates a 'dot' object with the
         appropriate name, coordinates, radius, and color.
         The dot will then be added to a skiplist sorted based on the name (the
         data dictionary) and to one based on the coordinates.  The latter structure is
         used to check for duplicate coordinates. 
 
         Coordinates will be non-negative.  This should be an O(logn) operation where n is 
         the number of dots already in the dictionary.  The dots should be stored in an 
         asciibetically sorted SkipList. (If you don't complete a working skiplist you should
         use a TreeMap here instead to get some credit).

         If a dot with the same name already exists print an error. If a dock already exists
         at the specified coordinates print an error.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Created dot <dot>.<nl>
         
          <error>:=<AE>|<DC>
          <AE>:=Error: Dot <name> already exists.<nl>
          <DC>:=Error: Dot <other\_dot\_name> already exists at the specified coordinates.
\end{verbatim}

        \item [DELETE\_DOT(name)] Removes the dot with the given name from the data dictionary.
         If the dot does not exist print an error.  If the given dot has already been added
         to the kd tree map print an error and do not remove it from the dictionary.  Delete
         from the dictionary should be O(logn), checking for existence in the kd tree will be
         dependent on the structure of the tree.  


\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Delete dot <name>.<nl>
         
          <error>:=<DNE>|<AA>
          <AA>:=Error: Dot <name> has already been mapped and cannot be deleted.
\end{verbatim}


        \item [LIST\_DOTS()] 
          Lists all dots in the data dictionary 
          in increasing asciibetical order.  This function will be used as a measure of 
          success for the CREATE\_DOT function.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>

          <success>:=<dotlist>
          <error>:= Dictionary is empty.<nl>
\end{verbatim}

        \item [COLOR\_DOT(name,color)] Changes the color of the dot with the specified
          name to the color given. The change should be reflected in the map, however the
          kd tree itself should not be accessed for this operation. 

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Color of <name> changed from <oldcolor> to <color>.<nl>
         
          <error>:=<DNE>
\end{verbatim}

        \item [MAP\_DOT(name)] inserts the specified dock into kd tree map. 
          If the dot does not exist in the dictionary 
          print an error message.  The kd tree is expected to be constructed in standard 
          fashion, which means that your tree should be exactly the same as the TA's (so
          long as the map\_all function is never called). 

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Dot <name> has been added to the map.<nl>

          <error>:=<DNE>|<AI>
          <AI>:=Error: The specified dot has already been added to the map.
\end{verbatim}

        \item [MAP\_ALL()] This function will build an ideal (log n depth)
          kd tree from all the
          dots currently in the dictionary.  In practice kd trees are often built to 
          analyze data that already exists, rather than being constructed point by point.  A 
          kd tree of order 2 built this way has guaranteed theta(logn) depth and O(sqrt(n))
          rectangle query search time.  The first part of this operation should be to remove
          any dots which are currently in the kd tree.  The run time of this function should be
          O(nlogn) expected.

          
\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=All dots have been added to the map.<nl>

          <error>:= Dictionary is empty.<nl>
\end{verbatim}



        \item [COUNT\_RECTANGLE(lx,ly, ux,uy)] prints the number of dots on the map 
          whose coordinates are within the closed rectangle determined by the four 
          points: (lx,ly),(lx,uy),(ux,ly),(ux,uy).
          Your program should be as efficient as possible, in particular it is not
          necessary to visit every point in order to get a correct count.  If the kd tree is
          built using the MAP\_ALL command then this should run in O(sqrt(n)) time.

\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Total count: <int>.<nl>
\end{verbatim}

        \item [COLOR\_RECTANGLE(lx,ly,ux,uy,color)] This function locates all dots in the 
          kd tree map whose coordinates are contained within the closed region determined 
          by the four points: (lx,ly),(lx,uy),(ux,ly),(ux,uy)
          and sets their color to the one specified.  Success can be determined with the DRAW\_MAP
          or LIST\_DOTS commands
 
\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Update complete.
\end{verbatim}

        \item [PRINT\_KD\_TREE()]  prints the output of traversing the
          kd tree in {\em preorder}.  If the MAP\_ALL function as not been called
          then your output should match the TA's exactly.
          The output format is identical to that of LIST\_DOTS, except for the order that the
          dots are printed and the error message for an empty tree.        

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>

          <success>:=<dotlist>
          <error>:= Tree is empty.<nl>
\end{verbatim}


        \item [DRAW\_MAP()]  Draws all the points of the map using the java canvas class.
           (If you're good with java graphics you are not required to use the canvas class,
           but your output should be similar).  Your program should stop running until the
           graphics window is closed(this is the default behavior of the canvas class).

\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Drawing complete.
\end{verbatim}

        \item [DRAW\_KD\_TREE()]  Same as the DRAW\_MAP function, except that the partitions
          of the kd tree are also displayed.  Examples will be provided.

\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Drawing complete.
\end{verbatim}
      \end{description}


  \subsection{Part 2: PM1 quadtree and ShortestPath}


    \subsubsection{Adjacency List- updated}
                             

      The first [smaller] part of this project will be to implement and use an 
      adjacency list.  You'll recall that an adjacency is conceptually a 'list of lists', ie: 
      
      
\begin{verbatim}
A->C->D
C
D
F->K->J
H->K
J
K
\end{verbatim}


      After much deliberation, for this project it has been decided that you will implement
      this structure as a Skiplist of Skiplists.  Code re-use is good stuff, and a skiplist
      is functionally(as far as writing your program) no worse 
      than any of the java API classes that are available.  If you don't like your own SkipList
      you may inherit someone elses from project 1.  Note that insertion/deletion from this 
      structure is O(log(n)log(m)), where n is the number of nodes in the graph and m is the 
      degree of the graph (the max number of edges incident to a single vertex).  This represents
      a binary search to find the correct row of the list to find the starting vertex, followed
      by a a binary search to check for existance of the ending vertex.  

      You are guaranteed that all paths in this project will be bidirectional.  This means that
      you need only store each edge once instead of twice, giving you half the memory usage and
      half the access time but making your graph less general.  
      This optimization is up to you(it's not much to implement).
        

      You'll use the graph to implement shortest path using dijkstra's algorithm.  If you have
      a fibbonacci heap handy the run time of this algorithm is O(V*lg(V)+E) 
      (where E is the number of edges and V is the number of vertices).  And a fibonacci heap
      is what you ask?  Well, I have no idea, but those of you who go on to take algorithms
      classes will no doubt hear about fibonacci heaps again, and I just wanted to be the first
      to share.  Let's just say that they are magical, and that you will probably *never* learn how
      they work.  If you've put this spec on paper, feel free to X is this paragraph to avoid 
      reading it ever again.  End digression.  


      So anyway, you will be required to do shortest path in O(ElgV).  It would be nice if you
      understand where this bound comes from, so I will explain it below, but as with the
      KDTree it suffices that if you implement the algorithm correctly, that is the runtime you
      will have.

      Allow me to sketch the algorithm to explain the running time(I'm not trying to 
      teach the algorithm here- see your book/class/newsgroup/google).  
      Every iteration of this
      algorithm you are guaranteed to find the correct shortest path to exactly one 
      node- so we know right away there will be V iterations.  At each state your graph is 
      split in two sections- the 'solved' section, for which you know the correct distances,
      and the rest, which have some distance values associated with them which may or may not
      be accurate- this set is stored in some kind of priority queue. An iteration begins by selecting the node (call it 'N')
      from this 
      queue with the best distance value, adding it to the 'solved' set, and 'relaxing' all it's
      edges.  Relaxing is when for each node adjacent to N we see if it is faster  
      to get to that node through
      N than it's current best known path.  We update distances and back-pointers 
      appropriately (so we know what
      the shortest path actually is when we finish), and that ends the round.  Note
      that if a node's distance value is changed, its position in the priority queue has to be 
      fixed up somehow. (this is where the magical fibonnaci heap would come into play, it's got an 
      advantage in this 'fix up' step).  One way to do this is just to have multiple copies
      of the same node in the queue and ignore them when they come back up (this is the approach
      I will use in the explanation), or else to remove the old value before reinserting it. Either works.

      Now, how long does all this take.  There are V rounds, and in every round we have to 
      pull something out of the front of the 
      priority queue- which with a skiplist is an O(1) expected time operation(note that it would be
      log(E) in a balanced binary tree), so each round takes O(V) time.  Rather than try and deal 
      with how many elements are added to and removed from the queue in any single round, it 
      is easier to think about how many such operations can occur in the life of the algorithm.
      Every single edge in the graph has exactly one opportunity
      to add a vertex to the queue (during a relax operation), so there are O(E) possible insertions.
      If we allow duplicates, the size of the queue can grow to O(E), so we may treat each 
      queue operation as O(log(E)).  That gives O(ElogE) running time for all queue operations
      during the life of the algorithm.  Together that gives a running time of O(V+ElgE), which
      since E is bounded by $V^2$, is O(ElgV).  And that's the required running time of your search;)

      Yes, your adjacency list is to be a skiplist of skiplists, and you should go ahead and 
      use your skiplist for the priority queue (you may either use the O(logn) operation to
      remove the head of the list, or you may implement a 'pop' or 'shift' operation that runs
      in O(1) expected/amortized time.  Why expected?  Well, you have update that tower for
      that node- and the tower may be up to about O(logn) height.  Recall though that the *average*
       height of a node is only 2.  

      You might want to understand this stuff- you might have occasion to want to explain it
      to someone someday,or something...  ;)

    \subsubsection{PM1 Quadtree}

      In a bit of spontaneity I've made one change to our usual quadtree.  The INIT\_QUADTREE()
      function will allow the user to specify the dimensions of the quadtree at runtime.
      (in the past we always fixed the size at 1024x1024).  In exchange you may prevent your 
      leaf nodes from ever splitting beyond 1x1 cells.  Any two objects that fall into a 1x1
      cell will be treated as an intersection.  

      Because no one objected, I am mandated that we all build our trees in a standardized way, 
      so that the structure appears identical.  Your tree
      and nodes will have to follow the following standard rules:

      \begin{enumerate}
        \item No two points can fall in the same node
        \item A point cannot be contained in the same node as a segment, unless that point is 
          an endpoint of that segment.
        \item No two segments can fall in the same node, unless they intersect at a shared
          endpoint *and* that endpoint is contained in the *same* node. 
        \item If a point falls on the boundary between more than one node, then it must 
          be added to every node that it intersects (a point may be contained in up to four
          leaf nodes).
        \item If a single point of a segment falls on the boundary of more than one node
          then it must be added to all of those nodes as above.  (A single segment can of course
          appear in a *lot* of nodes).
        \item The tree must at all times be minimal- that is, there must never be a smaller 
          tree which follows all of the above rules and still contains all of the same data. This
          should only be a complicated issue during deletion.
      \end{enumerate}

      In no case should you try to attempt to solve any pm1 problems with brute force.  All that
      is generally required is logical pruning- ie. "If the segment does not overlap my southeast 
      child, then don't try adding it to that child!"

      And oh yes, unlike in the book, *our* skiplists have (0,0) at the southwest corner and *not*
      the northwest corner(the inverted coordinate system used by your monitor and most graphics 
      apps). 

      Since there are a lot of complexities in how you build your quadtree there will be less 
      stringent speed requirements then there were in P1.  Still, try to make it as 
      efficient as you can!  There will still be benchmarks, and many kudos at least for the 
      fastest implementations(maybe extra credit, but I have no say in that).  Don't brute force,
      please? :)    

      That should be all you need to know to build a quadtree!

    \subsubsection{Part 2 Command Specification\label{cs2}}
   
      You will build a command decoder with a small set of commands; you 
      will expand it later to accommodate commands required for future parts.

      The following is a list of commands you should support for part 2 and a description of
      the output you should give for each one.  Note that for all functions, you should 
      print \verb|''*****\n''| followed by a \verb|'' ==> ``| and an echo of the command given.  
      For instance, the entire valid output to a hypothtical *wink wink* CLEAR\_ALL() command
      would be: 

\begin{verbatim}
*****
 ==> CLEAR_ALL()
All structures are cleared.
\end{verbatim}

      This is done to negate the
      effects of input redirection and to assist in grading.
      Note that although it is done in the samples that will appear later, 
      you are not required to reformat the original command 
      (fixing spacing, for instance) in any way.


      The definitions below will use the following standard BNF definitions. 

\begin{verbatim}
          <dotlist>:=<dot><nl><dotlist>|<dot><nl>
          <dot>:= <name> at (<int>,<int>) color:<color>
          <color>:= RED|GREEN|BLUE|BLACK|WHITE
          <DNE>:=Error: The specified dot does not exist.<nl> 
\end{verbatim}
      Whenever a <double> appears, it means a floating
      point decimal number printed with 
      exactly three digits after the decimal place 
      (including trailing zeros as necessary). To do this in java check out the NumberFormat class.
      
      Also, when looking at the list of errors, eg.

\begin{verbatim}
     <error>:= <DNE>|<NR>|<AI>|<DC>|<NZ>
\end{verbatim}

      the leftmost applicable error should always be the one printed.  
        

      \begin{description}

        \item [INIT\_QUADTREE(size)] Sets the upper bounds for the quadtree.  After 
         initialization the quadtree should hold points/lines that fall between [0,0] at the
         southwest/lower left hand corner, and [$2^{size}, 2^{size}$] in the northeast upper
         right hand corner.  If size is less than 2 or more than 30 print an error.  This 
         command will always precede the first command which requires the quadtree.  This 
         command is only valid the first time it is successfully called (out of range is 
         not a successful call).  If an  attempt is made to reinitialize the tree, print an 
         error.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Quadtree initialized.<nl>
         
          <error>:=<OOR>|<INIT>
          <OOR>:=Error: size out of range.<nl>
          <INIT>:=Error: The Quadtree has already been initialized.<nl>
\end{verbatim}


        \item [CREATE\_DOT(name, x, y, radius, color) UNCHANGED] 
         Creates a 'dot' object with the
         appropriate name, coordinates, radius, and color.
         The dot will then be added to a skiplist sorted based on the name (the
         data dictionary) and to one based on the coordinates.  The latter structure is
         used to check for duplicate coordinates. 
 
         Coordinates will be non-negative.  This should be an O(logn) operation where n is 
         the number of dots already in the dictionary.  The dots should be stored in an 
         asciibetically sorted SkipList. 

         If a dot with the same name already exists print an error. If a dock already exists
         at the specified coordinates print an error.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Created dot <dot>.<nl>
         
          <error>:=<AE>|<DC>
          <AE>:=Error: Dot <name> already exists.<nl>
          <DC>:=Error: Dot <other\_dot\_name> already exists at the specified coordinates.
\end{verbatim}
***
        \item [DELETE\_DOT(name)] Removes the dot with the given name from the data dictionary.
         If the dot does not exist print an error.  If the given dot has already been added
         to the Adjacency List (via CREATE\_PATH()) print an error and do not remove 
         it from the dictionary.  If it has already been added to the PM1 (via MAP\_SEGMENT())
         print an error.  Delete from the skiplist should be O(logn).  
         Some slowdown may occur from checks to the adjacency list and PM1 if either is 
         non-empty.  This command will likely be used to verify that you can search for points
         in those structures ;)
\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted dot <name>.<nl>
         
          <error>:=<DNE>|<AA>|<ZZ>
          <AA>:=Error: Dot <name> has already been added to the Adjacency List.
          <ZZ>:=Error: Dot <name> has already been added to the Quadtree.
\end{verbatim}


        \item [LIST\_DOTS() UNCHANGED] 
          Lists all dots in the data dictionary 
          in increasing asciibetical order.  This function will be used as a measure of 
          success for the CREATE\_DOT function.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>

          <success>:=<dotlist>
          <error>:= Dictionary is empty.<nl>
\end{verbatim}

        \item [COLOR\_DOT(name,color) UNCHANGED] Changes the color of the dot with the specified
          name to the color given. The change should be reflected in the map, however only
          the skiplist should be accessed for this operation. 

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Color of <name> changed from <oldcolor> to <color>.<nl>
         
          <error>:=<DNE>
\end{verbatim}



        \item[CREATE\_PATH(name1, name2)] adds a bidirectional path between the dots
           named to the Adjacency List.  If one or both dots does not exist print the <DNE>
           for the first argument not found.  If the segment already exists print an error.
           This command is not related to the PM1.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Created segment (name1,name2).<nl>
          <error>:=<DNE>|<AI>
         
          <AI>:=Error: The specified segment already exists.
\end{verbatim}


        \item[DELETE\_PATH(name1, name2)] Deletes the edge between name1 
          and name2 from the Adjacency list.  If
          either endpoint does not exist, or the edge does not exist print 
          an error. This command
          is not related to the PM1. 

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted Segment (name1,name2).<nl>
         
          <error>:=<DNE>|<SDNE>|<AM>
          <SDNE>:=Error: The specified segment does not exist.
\end{verbatim}
 
        \item[SHORTEST\_PATH(name1,name2)] Prints the shortest path from 
          the first dot to the second dot based on the segments in the Adjacency List. 
          If either name is not in the dictionary print an error. 
          If there is no path between the two dots (possibly because one of the endpoints
          was never added to the adjacency list) then print an error. 
          Otherwise print out the shortest path, followed by the total length of the path. 

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>

          <success>:= <name1> -> <moredots> <nl>Total length:<double>.<nl>
          <moredots>:= <dotname> -> <moredots>| <name2>
          <error>:= <DNE>|<NP>
          <NP>:= Error: No path exists.
\end{verbatim}


        \item[MAP\_SEGMENT(name1,name2)]  Adds a segment to the PM1.It is possible 
          that name1==name2,
          this should not be an error.  The PM1 should be able to know whether any given 
          point has a path to itself or not.  There is one further error to detect.  If the segment
          intersects a segment already in the tree(except for shared endpoints),
          print an error and leave the PM1 unchanged.
          You may use this error even if the segment intersected is the same as the one you
          are trying to insert.  Further discussion on interesection detection rules will
          appear on the newsgroup and later versions of the spec.
          This command is unrelated to the CREATE\_PATH command.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Mapped segment (name1,name2).<nl>
          <error>:=<DNE>|<ID>
         
          <ID>:=Error: Intersection detected.
\end{verbatim}

        \item[UNMAP\_SEGMENT(name1,name2)] Deletes a segment from the PM1.  If the points do 
          not exist, or the segment does not exist, print an error.  If after the operation
          an endpoint would be left with no adjacent segments then it should also be completely
          removed from the tree.  The tree should be collapsed so that it is minimal- which
          basically means that the tree should look as if the segment had never been in the
          tree to begin with. (Some collapsing will need to be done).  Remember that if 
          (A,A) is explicitly added to the tree via MAP\_SEGMENT, then 
          (A,A) must be unmapped before A is removed.


\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>
          <success>:=Unmapped Segment (name1,name2).<nl>

          <error>:=<DNE>|<SNF>
          <SNF>:=Error: The specified segment was not found on the map.
\end{verbatim}



        \item [COLOR\_SEGMENTS(lx,ly,ux,uy,color)] A twist on the old version.  This function
          will first locate all segments in PM1 which {\em OVERLAP} the specified 
          inclusive rectangular region(determined by (lx,ly),(lx,uy),(ux,ly),(ux,uy)).
          Then it will change the color of the endpoints of those segments to the color 
          specified.  The endpoints will not necessarily be in the tree.  Print the
          number of unique segments matched.  
          Success can also be determined with the DRAW\_MAP or LIST\_DOTS commands
 
\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Update complete.  Found <int> segments.
\end{verbatim}

        \item [PRINT\_QUADTREE()] Prints out the PM1 Quadtree map. Be sure to read the 
          section on the PM1 to understand what its structure must be. 
          When printing you must print in the following order: Northwest, 
          Northeast, Southwest, Southeast. 
          If you reach a leaf with a dot in it you should print the dot's name, followed
          by all the dots it is adjacent to in some order.  If a black leaf does not contain an 
          endpoint dot, print the segment that passes through it.  A tree with only one isolated
          point created by MAP\_SEGMENT(A,A) should have output:

\begin{verbatim}
          A:A
\end{verbatim}

          IE., a one element tree should look like a leaf, even if not implemented that way.

\begin{verbatim}
          Output summary:
          <output>:=<success>|<error>

          <success>:= <pmtree><nl>
          <pmtree>:=<black_node><nl>|<white_node><nl>|<nl><grey_node>
          <grey_node>:= NW <pmtree> NE <pmtree> SW <pmtree> SE <pmtree> 
          <black_node>:=<name>:<namelist>|<segment><nl>
          <white_node>:= 
          <namelist>:= <name><namelist>|<name>
          <segment>:= (<name1>,<name2>)     

          <error>:= Tree is empty.<nl>
\end{verbatim}



        \item [DRAW\_MAP()]  Draws all the points and segments of the pm1 map using the 
           java canvas class.  The points should be displayed as in part1, the lines can be
           plain solid black lines.
           (If you're good with java graphics you are not required to use the canvas class,
           but your output should be similar).  Your program should stop running until the
           graphics window is closed(this is the default behavior of the canvas class).

\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Drawing complete.
\end{verbatim}

        \item [DRAW\_QUADTREE()] Draws the internal partitions of the quadtree, as well
          as the segments inside it.  Do not draw the pretty colorful dots, as they will
          just get in the way of debugging.  

\begin{verbatim}
          Output summary:
          <output>:=<success>
          <success>:=Drawing complete.
\end{verbatim}
      \end{description}


  \subsection{Submission Instructions}

    To make your submission file, make a directory and copy all required files into 
    it.  Change to that directory and type:

\begin{verbatim}
           tar -cvf part#.tar *
           gzip part#.tar
\end{verbatim}
 
    To submit type(submit will usually be working 1 week before the due date):

\begin{verbatim}
           ~mhs20001/Bin/submit # part#.tar.gz
\end{verbatim}

    In all cases '\verb|#|' represents the number of the project part you are submitting(1,2,3 or 4).
    The filename is not really important; It is important that the file is in .tar.gz format and
    that your Main.java and other required files are not in a subfolder of the tar file.

    You must include the following with every submission: All necessary source files 
    (*.java etc.) to compile your program.  A file called README, all upper case,
    which contains your name, login id, and any information you would like to add.  

    If you leave out the README  your project will 
    fail to submit!

    You are welcome to use a makefile for development (javac doesn't track dependencies very well)
    but I should be able to run your project with the following two commands:

\begin{verbatim}
           javac Main.java
           java Main
\end{verbatim}
 

   No promises are made that I will read your READMEs, but they are useful
   when problems come up with a project. 

   There is a 100K filesize limit.  Please don't include .class files- I will probably
   strip them out before testing your projects anyway.

   Every early submission will overwrite the previous early submission, every
   ontime submission will overwrite any previous ontime submissions, every 1day late 
   submission will overwrite any previous 1day late submission and so on. So I will
   have one submission for every valid submission period.  (Late policy TBA).
   I will grade every submission that is saved(including applicable bonuses and penalties)
   and you will get the highest grade among them

   If there are any errors in my IO you are still responsible for them- the
   spec is what is in charge.  So if you match all my current IO and submit early 
   and then someone points out that I printed the wrong error message for some
   function, you have to fix your project and resubmit ;) You should be
   coding to match the command specification, not my sample IO.

   Here is a (c++) makefile that you might use as a hint for 
   how to set up dependencies for make.  

\begin{verbatim}
CC = cxx
FLAGS =
LFLAGS = -lm

proj4: bpnode.o bptree.o cell.o main.o pmedge.o pmpoint.o  pmquadtree.o util.o
	$(CC) $(LFLAGS) *.o -o proj4

bpnode.o: bpnode.cpp bpnode.h bpdata.h
	$(CC) -c $(FLAGS) bpnode.cpp

bptree.o: bptree.cpp bptree.h bpdata.h
	$(CC) -c $(FLAGS) bptree.cpp

cell.o: cell.cpp cell.h bpdata.h pmpoint.h pmedge.h celledge.h
	$(CC) -c $(FLAGS) cell.cpp

main.o: main.cpp bptree.h cell.h celledge.h pmedge.h pmpoint.h util.h psdraw.h $
	$(CC) -c $(FLAGS) main.cpp                     

pmedge.o: pmedge.cpp pmedge.h pmpoint.h util.h
	$(CC) -c $(FLAGS) pmedge.cpp

pmpoint.o: pmpoint.cpp pmpoint.h pmedge.h
	$(CC) -c $(FLAGS) pmpoint.cpp

pmquadtree.o: pmquadtree.cpp pmquadtree.h pmpoint.h pmedge.h util.h psdraw.h
	$(CC) -c $(FLAGS) pmquadtree.cpp

util.o: util.h util.cpp
	$(CC) -c $(FLAGS) util.cpp

clean:
	rm -f *.o
	rm -f proj4
	rm -f core 
\end{verbatim}




  \subsection{Grading}

   There will be a few parts to grading your projects
   Your projects will be graded running them on a number of test files for
   which I have already created correct(we hope) output.  Your output 
   will have all punctuation, blank lines, and non-newline
   whitespace stripped before diffing similarly cleaned files.  

   New to this semester some of your data structures may be included with the TAs own
   testing code to test their efficiency and correctness.  In addition, there may be
   some subjective grading based on your drawing functions.  

   Some text output cannot always be graded by simply diffing because there
   is no guarantee that we will have the same output.
   In these cases your project's output will be pre-processed. 
   In the case of the B+ tree, for instance, this program will verify that each
   node has the correct number of keys, that they are correctly ordered, and that all
   the correct data is at the leaves(and any other rules I may have left out).  

   Thanks to the miracle of automation you should expect your projects to be run on
   very very large inputs.

   Typically each test file will be worth 10 points, and you will be eligible for either
   10 or 0 points depending on whether you pass for fail that test.  There is no partial
   credit for an individual test.  I may give points projects 
   that fail a test because of 'small' errors after initial grading
   at my own discretion.  The tests will try to test mutually exclusive components of
   your projects independently. However, if you don't have a dictionary which at least 
   correctly stores all 
   points so that some 'get lost', you may still end up failing a k-d tree test.  So, 
   if you can't get the skiplist to work you may wish to replace it with a functional TreeMap
   so you can get credit for the rest of the project.  (This holds for other
   structures as well later on).


  \subsection{Standard Disclaimer: Right to Fail(twice for emphasis!)}

    As with most programming courses, the instructor reserves 
    the right to fail any student who does not
    make a good faith effort to complete the project.  

    If you have problems with completing any given part of the project 
    please talk to Dr. Hugue
    immediately- do not put it off!  While the TA enjoys failing students, Dr. Hugue
    does not, so please be kind and do the project.  A submission that gets only 20 or 30
    points is considerably better for you than no submission at all. 



  \subsection{Integrity Policy}
From Dr. Hugue:


    Your work is expected to be your own or to be labeled with its source,
    whether book or human or web page. Discussion of all parts of the project
    is permitted and encouraged, including diagrams and flow charts. However,
    pseudocode writing together is discouraged because it's too close to
    writing the code together for anyone to be able to tell the difference.

    Since the projects are interrelated, and double jeopardy is not my goal, we
    have a very liberal code use and reuse policy. First and foremost, use of
    code produced by anyone who is or has ever taken 420 from me requires
    email from provider and user to be sent to the instructor.

    The instructor is the sole arbiter of code use and reuse, and reserves the
    right to fail any student who does not make a good faith effort on the
    project, or who refuses to adhere to the policies stated herein.

    Remember, it is better to ask and feel silly, than not to ask and receive a
    complimentary F or XF.

\end{document}

