CSCI 2041 Assignment 3: Multi-List Manager

Download the code pack linked at the top of the page. Unzip this which will create a project folder. Create new files in this folder. Ultimately you will re-zip this folder to submit it.

NOTE: Tests Released Later: The tests for this assignment will not be released with the publication of the specification. They will be released sometime after once they have been completed. Further instructions on how to use them will be made available on release.

multimanager is demonstrated below. Study this demo session to gain an understanding of the direction of the program.

> make                                                 # compile
ocamlc -g -annot -c util.ml
ocamlc -g -annot -c sortedlist.ml
ocamlc -g -annot -c document.ml
ocamlc -g -annot -c doccol.ml
ocamlc -g -annot -c bulkops.ml
ocamlc -g -annot -c multimanager.ml
ocamlc -g -annot -o multimanager str.cma unix.cma util.cmo sortedlist.cmo document.cmo doccol.cmo bulkops.cmo multimanager.cmo

> ./multimanager                                       # run

(default.txt)> help                                    # show help
MULTI MANAGER
Maintains multiple sorted lists of unique elements..

--PROGRAM COMMANDS--:
  help           : print this help message
  quit           : quit the program

--CURRENT LIST COMMANDS--
The following commands modify the current list
  show           : print the current list to the screen
  clear          : set the list to empty, preserves undo history
  add <elem>     : add elem to the list
  remove <elem>  : remove elem from list
  mergein <file> : load the sorted list in the named file and merge with current list (undoable)
  save           : save the current list using the name of the list as the save file
  saveas <file>  : save the current list to the given file name; keeps the list name the same
  undo           : undo the last operation restoring list to a previous state
  redo           : redo the last undone operation restoring list to a previous state

--LIST MANAGEMENT COMMANDS--
The following commands will fail if a list name is already in use (new/open) or no present (close/edit/merge)
  lists          : prints the lists that are currently open
  edit <list>    : set the named list to the current list
  new <list>     : create a new empty list and switch to it
  open <file>    : create a new list named after the file specified; load the contents of the file into it and switch to it
  close <list>   : close the list with given name and remove it from the open documents; cannot close the current list
  merge <list>   : merge the named list contents into the current list

--BULK OPERATIONS--
The following commands act upon all open lists
  showall        : print all lists labelled with their list name
  saveall        : save all open lists; use filenames identical the list names (not undoable)
  addall <elem>  : add elem to all open lists; each list can undo this individually
  mergeall       : merge the contents of all lists into the current list; undoable

(default.txt)> add Korra                               # add some elements to default.txt
(default.txt)> add Bolin
(default.txt)> add Mako
(default.txt)> show                                    # show current list
--BEG LIST--
Bolin
Korra
Mako
--END LIST--

(default.txt)> new others.txt                          # create a new list others.txt and switch to it
(others.txt)> show                                     # others.txt is empty
--BEG LIST--
--END LIST--

(others.txt)> add Tenzin                               # add some element to it
(others.txt)> add Pema
(others.txt)> show                                     # show
--BEG LIST--
Pema
Tenzin
--END LIST--

(others.txt)> lists                                    # show the open lists
2 docs
- others.txt
- default.txt

(others.txt)> edit default.txt                         # switch back to default.txt
(default.txt)> show
--BEG LIST--
Bolin
Korra
Mako
--END LIST--

(default.txt)> undo                                    # undo history is retain independently for each list
(default.txt)> show
--BEG LIST--
Bolin
Korra
--END LIST--

(default.txt)> add Asami
(default.txt)> redo                                    # last op was an add so no redo history
WARNING: redo list empty, no changes made
(default.txt)> show
--BEG LIST--
Asami
Bolin
Korra
--END LIST--

(default.txt)> new vils.txt                            # make new list vils.txt and switch to it
(vils.txt)> add Unalaq
(vils.txt)> add Kuvira
(vils.txt)> show
--BEG LIST--
Kuvira
Unalaq
--END LIST--

(vils.txt)> close vils.txt                             # cannot close the current list
ERROR: cannot close the current list

(vils.txt)> edit others.txt                            # switch back to others.txt
(others.txt)> show
--BEG LIST--
Pema
Tenzin
--END LIST--

