123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211 |
- #include <iostream>
- #include <cassert>
- #include <cstdlib>
-
- using namespace std;
-
- typedef int ElementType;
-
-
- class ArrayList {
- private:
- ElementType *A;
- int length;
- int allocationSize;
-
- void resize(int newAllocationSize);
-
- public:
- ArrayList(int allocSize = 4);
- void append(ElementType val);
- void prepend(ElementType val);
- void insertAfter(int idx, ElementType val);
- int search(ElementType key) const;
- void removeAt(int idx);
-
- void display(ostream &out) const;
-
- void operator=(const ArrayList& L);
- ~ArrayList();
- ArrayList(const ArrayList& L);
-
-
- };
-
- ostream& operator<<(ostream &out, const ArrayList &AL);
-
- // Constructor. The allocsize parameter has a default value of 4.
- ArrayList::ArrayList(int allocSize): allocationSize(allocSize) {
- A = new ElementType[allocationSize];
- length = 0;
- }
-
- // resize(): changes the capacity of the dynamic array to the
- // specified allocationSize.
-
- void ArrayList::resize(int newAllocationSize) {
- int *newA = new ElementType[newAllocationSize];
-
- for (int i = 0; i < length && i < newAllocationSize; i++)
- newA[i] = A[i];
-
- delete A;
- A = newA;
- allocationSize = newAllocationSize;
- length = min(allocationSize, length);
- }
-
-
- // append(): given val, inserts it at the end of the list
-
- void ArrayList::append(ElementType val) {
- if (length == allocationSize -1)
- resize(allocationSize * 2);
-
- A[length] = val;
- length++;
- }
-
-
- // append(): given val, inserts it at the start of the list
-
- void ArrayList::prepend(ElementType val) {
- if (length == allocationSize -1)
- resize(allocationSize * 2);
-
- for (int i = length; i > 0; i--)
- A[i] = A[i-1];
-
- A[0] = val;
- length++;
- }
-
- // insertAfter(): given val inserts it after the index provided
- // idx = -1 means the same as prepend.
-
- void ArrayList::insertAfter(int idx, ElementType val) {
- if (idx < -1 || idx >= length)
- cout << "Invalid index for insertion: " << idx << endl;
- else {
- if (length == allocationSize -1)
- resize(allocationSize * 2);
-
- for (int i = length; i > idx + 1; i--)
- A[i] = A[i-1];
-
- A[idx+1] = val;
- length++;
- }
- }
-
- // search() : given a key, linear search through the list
-
- int ArrayList::search(ElementType key) const {
- for (int i = 0; i < length; i++) {
- if (A[i] == key) return i;
- }
- return -1;
- }
-
- // removeAt(): given idx, remove that element at that position
-
- void ArrayList::removeAt(int idx) {
- if (idx < 0 || idx >= length)
- cout << "Invalid index in removeAt: " << idx << endl;
- else {
- for (int i = idx; i < length - 1; i++)
- A[i] = A[i + 1];
-
- length--;
- }
- }
-
- // display(): helper function for display the contents of the list
-
- void ArrayList::display(ostream &out) const{
- for (int i = 0; i < length; i++)
- cout << A[i] << " ";
- }
-
- // Overload of the operator<<, so that cout << L works!
-
- ostream& operator<<(ostream &out, const ArrayList &AL) {
- AL.display(out);
- return out;
- }
-
- // Overload of the assignment operator.
-
- void ArrayList::operator=(const ArrayList& L) {
- if (this != &L) {
- length = L.length;
- allocationSize = L.allocationSize;
- delete [] A;
- A = new int[allocationSize];
- for (int i = 0; i < length; i++) {
- A[i] = L.A[i];
- }
- }
- }
-
- // Destructor
-
- ArrayList::~ArrayList(){
- delete [] A;
- }
-
- // Overload of the copy constructor.
-
- ArrayList::ArrayList(const ArrayList& L){
- if (this == &L) {
- length = 0;
- allocationSize = 4;
- A = new int[allocationSize];
- }
- else {
- length = L.length;
- allocationSize = L.allocationSize;
- A = new int[allocationSize];
- for (int i = 0; i < length; i++) {
- A[i] = L.A[i];
- }
- }
- }
-
-
-
-
- // The client provides an interface to run the various list functions.
- // -- a is append, e.g. a 15 : appends a 15 to the list
- // -- i is insertAfter, e.g. i 0 20: inserts a 20 after position 0
- // -- r is erase, e.g. r 4 removes the element at position 4.
-
- int main() {
-
- int position, element;
- ArrayList L;
- string inst;
-
- cout << "$ ";
- while (cin >> inst && inst != "q") {
- if (inst == "a") {
- cin >> element;
- cout << "Appending " << element << endl;
- L.append(element);
- }
- else if (inst == "i") {
- cin >> position;
- cin >> element;
- cout << "Inserting " << element << endl;
- L.insertAfter(position,element);
- }
- else if (inst == "r") {
- cin >> position;
- cout << "Erasing element after position " << position << endl;
- L.removeAt(position);
- }
- else if (inst == "d") cout << L << endl;
- cout << "$ ";
- }
- return 0;
- }
|