bcc-cis-277-602-2019

linkedlist.cpp

#include <iostream>

using namespace std;
// Changes the input type for the user, type must support comparison logic
typedef string INPUT_TYPE;

struct Node {
  INPUT_TYPE data;
  Node *next;
  Node *last;
};

void swap (INPUT_TYPE* a, INPUT_TYPE* b) {
  INPUT_TYPE t = *a;
  *a = *b;
  *b = t;
}

bool str_le(string l, string r) {
  if (l == r)
    return true;

  if (l.length() < r.length())
    return true;

  if (l.length() > r.length())
    return false;

  for (int i = 0; i < l.length(); ++i) {
    if (l[i] > r[i]) {
      return false;
    }
  }

  return true;
}

Node *partition(Node *l, Node *h) {
  INPUT_TYPE x = h->data;
  Node *i = l->last;

  for (Node *j = l; j != h; j = j->next) {
    // if (j->data <= x) {
    if (str_le(j->data, x)) {
      i = (i == NULL) ? l : i->next;
      swap(&(i->data), &(j->data));
    }
  }
  i = (i == NULL) ? l : i->next; // Similar to i++
  swap(&(i->data), &(h->data));
  return i;
}

void _quickSort(Node *l, Node *h) {
  if (h != NULL && l != h && l != h->next) {
    Node *p = partition(l, h);
    _quickSort(l, p->last);
    _quickSort(p->next, h);
  }
}

class DLL {
public:
  Node *here = nullptr;
  bool empty = true;
  int count = 0;

#define RETURN_IF_EMPTY                                                        \
  if (this->empty)                                                             \
    return false;

  DLL() {}

  bool next() {
    RETURN_IF_EMPTY
    if (this->here->next) {
      this->here = this->here->next;
      return true;
    } else {
      return false;
    }
  }

  bool back() {
    RETURN_IF_EMPTY
    if (this->here->last) {
      this->here = this->here->last;
      return true;
    } else {
      return false;
    }
  }

  Node *append() {
    if (!this->empty && this->here->next) {
      this->next();
      return this->append();
    } else {
      Node *t = new Node();
      if (!this->empty) {
        this->here->next = t;
        t->last = this->here;
      }
      this->here = t;
      this->empty = false;
      ++(this->count);
      return t;
    }
  }

  Node *appendBack() {
    if (!this->empty && this->here->last) {
      this->back();
      return this->appendBack();
    } else {
      Node *t = new Node();
      if (!this->empty) {
        this->here->last = t;
        t->next = this->here;
      }
      this->here = t;
      this->empty = false;
      ++(this->count);
      return t;
    }
  }

  bool del() {
    RETURN_IF_EMPTY
    Node *decendent;
    this->empty = true;

    if (this->here->next) {
      decendent = this->here->next;
      this->here->next->last = this->here->last;
      this->empty = false;
    }
    if (this->here->last) {
      decendent = this->here->last;
      this->here->last->next = this->here->next;
      this->empty = false;
    }

    delete this->here;
    --(this->count);
    this->here = decendent;
    return true;
  }

  Node *inject() {
    Node *t = new Node();
    t->next = this->here->next;
    t->last = this->here;
    if (this->here->next) {
      this->here->next->last = t;
    }
    this->here->next = t;
    this->here = t;
    ++(this->count);
    return this->here;
  }

  Node *scrollBack() {
    while (!this->empty && this->here->last) {
      this->back();
    }
    return this->here;
  }

  bool scrollTo(INPUT_TYPE cmp) {
    this->scrollBack();
    while (this->here->next && this->here->data != cmp) {
      if (!this->next()) {
        return false;
      }
    }
    return this->here->data == cmp;
  }

  void sort() {
    Node* end = this->here;
    Node* start = this->scrollBack();
    _quickSort(start, end);
  }
};

#ifndef MAIN
#define MAIN
int main() {
  DLL list;

  while (true) {
    cout << "1) Add\n"
            "2) Delete\n"
            "3) Display\n"
            "4) Modify\n";
            "5) Search\n";
    
    int cmd = -1;
    cout << "> ";
    cin >> cmd;

    switch (cmd) {
      case 1: 
        cout << "add> ";
        cin >> list.append()->data;
        list.sort();
        break;
      case 2: {
        cout << "delete> ";
        INPUT_TYPE cmp;
        cin >> cmp;
        if (list.scrollTo(cmp) && list.del()) {
          cerr << "Ok" << endl;
        }
        else {
          cerr << "Could not delete" << endl;
        }
      } break;        
      case 3:
        list.scrollBack();
        if (!list.empty) {
          do {
            cout << list.here->data << endl;
          } while (list.next());
        }

        break;
      case 4:
        cout << list.here->data << " > ";
        cin >> list.here->data;
        list.sort();
      case 5: {
        cout << "search> ";
        INPUT_TYPE cmp;
        cin >> cmp;
        if (list.scrollTo(cmp)) {
          cerr << list.here->data << endl;
        }
        else {
          cerr << "Could not find" << endl;
        }
      } break;
      default:
        cerr << "Select a command" << endl;
    }
  }
}
#endif

linkedlist.output