(others.txt)> save                                     # save list to file after its name "others.txt"

(others.txt)> new tmp                                  # make a new list called tmp
(tmp)> load others.txt                                 # load file into tmp
(tmp)> show                                            # show contents that were saved from another list
--BEG LIST--
Pema
Tenzin
--END LIST--

(tmp)> edit default.txt                                # switch to list default.txt

(default.txt)> close tmp                               # close list tmp discarding it

(default.txt)> edit tmp                                # cannot edit this as it was just closed
ERROR: list 'tmp' does not exist

(default.txt)> lists                                   # show open lists
3 docs
- vils.txt
- others.txt
- default.txt

(default.txt)> showall                                 # show all contents of all lists
--List vils.txt--
Kuvira
Unalaq

--List others.txt--
Pema
Tenzin

--List default.txt--
Asami
Bolin
Korra

(default.txt)> merge others.txt                        # merge list others.txt into current list default.tt

(default.txt)> show                                    # now has contents of other list
--BEG LIST--
Asami
Bolin
Korra
Pema
Tenzin
--END LIST--

(default.txt)> undo                                    # merge can be undone
(default.txt)> show
--BEG LIST--
Asami
Bolin
Korra
--END LIST--

(default.txt)> redo                                    # redo the merge
(default.txt)> show
--BEG LIST--
Asami
Bolin
Korra
Pema
Tenzin
--END LIST--

(default.txt)> saveall                                 # save all open files to their associated file names

(default.txt)> lists                                   # show open lists
3 docs
- vils.txt
- others.txt
- default.txt

(default.txt)> new tmp                                 # make a new tmp list
(tmp)> load vils.txt                                   # load contents of file vils.txt

(tmp)> show                                            # was saved as part of earlier saveall
--BEG LIST--
Kuvira
Unalaq
--END LIST--

(tmp)> edit default.txt                                # switch to default.txt
(default.txt)> close tmp                               # close tmp lsit

(default.txt)> open test-data/heros.txt                # open file create a list named after it

(test-data/heros.txt)> show
--BEG LIST--
Asami
Bolin
Bumi
Jinora
Korra
Kya
Mako
Tenzin
--END LIST--

(test-data/heros.txt)> undo                            # initially opened files have no undo history
WARNING: undo list empty, no changes made

(test-data/heros.txt)> lists                           # show open lists
4 docs
- test-data/heros.txt
- vils.txt
- others.txt
- default.txt

(test-data/heros.txt)> showall                         # show all data in all lists, some is redundant
--List test-data/heros.txt--
Asami
Bolin
Bumi
Jinora
Korra
Kya
Mako
Tenzin

--List vils.txt--
Kuvira
Unalaq

--List others.txt--
Pema
Tenzin

--List default.txt--
Asami
Bolin
Korra
Pema
Tenzin

(test-data/heros.txt)> addall Meelo                    # add Meelo to all lists

(test-data/heros.txt)> showall                         # show addition succeeded
--List test-data/heros.txt--
Asami
Bolin
Bumi
Jinora
Korra
Kya
Mako
Meelo                                                  # Meelo added
Tenzin

--List vils.txt--
Kuvira
Meelo                                                  # Meelo added
Unalaq

--List others.txt--
Meelo                                                  # Meelo added
Pema
Tenzin

--List default.txt--
Asami
Bolin
Korra
Meelo                                                  # Meelo added
Pema
Tenzin

(test-data/heros.txt)> new everyone                    # make a new empty list
(everyone)> show
--BEG LIST--
--END LIST--

(everyone)> mergeall                                   # merge all lists into the current list
(everyone)> show                                       # show resulting merged list, no duplicates
--BEG LIST--
Asami
Bolin
Bumi
Jinora
Korra
Kuvira
Kya
Mako
Meelo
Pema
Tenzin
Unalaq
--END LIST--
(everyone)> quit                                       # exit the program

Lists multi-managed!

Create a source file document.ml which will have the following bindings in it.

(* document.ml: Defines a "document" type which tracks a current state
   along with undo/redo history.  The document type is polymorphic
   meaning data can be any type such as 'int document' or 'string list
   document'. *)

(* document type declaration. *)
type 'a document = {
    mutable current    : 'a ;       (* current document state *)
    mutable undo_stack : 'a list;   (* past states that can be reached via undo *)
    mutable redo_stack : 'a list;   (* undone states that can be reached via redo *)
};;

