filesys.cpp

#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include "os.h"

using namespace std;

//function prototypes
void run_command(OS*,vector<string>*,string);
void test_mlist(int,char**);
void test_os(int,char**);


void usage() {
    cerr << "usage: ./filesys <options>"<< endl;
    cerr << "Examples:" << endl;
    cerr << "./filesys test_mlist <0-6>" << endl;
    cerr << "./filesys test_os <0-2>"<<endl;
    cerr << "./filesys terminal" << endl;
}

/*
	Main function - This is complete
   -------------------------------------------
   - DO NOT CHANGE ANYTHING IN THIS FUNCTION -
   -------------------------------------------
*/
int main(int argc, char* argv[])
{
    if(argc < 2){
    	usage();
    	return -1;
    }
    if(strcmp("terminal",argv[1])==0){
	    cout<<"--------------------------------"<<endl;
	    cout<<"Initailizing 103L OS ..........."<<endl;
	    OS terminal;
	    while(true){
	        string token;
	        string input;
	        vector<string> cmd;
	        cout << "\e[1m\e[38;5;54mCS103L_PA6_shell:\e[0m\e[1m";
	        terminal.present_working_dir();
	        cout<<"$\e[0m ";
	        getline(cin,input);
	        stringstream ss(input);
	        while(ss>>token){
	            cmd.push_back(token);
	        }
	        if(cmd.size() > 0){
	            string command = cmd.at(0);
	            if(command == "exit" || command == "quit"){
	                cout<<"Good bye!!"<<endl;
	                break;
	            }else{
	                run_command(&terminal,&cmd,command);
	            }
	        }
	    }
	    cout<<"--------------------------------"<<endl;
    	cout<<"Shutting down CS103L OS........."<<endl;
	    cout<<"--------------------------------"<<endl;
	}
	else if(strcmp("test_mlist",argv[1])==0){
		test_mlist(argc, argv);
	}else if(strcmp("test_os",argv[1])==0){
		test_os(argc,argv);
	}else{
		usage();
		return -1;
	}
    return 0;
}

/*
   List of commmands and invokation of functions
   -------------------------------------------
   - DO NOT CHANGE ANYTHING IN THIS FUNCTION -
   -------------------------------------------
*/
void run_command(OS* terminal,vector<string> *cmd,string command){
    if(command == "cd"){
        if(cmd->size() < 2){
            terminal->cd_dir("~");
        }else{
            terminal->cd_dir(cmd->at(1));
        }
    }else if(command == "ls")
    {
        if(cmd->size() < 2){
            //default option
            terminal->ls("-d");
        }else{
            terminal->ls(cmd->at(1));
        }
        cout<<endl;
    }else if(command == "pwd")
    {
        terminal->present_working_dir();
        cout<<endl;
    }else if(command == "write")
    {
        if(cmd->size()<2){
            cout<<"usage: write [filename]"<<endl;
        }
        else{
            terminal->file(cmd->at(1),false);
        }
    }else if(command == "read")
    {
        if(cmd->size()<2){
            cout<<"usage: read [filename]"<<endl;
        }else{
            terminal->file(cmd->at(1),true);
        }
    }else if(command == "rm")
    {
        if(cmd->size()<2){
            cout<<"usage: rm [file or directory name]"<<endl;
        }else{
            terminal->del(cmd->at(1));
        }
    }
    else if(command == "mkfile")
    {
        if(cmd->size()<2){
            cout<<"usage: mkfile [filename]"<<endl;
        }else{
            terminal->create_item(cmd->at(1),false);
        }
    }else if(command == "mkdir")
    {
        if(cmd->size()<2){
            cout<<"usage: mkdir [directory]"<<endl;
        }else{
            terminal->create_item(cmd->at(1),true);
        }
    }
    else if(command == "help")
    {
        cout<<"*---------------------------"<<endl;
        cout<<"*----Available Commands:----*"<<endl;
        cout<<"*---------------------------"<<endl;
        cout<<"cd - change directory"<<endl;
        cout<<"pwd - present working director"<<endl;
        cout<<"ls - list everything in the directory"<<endl;
        cout<<"mkfile - make a file"<<endl;
        cout<<"mkdir - make a directory"<<endl;
        cout<<"write - write to a file"<<endl;
        cout<<"read - read a file"<<endl;
        cout<<"rm - delete a file or directory"<<endl;
        cout<<"help - list all available commands"<<endl;
        cout<<"quit or exit - to terminate the program"<<endl;
    }else{
        cout<<"command: '"<<command<<"' not found"<<endl;
    }
}

