// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-FileCopyrightText: Copyright 2004 Sandia Corporation
// SPDX-License-Identifier: BSD-3-Clause

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

#include "vtkStdString.h"

#include "vtkStringArray.h"

#include "vtkArrayIteratorTemplate.h"
#include "vtkCharArray.h"
#include "vtkIdList.h"
#include "vtkObjectFactory.h"
#include "vtkSMPTools.h"
#include "vtkSortDataArray.h"

#include <algorithm>
#include <map>
#include <utility>
#include <vector>

// Map containing updates to a vtkStringArray that have occurred
// since we last build the vtkStringArrayLookup.
typedef std::multimap<vtkStdString, vtkIdType> vtkStringCachedUpdates;

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

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

vtkStandardNewMacro(vtkStringArray);
vtkStandardExtendedNewMacro(vtkStringArray);

//------------------------------------------------------------------------------

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

//------------------------------------------------------------------------------

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

//------------------------------------------------------------------------------
vtkStringArray* vtkStringArray::FastDownCast(vtkAbstractArray* source)
{
  if (source)
  {
    switch (source->GetArrayType())
    {
      case vtkStringArray::ArrayTypeTag::value:
        return static_cast<vtkStringArray*>(source);
      default:
        break;
    }
  }
  return nullptr;
}

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

//------------------------------------------------------------------------------
// This method lets the user specify data to be held by the array.  The
// array argument is a pointer to the data.  size is the size of
// the array supplied by the user.  Set save to 1 to keep the class
// from deleting the array when it cleans up or reallocates memory.
// The class uses the actual array provided; it does not copy the data
// from the suppled array.
void vtkStringArray::SetArray(ValueType* array, 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: " << array);

  this->Array = array;
  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 vtkStringArray::SetArrayFreeFunction(void (*callback)(void*))
{
  this->DeleteFunction = callback;
}

//------------------------------------------------------------------------------
// Allocate memory for this array. Delete old storage only if necessary.

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

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

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

  return 1;
}

//------------------------------------------------------------------------------
// Release storage and reset array to initial state.

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

//------------------------------------------------------------------------------
bool vtkStringArray::CopyComponent(int dstComponent, vtkAbstractArray* src, int srcComponent)
{
  auto* source = vtkStringArray::SafeDownCast(src);
  if (!source || source->GetNumberOfTuples() != this->GetNumberOfTuples() || srcComponent < 0 ||
    srcComponent >= source->GetNumberOfComponents() || dstComponent < 0 ||
    dstComponent >= this->GetNumberOfComponents())
  {
    return false;
  }

  vtkIdType nn = this->GetNumberOfTuples();
  vtkSMPTools::For(0, nn,
    [this, dstComponent, source, srcComponent](vtkIdType begin, vtkIdType end)
    {
      vtkIdType ndc = this->GetNumberOfComponents();
      vtkIdType nsc = source->GetNumberOfComponents();
      for (vtkIdType ii = begin; ii < end; ++ii)
      {
        this->SetValue(ii * ndc + dstComponent, source->GetValue(ii * nsc + srcComponent));
      }
    });
  return true;
}

//------------------------------------------------------------------------------
// Deep copy of another string array.

void vtkStringArray::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 string array ");
    return;
  }

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

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

  this->Superclass::DeepCopy(aa); // copy information objects.

  // Copy the given array into new memory.
  this->NumberOfComponents = aa->GetNumberOfComponents();
  this->MaxId = fa->GetMaxId();
  this->Size = fa->GetSize();
  this->DeleteFunction = DefaultDeleteFunction;
  this->Array = new ValueType[this->Size];

  for (int i = 0; i < this->Size; ++i)
  {
    this->Array[i] = fa->Array[i];
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
// Interpolate array value from other array value given the
// indices and associated interpolation weights.
// This method assumes that the two arrays are of the same time.
void vtkStringArray::InterpolateTuple(
  vtkIdType i, vtkIdList* ptIndices, vtkAbstractArray* source, double* weights)
{
  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 strings.
  // 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 = ptIndices->GetId(k);
      max_weight = weights[k];
    }
  }

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

