vtkVariantArray.cxx

/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkVariantArray.cxx

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
/*-------------------------------------------------------------------------
  Copyright 2008 Sandia Corporation.
  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
  the U.S. Government retains certain rights in this software.
-------------------------------------------------------------------------*/

// We do not provide a definition for the copy constructor or
// operator=.  Block the warning.
#ifdef _MSC_VER
#pragma warning(disable : 4661)
#endif

#include "vtkVariantArray.h"

#include "vtkArrayIteratorTemplate.h"
#include "vtkDataArray.h"
#include "vtkIdList.h"
#include "vtkObjectFactory.h"
#include "vtkSortDataArray.h"
#include "vtkStringArray.h"
#include "vtkVariant.h"

#include <algorithm>
#include <cmath>
#include <map>
#include <utility>

// Map containing updates to a vtkVariantArray that have occurred
// since we last build the vtkVariantArrayLookup.
typedef std::multimap<vtkVariant, vtkIdType, vtkVariantLessThan> vtkVariantCachedUpdates;

namespace
{
auto DefaultDeleteFunction = [](void* ptr) { delete[] reinterpret_cast<vtkVariant*>(ptr); };
}

//------------------------------------------------------------------------------
class vtkVariantArrayLookup
{
public:
  vtkVariantArrayLookup()
    : Rebuild(true)
  {
    this->SortedArray = nullptr;
    this->IndexArray = nullptr;
  }
  ~vtkVariantArrayLookup()
  {
    if (this->SortedArray)
    {
      this->SortedArray->Delete();
      this->SortedArray = nullptr;
    }
    if (this->IndexArray)
    {
      this->IndexArray->Delete();
      this->IndexArray = nullptr;
    }
  }
  vtkVariantArray* SortedArray;
  vtkIdList* IndexArray;
  vtkVariantCachedUpdates CachedUpdates;
  bool Rebuild;
};

//
// Standard functions
//

vtkStandardNewMacro(vtkVariantArray);
vtkStandardExtendedNewMacro(vtkVariantArray);
//------------------------------------------------------------------------------
void vtkVariantArray::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
  if (this->Array)
  {
    os << indent << "Array: " << this->Array << "\n";
  }
  else
  {
    os << indent << "Array: (null)\n";
  }
}

//------------------------------------------------------------------------------
vtkVariantArray::vtkVariantArray()
{
  this->Array = nullptr;
  this->DeleteFunction = DefaultDeleteFunction;
  this->Lookup = nullptr;
}

//------------------------------------------------------------------------------
vtkVariantArray::~vtkVariantArray()
{
  if (this->DeleteFunction)
  {
    this->DeleteFunction(this->Array);
  }
  delete this->Lookup;
}

//
//
// Functions required by vtkAbstractArray
//
//

//------------------------------------------------------------------------------
vtkTypeBool vtkVariantArray::Allocate(vtkIdType sz, vtkIdType)
{
  if (sz > this->Size)
  {
    if (this->DeleteFunction)
    {
      this->DeleteFunction(this->Array);
    }

    this->Size = (sz > 0 ? sz : 1);
    this->Array = new vtkVariant[this->Size];
    if (!this->Array)
    {
      return 0;
    }
    this->DeleteFunction = DefaultDeleteFunction;
  }

  this->MaxId = -1;
  this->DataChanged();

  return 1;
}

//------------------------------------------------------------------------------
void vtkVariantArray::Initialize()
{
  if (this->DeleteFunction)
  {
    this->DeleteFunction(this->Array);
  }
  this->Array = nullptr;
  this->Size = 0;
  this->MaxId = -1;
  this->DeleteFunction = DefaultDeleteFunction;
  this->DataChanged();
}

//------------------------------------------------------------------------------
int vtkVariantArray::GetDataType() const
{
  return VTK_VARIANT;
}

//------------------------------------------------------------------------------
int vtkVariantArray::GetDataTypeSize() const
{
  return static_cast<int>(sizeof(vtkVariant));
}