/*
   This function is used to test your List class.
   -------------------------------------------
   - DO NOT CHANGE ANYTHING IN THIS FUNCTION -
   -------------------------------------------
*/
void test_mlist(int argc, char** argv){
    MList list;
    //statically allocate these data obj to be used for this function
    Data a = {}; //a way to zero intialize = all fields are zero
    Data b = {}; Data c = {}; Data d = {}; Data e = {};
    Data f = {}; Data g = {}; Data h = {}; Data i = {};
    Data j = {}; Data k = {}; Data l = {}; Data m = {};
    a.name = "a"; a.size = 3; b.name = "b"; b.size = 6;
    c.name = "c"; c.size = 1; d.name = "d"; d.size = 4;
    e.name = "e"; e.size = 19; f.name = "f"; f.size = 7;
 	g.name = "g"; h.name = "h"; i.name = "i"; j.name = "j";
 	k.name = "k"; l.name = "l"; m.name ="m"; m.size = 10;
 	c.isFolder = true;l.isFolder=true;
    cout<<boolalpha;
    bool all = false;
    if(argc == 2 || atoi(argv[2]) == 0){
    	all = true;
    }
    if(all || atoi(argv[2]) == 1){
	    cout<<"- \e[35mBASIC CHECKING - MODE 1\e[0m -----"<<endl;
	    //Start our test ----------------------------
	    cout<<list.isEmpty()<<endl;//is empty? true
	    list.push_top(&g);
	    cout<<list.top()->nodeData->name<<endl;//g
	    cout<<list.bottom()->nodeData->name<<endl;//g
	    cout<<list.isEmpty()<<endl;//false
        list.pop_top();
        list.push_top(&g);
        list.pop_bottom();
	    list.push_top(&g);
	    list.push_top(&f);
	    list.push_bottom(&k);
	    cout<<list.top()->nodeData->name<<endl;//f
	    cout<<list.bottom()->nodeData->name<<endl;//k
	    list.pop_bottom();list.pop_top();list.pop_top();
	    cout<<list.isEmpty()<<endl;//true
    }
    if(all || atoi(argv[2]) == 2){
	    cout<<"- \e[35mPRINT CHECKING - MODE 2\e[0m -----"<<endl;
	    list.clear();
	    list.push_top(&l);list.push_top(&d);list.push_top(&c);
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;//c and l are a folder: T-> c d(4) l <-B
	    cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;//c and l are a folder: B-> l d(4) c <-B
	    list.clear();
	    list.push_top(&m);list.push_top(&d);list.push_top(&e);
	    list.push_bottom(&g);list.push_top(&b);list.push_bottom(&f);
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;
	    cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	}
	if(all || atoi(argv[2]) == 3){
	    cout<<"- \e[35mSWAP AND INSERT AFTER CHECKING - MODE 3\e[0m -----"<<endl;
	    list.clear();
        list.push_top(&c);
        list.swapNode(list.top(),list.bottom());
        cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
        list.clear();
	    list.push_top(&d);list.push_top(&e);//before swap: T-> e d <-B
	    list.swapNode(list.top(),list.bottom());//a before b//now T-> d e <-B
	    list.swapNode(list.bottom(),list.top());//b before a//expect the same as starting, since we swap two times: T-> e d <-B
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.clear();
	    list.push_top(&m);list.push_top(&d);list.push_top(&e);list.push_bottom(&g);
	    list.swapNode(list.top()->next,list.bottom());
        //before swap: T-> e d m g <-B
	    //expect: T-> e g m d <-B
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    //moving node m to the top. Expect: T-> m e g d <-B
	    Node * tmp = list.bottom()->prev;list.removeNode(tmp);list.insertAfter(tmp,NULL);
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
        //moving node e to bottom. Expect: T-> m g d e <-
		tmp = list.top()->next;
        list.removeNode(tmp);
        list.insertAfter(tmp,list.bottom());
		cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	}
	if(all || atoi(argv[2]) == 4){
	    cout<<"- \e[35mSORT CHECKING - MODE 4\e[0m -----"<<endl;
	    //each sort 3 steps: 1). when it's empty 2). when there's one element, 3). when there're many elements
	    //SELECTION SORT
	    list.clear();
	    list.sortByNameSelection();//no item to sort, shouldn't do anything
	    list.push_top(&m);list.sortByNameSelection();//one element, sort should be the same: T-> m <-B
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.clear();
	    list.push_top(&m);list.push_top(&d);list.push_top(&e);list.push_bottom(&g);list.push_top(&b);list.push_bottom(&f);
	    //before sort: T-> b e d m g f <-B
	    //expect after: T-> b d e f g m <-B
	    list.sortByNameSelection();
        list.sortByNameSelection();//sort on a sorted list
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    //SortBySize
	    list.clear();
	    list.sortBySizeSelection();//no item to sort, dont do anything
		list.push_top(&m);list.sortBySizeSelection();//one element, sort should be the same: T-> m <-B
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.clear();
	    list.push_top(&m);list.push_top(&d);list.push_top(&e);list.push_bottom(&g);list.push_top(&b);list.push_bottom(&f);
        //before sort: T-> 6 19 4 10 0 7 <-B
	    //expect after: T-> 0 4 6 7 10 19 <-B
	    list.sortBySizeSelection();
        list.sortBySizeSelection();//sort on a sorted list
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
		//INSERTION SORT
	    list.clear();
	    list.sortByNameInsertion();//no item to sort, dont do anything
	    list.push_bottom(&m);list.sortByNameInsertion();//one element, sort should be the same: T-> m <-B
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.clear();
	    list.push_top(&m);list.push_top(&d);list.push_top(&e);list.push_bottom(&g);list.push_top(&b);list.push_bottom(&f);
        //before sort: T-> b e d m g f <-B
	    //expect after: T-> b d e f g m <-B
	    list.sortByNameInsertion();
        list.sortByNameInsertion();//sort on a sorted list
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	}
	if(all || atoi(argv[2]) == 5){
	    cout<<"- \e[35mDELETE CHECKING - MODE 5\e[0m -----"<<endl;
	    //4 cases - delete one element, delete top, delete bottom, delete middle
	    list.clear();
	    list.push_top(&m);cout<<list.isEmpty()<<endl;//not empty = false
	    list.deleteNode(list.top());cout<<list.isEmpty()<<endl;//now empty = true
	    list.clear();
	    list.push_top(&f);list.push_top(&d);cout<<(list.top()==list.bottom())<<endl;//top != bottom; false
	    list.deleteNode(list.top());cout<<(list.top()==list.bottom())<<endl;//now top == bottom; true
	    //expect T-> f <-B, since we delete top which is d
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.clear();
	    list.push_top(&f);list.push_top(&d);
	    list.deleteNode(list.bottom());cout<<(list.top()==list.bottom())<<endl;//now bottom == top; true
	    //expect T-> d <-B, since we delete bottom which is f
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.clear();
	    list.push_top(&m);list.push_top(&d);list.push_top(&e);//before delete: T->e d m<-B
	    list.deleteNode(list.top()->next);
	    //expect after delete: T-> e m <-B
	    cout<<"T-> ";list.printTtB(" ");cout<<"<-B"<<endl;cout<<"B-> ";list.printBtT(" ");cout<<"<-T"<<endl;
	    list.deleteNode(list.top());list.deleteNode(list.top());cout<<list.isEmpty()<<endl;//delete everything, should be an empty list
	}
	if(all || atoi(argv[2]) == 6){
	    cout<<"- \e[35mSEARCH CHECKING - MODE 6\e[0m -----"<<endl;
	    list.clear();
	    cout<<((list.search(list.top(),"a")==NULL)?true:false)<<endl;//search on empty list, not found? -> true
	    list.push_top(&m);list.push_top(&d);
	    cout<<((list.search(list.top(),"a")==NULL)?true:false)<<endl;//a is not in the list, not found? -> true
	    cout<<((list.search(list.top(),"m")==NULL)?true:false)<<endl;//m is in the list, not found? -> false
	}
}