let make initial = ... ;;
(* val make : 'a -> 'a document
   Create a new document with initial as the current state and empty
   undo/redo stacks. *)

let set document data = ... ;;
(* val set : 'a document -> 'a -> unit
   Set the document to the given data. Push current state into the
   undo stack. Empty the redo stack *)

let undo document = ... ;;
(* val undo : 'a document -> bool
   If the undo_stack is not empty, undo the last operation. current
   is moved to the redo_stack and the top element of undo_stack is
   removed and becomes current.  Returns true if changes are made
   and false if undo_stack is empty and no changes are made. Operates
   in constant time. *)

let redo document = ... ;;
(* val redo : 'a document -> bool
   If the redo_stack is not empty, redo the last operation. current
   is moved to the undo_stack and the top element of redo_stack is
   removed and becomes current.  Returns true if changes are made
   and false if redo_stack is empty and no changes are made. Operates
   in constant time. *)

• These functions are close in functionality to those of undolist.ml from the prior assignment with the major change being that they each operate on a parameter document rather than global variables.
• Make use of the dot notation to access fields of the record such as in document.current and document.undo_stack

• Since document fields are all declared mutable, they may be re-assigned to new values using the left-arrow syntax as in

  document.current <- something new;
  
  

• Otherwise, the semantics of set/undo/redo are identical to the previous assignment and should be familiar. If not, refer back to this section on their implementation

The following criteria will be checked in this problem.

Create a source file doccol.ml which will have the following bindings in it.

(* doccol.ml: Type and functions for a collection of named documents.
   Tracks a current document and its name along with an association
   list of all docs in the collection.  Preserves uniqueness of names
   in the collection. Makes use of built-in List functions to
   ad/remove/get docs from the association list. *)

(* Type to track a collection of named documents in an association
   list. *)
type 'a doccol = {
  mutable count   : int;                                  (* count of docs in list *)
  mutable curdoc  : 'a Document.document;                 (* current list being edited *)
  mutable curname : string;                               (* name of current list *)
  mutable docs    : (string * 'a Document.document) list; (* association list of names/docs *)
};;

let make name doc = ... ;;
(* val make : string -> 'a Document.document -> 'a doccol
   Create a doccol. The parameters name and doc become the current
   doc and the only pair in the docs association list. *)

let add doccol name doc = ... ;;
(* val add : 'a doccol -> string -> 'a Document.document -> bool
   If there is already a doc with name in doccol, do nothing and
   return false.  Otherwise, add the given doc to doccol with the
   given name, update the count of docs and return true. Uses
   association list functions from the List module. *)

let remove doccol name = ... ;;
(* val remove : 'a doccol -> string -> bool
   If name is equal to curname for the doccol, do nothing and return
   false.  If there is no doc with name in doccol, do nothing and
   return false.  Otherwise, remove the named doc from doccol,
   decrement the count of docs, and return true. Uses association list
   functions from the List module. *)

let has doccol name = ... ;;
(* val has : 'a doccol -> string -> bool
   Returns true if the named doc is in the doccol and false otherwise. *)

let switch doccol name = ... ;;
(* val switch : 'a doccol -> string -> bool
   Change the current document/name to the named document and return
   true. If the named document does not exist, return false and make
   no changes to doccol. *)

let string_of_doccol doccol = ... ;;
(* val string_of_col : 'a doccol -> string
   Creates a string representation of doccol showing the count of
   docs and the names of all docs. Each doc is listed on its own
   line. It has the following format:

   4 docs
   - test-dir/heros.txt
   - places.txt
   - stuff.txt
   - default.txt

   Does not define any helper functions. Makes use of higher order
   functions such as List.map and/or List.fold. May also use string 
   processing functions such asString.concat and/or Printf.sprintf *)

