/* Ma'sum Abdul Wadud
 * Lab 7
 * CSC 230 Section 01
 */


#include <iostream>
#include <string>
#include <fstream>

using namespace std;

struct node{
  string fullName;
  string ssn;
  node* next;
  node* prev;
};

void search(node* head, string userSSN){
  int count = 0;

  while(head != NULL){
    if(userSSN.compare(head->ssn) == 0){
      cout << "Found at location: " << count << "\n" << endl;
    }
    head = head->next;
    count++;
  }
}

void append(node*& head, string userSSN, string name)
{
  node* newNode = new node;
  newNode->ssn = userSSN;
  newNode->fullName = name;
  newNode->next = NULL;
  //newNode -> prev = NULL;

  if(head == NULL)
    {
      head = newNode;
    }

  else
    {
    node* temp = head;
    while(temp -> next != NULL){
        temp = temp -> next;
    }
    temp -> next = newNode;
    }
}

void insert(node*& head, node*& tail, string userSSN, string name){
    if(head == NULL){
        head = new node;
        head->next = NULL;
        head->prev = NULL;

        head->ssn = userSSN;
        head->fullName = name;
    }

else if((head->ssn) > userSSN){
    node* temp = new node;
    temp->next = head;
    temp->prev = NULL;
    head->prev = temp;
    head = temp;

    head->ssn = userSSN;
    head->fullName = name;
}

else{
    node* temp = head;
    while(temp->next != NULL){
        if((temp->ssn < userSSN) && ((temp->next)->ssn) > userSSN){
            break;
        }
        temp = temp->next;
    }

    if(temp->next == NULL){
        node* current = new node;
        temp->next = current;
        current->prev = temp;
        current->next = NULL;

        current->ssn = userSSN;
        current->fullName = name;
    }
    else{
        node* following = temp->next;
        node* current = new node;
        temp->next = current;
        following->prev = current;
        current->next = following;
        current->prev = temp;

        current->ssn = userSSN;
        current->fullName = name;

    }
}
}
    /*if((newPtr->ssn) < (head->ssn)){
        newPtr->prev = NULL;
        head->prev = newPtr;
        newPtr->next = head;
        head = newPtr;
        //return;
    }

    if((newPtr->ssn) > (tail->ssn)){

    }
    else{
        newPtr = new node;
        newPtr->ssn = userSSN;
        newPtr->fullName = name;
        newPtr->prev = tail;
        tail->next = newPtr;
        tail = newPtr;
    }
    tail->next = NULL;
}*/




void print(node*& head){
  node* tmp = head;

  while(tmp != NULL){
    cout << tmp->ssn << endl;
    tmp = tmp->next;
  }
}


int main(int argc, char* argv[]){
  fstream input(argv[1]);
  string i, s, f, l;
  string userSSN;
  string personName;

  int count = 0;
  node* headPtr;
  node* tailPtr;

  while(!input.eof()){
    input >> i >> s >> f >> l;
    personName = f + " " + l;
    userSSN = s;

    insert(headPtr, tailPtr, userSSN, personName);
    count++;

    if(!input){
      break;
    }
  }
  input.close();
  cout << "\nInput a Social Security Number: " << endl;
  cin >> userSSN;

  //search(headPtr, tailPtr, userSSN);
  print(headPtr);

  return 0;
}