/*
   This function tests a basic functionality of your OS class.
   -------------------------------------------
   - DO NOT CHANGE ANYTHING IN THIS FUNCTION -
   -------------------------------------------
*/
void test_os(int argc, char** argv){
    bool all = false;
    cout<<boolalpha;
    if(argc == 2 || atoi(argv[2]) == 0){
    	all = true;
    }
    if(all || atoi(argv[2]) == 1){
    	OS t;
    	cout<<"- \e[33mTEST BASIC 1\e[0m -----"<<endl;
    	//test basic add files and folders, move into folders, print working directory, go back to root
    	cout<<((t.search_item("itemsearch")==NULL)? true:false)<<endl;//true, nothing in the directory yet.
    	t.create_item("Paola",false);t.create_item("Bonny",true);
    	t.create_item("Shaunta",true);t.create_item("Holl",false);
    	t.create_item("Federico",false);t.create_item("Terrian",false);
    	t.create_item("Marie",true);t.create_item("Charlie",true);
    	//Bonny Charlie Federico(0) Holl(0) Marie Paola(0) Shaunta Terrian(0) - list should already be sorted ascending order
    	t.ls("-d");cout<<endl;
    	//reverse of above: Terrian(0) Shaunta Paola(0) Marie Holl(0) Federico(0) Charlie Bonny
    	t.ls("-r");cout<<endl;
    	t.cd_dir("Marie");t.create_item("Shuan",true);t.cd_dir("Shuan");
    	t.create_item("Jarrod",true);t.create_item("Reinaldo",false);
    	//Jarrod Reinaldo(0)
    	t.ls("-d");cout<<endl;
    	cout<<((t.search_item("Jarrod")==NULL)? true:false)<<endl;//true, item found
    	t.cd_dir("Jarrod");
    	t.present_working_dir();cout<<endl;//root/Marie/Shuan/Jarrod/
    	t.cd_dir("..");//back up one step
    	t.ls("-r");cout<<endl;//reverse print = Reinaldo(0) Jarrod
    	t.present_working_dir();cout<<endl;//root/Marie/Shuan/
    	t.cd_dir("~");//back to root
    	t.present_working_dir();cout<<endl;//root/
    	t.ls("-d");cout<<endl;//
    }
    if(all || atoi(argv[2]) == 2){
    	OS t;
    	cout<<"- \e[33mTEST BASIC 2\e[0m -----"<<endl;
        t.cd_dir("..");
        t.present_working_dir();cout<<endl;//root/
        t.cd_dir("..");
        t.present_working_dir();cout<<endl;//root/
    	t.create_item("o",true);t.cd_dir("o");//root/o/
    	t.create_item("o",true);t.cd_dir("o");//root/o/o/
    	t.create_item("o",true);t.create_item("d",false);//root/o/o/(d(0) o)
    	t.ls("-d");cout<<endl;//d(0) o
    	t.cd_dir("o");
    	t.create_item("o",true);//root/o/o/(d o)/o
		t.cd_dir("o");t.create_item("o",true);//root/o/o/(d o)/o/o
    	t.cd_dir("o");t.create_item("o",false);//root/o/o/(d o)/o/
    	t.ls("-r");cout<<endl;//o(0)
    	t.present_working_dir();cout<<endl;//root/o/o/o/o/o/
    	t.create_item("a",true);t.create_item("c",false);
    	t.ls("-r");cout<<endl;//o(0) c(0) a
    	t.cd_dir("a");t.cd_dir("~");//back to root
    	t.create_item("b",true);t.create_item("c",false);
    	t.ls("-d");cout<<endl;//b c(0) o(0)
    	t.del("b");t.del("orange");t.del("o");
    	t.ls("-sort=size");cout<<endl;//c(0)
    }
}