//------------------------------------------------------------------------------
// Interpolate value from the two values, p1 and p2, and an
// interpolation factor, t. The interpolation factor ranges from (0,1),
// with t=0 located at p1. This method assumes that the three arrays are of
// the same type. p1 is value at index id1 in fromArray1, while, p2 is
// value at index id2 in fromArray2.
void vtkStringArray::InterpolateTuple(vtkIdType i, vtkIdType id1, vtkAbstractArray* source1,
  vtkIdType id2, vtkAbstractArray* source2, double t)
{
  if (source1->GetDataType() != vtkStringArray::DataTypeTag::value ||
    source2->GetDataType() != vtkStringArray::DataTypeTag::value)
  {
    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);
  }
}

//------------------------------------------------------------------------------
void vtkStringArray::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";
  }
}

//------------------------------------------------------------------------------
// Protected function does "reallocate"

vtkStringArray::ValueType* vtkStringArray::ResizeAndExtend(vtkIdType sz)
{
  ValueType* 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 + 1) + 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 ValueType[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;
}

//------------------------------------------------------------------------------
vtkTypeBool vtkStringArray::Resize(vtkIdType sz)
{
  ValueType* newArray;
  vtkIdType newSize = sz * this->NumberOfComponents;

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

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

  newArray = new ValueType[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 = DefaultDeleteFunction;
      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;
}

//------------------------------------------------------------------------------
vtkStringArray::ValueType* vtkStringArray::WritePointer(vtkIdType id, vtkIdType number)
{
  vtkIdType newSize = id + number;
  if (newSize > this->Size)
  {
    this->ResizeAndExtend(newSize);
  }
  if ((--newSize) > this->MaxId)
  {
    this->MaxId = newSize;
  }
  this->DataChanged();
  return this->Array + id;
}

//------------------------------------------------------------------------------
void vtkStringArray::InsertValue(vtkIdType id, ValueType f)
{
  if (id >= this->Size)
  {
    if (!this->ResizeAndExtend(id + 1))
    {
      return;
    }
  }
  this->Array[id] = f;
  this->MaxId = std::max(id, this->MaxId);
  this->DataElementChanged(id);
}

//------------------------------------------------------------------------------
vtkIdType vtkStringArray::InsertNextValue(ValueType f)
{
  this->InsertValue(++this->MaxId, f);
  this->DataElementChanged(this->MaxId);
  return this->MaxId;
}

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

//------------------------------------------------------------------------------
unsigned long vtkStringArray::GetActualMemorySize() const
{
  size_t totalSize = 0;
  size_t numPrims = static_cast<size_t>(this->GetSize());

  for (size_t i = 0; i < numPrims; ++i)
  {
    totalSize += sizeof(ValueType);
    totalSize += this->Array[i].size() * sizeof(ValueType::value_type);
  }

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

//------------------------------------------------------------------------------
vtkIdType vtkStringArray::GetDataSize() const
{
  size_t size = 0;
  size_t numStrs = static_cast<size_t>(this->GetMaxId() + 1);
  for (size_t i = 0; i < numStrs; i++)
  {
    size += this->Array[i].size() + 1;
    // (+1) for termination character.
  }
  return static_cast<vtkIdType>(size);
}

//------------------------------------------------------------------------------
// Set the tuple at the ith location using the jth tuple in the source array.
// This method assumes that the two arrays have the same type
// and structure. Note that range checking and memory allocation is not
// performed; use in conjunction with SetNumberOfTuples() to allocate space.
void vtkStringArray::SetTuple(vtkIdType i, vtkIdType j, vtkAbstractArray* source)
{
  vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source);
  if (!sa)
  {
    vtkWarningMacro("Input and outputs array data types do not match.");
    return;
  }

  vtkIdType loci = i * this->NumberOfComponents;
  vtkIdType locj = j * sa->GetNumberOfComponents();
  for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
  {
    this->SetValue(loci + cur, sa->GetValue(locj + cur));
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
// Insert the jth tuple in the source array, at ith location in this array.
// Note that memory allocation is performed as necessary to hold the data.
void vtkStringArray::InsertTuple(vtkIdType i, vtkIdType j, vtkAbstractArray* source)
{
  vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source);
  if (!sa)
  {
    vtkWarningMacro("Input and outputs array data types do not match.");
    return;
  }

  vtkIdType loci = i * this->NumberOfComponents;
  vtkIdType locj = j * sa->GetNumberOfComponents();
  for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
  {
    this->InsertValue(loci + cur, sa->GetValue(locj + cur));
  }
  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkStringArray::InsertTuples(vtkIdList* dstIds, vtkIdList* srcIds, vtkAbstractArray* source)
{
  vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source);
  if (!sa)
  {
    vtkWarningMacro("Input and outputs array data types do not match.");
    return;
  }

  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;
  }

  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->GetValue(srcLoc++));
    }
  }

  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkStringArray::InsertTuplesStartingAt(
  vtkIdType dstStart, vtkIdList* srcIds, vtkAbstractArray* source)
{
  vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source);
  if (!sa)
  {
    vtkWarningMacro("Input and outputs array data types do not match.");
    return;
  }

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

  vtkIdType numIds = srcIds->GetNumberOfIds();

  for (vtkIdType idIndex = 0; idIndex < numIds; ++idIndex)
  {
    vtkIdType numComp = this->NumberOfComponents;
    vtkIdType srcLoc = srcIds->GetId(idIndex) * this->NumberOfComponents;
    vtkIdType dstLoc = (dstStart + idIndex) * this->NumberOfComponents;
    while (numComp-- > 0)
    {
      this->InsertValue(dstLoc++, sa->GetValue(srcLoc++));
    }
  }

  this->DataChanged();
}

