QSDK 1.1 Documentation

vector.h

Go to the documentation of this file.

/*-
 * Copyright (c) 1999-2003 Qube Software, Ltd.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * 1. Redistributions of the source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 
 * 2. Any redistribution solely in binary form must conspicuously
 *    reproduce the following disclaimer in documentation provided with the
 *    binary redistribution.
 * 
 * THIS SOFTWARE IS PROVIDED ``AS IS'', WITHOUT ANY WARRANTIES, EXPRESS
 * OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  LICENSOR SHALL
 * NOT BE LIABLE FOR ANY LOSS OR DAMAGES RESULTING FROM THE USE OF THIS
 * SOFTWARE, EITHER ALONE OR IN COMBINATION WITH ANY OTHER SOFTWARE.
 * 
 *      $Qube: Q/utils/sdk/vector.h,v 1.37.2.9 2004/09/07 17:38:22 jamief Exp $
 */

#ifndef __vector_h__
#define __vector_h__

#include        <stddef.h>

#include        <Q/qsys.h>
#include        <Q/linkage.h>
#include        "templbase.h"

#ifndef UTILS_BEGIN
#define UTILS_BEGIN     namespace Utils {
#define UTILS_END       }
#endif

#ifdef XDECL_SYNTAX
#define XDECL(x)   [x]
#else
#define XDECL(x)
#endif

UTILS_BEGIN

struct EXPORT_QUTILS VectorBase
{
    // Constructors
                                VectorBase() { init(); }

protected:

    void                        init() { size_ = 0; }
    
    void                        purge(void*, const TemplOps& ops);
    void                        clear(void*, const TemplOps& ops);
    void                        resizeFor(size_t n, 
                                         const TemplOps&,
                                         void*);
    bool                        locate(const void* t,
                                       size_t& atIndex,
                                       const TemplOps&,
                                       const void* v) const;
    bool                        locateLast(const void* t,
                                           size_t& atIndex,
                                           const TemplOps&,
                                           const void* v) const;
    void                        insert(const void* t,
                                       size_t atIndex,
                                       const TemplOps&,
                                       void* v);
    size_t                      add(const void* t, 
                                    const TemplOps&,
                                    void* v);

    void                        insert(const void* vsrc,
                                       size_t vSize,
                                       size_t atIndex,
                                       const TemplOps&,
                                       void* v);

    int                         compare(const void* vsrc, 
                                        size_t vSize,
                                        const TemplOps&,
                                        const void* v) const;

    bool                        removeAt(size_t i,
                                         const TemplOps&,
                                         void* v);

    bool                        removeAtOrdered(size_t i,
                                                const TemplOps&,
                                                void* base);

    bool                        removeAt(size_t start,
                                         size_t end,
                                         const TemplOps&,
                                         void* v);

    void                        sizeTo(size_t n,
                                       const TemplOps& ops,
                                       void* v);

    void                        sizeToExact(size_t n,
                                       const TemplOps& ops,
                                       void* v);

    void                        vectorCopyOp(const void* vsrc,
                                             size_t vSize,
                                             const TemplOps& ops,
                                             void* v);

    void                        add(const void* vsrc, size_t vSize,
                                    const TemplOps& ops,
                                    void* v);

    bool                        remove(const void* vsrc,
                                       size_t vSize,
                                       const TemplOps& ops,
                                       void* v);

    size_t                size_;
};

template<class T> struct Vector: public VectorBase
{
    // Constructors
                                Vector() { init(); }
                                Vector(const Vector<T>& v) 
                                   { init(); *this = v; }
                                Vector(size_t n)
                                   { init(); resizeFor(n); }

    // Destructor
                                ~Vector() { purge(); }

    // Accessors
    size_t                      size() const { return size_; }
    size_t                      space() const { return space_; }

    // Operators

    T&                          operator[](size_t i) 
        {
            QfAssert(i < size());
            return v_[i];
        }
    const T&                    operator[](size_t i) const
        {
            QfAssert(i < size());
            return v_[i];
        }
    T&                          at(size_t i)
        {
            QfAssert(i < size());
            return v_[i];
        }
    const T&                    at(size_t i) const
        {
            QfAssert(i < size());
            return v_[i];
        }
    
    // Features

    size_t                      add(const T& e);
    void                        add(const Vector<T>& v);

    bool                        locate(const T& e, size_t& i) const;

    bool                        locateFirst(const T& e, size_t& i) const
                                        { return locate(e, i); }

    bool                        locateLast(const T& e, size_t& i) const;

    bool                        intern(const T& e, size_t& i);
    void                        insert(const T& e, size_t i);
    void                        insert(const Vector<T>& v, size_t i);
    bool                        removeAt(size_t i);
    bool                        removeAt(size_t start, size_t end);
    
    bool                        remove(const T& e);
    bool                        remove(const Vector<T>& v);
    bool                        member(const T& t) const
                                  { size_t at; return locate(t, at); }
    void                        empty() { resizeFor(0); }
    void                        clear() { VectorBase::clear(this, ops_); }
    int                         compare(const Vector<T>& v) const;
    void                        consume(Vector<T>& v);
    void                        subtract(const Vector<T>& v, 
                                         Vector<T>& result) const;
    void                        intersect(const Vector<T>& v, 
                                          Vector<T>& result) const;
    Vector<T>&                  operator+=(const Vector<T>& v) 
                                { add(v); return *this; }
    Vector<T>&                  operator-=(const Vector<T>& v)
                                { remove(v); return *this; }

    int                         operator==(const Vector<T>& v) const
                                   { return !compare(v); }
    const T&                    first() const { return v_[0]; }
    const T&                    last() const { return v_[size_ - 1]; }

    void                        at(size_t i, const T& t)
        {
            QfAssert(i < size());
            v_[i] = t;
        }
    void                        sizeTo(size_t n);
    void                        sizeToExact(size_t n);
    void                        spaceTo(size_t n) { resizeFor(n); }
    Vector<T>&                  operator=(const Vector<T>& v);
    void                        slice(size_t start,
                                      size_t end,
                                      Vector<T>& result) const;
    size_t                      instanceSize() const;

protected:

    void                        init() { v_ = 0; space_ = 0; }
    void                        size(size_t s) { size_ = s; }
    void                        resizeFor(size_t);
    void                        purge() { VectorBase::purge(this, ops_); }

    DECL_OPERATORS(T);

protected:

    size_t                      space_;
    T* XDECL(space_)            v_;
};

#if defined(__GNUC__) && __GNUC__ == 3 && __GNUC_MINOR__ >= 1 && __GNUC_MINOR__ < 4
DEFINE_OPERATORS2(Vector, T,
                  (unsigned int)(&Vector<T>::space_),
                  (unsigned int)(&Vector<T>::v_));
#else
DEFINE_OPERATORS2(Vector, T,
                  offsetof(Vector<T>, space_),
                  offsetof(Vector<T>, v_));
#endif

template<class T> struct OrderByLess
{
    int compare(const T& a, const T& b) const
    {
        if (a == b) {
            return 0;
        } else if (a <= b) {
            return -1;
        } else {
            return 1;
        }
    }

    int pad;                    // This is just a reminder to indicate that
                                // the structure is padded to this size anyway.
};

template<class T, class C = OrderByLess<T> >
struct OrderedVector: public Vector<T>
{
                                OrderedVector() {}
                                OrderedVector(size_t n)
                                    : Vector<T>(n) {}
       
                                OrderedVector(const Vector<T>& v) { add(v); }
                                OrderedVector(const OrderedVector<T,C>& v)
                                                { *this = v; }

    // Overrides
    size_t                      add(const T&);
    bool                        locate(const T& e, size_t& i) const;
    bool                        locateFirst(const T& e, size_t& i) const;
    bool                        locateLast(const T& e, size_t& i) const;
    bool                        locateSeeded(const T& e, size_t& i) const;
    void                        add(const Vector<T>& v);
    bool                        intern(const T& e, size_t& i);
    bool                        remove(const T& e);
    bool                        member(const T& e) const;
    