//------------------------------------------------------------------------------
int vtkVariantArray::GetElementComponentSize() const
{
  return this->GetDataTypeSize();
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetNumberOfTuples(vtkIdType number)
{
  this->SetNumberOfValues(this->NumberOfComponents * number);
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetTuple(vtkIdType i, vtkIdType j, vtkAbstractArray* source)
{
  if (source->IsA("vtkVariantArray"))
  {
    vtkVariantArray* a = vtkArrayDownCast<vtkVariantArray>(source);
    vtkIdType loci = i * this->NumberOfComponents;
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      this->SetValue(loci + cur, a->GetValue(locj + cur));
    }
  }
  else if (source->IsA("vtkDataArray"))
  {
    vtkDataArray* a = vtkArrayDownCast<vtkDataArray>(source);
    vtkIdType loci = i * this->NumberOfComponents;
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      // TODO : This just makes a double variant by default.
      //        We really should make the appropriate type of variant
      //        based on the subclass of vtkDataArray.
      vtkIdType tuple = (locj + cur) / a->GetNumberOfComponents();
      int component = static_cast<int>((locj + cur) % a->GetNumberOfComponents());
      this->SetValue(loci + cur, vtkVariant(a->GetComponent(tuple, component)));
    }
  }
  else if (source->IsA("vtkStringArray"))
  {
    vtkStringArray* a = vtkArrayDownCast<vtkStringArray>(source);
    vtkIdType loci = i * this->NumberOfComponents;
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      this->SetValue(loci + cur, vtkVariant(a->GetValue(locj + cur)));
    }
  }
  else
  {
    vtkWarningMacro("Unrecognized type is incompatible with vtkVariantArray.");
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::InsertTuple(vtkIdType i, vtkIdType j, vtkAbstractArray* source)
{
  if (source->IsA("vtkVariantArray"))
  {
    vtkVariantArray* a = vtkArrayDownCast<vtkVariantArray>(source);
    vtkIdType loci = i * this->NumberOfComponents;
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      this->InsertValue(loci + cur, a->GetValue(locj + cur));
    }
  }
  else if (source->IsA("vtkDataArray"))
  {
    vtkDataArray* a = vtkArrayDownCast<vtkDataArray>(source);
    vtkIdType loci = i * this->NumberOfComponents;
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      vtkIdType tuple = (locj + cur) / a->GetNumberOfComponents();
      int component = static_cast<int>((locj + cur) % a->GetNumberOfComponents());
      this->InsertValue(loci + cur, vtkVariant(a->GetComponent(tuple, component)));
    }
  }
  else if (source->IsA("vtkStringArray"))
  {
    vtkStringArray* a = vtkArrayDownCast<vtkStringArray>(source);
    vtkIdType loci = i * this->NumberOfComponents;
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      this->InsertValue(loci + cur, vtkVariant(a->GetValue(locj + cur)));
    }
  }
  else
  {
    vtkWarningMacro("Unrecognized type is incompatible with vtkVariantArray.");
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::InsertTuples(vtkIdList* dstIds, vtkIdList* srcIds, vtkAbstractArray* source)
{

  if (this->NumberOfComponents != source->GetNumberOfComponents())
  {
    vtkWarningMacro("Input and output component sizes do not match.");
    return;
  }

  vtkIdType numIds = dstIds->GetNumberOfIds();
  if (srcIds->GetNumberOfIds() != numIds)
  {
    vtkWarningMacro("Input and output id array sizes do not match.");
    return;
  }

  if (vtkVariantArray* va = vtkArrayDownCast<vtkVariantArray>(source))
  {
    for (vtkIdType idIndex = 0; idIndex < numIds; ++idIndex)
    {
      vtkIdType numComp = this->NumberOfComponents;
      vtkIdType srcLoc = srcIds->GetId(idIndex) * this->NumberOfComponents;
      vtkIdType dstLoc = dstIds->GetId(idIndex) * this->NumberOfComponents;
      while (numComp-- > 0)
      {
        this->InsertValue(dstLoc++, va->GetValue(srcLoc++));
      }
    }
  }
  else if (vtkDataArray* da = vtkDataArray::FastDownCast(source))
  {
    for (vtkIdType idIndex = 0; idIndex < numIds; ++idIndex)
    {
      vtkIdType numComp = this->NumberOfComponents;
      vtkIdType srcLoc = srcIds->GetId(idIndex) * this->NumberOfComponents;
      vtkIdType dstLoc = dstIds->GetId(idIndex) * this->NumberOfComponents;
      while (numComp-- > 0)
      {
        this->InsertValue(dstLoc++, da->GetVariantValue(srcLoc++));
      }
    }
  }
  else if (vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source))
  {
    for (vtkIdType idIndex = 0; idIndex < numIds; ++idIndex)
    {
      vtkIdType numComp = this->NumberOfComponents;
      vtkIdType srcLoc = srcIds->GetId(idIndex) * this->NumberOfComponents;
      vtkIdType dstLoc = dstIds->GetId(idIndex) * this->NumberOfComponents;
      while (numComp-- > 0)
      {
        this->InsertValue(dstLoc++, sa->GetVariantValue(srcLoc++));
      }
    }
  }
  else
  {
    vtkWarningMacro("Unrecognized type is incompatible with vtkVariantArray.");
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::InsertTuples(
  vtkIdType dstStart, vtkIdType n, vtkIdType srcStart, vtkAbstractArray* source)
{
  if (this->NumberOfComponents != source->GetNumberOfComponents())
  {
    vtkWarningMacro("Input and output component sizes do not match.");
    return;
  }

  vtkIdType srcEnd = srcStart + n;
  if (srcEnd > source->GetNumberOfTuples())
  {
    vtkWarningMacro("Source range exceeds array size (srcStart="
      << srcStart << ", n=" << n << ", numTuples=" << source->GetNumberOfTuples() << ").");
    return;
  }

  for (vtkIdType i = 0; i < n; ++i)
  {
    vtkIdType numComp = this->NumberOfComponents;
    vtkIdType srcLoc = (srcStart + i) * this->NumberOfComponents;
    vtkIdType dstLoc = (dstStart + i) * this->NumberOfComponents;
    while (numComp-- > 0)
    {
      this->InsertValue(dstLoc++, source->GetVariantValue(srcLoc++));
    }
  }

  this->DataChanged();
}

//------------------------------------------------------------------------------
vtkIdType vtkVariantArray::InsertNextTuple(vtkIdType j, vtkAbstractArray* source)
{
  if (source->IsA("vtkVariantArray"))
  {
    vtkVariantArray* a = vtkArrayDownCast<vtkVariantArray>(source);
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      this->InsertNextValue(a->GetValue(locj + cur));
    }
  }
  else if (source->IsA("vtkDataArray"))
  {
    vtkDataArray* a = vtkArrayDownCast<vtkDataArray>(source);
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      vtkIdType tuple = (locj + cur) / a->GetNumberOfComponents();
      int component = static_cast<int>((locj + cur) % a->GetNumberOfComponents());
      this->InsertNextValue(vtkVariant(a->GetComponent(tuple, component)));
    }
  }
  else if (source->IsA("vtkStringArray"))
  {
    vtkStringArray* a = vtkArrayDownCast<vtkStringArray>(source);
    vtkIdType locj = j * a->GetNumberOfComponents();
    for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
    {
      this->InsertNextValue(vtkVariant(a->GetValue(locj + cur)));
    }
  }
  else
  {
    vtkWarningMacro("Unrecognized type is incompatible with vtkVariantArray.");
    return -1;
  }

  this->DataChanged();
  return (this->GetNumberOfTuples() - 1);
}