mlist.cpp

#include <iostream>
#include <string>
#include <cstring>
#include "mlist.h"
using namespace std;
//------------------------------------------------------------------------------
//IMPORTANT: You are not allowed to remove or add any parameters to any functions.
//NOTE: There can only be at most 2 loops in this file
//------------------------------------------------------------------------------

//Constructor, construct an empty doubly linked list.
MList::MList(){
    ntop = NULL;
    nbottom = NULL;
}

//Destructor, properly clears and deallocates everything of current list.
//simply call the clear function if you have already implemented that.
MList::~MList(){
    clear();
}


//Note: RECURSION --- This function should be implemented using recursion.
//this function properly clears and deallocates everything of current list.
//there should be no loop in this function
void MList::clear(){
    if(isEmpty()) return; // this is the base case

    Data * data = ntop->nodeData;
    if (data->childList != NULL){
        data->childList->clear();
    }
    if (ntop->next == NULL) {
        ntop = NULL;
        nbottom = NULL;
        return;
    }

    ntop = ntop->next;
    clear();
}

//returns a boolean true if the list is empty, false if otherwise.
bool MList::isEmpty(){
    return (ntop==NULL);
}

/*
    Add or insert a new node with d_item as its data at the top of the list.
    You need to dynamically allocate memory for the new node.
*/
void MList::push_top(Data* d_item){
    Node * newNode = new Node;
    newNode->nodeData = d_item;
    newNode->prev = NULL;
    newNode->next = ntop;

    if (ntop != NULL) {
        ntop->prev = newNode;
    }
    if (nbottom == NULL) {
        nbottom = newNode;
    }

    ntop = newNode;
}
/*
    Add or insert a new node with d_item as its data at the bottom of the list.
    You need to dynamically allocate memory for the new node.
*/
void MList::push_bottom(Data* d_item){
    Node * newNode = new Node;
    newNode->nodeData = d_item;
    newNode->prev = nbottom;
    newNode->next = NULL;

    if (isEmpty()) {
        ntop = newNode;
        nbottom = newNode;
        return;
    }

    if (nbottom != NULL) {
        nbottom->next = newNode;
    }
    nbottom = newNode;
}

/*
    Delete or remove the top node of the list.
    Once pop, you need to properly deallocate the memory for the node (not the data).
    If your list is currently empty, you don't have to do anything.
*/
void MList::pop_top(){
    if(isEmpty()) return;  // just to test to make sure that this is not empty

    Node *temp = ntop;
    ntop = temp->next;
    if(ntop!=NULL){ // if the next thing in the list was not the end of the list
        ntop->prev = NULL;
    }
    else{
        nbottom = NULL;
    }
    delete temp;
}

/*
    Delete or remove the bottom node of the list.
    Once pop, you need to properly deallocate the memory for the node (not the data).
    If your list is currently empty, you don't have to do anything.
*/
void MList::pop_bottom(){
    if(isEmpty()) return;  // just to test to make sure that this is not empty

    Node *temp = nbottom;
    nbottom = temp->prev;
    if(nbottom!=NULL){ // if the next thing in the list was not the end of the list
        nbottom->prev = NULL;
    }
    else{
        ntop = NULL;
    }
    delete temp;
}

/*
    Note: RECURSION --- This function should be implemented using recursion.
    Search a node in the list that has data with the same name as the parameter.
    If one is found, return the pointer to the node.
    If one is not found, return NULL.
*/
Node* MList::search(Node* start, string name){
    if(isEmpty()) return NULL; // if the thing is empty to begin with then return NULL
    if(start==NULL) return NULL; // if we are at the end of our ropes here then we are going to stop

    //if both of the base cases are not applicable then go into the rest of the search

    if(start->nodeData->name == name){
        return start;
    }
    else{
        start = search(start->next,name);
        return start; // when it echos all the way back out, it will return what start is
    }
}


