Skip to content

Instantly share code, notes, and snippets.

@matteocng
Last active August 19, 2018 11:04
Show Gist options
  • Save matteocng/7d37f39e252eeb72d0d35df7d42adaac to your computer and use it in GitHub Desktop.
Save matteocng/7d37f39e252eeb72d0d35df7d42adaac to your computer and use it in GitHub Desktop.
SampleLintList

"Low level" programming exercise: reproduce functionality of Java ArrayList using C style arrays and dynamic memory allocation. The list can be mutable and does not have to be polymorphic, it may contain only int. lambda functions introduced in C++ 11 may be used as "callbacks".

ArrayList Java documentation

# How to compile and run the tests:
# `docker build -t sample-intl-list-app . && docker run -it --rm sample-intl-list-app`
FROM gcc:4.9
COPY . /usr/src/app
WORKDIR /usr/src/app
RUN g++ -std=c++1y -o app sample-list-tests.cpp
CMD ["./app"]
/**
* `assert` tests for `SampleIntList`.
*
* @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.htm}
*/
#include <cassert>
#include "sample-list.cpp"
int numbers[] = {3000, 4000, 5000, 6000};
int numbersAlternate[] = {10000, 20000, 30000, 40000};
SampleIntList baseList;
void assertCsv(SampleIntList &sampleList, std::string csvExpected)
{
const std::string message = "Expected this csv: " + csvExpected + " but instead got: " + sampleList.toCsv() + ".";
const bool expectedTrue = sampleList.toCsv() == csvExpected;
if (!expectedTrue)
{
std::cout << message << std::endl;
}
assert(expectedTrue);
}
void prepare()
{
baseList = SampleIntList();
baseList.addAll(numbers, 4);
}
// Tests.
void test_init()
{
SampleIntList sampleList2 = SampleIntList();
}
void test_size()
{
SampleIntList sampleList = SampleIntList();
assertCsv(sampleList, "");
assert(sampleList.size() == 0);
}
void test_add()
{
SampleIntList sampleList = SampleIntList();
sampleList.add(34);
assertCsv(sampleList, "34");
assert(sampleList.size() == 1);
sampleList.add(1188);
assertCsv(sampleList, "34,1188");
assert(sampleList.size() == 2);
sampleList.add(6000);
assertCsv(sampleList, "34,1188,6000");
assert(sampleList.size() == 3);
sampleList.set(1, 5000);
assertCsv(sampleList, "34,5000,6000");
assert(sampleList.size() == 3);
sampleList.set(0, 3000);
assertCsv(sampleList, "3000,5000,6000");
assert(sampleList.size() == 3);
sampleList.add(4000, 1);
assertCsv(sampleList, "3000,4000,5000,6000");
assert(sampleList.size() == 4);
sampleList.add(100, sampleList.size());
assertCsv(sampleList, "3000,4000,5000,6000,100");
assert(sampleList.size() == 5);
try
{
sampleList.add(500, 50);
assert(false);
}
catch (std::exception e)
{
}
try
{
sampleList.add(500, 6);
assert(false);
}
catch (std::exception e)
{
}
try
{
sampleList.add(500, -1);
assert(false);
}
catch (std::exception e)
{
}
try
{
sampleList.add(500, sampleList.size() + 1);
assert(false);
}
catch (std::exception e)
{
}
}
void test_remove()
{
SampleIntList sampleList = baseList.clone();
sampleList.remove(5000);
assertCsv(sampleList, "3000,4000,6000");
assert(sampleList.size() == 3);
sampleList.remove(3000);
assertCsv(sampleList, "4000,6000");
assert(sampleList.size() == 2);
sampleList.remove(4000);
assertCsv(sampleList, "6000");
assert(sampleList.size() == 1);
sampleList.remove(6000);
assertCsv(sampleList, "");
assert(sampleList.size() == 0);
}
void test_get()
{
SampleIntList sampleList = baseList.clone();
assert(sampleList.get(2) == 5000);
try
{
sampleList.get(sampleList.size());
assert(false);
}
catch (std::exception e)
{
}
assert(sampleList.get(sampleList.size() - 1) == 6000);
}
void test_remove_at()
{
SampleIntList sampleList = baseList.clone();
sampleList.removeAt(2);
assertCsv(sampleList, "3000,4000,6000");
sampleList.removeAt(sampleList.size() - 1);
assertCsv(sampleList, "3000,4000");
sampleList.removeAt(0);
assertCsv(sampleList, "4000");
try
{
sampleList.removeAt(-1);
assert(false);
}
catch (std::exception e)
{
}
}
void test_add_all()
{
SampleIntList sampleList = baseList.clone();
SampleIntList sampleListTwo = SampleIntList();
sampleListTwo.addAll(&numbersAlternate[0], 4);
assertCsv(sampleListTwo, "10000,20000,30000,40000");
sampleList.addAll(sampleListTwo);
assertCsv(sampleList, "3000,4000,5000,6000,10000,20000,30000,40000");
sampleList.clear();
sampleList.addAll(&numbers[0], 4);
sampleList.addAll(2, sampleListTwo);
assertCsv(sampleList, "3000,4000,10000,20000,30000,40000,5000,6000");
try
{
sampleList.addAll(sampleList.size() + 1, sampleListTwo);
assert(false);
}
catch (std::exception e)
{
}
try
{
sampleList.addAll(-1, sampleListTwo);
assert(false);
}
catch (std::exception e)
{
}
}
void test_remove_all()
{
SampleIntList sampleList = baseList.clone();
SampleIntList sampleListTwo = SampleIntList();
sampleListTwo.add(3000);
sampleListTwo.add(5000);
sampleList.removeAll(sampleListTwo);
assertCsv(sampleList, "4000,6000");
SampleIntList sampleListThree = SampleIntList();
sampleListThree.add(4000);
sampleListThree.add(6000);
sampleListThree.removeAll(sampleList);
assert(sampleListThree.size() == 0);
}
void test_retain_all()
{
SampleIntList sampleList = baseList.clone();
SampleIntList sampleListTwo = SampleIntList();
sampleListTwo.add(3000);
sampleListTwo.add(5000);
const bool modified = sampleList.retainAll(sampleListTwo);
assert(modified);
assertCsv(sampleList, "3000,5000");
SampleIntList sampleListThree = baseList.clone();
const bool secondTimeModified = sampleList.retainAll(sampleListThree);
assert(secondTimeModified == false);
assertCsv(sampleListThree, baseList.toCsv());
}
void test_clear()
{
SampleIntList sampleList = baseList.clone();
assert(sampleList.size() == 4);
sampleList.clear();
assert(sampleList.size() == 0);
}
void test_clone()
{
SampleIntList sampleList = baseList.clone();
assertCsv(sampleList, "3000,4000,5000,6000");
SampleIntList cloneList = sampleList.clone();
assertCsv(cloneList, sampleList.toCsv());
}
void test_set()
{
SampleIntList sampleList = baseList.clone();
sampleList.set(2, 9000);
assert(sampleList.get(2) == 9000);
sampleList.set(0, 10);
assertCsv(sampleList, "10,4000,9000,6000");
}
void test_for_each()
{
SampleIntList sampleList = baseList.clone();
// Lambda expression.
// @see {@link https://en.cppreference.com/w/cpp/language/lambda}
std::function<int(int, int)> func([](int currentElement, int currentPosition) {
return currentElement == 3000 ? currentElement : 9000;
});
sampleList.forEach(func);
assertCsv(sampleList, "3000,9000,9000,9000");
std::function<int(int, int)> funcTwo([](int currentElement, int currentPosition) {
return currentElement;
});
sampleList.forEach(funcTwo);
assertCsv(sampleList, "3000,9000,9000,9000");
}
int main()
{
prepare();
test_init();
test_size();
test_add();
test_add_all();
test_clone();
test_get();
test_set();
test_remove();
test_remove_at();
test_remove_all();
test_retain_all();
test_for_each();
test_clear();
return 0;
}
/**
* "SampleIntlList".
*
* @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html}
*/
#include <iostream>
#include <string>
#include <functional>
struct SampleIntList
{
private:
int *pBuffer;
int countElements;
void init()
{
if (size() > 0)
{
throw std::invalid_argument(
"(init) Expected to be called on an empty list instead of a list with size: " +
std::to_string(size()) + ".");
}
pBuffer = (int *)calloc(1, sizeof(int));
}
void throwIfPositionIsOutOfBounds(int index, int upperInclusive = false) const
{
const int count = size();
int secondCondition = upperInclusive ? index >= count : index > count;
if (index < 0 || secondCondition)
{
const int lastIndex = count == 0 ? 0 : count - 1;
throw std::invalid_argument(
"Index " + std::to_string(index) + " is out of bounds (there are " +
std::to_string(count) + " elements, last index is " +
std::to_string(lastIndex) + ").");
}
}
// This is a placeholder for now, since we know the buffer can only contain
// int and every "+1" inside it contains an int.
int positionToBufferIndex(int index) const
{
return index;
}
public:
~SampleIntList()
{
if (size())
{
free(pBuffer);
}
pBuffer = NULL;
countElements = 0;
}
SampleIntList()
{
countElements = 0;
init();
}
// @todo Copy and move constructors.
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#size()}
int size() const
{
return countElements;
}
std::string toCsv() const
{
return join(",");
}
std::string join(std::string separator = "") const
{
if (size() == 0)
{
return "";
}
std::string csv;
for (int i = 0; i < size(); i++)
{
csv = csv + std::to_string(get(i)) + separator;
}
// Remove the last seoarator.
csv.pop_back();
return csv;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#get(int)}
int get(int position) const
{
throwIfPositionIsOutOfBounds(position, true);
int bufferIndex = positionToBufferIndex(position);
const int value = pBuffer[bufferIndex];
return value;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#isEmpty()}
bool isEmpty() const
{
return size() == 0;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#contains(java.lang.Object)}
bool contains(int element) const
{
bool contained = false;
for (int i = 0; i < size(); i++)
{
if (get(i) == element)
{
contained = true;
break;
}
}
return contained;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#clone()}
SampleIntList clone()
{
SampleIntList cloneList = SampleIntList();
cloneList.addAll(*this);
return cloneList;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#clear()}
void clear()
{
free(pBuffer);
pBuffer = NULL;
countElements = 0;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#set(int,E)}
void set(int position, int element)
{
throwIfPositionIsOutOfBounds(position, true);
int bufferIndex = positionToBufferIndex(position);
pBuffer[bufferIndex] = element;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#remove(int)}
bool remove(int element)
{
std::function<bool(int, int)> func([element](int currentElement, int currentPosition) {
return currentElement == element;
});
return removeIf(func);
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#forEach(java.util.function.Consumer)}
void forEach(std::function<int(int, int)> &callback)
{
for (int i = 0; i < size(); i++)
{
int currentElement = get(i);
const int maybeNewElement = callback(currentElement, i);
set(i, maybeNewElement);
}
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#removeIf(java.util.function.Predicate)}
bool removeIf(std::function<bool(int, int)> &callback)
{
if (size() == 0)
{
return false;
}
// The worst case is that we remove nothing, so we need a buffer of the same
// size as the current one.
int *pNewBuffer = (int *)calloc(size(), sizeof(int));
int positionNewBuffer = 0;
int elementsRemoved = 0;
for (int i = 0; i < size(); i++)
{
int currentElement = get(i);
const bool shouldRemove = callback(currentElement, i);
if (!shouldRemove)
{
int newBufferIndex = positionToBufferIndex(positionNewBuffer);
pNewBuffer[newBufferIndex] = currentElement;
positionNewBuffer = positionNewBuffer + 1;
}
else
{
elementsRemoved = elementsRemoved + 1;
}
}
countElements = countElements - elementsRemoved;
if (elementsRemoved)
{
free(pBuffer);
pBuffer = pNewBuffer;
}
return elementsRemoved;
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#remove(int)}
bool removeAt(int position)
{
throwIfPositionIsOutOfBounds(position, true);
std::function<bool(int, int)> func([position](int currentElement, int index) {
return index == position;
});
return removeIf(func);
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#retainAll(java.util.Collection)}
bool retainAll(SampleIntList &inputSampleIntList)
{
std::function<bool(int, int)> func([&inputSampleIntList](int currentElement, int index) {
return !inputSampleIntList.contains(currentElement);
});
return removeIf(func);
}
//@see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#removeAll(java.util.Collection)}
bool removeAll(SampleIntList &inputSampleIntList)
{
std::function<bool(int, int)> func([&inputSampleIntList](int currentElement, int index) {
return inputSampleIntList.contains(currentElement);
});
return removeIf(func);
}
void addAll(int *intList, int countListElements)
{
for (int i = 0; i < countListElements; i++)
{
add(intList[i]);
}
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#addAll(java.util.Collection)}
void addAll(SampleIntList &inputSampleIntList)
{
return addAll(size(), inputSampleIntList);
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#addAll(int,java.util.Collection)}
void addAll(int position, SampleIntList &inputSampleIntList)
{
int positionToAddNewElement = position;
throwIfPositionIsOutOfBounds(positionToAddNewElement);
for (int i = 0; i < inputSampleIntList.size(); i++)
{
int element = inputSampleIntList.get(i);
add(element, positionToAddNewElement);
positionToAddNewElement = positionToAddNewElement + 1;
}
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#add(E)}
void add(int element)
{
return add(element, size());
}
// @see {@link https://docs.oracle.com/javase/10/docs/api/java/util/ArrayList.html#add(int,E)}
void add(int element, int insertAtPosition)
{
throwIfPositionIsOutOfBounds(insertAtPosition, false);
int *pNewBuffer = (int *)calloc(sizeof(int), size() + 1);
if (size() == 0)
{
// No elements in the buffer. We set the first element in the new buffer to
// the provided element, no need to iterate on the current (empty) buffer.
pNewBuffer[0] = element;
}
else
{
// There are existing elements in the current buffer: copy them over to the
// new buffer in the correct positions.
int positionNewBuffer = 0;
for (int i = 0; i < size(); i++)
{
int currentBufferPosition = positionToBufferIndex(i);
positionNewBuffer = currentBufferPosition;
if (i < insertAtPosition)
{
int curElement = pBuffer[currentBufferPosition];
pNewBuffer[currentBufferPosition] = curElement;
}
else if (i == insertAtPosition)
{
pNewBuffer[currentBufferPosition] = element;
int currentBufferPositionNext = positionToBufferIndex(i + 1);
pNewBuffer[currentBufferPositionNext] = pBuffer[currentBufferPosition];
}
else if (i > insertAtPosition)
{
positionNewBuffer = positionToBufferIndex(i + 1);
pNewBuffer[positionNewBuffer] = pBuffer[currentBufferPosition];
}
}
// In this case we have to "append" at the end of the current buffer.
// The newly added element will be the last element.
if (insertAtPosition == size())
{
pNewBuffer[insertAtPosition] = element;
}
}
free(pBuffer);
pBuffer = pNewBuffer;
countElements = countElements + 1;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment