UT/UT_PtrArraySorted.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Side Effects Software Inc.
 *      477 Richmond Street West, Suite 1001
 *      Toronto, Ontario
 *      Canada   M5V 3E7
 *      416-504-9876
 */

#ifndef __UT_PtrArraySorted_h__
#define __UT_PtrArraySorted_h__

#include "UT_PtrArray.h"

template <class utPtr>
class UT_PtrArraySorted
{
public:
                         UT_PtrArraySorted()
                             : myComparator(
                                typename UT_PtrArray<utPtr>::Comparator(
                                           UTcomparePointers))
                         { }

                         UT_PtrArraySorted(
                            typename UT_PtrArray<utPtr>::Comparator comparator)
                             : myComparator(comparator)
                         { }
    virtual             ~UT_PtrArraySorted()
                         { }

    void                 setComparator(typename
                                       UT_PtrArray<utPtr>::Comparator cmp)
                         { myComparator = cmp; myArray.sort(myComparator); }
    void                 sort()
                         { myArray.sort(myComparator); }

    int                  entries() const
                         { return myArray.entries(); }
    void                 entries(int newnumentries)
                         { myArray.entries(newnumentries); }
    void                 resize(int newsize)
                         { myArray.resize(newsize); }
    
    utPtr                operator()(int index) const
                         { return myArray(index); }
    utPtr                last() const
                         { return myArray.last(); }
    int                  find(utPtr ptr) const
                         { return myArray.find(ptr, myComparator); }
    // This is only valid if utPtr == char *
    int                  findString(const char *str) const
                         { return myArray.findString(str); }

    bool                 operator==(const UT_PtrArraySorted &cmp) const
                         {
                             utPtr       ptr, cmpptr;
                             int         idx, num, diff;

                             if( entries() != cmp.entries() )
                                 return false;

                             num = entries();
                             for( idx = 0; idx < num; idx++ )
                             {
                                 ptr = myArray(idx);
                                 cmpptr = cmp.myArray(idx);
                                 diff = myComparator(&ptr, &cmpptr);

                                 if( diff != 0 )
                                     return false;
                             }

                             return true;
                         }

    bool                 containsAny(const UT_PtrArraySorted &cmp) const
                         {
                             utPtr       ptr, cmpptr;
                             int         idx, cmpidx, num, numcmp, diff;

                             numcmp = cmp.entries();
                             num = entries();
                             for( idx = 0, cmpidx = 0;
                                  idx < num && cmpidx < numcmp; )
                             {
                                 ptr = myArray(idx);
                                 cmpptr = cmp.myArray(cmpidx);
                                 diff = myComparator(&ptr, &cmpptr);

                                 if( diff < 0 )
                                 {
                                     idx++;
                                 }
                                 else if( diff > 0 )
                                 {
                                     cmpidx++;
                                 }
                                 else
                                 {
                                     return true;
                                 }
                             }

                             return false;
                         }
    bool                 containsFully(const UT_PtrArraySorted &cmp) const
                         {
                             utPtr       ptr, cmpptr;
                             int         idx, cmpidx, num, numcmp, diff;

                             numcmp = cmp.entries();
                             num = entries();
                             for( idx = 0, cmpidx = 0;
                                  idx < num && cmpidx < numcmp; )
                             {
                                 ptr = myArray(idx);
                                 cmpptr = cmp.myArray(cmpidx);
                                 diff = myComparator(&ptr, &cmpptr);

                                 if( diff < 0 )
                                 {
                                     idx++;
                                 }
                                 else if( diff > 0 )
                                 {
                                     return false;
                                 }
                                 else
                                 {
                                     idx++;
                                     cmpidx++;
                                 }
                             }

                             return (cmpidx >= numcmp) ? true : false;
                         }

