Optimize insertion/deletion of word/meanings

The externalDictionary interaction with the dictionary application must remain intact (i.e. Nothing in the application should have to change because of this extra credit). You may choose to turn in this version of externalDictionary in place of what the assignment #2 requires; however, if you do so, you need to meet the deadline for the assignment itself, and not the extra credit.

The format of each record remains the same except for the addition of one byte that will act as your flag; a 'D' would indicate that a record is deleted.

The word vector should no longer be a vector of words ONLY. Deleted record of our file are not part of the dictionary and should not be in the word vector. Here is what needs to change:

• Write a vectorElement class that stores a word and the position of that word in the file. vectorElement needs to implement Comparable; the compareTo allow vector elements to be compared to each other by only comparing their word fields. The rational for changing what the word vector contents is simple; we want word to only contain words that actually exist in our file, we don't want entries of deleted words in our vector. So, the vector can no longer mirror our file. For example, the 1st entry in it may be a word that would be found in the 10th record of the file as the first 9 are in a deleted state; if the word in that entry is not accompanied with its position in the file, the word vector becomes a useless index.
• word should be populated at construction with words that have not been deleted, accompanied in each case with their position in the file. So, your constructor has to change. More over, you need to sort the word vector using a simple sort technique like selection sort, since the words in the file will no longer be guaranteed to be ordered.
• The process of looking for a word in find or add methods does not change much here. In Each case, you could use some combination of indexOf() and elementAt() methods from the Vector class to find the word in your vector, assuming you construct a dummy vectorElement with just the word in it that you are trying to find or add.
• For add, you should change you algorithm and place a new word/meaning/flag at the end of the file, instead of finding the right location for it. This way, you avoid dealing with deleted records, and changing the position of other words in the file by moving them to make room. Adding to the word vector will need the obvious change; you no longer just put a word into it, you need to build a vectorElement and store it in the appropriate location of the vector.

  Understand that we are not making these changes to save space; we are expecting time improvements in processing deletions and insertions.

• The remove method will no longer have to move records back. The correct record needs to be located, but this time, read; then marked as deleted, and then written back to file. The entry in the word vector for this word will then need to be deleted.
• The Iternator methods need be changed as in this version of externalDictionary records may be deleted and their words should not be processed as part of iteration.

Hand In

externalDictionary.java assuming you keep vectorElement in that file.