Dynamic Array Bags

Question

For one of my assignments, we were asked to create a data structure similar to Bags using dynamic arrays where the order would be important - which I was able to do successfully, that is, the code that follows works fine. We now have to optimize the code according to the memory usage and timing.

One of the functions that I know isn't optimized is my INSERT() function, I would appreciate any suggestion to help optimize this and any other function.

Here are the files should you not want to copy and paste.

sequence.h:

#ifndef SEQUENCE_SEQUENCE_H
#define SEQUENCE_SEQUENCE_H
#include<iostream>

namespace sqc {
 class sequence {
 public:
    sequence(int newSize = DEFAULT_CAPACITY);

    int find_empty();
    void erase_first(int n);
    void erase_last(int n);
    void erase_occurence(int occur, int num);
    void erase_from(int index);
    void insert(int n);
    void insert_at(int n, int in);
    void insert_first(int n);
    int count(int n);
    int size();
    friend sequence operator+(const sequence& ss, const sequence& s);
    friend sequence operator+(const sequence& s, const int& n);
    sequence& operator+=(const sequence& s);
    sequence& operator+=(const int& n);
    void operator=(const sequence& s);
    bool operator==(const sequence& s);
    friend std::ostream& operator <<(std::ostream& os, const sequence& s);
    friend std::istream& operator >> (std::istream& is, sequence& s);   
private:
    static const int DEFAULT_CAPACITY = 5;
    int seqSize;
    int *data;
    bool *used;
};
}
#endif

sequence.cpp:

#include<iostream>
#include "sequence.h"
using namespace sqc;
// C O N S T R U C T O R
sequence::sequence(int newSize) {
    seqSize = newSize;
    data = new int[newSize];
    used = new bool[newSize];
    for (int i = 0; i < newSize; i++) {
        used[i] = false;
    }
}

//FIND_EMPTY
//Returns location of the last empty location
//[NULL] [VALUE] [NULL] [NULL]
//.................^...........
//.................|...........Returns this location
int sequence::find_empty() {
    int trueCount = 0;
    for (int i = 0; i < seqSize-1; i++) {
        if (used[i]==true){
           trueCount++;
           for (int j=i;j < seqSize-1; j++){
                if (used[i] == false) {
                    return i;
                }
                else {
                    trueCount++;
                }
           }
        if (trueCount == seqSize) return seqSize+1;
        }
    }
}

/*void resizeData() {
    data = new int[seqSize + (seqSize / 2)];
    int newSize = seqSize + (seqSize / 2);
    seqSize = newSize;
}*/

//ERASE_FIRST
//Input Integer <Value>
//Deletes the first occurence of the given value
void sequence::erase_first(int n) {
    for (int i = 0; i < seqSize; ++i) {
        if (n == data[i]) {
            for (int j = i; j < seqSize; ++j) {
                data[j] = data[j + 1];
            }
            int *newData = new int[seqSize - 1];
            for (int k = 0; k < seqSize - 1; k++) {
                newData[k] = data[k];
            }
            delete[] data;
            data = newData;
            seqSize = seqSize - 1;
            break;
        }
    }
}

//ERASE_LAST
//Input Integer <Value>
//Deletes the last occurence of the given value
void sequence::erase_last(int n) {
    for (int i = seqSize; i > 0; --i) {
        if (n == data[i]) {
            for (int j = i; j < seqSize; ++j) {
                data[j] = data[j + 1];
            }
            int *newData = new int[seqSize - 1];
            for (int k = 0; k < seqSize - 1; k++) {
                newData[k] = data[k];
            }
            delete[] data;
            data = newData;
            seqSize = seqSize - 1;
            break;
        }
    }
}

//ERASE_OCCURENCE
//Input: Integer <Occurence>, Integer <Value>
//Deletes the specified occurence of the given value from the array
void sequence::erase_occurence(int occur, int num) {
    int occurCount = 0;
    for (int i = 0; i < seqSize; ++i) {
        if (num = data[i]) {
            occurCount++;
        }
        if (occurCount == occur) {
            for (int j = i; j < seqSize; ++j) {
                data[j] = data[j + 1];
            }
            int *newData = new int[seqSize - 1];
            for (int k = 0; k < seqSize - 1; k++) {
                newData[k] = data[k];
            }
            delete[] data;
            data = newData;
            seqSize = seqSize - 1;
            break;
        }
    }
}

