algorithms.h

#pragma once


#include <libutl/Predicate.h>
#include <libutl/RandIt.h>
#include <libutl/Stream.h>
#include <libutl/String.h>


UTL_NS_BEGIN;


enum sort_t
{
    sort_heapSort,      
    sort_insertionSort, 
    sort_mergeSort,     
    sort_quickSort,     
    sort_none           
};


size_t binarySearch(const RandIt& begin,
                    const RandIt& end,
                    const Object& key,
                    const Ordering* ordering = nullptr,
                    uint_t findType = find_first);


void clobber(const FwdIt& lhsBegin,
             const FwdIt& lhsEnd,
             const FwdIt& rhsBegin,
             const FwdIt& rhsEnd,
             const Ordering* ordering = nullptr);


int compare(const FwdIt& lhsBegin,
            const FwdIt& lhsEnd,
            const FwdIt& rhsBegin,
            const FwdIt& rhsEnd,
            const Ordering* ordering = nullptr);


void copy(FwdIt& out,
          const FwdIt& begin,
          const FwdIt& end,
          bool cloning = false,
          const Predicate* pred = nullptr,
          bool predVal = true);


void copy(Object** out,
          const FwdIt& begin,
          const FwdIt& end,
          bool cloning = false,
          const Predicate* pred = nullptr,
          bool predVal = true);


void copy(FwdIt& out,
          const Vector<Object*>& in,
          bool cloning = false,
          const Predicate* pred = nullptr,
          bool predVal = true);


size_t
count(const FwdIt& begin, const FwdIt& end, const Predicate* pred = nullptr, bool predVal = true);


void difference(const FwdIt& lhsBegin,
                const FwdIt& lhsEnd,
                const FwdIt& rhsBegin,
                const FwdIt& rhsEnd,
                FwdIt& out,
                const Ordering* ordering = nullptr,
                bool cloning = false,
                bool outIsLHS = false);


void dump(const FwdIt& begin,
          const FwdIt& end,
          Stream& os,
          uint_t level = uint_t_max,
          bool key = false,
          bool printClassName = false,
          uint_t indent = 0,
          const char* separator = nullptr);


void heapSort(const BidIt& begin,
              const BidIt& end,
              const Ordering* ordering = nullptr,
              size_t size = size_t_max);


void heapSort(Object** array, size_t begin, size_t end, const Ordering* ordering = nullptr);


void insertionSort(const FwdIt& begin,
                   const FwdIt& end,
                   const Ordering* ordering = nullptr,
                   size_t size = size_t_max);


void insertionSort(Object** array, size_t begin, size_t end, const Ordering* ordering = nullptr);


void intersect(const FwdIt& lhsBegin,
               const FwdIt& lhsEnd,
               const FwdIt& rhsBegin,
               const FwdIt& rhsEnd,
               FwdIt& out,
               const Ordering* ordering = nullptr,
               bool cloning = false,
               bool multiSet = false,
               bool outIsLHS = false);


size_t intersectCard(const FwdIt& lhsBegin,
                     const FwdIt& lhsEnd,
                     const FwdIt& rhsBegin,
                     const FwdIt& rhsEnd,
                     const Ordering* ordering = nullptr,
                     bool multiSet = false);


bool intersects(const FwdIt& lhsBegin,
                const FwdIt& lhsEnd,
                const FwdIt& rhsBegin,
                const FwdIt& rhsEnd,
                const Ordering* ordering = nullptr);


bool isSorted(const FwdIt& begin, const FwdIt& end, const Ordering* ordering = nullptr);


bool isSubSet(const FwdIt& lhsBegin,
              const FwdIt& lhsEnd,
              const FwdIt& rhsBegin,
              const FwdIt& rhsEnd,
              const Ordering* ordering = nullptr);


bool isSuperSet(const FwdIt& lhsBegin,
                const FwdIt& lhsEnd,
                const FwdIt& rhsBegin,
                const FwdIt& rhsEnd,
                const Ordering* ordering = nullptr);


void linearSearch(const FwdIt& begin,
                  const FwdIt& end,
                  const Object& key,
                  FwdIt& out,
                  const Ordering* ordering = nullptr,
                  uint_t findType = find_first);


void linearSearchSorted(const FwdIt& begin,
                        const FwdIt& end,
                        const Object& key,
                        FwdIt& out,
                        const Ordering* ordering = nullptr,
                        uint_t findType = find_first);


void merge(const FwdIt& lhsBegin,
           const FwdIt& lhsEnd,
           const FwdIt& rhsBegin,
           const FwdIt& rhsEnd,
           FwdIt& out,
           const Ordering* ordering = nullptr,
           bool cloning = false);


void mergeSort(const FwdIt& begin,
               const FwdIt& end,
               const Ordering* ordering = nullptr,
               size_t size = size_t_max);


void mergeSort(Object** array, size_t begin, size_t end, const Ordering* ordering = nullptr);


void multiKeyQuickSort(const FwdIt& begin,
                       const FwdIt& end,
                       bool key = true,
                       bool reverse = false,
                       size_t size = size_t_max);


void quickSort(const FwdIt& begin,
               const FwdIt& end,
               const Ordering* ordering = nullptr,
               size_t size = size_t_max);


void quickSort(Object** array, size_t begin, size_t end, const Ordering* ordering = nullptr);


void remove(FwdIt& begin,
            const FwdIt& end,
            bool cmp = false,
            const Predicate* pred = nullptr,
            bool predVal = false);


void reverse(const BidIt& begin, const BidIt& end);


void serializeIn(FwdIt& out,
                 size_t numItems,
                 Stream& is,
                 uint_t mode = ser_default,
                 const RunTimeClass* rtc = nullptr);


void serializeOut(
    const FwdIt& begin, const FwdIt& end, Stream& os, uint_t mode = ser_default, bool boxed = true);


void sort(const FwdIt& begin,
          const FwdIt& end,
          const Ordering* ordering = nullptr,
          uint_t algorithm = sort_quickSort,
          size_t size = size_t_max);


void sort(Object** array,
          size_t begin,
          size_t end,
          const Ordering* ordering = nullptr,
          uint_t algorithm = sort_quickSort);


inline void
swap(FwdIt& lhs, FwdIt& rhs)
{
    Object* tmp = *lhs;
    lhs.set(*rhs);
    rhs.set(tmp);
}


inline void
swap(RandIt& it, size_t lhsIdx, size_t rhsIdx)
{
    Object* tmp = it[lhsIdx];
    it.set(lhsIdx, it.get(rhsIdx));
    it.set(rhsIdx, tmp);
}


void symmetricDifference(const FwdIt& lhsBegin,
                         const FwdIt& lhsEnd,
                         const FwdIt& rhsBegin,
                         const FwdIt& rhsEnd,
                         FwdIt& out,
                         const Ordering* ordering = nullptr,
                         bool cloning = false);


void symmetricDifference(const FwdIt& lhsBegin,
                         const FwdIt& lhsEnd,
                         const FwdIt& rhsBegin,
                         const FwdIt& rhsEnd,
                         FwdIt& lhsOut,
                         FwdIt& rhsOut,
                         const Ordering* ordering = nullptr,
                         bool lhsCloning = false,
                         bool rhsCloning = false);


String toString(const FwdIt& begin, const FwdIt& end, const String& sep, bool key = false);


void unique(const FwdIt& begin,
            const FwdIt& end,
            FwdIt& out,
            const Ordering* ordering = nullptr,
            bool cloning = false,
            bool outIsSrc = false);


UTL_NS_END;


#include <libutl/algorithms_inl.h>