//=========================================================================
//  Copyright (c) Kitware, Inc.
//  All rights reserved.
//  See LICENSE.txt 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.
//=========================================================================
#include "smtk/model/Entity.h"

#include "smtk/common/StringUtil.h"

#include <algorithm>
#include <cctype>
#include <map>
#include <set>
#include <vector>

#include <sstream>

//#include <boost/variant.hpp>

using namespace std;
using namespace smtk::common;

namespace smtk
{
namespace model
{

static const char* cellNamesByDimensionSingular[] = { "vertex", "edge", "face", "volume",
  "spacetime", "mixed-dimension cell" };

static const char* cellNamesByDimensionPlural[] = { "vertices", "edges", "faces", "volumes",
  "spacetimes", "mixed-dimension cells" };

static const char* auxGeomNamesByDimensionSingular[] = { "auxiliary point", "auxiliary curve",
  "auxiliary surface", "auxiliary volume", "auxiliary spacetime", "auxiliary geometry" };

static const char* auxGeomNamesByDimensionPlural[] = { "auxiliary points", "auxiliary curves",
  "auxiliary surfaces", "auxiliary volumes", "auxiliary spacetimes", "auxiliary geometries" };

static const char* entityTypeNames[] = { "cell", "use", "shell", "group", "model", "instance",
  "session", "aux_geom", "concept" };

/**\class smtk::model::Entity
  *
  * Store links between named entities.
  */

/// The default constructor creates an invalid link.
Entity::Entity()
  : m_entityFlags(INVALID)
  , m_firstInvalid(-1)
{
}

/// Construct a link with the given \a dimension with a type specified by \a entityFlags.
Entity::Entity(BitFlags entFlags, int dim)
  : m_entityFlags(entFlags)
  , m_firstInvalid(-1)
{
  // Override the dimension bits if the dimension is specified
  if (dim >= 0 && dim <= 4)
  {
    // Clear the dimension bits:
    this->m_entityFlags &= ~(DIMENSION_0 | DIMENSION_1 | DIMENSION_2 | DIMENSION_3 | DIMENSION_4);
    // Now add in the *proper* dimension bit to match m_dimension:
    this->m_entityFlags |= (1 << dim);
  }
}

/**\brief Return the bit vector describing the type and attributes of the associated entity.
  *
  * \sa smtk::model::EntityTypeBits
  */
BitFlags Entity::entityFlags() const
{
  return this->m_entityFlags;
}

bool Entity::setEntityFlags(BitFlags flags)
{
  bool allowed = false;
  if (this->m_entityFlags == INVALID)
  {
    this->m_entityFlags = flags;
    allowed = true;
  }
  else
  {
    // Only allow changes to properties, not the entity type
    // after it has been set to something valid.
    // Otherwise, craziness may ensue.
    if ((flags & ANY_ENTITY) == (this->m_entityFlags & ANY_ENTITY))
    {
      this->m_entityFlags = flags;
      allowed = true;
    }
  }
  return allowed;
}

/**\brief Return the dimension of the associated entity.
  *
  * When \a entityFlags() includes the CELL bit, this must be in [0,3] for
  * the cell to be considered valid.
  * For the SHELL bit, this must be in [1,3] for the shell to be valid.
  * For the USE bit, this must be in [0,2] for the use to be valid.
  *
  * For the GROUP bit, the integer returned should be treated as a bit
  * vector. Valid values include [0,15].
  */
int Entity::dimension() const
{
  BitFlags dimBits = this->m_entityFlags & ANY_DIMENSION;
  if ((dimBits != 0) & ((dimBits & (dimBits - 1)) == 0))
  { // dimBits is exactly a power of two:
    switch (dimBits)
    {
      case DIMENSION_0:
        return 0;
      case DIMENSION_1:
        return 1;
      case DIMENSION_2:
        return 2;
      case DIMENSION_3:
        return 3;
      case DIMENSION_4:
        return 4;
      default:
        return -2; // A power of two, but not one we know
    }
  }
  // dimBits is NOT a power of two:
  return -1;
}

BitFlags Entity::dimensionBits() const
{
  return this->m_entityFlags & ANY_DIMENSION;
}

UUIDArray& Entity::relations()
{
  return this->m_relations;
}
const UUIDArray& Entity::relations() const
{
  return this->m_relations;
}

/**\brief Append a relation \a b to this entity's list of relations.
  *
  * This returns the index of \a b in the entity's list of relations.
  *
  * If \a useHoles is true, then a slower algorithm is used that
  * replaces the first invalid relation with \a b (or appends \a b if
  * there are no invalid relations). Once the hole is used, a linear-time
  * search is used to find the next hole. If you will be performing
  * many intermixed insertions and invalidations, you may wish to
  * set \a useHoles to false. Also, if you are restoring an Entity
  * from an archive, you should pass false.
  */
int Entity::appendRelation(const UUID& b, bool useHoles)
{
  int idx;
  if (useHoles)
  {
    if ((idx = this->consumeInvalidIndex(b)) >= 0)
      return idx;
  }
  idx = static_cast<int>(this->m_relations.size());
  this->m_relations.push_back(b);
  return idx;
}

Entity& Entity::pushRelation(const UUID& b)
{
  this->m_relations.push_back(b);
  return *this;
}

/**\brief Remove the relation from the entity. Do not use this unless you know what you are doing.
  *
  * Instead of this method, you should probably use invalidateRelation().
  *
  * This removes the first array entry holding \a b.
  * When the relation \a b is not at the end of the entity's array of relations,
  * the index of all following relations is reduced by one (because the array is
  * compacted).
  * Since arrangements store indices into this list of relations, you should only
  * call removeRelation when you also update all of the Entity's arrangements.
  */
Entity& Entity::removeRelation(const UUID& b)
{
  UUIDArray& arr(this->m_relations);
  UUIDArray::size_type size = arr.size();
  UUIDArray::size_type curr;
  for (curr = 0; curr < size; ++curr)
  {
    if (arr[curr] == b)
    {
      arr.erase(arr.begin() + curr);
      --curr;
      --size;
    }
  }
  return *this;
}

/**\brief Completely clear the entire list of related entities.
  *
  * \warning This invalidates all Arrangement information for the entity.
  *          Do not invoke this unless you know there are no Arrangements.
  */
void Entity::resetRelations()
{
  this->m_relations.clear();
  this->m_firstInvalid = -1;
}

/**\brief Find the given relation \a r and return its index, inserting it if not present.
  */
int Entity::findOrAppendRelation(const UUID& r)
{
  for (UUIDArray::size_type i = 0; i < this->m_relations.size(); ++i)
  {
    if (this->m_relations[i] == r)
    {
      return static_cast<int>(i);
    }
  }
  int idx = static_cast<int>(this->m_relations.size());
  this->m_relations.push_back(r);
  return idx;
}

/**\brief Find the given relation \a r and invalidate its index.
  *
  * This returns the invalidated index if the relation was found
  * and -1 if \a r was not present.
  */
int Entity::invalidateRelation(const UUID& r)
{
  for (UUIDArray::size_type i = 0; i < this->m_relations.size(); ++i)
  {
    if (this->m_relations[i] == r)
    {
      return this->invalidateRelationByIndex(static_cast<int>(i));
    }
  }
  return -1;
}

/**\brief Given a valid index, invalidate the UUID at that index.
  *
  * This returns the index upon success or -1 upon failure.
  */
int Entity::invalidateRelationByIndex(int relIdx)
{
  if (relIdx < 0 || relIdx >= static_cast<int>(this->m_relations.size()))
    return -1;

  this->m_relations[relIdx] = smtk::common::UUID::null();
  if (this->m_firstInvalid < 0 || (this->m_firstInvalid >= 0 && relIdx < this->m_firstInvalid))
    this->m_firstInvalid = relIdx;
  return relIdx;
}

/**\brief Return a list the dimension bits set in \a entityFlags.
  *
  * The \a plural reference is set to true if \a flags has
  * more than 1 dimension bit set. Otherwise, it returns false.
  */
std::string Entity::flagDimensionList(BitFlags flags, bool& plural)
{
  std::ostringstream result;
  bool needSeparator = false;
  plural = false;
  for (int i = 0; i <= 4; ++i)
  {
    if (flags & (1 << i))
    {
      if (needSeparator)
      {
        result << ", ";
        plural = true;
      }
      else
      {
        needSeparator = true;
      }
      result << i;
    }
  }
  return result.str();
}

// If you change this, you may need to change flagSummmary/flagDescription/defaultNameFromCounters
std::string Entity::flagSummaryHelper(BitFlags flags, int form)
{
  std::string result;
  if (flags & GROUP_ENTITY)
    flags &= (~ENTITY_MASK) | GROUP_ENTITY; // omit all other entity types for switch statement;

  switch (flags & ENTITY_MASK)
  {
    case CELL_ENTITY:
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0:
          result = form ? cellNamesByDimensionPlural[0] : cellNamesByDimensionSingular[0];
          break;
        case DIMENSION_1:
          result = form ? cellNamesByDimensionPlural[1] : cellNamesByDimensionSingular[1];
          break;
        case DIMENSION_2:
          result = form ? cellNamesByDimensionPlural[2] : cellNamesByDimensionSingular[2];
          break;
        case DIMENSION_3:
          result = form ? cellNamesByDimensionPlural[3] : cellNamesByDimensionSingular[3];
          break;
        case DIMENSION_4:
          result = form ? cellNamesByDimensionPlural[4] : cellNamesByDimensionSingular[4];
          break;
        default:
          result = form ? cellNamesByDimensionPlural[5] : cellNamesByDimensionSingular[5];
      }
      break;
    case AUX_GEOM_ENTITY:
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0:
          result = form ? auxGeomNamesByDimensionPlural[0] : auxGeomNamesByDimensionSingular[0];
          break;
        case DIMENSION_1:
          result = form ? auxGeomNamesByDimensionPlural[1] : auxGeomNamesByDimensionSingular[1];
          break;
        case DIMENSION_2:
          result = form ? auxGeomNamesByDimensionPlural[2] : auxGeomNamesByDimensionSingular[2];
          break;
        case DIMENSION_3:
          result = form ? auxGeomNamesByDimensionPlural[3] : auxGeomNamesByDimensionSingular[3];
          break;
        case DIMENSION_4:
          result = form ? auxGeomNamesByDimensionPlural[4] : auxGeomNamesByDimensionSingular[4];
          break;
        default:
          result = form ? auxGeomNamesByDimensionPlural[5] : auxGeomNamesByDimensionSingular[5];
      }
      break;
    case USE_ENTITY:
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0:
          result = "vertex use";
          break;
        case DIMENSION_1:
          result = "edge use";
          break;
        case DIMENSION_2:
          result = "face use";
          break;
        case DIMENSION_3:
          result = "volume use";
          break;
        case DIMENSION_4:
          result = "spacetime volume use";
          break;
        default:
          result = "mixed-dimension cell use";
      }
      if (form)
      {
        result += "s"; // plural is easy in this case.
      }
      break;
    case SHELL_ENTITY:
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0 | DIMENSION_1:
          result = "chain";
          break;
        case DIMENSION_1 | DIMENSION_2:
          result = "loop";
          break;
        case DIMENSION_2 | DIMENSION_3:
          result = "shell";
          break;
        case DIMENSION_3 | DIMENSION_4:
          // a spacetime volume with no volumetric boundary
          result = "timeloop";
          break;
        case 0:
          result = "dimensionless shell";
          break;
        default:
          result = "unknown-dimensionality shell";
      }
      if (form)
      {
        result += "s"; // plural is easy in this case.
      }
      break;
    case GROUP_ENTITY:
      if (flags & MODEL_BOUNDARY)
        result += "boundary ";
      if (flags & MODEL_DOMAIN)
        result += "domain ";
      result += "group";
      if (form)
      {
        result += "s"; // plural is easy in this case.
      }
      break;
    case MODEL_ENTITY:
      // If dimension bits are set, use them.
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0:
          result = "point ";
          break;
        case DIMENSION_1:
          result = "curve ";
          break;
        case DIMENSION_2:
          result = "surface ";
          break;
        case DIMENSION_3:
          result = "volumetric ";
          break;
        case DIMENSION_4:
          result = "space-time ";
          break;
      }
      result += "model";
      if (form)
      {
        result += "s"; // plural is easy in this case.
      }
      break;
    case INSTANCE_ENTITY:
      result = "instance";
      if (form)
      {
        result += "s"; // plural is easy in this case.
      }
      break;
    case SESSION:
      result = "session";
      if (form)
      {
        result += "s"; // plural is easy in this case.
      }
      break;
    default:
      result = "invalid";
      break;
  }
  return result;
}

