You must write an XML application to convert suitably tagged documents into plain text.

A (simplified) well-formed XML document has the following format:

• The first line is the XML declaration <?xml version="1.0"?>
• The remainder of the document includes strings surrounded by matched tags of the form

  <TagName> ... </TagName>

  where any identifier (string of alphanumeric characters starting with a letter) can be used as a tag name, as long as the name in the closing tag matches the name in the opening tag. Pairs of tags can be arbitrarily placed, including nested one within the other, as long as they are properly matched.

(Note that a document encoded in HTML is a tagged text that is meant to be interpreted by a browser, such as the ones marketed by Netscape and Microsoft. View the "page source" of any HTML document to see the tags.)

Your program is an XML application that interprets certain tags as follows:

• Text enclosed by <d> ... </d> declares strings to be saved and numbered by your application (starting at 0). Such strings may include arbitrary characters other than the character < (left angle bracket). Thus

  <d>Humpty Dumpty sat on a wall.</d>
  <d>had a great f</d>
  <d>All the king's horses,
  and </d>
  <d>all men</d><d>couldn't put</d>

  declares 5 strings (one of which includes a newline character).

• Text enclosed by <r> ... </r> must contain exactly three tagged substrings and nothing else as follows:
  1. it must start with <s>i</s> where i is an integer denoting the i^th declared string (counting from 0)
  2. immediately after, it must contain <o>j</o> where j is an integer denoting an offset into that string (where 0 represents the first character)
  3. it must finally contain the string <l>k</l> where k is an integer denoting the length of a substring.

  For example, the text

  <r><s>1</s><o>7</o><l>6</l></r>

  denotes the 6 characters starting from character number 7 in declared string number 1 (namely "reat f" if strings are declared as above).

• Text enclosed by <k> ... </k> may include arbitrary characters other than the character < (left angle bracket) and denotes the string enclosed by the tags. For example,

  <k>xact >>*/ text</k>

  denotes the string "xact  >>*/  text".

• All other text is ignored.

Given such a tagged document as input, your program should remove declarations of strings (tagged with <d>...</d>), replace references (tagged with <r>...</r>) by the substrings they denote, retain kept strings (<k>...</k>) in place, and remove all other text. For example, given the input

would produce as output:

Your solution should include two Java interfaces: one to process XML text (find tags, interpret specific tag semantics such as declaring strings and referencing substrings, etc.) and the other to manage the collection of declared strings (saving them and extracting designated substrings).

Your solution must also include (at least) two Java classes, one to implement each interface. The class that manages the collection of declared strings should use a Vector, since this makes it easy to add another string and to reference the i^th string. (Read C.3.3 in Weiss' text to learn how to use Vectors.)

Your program should report errors if the input is invalid, except that it need not check that ignored tags are properly matched and balanced. For example, you should check that the tags <d>, <r>, <s>, <o>, <l>, and <k> are all properly used, but you need not report an error if other tags are not matched properly (thus you need not report it as an error when given "<A> <B> <C> </A>" even though it is not valid XML).

Pre- and post-conditions are necessary for all methods. Loop invariants are not necessary, but your code must contain sufficient comments to be easily understandable.

Your solution need not be as robust as the sample project, but it must meet the above specifications.

Note the emphasis on testing. Take the information from class and from the notes as well as the sample project as a good guide to what is proper and sufficient testing. Many of the testing marks will come from your test summary file. Be sure it is clear and complete. The sample project shows one acceptable way to set up such a file.

Be sure to submit:

• all your .java files, with your name and ID number included in each file,
• a text file named approach.txt that explains the approach you have taken to solve the problem, highlighting any assumptions or clarifications that you have made, explaining your solution's user interface, and describing and defending how you have chosen to handle illegal data,
• a text file named summary.txt that summarizes your tests,
• one or more pairs of text files named in0.txt and out0.txt, in1.txt and out1.txt, etc. containing your test data and matching program output.

The description of XML given here is quite simplified. You are not required to learn XML for this assignment, beyond the specifications given above. However, if you are interested in exploring this topic further, you may wish to refer to Robin Cover's SGML/XML Web page or to Tim Bray's annotated XML specification.