SortedArray - bug or user mistake

On 23/03/2018 at 04:59, xxxxxxxx wrote:

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

  
[T](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/classmaxon_1_1_sorted_array.html#ad3a1bd799977d25c6e2f36919a4b25bd) * [FindOrInsert](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/classmaxon_1_1_sorted_array.html#a5356f3c1132c7dd74218374f6bec26fe) (const SEARCH &key, const [T](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/classmaxon_1_1_sorted_array.html#ad3a1bd799977d25c6e2f36919a4b25bd) *ptr=[nullptr](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/compilerdetection_8h.html#ac3c36c503cc2ba5594bb924b009713fc))  

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

  
[T](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/classmaxon_1_1_sorted_array.html#ad3a1bd799977d25c6e2f36919a4b25bd) * [FindOrInsert](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/classmaxon_1_1_sorted_array.html#a630e3073602651759e7418541f2a2b64) (const SEARCH &key, [Bool](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/namespacemaxon.html#a76a8b016e5ad61faf9062cc387df5016) &newElement, const [T](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/classmaxon_1_1_sorted_array.html#ad3a1bd799977d25c6e2f36919a4b25bd) *ptr=[nullptr](https://developers.maxon.net/docs/Cinema4DCPPSDK/html/compilerdetection_8h.html#ac3c36c503cc2ba5594bb924b009713fc))  

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 ???

On 26/03/2018 at 08:45, xxxxxxxx wrote:

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>

On 26/03/2018 at 12:12, xxxxxxxx wrote:

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