.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer

.. slideconf::
   :autoslides: False

================
Project 4 Design
================

Project 4 Design
----------------

.. slide:: Project 4

   | Be aware of project due date, milestone due dates
   | Aim 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 parameters
   |   See Tutorials in Chapter 2 of OpenDSA
   |   For parsing: Use Scanner Class [2.7] or
       Pattern/Matcher classes

       
.. slide:: Project 1 Class Organization (1)

   | Q: When do you need separate classes?
   |   Wrong A: When they get too long
   |   Right A: When they separate meaningfully different behavior
   | Things you need in this project
   |   Multiple data structures (hash table class, memory manager class)
   |   "Main" routine, that sets things up
   |   Command syntactic parsing (separate the behavior, NOT the code length)
   |   Command semantic processing (separate the behavior, NOT the code length)
           
.. slide:: Project 1 Class Organization (2)

   | Bad:
   |   Main Class (Scanner/interpreter)  ==> Main Data Structures           
   | Good:
   |   Main (Program parameters, initialization) ==>
   |     Parser (Syntactic processing of commands) ==>
   |       "Database" or "World" (semantic processing of commands) ==> 
   |         Various data structures classes
           
.. slide:: Scheduling the project

   | Most people find these projects to be hard and/or time consuming
   |   Need some planning structure
   |   Milestones help to enforce time management
   |   Incremental Development is crucial to success
   | Scheduling 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!
         

.. slide:: General Project Info              

   | You are usually banned from using standard Java data structures
     classes
   |   You may **not** use things like ``HashMap``, ``ListArray``, ``Vector``
   |     Exception: You may use ``ListArray`` to thelp you with
         processing the keywords in the parser.
   |   You may use standard language features like arrays
   |   You may use string and file manipulation classes/methods that
       make parsing of the command file easy.          

.. slide:: Good Design Practice

   | 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 P4, your memory manager should not know anything about the
       rest of the project, it just stores bytes
   |   See the Seminar class serializer/deserializer

   
.. slide:: Container Classes: Hash Table

   | 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 class
   | Need to deal with concept of comparison. Your record should give
     you back the string as its key.

Project 4 Hashing
-----------------

.. slide:: What you need to know about Hashing

   * 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)

   * Feel free to reuse code from P1

   * You can write Hash Table Class **assuming** that it uses the
     given hash function, and that the key is an integer.


.. slide:: Quadratic Probing

   .. inlineav:: collisionCON5 ss
      :long_name: Quadratic Probing Slideshow
      :links: AV/Hashing/collisionCON.css
      :scripts: AV/Hashing/collisionCON5.js
      :output: show

   .. inlineav:: collisionCON6 ss
      :long_name: Quadratic Probing Problem
      :links: AV/Hashing/collisionCON.css
      :scripts: AV/Hashing/collisionCON6.js
      :output: show


.. slide:: Primary design issue: Communications

   * World/DB/Controller class, Hash Table, Memory Manager need appropriate
     coordination.
   
   * World/DB/Controller probably initializes Memory Manager and Hash Tables,
     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.

     
.. slide:: What is stored in the hash table?

   * 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


.. slide:: Milestone 1

   * 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


.. slide:: Milestone 2

   * Must pass some number of tests, some mutant coverage (from your
     JUnit tests), some style points

   * Functionally: Get the hash table fully working and begin
     memory manager