Column.h

Go to the documentation of this file.

#ifndef CARMA_DBMS_COLUMN_H
#define CARMA_DBMS_COLUMN_H

#include <algorithm>
#include <string>
#include <sstream>
#include <map>
#include <math.h>
#include <vector>
#include "carma/util/ErrorException.h"
#include "carma/util/IllegalArgumentException.h"

namespace carma {
namespace dbms {


template < typename T >
class Column : public ::std::vector< T > {

public:

    Column(const std::string& name) {
        name_ = name;
    }

    virtual ~Column() {
    }

    std::string getName() const {return name_;}

    bool hasNulls() const {return ! nullIndices_.empty();}

    std::vector< unsigned > getNullIndices() const { return nullIndices_; }

    void push_back_null() {
        this->push_back(nullValue_);
        nullIndices_.push_back(this->size()-1);
    }

    void setNullValue(const T& nullValue) {
        nullValue_ = nullValue;
        for(::size_t i = 0; i < nullIndices_.size(); i++) {
            (*this)[nullIndices_[i]] = nullValue_;
        }
    }


    inline T getNullValue() const {return nullValue_;}

    std::string toString() const {
        std::ostringstream ss;
        unsigned int nullPos = 0;
        //for (int i=0; i<data_.size(); i++) {
        for (::size_t i=0; i<this->size(); i++) {
            if(nullPos < nullIndices_.size() && i == nullIndices_[nullPos]) {
                ss << "NULL";
                nullPos++;
            } else {
                //ss << data_[i];
                ss << (*this)[i];
            }
            ss << " ";
        }
        return ss.str();
    }

    // FIXME brain dead search algorithm which needs to be improved
    // would probably be OK in most cases though since in CARMA we expect
    // not to have many nulls in our columns. Ultimately, we probably want a binary
    // search algorithm
    bool isElementNull(unsigned index) const {
        if(index >= this->size()) {
            std::ostringstream emsg;
            emsg << "Requested index " << index << " is >= number of elements "
                 << "which is " << this->size();
            throw CARMA_EXCEPTION(carma::util::IllegalArgumentException,
                                  emsg.str());
        }
        std::vector< unsigned >::const_iterator iter;
        for(iter=nullIndices_.begin(); iter!=nullIndices_.end(); iter++) {
            if(*iter == index) {
                return true;
            } else if (*iter > index) {
                // take advantage of the fact that nullIndices_ is sorted in
                // ascending order
                return false;
            }
        }
        return false;
    }

    T sum() const {
        T sum=0;
        for(::size_t i=0; i<this->size(); i++) {
            if(!isElementNull(i)) {
                //sum += data_[i];
                sum += (*this)[i];
            }
        }
        return sum;
    }

    T mean() const {
        //return sum/(data_.size()-nullIndices_.size());
        return sum()/(this->size()-nullIndices_.size());
    }

    T max() const {
        T max;
        // get the first non-null value as the initial test value
        for(int i=0; i<this->size(); i++) {
            if(!isElementNull(i)) {
                max = (*this)[i];
                break;
            }
        }
        for(int i=0; i<this->size(); i++) {
            if(!isElementNull(i)) {
                max = std::max((*this)[i],max);
            }
        }
        return max;
    }


    T min() const {
        T min;
        for(int i=0; i<this->size(); i++) {
            if(!isElementNull(i)) {
                min = (*this)[i];
                break;
            }
        }
        for(int i=0; i<this->size(); i++) {
            if(!isElementNull(i)) {
                min = std::min((*this)[i],min);
            }
        }
        return min;
    }

    int indexOf(const T& value) const {
        typename Column<T>::const_iterator iter;
        unsigned count = 0;
        std::vector< unsigned >::const_iterator niter = nullIndices_.begin();
        bool elementIsNull = false;
        bool hasNulls = !nullIndices_.empty();
        for(iter = this->begin(); iter != this->end(); iter++) {
            // takes advantage of the fact that nullIndices_ is sorted
            if(hasNulls) {
                while(niter != nullIndices_.end() && *niter < count) {
                    niter++;
                }
            }
            elementIsNull = (hasNulls) ? (*niter == count) : false;
            if(!elementIsNull && (*iter == value)) {
                return count;
            }
            count++;
        }
        return -1;
    }

    Column
    getDistinctValues( const ::std::string & name = "Distinct Values",
                       bool                  includeNull = true ) const;

protected:
    std::string name_;
    std::vector< unsigned > nullIndices_;
    T nullValue_;

    // prohibit use of the default constructor
    Column() {}

    class ValueMajorIndexMinorOrderingPred {
        private:
            const Column & c_;

        public:
            explicit ValueMajorIndexMinorOrderingPred( const Column & c );

            bool operator()( const size_t rhsIndex,
                             const size_t lhsIndex ) const;
    };
};