• Make use of functions that exist in the List module, notable assoc_opt will be useful in several situations.
• Since assoc_opt will return option's, you will need to utilize pattern matching in many of the doccol functions.
• Do Not make use of any exception handling. Use this as an opportunity to gain some familiarity with options
• Notice that add ensures that document names remain unique. This means searching the collection for a name to ensure it does not already exist. If not, add it and return true to indicate success. If not, make no change and return false.
• Similarly, removing a document that does not exist in the collection does not change anything about the collection and returns false to indicate no change was made.
• The final function string_of_docs should employ a higher-order List function such as map / fold / iter to produce the resulting string with little code effort.
• String.concat and Printf.sprintf are also useful for this function in conjunction with higher-order list functions. Review descriptions associated with these in the OCaml Standard library documentation if they are unfamiliar.

The following criteria will be checked in this problem.

Create a source file bulkops.ml which will have the following bindings in it.

(* bulkops.ml: Implement bulk operations on Doccol's of string list
   Documents that are useful for multimanager.  Since the functions in
   this module require access to fields and types of other modules, start
   the file by opening those two modules:

   open Document;; 
   open Doccol;; 
*)

let showall doccol = ... ;;
(* val showall : string list Doccol.doccol -> unit
   Prints all documents in doccol to the screen. For each list,
   prints the list name first and then each element of the list using
   Sortedlist functions. Uses higher-order functions to iterate over
   the doclist. 

   EXAMPLE:
   --List test-data/heros.txt--
   Asami
   Bolin
   Bumi
   Jinora
   Korra
   Kya
   Mako
   Tenzin
   
   --List test-data/villains.txt--
   Amon
   Hiroshi
   Kuvira
   Ming-Hua
   P-li
   Unalaq
   Zaheer
   
   --List default.txt--
   Korra
   Meelo
   Pema
*)

let saveall doccol = ... ;;
(* val saveall : string list Doccol.doccol -> unit
   Saves all documents in doccol. Makes use of Util functions to do
   I/O. Makes use of higher-order functions to write each list to
   associated file name. *)

let addall doccol elem = ... ;;
(* val addall : 'a list Doccol.doccol -> 'a -> unit
   Adds the given element to all docs in doccol. Makes use of
   higher-order functions and Sortedlist functions to modify each
   list. Each doc/list can individually undo the addition. *)

let mergeall doccol = ... ;;
(* val mergeall : 'a list Doccol.doccol -> 'a list
   Merges all lists in doccol.docs into a single list and returns
   it. Uses higher-order functions and Sortedlist functions to perform
   the merge. *)

• Each of these functions takes a doccol as an argument and works with the field doccol.docs which is an association list.
• As suggested above all of these functions define helper functions and then make use of higher-order List functions to apply them to all doccol.docs elements
• Make sure each helper is nested within the scope of the relevant function: no new module-level bindings should be introduced

• Helper functions will be applied to the elements of association list doccol.docs which is comprised of name/doc pairs. It is therefore helpful to define helpers as taking a pair argument with named parts such as

    let master_func doccol =
      let helper (name,doc) =
        ...   (* use name and doc *)
      in
      ... 
    ;;
  

• Helper functions are not required to be named and can instead be anonymous using the fun syntax though this is optional.
• Make use of an appropriate higher-order functions from List to apply the helper function to all elements of the association list. Consider the following when selecting an appropriate higher-order function.
  • Changes to each element that result in unit are often associated with List.iter
  • Extracting some elements from the list is often associated with List.filter. The resulting list will likely be shorter but have the same type of elements.
  • Mapping a function to all elements in the list to produce a new list the business of List.map. The resulting list will have the same length as the input list but may have a different type of element.
  • Creating a new result that combines all elements of a list is usually done with List.fold_left or List.fold_right.

The following criteria will be checked in this problem.

The source file multimanager.ml is provided and has the following structure. Edit the execute_command function so that it implements the indicated commands.

(* multimanager.ml : main function to allow manipulation of multiple
   lists of sorted, unique elements.  *)

let help_string = ... ;;
(* Help string to be printed for the "help" command. *)

let global : string list Doccol.doccol = ... ;;
(* Tracks the global state associated with the application. This
   binding uses a series of statements to initialize the global state
   to have a default empty list named 'default.txt' which is the
   current document and the only entry in the doccol. *)

let quit_now = ... ;;
(* Set to true to end execution of the program *)