//------------------------------------------------------------------------------
void vtkStringArray::InsertTuples(
  vtkIdType dstStart, vtkIdType n, vtkIdType srcStart, vtkAbstractArray* source)
{
  vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source);
  if (!sa)
  {
    vtkWarningMacro("Input and outputs array data types do not match.");
    return;
  }

  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++, sa->GetValue(srcLoc++));
    }
  }

  this->DataChanged();
}

//------------------------------------------------------------------------------
// Insert the jth tuple in the source array, at the end in this array.
// Note that memory allocation is performed as necessary to hold the data.
// Returns the location at which the data was inserted.
vtkIdType vtkStringArray::InsertNextTuple(vtkIdType j, vtkAbstractArray* source)
{
  vtkStringArray* sa = vtkArrayDownCast<vtkStringArray>(source);
  if (!sa)
  {
    vtkWarningMacro("Input and outputs array data types do not match.");
    return -1;
  }

  vtkIdType locj = j * sa->GetNumberOfComponents();
  for (vtkIdType cur = 0; cur < this->NumberOfComponents; cur++)
  {
    this->InsertNextValue(sa->GetValue(locj + cur));
  }
  this->DataChanged();
  return (this->GetNumberOfTuples() - 1);
}

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

vtkStringArray::ValueType& vtkStringArray::GetValue(vtkIdType id)
{
  return this->Array[id];
}

//------------------------------------------------------------------------------
void vtkStringArray::GetTuples(vtkIdList* indices, vtkAbstractArray* aa)
{
  if (aa == nullptr)
  {
    vtkErrorMacro(<< "GetTuples: Output array is null!");
    return;
  }

  vtkStringArray* output = vtkArrayDownCast<vtkStringArray>(aa);

  if (output == nullptr)
  {
    vtkErrorMacro(<< "Can't copy values from a string array into an array "
                  << "of type " << aa->GetDataTypeAsString());
    return;
  }

  for (vtkIdType i = 0; i < indices->GetNumberOfIds(); ++i)
  {
    vtkIdType index = indices->GetId(i);
    output->SetValue(i, this->GetValue(index));
  }
}

//------------------------------------------------------------------------------
void vtkStringArray::GetTuples(vtkIdType startIndex, vtkIdType endIndex, vtkAbstractArray* aa)
{
  if (aa == nullptr)
  {
    vtkErrorMacro(<< "GetTuples: Output array is null!");
    return;
  }

  vtkStringArray* output = vtkArrayDownCast<vtkStringArray>(aa);

  if (output == nullptr)
  {
    vtkErrorMacro(<< "Can't copy values from a string array into an array "
                  << "of type " << aa->GetDataTypeAsString());
    return;
  }

  for (vtkIdType i = 0; i < (endIndex - startIndex) + 1; ++i)
  {
    vtkIdType index = startIndex + i;
    output->SetValue(i, this->GetValue(index));
  }
}

