// Doubly Linked List
#include <stdlib.h> // Provides size_t
#include <assert.h>
#include <iostream.h>

struct Node
{   typedef double Item;
    Item data;
    Node *blink; // Backward Link
    Node *flink; // Forward Link
};

size_t list_length(Node* head_ptr)
{
    Node *cursor;
    size_t answer = 0;
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->flink)
        answer++;
    return answer;
}

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

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->flink;
    return cursor;
}

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

    insert_ptr = new Node;
    insert_ptr->data = entry;
    insert_ptr->blink = NULL;
    insert_ptr->flink = head_ptr;
    if(head_ptr != NULL)
       head_ptr->blink = insert_ptr;
    head_ptr = insert_ptr;
}

void list_insert(Node* previous_ptr, const Node::Item& entry) // page 218
{
    Node *insert_ptr;








}

void list_head_remove(Node*& head_ptr) // removing just head
{
    Node *remove_ptr;










}

void list_remove(Node* previous_ptr) // removing a node after previous_ptr
{
    Node *remove_ptr;








}

void main()
{
   Node *head = NULL;  // NULL from stdlib.h
   int i;
   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 an index (head position is 1, ...) A node added after that: ";
   cin >> i;
   Node* found_ptr = list_locate(head, i);
   cout << "Enter a number: ";
   cin >> in;
   list_insert(found_ptr, in);
   list_display(head);

   cout << "One head node will be removed" << endl;
   list_head_remove(head);
   list_display(head);

   cout << "Enter an index (head position is 1, ...) The next node deleted: ";
   cin >> i;
   found_ptr = list_locate(head, i);
   list_remove(found_ptr);
   list_display(head);
}