// FILE: 93ab3.cpp 
// PURPOSE: Linked list problem fro 1993 AP exam
//---------------------------------------------------------------
// COMPILATION INSTRUCTIONS: g++ and gxx 
// COMMAND LINE: 
//    g++ (or gxx) 93ab3.cpp 
//----------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// Read question  below and complete AddStudent() accordingly
/*-----------------------------------------------------------
This problem concerns linked lists of integers defined as follows.

struct NodeType {
  int Info;
  NodeType *Next;
};


A. Write a function ListSum whose header is given below. The function 
   ListSum has one NodeType * parameter L. ListSum returns a new linked 
   list with _one_ node whose Info field contains the sum of the values 
   in L. By definition, the sum of the values of the empty list is 0.

EXPECTED OUTPUT:

Testing ListSum(list) with list:
list--> [2]--> [-3]--> [9]--> [3]--> NULL

ListSum(list)->Info = 11
-------------------------------------------------------------*/
/*
B. Consider a linked list, each of whose elements is a linked list of 
   integers. Such lists are implemented using the following definition.

    struct LLNodeType {
      NodeType *Ptr;
      LLNodeType *Next;
    };
   
   Write a function ListOfListSums whose header is given below. 
   ListOfSums has one parameter M of type LLNodeType *. If M is NULL, 
   ListOfListSums returns NULL; otherwise ListOfListSums returns a new 
   linked list of integers with the property that the value stored in 
   the kth node of the new list is sum of the integers in the kth 
   element of M.

EXAMPLE:

M--> [][]--> [][]--> [][]--> [][]--> [][\] 
      |       |       |       |       |  
      5       9      10      NULL    -3
      |       |       |               |
      6      NULL    NULL            NULL
      |
     -2
      |
     NULL   
       
EXPECTED OUTPUT:

Printing list from p = ListOfLists(M):

p--> [9]--> [9]--> [10]--> [0]--> [-3]--> NULL
-----------------------------------------------------------------*/   
#include <iomanip.h>
#include <stdlib.h>
#include <string>


struct NodeType {
  int Info;
  NodeType *Next;
};


struct LLNodeType {
  NodeType *Ptr;
  LLNodeType *Next;
};

//******************************
//        PART A
//******************************
NodeType *ListSum(NodeType *L) {
  return NULL;
}//*** ListSum



//******************************
//        PART B
//******************************
NodeType *ListOfListSums(LLNodeType *M) {
    return NULL;
} //***ListOfListSums


void ListSumDriver(void);
void ListOfListsSumDriver(void);
void print(NodeType *L);
void cls();
void pause();

int main() {
  cls();
  string title("1993 AB Exam: question 3");
  cout << setw(39 - title.length()/2) << "" << title << "\n\n";

  ListSumDriver();
  ListOfListsSumDriver();
  pause();
  return 0;
}//-------------------------- main -------------------------



void ListSumDriver(void) {
  int data[] = {2, -3, 9, 3}, n = sizeof(data)/sizeof(int);
  NodeType *p, *q, *list;
  // 1. -----------------  build list (2,-3,9,3)
  p = list = q = new NodeType;
  for (int k = 0; k < n - 1; k++) {
    p->Info = data[k]; 
    p = new NodeType;
    q->Next = p;
    q = p;
  }
  p->Info = data[n-1]; p->Next = NULL;
  cout << "Testing ListSum(list) with list:\n" << "list--> ";
  print(list); cout << endl;
  NodeType *lst = ListSum(list);
  if ( lst == NULL ) 
    return;
  cout << "ListSum(list)->Info = " << lst->Info << endl << endl;
} //***** ListSumDriver 


void ListOfListsSumDriver(void) {
  LLNodeType *LL = new LLNodeType, *LL2 = LL;
  NodeType *N = new NodeType;
  LL2->Ptr = N;
  N->Info = 5; N->Next = new NodeType;
  N = N->Next; N->Info = 6; N->Next = new NodeType;
  N = N->Next; N->Info = -2; N->Next = NULL;
 
  LL2->Next = new LLNodeType; LL2 = LL2->Next;
  N = new NodeType;  LL2->Ptr = N;
  N->Info = 9; N->Next = NULL;

  LL2->Next = new LLNodeType; LL2 = LL2->Next;
  N = new NodeType;  LL2->Ptr = N;
  N->Info = 10; N->Next = new NodeType;
  N = N->Next; N->Info = 0; N->Next = NULL;

  LL2->Next = new LLNodeType; LL2 = LL2->Next;
  LL2->Ptr = NULL;

  LL2->Next = new LLNodeType; LL2 = LL2->Next;
  N = new NodeType;  LL2->Ptr = N;
  N->Info = -3; N->Next = NULL;
  LL2->Next = NULL;

  NodeType *p = ListOfListSums(LL);
  cout << "Printing list from p = ListOfLists(LL):\n";
  cout << "p--> ";
  print(p);
  cout << endl;
}//***** ListOfListsSumDriver


void print(NodeType *p) {
  for (; p != NULL; p = p->Next ) {
    cout << "[" << p->Info << "]--> ";
  }
  cout << "NULL\n";
}

void cls(void) {
  for (int k = 0; k < 55; k++)
    cout << endl;
}

void pause(void) {
  cout << "\nPress <ENTER>...";
  cin.ignore(80, '\n');
}