//------------------------------------------------------------------------------
void vtkStringArray::UpdateLookup()
{
  if (!this->Lookup)
  {
    this->Lookup = new vtkStringArrayLookup();
    this->Lookup->SortedArray = vtkStringArray::New();
    this->Lookup->IndexArray = vtkIdList::New();
  }
  if (this->Lookup->Rebuild)
  {
    int numComps = this->GetNumberOfComponents();
    vtkIdType numTuples = this->GetNumberOfTuples();
    this->Lookup->SortedArray->Initialize();
    this->Lookup->SortedArray->SetNumberOfComponents(numComps);
    this->Lookup->SortedArray->SetNumberOfTuples(numTuples);
    this->Lookup->IndexArray->SetNumberOfIds(numComps * numTuples);
    std::vector<std::pair<ValueType, vtkIdType>> v;
    v.reserve(numComps * numTuples);
    for (vtkIdType i = 0; i < numComps * numTuples; i++)
    {
      v.emplace_back(this->Array[i], i);
    }
    std::sort(v.begin(), v.end());
    for (vtkIdType i = 0; i < numComps * numTuples; i++)
    {
      this->Lookup->SortedArray->SetValue(i, v[i].first);
      this->Lookup->IndexArray->SetId(i, v[i].second);
    }
    this->Lookup->Rebuild = false;
    this->Lookup->CachedUpdates.clear();
  }
}

//------------------------------------------------------------------------------
vtkIdType vtkStringArray::LookupValue(vtkVariant var)
{
  return this->LookupValue(var.ToString());
}

//------------------------------------------------------------------------------
void vtkStringArray::LookupValue(vtkVariant var, vtkIdList* ids)
{
  this->LookupValue(var.ToString(), ids);
}

//------------------------------------------------------------------------------
vtkIdType vtkStringArray::LookupValue(const ValueType& 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 vtkStringCachedUpdates::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.
      ValueType currentValue = this->GetValue(cached->second);
      if (value == currentValue)
      {
        return cached->second;
      }
    }
    else
    {
      break;
    }

    ++cached;
  }

  int numComps = this->Lookup->SortedArray->GetNumberOfComponents();
  vtkIdType numTuples = this->Lookup->SortedArray->GetNumberOfTuples();
  ValueType* ptr = this->Lookup->SortedArray->GetPointer(0);
  ValueType* ptrEnd = ptr + numComps * numTuples;
  ValueType* found = std::lower_bound(ptr, ptrEnd, value);

  // 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);
      ValueType currentValue = this->GetValue(index);
      if (value == currentValue)
      {
        return index;
      }
    }
    else
    {
      break;
    }

    ++found;
    ++offset;
  }

  return -1;
}

//------------------------------------------------------------------------------
void vtkStringArray::LookupValue(const ValueType& 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 vtkStringCachedUpdates::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.
    ValueType 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();
  ValueType* ptr = this->Lookup->SortedArray->GetPointer(0);
  std::pair<ValueType*, ValueType*> found =
    std::equal_range(ptr, ptr + numComps * numTuples, value);

  // 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);
    ValueType currentValue = this->GetValue(index);
    if (*found.first == currentValue)
    {
      ids->InsertNextId(index);
    }

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

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

//------------------------------------------------------------------------------
void vtkStringArray::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 ValueType, vtkIdType> value(this->GetValue(id), id);
      this->Lookup->CachedUpdates.insert(value);
    }
  }
}

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

//------------------------------------------------------------------------------

//
//
// Below here are interface methods to allow values to be inserted as
// const char * instead of ValueType.  Yes, they're trivial.  The
// wrapper code needs them.
//
//

void vtkStringArray::SetValue(vtkIdType id, const char* value)
{
  if (value)
  {
    this->SetValue(id, ValueType(value));
  }
}

void vtkStringArray::InsertValue(vtkIdType id, const char* value)
{
  if (value)
  {
    this->InsertValue(id, ValueType(value));
  }
}

void vtkStringArray::SetVariantValue(vtkIdType id, vtkVariant value)
{
  this->SetValue(id, value.ToString());
}

void vtkStringArray::InsertVariantValue(vtkIdType id, vtkVariant value)
{
  this->InsertValue(id, value.ToString());
}

vtkIdType vtkStringArray::InsertNextValue(const char* value)
{
  if (value)
  {
    return this->InsertNextValue(ValueType(value));
  }
  return this->MaxId;
}

vtkIdType vtkStringArray::LookupValue(const char* value)
{
  if (value)
  {
    return this->LookupValue(ValueType(value));
  }
  return -1;
}

void vtkStringArray::LookupValue(const char* value, vtkIdList* ids)
{
  if (value)
  {
    this->LookupValue(ValueType(value), ids);
    return;
  }
  ids->Reset();
}

//------------------------------------------------------------------------------
VTK_ABI_NAMESPACE_END