//=========================================================================
//  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/model/Resource.h"

#include "smtk/attribute/Attribute.h"
#include "smtk/attribute/Definition.h"
#include "smtk/attribute/Resource.h"

#include "smtk/common/StringUtil.h"
#include "smtk/common/UUIDGenerator.h"

#include "smtk/resource/Resource.h"

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

#include <sstream>

//#include <boost/variant.hpp>

using namespace std;
using namespace smtk::common;
using namespace smtk::resource;

namespace smtk
{
namespace model
{

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

static const char* cellNamesByDimensionPlural[] = { "vertices", "edges", "faces", "volumes",
  "spacetimes", "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)
  , m_id(smtk::common::UUIDGenerator::instance().random())
{
}

Entity::~Entity()
{
}

/// Create and set up an entity object in a single call. This version sets the Entity's UUID.
EntityPtr Entity::create(const UUID& uid, BitFlags entityFlags, ResourcePtr resource)
{
  EntityPtr result = Entity::create();
  int dim = Entity::dimensionBitsToDimension(entityFlags & EntityTypeBits::ANY_DIMENSION);
  result->setId(uid);
  result->setup(entityFlags, dim, resource);
  return result;
}

/// Create and set up an entity object in a single call. This version does not set the UUID.
EntityPtr Entity::create(BitFlags entityFlags, int dimension, ResourcePtr resource)
{
  EntityPtr result = Entity::create();
  result->setup(entityFlags, dimension, resource);
  return result;
}

/**\brief Populate an object with the given \a dimension with a type specified by \a entityFlags.
  *
  * By default, this does resets the array of relations,
  * since changing the type or dimension of an object would usually
  * invalidate relations; if it does not, you should
  * pass \a resetRelations = false.
  */
EntityPtr Entity::setup(BitFlags entFlags, int dim, Resource::Ptr resource, bool resetRelations)
{
  m_entityFlags = entFlags;
  m_resource = resource;
  // Override the dimension bits if the dimension is specified
  if (dim >= 0 && dim <= 4)
  {
    // Clear the dimension bits:
    m_entityFlags &= ~(DIMENSION_0 | DIMENSION_1 | DIMENSION_2 | DIMENSION_3 | DIMENSION_4);
    // Now add in the *proper* dimension bit to match m_dimension:
    m_entityFlags |= (1 << dim);
  }
  if (resetRelations)
  {
    m_firstInvalid = -1;
    m_relations.clear();
  }
  return shared_from_this();
}

const smtk::resource::ResourcePtr Entity::resource() const
{
  return std::dynamic_pointer_cast<smtk::resource::Resource>(m_resource.lock());
}

ResourcePtr Entity::modelResource() const
{
  return std::dynamic_pointer_cast<smtk::model::Resource>(m_resource.lock());
}

bool Entity::reparent(ResourcePtr newParent)
{
  ResourcePtr oldParent = m_resource.lock();
  if (oldParent == newParent)
  {
    return false;
  }
  m_resource = newParent;
  return true;
}

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

bool Entity::setEntityFlags(BitFlags flags)
{
  bool allowed = false;
  if (m_entityFlags == INVALID)
  {
    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) == (m_entityFlags & ANY_ENTITY))
    {
      m_entityFlags = flags;
      allowed = true;
    }
  }
  return allowed;
}

std::string Entity::name() const
{
  auto mr = this->modelResource();
  if (mr)
  {
    return mr->name(m_id);
  }
  return std::string();
}

/**\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 = 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 m_entityFlags & ANY_DIMENSION;
}

UUIDArray& Entity::relations()
{
  return m_relations;
}
const UUIDArray& Entity::relations() const
{
  return 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>(m_relations.size());
  m_relations.push_back(b);
  return idx;
}

EntityPtr Entity::pushRelation(const UUID& b)
{
  m_relations.push_back(b);
  return shared_from_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.
  */
EntityPtr Entity::removeRelation(const UUID& b)
{
  UUIDArray& arr(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 shared_from_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()
{
  m_relations.clear();
  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 < m_relations.size(); ++i)
  {
    if (m_relations[i] == r)
    {
      return static_cast<int>(i);
    }
  }
  int idx = static_cast<int>(m_relations.size());
  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 < m_relations.size(); ++i)
  {
    if (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>(m_relations.size()))
    return -1;

  m_relations[relIdx] = smtk::common::UUID::null();
  if (m_firstInvalid < 0 || (m_firstInvalid >= 0 && relIdx < m_firstInvalid))
    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 = "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 (smtk::model::isCellEntity(val))
        {
          haveType = true;
          spec << "cell";
        }
        if (smtk::model::isUseEntity(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "use";
        }
        if (smtk::model::isShellEntity(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "shell";
        }
        if (smtk::model::isGroup(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "group";
        }
        if (smtk::model::isModel(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "model";
        }
        if (smtk::model::isInstance(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "instance";
        }
        if (smtk::model::isSessionRef(val))
        {
          if (haveType)
            spec << "|";
          else
            haveType = true;
          spec << "session";
        }
        if (smtk::model::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[] = {
  { "*", smtk::model::ANY_ENTITY }, { "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::dimensionBitsToDimension(BitFlags dimBits)
{
  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:
      break;
  }
  return -1;
}

int Entity::arrange(ArrangementKind kind, const Arrangement& arr, int index)
{
  KindsToArrangements::iterator kit = m_arrangements.find(kind);
  if (kit == m_arrangements.end())
  {
    if (index >= 0)
    { // failure: can't replace information that doesn't exist.
      return -1;
    }
    Arrangements blank;
    kit = m_arrangements.insert(std::pair<ArrangementKind, Arrangements>(kind, blank)).first;
  }

  if (index >= 0)
  {
    if (index >= static_cast<int>(kit->second.size()))
    { // failure: can't replace information that doesn't exist.
      return -1;
    }
    kit->second[index] = arr;
  }
  else
  {
    index = static_cast<int>(kit->second.size());
    kit->second.push_back(arr);
  }
  return index;
}

int Entity::unarrange(ArrangementKind kind, int index, bool removeIfLast)
{
  int result = 0;
  if (index < 0 || m_arrangements.empty())
  {
    return result;
  }
  ArrangementKindWithArrangements ak = m_arrangements.find(kind);
  if (ak == m_arrangements.end() || index >= static_cast<int>(ak->second.size()))
  {
    return result;
  }

  ArrangementReferences duals;
  bool hasDuals = this->modelResource()->findDualArrangements(this->id(), kind, index, duals);

  // TODO: notify someone of imminent removal? Rewrite relations?
  std::vector<int> relIdxs;

  if ((ak->second.begin() + index)->relationIndices(relIdxs, shared_from_this(), kind))
  {
    for (std::vector<int>::iterator rit = relIdxs.begin(); rit != relIdxs.end(); ++rit)
    {
      this->invalidateRelationByIndex(*rit);
    }
  }
  ak->second.erase(ak->second.begin() + index);
  ++result;

  // Now, if we removed the last arrangement of this kind, kill the kind-dictionary entry
  if (ak->second.empty())
  {
    m_arrangements.erase(ak);
  }

  // Now find and remove the dual arrangement (if one exists)
  // This branch should not be taken if we are inside the inner unarrangeEntity call below.
  if (hasDuals)
  {
    // Unarrange every dual to this arrangement.
    bool canIncrement = false;
    for (ArrangementReferences::iterator dit = duals.begin(); dit != duals.end(); ++dit)
    {
      if (this->modelResource()->unarrangeEntity(
            dit->entityId, dit->kind, dit->index, removeIfLast) == 2)
      {
        // Only increment result when dualEntity is removed, not the dual arrangement.
        canIncrement = true;
      }
    }
    // Only increment once if other entities were removed; we do not indicate how many were removed.
    if (canIncrement)
    {
      ++result;
    }
  }

  return result;
}

bool Entity::clearArrangements()
{
  bool didRemove = !m_arrangements.empty();
  if (didRemove)
    m_arrangements.clear();
  return didRemove;
}

const Arrangements* Entity::hasArrangementsOfKind(ArrangementKind kind) const
{
  auto ait = m_arrangements.find(kind);
  if (ait != m_arrangements.end())
  {
    return &ait->second;
  }
  return nullptr;
}

Arrangements* Entity::hasArrangementsOfKind(ArrangementKind kind)
{
  ArrangementKindWithArrangements ait = m_arrangements.find(kind);
  if (ait != m_arrangements.end())
  {
    return &ait->second;
  }
  return nullptr;
}

Arrangements& Entity::arrangementsOfKind(ArrangementKind kind)
{
  return m_arrangements[kind];
}

const Arrangement* Entity::findArrangement(ArrangementKind kind, int index) const
{
  if (index < 0)
  {
    return nullptr;
  }

  auto kit = m_arrangements.find(kind);
  if (kit == m_arrangements.end())
  {
    return nullptr;
  }

  if (index >= static_cast<int>(kit->second.size()))
  { // failure: can't replace information that doesn't exist.
    return nullptr;
  }

  return &kit->second[index];
}

Arrangement* Entity::findArrangement(ArrangementKind kind, int index)
{
  if (index < 0)
  {
    return nullptr;
  }

  KindsToArrangements::iterator kit = m_arrangements.find(kind);
  if (kit == m_arrangements.end())
  {
    return nullptr;
  }

  if (index >= static_cast<int>(kit->second.size()))
  { // failure: can't replace information that doesn't exist.
    return nullptr;
  }

  return &kit->second[index];
}

int Entity::findArrangementInvolvingEntity(
  ArrangementKind kind, const smtk::common::UUID& involved) const
{
  const Arrangements* arr = this->hasArrangementsOfKind(kind);
  if (!arr)
    return -1;

  Arrangements::const_iterator it;
  int idx = 0;
  UUIDArray rels;
  for (it = arr->begin(); it != arr->end(); ++it, ++idx, rels.clear())
  {
    if (it->relations(rels, const_cast<Entity*>(this)->shared_from_this(), kind))
    {
      for (UUIDArray::iterator rit = rels.begin(); rit != rels.end(); ++rit)
      {
        if (*rit == involved)
        {
          return idx;
        }
      }
    }
  }

  return -1;
}

bool Entity::findDualArrangements(
  ArrangementKind kind, int index, ArrangementReferences& duals) const
{
  const Arrangements* arr = this->hasArrangementsOfKind(kind);
  if (!arr || index < 0 || index >= static_cast<int>(arr->size()))
  {
    return false;
  }

  int relationIdx;
  int sense;
  Orientation orient;

  UUID dualEntityId;
  ArrangementKind dualKind;
  int dualIndex;
  int relStart, relEnd;

  switch (kind)
  {
    case HAS_USE:
      switch (this->entityFlags() & ENTITY_MASK)
      {
        case CELL_ENTITY:
          if ((*arr)[index].IndexSenseAndOrientationFromCellHasUse(relationIdx, sense, orient))
          { // OK, find use's reference to this cell.
            if (relationIdx < 0 || static_cast<int>(this->relations().size()) <= relationIdx)
              return false;
            dualEntityId = m_relations[relationIdx];
            dualKind = HAS_CELL;
            if ((dualIndex = this->modelResource()->findArrangementInvolvingEntity(
                   dualEntityId, dualKind, this->id())) >= 0)
            {
              duals.push_back(ArrangementReference(dualEntityId, dualKind, dualIndex));
              return true;
            }
          }
          break;
        case SHELL_ENTITY:
          if ((*arr)[index].IndexRangeFromShellHasUse(relStart, relEnd))
          { // Find the use's reference to this shell.
            dualKind = HAS_SHELL;
            for (; relStart != relEnd; ++relStart)
            {
              dualEntityId = m_relations[relStart];
              if ((dualIndex = this->modelResource()->findArrangementInvolvingEntity(
                     dualEntityId, dualKind, this->id())) >= 0)
                duals.push_back(ArrangementReference(dualEntityId, dualKind, dualIndex));
            }
            if (!duals.empty())
              return true;
          }
          break;
        /*
      bool IndexFromCellEmbeddedInEntity(int& relationIdx) const;
      bool IndexFromCellIncludesEntity(int& relationIdx) const;
      bool IndexFromCellHasShell(int& relationIdx) const;
      bool IndexAndSenseFromUseHasCell(int& relationIdx, int& sense) const;
      bool IndexFromUseHasShell(int& relationIdx) const;
      bool IndexFromUseOrShellIncludesShell(int& relationIdx) const;
      bool IndexFromShellHasCell(int& relationIdx) const;
      bool IndexRangeFromShellHasUse(int& relationBegin, int& relationEnd) const;
      bool IndexFromShellEmbeddedInUseOrShell(int& relationIdx) const;
      bool IndexFromInstanceInstanceOf(int& relationIdx) const;
      bool IndexFromEntityInstancedBy(int& relationIdx) const;
      */
        case USE_ENTITY:
        case GROUP_ENTITY:
        case MODEL_ENTITY:
        case INSTANCE_ENTITY:
          break;
      }
      break;
    case INCLUDES: // INCLUDES/EMBEDDED_IN are always simple and duals; entity type doesn't matter.
    case EMBEDDED_IN:
      if ((*arr)[index].IndexFromSimple(relationIdx))
      { // OK, find use's reference to this cell.
        if (relationIdx < 0 || static_cast<int>(m_relations.size()) <= relationIdx)
          return false;
        dualEntityId = m_relations[relationIdx];
        dualKind = kind == INCLUDES ? EMBEDDED_IN : INCLUDES;
        if ((dualIndex = this->modelResource()->findArrangementInvolvingEntity(
               dualEntityId, dualKind, this->id())) >= 0)
        {
          duals.push_back(ArrangementReference(dualEntityId, dualKind, dualIndex));
          return true;
        }
      }
      break;
    case SUPERSET_OF:
    case SUBSET_OF:
      if ((*arr)[index].IndexFromSimple(relationIdx))
      { // OK, find the related entity's reference to this one.
        if (relationIdx < 0 || static_cast<int>(m_relations.size()) <= relationIdx)
        {
          return false;
        }
        dualEntityId = m_relations[relationIdx];
        dualKind = (kind == SUPERSET_OF ? SUBSET_OF : SUPERSET_OF);
        if ((dualIndex = this->modelResource()->findArrangementInvolvingEntity(
               dualEntityId, dualKind, this->id())) >= 0)
        {
          duals.push_back(ArrangementReference(dualEntityId, dualKind, dualIndex));
          return true;
        }
      }
      break;
    case INSTANCE_OF:
    case INSTANCED_BY:
      if ((*arr)[index].IndexFromSimple(relationIdx))
      { // OK, find the related entity's reference to this one.
        if (relationIdx < 0 || static_cast<int>(m_relations.size()) <= relationIdx)
        {
          return false;
        }
        dualEntityId = m_relations[relationIdx];
        dualKind = (kind == INSTANCED_BY ? INSTANCE_OF : INSTANCED_BY);
        if ((dualIndex = this->modelResource()->findArrangementInvolvingEntity(
               dualEntityId, dualKind, this->id())) >= 0)
        {
          duals.push_back(ArrangementReference(dualEntityId, dualKind, dualIndex));
          return true;
        }
      }
      break;
    case HAS_CELL:
    case HAS_SHELL:
      // These (HAS_CELL, HAS_SHELL) are not duals of each other.
      // Instead, they are the easier half of HAS_USE relations,
      // and is only defined when the source is a use-record.
      if ((this->entityFlags() & ENTITY_MASK) == USE_ENTITY)
      {
        if ((*arr)[index].IndexFromSimple(relationIdx))
        { // OK, find the related entity's reference to this one.
          if (relationIdx < 0 || static_cast<int>(m_relations.size()) <= relationIdx)
          {
            return false;
          }
          dualEntityId = m_relations[relationIdx];
          dualKind = HAS_USE;
          if ((dualIndex = this->modelResource()->findArrangementInvolvingEntity(
                 dualEntityId, dualKind, this->id())) >= 0)
          {
            duals.push_back(ArrangementReference(dualEntityId, dualKind, dualIndex));
            return true;
          }
        }
      }
      break;
    default:
      smtkErrorMacro(this->modelResource()->log(),
        "Asked to find dual of unknown kind of arrangement: " << kind << ".");
      break;
  }
  return false;
}

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

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

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

/**\brief Return the attributes associated with the entity
that are of type (or derived type) def.
  */
smtk::attribute::Attributes Entity::attributes(smtk::attribute::ConstDefinitionPtr def) const
{
  smtk::attribute::Attributes atts;
  // If there was no definition return empty list
  if (def == nullptr)
  {
    return atts;
  }
  auto attResource = def->resource();
  // If there is no resource then return an empty list
  if (attResource == nullptr)
  {
    return atts;
  }

  // First lets find all attribute IDs that are assoicated with the entity
  ResourcePtr resource = this->modelResource();
  UUIDsToAttributeAssignments::const_iterator entry = resource->attributeAssignments().find(m_id);
  // No attributes then just return an emoty list
  if (entry == resource->attributeAssignments().end())
  {
    return atts;
  }
  // Lets go through all of the attributes and find the ones that come from def
  for (auto id : entry->second.attributeIds())
  {
    auto a = attResource->findAttribute(id);
    if (a == nullptr)
    {
      // Could not find the attribute for that ID
      continue;
    }
    // Is this attribute based on def
    if (a->definition()->isA(def))
    {
      atts.push_back(a);
    }
  }
  return atts;
}

EntityPtr Entity::owningModel() const
{
  auto myResource = this->modelResource();
  UUID modelId = myResource->modelOwningEntity(m_id);
  return myResource->findEntity(modelId);
}

} // namespace model
} //namespace smtk