    int                         compare(const OrderedVector<T,C>& v) const;


    int                         operator==(const OrderedVector<T,C>& v) const
                                   { return !compare(v); }
    int                         operator<=(const OrderedVector<T,C>& v) const
                                   { return compare(v) <= 0; }

    // Features
    void                        consume(OrderedVector<T,C>& v)
                                {
                                    Vector<T>::consume(v);
                                }

    bool                        removeAt(size_t i);

    bool                        removeAt(size_t start, size_t end);

    OrderedVector<T,C>&         operator=(const OrderedVector<T,C>& v);
    
    void                        intersect(const OrderedVector<T,C>& v,
                                          OrderedVector<T,C>& result) const; 
    void                        subtract(const OrderedVector<T,C>& v,
                                         OrderedVector<T,C>& result) const;
    void                        slice(size_t start,
                                      size_t end,
                                      OrderedVector<T,C>& result) const;

    void                        setComparison(const C& compare);

private:
    C                           comparison_;
};

/***************** Vector<T>, methods for ******************************/

template<class T> size_t Vector<T>::add(const T& t)
{
    return VectorBase::add(&t, ops_, this);
}

template<class T> void Vector<T>::resizeFor(size_t n)
{
    if (!n) purge();
    else VectorBase::resizeFor(n, ops_, this);
}

template<class T>
bool Vector<T>::locate(const T& t, size_t& atIndex) const
{
    return VectorBase::locate(&t, atIndex, ops_, this);
}

template<class T>
bool Vector<T>::locateLast(const T& t, size_t& atIndex) const
{
    return VectorBase::locateLast(&t, atIndex, ops_, this);
}

template<class T> void Vector<T>::insert(const T& t, size_t atIndex)
{
    VectorBase::insert(&t, atIndex, ops_, this);
}

template<class T> void Vector<T>::insert(const Vector<T>& v,
                                         size_t atIndex)
{
    /* Insert the given vector, `v' at `atIndex' */
    VectorBase::insert(v.v_, v.size(), atIndex, ops_, this);
}

template<class T> bool Vector<T>::intern(const T& t, size_t& atIndex)
{
    bool found = locate(t, atIndex);
    if (!found) {
        add(t);
    }
    return bool(!found);
}

template <class T> int Vector<T>::compare(const Vector<T>& v) const
{
    return VectorBase::compare(v.v_, v.size(), ops_, this);
}

template <class T> bool Vector<T>::removeAt(size_t i)
{
    return VectorBase::removeAt(i, ops_, this);
}

template <class T> bool Vector<T>::removeAt(size_t start,
                                            size_t end)
{
    /* Remove the range [start, end) */
    return VectorBase::removeAt(start, end, ops_, this);
}

template <class T> bool Vector<T>::remove(const T& t)
{
    size_t at;
    if (locate(t, at)) return removeAt(at);
    return false;
}

template<class T>
void Vector<T>::slice(size_t start, size_t end,
                      Vector<T>& result) const
{
    result.empty();

    if (end > size()) end = size();
    if (start >= end) return;

    result.sizeTo(end - start);
    for (size_t i = start; i < end; ++i) {
        result[i - start] = v_[i];
    }
}

template<class T> void Vector<T>::consume(Vector<T>& v)
{
    if (this != &v) {
        /* Steal the contents of v, leaving v empty */
        purge();

        v_ = v.v_;
        size_ = v.size_;
        space_ = v.space_;

        v.init();
        v.VectorBase::init();
    }
}

template<class T> void Vector<T>::sizeTo(size_t n) 
{
    VectorBase::sizeTo(n, ops_, this);
}

template<class T> void Vector<T>::sizeToExact(size_t n) 
{
    VectorBase::sizeToExact(n, ops_, this);
}

template<class T> Vector<T>& Vector<T>::operator=(const Vector<T>& v)
{
    VectorBase::vectorCopyOp(v.v_, v.size(), ops_, this);
    return *this;
}