    void                 remove(int index)
                         { myArray.removeIndex(index); }
    void                 remove(utPtr ptr)
                         { int pos = find(ptr); if( pos >= 0 ) remove(pos); }
    void                 remove(const UT_PtrArraySorted &src)
                         {
                             utPtr       srcptr, destptr;
                             int         idx, srcidx, diff, numsrc;
                             bool        removed = false;

                             numsrc = src.entries();
                             for( idx = 0, srcidx = 0;
                                  srcidx < numsrc && idx < entries(); )
                             {
                                 destptr = myArray(idx);
                                 srcptr = src.myArray(srcidx);
                                 diff = myComparator(&destptr, &srcptr);

                                 if( diff < 0 )
                                 {
                                     idx++;
                                 }
                                 else
                                 {
                                     if( diff == 0 )
                                     {
                                         myArray(idx) = 0;
                                         removed = true;
                                         idx++;
                                     }
                                     srcidx++;
                                 }
                             }
                             if( removed )
                                 myArray.removeZeros();
                         }
    void                 keepOnly(const UT_PtrArraySorted &src)
                         {
                             utPtr       srcptr, destptr;
                             int         idx, srcidx, diff, numsrc;
                             bool        removed = false;

                             numsrc = src.entries();
                             for( idx = 0, srcidx = 0; idx < entries(); )
                             {
                                 if( srcidx < numsrc )
                                 {
                                     destptr = myArray(idx);
                                     srcptr = src.myArray(srcidx);
                                     diff = myComparator(&destptr, &srcptr);
                                 }
                                 else
                                     diff = -1;

                                 if( diff < 0 )
                                 {
                                     myArray(idx) = 0;
                                     removed = true;
                                     idx++;
                                 }
                                 else
                                 {
                                     if( diff == 0 )
                                         idx++;
                                     srcidx++;
                                 }
                             }
                             if( removed )
                                 myArray.removeZeros();
                         }
    
    const UT_PtrArraySorted &operator=(const UT_PtrArraySorted &src)
                         { set(src); return *this; }
    int                  add(utPtr ptr)
                         {
                             return myArray.
                                    uniqueSortedInsert(ptr, myComparator);
                         }
    void                 set(const UT_PtrArraySorted &src)
                         {
                             myComparator = src.myComparator;
                             myArray = src.myArray;
                         }
    void                 setUnsorted(const UT_PtrArray<utPtr> &src,
                                     UT_PtrArraySorted &duplicates)
                         {
                             utPtr       lastptr, nextptr;
                             int         idx;

                             myArray = src;
                             sort();
                             for( idx = 1; idx < entries(); idx++ )
                             {
                                 lastptr = myArray(idx-1);
                                 nextptr = myArray(idx);
                                 if( myComparator(&lastptr, &nextptr) == 0 )
                                 {
                                     duplicates.add(lastptr);
                                     myArray(idx-1) = 0;
                                 }
                             }
                             if( duplicates.entries() )
                                 myArray.removeZeros();
                         }
    void                 merge(const UT_PtrArraySorted &src)
                         {
                             utPtr       srcptr, destptr;
                             int         idx, srcidx, diff, numsrc;

                             numsrc = src.entries();
                             for( idx = 0, srcidx = 0; srcidx < numsrc; )
                             {
                                 if( idx < entries() )
                                 {
                                     destptr = myArray(idx);
                                     srcptr = src.myArray(srcidx);
                                     diff = myComparator(&destptr, &srcptr);
                                 }
                                 else
                                     diff = 1;
                                 if( diff < 0 )
                                 {
                                     idx++;
                                 }
                                 else
                                 {
                                     if( diff > 0 )
                                         myArray.insert(src(srcidx), idx);
                                     idx++;
                                     srcidx++;
                                 }
                             }
                         }
    void                 mergeSelected(const UT_PtrArraySorted &src,
                                       bool (*selectfunc)(utPtr))
                         {
                             utPtr       srcptr, destptr;
                             int         idx, srcidx, diff, numsrc;

                             numsrc = src.entries();
                             for( idx = 0, srcidx = 0; srcidx < numsrc; )
                             {
                                 // Just skip over any source pointers that
                                 // aren't accepted by the select function.
                                 if( selectfunc(src.myArray(srcidx)) )
                                 {
                                     if( idx < entries() )
                                     {
                                         destptr = myArray(idx);
                                         srcptr = src.myArray(srcidx);
                                         diff = myComparator(&destptr, &srcptr);
                                     }
                                     else
                                         diff = 1;
                                     if( diff < 0 )
                                     {
                                         idx++;
                                     }
                                     else
                                     {
                                         if( diff > 0 )
                                             myArray.insert(src(srcidx), idx);
                                         idx++;
                                         srcidx++;
                                     }
                                 }
                                 else
                                     srcidx++;
                             }
                         }


    // Not that this function can ruin the sort order. Use with caution.
    void                         appendUnsafe(utPtr ptr)
                                 { myArray.append(ptr); }
    // This function gets our contained UT_PtrArray.
    const UT_PtrArray<utPtr>    &getRawArray() const
                                 { return myArray; }
     // This function gets our contained UT_PtrArray.
    UT_PtrArray<utPtr>  &getRawArray()
                                 { return myArray; }
    
private:
    typename UT_PtrArray<utPtr>::Comparator      myComparator;
    UT_PtrArray<utPtr>                           myArray;
};


#endif

---