// Lab 7: Append, Middle, Min, and Max
// Note: This program is not OOP
#include <stdlib.h> // Provides size_t
#include <assert.h>
#include <iostream.h>

struct Node
{   typedef double Item;
    Item data;
    Node *link;
};

size_t list_length(Node* head_ptr)
{
    Node *cursor;
    size_t answer;

    answer = 0;
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
        answer++;
    return answer;
}

void list_display(Node* head_ptr)
{
    Node *cursor;
    cout << "( ";
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
       cout << cursor->data << " ";
    cout << "), " << "Size = " << list_length(head_ptr) << endl << endl;
}

void list_head_insert(Node*& head_ptr, const Node::Item& entry)
{
    Node *insert_ptr;

    insert_ptr = new Node;
    insert_ptr->data = entry;
    insert_ptr->link = head_ptr;
    head_ptr = insert_ptr;
}

Node* list_locate(Node* head_ptr, size_t position) // page 222
// Finding a node by its position in a llist
{
    Node *cursor;
    size_t i;

    assert (0 < position);
    assert (position <= list_length(head_ptr)); // by chung
    cursor = head_ptr;
    for (i = 1; (i < position) && (cursor != NULL); i++)
        cursor = cursor->link;
    return cursor;
}

void list_append(Node*& head_ptr, const Node::Item& entry) // insert to the rear
{
    Node *cursor, *append_ptr;
    for (cursor = head_ptr; cursor->link != NULL; cursor = cursor->link);
    append_ptr = new Node;
    append_ptr->data = entry;
    append_ptr->link = NULL;
    cursor->link = append_ptr;
}

Node::Item min(Node* head_ptr)  // keeping a min pointer
{
    assert(head_ptr != NULL);
    Node *smallest = head_ptr;
    for(Node *cursor = head_ptr->link; cursor != NULL; cursor = cursor->link)
       if (cursor->data < smallest->data)
          smallest=cursor;
    return smallest->data;
}

Node::Item max(Node* head_ptr)  // keeping a max data value
{
    assert(head_ptr != NULL);
    Node::Item largest = head_ptr->data;
    for(Node *cursor = head_ptr->link; cursor != NULL; cursor = cursor->link)
       if (cursor->data > largest)
          largest = cursor->data;
    return largest;
}

Node::Item display_middle(Node* head_ptr)
{
    assert(head_ptr != NULL);
    /* Solution 1
    int midi = list_length(head_ptr)/2 + 1;
    return (list_locate(head_ptr, midi))->data;
    */
    // another way
    Node *temp = head_ptr;
    for(size_t i=0; i < list_length(head_ptr)/2; i++) // skipping
       temp=temp->link;
    return temp->data;
}

void main()
{
   Node *head = NULL;  // NULL from stdlib.h

   Node::Item in;
   cout << "Enter numbers to create a linked list (-1 at the end): ";
   cin >> in;
   while (in > 0.0)
   {
      list_head_insert(head, in);
      cin >> in;
   }
   list_display(head);

   cout << "Enter a number to be inserted at the head of the linked list: ";
   cin >> in;
   list_head_insert(head, in);
   list_display(head);
   cout << "Enter a number to be appended to the rear of the linked list: ";
   cin >> in;
   list_append(head, in);
   list_display(head);
   cout << "Middle node = " << display_middle(head) << endl;
   cout << "Min item = " << min(head) << endl;
   cout << "Max item = " << max(head) << endl;
}