// If you change this, you may also need to change flagDescription/defaultNameForCount below.
/**\brief Return a string summarizing the type of the entity given its bit-vector \a flags.
  */
std::string Entity::flagSummary(BitFlags flags, int form)
{
  std::string result = flagSummaryHelper(flags, form);
  // Add some extra information about groups.
  if ((flags & GROUP_ENTITY) == GROUP_ENTITY)
  {
    bool dimSep = false;
    if (flags & (ANY_ENTITY & ~GROUP_ENTITY))
      result += " (";
    if (flags & ANY_DIMENSION)
    {
      for (int i = 0; i <= 4; ++i)
      {
        int dim = 1 << i;
        if (flags & dim)
        {
          if (dimSep)
            result += ",";
          result += ('0' + i);
          dimSep = true;
        }
      }
      if (dimSep)
        result += "-d";
    }

    bool entSep = false;
    for (BitFlags entType = CELL_ENTITY; entType < ENTITY_MASK; entType <<= 1)
    {
      if ((entType & GROUP_ENTITY) && NO_SUBGROUPS)
        continue;
      if (entType & flags)
      {
        if (entSep)
          result += ", ";
        else if (dimSep)
          result += " ";
        entSep = true;
        switch (entType)
        {
          case CELL_ENTITY:
            result += "cells";
            break;
          case USE_ENTITY:
            result += "uses";
            break;
          case SHELL_ENTITY:
            result += "shells";
            break;
          case GROUP_ENTITY:
            result += "groups";
            break;
          case MODEL_ENTITY:
            result += "models";
            break;
          case INSTANCE_ENTITY:
            result += "instances";
            break;
          case SESSION:
            result += "sessions";
            break;
          case AUX_GEOM_ENTITY:
            result += "auxiliary geometries";
            break;
          default:
            break;
        }
      }
    }
    if (dimSep && !entSep)
      result += " entities";
    if (dimSep || entSep)
      result += ")";

    if (flags & COVER)
      result += " cover";
    if (flags & PARTITION)
      result += " partition";
  }
  return result;
}