//Swapping node a with node b.
void MList::swapNode(Node* a, Node*b){ // changes everything about the nodes. They switch from one to another
//this includes the data, previous and next pointers
    Node * temp = new Node;
    temp->nodeData = a->nodeData;
    temp->next= a->next;
    temp->prev= a->prev;

    a->nodeData = b->nodeData;
    a->next= b->next;
    a->prev= b->prev;

    b->nodeData= temp->nodeData;
    b->next = temp->next;
    b->prev= temp->prev;
}

/*
    This function PERMANENTLY deletes a node from the list given a pointer to that node.
    You can assume that the node exists in the list - no need to search for the node.
*/
void MList::deleteNode(Node* a){ // check this!!
if(search(ntop,a->nodeData->name)==NULL) return; // if the node doesnt exist then dont do anything!
    if(nbottom==a) pop_bottom();
    else if(ntop==a) pop_top();
    else{
        Node* temp_1 = new Node;
        temp_1 = a->prev;
        temp_1->next = a->next;

        Node* temp_2 = new Node;
        temp_2 = a->next;
        temp_2->prev = a->prev;

        delete temp_2;
        delete temp_1;  // because we dont need these now. We have
    }
}

/*
    Unlike the delete function above, this function does NOT permanently delete the node.
    What you need to do at the last step is to set the node's prev and next pointers to NULL.
    Again, you can assume that the node exists in the list - no need to search for the node.
    Note: this function will be useful
        when we want to insert the given node later at another position after you remove it from the list.
*/
void MList::removeNode(Node* a){
    Node * prevNode = a->prev;
    Node * nextNode = a->next;

    if (prevNode == NULL) {
        ntop = nextNode;
    }
    if (nextNode == NULL) {
        nbottom = prevNode;
    }

    if (prevNode != NULL) {
        prevNode->next = nextNode;
    }
}

/*
    Insert node a after node b.
    Note: b can be NULL, Q: what does that mean? // there is nothing in the set yet.
    otherwise, you can assume that b exists in the list.
*/
void MList::insertAfter(Node *a, Node* b){ // do you delete the memory now or later
    if (b == NULL) {
        ntop = a;
        nbottom = a;
        return;
    }

    // Given a list such as ...
    // B  -->  C
    // This means that nTop == B and nBottom = C
    // To insert A after B... we need to make sure that A's "next" pointer points to C!
    // If B doesn't have a next pointer, then it means we're at the end of the list, and our new nBottom is now A!
    // Now, this means that nTop == B, b -> A , A -> C  and nBottom is still C
    //
    // Given a list B
    // this means nTop == B and nBottom == B and B->next == null
    // to insert A after B we need to now set "A" to the bottom of the list
    // which means we now have:
    // B --> A    nTop = B and nBottom = A
    if (b->next == NULL) {
        nbottom = a;
    }

    a->next = b->next;
    a->prev = b;
    b->next = a;
}


/*
    Note: RECURSION --- This function should be implemented using recursion.
    Implement a SELECTION SORT algorithm using recursion.
    The function takes in a start node.
    Things to keep in mind:
        1). sort should NOT be run if the list is empty.
        2). if mode = true, sort by name in alphabetical order
            (i.e., A-Za-z) based on ASCII number if mode = true
        3). if mode = false, sort by size in ascending order (low->high)
    You can search any online resources available to you (i.e. search 'selection sort')
    to understand the basic idea behind the selection sort algorithm.
    Note:
        1). there can only be at most one loop in this function
        2). this function is private
            see sortByNameSelection and sortBySizeSelection for the calls to this function
*/
void MList::sortSelection(Node* start, bool mode){
    if(isEmpty()) return;
    if(start == NULL) return;// if the last start was the end and now we are pointing to a NULL

    Node *nextposition = start->next;

    Node *place = start;
    Node *lowest = start;

    while(place!=NULL){ // while we are not at the end of the list of nodes
        if(mode){
            if(lowest->nodeData->name > place->nodeData->name){ // if the one we are looking at is
                lowest = place;
            }
        }
        else{
            if(lowest->nodeData->size > place->nodeData->size){
                lowest = place;
            }
        }
        place = place->next;
        //lowest will keep track of which one is lowest. Place will be what goes through. and then at the end lowest and start will switch and will run next iteration with next position
    }

    swapNode(lowest, start); // this may not work as you are intending
    sortSelection(start->next, mode);
}


/*
    Note: RECURSION --- This function should be implemented using recursion.
    Implement an INSERTION SORT algorithm using recursion.
    The function takes in a start node.
    Things to keep in mind:
        1). sort should NOT be run if the list is empty.
        2). we are trying to sort by name in alphabetical order
            (i.e., A-Za-z) based on ASCII number.
    You can search any online resources available to you (i.e. search 'insertion sort')
    to understand the basic idea behind the insertion sort algorithm.
    The gif from the wikipedia page of this algorithm is the easiest to understand in my opinion
    Link: https://en.wikipedia.org/wiki/Insertion_sort
    Note:
        1). there can only be at most one loop in this function
        2). this function is private, see sortByNameInsertion for the call to this function
*/
void MList::sortInsertion(Node* start){
    if(isEmpty()) return; // if it is empty
    if(start==NULL) return;  // if the last start was the end and now we are pointing to a NULL
    // when we start this we are gonna start at the header of this
    Node *nextposition = start->next; // this is gonna be used so that we go to the next one on the next iteration of recursion

    while(start->prev!=NULL){ // once it is all the way to the left
        if(start->prev->nodeData->name > start->nodeData->name) swapNode(start->prev, start);
                // if the previous node's name is high on ascii, switch the nodes

        else break; // if it isnt, then break and go to the next node and push it through the sorted part on the left
    }

    if(start->prev == NULL) sortInsertion(nextposition);
}



