I. tools for implementation (HR 5, 7-9)
------------------------------
       DATA STRUCTURES

   TOOLS FOR IMPLEMENTATION

HR 5 Records and Variants
     (C++ structs and unions)

HR 7 Pointers and Dynamic Data

HR 8 Linked Lists

HR 9 Design and Implmentation of ADTs
-------------------------------
---------------------------------
        MAIN QUESTIONS

 - how to model real-world collections
   of information?

 - what algorithms to use with each
   implementation data structure?

 - what implementation data structures
   are suited for implementing
   which structured ADTs?
---------------------------------
II. structs in C++ (HR 5.1-2)
 A. syntax (5.1)
--------------------------
  C++ structs IMPLEMENT RECORDS

struct PhoneRecord {
  char  name[50];
  int   number;
};

struct BookType {
  char  author[50];
  char  title[150];
  int   year;
  float price;
};

enum GenderType {male, female, unknown};

struct EmployeeType {
  char       firstInit;
  char       lastInit;
  int        age;
  GenderType gender;
  float      hourlyWage;
};
--------------------------
 B. client code
--------------------------
  DECLARING struct OBJECTS IN CLIENT CODE

PhoneRecord bank, police, fire;

BookType referenceManual;

EmployeeType manager;
EmployeeType worker1;
EmployeeType dean = {
       'E', 'H', 45, female, 75.0};
--------------------------
--------------------------
 USING struct OBJECTS IN CLIENT CODE

// assignment to data members
worker1.firstInit = 'G';
worker1.lastInit = 'L';
worker1.age = 38;
worker1.gender = male;
worker1.hourlyWage = 30.0;

cout << worker1.age << endl;
if (worker1.age > 65) {
  cout << worker1.firstInit << ". ";
  cout << worker1.lastInit << ". ";
  cout << "should retire";
}
worker1.age = worker1.age + 1;

const float MINIMUM = 4.65;

void payMinimum(EmployeeType & emp)
  // MODIFIES: emp
  // POST: emp.hourlyWage >= MINIMUM
{



}
--------------------------
---------------------------
      FOR YOU TO DO

enum GenderType {male, female, unknown};

struct EmployeeType {
  char       firstInit;
  char       lastInit;
  int        age;
  GenderType gender;
  float      hourlyWage;
};

IMPLEMENT THE FOLLOWING SPECIFICATIONS:

void RaisePay(EmployeeType & emp,
              float rate)
  // PRE: 0.0 < rate && rate <= 1.0;
  // MODIFIES: emp
  // POST: emp.hourlyWage ==
  // (1 + rate) * emp.hourlyWage<entry>



void EqualizePay(EmployeeType & mgr,
              EmployeeType e)
  // MODIFIES: mgr
  // POST: make mgr's hourly wage
  // at least as high as e's pay.
----------------------------
  1. semantics
---------------------------------
     MANIPULATING struct INSTANCES

Can do:
  manager.age
  manager.age = 30;

  manager = worker1;
  // which means:
  manager.firstInit = worker1.firstInit;
  manager.lastInit = worker1.lastInit;
  manager.age = worker1.age;
  manager.gender = worker1.gender;
  manager.hourlyWage = worker1.hourlyWage;
--------------------------------
---------------------------------
Cannot do:
  manager.age()
  manager == worker1
  manager + worker1
---------------------------------
	does this look familiar?
--------------------------------
 A struct IS A class WITH public DEFAULT

struct PhoneRecord {
  char  name[50];
  int   number;
};

// same as

struct PhoneRecord {
public:
  char  name[50];
  int   number;
};

// same as

class PhoneRecord {
public:
  char  name[50];
  int   number;
};
--------------------------------
--------------------------------
    class VS. struct (USAGE)

Use a class when:
	hiding information,
	have abstraction,
	have member functions
	used as ADT

Use a struct when:
	no data is hidden,
	no abstraction,
	no member functions
	 (except maybe constructors)
	used as impl. data structure
--------------------------------
	so if you want to make some data private, which should be used?
----------------------------------
      PARAMETER PASSING

struct PhoneRecord {
  char  name[50];
  int   number;
};

void assign2(PhoneRecord & v1,
             PhoneRecord & v2,
	     PhoneRecord e1,
             PhoneRecord e2)
{
  v1 = e1;
  v2 = e2;
}
--------------------------------
--------------------------------
// InHouse.C

#include "PhoneRecord.h"

PhoneRecord InHouse(
        	const PhoneRecord & pr)
  // PRE: pr.number >= 0;
  // POST: FCTVAL is just like pr
  // but retains only last 5 digits of
  // pr.number
{

  

}
----------------------------------
	How would you use InHouse to print the local phone number of p?
