新南威尔士大学COMP2521Assignment1课业解析 题意： 实现一个C语言的抽象数据类型textbuffer的各种操作 解析： 包含下列操作：TB newTB (char *text);开辟新的空间用给定的text内容初始化；void releaseTB (TB tb);释放内存，之后不可访问；char *dumpTB (TB tb, bool showLineNumbers);按格式按行显示textbuffer存贮的内容，如果showLineNumbers是True，那么显示每行的行号，false则不显示，如下： text原内容： hello world amazing dumpTB(tb,True)结果： 1.hello world\n2.amazing\n；dumpTB(tb,Flase)结果： hello world\namazing\n int linesTB (TB tb);返回行数；void addPrefixTB (TB tb, int from, int to, char *prefix);给指定行数添加前缀；如addPrefixTB (tb, 1, 3, “goodnight “)给tb的1至3行添加前缀 goodnight；类似地void deleteTB (TB tb, int from, int to);删除from至to行的内容；void mergeTB (TB tb1, int pos, TB tb2);在tb1的pos行插入tb2的内容，之后释放tb2；void pasteTB (TB tb1, int pos, TB tb2);和merge类似但是保留tb2；TB cutTB (TB tb, int from, int to);剪切from至to行的内容；Match searchTB (TB tb, char *search);在tb中搜索search的内容，返回起始字母的行号列号。 涉及知识点： 文本处理 更多可加微信讨论 微信号g19963812037 pdfCOMP2521 Assignment 1TextbufferSubmissionSpecificationJump to FAQYour task is to implement an abstract textbuffer data type that meets the given interface.You will submit the C code implementing the textbuffer ADT (textbuffer.c).This page describes the interface of the textbuffer ADT that you are to implement. For your implementation, downloadtextbuffer.c below and implement the type struct textbuffer as well as all of the functions whose prototypes are givenin the header file textbuffer.h. All your code should go in textbuffer.c, which you have to submit.Changelog1st OctoberProofreadingLine numbers now always start at 1Changed charIndex in struct _matchNode to columnNumberChanged int showLineNumbers in dumpTB to bool showLineNumbersAdded a stub test file testTextbuffer.c for students to write testsImproved formatting/style of textbuffer.c and textbuffer.hAdded some clarifications to the spec2nd OctoberAdded clarifications for searchTB to the FAQAdded a line to testTextbuffer.c that calls linesTBUpdated the comment for addPrefixTB in textbuffer.c to be consistent with textbuffer.h3rd OctoberAdded a clarification for pasteTB to the FAQAdded a clarification about bonus marksAdded a clarification for formRichText – “Note that the # character must be the first character in a line and there mustbe more characters on that line for it to be treated as a special character – otherwise, it does nothing.”Moved testing for memory leaks from Style Marks to Autotesting Marks4th OctoberAdded a question to the FAQ under newTB on the input text being NULL.Fixed the answer to one of the newTB questions: “Unless text is the empty string, it will always have a newline at theend.”8th OctoberAdded details to the FAQ on how diffTB will be testedAdded an example for diffTB to the FAQ9th OctoberAdded details to “Late Submission” sectionBonus marks can now only make up for lost marks in the labs and the second assignment – not the midterm exam. Sorry!11th OctoberRemoved confusing question about abort from the FAQ13th OctoberSubmission instructions are now available14th OctoberAdded a clarification for dumpTB to the FAQ – the returned string should always be allocated such that that the user canfree it.Added a clarification for searchTB to the FAQ about returning an empty list15th OctoberRemoved the -O flag from the compilation line and replaced it with -g, which supports debugging. (-O is just anoptimisation flag, which is unnecessary for this assignment.)Clarified and removed vagueness from the ‘Compactness’ requirement for diffTB. There is now no ‘model solution’.Instead, you’ll pass each test if the number of commands in your edit solution is smaller than some threshold, determinedby the sizes of the optimal and brute-force solutions (see the section for diffTB for details).Added a link to download all dryrun filesAdded clarifications on undoing cutTB and pasteTB to the FAQ.19th OctoberAdded some clarifications/examples based on questions asked on WebCMS.MarksThe assignment is worth 10 marks. The mark breakdown is as follows:ComponentMarkAutotesting of functionality8 (+2 bonus)Subjective evaluation of style2Due to the bonus challenges, you could get up to 12 marks for the assignment. Any extra marks obtained during thisassignment (in excess of the usual 10 marks) can be used to make up for lost marks in the labs and the second assignment.Automarking – 8 (+2) MarksWe will run a number of tests against your textbuffer implementation. These will be much more comprehensive than the testswe run during submission. You get marks for each test you pass.We will also test your program for memory leaks (memory you have allocated and have responsibility to free but never free’d)and memory errors. Your program will be tested for memory leaks/errors via valgrind.Style – 2 MarksStyle marks will include comments, indentation, variable names, etc., and will also include marks for choosing an appropriaterepresentation for your ADT and for the efficiency of the functions you implement. For example, you will lose marks if yourimplementation of a function has a time complexity of O(n^2) when there is a solution with a time complexity of O(n) or O(n* log n).SubmissionDeadline: 9am, Saturday 26 October 2019.You need to submit one file: textbuffer.cYou can submit from the assignment page on WebCMS via the give interface or by running the command below:give cs2521 assign1 textbuffer.cThe submission system runs a few simple dryrun tests. All files used by the dryrun are available here (click here to downloadthe whole lot). After the deadline, all functions will be more thoroughly tested by the automarking system.You can submit multiple times – only your last submission will count.Late SubmissionA late penalty of 15% per day will be applied. The latest you can submit the assignment is 9am, 31 October 2019, of coursewith late penalty.Files1.2. textbuffer.h1.2. textbuffer.c1.2. testTextbuffer.cNote: When we test your assignment, it with be compiled with gcc and the following flags:gcc -Wall -Werror -std=c11 -g -lm -o testTextbuffer testTextbuffer.c textbuffer.cADT SpecificationThe following is a description of the components of theinterface.As marks are awarded by an automated marking program, you must follow this specification precisely. Otherwise, you riskgetting few or no marks! You must NOT modify the textbuffer.h file.The ADT typeWe represent the ADT by way of a handle of type TB. The handle type is declared in the header file, but you will have toprovide an implementation of the handle representation – i.e. of struct textbuffer – as part of your implementation:typedef struct textbuffer *TB;Refer to the lecture about ADTs for examples of this construction.Required properties of the implementationA textbuffer is an ordered collection of strings, where each string represents one line of a text file. Your implementation mustkeep the lines of a textbuffer in a linked data structure (such as a linked list or a variant of that). Each line must berepresented as a (dynamically allocated) string. Adding, deleting, or moving lines requires manipulation of the linked structure.Such a data structure may, for example, be used as part of a text editor.Constructor and destructornewTBTB newTB (char *text);newTB allocates a new textbuffer and initialises its contents with the text in the given string. Each fragment of the string thatends with a newline character (‘\n’) indicates a separate line in the textbuffer.releaseTBvoid releaseTB (TB tb);releaseTB frees the memory occupied by the given textbuffer. It is an error to access a textbuffer after freeing it.Query functionsThe following functions do not alter their textbuffer argument.dumpTBchar *dumpTB (TB tb, bool showLineN
umbers);dumpTB allocates and returns a string containing the text in the given textbuffer. The returned string should contain newlinecharacters (‘\n’) to indicate the end of each line in the textbuffer. It is the caller’s responsibility to free the memory occupiedby the returned string. If there are no lines in the textbuffer, return an empty string (the string should still be allocated). IfshowLineNumbers is true, prepend a line number (along with a dot and space) to each line of the output.For example, if dumpTB was called on a textbuffer containing the lines “hello world” and “amazing”, andshowLineNumbers was true, it should return “1. hello world\n2. amazing\n”. If showLineNumbers was false, itshould instead return “hello world\namazing\n”.linesTBint linesTB (TB tb);linesTB returns the number of lines in the given textbuffer.Textbuffer editingFor all editing functions, if any of the arguments indicating a line number is out of range (i.e., smaller than 1 or bigger than thenumber of lines in the textbuffer), the function must print a suitable error message and terminate the program with the standardfunction abort().The first line of a textbuffer is at position/index 1.addPrefixTBvoid addPrefixTB (TB tb, int from, int to, char *prefix);addPrefixTB adds the supplied prefix to all lines between from and to (inclusive). If to is less than from, abort.For example, consider calling addPrefixTB (tb, 1, 3, “goodnight “):+ —————————- + + ———————————— +| room | | goodnight room || moon | —> | goodnight moon || cow jumping over the moon | | goodnight cow jumping over the moon || light | | light |+ —————————- + + ———————————— +deleteTBvoid deleteTB (TB tb, int from, int to);deleteTB deletes the lines between from and to (inclusive) from the textbuffer tb. It should free the memory of the deletedlines. If to is less than from, abort.Combining textbuffersFor all combining functions, if any of the arguments indicating a line number is out of range, the function must print a suitableerror message and terminate the program with the standard function abort().Note that for these functions, if the number of lines in tb1 is n, then n + 1 is a valid argument for pos (the lines in tb2 areadded to the end of tb1).mergeTBvoid mergeTB (TB tb1, int pos, TB tb2);mergeTB merges tb2 into tb1 at line pos. Afterwards, what was at line 1 of tb2 will now be at line pos of tb1. Line pos oftb1 will be moved to line pos + linesTB (tb2), after the merged-in lines from tb2. After this operation, tb2 cannot be usedanymore (as if we had used releaseTB on it).pasteTBvoid pasteTB (TB tb1, int pos, TB tb2);pasteTB copies (i.e., pastes) all lines from tb2 into tb1 at line pos. It is like mergeTB, but tb2 remains unmodified and is stillusable independent of tb1.Extracting textbuffersFor all extracting functions, if any of the arguments indicating a line number is out of range, the function must print a suitableerror message and terminate the program with the standard function abort().The textbuffers returned by the extracting functions are as if they were newly created with newTB().cutTBTB cutTB (TB tb, int from, int to);cutTB cuts the lines between from and to (inclusive) out of the textbuffer tb into a new textbuffer, which is then returned. Ifto is less than from, return NULL.Searching textbuffersMatch searchTB (TB tb, char *search);searchTB returns a linked list of all non-overlapping matches in tb of a certain string. The search is case sensitive and thetextbuffer tb must remain unmodified. The matches must be returned in order of their appearance in the textbuffer. It is thecaller’s responsibility to free the returned list.Consider calling searchTB (tb, “love”) on the following TB:1 Hello World My2 name is jarred lovegood3 and i love carley ray jepsonThis should return a list:+====================+ +====================+| lineNumber: 2 | | lineNumber: 3 || columnNumber: 16 | | columnNumber: 7 || next: —————–>| next: —————–> NULL+====================+ +====================+Note that the line number and column number are both 1-indexed (i.e., start at 1). The column number refers to a positionwithin the line where there is a match.Note that Match is a pointer to the first node in the list. If there are no matches, then return NULL.Rich textformRichTextvoid formRichText (TB tb);formRichText searches every line of tb and performs the following substitutions:StringReplacementExample*some string*some string*hello* -> hello_some string_ some string_hello_ -> hello#some string …