std::string Entity::flagDescription(BitFlags flags, int form)
{
  // TODO: Eventually this should return a markdown-formatted
  // description documenting the entity type.
  // Example (for CELL_ENTITY | DIMENSION_0):
  //
  // A **vertex** is a cell of dimension 0 that corresponds to
  // a single point in space in the embedding dimension of its
  // containing model. It has no parametric coordinates.
  // Vertices are used as boundary endpoints of vertex chains
  // which define edges.
  return Entity::flagSummary(flags, form);
}

/**\brief Return the next pedigree ID for an entity of the given type when given a vector of counters appropriate to the context.
  *
  * This does not increment the counter by default (so that it can be used to assign names),
  * however if you pass \a incr = true, the counter will be incremented.
  */
int Entity::countForType(BitFlags flags, IntegerList& counters, bool incr)
{
  if (counters.empty())
  {
    return -1;
  }
  IntegerList::value_type* ptr = NULL;
  switch (flags & ENTITY_MASK)
  {
    case CELL_ENTITY:
    case USE_ENTITY:
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0:
          ptr = counters.size() > 0 ? &counters[0] : NULL;
          break;
        case DIMENSION_1:
          ptr = counters.size() > 1 ? &counters[1] : NULL;
          break;
        case DIMENSION_2:
          ptr = counters.size() > 2 ? &counters[2] : NULL;
          break;
        case DIMENSION_3:
          ptr = counters.size() > 3 ? &counters[3] : NULL;
          break;
        case DIMENSION_4:
          ptr = counters.size() > 4 ? &counters[4] : NULL;
          break;
        default:
          ptr = counters.size() > 5 ? &counters[5] : NULL;
          break;
      }
      break;
    case SHELL_ENTITY:
      switch (flags & ANY_DIMENSION)
      {
        case DIMENSION_0 | DIMENSION_1:
          ptr = counters.size() > 0 ? &counters[0] : NULL;
          break;
        case DIMENSION_1 | DIMENSION_2:
          ptr = counters.size() > 1 ? &counters[1] : NULL;
          break;
        case DIMENSION_2 | DIMENSION_3:
          ptr = counters.size() > 2 ? &counters[2] : NULL;
          break;
        case DIMENSION_3 | DIMENSION_4:
          ptr = counters.size() > 3 ? &counters[3] : NULL;
          break;
        case 0:
          ptr = counters.size() > 4 ? &counters[4] : NULL;
          break;
        default:
          ptr = counters.size() > 5 ? &counters[5] : NULL;
      }
      break;
    case GROUP_ENTITY:
      if ((((flags & MODEL_BOUNDARY) != 0) ^ ((flags & MODEL_DOMAIN) != 0)) == 0)
      {
        ptr = counters.size() > 0 ? &counters[0] : NULL;
      }
      else if (flags & MODEL_DOMAIN)
      {
        ptr = counters.size() > 1 ? &counters[1] : NULL;
      }
      else // if (flags & MODEL_BOUNDARY)
      {
        ptr = counters.size() > 2 ? &counters[2] : NULL;
      }
      break;
    case MODEL_ENTITY:
      ptr = counters.size() > 0 ? &counters[0] : NULL;
      break;
    case INSTANCE_ENTITY:
    case SESSION:
    case AUX_GEOM_ENTITY:
    default:
      ptr = counters.size() > 0 ? &counters[0] : NULL;
      break;
  }
  if (!ptr)
  {
    return -1;
  }
  int count = *ptr;
  if (incr)
  {
    ++(*ptr);
  }
  return count;
}