./linkedlist 
1) Add
2) Delete
3) Display
4) Modify
> 1
add> 123
1) Add
2) Delete
3) Display
4) Modify
> 1
add> 2222
1) Add
2) Delete
3) Display
4) Modify
> 1
add> 111
1) Add
2) Delete
3) Display
4) Modify
> 3
111
123
2222
1) Add
2) Delete
3) Display
4) Modify
> 2
delete> 222
Could not delete
1) Add
2) Delete
3) Display
4) Modify
> 1
add> 222
1) Add
2) Delete
3) Display
4) Modify
> 3
111
222
123
2222
1) Add
2) Delete
3) Display
4) Modify
> 2
delete> 999
Could not delete
1) Add
2) Delete
3) Display
4) Modify
> 2
delete> 222
Ok
1) Add
2) Delete
3) Display
4) Modify
> 3
111
123
2222
1) Add
2) Delete
3) Display
4) Modify
> 2
delete> 2222
Ok
1) Add
2) Delete
3) Display
4) Modify
> 3
111
123
1) Add
2) Delete
3) Display
4) Modify
> 2
delete> 111
Ok
1) Add
2) Delete
3) Display
4) Modify
> 3
123
1) Add
2) Delete
3) Display
4) Modify
> ^C

makefile

CC=g++
CFLAGS=-g.

all:
	@$(MAKE) linkedlist
	@$(MAKE) queue
	@$(MAKE) stack

linkedlist:
	$(CC) linkedlist.cpp -o linkedlist

queue:
	$(CC) queue.cpp -o queue

stack:
	$(CC) stack.cpp -o stack

clean:
	rm linkedlist queue stack

queue.cpp

#define MAIN

#include <iostream>
#include "linkedlist.cpp"

using namespace std;

class Queue : protected DLL {
public:
  Node *push() {
    return this->append();
  }

  Node pop() {
    if (!this->empty) {
      Node t = *(this->here);
      if (this->del()) {
        return t;
      }
    }
    else {
      return Node{.data = "empty"};
    }
  }

  Node *front() {
    if (!this->empty) {
      while (!this->empty && this->here->next) {
        this->next();
      }
      return this->here;
    } else {
      return new Node{.data = "empty"};
    }
  }

  void purge() {
    scrollBack();
    while(this->here->next && this->del()) {
      
    }
  }
};

int main() {
  Queue queue;
  while (true) {
    cout << "1) Enqueue\n"
            "2) Dequeue\n"
            "3) Front\n"
            "4) Purge\n"
            "5) Exit\n";
    
    int cmd = -1;
    cout << "> ";
    cin >> cmd;

    switch (cmd) {
      case 1:
        cout << "enqueue> ";
        cin >> queue.push()->data;
        break;
      case 2:
        cout << queue.pop().data << endl;
        break;
      case 3:
        cout << queue.front()->data << endl;
        break;
      case 4:
        queue.purge();
        break;
      case 5:
        exit(0);
        break;
      default:
        cerr << "Select a command" << endl;
    }
  }
  return 0;
}

queue.output

./queue
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 1
enqueue> 123
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 2
123
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 2
empty
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 1
enqueue> 234
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 3
234
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 2
234
1) Enqueue
2) Dequeue
3) Front
4) Purge
5) Exit
> 3
empty

stack.cpp

#define MAIN

#include <iostream>
#include "linkedlist.cpp"

using namespace std;

class Stack : public DLL {
public:
  Node *push() {
    return this->appendBack();
  }

  Node pop() {
    if (!this->empty) {
      Node t = *(this->here);
      if (this->del()) {
        return t;
      }
    }
    else {
      return Node{.data = "empty"};
    }
  }

  Node *front() {
    /* while (this->here->last && !this->empty) {
      this->next();
    } */
    this->scrollBack();
    return this->here;
  }

  void purge() {
    scrollBack();
    while(this->here->next && this->del()) {
      
    }
  }
};

int main() {
  Stack stack;
  while (true) {
    cout << "1) Push\n"
            "2) Pop\n"
            "3) Top\n"
            "4) Purge\n"
            "5) Exit\n";

    int cmd = -1;
    cout << "> ";
    cin >> cmd;

    switch (cmd) {
      case 1:
        cout << (stack.empty ? "1" : "0") << endl;
        cout << "push> ";
        cin >> stack.push()->data;
        break;
      case 2:
        cout << stack.pop().data << endl;
        break;
      case 3:
        cout << stack.front()->data << endl;
        break;
      case 4:
        stack.purge();
      case 5:
        exit(0);
      default:
        cerr << "Select a command" << endl;
    }
  }
  return 0;
}

stack.output

./stack 
1) Push
2) Pop
3) Top
4) Purge
5) Exit
> 1
1
push> 123
1) Push
2) Pop
3) Top
4) Purge
5) Exit
> 1
0
push> 234
1) Push
2) Pop
3) Top
4) Purge
5) Exit
> 3
234
1) Push
2) Pop
3) Top
4) Purge
5) Exit
> 2
234
1) Push
2) Pop
3) Top
4) Purge
5) Exit
> 3
123
1) Push
2) Pop
3) Top
4) Purge
5) Exit
> 4