Show Source | | About « 0.2. Data Structures and Algorithm Analysis Introduction :: Contents :: 0.4. Math Background »
Be aware of project due date, milestone due datesAim to get it done PRIOR to the EARLY BONUS date.You need to write a “scanner” or “parser” to read info from command file (text).You need to use command line parametersSee Tutorials in Chapter 2 of OpenDSAFor parsing: Use Scanner Class [2.7] or Pattern/Matcher classes
Q: When do you need separate classes?Wrong A: When they get too longRight A: When they separate meaningfully different behaviorThings you need in this projectMultiple data structures (hash table class, memory manager class)“Main” routine, that sets things upCommand syntactic parsing (separate the behavior, NOT the code length)Command semantic processing (separate the behavior, NOT the code length)
Bad:Main Class (Scanner/interpreter) ==> Main Data StructuresGood:Main (Program parameters, initialization) ==>Parser (Syntactic processing of commands) ==>“Database” or “World” (semantic processing of commands) ==>Various data structures classes
Most people find these projects to be hard and/or time consumingNeed some planning structureMilestones help to enforce time managementIncremental Development is crucial to successScheduling the project:1. Main/Parser first.2. World Database class next.3. Hash table, implemented with direct access to strings in memory (hidden behind record interface)4. Memory manager last!
You are usually banned from using standard Java data structures classesYou may not use things likeHashMap,ListArray,VectorException: You may useListArrayto thelp you with processing the keywords in the parser.You may use standard language features like arraysYou may use string and file manipulation classes/methods that make parsing of the command file easy.
Good names matter. REALLY!Every competent software development organization enforces some coding style.Web-CAT enforces a particular coding style.Generalize your container classes (hash table, memory manager)For P1, your memory manager should not know anything about the rest of the project, it just stored bytesSee the Seminar class serializer/deserializer
The hash table is a container class. A container class is anything that stores a collection of arbitrary objects.Want to support any record type. (OK to assume an integer key.)Hide details behind some Record classNeed to deal with concept of comparison. Your record should give you back the string as its key.
Read Module 10.1, Skim 10.3, Read 10.6 carefully, Read 10.7.4 Double Hashing, Read 10.9 Deletion
Feel free to use code posted as part of OpenDSA modules (Insert, search)
You can write Hash Table Class assuming that it uses the given hash function, and that the key is an integer.
World/DB class, Hash Table, Memory Manager need appropriate coordination.
World probably initializes memory manager, and calls memory manager to insert/process records. Store resulting Handle in a Record to pass to hash table.
Hash table does not need to know that there is a Memory Manager, or Seminar records.
Record class and Handle class can hide most implementation details.
Clearly there has to be a key, and there has to be a value (a record?)
The key is an integer (ID value for the Seminar, but the hash table class doesn’t know that)
- The “value” might be dealt with in different ways.
Definitely NOT the byte array (this is in memory manager)
Maybe the handle for the record? That means that the hash table needs to know about handles.
- Can hide handles behind a Record class.
What is key? Store integer? Get from Record? Space vs. Time tradeoff, either is reasonable
Must pass some number of tests, some mutant coverage (from your JUnit tests), some style points
Functionally: Get the hash table working, at least inserts.
Contact Us || Privacy | | License « 0.2. Data Structures and Algorithm Analysis Introduction :: Contents :: 0.4. Math Background »