----------------------------------
         SCOPE OF MEMBER NAMES

 - member names are local to a struct
----------------------------------
----------------------------------
struct BookType {
  char  author[50];
  char  title[150];
  int   year;
  float price;
};

struct DateType {
  int year;
  int month;
  int day;
};

DateType independence;
BookType refManual;
int year;

year = 1945;
refManual.year = 1990;
independence.year = 1776;
----------------------------------
 C. combinations (p.209ff)
---------------------------------
   ALL NESTINGS OF TYPES ARE OK!

 - data members can be structs

    student.name.middleInit = 'T';

 - data members can be arrays

    refManual.title[0] = '\0';

 - arrays can contain structs

    employee[2].age = 30;

 - etc.

    students[4].name.first[0] = '\0';
---------------------------------
  1. simple example
----------------------------------
    EXAMPLE OF NESTED DATA STRUCTURES

// StudentType.h

#ifndef StudentType_h
#define StudentType_h 1

typedef char IDNum[10];
const int STRING_CHARS = 20;
typedef char String[STRING_CHARS+1];

enum GenderType {male, female, unknown};
enum ClassType {fresh, soph, junior,
	 senior, grad, special};

struct NameType {
  String first;
  char   middleInit;
  String last;
};

struct StudentType {
  NameType   name;
  ClassType  classific;
  IDNum      socialSecNum;
  GenderType gender;
  float      gradePtAvg;
};
#endif
---------------------------
---------------------------
   HOW DO YOU REFER TO ... ?


// StudentTypeClient.C

#include <string.h>
#include "StudentType.h"

int main()
{
  StudentType student;

  // make the gender be female

  // make the middle initial be Q

  // make the first name be "Jane"


  // make the last name be "Public"

  // make the soc. sec number be 000...0



}
-------------------------------
----------------------------------
        FOR YOU TO DO

// StudentTypeClient.C

#include <string.h>
#include "StudentType.h"

int main()
{
  StudentType student[150];

  for (int i = 0; i < 150; i++) {
    // make the gender be unknown

    // make the middle initial be A

    // the first name be "Jon"

    // make the last name be "Fuddyduddy"

    // make the soc. sec number be 123...9




  }
}
-------------------------------------
  2. problem example (compare HR 5.2-3)
----------------------------------
       PROBLEM

Find index of first record that has
the least name (in alphabetic order)
in an array of StudentType records.
---------------------------------
 D. type equality is by name for structs
------------------------------------
   struct TYPES COMPARED BY NAME

// client code

struct MilesType { float value; };
extern void PointLaser(MilesType height);

int main()
{
  MilesType MtK;
  MtK.value = 7;
  PointLaser(MtK);  // ok?
}

// implementation code

struct KmType { float value; };
void PointLaser(KmType height)
{
  // ...
}
------------------------------------
 E. syntactic variations useful for programming variants
----------------------------------
    SYNTACTIC VARIATIONS (USEFUL LATER)

// declaring struct and instances at once

struct EmployeeType {
  char       firstInit;
  char       lastInit;
  int        age;
  GenderType gender;
  float      hourlyWage;
} manager, worker1;

// declaring instances of unnamed structs

struct {
  int   age;
  float weight;
} thisPerson;
----------------------------------
III. variants (HR 5.4-5)
 A. syntax and examples (5.4)
-----------------------------
    C++ unions IMPLEMENT NOTION OF "OR"

 - holds one of its members
   (not of all of them)

 - space cost for the largest member

union LiteralType {
  char     c;
  long int i;
  double   d;
  char     str[100];
};


enum ArticleType {the, a, an};

union PartOfSpeechType {
  char        noun[30];
  char        verb[30];
  ArticleType article;
};
-----------------------------
 B. client code
------------------
   DECLARING union OBJECTS IN CLIENT CODE

LiteralType lit1;

PartOfSpeechType part1, part2;


// cannot use initializer like:
PartOfSpeechType art = {the};  // error!
-----------------------------
--------------------------------
   USING union OBJECTS IN CLIENT CODE

lit1.i = 7;
lit1.d = 3.14159;

part1.article = a;

for (int i = 0; i < 30; i++) {
  part2.verb[i] = '\0';
}

strcpy(part2.verb, "runs");


if (lit1.d < 4.0) {
  cout << "lit1.d is less than 4" << endl;
}
-----------------------------------
  1. summary
------------------------------
   MANIPULATING union INSTANCES

Can do:
    lit1.i
    lit2.d = 2.73;

    lit1 = lit2;
    // which means:
    lit1.d = lit2.d;
--------------------------------
---------------------------------
Cannot do:
    part1.article()
    part1 == part2
    lit1 + lit2
------------------------------
  2. example