template<class T> void Vector<T>::add(const Vector<T>& v)
{
    VectorBase::add(v.v_, v.size(), ops_, this);
}

template<class T> bool Vector<T>::remove(const Vector<T>& v)
{
    /* Return true iff all elements of `v' removed.
     */
    return VectorBase::remove(v.v_, v.size(), ops_, this);
}

template<class T> void
Vector<T>::subtract(const Vector<T>& v, Vector<T>& result) const
{
    result.empty();
    for (size_t i = 0; i < size(); ++i) {
        if (!v.member(v_[i])) result.add(v_[i]);
    }
}

template<class T> void
Vector<T>::intersect(const Vector<T>& v, Vector<T>& result) const
{
    result.empty();
    for (size_t i = 0; i < size(); ++i) {
        if (v.member(v_[i])) result.add(v_[i]);
    }
}

template<class T> size_t Vector<T>::instanceSize() const
{
    return sizeof(*this) + space_*sizeof(T);
}

/*********** OrderedVector<T,C>, methods for ****************************/

template<class T, class C>
OrderedVector<T,C>& OrderedVector<T,C>::operator=(const OrderedVector<T,C>& v)
{
    Vector<T>::operator=(v);
    return *this;
}

template<class T, class C>
bool OrderedVector<T,C>::locate(const T& t, size_t& atIndex) const
{
    size_t lo = (size_t)-1;
    size_t hi = this->size_;

    bool found = false;
    size_t probe;
    
    while (hi - lo > 1) {
        probe = (lo + hi) / 2;
        int val = comparison_.compare(this->v_[probe], t);
        
        if (!val) {
            hi = probe;
            found = true;
            break;
        } else if (val < 0) {
            lo = probe;
        } else {
            hi = probe;
        }
    }

    atIndex = hi;
    return found;
}

template<class T, class C>
bool OrderedVector<T,C>::locateFirst(const T& t, size_t& atIndex) const
{
    /* Find the first match in the ordered vector not just any match.
     */

    bool found = locate(t, atIndex);
    if (found && atIndex > 0) {
        /* We have a match, but it might not be the first.
         * step back until we have the first match.
         */
        size_t i = atIndex;

        do {
            --i;
            int val = comparison_.compare(this->v_[i], t);
            if (!val) atIndex = i;
            else break;
        } while (i > 0);
    }
    return found;
}

template<class T, class C>
bool OrderedVector<T,C>::locateLast(const T& t, size_t& atIndex) const
{
    /* Find the last match in the ordered vector not just any match.
     */

    bool found = locate(t, atIndex);
    if (found) {
        /* We have a match, but it might not be the last.
         * step forwards until we have the last match.
         */
        size_t i = atIndex + 1;
        while (i < this->size_) {
            int val = comparison_.compare(this->v_[i], t);
            if (!val) atIndex = i;
            else break;
            ++i;
        };
    }
    return found;
}

template<class T, class C>
bool OrderedVector<T,C>::locateSeeded(const T& t, size_t& atIndex) const
{
    /* Pass initial guess in as `atIndex'.
     * The first element looked at will be atIndex + 1. this is
     * so that the seed can be the last result and we work through
     * one at a time for repeated keys.
     * 
     * pass in atIndex >= size-1 or atIndex == -1 for a search of whole table.
     */

    size_t probe;
    int val;
    size_t hi;
    size_t lo;
    size_t inc;

    /* Use `atIndex + 1' as first guess */
    probe = atIndex + 1;
    if (probe && probe < this->size_) {
        val = comparison_.compare(this->v_[probe], t);
        
        if (!val) {
            /* Hit the answer, return straight away */
            atIndex = probe;
            return true;
        }
        
        inc = 2;
        if (val < 0) {
            lo = probe;
            
            for (;;) {
                hi = lo + inc;
                if (hi >= this->size_) {
                    hi = this->size_;
                    break;
                }
                
                val = comparison_.compare(this->v_[hi], t);
                
                if (!val) {
                    atIndex = hi;
                    return true;
                } else if (val < 0) {
                    lo = hi;
                    inc <<= 1;
                } else {
                    break;
                }
            }
        } else {
            hi = probe;
            for (;;) {
                if (hi < inc) {
                    lo = (size_t)-1;
                    break;
                }
                
                lo = hi - inc;
                val = comparison_.compare(this->v_[lo], t);
                
                if (!val) {
                    atIndex = lo;
                    return true;
                } else if (val > 0) {
                    hi = lo;
                    inc <<= 1;
                } else {
                    break;
                }
            }
        }
    } else {
        /* Guess is out of range, search whole table */
        hi = this->size_;
        lo = (size_t)-1;
    }

    bool found = false;
    while (hi - lo > 1) {
        probe = (lo + hi) / 2;
        val = comparison_.compare(this->v_[probe], t);
        
        if (!val) {
            hi = probe;
            found = true;
            break;
        } else if (val < 0) {
            lo = probe;
        } else {
            hi = probe;
        }
    }

    atIndex = hi;
    return found;
}