/**\brief Given a vector of counters, return a numbered name string and advance counters as required.
  *
  * If you change this method, you may also need to change flagSummmary/flagDescription.
  *
  * By default, this increments the counter as the name is assigned but the \a incr argument
  * can be provided to override this behavior.
  */
std::string Entity::defaultNameFromCounters(BitFlags flags, IntegerList& counters, bool incr)
{
  std::ostringstream name;
  name << Entity::flagSummaryHelper(flags, /*singular*/ 0) << " "
       << Entity::countForType(flags, counters, incr);
  return name.str();
}

template <EntityTypeBits B>
bool hasBit(BitFlags val)
{
  return ((val & B) == B);
}

/**\brief Given a bitmask or entity flag, return a string specifier.
  *
  * The second argument, \a textual, indicates whether or not the value
  * will be converted to a human-oriented textual description of the bits
  * set or simply a string containing the decimal value of the bit vector.
  * The default is to generate human-oriented text since it is also
  * robust to version changes.
  *
  * The textual version should never begin with a number so that the
  * inverse of this method (specifierStringToFlag) need not expend effort
  * inferring the format.
  */
std::string Entity::flagToSpecifierString(BitFlags val, bool textual)
{
  std::ostringstream spec;
  if (textual)
  {
    // Check for specially-named bit values (convenience names)
    if (val == smtk::model::INVALID)
      spec << "invalid";

    else if (val == smtk::model::VERTEX)
      spec << "vertex";
    else if (val == smtk::model::EDGE)
      spec << "edge";
    else if (val == smtk::model::FACE)
      spec << "face";
    else if (val == smtk::model::VOLUME)
      spec << "volume";

    else if (val == smtk::model::VERTEX_USE)
      spec << "vertex_use";
    else if (val == smtk::model::EDGE_USE)
      spec << "edge_use";
    else if (val == smtk::model::FACE_USE)
      spec << "face_use";
    else if (val == smtk::model::VOLUME_USE)
      spec << "volume_use";

    else if (val == smtk::model::CHAIN)
      spec << "chain";
    else if (val == smtk::model::LOOP)
      spec << "loop";
    else if (val == smtk::model::SHELL)
      spec << "shell2";

    else if (val == smtk::model::ANY_ENTITY)
      spec << "any";

    // Not a specially-named bit value; generate a name:
    else
    {
      // Put entity type bits first and ensure they are all non-numeric.
      bool haveType = false;
      BitFlags tmp = val & smtk::model::ENTITY_MASK;
      if ((tmp != 0) && !(tmp & (tmp - 1)))
      {
        // If exactly one entity-type bit is set (this is what test on tmp does above), add it:
        if (isCellEntity(val))
        {
          haveType = true;
          spec << "cell";
        }
        if (isUseEntity(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "use";
        }
        if (isShellEntity(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "shell";
        }
        if (isGroup(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "group";
        }
        if (isModel(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "model";
        }
        if (isInstance(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "instance";
        }
        if (isSessionRef(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "session";
        }
        if (isAuxiliaryGeometry(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "aux_geom";
        }
      }

      // It is possible to get here with a non-zero value but no text in spec yet.
      // This happens with group/attribute-association membership masks. Check for
      // combinations of entity type bits.
      if (!haveType && spec.str().empty() && (val | smtk::model::ENTITY_MASK))
      {
        int eti = 0;
        for (BitFlags ebit = CELL_ENTITY; ebit < smtk::model::ENTITY_MASK; ebit <<= 1, ++eti)
        {
          if (ebit & val)
          {
            if (haveType)
            {
              spec << "|";
            }
            spec << entityTypeNames[eti];
            haveType = true;
          }
        }
      }

      if (!haveType)
      {
        spec << "none";
      }

      if (hasBit<smtk::model::MODEL_DOMAIN>(val))
        spec << "|domain";
      if (hasBit<smtk::model::MODEL_BOUNDARY>(val))
        spec << "|bdy";

      if (hasBit<smtk::model::COVER>(val))
        spec << "|cover";
      if (hasBit<smtk::model::PARTITION>(val))
        spec << "|partition";

      if (hasBit<smtk::model::OPEN>(val))
        spec << "|open";
      if (hasBit<smtk::model::CLOSED>(val))
        spec << "|closed";

      if (hasBit<smtk::model::HOMOGENOUS_GROUP>(val))
        spec << "|homg";

      if (hasBit<smtk::model::NO_SUBGROUPS>(val))
        spec << "|flat";

      if (hasBit<smtk::model::ANY_DIMENSION>(val))
        spec << "|anydim";
      else if (!(val & smtk::model::ANY_DIMENSION))
        spec << "|nodim";
      else
      {
        spec << "|";
        // Note that explicit dimension bits are not separated; they are only 1 character.
        if (hasBit<smtk::model::DIMENSION_0>(val))
          spec << "0";
        if (hasBit<smtk::model::DIMENSION_1>(val))
          spec << "1";
        if (hasBit<smtk::model::DIMENSION_2>(val))
          spec << "2";
        if (hasBit<smtk::model::DIMENSION_3>(val))
          spec << "3";
        if (hasBit<smtk::model::DIMENSION_4>(val))
          spec << "4";
      }
    }
  }
  else
  {
    spec << val;
  }
  return spec.str();
}

// WARNING!!! This array must be kept sorted (according to
// std::string's less-than operator) so that bisection works
// for searching by keyword.
static struct
{
  std::string name;
  BitFlags value;
} orderedValues[] = {
  { "0", smtk::model::DIMENSION_0 }, { "1", smtk::model::DIMENSION_1 },
  { "2", smtk::model::DIMENSION_2 }, { "3", smtk::model::DIMENSION_3 },
  { "4", smtk::model::DIMENSION_4 }, { "any", smtk::model::ANY_ENTITY },
  { "anydim", smtk::model::ANY_DIMENSION }, { "aux_geom", smtk::model::AUX_GEOM_ENTITY },
  { "b", smtk::model::SESSION }, { "bdy", smtk::model::MODEL_BOUNDARY },
  { "cell", smtk::model::CELL_ENTITY }, { "chain", smtk::model::CHAIN },
  { "closed", smtk::model::CLOSED }, { "cover", smtk::model::COVER },
  { "domain", smtk::model::MODEL_DOMAIN }, { "e", smtk::model::EDGE }, // Backwards-compatibility
  { "edge", smtk::model::EDGE }, { "edge_use", smtk::model::EDGE_USE },
  { "ef", smtk::model::EDGE | smtk::model::FACE },                        // Backwards-compatibility
  { "efr", smtk::model::EDGE | smtk::model::FACE | smtk::model::VOLUME }, // Backwards-compatibility
  { "ev", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_1 |
      smtk::model::DIMENSION_0 }, // Backwards compatibility
  { "f", smtk::model::FACE },     // Backwards-compatibility
  { "face", smtk::model::FACE },
  { "face_use", smtk::model::FACE_USE },
  { "fe", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_2 |
      smtk::model::DIMENSION_1 }, // Backwards compatibility
  { "fev", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_2 | smtk::model::DIMENSION_1 |
      smtk::model::DIMENSION_0 }, // Backwards compatibility
  { "flat", smtk::model::NO_SUBGROUPS },
  { "fr", smtk::model::FACE | smtk::model::VOLUME }, // Backwards-compatibility
  { "fv", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_2 |
      smtk::model::DIMENSION_0 },     // Backwards compatibility
  { "g", smtk::model::GROUP_ENTITY }, // Backwards compatibility
  { "gmrfev", smtk::model::GROUP_ENTITY | smtk::model::MODEL_ENTITY | smtk::model::CELL_ENTITY |
      smtk::model::ANY_DIMENSION }, // Backwards compatibility
  { "group", smtk::model::GROUP_ENTITY },
  { "homg", smtk::model::HOMOGENOUS_GROUP }, { "instance", smtk::model::INSTANCE_ENTITY },
  { "invalid", smtk::model::INVALID }, { "loop", smtk::model::LOOP },
  { "m", smtk::model::MODEL_ENTITY }, // Backwards compatibility
  { "model", smtk::model::MODEL_ENTITY },
  { "mrfev", smtk::model::MODEL_ENTITY | smtk::model::CELL_ENTITY |
      smtk::model::ANY_DIMENSION }, // Backwards compatibility
  { "nodim", 0 },
  { "none", 0 }, { "open", smtk::model::OPEN }, { "partition", smtk::model::PARTITION },
  { "r", smtk::model::VOLUME }, // Backwards compatibility
  { "re", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 |
      smtk::model::DIMENSION_1 }, // Backwards compatibility
  { "region", smtk::model::VOLUME },
  { "rev", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 | smtk::model::DIMENSION_1 |
      smtk::model::DIMENSION_0 }, // Backwards compatibility
  { "rf", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 |
      smtk::model::DIMENSION_2 }, // Backwards compatibility
  { "rfe", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 | smtk::model::DIMENSION_2 |
      smtk::model::DIMENSION_1 }, // Backwards compatibility
  { "rfev", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 | smtk::model::DIMENSION_2 |
      smtk::model::DIMENSION_1 | smtk::model::DIMENSION_0 }, // Backwards compatibility
  { "rfv", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 | smtk::model::DIMENSION_2 |
      smtk::model::DIMENSION_0 }, // Backwards compatibility
  { "rv", smtk::model::CELL_ENTITY | smtk::model::DIMENSION_3 |
      smtk::model::DIMENSION_0 }, // Backwards compatibility
  { "session", smtk::model::SESSION },
  { "shell", smtk::model::SHELL_ENTITY }, { "shell2", smtk::model::SHELL },
  { "use", smtk::model::USE_ENTITY }, { "v", smtk::model::VERTEX },       // Backwards-compatibility
  { "ve", smtk::model::VERTEX | smtk::model::EDGE },                      // Backwards-compatibility
  { "vef", smtk::model::VERTEX | smtk::model::EDGE | smtk::model::FACE }, // Backwards-compatibility
  { "vefr", smtk::model::VERTEX | smtk::model::EDGE | smtk::model::FACE |
      smtk::model::VOLUME }, // Backwards-compatibility
  { "vertex", smtk::model::VERTEX },
  { "vertex_use", smtk::model::VERTEX_USE }, { "volume", smtk::model::VOLUME },
  { "volume_use", smtk::model::VOLUME_USE },
};

static int numOrderedValues = sizeof(orderedValues) / sizeof(orderedValues[0]);

BitFlags keywordToBitFlags(const std::string& keyword)
{
  if (keyword.empty())
    return 0;

  // If a keyword starts with a number, it is a sequence of dimension bits:
  if (keyword.size() > 1 && (keyword[0] >= '0' && keyword[0] <= '4'))
  {
    BitFlags dims = 0;
    for (std::size_t i = 0; i < keyword.size(); ++i)
      dims |= keywordToBitFlags(keyword.substr(i, 1));
    return dims;
  }

  std::string proper = keyword;            // make a mutable copy.
  smtk::common::StringUtil::lower(proper); // downcase it.
  // Must be an actual keyword. Try looking it up.
  int lo = 0;
  int hi = numOrderedValues;
  while (lo < hi)
  {
    int mid = (lo & hi) + ((lo ^ hi) >> 1);
    if (orderedValues[mid].name < proper)
      lo = mid + 1;
    else
      hi = mid;
  }
  if (orderedValues[hi].name == proper)
    return orderedValues[hi].value;

  return 0;
}

BitFlags Entity::specifierStringToFlag(const std::string& spec)
{
  std::string val(spec);
  StringUtil::trim(val);
  BitFlags result = 0;
  if (val.empty())
    return result;

  // If the string starts with a digit, it must be a direct numeric value.
  if (isdigit(val[0]))
  {
    std::istringstream strval(val);
    strval >> result;
    return result;
  }
  // OK, we have textual values which we will bitwise-OR together.
  // First, split the values at "|"
  StringList vals = smtk::common::StringUtil::split(val, "|", /*omit:*/ true, /*trim:*/ true);
  for (StringList::iterator it = vals.begin(); it != vals.end(); ++it)
  {
    // Now find keywords in our carefully-arranged lookup table
    result |= keywordToBitFlags(smtk::common::StringUtil::lower(*it));
  }
  return result;
}

/**\brief Given a dimension number (0, 1, 2, 3, 4), return the proper bitcode.
  *
  * This does bounds checking and will return 0 for out-of-bound dimensions.
  */
BitFlags Entity::dimensionToDimensionBits(int dim)
{
  switch (dim)
  {
    case 0:
      return DIMENSION_0;
    case 1:
      return DIMENSION_1;
    case 2:
      return DIMENSION_2;
    case 3:
      return DIMENSION_3;
    case 4:
      return DIMENSION_4;
    default:
      break;
  }
  return 0;
}

int Entity::consumeInvalidIndex(const smtk::common::UUID& uid)
{
  int result = this->m_firstInvalid;
  if (result < 0)
    return result; // no hole to consume
  this->m_relations[result] = uid;

  // Now update m_firstInvalid:
  // I. Are we already at the end of the relations? If so, we're done.
  if (this->m_firstInvalid == static_cast<int>(this->m_relations.size()) - 1)
  {
    this->m_firstInvalid = -1;
    return result;
  }

  // II. Keep looking past the entry we just consumed for the next invalid one.
  ++this->m_firstInvalid;
  UUIDArray::iterator it = this->m_relations.begin() + this->m_firstInvalid;
  for (; it != this->m_relations.end(); ++it, ++this->m_firstInvalid)
    if (!*it)
    {
      return result;
    }
  this->m_firstInvalid = -1;
  return result;
}

} // namespace model
} //namespace smtk
