sortedArray.hpp

#pragma once
#ifndef SORTEDARRAY_H_INCLUDED
#define SORTEDARRAY_H_INCLUDED
 
#include "array.hpp"
 
namespace z {
namespace core {
template <typename T>
class sortedArray : public array<T> {
public:
    sortedArray() {}
 
    template <typename... Args>
    sortedArray(const T &arg1, const Args &...args) {
        this->init(arg1, args...);
    }
 
    virtual int add(const T &object) override;
 
    virtual int find(const T &object) const override;
 
    virtual int findInsert(const T &object, bool allowDuplicates = true) const;
 
    // For sorted arrays, shuffle does nothing.
    virtual void shuffle() noexcept override {}
 
    // For sorted arrays, reverse does nothing.
    virtual void reverse() noexcept override {}
};
 
template <typename T>
int sortedArray<T>::add(const T &object) {
    int index = findInsert(object);
 
    this->insert(object, index);
 
    return index;
}
 
template <typename T>
int sortedArray<T>::find(const T &object) const {
    if (this->array_data.size() == 0) {
        return -1;
    }
 
    int left = 0;
    int right = this->array_data.size() - 1;
 
    while (left < right) {
        int center = (left + right) / 2;
 
        if (this->lt(this->array_data.at(center), object)) {
            left = center + 1;
        } else if (this->gt(this->array_data.at(center), object)) {
            right = center - 1;
        } else {
            return center;
        }
    }
 
    if (this->eq(this->array_data.at(left), object)) {
        return left;
    } else {
        return -1;
    }
}
 
template <typename T>
int sortedArray<T>::findInsert(const T &object, bool allowDuplicates) const {
    if (this->array_data.size() == 0) {
        return 0;
    }
 
    int left = 0;
    int right = this->array_data.size() - 1;
 
    while (left < right) {
        int center = (left + right) / 2;
 
        if (this->lt(this->array_data.at(center), object)) {
            left = center + 1;
        } else if (this->gt(this->array_data.at(center), object)) {
            right = center - 1;
        } else {
            return allowDuplicates ? center : -1;
        }
    }
 
    if (this->lt(this->array_data.at(left), object)) {
        return left + 1;
    } else if (allowDuplicates || !this->eq(this->array_data.at(left), object)) {
        return left;
    } else {
        return -1;
    }
}
 
} // namespace core
} // namespace z
 
#endif // SORTEDARRAY_H_INCLUDED