A4: HTML Validator/Basic DOM Operation Overview You are tasked with creating a basic HTML parser to perform a *very* limited subset of what a web browser does behind the scenes to setup the DOM for displaying the page and interaction with JavaScript. Deliverables a4.cpp will be submitted to A4 Coding assignment on Autolab. o This will be the file containing your full C++ code for the required functions. o You must put your name and person number on your file in the provided space or it will not be accepted for grading. o You are allowed 10 submissions to Autolab. If you submit more than 10 times, you will be penalized 5 points per submission. o If your code contains memory leaks, your score will be deducted by 20 points. You dont need to worry about destroying the trees created, but if you lose memory while creating it, you will lose points. a4-written.pdf will be submitted to A4 Analysis assignment on Autolab. o This will be the file containing the requested written analysis for your assignment. o This file will not be accepted late. Start Early!!!!!!!! Late Policy The policy for late submissions is as follows: Before the deadline: 100% of what you earn (from your best submission). Each day late: additional 20-point penalty (lower your earned points by 20, minimum of 0). > 2 days late: 0 points. Keep track of the time if you are working up until the deadline. Submissions become late after the set deadline. Please note the change in submission time. CSE 250 Spring 2017 Objectives In this assignment, you will create Useful Resources You may want to review stack and queue functionality for this assignment. The following links will also likely be helpful: 1. HTML Validator This will help you check if your example code you try to write to test your code is valid or not. 2. DOM Intro This provides some background on the document object model (DOM). You dont need to be an expert on this to do the assignment. This provides some simple images and explanation. Instructions Download the file a4-handout.zip and extract the skeleton files. Rename the skeleton files appropriately. A CMakeLists.txt file is included to properly build your program. You may use this by Importing the folder into CLion, or from the command line by the following commands: cmake . make You will have to add the function definitions in a4.cpp. This is the only file you will submit, so make sure you put all of your code within this file. You may not use any other standard libraries aside from: o , , , , , , , Required: Your first task is to write code to validate a subset of HTML code. The following will provide an overview of HTML tags. We will be considering the tags: html, head, body, title, div, p, br, span The tags have the following restrictions on their contents/children: html must have exactly 2 children: head and body. The head element must come first. head must have exactly 1 child: title. May not contain any other tags. body may contain any number (0 or more) of the tags: div, p, br, span. May contain text. title may only contain text. Must not be empty. div may contain any number of the tags: div, p, br, span. May contain text. p may contain any number of the tags: br, span. May contain text. br Self closing tag. Contains no content. span may only contain text. The following rules apply to the creation of tags: CSE 250 Spring 2017 Tag names are not required to be lowercase. All tags must come as a pair of an opening tag and a closing tag unless the tag is self-closing. A tag may not close inside of any other tag that opened after it. If a tag is self-closing, the tag may appear as either or A tag may contain an attribute called the id. This is a string that may not contain spaces and may not be empty. It would appear as . An id may not appear in a closing tag. The following rules apply to whitespace (tabs, new line, spaces) within a document: All whitespace in a document is treated as a space (i.e., the character ' '). All whitespace is omitted between the '>' symbol at the end of a tag (open or close), and the start of the next tag or content text. All strings of consecutive whitespace are treated as a single space. This happens both within a tag and within the content (e.g., 4 spaces to indent code in a document would be displayed as a single space on a page). In the descriptions above, text means any string (including the empty string, unless specified otherwise). Any number includes 0. 1) HTML VALIDATION (20 points): For an HTML document to be valid, we have to check the following: The first tag overall is of the form The document is required to contain a valid html tag. For this part, you will complete the definition of bool html_is_valid (const std::string& document) where: The string document contains the entire contents of a file to validate. Return true if the document contains valid html code as described above. Return false if any of the rules/specifications were violated. 2) Build the DOM tree (20 points): For a valid HTML page, we can view the Document Object Model (DOM) for the page. As each tag is nested within another, we can view the page as a tree-like object. In this case, we can consider the root of the tree as the html tag, and then everything falls as a descendent. For this part, you should complete the definition of Tag* generate_DOM_tree (const std::string& document) where: Each tag should be represented by a Tag object within the tree. Any text within a tag should be put into a Tag object with the name value "content" o Tag objects with the name "content" should never contain empty content strings. CSE 250 Spring 2017 Tag objects should contain: o name the tag name (e.g., html, head, etc.) o id the id assigned by the id attribute within the tag. Leave as an empty string if none is given in the tag. o content for any tag other than "content" or "title" this should be left empty. For "content" and "title" tags this should never be empty. o displayed leave this as false for now. o children an object of type std::vector containing all child nodes, if any exist, in the order they appear going top down (so the first tag should be index 0, the second tag should be index 1, and so on). You may assume that only valid HTML will be given to this function. 3) Determine all visible objects within the DOM tree (15 points) There may be many elements on a page, but they may not appear visually on the page. Here, your task is to determine which elements will be visible. A Tags displayed property should be set to true if: The Tag name is "content" or "title" The Tag contains a child node that has the property "displayed" set to true. Complete the definition of void determine_visible_objects(Tag* const root) where you correctly set flags for "displayed" within the Tag nodes in the given tree. 4) Generate string output containing all visible elements (15 points) Given a tree of elements within the page and correctly setting the displayed properties, printout all the nodes that are visible, nesting them appropriately, and displaying content when necessary. Tag name should be on its own line, indenting by 2 spaces at a time. The Tags content and title should display on the next line, indented, the content string associated with them (the line following should return to the same indentation). Tags that have their "displayed" flag set to false should be omitted. Complete the definition of std::string print_visible_elements(Tag* const root) where you correctly construct a string to display only visible elements. Make sure you test your output formatting! 5) Document getElementByID (10 points) Given a tree of elements, find an element by a given ID. Complete the definition of Tag* getElementByID(Tag* const root, const std::string& id) where: The Tag object inside the tree with the given ID is returned. If no Tag is found with the requested ID or ID is the empty string, nullptr is returned. You may assume each ID is unique. CSE 250 Spring 2017 6) Written Analysis (20 points) For each of parts 3 and 5: Write pseudocode that explains the process you performed to compute the function. Analyze the runtime and space usage using asymptotic notation. Testing To test your code, you should write tests in the main function in main.cpp. The default code provides some basic functionality to read a file and check if it is valid. You should add tests here and create more HTML files. Feel free to share HTML files on Piazza with one another (you should share it as an attachment as Piazza will treat tags as HTML). Submission Code Submission (80 points): You must submit your a4.cpp file to the A4 Coding assignment on Autolab. Your submission must compile and run on Autolab. I suggest that you compile often as you build your code to avoid difficulties debugging syntax and other errors. Make sure your code does not leak memory. You will lose 20 points if your code leaks memory. Tests will be run on your file and your score will be reported to you when finished. For this assignment there is a limit of 10 submissions. Please test your code and ensure it compiles and completes the task prior to submitting. Written Submission (20 points): You must submit your a4-written.cpp file to the A4 Analysis assignment on Autolab. You should include the pseudocode and analysis for your determine_visible_objects and getElementByID functions.