/*
    Note: RECURSION --- This function should be implemented using recursion.
    Traverse and print our list from node n to the top.
    we will seperate each node printed by the passed-in delimiter.
    If a node you encounter is a folder type, do

        cout<<....name.....<<delim;

    If a node you encounter is a file type, do

        cout<<....name.....<<"("<<..size..<<")"<<delim;

    Note: please do NOT include <<endl; (aka newline)
    Example output (assume that the delimiter is a single space):

        folder1 file1(0) folder2 file2(0)

    There should be no loop in this function
    See printBtT function for the call to this function.
    This function is private
*/
void MList::traverseToTop(Node* n, string delim){
    if(isEmpty() || n == NULL) return;

    Data *data = n->nodeData;
    if (!data->isFolder) {
        std::cout<<data->name<<"("<<data->size<<")"<<delim;
    } else {
        std::cout<<data->name<<delim;
    }

    traverseToTop(n->prev, delim);
}

/*
    Note: RECURSION --- This function should be implemented using recursion.
    Traverse and print our list from node n to the bottom.
    we will seperate each node printed by the passed-in delimiter.
    If a node you encounter is a folder type, do

        cout<<....name.....<<delim;

    If a node you encounter is a file type, do

        cout<<....name.....<<"("<<..size..<<")"<<delim;

    Note: please do NOT include <<endl; (aka newline)
    Example output (assume that the delimiter is a single space):

        folder1 file1(0) folder2 file2(0)

    There should be no loop in this function
    See printTtB function for the call to this function.
    This function is private
*/
void MList::traverseToBottom(Node* n,string delim){
    if(isEmpty() || n == NULL) return;

    Data *data= n->nodeData;
    if (!data->isFolder) {
        std::cout<<data->name<<"("<<data->size<<")"<<delim;
    } else {
        std::cout<<data->name<<delim;
    }

    traverseToBottom(n->next, delim);
}

//------------------------------------------------------------------------------
//FUNCTIONS BELOW ARE COMPLETE, PLEASE DON'T CHANGE ANYTHING HERE
//------------------------------------------------------------------------------

//getting the pointer to the top node.
Node* MList::top(){
    return ntop;
}

//getting the pointer to the bottom node.
Node* MList::bottom(){
    return nbottom;
}

//call traverseToBottom to print all item in the list from bottom node to top node
//the list of items is separated by a given delimiter
void MList::printBtT(string delim){
    //create a temp pointer to hold bottom
    traverseToTop(nbottom,delim);
}

//call traverseToBottom to print all item in the list from top node to bottom node
//the list of items is separated by a given delimiter
void MList::printTtB(string delim){
    Node* tmp = ntop;
    traverseToBottom(tmp,delim);
}

//call sortSelection function, mode = true = sort by name
//public member
void MList::sortByNameSelection(){
    bool mode = true;
    Node *tmp = ntop;
    sortSelection(tmp,mode);
}

//call sortSelection function, mode = false = sort by size
//public member
void MList::sortBySizeSelection(){
    bool mode = false;
    Node *tmp = ntop;
    sortSelection(tmp,mode);
}

//call sortInsertion function
//public member
void MList::sortByNameInsertion(){
    Node *tmp = ntop;
    sortInsertion(tmp);
}

mlist.h

#ifndef MLIST_H
#define MLIST_H
#include <string>
using namespace std;

//------------------------------------------------------------------------------
//IMPORTANT: You are not allowed to remove or add any parameters to any functions.
//------------------------------------------------------------------------------


//struct and class declarations
struct Data;
class MList;

/*
   Node struct:
   		2 pointers - prev/next are for doubly linked list
		1 pointer points to the Data object.
*/
struct Node{
	//for doubly linked list
	Node* prev;
	Node* next;
	//a pointer that points to the data object that this node holds
	Data* nodeData;
};


//Data struct i.e., data object
struct Data{
	string name;
	bool isFolder;
	string text;
	size_t size;
	MList* childList;//a list of children - a pointer to MList
};