template<class T, class C> size_t OrderedVector<T,C>::add(const T& t)
{
    size_t atIndex;
    locate(t, atIndex);         // &atIndex
    insert(t, atIndex);
    return atIndex;
}

template<class T, class C> void OrderedVector<T,C>::add(const Vector<T>& v)
{
    resizeFor(this->size_ + v.size());
    for (size_t i = 0; i < v.size(); ++i) add(v[i]);
}

template<class T, class C> bool OrderedVector<T,C>::intern(const T& t,
                                                size_t& atIndex)
{
    bool found = locate(t, atIndex);
    if (!found) {
        insert(t, atIndex);
    }
    return bool(!found);
}

template<class T, class C> bool OrderedVector<T,C>::remove(const T& t)
{
    size_t at;
    if (locate(t, at)) return removeAt(at);
    return false;
}

template<class T, class C> bool OrderedVector<T,C>::member(const T& t) const
{
    size_t atIndex;
    return locate(t, atIndex);
}


template<class T, class C>
int OrderedVector<T,C>::compare(const OrderedVector<T,C>& v) const
{
    if (this->size_ != v.size())
        return 1;

    int val = 0;
    for (size_t i = 0; i < this->size_; ++i) {
        val = comparison_.compare(v.v_[i], this->v_[i]);
        if (val) break;
    }
    return val;
}

template<class T, class C> void
OrderedVector<T,C>::slice(size_t start, size_t end,
                          OrderedVector<T,C>& result) const
{
    result.empty();

    if (end > this->size()) end = this->size();
    if (start >= end) return;

    result.sizeTo(end - start);
    for (size_t i = start; i < end; ++i) {
        result[i - start] = this->v_[i];
    }
}

template<class T, class C> void
OrderedVector<T,C>::subtract(const OrderedVector<T,C>& v,
                             OrderedVector<T,C>& result) const
{
    result.empty();
    for (size_t i = 0; i < this->size(); ++i) {
        if (!v.member(this->v_[i])) result.add(this->v_[i]);
    }
}

template<class T, class C> void
OrderedVector<T,C>::intersect(const OrderedVector<T,C>& v,
                              OrderedVector<T,C>& result) const
{
    result.empty();
    for (size_t i = 0; i < this->size(); ++i) {
        if (v.member(this->v_[i])) result.add(this->v_[i]);
    }
}

template<class T, class C>
bool OrderedVector<T,C>::removeAt(size_t i)
{
    /* Use version that preserves order */
    return VectorBase::removeAtOrdered(i, this->ops_, this);
}

template<class T, class C>
bool OrderedVector<T,C>::removeAt(size_t start,
                                        size_t end)
{
    return VectorBase::removeAt(start, end, this->ops_, this);
}

template<class T, class C>
void OrderedVector<T,C>::setComparison(const C& compare)
{
    comparison_ = compare;
}

UTILS_END

#endif /* __vector_h__ */

// Local Variables:
// mode: c++
// End:

		Qube Software Limited © 2000-2004