some string …

#hello ->

hello

The matching is simplistic in that you would begin scanning at the first special character and continue to consume characters(ignoring any further special characters) until a matching special character. If there is no matching special character, nothing isdone and the next special character (if there is one) is processed.Note that the # character must be the first character in a line and there must be more characters on that line for it to be treated asa special character – otherwise, it does nothing. Furthermore, it matches until the end of the line and not until a matching #. Seeexample below.ExampleResult*some string*some string*some string*lol*some stringlol** * *some_string*again_ some_stringagain_*some* _string_some stringsome *string_again_ some *stringagainsome#string*once_again* some#stringonce_again#string_stuff_

string_stuff_

# ####

##

Example ResultIn the case of nested special characters, for example:*some_string_*#some _string_Take the outermost element and ignore any nesting.Example Result*some_string_* some_string_#some _string_

some _string_

If there are no characters between a pair of consecutive special characters, for example, hello ** world, ignore it andcontinue to the next pair of special characters (if there is one). For example:hello ** world –> hello ** worldhello **world* –> hello *worldhello **world** –> hello *world***hello***world** –> *hello*world****hello* –> **helloNote that in the last case, the first * does nothing because there are no characters between it and the next *. In that case the first* is ignored and the next one is processed as normal.Assignment 1 Bonus ChallengesdiffTB (1 bonus mark)char *diffTB (TB tb1, TB tb2);Given two text files, we sometimes want to know what changes are made from one file to another file.The function diffTB works out which lines of texts are added or deleted from tb1 to get tb2. The string returned from thefunction is an edit solution consisting of a series of add and delete commands. Applying such commands on tb1 in sequenceshould result in tb2.An edit solution should have one command per line to either add or delete a line of text at a specific line number. An exampleis given below. The first command adds a line of text ‘add this line please’ at line 2 of the current textbuffer (counting from 1).The existing line 2 is moved to line 3, and so on. The second command deletes line 3 of the textbuffer. The last command addsthe specified text at line 12 of the textbuffer.+,2,add this line please-,3+,12,add this line as well pleaseA mark is given if your solution satisfies two criteria given below:Correctness – applying your edit solution on tb1 results in tb2.Compactness – the size of your edit solution (i.e., number of commands/lines) is smaller than or equal to the average ofthe sizes of the optimal solution and the brute-force solution (which is “delete all lines of tb1 and add all lines of tb2”).This is to avoid brute-force solutions, such as the one just described.undoTB and redoTB (1 bonus mark)void undoTB (TB tb);undoTB allows the user to reverse up to 10 of the most-recently called operations on tb. Applicable operations are: deleteTB,mergeTB, pasteTB, and cutTB. Each time undoTB is called, one
operation is reversed on tb. When the maximum number ofallowable undo operations is reached, further calls to undoTB should do nothing (until one of the applicable operations isperformed again or redoTB is called).void redoTB (TB tb);The function redoTB allows the user to redo operations that have been reversed by undoTB. Similar to undoTB, this functionshould redo one operation on tb per function call. However, when a new operation is called on tb, any reversed operationscannot be executed again with redoTB.Note: When testing your undoTB and redoTB functions, we will not call inapplicable operations such as addPrefixTB andformRichText, so you do not have to worry about undoing such operations.COMP2521 Assignment 1 FAQGeneral questionsCan I modify textbuffer.h?No.Can I add my own structs and functions to textbuffer.c?Yes! Make sure your helper functions are declared static, and that you document what the functions and structuresyou add are for.Can I use functions from ?Yes. It’s much, much harder if you don’t.Will I need to check my code with valgrind?We’ll certainly be checking your submission with valgrind for memory leaks.Can TB ever be NULL?It can be in the case something goes wrong but in any case you have a TB which is NULL the correct course of actionwould be to print a suitable error message and abort().Can I use the math.h library?Yes.Will the time complexity of bonus functions affect the bonus marks?No.newTBHow does newTB work?If the input text is, for example, “Hi there,\nhow\nare\nthings\n”, the textbuffer should contain the following lines:{ “Hi there,”, “how”, “are”, “things” }. You will have to process the input text, extract all the substringsseparated by newlines, and copy them into your textbuffer structure.Should I leave the ‘\n’ characters in?Depending on your approach to splitting text, they may already be gone. The only other place you need the ‘\n’characters is in dumpTB, so you could probably get away without storing them. But it is up to you.Is it safe to assume that the input text will always have a newline at the end?Unless text is the empty string, it will always have a newline at the end.What should happen with multiple consecutive newlines?Every newline marks a new line in the textbuffer, so a newline that immediately follows another newline (or a newline atthe beginning of the input text) would represent an empty line. You need to track empty lines.Can I assume a maximum length for lines?No. Your program should be able to dynamically allocate any memory needed for your strings depending on the inputtext.What if the input text is a empty string?Create an empty TB.What if the input text consists of just a single newline character?Create a TB with one empty line.What if the input text is NULL?We won’t be testing this (as NULL is not a valid string), but in this case a sensible thing to do would be to print a suitableerror message and abort().releaseTBHow can I test releaseTB?You can’t. You can’t write a black-box test for a destructor.When you free() memory, what you’re saying is that you no longer need the block of memory you had a pointer to; itshould be irrelevant to you whether that memory’s value changes or becomes invalid in some way, because you areabsolutely forbidden from accessing the memory once free’d. Use-after-free is an illegal and undefined operation.A good test that your releaseTB worked is that your program is still running after you do so.Do note though that valgrind may be useful to help diagnose memory leaks which can indirectly signal a error withyour releaseTB.dumpTBMy textbuffer has no lines; what should dumpTB return?It should return an empty string, regardless of whether showLineNumbers is true or false. Note that this string shouldstill be allocated so that the user can free it.addPrefixTBCan the prefix string have newlines in it?No. We will not test these cases.Can the prefix string be the empty string?Yes. In this case, do nothing.Can the prefix string be NULL?No. In this case, abort().mergeTBWhat should happen if I mergeTB (tb1, 1, tb1)?Attempts to merge a textbuffer with itself should be ignored.Should I call releaseTB as well?No! This will probably destroy both the source and destination textbuffers. However, you’ve moved the contents of thesource textbuffer, so you can just free() as you would in releaseTB. You must not subsequently dereference it; that’sa use-after-free and (say it with me, folks!) use-after-free is illegal.Can I concatenate text buffers with mergeTB?The correct behaviour should be as follows, for mergeTB (dest, pos, src):pos == 1: Insert src before the start of dest.pos == linesTB (dest): Insert src before the last line of dest.pos == linesTB (dest) + 1: Append src to the end of dest.What should happen if tb1 or tb2 are empty?Both may be empty. If dest is empty then the only valid value for pos is 1, which would cause src to be appended tothe end of the empty TB.pasteTBCan a textbuffer be pasted onto itself?Yes! For example, suppose tb was:1 Never gonna give you up2 Never gonna let you downThen after calling pasteTB (tb, 2, tb), tb would look like:1 Never gonna give you up2 Never gonna give you up3 Never gonna let you down4 Never gonna let you downsearchTBCan the search string have newlines in it?No. We will not test these cases.Can the search string be the empty string?Yes. In this case, return an empty list.How should I return an empty list?In general, this depends on the representation of the list. If the list is represented by a structure containing metadata aboutthe list (such as its size, the pointer to the first node, etc.), like in the Week 1 and Week 2 labs, then an empty list isrepresented by a (pointer to a) metadata structure where the size field is set to 0, and the pointers to the first/last nodes areset to NULL. If the list is represented by a pointer to the first node, then an empty list is represented by a NULL pointer, asthere are no nodes in the list. In this assignment, because a list of matches is merely represented by a pointer to the firstmatch node, an empty list is represented by NULL.Can the search string be the NULL?No. In this case, abort().Can the search string occur multiple times on the same line?Yes. In this case, the returned list of matches should have a node for each of the occurrences on that line. For example, ifsearchTB (tb, “bird”) is called, and tb is:1 A well a everybody’s heard about the bird2 B-b-b bird, bird, bird, b-bird’s the word3 A well a bird, bird, bird, the bird is the word4 A well a bird, bird, bird, well the bird is the word5 A well a bird, bird, bird, b-bird’s the wordThe returned list should be:(1, 38) –> (2, 7) –> (2, 13) –> (2, 19) –> (2, 27) –> (3, 10) –> (3, 16) –> …How do you handle the case where the search string is a repeated pattern (e.g., looking for ‘abab’ in ‘ababab’)?The matches you return should not overlap. After you find a match on a line, the search should resume from after thepart of the line that was matched. For example, if we searched for “abracadabra” in the string”abracadabracadabracadabracadabra”, the matches are “abracadabracadabracadabracadabra”. So if wesearched for “abracadabra” in this textbuffer:1 abracadabra alacazam2 abracadabracadabracadabracadabraThe returned list should be:(1, 1) –> (2, 1) –> (2, 15) –> XformRichTextHow should I handle cases where there are no characters between a pair of special characters (such as **)?In this case, nothing should happen. Only add the tags if there is at least 1 character being acted on.Can substitutions occur across lines?No.diffTBDoes diffTB change either of its textbuffer arguments?No. diffTB is non-destructive.How will diffTB be tested?There are many possible valid sequences of commands that could be returned from diffTB, so comparing the outputagainst an expected output would not work. Instead, we will parse your edit solution and apply the commands one byone to tb1. After applying the commands, we will call dumpTB on tb1 and tb2. If they return the same string, and youredit so
lution consists of fewer commands than the threshold, then you pass the test.Could we get an example?Certainly!Suppose that these are tb1 (left) and tb2 (right):1 first line 1 first line2 second line 2 2nd line3 third line 3 third line4 fourth line 4 quatreHere are some examples of correct command strings (there are others):”+,2,2nd line\n-,3\n+,4,quatre\n-,5\n””-,2\n+,2,2nd line\n-,4\n+,4,quatre\n””-,2\n-,3\n+,2,2nd line\n+,4,quatre\n””-,4\n-,2\n+,3,quatre\n+,2,2nd line\n”undoTB and redoTBMy implementation of undoTB and redoTB requires me to modify existing functions (e.g., mergeTB), which affects their timecomplexities. Will I be penalised for having a slow time complexity for these functions?Your implementation of the applicable functions will probably be split into two parts: (1) one part that allows undoTBand redoTB to work, and (2) a second part that actually does the main work of the function. In checking your functions’time complexities we will only consider the second part of the code.Should I record an operation that has no effect on the TB, such as merging an empty textbuffer?It’s up to you – we won’t be testing these cases.What should happen if I undo a merge? Is tb2 alive again?If you called mergeTB (dest, pos, src), src no longer exists, so calling undoTB (src) is invalid. Calling undoTB(dest) should simply remove the merged lines from dest (of course, they may reappear again if redoTB (dest) iscalled).What should happen if I undo a cut?If you called cutTB (tb1, from, to), the returned TB (let’s call it tb2) is completely independent of tb1. CallingundoTB (tb1) should restore the lines that were cut from tb1, but have no effect on tb2.What should happen if I undo a paste?If you called pasteTB (tb1, pos, tb2), the paste operation is performed on tb1, not tb2, so tb2 has no record of theoperation taking place. Thus, calling undoTB (tb1) should remove the pasted lines from tb1 (they may reappear ifredoTB (tb1) is called), while calling undoTB (tb2) should do nothing unless some operation was performed on tb2before the paste.PlagiarismThis is an individual assignment. Each student will have to develop their own solution without help from other people. Inparticular, it is not permitted to exchange code or pseudocode. You are not allowed to use code developed by persons otherthan yourself. If you have questions about the assignment, ask your tutor.Plagiarism is defined as using the words or ideas of others and presenting them as your own. UNSW and CSE treat plagiarismas academic misconduct, which means that it carries penalties as severe as being excluded from further study at UNSW. Thereare several on-line sources to help you understand what plagiarism is and how it is dealt with at UNSW:Plagiarism and Academic IntegrityUNSW Plagiarism ProcedureMake sure that you read and understand these. Ignorance is not accepted as an excuse for plagiarism. In particular, you are alsoresponsible that your assignment files are not accessible by anyone but you by setting the correct permissions in your CSEdirectory and code repository, if using. Note also that plagiarism includes paying or asking another person to do a piece ofwork for you and then submitting it as your own work.UNSW has an ongoing commitment to fostering a culture of learning informed by academic integrity. All UNSW staff andstudents have a responsibility to adhere to this principle of academic integrity. Plagiarism undermines academic integrity and isnot tolerated at UNSW. Plagiarism at UNSW is defined as using the words or ideas of others and passing them off as yourown.If you haven’t done so yet, please take the time to read the full text ofUNSW’s policy regarding academic honesty and plagiarismThe pages below describe the policies and procedures in more detail:Student Code PolicyStudent Misconduct ProcedurePlagiarism Policy StatementPlagiarism ProcedureYou should also read the following page which describes your rights and responsibilities in the CSE context:Essential Advice for CSE Students