-----------------------------------
	PROBLEM

Implement the following specification

#include "LiteralType.h"

LiteralType ParseLiteral();
  // PRE: the literal on cin doesn't
  // have any escape sequences
  // MODIFIES: cin
  // POST: FCTVAL is a literal from cin
--------------------------------
 C. syntactic variations on union declarations
--------------------------------
     SYNTACTIC VARIATIONS

Unnamed union types:

   union {
     char  input[50000];
     int   output[10000];
   } myCharOrInt;

   myCharOrInt.output[0] = 'a';
--------------------------------
-------------------------------
Anonymous union:

   union {
     int    myInts[10000];
     double myDoubles[1000];
   };

   myInts[3] = 7;
-------------------------------
 D. variant records (5.5)
  1. motivation
------------------------------
     PROBLEM: UNIONS ARE UNSAFE

- C++ prevents:

  struct MilesType { float value; };
  struct KmType { float value; };

  MilesType distance = 5.7;
  KmType  length;

  length = distance;
  cout << "length is " << length;

- C++ allows:

  union MilesOrKm {
    MilesType m;
    KmType    km;
  };

  MilesOrKm distance;
  distance.m.value = 5.7;
  MilesOrKm  length;

  length.m = distance.m;
  cout << "length is "
       << length.km.value << endl;
------------------------------
--------------------------------------
 PROBLEM: EFFICIENT STORAGE OF MIXED TYPES

Suppose want to store 1000
bibliographic citations

  all: author, title, year
  books: publisher, address
  journal: name, volume, number, page


         FIRST ATTEMPT

enum BibTag {book, journal};

struct CitationType {
  char   author[100];
  char   title[100];
  int    year;
  BibTag tag;
  char   publisher[100];
  char   address[100];
  char   name[100];
  int    volume;
  int    number;
  int    page;
};

CitationType ScholarDB[1000];
--------------------------------------
--------------------------------------
            0   1   2   3   4         999
           _____________________     _____
ScholarDB |___|___|___|___|___|_ ... |___|



 author    [B|j|a|...]
 title     [C|+|+...]
 year      [1994]
 tag       [book]
 publisher [A|d|d|...]
 address   [N|e|w|...]
 name      [ | | |...]
 volume    [    ]
 number    [    ]
 page      [    ]

                     author    [G|a|r|...]
                     title     [S|p|e...]
                     year      [1991]
                     tag       [journal]
                     publisher [ | | |...]
                     address   [ | | |...]
                     name      [I|E|E|...]
                     volume    [   8]
                     number    [   4]
                     page      [  72]
--------------------------------------
  2. solution
--------------------------------------
      USE OF VARIANTS TO SAVE SPACE

struct BookInfo {
  char   author[100];
  char   title[100];
  int    year;
  char   publisher[100];
  char   address[100];
};

struct JournalInfo {
  char   author[100];
  char   title[100];
  int    year;
  char   name[100];
  int    volume;
  int    number;
  int    page;
};

enum BibTag {book, journal};

struct CitationType {
  BibTag tag;
  union {
    BookInfo    b;
    JournalInfo j;
  };
};

CitationType ScholarDB[1000];
--------------------------------------
--------------------------------------
            0   1   2   3   4         999
           _____________________     _____
ScholarDB |___|___|___|___|___|_ ... |___|



 tag       [book]
 b|---------------------|
  |author    [B|j|a|...]|
  |title     [C|+|+...]	|
  |year      [1994]	|
  |publisher [A|d|d|...]|
  |address   [N|e|w|...]|
  |---------------------|

                   tag       [journal]
                   j|--------------------|
                    |author   [G|a|r|...]|
                    |title    [S|p|e...] |
                    |year     [1991]	 |
                    |name     [I|E|E|...]|
                    |volume   [   8]	 |
                    |number   [   4]	 |
                    |page     [  72]	 |
		    |--------------------|
--------------------------------------
  3. practice
------------------------------------
       FOR YOU TO DO

What in C++ do you write to:

   1. test what kind of citation
      the ith element of ScholarDB is?


   2. assuming the ith entry is a journal
      set the volume to 51?


   3. assuming the ith entry is a book
      set the publisher to "Books R Us"?

------------------------------------
  4. summary
------------------------------------
       VARIANT RECORDS

def: a *variant record* is implemented
     in C++ using a
      - tag field (also called type field)
      - and one or more anonymous unions

example:

  enum Type {anInt, aFloat};

  struct NumType {
    Type whichType;
    union {
      int    intVal;
      float  floatVal;
    };
  };
------------------------------------
 E. an ADT for variants
-------------------------------------
	PROBLEM

How would you design something in C++
that enforced only accessing the right
field for a given tag?
-------------------------------------