//ERASE_FROM
//Input: Integer <Index>
//Deletes value from given index
void sequence::erase_from(int index) {
    for (int j = index; j < seqSize; ++j) {
        data[j] = data[j + 1];
    }
    int *newData = new int[seqSize - 1];
    for (int k = 0; k < seqSize - 1; k++) {
        newData[k] = data[k];
    }
    delete[] data;
    data = newData;
    seqSize = seqSize - 1;
}

//INSERT
//Input: Integer <Value>
//Inserts the value to the end of the array
void sequence::insert(int n) {
    if (find_empty() > seqSize) {
        int newSize = seqSize + (seqSize/2);
        int *newData = new (std::nothrow) int[newSize];
        for (int i = 0; i < seqSize-1; ++i) {
            newData[i] = data[i];
        }
        newData[seqSize] = n;
        delete[] data;
        data = newData;
        seqSize = newSize;
        bool *newUsed = new bool[seqSize + (seqSize / 2)];
        for (int i = 0; i < seqSize; ++i) {
            newUsed[i] = used[i];
        }
        for (int j = 0; j < newSize - seqSize; ++j) {
            newUsed[j] = false;
        }
        delete[] used;
        used = newUsed;
    }
    else {
        int index = find_empty();
        data[index] = n;
    }
}

//INSERT_AT
//Input: Integer <Value>, Integer <Index>
//Inserts value to the specified index, all following values are shifted
void sequence::insert_at(int n, int in) {
    int *newData = new (std::nothrow) int[seqSize + 1];
    int newSize = seqSize + 1;
    for (int i = 0; i < in; ++i) {
        if (in > seqSize + 1) {
            std::cout << "Invalid index, max index is size + 1.";
            break;
        }
        newData[i] = data[i];
    }
    newData[in] = n;
    for (int i = newSize; i > in + 1; --i) {
        newData[i] = data[i - 1];
    }
    delete[] data;
    data = newData;
    seqSize = newSize;
}

//INSERT_FIRST
//Input: Integer <Value>
//Inserts value to the beginning of the array, all following values are shifted
void sequence::insert_first(int n) {
    int *newData = new (std::nothrow) int[seqSize + 1];
    int newSize = seqSize + 1;
    for (int i = seqSize; i > 0; i--) {
        newData[i + 1] = data[i];
    }
    newData[0] = n;
    delete[] data;
    data = newData;
    seqSize = newSize;
}

//COUNT
//Input: Integer <Value>
//Returns the number of times the value occurs in the array
int sequence::count(int n) {
    int occur = 0;
    for (int i = 0; i < seqSize; i++) {
        if (data[i] == n) occur++;
    }
    return occur;
}

//SIZE
//*NO INPUT*
//Returns size of the array
int sequence::size() {
    return seqSize;
}

//[NON-MEMBER FUNCTION] <SEQUENCE> + <SEQUENCE>
//Returns new sequence containing all values from both sequences and of the combined size
sequence sqc::operator+(const sequence& ss, const sequence& s) {
    sequence toReturn;
    int *newData = new (std::nothrow) int[s.seqSize + ss.seqSize];
    int newSize = s.seqSize + ss.seqSize;
    int index = 0;
    for (index; index < ss.seqSize; ++index) {
        newData[index] = ss.data[index];
    }
    for (int i = 0; i < s.seqSize; i++) {
        newData[index + i] = s.data[i];
    }
    delete[] toReturn.data;
    toReturn.data = newData;
    toReturn.seqSize = newSize;
    return toReturn;
}

//[NON-MEMBER FUNCTION] <SEQUENCE> + <INT>
//Returns new sequence containing all values from the 
//sequence with the integer as the last value of the array
sequence sqc::operator+(const sequence& s,const int& n) {
    sequence toReturn;
    int *newData = new (std::nothrow) int[s.seqSize + 1];
    int newSize = s.seqSize + 1;
    for (int i = 0; i < s.seqSize; ++i) {
        newData[i] = s.data[i];
    }
    newData[newSize - 1] = n;
    delete[] toReturn.data;
    toReturn.data = newData;
    toReturn.seqSize = newSize;
    return toReturn;
}

