SampleLintList

.SampleLintList.md

"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

Dockerfile

# 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"]

sample-list-tests.cpp

/**
 * `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;
}

sample-list.cpp

/**
 * "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;
  }
};