class MList{
public:
	//constructor
	MList();
	//destructor
	~MList();
	//push item to list (from top)
	void push_top(Data* d_item);
	//delete the top Node
	void pop_top();
	//push item to list (from bottom)
	void push_bottom(Data* d_item);
	//delete the bottom Node
	void pop_bottom();
	//check if list is empty
	bool isEmpty();
	//clear/empty out the list
	void clear();
	//swap two nodes
	void swapNode(Node* a, Node*b);
	//delete node permanently
	void deleteNode(Node* a);
	//remove the node, not permantly, useful for adding it later. If really want to delete, use delete function.
	void removeNode(Node* a);
	//insert Node a after Node b
	void insertAfter(Node *a, Node* b);
	//search a node with a given name from the starting point.
	Node* search(Node* start,string name);
	//retrieve the top node
	Node* top();
	//retrieve the bottom node
	Node* bottom();
	//print from bottom to the top node
	void printBtT(string delim);
	//print from top to the bottom node
	void printTtB(string delim);
    //call to recursive sort (by name) function using Selection sort algorithm
	void sortByNameSelection();
	//call to recursive sort (by name) function using Insertion sort algorithm
	void sortByNameInsertion();
	//call to recursive sort (by size) function using Selection sort algorithm
	void sortBySizeSelection();
    
private:
	//a pointer that points to the first node (top)
	Node* ntop;
	//a pointer that points to the last node (bottom)
	Node* nbottom;
	//recursively traverse the list from n_item to the top node
	void traverseToTop(Node* n_item,string s);
	//recursively traverse the list from n_item to the bottom node
	void traverseToBottom(Node* n_item,string s);
    //recursive sort using Selection sort algorithm, mode determines if it's by size or by name
	void sortSelection(Node* start, bool mode);
	//recursive sort (by name) using Insertion sort algorithm
	void sortInsertion(Node* start);
};
#endif

os.cpp

#include <iostream>
#include "os.h"
using namespace std;
//------------------------------------------------------------------------------
//IMPORTANT: You are not allowed to remove or add any parameters to any functions.
//------------------------------------------------------------------------------

/*
Constructor
	Dynamically allocate root data.
	set isFolder = true.
	dynamically allocate Mlist for our root data as well (since it's a directory type).
    push our newly created data object pointer to wd and dataStack from the top.
*/
OS::OS(){
    //is folder is part of the node data
    root_data = new Data; // dynamically allocate this new data
    root_data->isFolder = true; // it is a folder
    root_data->childList = new MList; // then make its childlist new as well
    wd.push_top(root_data); // then push it to the top of the mlist that we are currently on 
    dataStack.push_top(root_data);
}

/*
Destructor to clean-up memory, i will leave this for you to figure it out.
*/
OS::~OS(){

    
     
    
    
}

/*
Search a node in the current directory
	If one is found, return a pointer to that node
	If one is not found, return NULL
*/
Node* OS::search_item(string fname){
    if(wd.isEmpty()) return NULL; 
    Node* data = wd.top();
    return wd.search(data,fname);
}

/*
Delete a node in the current directory
	Note: this function only deletes (permanently) the node, not the Data obj the node points to
	If the item you want to delete doesn't exist in the current directly, do

		cout<<"Error: cannot find file or directory '"<<fname<<"'"<<endl;
*/
void OS::del(string fname){
    Node* data = wd.top();
    data = wd.search(data,fname);
    if(data==NULL){
        std::cout<<"Error: cannot find file or directory '"<<fname<<"'"<<std::endl;
        return;
    } 
    else{
        // at this point we know that the node exists in this directory
        wd.deleteNode(data);
    }
}

/*
Create a file or a folder, use boolean isFolder to tell (true if folder, false if file)
Things to keep in mind:
	1). Don't forget to search for a node in the current directory with the same name first.
		if the name already exists, do:

				cout<<"Directory or file name '"<<fname<<"' already exists"<<endl;

	2). If you are creating a folder, make sure to allocate a memory for its MList object
		and set the boolean isFolder appropriately.
    3). At this point you should initialize the size of file and folder to 0
	4). Once the data object is created, add the pointer to that to dataStack from the "top" 
		and add the node to the current directory list from the "bottom".
	5). Once added, sort the current directory list by name.
*/
void OS::create_item(string fname, bool isFolder){
    Node* data = wd.top();
    data = wd.search(data,fname);
    if(data == NULL){
        std::cout<<"Directory or file name '"<<fname<<"' already exists"<<endl;
        return;
    }
    else{
        if(isFolder){
            Data* newfolder = new Data; // creating new data in the form of a folder 
            newfolder->name = fname;
            newfolder->isFolder= true;
            newfolder->childList = new MList;
            newfolder->size = 0;
            wd.push_bottom(newfolder);
            wd.sortByNameInsertion();
            dataStack.push_bottom(newfolder);
        }
        else{
            Data* newfile = new Data;
            newfile->name = fname;
            newfile->isFolder = false;
            newfile->childList = NULL;
            newfile->size = 0;
            wd.push_bottom(newfile);
            wd.sortByNameInsertion();
            dataStack.push_bottom(newfile);
        }
    }
}

/*
Read or write a file according to the boolean isRead (true = read, false = write)
Things to keep in mind:
	1). make sure that a file "fname" exists in our current directly, if not

			cout<<"Error: cannot find file '"<<fname<<"'"<<endl;

	2). if it exists, make sure that it is a file type, not a folder type. If it is a folder type,

			cout<<"Error: '"<<fname<<"' is not a file"<<endl;

	3). read mode is simply just cout<<...text...<<endl;
	4). for write mode you need to allow user input, use these 3 lines below:

                cout<<"$> ";
				string input;
				getline(cin,input);

		then simply just set text to the input string.
	5). the size of the file should be based on the length of the input string.
*/
void OS::file(string fname, bool isRead){
    Node* data = wd.top();
    data = wd.search(data,fname);
    if(data==NULL){
        std::cout<<"Error: cannot find file or directory '"<<fname<<"'"<<std::endl;
        return;
    } 
    else if(data->nodeData->isFolder){
		std::cout<<"Error: '"<<fname<<"' is not a file"<<std::endl;
        return; 
    }
    else{
        if(isRead){
            std::cout<<data->nodeData->text<<std::endl;
        }
        else{
            std::cout<<"$> ";
            std::string input;
            std::getline(std::cin,input);

            data->nodeData->text = input;
            data->nodeData->size = input.length();
        }
    }
}


//Change directory
void OS::cd_dir(string fname){
	if(fname == ".."){
		//this option takes you up one directory (move the directory back one directory)
		//you should not be able to go back anymore if you are currently at root.
        if(wd.top() == dataStack.top()) return;
        // we should use the top node in wd, find it in datastack and then change wd to that in datastack
        Node* changer = wd.top();
        // now find changer in datastack
        changer = dataStack.search(dataStack.top(),changer->nodeData->name)->prev;
        wd.clear();
        // idk what to do with this 
	}
    else if(fname == "~"){
		//this option takes you directly to the home directory (i.e., root).
        Node* topOfDataStack= dataStack.top();
        wd.clear(); // does this fuck shit up bad??
        // wd.push_bottom(topOfDataStack->nodeData);
        wd = *topOfDataStack->nodeData->childList;
	}
    else{
		/*
			This option means that you are trying to access (go into) a directory
			1). check whether there exists a node with that name, if you cannot find it:

					cout<<"Error: cannot find directory '"<<fname<<"'"<<endl;

			2). if it does exist, check whether it is a folder type. If it is a file type:

					cout<<"Error: '"<<fname<<"' is not a directory"<<endl;
			
			3). after checking both things, you can safely move to another directory
		*/
        Node* data = wd.top();
        data = wd.search(data,fname);
        if(data==NULL){
            std::cout<<"Error: cannot find file or directory '"<<fname<<"'"<<std::endl;
        return;
        } 
        else if(! data->nodeData->isFolder){
            std::cout<<"Error: '"<<fname<<"' is not a directory"<<std::endl;
        }   
        else{
            Node* newlist = dataStack.search(wd.top(),fname);  // this is gonna be the node for the new list, find it in datastack
            if(newlist->prev!=NULL){
                newlist = newlist->prev;
            }
            else newlist = dataStack.top();
                // now we are to the parent of the mlist
            wd.clear();
            wd = *newlist->nodeData->childList; 
        }
	}
}

//Print list of item in the current directory, the way you print it will be according to the passed-in option
void OS::ls(string option){
	if(option == "-d"){
		//Default option - print the list of items in the current directory from top to bottom.
		//use a single space as delimiter.
        wd.printTtB(option);
	}
	else if(option == "-sort=name"){
		//Use Insertion Sort to sort items in the current directory and print from top to bottom (alphabetically A-Za-z).
		//use a single space as delimiter.
        wd.sortByNameInsertion(); 
	}
    else if(option == "-r"){
		//Reverse print the list of items in the current directory (i.e., print form bottom to top).
		//use single space as delimiter.
        wd.printBtT(option);
	}
    else if(option == "-sort=size"){
		//Sort list by size and print the list of items in the current directory from top to bottom.
		//use single space as delimiter.
        wd.sortBySizeSelection(); 
	}
	else{
		cout<<"usage: ls [optional: -r for reverse list, -sort=size to sort list by file size, -sort=name to soft list by name]";
	}
}

//Priting path from root to your current directory.
//use slash "/" as our delimiter.
//Example output: root/cs103/usc/viterbi/
void OS::present_working_dir(){
    
}

os.h

#ifndef OS_H
#define OS_H
#include "mlist.h"

//------------------------------------------------------------------------------
//IMPORTANT: You are not allowed to remove or add any parameters to any functions.
//------------------------------------------------------------------------------

class OS{
	public:
		//constructor
		OS();
		//destructor
		~OS();
		//read and write a file (depending on the boolean flag)
		void file(string fname,bool isRead);
		//delete file and folder:
		//Note; node that holds the data is permanently deleted, but not the data itself
		void del(string fname);
		//ls - list a file in the directory (the order of listing depends on the option)
		void ls(string option);
		//create folder or file (depending on the boolean flag)
		void create_item(string fname,bool isFolder);
		//delete directory or file
		void rm(string fname);
		//cd - changing directory
		void cd_dir(string fname);
		//pwd - present working directory (print path)
		void present_working_dir();
		//search item in dir
		Node* search_item(string s);
	private:
		Data* root_data;//data for root - technically don't really need this! but help keeping track of root
		MList wd;//keep track of the current directory, LIFO manner
		MList dataStack;//keep track of all dynamically allocate, LIFO manner
};
#endif