// <SEQUENCE> += <SEQUENCE>
//Re-constructs the first sequence such that it contains all values from both sequences and of the combined size
 sequence& sequence::operator+=(const sequence& s) {
    int *newData = new (std::nothrow) int[s.seqSize + seqSize];
    int newSize = s.seqSize + seqSize;
    int index = 0;
    for (index; index < seqSize; ++index) {
        newData[index] = data[index];
    }
    for (int i = 0; i < s.seqSize; i++) {
        newData[index + i] = s.data[i];
    }
    delete[] data;
    data = newData;
    seqSize = newSize;
    return *this;
}

// <SEQUENCE> += <INT>
// Re-constructs the first sequence such that it contains the integer as its last value
sequence& sequence::operator+=(const int& n) {
    int *newData = new (std::nothrow) int[seqSize + 1];
    int newSize = seqSize + 1;
    for (int i = 0; i < seqSize; ++i) {
        newData[i] = data[i];
    }
    newData[newSize - 1] = n;
    delete[] data;
    data = newData;
    seqSize = newSize;
    return *this;
}

// <SEQUENCE> = <SEQUENCE>
// Sets the left hand side sequence's attributes to be equal to that of the right hand side sequence
void sequence::operator=(const sequence& s) {
    delete[] data;
    data = s.data;
    seqSize = s.seqSize;
}

// <SEQUENCE> == <SEQUENCE>
// Returns true if the size and ALL elements of the two sequences are identical
// Else, returns false
bool sequence::operator==(const sequence& s) {
    if (seqSize == s.seqSize) {
        int trueCount = 0;
        for (int i = 0; i < seqSize; i++) {
            if (data[i] == s.data[i]) {
                trueCount++;
            }
        }
        if (trueCount == seqSize) {
            return true;
        }
        else {
            return false;
        }
    }
}

//OSTREAM OPERATOR : USED TO PRINT ALL VALUES CONTAINED IN A SEQUENCE
std::ostream& sqc::operator <<(std::ostream& os, const sequence& s) {
    for (int i = 0; i < s.seqSize; i++) {
        os << s.data[i] << "\t";
    }
    return os;
}

//ISTREAM OPERATOR : USED TO ASSIGN VALUES TO A SEQUENCE IN BULK
std::istream& sqc::operator >> (std::istream& is, sequence& s) {
    for (int i = 0; i < s.seqSize; i++) {
        is >> s.data[i];
        s.used[i] = true;
    }
    return is;
}

main.cpp:

#include <iostream>
#include "sequence.h"

using namespace sqc;

int main() {
sequence s1(2);
std::cout << s1 << std::endl;
s1.erase_from(0);
std::cout << s1 << std::endl;
s1.insert_at(2, 1);
std::cout << s1 << std::endl;
s1.insert(3);
std::cout << s1 << std::endl;
s1.insert_first(1);
std::cout << s1 << std::endl;

sequence s2(2);
std::cout << s2 << std::endl;

std::cout << s1 + s2 << std::endl;
std::cout << s1 + 9 << std::endl;

s1 += s2;
std::cout << s1 << std::endl;

s1 = s2;
std::cout << s1 << std::endl;

if (s1 == s2) {
    std::cout << "s1 == s2" << std::endl;
}
else {
    std::cout << "not equal" << std::endl;
}

std::cin >> s1;
std::cout << s1 << std::endl;

return 0;
}

Answer 1

I think you find_empty routine is buggy. Also it will always return the first empty location after the first nonempty one. As an example look at [Null] [Value] [Null] [Value] [Null], which is not the last empty location. Also from the name find empty I would expect it to return the first empty slot it finds. So if you really want the first empty spot behind the first nonempty you have to traverse from the back. Also you are inconsistent in your return value. If you found an unused value, you return i, but if you did not found one then you return seqSize+1, which is off by one

