Plugin Cafe Homepage
Forum Home Forum Home > Plugin Cafe > SDK Help
  New Posts New Posts
  FAQ FAQ  Forum Search

SortedArray - bug or user mistake

Author
Message
  Topic Search Topic Search
C4DS View Drop Down
Member
Member


Joined: 2015 Dec 01
Online Status: Offline
Posts: 235
Direct Link To This Post Topic: SortedArray - bug or user mistake
    Posted: 2018 Mar 23 at 4:59am

User Information:

Cinema 4D Version:   R19 
Platform:   Windows  ;   
Language(s):     C++  ;   

---------

Hi,

I was playing around with the SortedArray, writing a little helper class to sort Int32 values


class SortedInt32Array : public maxon::SortedArray<SortedInt32Array, maxon::BaseArray<Int32>>
{
public:
    SortedInt32Array() {}
   
    static inline maxon::Bool LessThan(Int32 a, Int32 b)    { return a < b; }
    static inline maxon::Bool IsEqual(Int32 a, Int32 b)    { return a == b; }
    static void InitInsertData(Int32& initme, const Int32& key) { initme = key; }
};



void SortInt32(const maxon::BaseArray<Int32>& numbers)
{
    SortedInt32Array sorted;
    for (const Int32& nbr : numbers)
    {
        maxon::Bool inserted;
        Int32* item = sorted.FindOrInsert(nbr, inserted);
        if (inserted)
        {
            // why do I need following line, shouldn't this be part of FindOrInsert implementation ???
            sorted.InitInsertData(*item, nbr);
        }
    }

// some more ...
}



If I don't provide a call to sorted.InitInsertData() the value actually inserted into sorted is a zero, and I end up with sorted being a list of zeros.

When I am looking at the actual SortedArray implementation

    template <typename SEARCH> T* FindOrInsert(const SEARCH& key, const T* ptr = nullptr)
    {
        CheckSort();
        BaseSort<MYSELF> sort;
        Int insertIdx = NOTOK;
        T*    e = sort.FindInsertionIndex(key, _array, insertIdx);
        if (!e)
        {
            e = _array.Insert(insertIdx);
            if (e)
                MYSELF::InitInsertData(*e, key);
        }
        return e;
    }

    template <typename SEARCH> T* FindOrInsert(const SEARCH& key, Bool& newElement, const T* ptr = nullptr)
    {
        CheckSort();
        BaseSort<MYSELF> sort;
        Int insertIdx = NOTOK;
        T*    e = sort.FindInsertionIndex(key, _array, insertIdx);
        if (!e)
        {
            e = _array.Insert(insertIdx);
            newElement = true;
        }
        else
        {
            newElement = false;
        }
        return e;
    }


I notice that the function

TFindOrInsert (const SEARCH &key, const T *ptr=nullptr)

does actually perform a MYSELF::InitInsertData(*e, key);
while function

TFindOrInsert (const SEARCH &key, Bool &newElement, const T *ptr=nullptr)

does not, while I would expect both function would perform a MYSELF::InitInsertData right after the item was inserted into the array.

Am I missing something from the documentation, that as a user I should perform the InitInsertData after using the second function, but not when calling the first function ???



Edited by C4DS - 2018 Mar 23 at 5:00am
Back to Top
Andreas Block View Drop Down
Forum Moderator
Forum Moderator
Avatar

Joined: 2014 Oct 01
Location: Hannover
Online Status: Offline
Posts: 1878
Direct Link To This Post Posted: 2018 Mar 26 at 8:45am
Hi,

after discussion with development this seems to be intentional. Of course then the documentation is a bit misleading and needs a fix.
The FindOrInsert() with three parameters expects the value to be filled in after return.

The developer suggested a shorter and more efficient implementation:
void SortInt32(const maxon::BaseArray<Int32>& numbers)
{
    SortedInt32Array sorted;
    Bool res = sorted.CopyFrom(numbers);
    if (!res)
        // handle error...
}
With this implementation there's also no need for InitInsertData().

Or to make use of SimpleSort class, if sorting the array once is sufficient:
    SimpleSort<Int32> sort;
    sort.Sort(numbers); // with numbers again being a BaseArray<Int32>

Cheers,
Andreas
SDK Support Engineer
Back to Top
C4DS View Drop Down
Member
Member


Joined: 2015 Dec 01
Online Status: Offline
Posts: 235
Direct Link To This Post Posted: 2018 Mar 26 at 12:12pm
Thanks for the info, Andreas.

I made a copy/paste mistake when providing my sort method to describe the problem.
Where I originally had put the "// some more" outside of the "if (inserted)", I actually intended to have it inside.
Hence the shorter suggestion from developer (while still a useful example) isn't really of use here.


void SortInt32(const maxon::BaseArray<Int32>& numbers)
{
    SortedInt32Array sorted;
    for (const Int32& nbr : numbers)
    {
        maxon::Bool inserted;
        Int32* item = sorted.FindOrInsert(nbr, inserted);
        if (inserted)
        {
            // why do I need following line, shouldn't this be part of FindOrInsert implementation ???
            sorted.InitInsertData(*item, nbr);

            // some more ... [intended]
        }
    }

    // some more ... [original]
}



I guess, I could simply do a FindValue, and if not found, perform a FindOrInsert with 2 parameters (instead of the one with 3)

Daniel
Back to Top

Forum Jump Forum Permissions View Drop Down

Bulletin Board Software by Web Wiz Forums® version 9.61 [Free Express Edition]
Copyright ©2001-2009 Web Wiz

This page was generated in 0.109 seconds.