//------------------------------------------------------------------------------
void* vtkVariantArray::GetVoidPointer(vtkIdType id)
{
  return this->GetPointer(id);
}

//------------------------------------------------------------------------------
void vtkVariantArray::DeepCopy(vtkAbstractArray* aa)
{
  // Do nothing on a nullptr input.
  if (!aa)
  {
    return;
  }

  // Avoid self-copy.
  if (this == aa)
  {
    return;
  }

  // If data type does not match, we can't copy.
  if (aa->GetDataType() != this->GetDataType())
  {
    vtkErrorMacro(<< "Incompatible types: tried to copy an array of type "
                  << aa->GetDataTypeAsString() << " into a variant array ");
    return;
  }

  vtkVariantArray* va = vtkArrayDownCast<vtkVariantArray>(aa);
  if (va == nullptr)
  {
    vtkErrorMacro(<< "Shouldn't Happen: Couldn't downcast array into a vtkVariantArray.");
    return;
  }

  // Free our previous memory.
  if (this->DeleteFunction)
  {
    this->DeleteFunction(this->Array);
  }

  // Copy the given array into new memory.
  this->MaxId = va->GetMaxId();
  this->Size = va->GetSize();
  this->DeleteFunction = DefaultDeleteFunction;
  this->Array = new vtkVariant[this->Size];

  for (int i = 0; i < (this->MaxId + 1); ++i)
  {
    this->Array[i] = va->Array[i];
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::InterpolateTuple(
  vtkIdType i, vtkIdList* ptIndices, vtkAbstractArray* source, double* weights)
{
  // Note: Something much more fancy could be done here, allowing
  // the source array be any data type.
  if (this->GetDataType() != source->GetDataType())
  {
    vtkErrorMacro("Cannot CopyValue from array of type " << source->GetDataTypeAsString());
    return;
  }

  if (ptIndices->GetNumberOfIds() == 0)
  {
    // nothing to do.
    return;
  }

  // We use nearest neighbour for interpolating variants.
  // First determine which is the nearest neighbour using the weights-
  // it's the index with maximum weight.
  vtkIdType nearest = ptIndices->GetId(0);
  double max_weight = weights[0];
  for (int k = 1; k < ptIndices->GetNumberOfIds(); k++)
  {
    if (weights[k] > max_weight)
    {
      nearest = k;
    }
  }

  this->InsertTuple(i, nearest, source);
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::InterpolateTuple(vtkIdType i, vtkIdType id1, vtkAbstractArray* source1,
  vtkIdType id2, vtkAbstractArray* source2, double t)
{
  // Note: Something much more fancy could be done here, allowing
  // the source array to be any data type.
  if (source1->GetDataType() != VTK_VARIANT || source2->GetDataType() != VTK_VARIANT)
  {
    vtkErrorMacro("All arrays to InterpolateValue() must be of same type.");
    return;
  }

  if (t >= 0.5)
  {
    // Use p2
    this->InsertTuple(i, id2, source2);
  }
  else
  {
    // Use p1.
    this->InsertTuple(i, id1, source1);
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::Squeeze()
{
  this->ResizeAndExtend(this->MaxId + 1);
}

//------------------------------------------------------------------------------
vtkTypeBool vtkVariantArray::Resize(vtkIdType sz)
{
  vtkVariant* newArray;
  vtkIdType newSize = sz * this->GetNumberOfComponents();

  if (newSize == this->Size)
  {
    return 1;
  }

  if (newSize <= 0)
  {
    this->Initialize();
    return 1;
  }

  newArray = new vtkVariant[newSize];
  if (!newArray)
  {
    vtkErrorMacro(<< "Cannot allocate memory\n");
    return 0;
  }

  if (this->Array)
  {
    vtkIdType numCopy = (newSize < this->Size ? newSize : this->Size);

    for (vtkIdType i = 0; i < numCopy; ++i)
    {
      newArray[i] = this->Array[i];
    }

    if (this->DeleteFunction)
    {
      this->DeleteFunction(this->Array);
    }
  }

  if (newSize < this->Size)
  {
    this->MaxId = newSize - 1;
  }
  this->Size = newSize;
  this->Array = newArray;
  this->DeleteFunction = DefaultDeleteFunction;
  this->DataChanged();
  return 1;
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetVoidArray(void* arr, vtkIdType size, int save)
{
  this->SetArray(static_cast<vtkVariant*>(arr), size, save);
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetVoidArray(void* arr, vtkIdType size, int save, int deleteM)
{
  this->SetArray(static_cast<vtkVariant*>(arr), size, save, deleteM);
  this->DataChanged();
}

//------------------------------------------------------------------------------
unsigned long vtkVariantArray::GetActualMemorySize() const
{
  // NOTE: Currently does not take into account the "pointed to" data.
  size_t totalSize = 0;
  size_t numPrims = static_cast<size_t>(this->GetSize());

  totalSize = numPrims * sizeof(vtkVariant);

  return static_cast<unsigned long>(ceil(static_cast<double>(totalSize) / 1024.0)); // kibibytes
}

//------------------------------------------------------------------------------
int vtkVariantArray::IsNumeric() const
{
  return 0;
}

//------------------------------------------------------------------------------
vtkArrayIterator* vtkVariantArray::NewIterator()
{
  vtkArrayIteratorTemplate<vtkVariant>* iter = vtkArrayIteratorTemplate<vtkVariant>::New();
  iter->Initialize(this);
  return iter;
}

//
//
// Additional functions
//
//

//------------------------------------------------------------------------------
vtkVariant& vtkVariantArray::GetValue(vtkIdType id) const
{
  return this->Array[id];
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetValue(vtkIdType id, vtkVariant value)
{
  this->Array[id] = value;
  this->DataElementChanged(id);
}

//------------------------------------------------------------------------------
void vtkVariantArray::InsertValue(vtkIdType id, vtkVariant value)
{
  if (id >= this->Size)
  {
    if (!this->ResizeAndExtend(id + 1))
    {
      return;
    }
  }
  this->Array[id] = value;
  if (id > this->MaxId)
  {
    this->MaxId = id;
  }
  this->DataElementChanged(id);
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetVariantValue(vtkIdType id, vtkVariant value)
{
  this->SetValue(id, value);
}

//------------------------------------------------------------------------------
void vtkVariantArray::InsertVariantValue(vtkIdType id, vtkVariant value)
{
  this->InsertValue(id, value);
}

//------------------------------------------------------------------------------
vtkIdType vtkVariantArray::InsertNextValue(vtkVariant value)
{
  this->InsertValue(++this->MaxId, value);
  this->DataElementChanged(this->MaxId);
  return this->MaxId;
}

//------------------------------------------------------------------------------
vtkVariant* vtkVariantArray::GetPointer(vtkIdType id)
{
  return this->Array + id;
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetArray(vtkVariant* arr, vtkIdType size, int save, int deleteMethod)
{
  if ((this->Array) && (this->DeleteFunction))
  {
    vtkDebugMacro(<< "Deleting the array...");
    this->DeleteFunction(this->Array);
  }
  else
  {
    vtkDebugMacro(<< "Warning, array not deleted, but will point to new array.");
  }

  vtkDebugMacro(<< "Setting array to: " << arr);

  this->Array = arr;
  this->Size = size;
  this->MaxId = size - 1;

  if (save != 0)
  {
    this->DeleteFunction = nullptr;
  }
  else if (deleteMethod == VTK_DATA_ARRAY_DELETE || deleteMethod == VTK_DATA_ARRAY_USER_DEFINED)
  {
    this->DeleteFunction = DefaultDeleteFunction;
  }
  else if (deleteMethod == VTK_DATA_ARRAY_ALIGNED_FREE)
  {
#ifdef _WIN32
    this->DeleteFunction = _aligned_free;
#else
    this->DeleteFunction = free;
#endif
  }
  else if (deleteMethod == VTK_DATA_ARRAY_FREE)
  {
    this->DeleteFunction = free;
  }

  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkVariantArray::SetArrayFreeFunction(void (*callback)(void*))
{
  this->DeleteFunction = callback;
}

//------------------------------------------------------------------------------
vtkVariant* vtkVariantArray::ResizeAndExtend(vtkIdType sz)
{
  vtkVariant* newArray;
  vtkIdType newSize;

  if (sz > this->Size)
  {
    // Requested size is bigger than current size.  Allocate enough
    // memory to fit the requested size and be more than double the
    // currently allocated memory.
    newSize = this->Size + sz;
  }
  else if (sz == this->Size)
  {
    // Requested size is equal to current size.  Do nothing.
    return this->Array;
  }
  else
  {
    // Requested size is smaller than current size.  Squeeze the
    // memory.
    newSize = sz;
  }

  if (newSize <= 0)
  {
    this->Initialize();
    return nullptr;
  }

  newArray = new vtkVariant[newSize];
  if (!newArray)
  {
    vtkErrorMacro("Cannot allocate memory\n");
    return nullptr;
  }

  if (this->Array)
  {
    // can't use memcpy here
    vtkIdType numCopy = (newSize < this->Size ? newSize : this->Size);
    for (vtkIdType i = 0; i < numCopy; ++i)
    {
      newArray[i] = this->Array[i];
    }
    if (this->DeleteFunction)
    {
      this->DeleteFunction(this->Array);
    }
  }

  if (newSize < this->Size)
  {
    this->MaxId = newSize - 1;
  }
  this->Size = newSize;
  this->Array = newArray;
  this->DeleteFunction = DefaultDeleteFunction;
  this->DataChanged();

  return this->Array;
}

//------------------------------------------------------------------------------
void vtkVariantArray::UpdateLookup()
{
  if (!this->Lookup)
  {
    this->Lookup = new vtkVariantArrayLookup();
    this->Lookup->SortedArray = vtkVariantArray::New();
    this->Lookup->IndexArray = vtkIdList::New();
  }
  if (this->Lookup->Rebuild)
  {
    int numComps = this->GetNumberOfComponents();
    vtkIdType numTuples = this->GetNumberOfTuples();
    this->Lookup->SortedArray->DeepCopy(this);
    this->Lookup->IndexArray->SetNumberOfIds(numComps * numTuples);
    for (vtkIdType i = 0; i < numComps * numTuples; i++)
    {
      this->Lookup->IndexArray->SetId(i, i);
    }
    vtkSortDataArray::Sort(this->Lookup->SortedArray, this->Lookup->IndexArray);
    this->Lookup->Rebuild = false;
    this->Lookup->CachedUpdates.clear();
  }
}

//------------------------------------------------------------------------------
vtkIdType vtkVariantArray::LookupValue(vtkVariant value)
{
  this->UpdateLookup();

  // First look into the cached updates, to see if there were any
  // cached changes. Find an equivalent element in the set of cached
  // indices for this value. Some of the indices may have changed
  // values since the cache was built, so we need to do this equality
  // check.
  typedef vtkVariantCachedUpdates::iterator CacheIterator;
  CacheIterator cached = this->Lookup->CachedUpdates.lower_bound(value),
                cachedEnd = this->Lookup->CachedUpdates.end();
  while (cached != cachedEnd)
  {
    // Check that we are still in the same equivalence class as the
    // value.
    if (value == (*cached).first)
    {
      // Check that the value in the original array hasn't changed.
      vtkVariant currentValue = this->GetValue(cached->second);
      if (value == currentValue)
      {
        return (*cached).second;
      }
    }
    else
    {
      break;
    }

    ++cached;
  }

  // Perform a binary search of the sorted array using STL equal_range.
  int numComps = this->Lookup->SortedArray->GetNumberOfComponents();
  vtkIdType numTuples = this->Lookup->SortedArray->GetNumberOfTuples();
  vtkVariant* ptr = this->Lookup->SortedArray->GetPointer(0);
  vtkVariant* ptrEnd = ptr + numComps * numTuples;
  vtkVariant* found = std::lower_bound(ptr, ptrEnd, value, vtkVariantLessThan());

  // Find an index with a matching value. Non-matching values might
  // show up here when the underlying value at that index has been
  // changed (so the sorted array is out-of-date).
  vtkIdType offset = static_cast<vtkIdType>(found - ptr);
  while (found != ptrEnd)
  {
    // Check whether we still have a value equivalent to what we're
    // looking for.
    if (value == *found)
    {
      // Check that the value in the original array hasn't changed.
      vtkIdType index = this->Lookup->IndexArray->GetId(offset);
      vtkVariant currentValue = this->GetValue(index);
      if (value == currentValue)
      {
        return index;
      }
    }
    else
    {
      break;
    }

    ++found;
    ++offset;
  }

  return -1;
}

//------------------------------------------------------------------------------
void vtkVariantArray::LookupValue(vtkVariant value, vtkIdList* ids)
{
  this->UpdateLookup();
  ids->Reset();

  // First look into the cached updates, to see if there were any
  // cached changes. Find an equivalent element in the set of cached
  // indices for this value. Some of the indices may have changed
  // values since the cache was built, so we need to do this equality
  // check.
  typedef vtkVariantCachedUpdates::iterator CacheIterator;
  std::pair<CacheIterator, CacheIterator> cached = this->Lookup->CachedUpdates.equal_range(value);
  while (cached.first != cached.second)
  {
    // Check that the value in the original array hasn't changed.
    vtkVariant currentValue = this->GetValue(cached.first->second);
    if (cached.first->first == currentValue)
    {
      ids->InsertNextId(cached.first->second);
    }

    ++cached.first;
  }

  // Perform a binary search of the sorted array using STL equal_range.
  int numComps = this->GetNumberOfComponents();
  vtkIdType numTuples = this->GetNumberOfTuples();
  vtkVariant* ptr = this->Lookup->SortedArray->GetPointer(0);
  vtkVariant* ptrEnd = ptr + numComps * numTuples;
  std::pair<vtkVariant*, vtkVariant*> found =
    std::equal_range(ptr, ptrEnd, value, vtkVariantLessThan());

  // Add the indices of the found items to the ID list.
  vtkIdType offset = static_cast<vtkIdType>(found.first - ptr);
  while (found.first != found.second)
  {
    // Check that the value in the original array hasn't changed.
    vtkIdType index = this->Lookup->IndexArray->GetId(offset);
    vtkVariant currentValue = this->GetValue(index);
    if (*(found.first) == currentValue)
    {
      ids->InsertNextId(index);
    }

    ++found.first;
    ++offset;
  }
}

//------------------------------------------------------------------------------
void vtkVariantArray::DataChanged()
{
  if (this->Lookup)
  {
    this->Lookup->Rebuild = true;
  }
}

//------------------------------------------------------------------------------
void vtkVariantArray::DataElementChanged(vtkIdType id)
{
  if (this->Lookup)
  {
    if (this->Lookup->Rebuild)
    {
      // We're already going to rebuild the lookup table. Do nothing.
      return;
    }

    if (this->Lookup->CachedUpdates.size() > static_cast<size_t>(this->GetNumberOfTuples() / 10))
    {
      // At this point, just rebuild the full table.
      this->Lookup->Rebuild = true;
    }
    else
    {
      // Insert this change into the set of cached updates
      std::pair<const vtkVariant, vtkIdType> value(this->GetValue(id), id);
      this->Lookup->CachedUpdates.insert(value);
    }
  }
}

//------------------------------------------------------------------------------
void vtkVariantArray::ClearLookup()
{
  delete this->Lookup;
  this->Lookup = nullptr;
}