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


Log in to reply