 template <typename T, typename U>
     std::map<T,U> columnsToMap(const carma::dbms::Column<T>& keyColumn,
                                const carma::dbms::Column<U>& valueColumn) {
     std::ostringstream emsg;
     if(keyColumn.size() != valueColumn.size()) {
         emsg << "The key column has " << keyColumn.size() << " elements "
              << "while the value column has " << valueColumn.size()
              << " elements. This method can only be run on columns of the "
              << "same size.";
         throw CARMA_EXCEPTION(carma::util::IllegalArgumentException,
                               emsg.str());
     }
     if(keyColumn.hasNulls()) {
         emsg << "The key column has NULL values. Both columns must not "
              << " have NULLS";
         throw CARMA_EXCEPTION(carma::util::IllegalArgumentException,
                               emsg.str());
     }
     if(valueColumn.hasNulls()) {
         emsg << "The value column has NULL values. Both columns must not "
              << " have NULLS";
         throw CARMA_EXCEPTION(carma::util::IllegalArgumentException,
                               emsg.str());
     }
     if(keyColumn.size() != keyColumn.getDistinctValues().size()) {
         emsg << "Some of the key column's values are not distinct. In order "
              << "for the mapping to work, all of this column's elements "
              << "must be unique";
         throw CARMA_EXCEPTION(carma::util::IllegalArgumentException,
                               emsg.str());
     }
     typename Column<T>::const_iterator iter = keyColumn.begin();
     typename Column<U>::const_iterator niter = valueColumn.begin();
     std::map<T,U> mapping;
     for ( ; iter != keyColumn.end(); iter++) {
         mapping[*iter] = *niter;
         niter++;
     }
     return mapping;
 };

}}
 template <typename T> std::ostream& operator<<
     (std::ostream &os, const carma::dbms::Column<T> &column) {
     os << column.toString();
     return os;
 }


template < typename T >
inline
carma::dbms::Column< T >::
ValueMajorIndexMinorOrderingPred::ValueMajorIndexMinorOrderingPred(
    const Column & c ) :
c_( c )
{
}


template < typename T >
inline bool
carma::dbms::Column< T >::
ValueMajorIndexMinorOrderingPred::operator()(
    const size_t rhsIndex,
    const size_t lhsIndex ) const
{
    if ( c_[ rhsIndex ] == c_[ lhsIndex ] )
        return (rhsIndex < lhsIndex);
    else
        return (c_[ rhsIndex ] < c_[ lhsIndex ]);
}


template < typename T >
carma::dbms::Column< T >
carma::dbms::Column< T >::getDistinctValues(
    const ::std::string & name,
    const bool            includeNull ) const
{
    const size_t mySize = this->size();

    // Get a guaranteed sorted vector of null value indices with no duplicates
    // Note that it could still have indices greater than or equal to mySize!
    ::std::vector< unsigned > localNullIndices = nullIndices_;
    if ( localNullIndices.empty() == false ) {
        stable_sort( localNullIndices.begin(), localNullIndices.end() );

        ::std::vector< unsigned >::iterator eraseBegin =
            unique( localNullIndices.begin(), localNullIndices.end() );

        if ( eraseBegin != localNullIndices.end() )
            localNullIndices.erase( eraseBegin, localNullIndices.end() );
    }

    // Get the vector of non-null indices
    ::std::vector< unsigned > nonNullIndices;
    {
        if ( localNullIndices.size() < mySize )
            nonNullIndices.reserve( mySize - localNullIndices.size() );

        ::std::vector< unsigned >::const_iterator k =
            localNullIndices.begin();

        const ::std::vector< unsigned >::const_iterator kEnd =
            localNullIndices.end();

        for ( unsigned i = 0; i < mySize; ++i ) {
            if ( (k != kEnd) && (i == *k) )
                ++k;  // It's the next null valued index
            else
                nonNullIndices.push_back( i );
        }
    }

    if ( nonNullIndices.empty() == false ) {
        // Sort the non-null indices by value and, more importantly,
        // by index for equal values
        {
            const ValueMajorIndexMinorOrderingPred orderingPred( *this );

            stable_sort( nonNullIndices.begin(),
                         nonNullIndices.end(),
                         orderingPred );
        }

        // Throw away all but the first index for each distinct non-null value
        {
            ::std::vector< unsigned > firstIndexForNonNullValue;
            firstIndexForNonNullValue.reserve( nonNullIndices.size() );

            ::std::vector< unsigned >::const_iterator j =
                nonNullIndices.begin();

            const ::std::vector< unsigned >::const_iterator jEnd =
                nonNullIndices.end();

            // First element is always a first index for a non-null value
            firstIndexForNonNullValue.push_back( *j );
            ::std::vector< unsigned >::const_iterator k = j;
            ++j;

            for ( ; j != jEnd; ++j ) {
                if ( ((*this)[*j]) == ((*this)[*k]) )
                    continue;

                // New distinct value
                firstIndexForNonNullValue.push_back( *j );
                k = j;
            }

            nonNullIndices.swap( firstIndexForNonNullValue );
        }

        // Sort the first indices that are left
        stable_sort( nonNullIndices.begin(), nonNullIndices.end() );
    }

    // Produce the final result
    Column distinct( name );

    const size_t distinctCount =
        ((includeNull && (localNullIndices.empty() == false)) ? 1 : 0) +
        nonNullIndices.size();

    if ( distinctCount != 0 ) {
        distinct.reserve( distinctCount );

        const ::std::vector< unsigned >::const_iterator kBegin =
            localNullIndices.begin();

        const ::std::vector< unsigned >::const_iterator kEnd =
            localNullIndices.end();

        ::std::vector< unsigned >::const_iterator k = kBegin;

        ::std::vector< unsigned >::const_iterator j =
            nonNullIndices.begin();

        const ::std::vector< unsigned >::const_iterator jEnd =
            nonNullIndices.end();

        for ( unsigned i = 0; i < mySize; ++i ) {
            if ( (k != kEnd) && (i == *k) ) {
                if ( includeNull && (k == kBegin) )
                    distinct.push_back_null();
                ++k;
            } else if ( (j != jEnd) && (i == *j) ) {
                ++j;
                distinct.push_back( (*this)[i] );
            }
        }
    }

    return distinct;
}


#endif // CARMA_DBMS_COLUMN_H