let execute_command tokens = ... ;;
(* val execute_command : string array -> unit
   Execute a single command which is the 0th element of the argument
   array tokens.  If the command has additional parameters these will
   be in tokens.(1), tokens.(2), etc.  Makes use of functions in Util,
   Sortedlist, Document, doccol, and Bulkops to implement each
   command. *)

let echo  = ... ;;
(*********************************************************************************
   Code beyond this point should not require modification though it
   may be interesting to examine. 
*)

let debug = ... ;;


let options = ... ;;
(* Options accepted by the program *)

let handle_extra_args arg = ... ;;
(* Do nothing with extra command line arguments *)

let usage = ... ;;
(* Simple usage message for Arg.parse *)

let _ = ... ;;
(* main routine *)

• DO NOT MODIFY THE ORDER of commands in execute_command. Graders will expect code to appear in the order given and altering this will irritate them. Whenever possible, avoid irritating graders.
• Do not open any modules other than Printf which is already done. Instead, refer to functions in various source files via the module syntax discussed in the last assignment.
• The below subsections give some details associated with the major types of commands and how they should be implemented.

• You may wish to consult your solution for listmanager.ml for the CURRENT LIST COMMANDS but note that you will need to make some substantial changes due to move from a single global undo list to use of individual document records with undo/redo.

  The other commands for list management and bulk operations are new enough to need from-scratch implementation.

• Keep the access pattern to the Current List in mind
  • global.curdoc is a string list document which means functions from Document such as set and undo are applicable to it.
  • global.curdoc.current is a string list so functions from Sortedlist such as insert are applicable to it.
• Inspect the provided show and clear commands as examples of how this works. These are similar to equivalents in listmanager but work with the individual global.curdoc rather than the a global undo list.
• Note the slight change in the save command: it no longer takes a file argument but uses global.curname as the file to save into. Command saveas takes an additional argument in tokens.(1) as the file name to save.

• Each of these commands take a maximum of around 10 lines of code to complete. If you implementation badly exceeds that, rethink your solution path.
• Most commands manipulate global using functions from Doccol such as Doccol.add and Doccol.switch.

• edit <list>: If the names list exists, it becomes the Current List. If not, print a warning message as follows:

  printf "ERROR: list '%s' does not exist\n" name;
  
  

  This command should make use of options and never raise exceptions.

• new <list> and open <file>: Check that the resulting named list is not already part of the Open List Collection. If it is, print an error message as follows

  printf "ERROR: list '%s' already exists\n" name
  
  

  Otherwise, new switches to a new empty list while open <file> reads the file contents as the initial list using Util functions. Both create documents so Document.make should be employed.

• close <list>: remove the named list from the Open List Collection. If <list> is the current list, do not remove anything and print an error message with the via

  printf "ERROR: cannot close the current list\n"
  
  

  If <list> is not in the Open List Collection print the error message

  printf "ERROR: list '%s' does not exist\n" name;
  
  

• There may be a few situations in which one wishes to call switch simply for its side-effect of switching the current document. Make use of the ignore syntax to do so without generating a compiler warning as in

  ignore(Doccol.switch ...);
  
  

  This will cause the returned true/false value to be ignored so the compiler does not complain that the `expression should have type unit'.

• merge <list>: Similar to close, if the names list does not exist print an error message:

  printf "ERROR: list '%s' does not exist\n" name;
  
  

  Otherwise use Sortedist functions to merge the named list into the Current List.

• Each of these commands has very short implementations that draw on functions in Bulkops
• showall / saveall / addall are essentially calls to corresponding Bulkops functions
• mergeall requires that the Current List be changed; after creating the merged list, use Document.set for this so that the operation can be undone.

The following criteria will be checked in this problem.

If creating a zip file is unfamiliar to you, refer to the following guide: Making Zips (tutorial)

Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to Canvas.

On Canvas:

• Click on the Assignments section
• Click on the appropriate link for this lab/assignment
• Scroll down to "Attach a File"
• Click "Browse My Computer"
• Select you Zip file and press OK

You may wish to review the policy on late project submission which will cost you late tokens to submit late or credit if you run out of tokens. No projects will be accepted more than 48 hours after the deadline.

http://www-users.cs.umn.edu/~kauffman/2041/syllabus.html#late-projects