//FIND_EMPTY
//Returns location of the last empty location
//[NULL] [VALUE] [NULL] [NULL]
//.................^...........
//.................|...........Returns this location
int sequence::find_empty() {
    int trueCount = 0;
    // Bail early if the last element is used
    if (used[seqSize-1]) {
        return seqSize;
    }
    for (int i = seqSize-2; i >= 0; --i) {
        if (used[i]==true) {
           return i+1;
        }
    }
    return 0;
}

---

Try to reuse your work. For example insert_first(value) should be equal to insert_at(0, value)

//INSERT_FIRST
//Input: Integer <Value>
//Inserts value to the beginning of the array, all following values are shifted
void sequence::insert_first(int value) {
    insert_at(0, value);
}

---

What is the actual purpose of bool used? Generally i would expect that it tells me whether the data at position used[i] is valid. So a function like erase_from() should simply set the boolean to false and not tamper with the data. Also your code contains an invalid memory access here

for (int j = index; j < seqSize; ++j) {
        data[j] = data[j + 1];
}

As this will access data[seqSize] which is not valid. A similar error is in erase_last()

for (int i = seqSize; i > 0; --i) {
        if (n == data[i]) {

You access data out off bounds. In any case if you want to improve your code you should have a look at http://www.cplusplus.com/reference/cstdlib/realloc/ . This should considerably simplify your code. What actually worst about all your erase function is that they do not modify the used data completely invalidating your logic

As you need this all the time so you should utilize erase_from for this

//ERASE_FROM
//Input: Integer <Index>
//Deletes value from given index
void sequence::erase_from(int index) {
    for (int j = index; j < seqSize-1; ++j) {
        data[j] = data[j + 1];
        used[j] = used[j + 1];
    }
    seqSize--;
    data = (int*)  realloc (data, seqSize * sizeof(int));
    used = (bool*) realloc (used, seqSize * sizeof(bool));
}

//ERASE_FIRST
//Input Integer <Value>
//Deletes the first occurence of the given value
void sequence::erase_first(int value) {
    for (int i = 0; i < seqSize; ++i) {
        if (value == data[i]) {
            erase_from(i);
            break;
        }
    }
}

//ERASE_LAST
//Input Integer <Value>
//Deletes the last occurence of the given value
void sequence::erase_last(int value) {
    for (int i = seqSize-1; i >= 0; --i) {
        if (value == data[i]) {
            erase_from(i);
            break; 
        }
    }
}

//ERASE_OCCURENCE
//Input: Integer <Occurence>, Integer <Value>
//Deletes the specified occurence of the given value from the array
void sequence::erase_occurence(int occur, int value) {
    int occurCount = 0;
    for (int i = 0; i < seqSize; ++i) {
        if (value = data[i]) {
            occurCount++;
        }
        if (occurCount == occur) {
            erase_from(i);
            break; 
        }
    }
}

Also generally you should really check whether the memory allocation succeeded. Have a look here http://www.cplusplus.com/reference/new/bad_alloc/

---

Your insert function is bogus too. When reassigning the used values, you overwrite the old ones here for (int j = 0; j < newSize - seqSize; ++j). This should start at seqSize+1. Similarly your insert function can benefit from realloc

//INSERT
//Input: Integer <Value>
//Inserts the value to the end of the array
void sequence::insert(int value) {
    if (find_empty() >= seqSize) {
        int oldSize = seqSize;
        seqSize += seqSize/2;
        data = (int*)  realloc (data, seqSize * sizeof(int));
        used = (bool*) realloc (used, seqSize * sizeof(bool));
        data[oldSize] = value;
        used[oldSize] = true;
        for (int j = oldSize+1; j < seqSize; ++j) {
            used[j] = false;
        }
    }
    else {
        data[find_empty()] = value;
    }
}

//INSERT_AT
//Input: Integer <Value>, Integer <Index>
//Inserts value to the specified index, all following values are shifted
void sequence::insert_at(int value, int index) {
    if (index >= seqSize) {
        std::cout << "Invalid index, max index is seqSize: " << seqSize << "\n";
    }
    seqSize++;
    data = (int*)  realloc (data, seqSize * sizeof(int));
    used = (bool*) realloc (used, seqSize * sizeof(bool));
    for (int i = index + 1; i < seqSize; ++i) {
        data[i] = data[i-1];
        used[i] = used[i-1];
    }
    data[index] = value;
    used[index] = true; 
}