xref: /dports/math/moab/fathomteam-moab-7bde9dfb84a8/src/TypeSequenceManager.cpp

#include "TypeSequenceManager.hpp"
#include "SequenceData.hpp"
#include "moab/Error.hpp"
#include <assert.h>
#include <limits>

namespace moab {

TypeSequenceManager::~TypeSequenceManager()
{
  // We assume that for there to be multiple sequences referencing
  // the same SequenceData, there must be some portion of the
  // SequenceData that is unused. Otherwise the sequences should
  // have been merged. Given that assumption, it is the case that
  // either a) a SequenceData is in availableList or b) the
  // SequenceData is referenced by exactly one sequence.

  // Delete every entity sequence
  for (iterator i = begin(); i != end(); ++i) {
    EntitySequence* seq = *i;
    // Check for case b) above
    if (seq->using_entire_data()) {
      // Delete sequence before data, because sequence
      // has a pointer to data and may try to dereference
      // that pointer during its destruction.
      SequenceData* data = seq->data();
      delete seq;
      delete data;
    }
    else {
      delete seq;
    }
  }
  sequenceSet.clear();

  // Case a) above
  for (data_iterator i = availableList.begin(); i != availableList.end(); ++i)
    delete *i;
  availableList.clear();
}

ErrorCode TypeSequenceManager::merge_internal(iterator i, iterator j)
{
  EntitySequence* dead = *j;
  sequenceSet.erase(j);
  ErrorCode rval = (*i)->merge(*dead);
  if (MB_SUCCESS != rval) {
    sequenceSet.insert(dead);
    return rval;
  }

  if (lastReferenced == dead)
    lastReferenced = *i;
  delete dead;

  // If merging results in no unused portions of the SequenceData,
  // remove it from the available list.
  if ((*i)->using_entire_data())
    availableList.erase((*i)->data());

  return MB_SUCCESS;
}

ErrorCode TypeSequenceManager::check_merge_next(iterator i)
{
  iterator j = i; ++j;
  if (j == end() || (*j)->data() != (*i)->data() ||
     (*j)->start_handle() > (*i)->end_handle() + 1)
    return MB_SUCCESS;

  assert((*i)->end_handle() + 1 == (*j)->start_handle());
  return merge_internal(i, j);
}

ErrorCode TypeSequenceManager::check_merge_prev(iterator i)
{
  if (i == begin())
    return MB_SUCCESS;

  iterator j = i; --j;
  if ((*j)->data() != (*i)->data() ||
     (*j)->end_handle() + 1 < (*i)->start_handle())
    return MB_SUCCESS;

  assert((*j)->end_handle() + 1 == (*i)->start_handle());
  return merge_internal(i, j);
}

ErrorCode TypeSequenceManager::insert_sequence(EntitySequence* seq_ptr)
{
  if (!seq_ptr->data())
    return MB_FAILURE;

  if (seq_ptr->data()->start_handle() > seq_ptr->start_handle() ||
      seq_ptr->data()->end_handle() < seq_ptr->end_handle() ||
      seq_ptr->end_handle() < seq_ptr->start_handle())
    return MB_FAILURE;

  iterator i = lower_bound(seq_ptr->start_handle());
  if (i != end()) {
    if ((*i)->start_handle() <= seq_ptr->end_handle())
      return MB_ALREADY_ALLOCATED;
    if (seq_ptr->data() != (*i)->data() &&
        (*i)->data()->start_handle() <= seq_ptr->data()->end_handle())
      return MB_ALREADY_ALLOCATED;
  }

  if (i != begin()) {
    iterator j = i; --j;
    if (seq_ptr->data() != (*j)->data() &&
        (*j)->data()->end_handle() >= seq_ptr->data()->start_handle())
      return MB_ALREADY_ALLOCATED;
  }

  i = sequenceSet.insert(i, seq_ptr);

  // Merge with previous sequence ?
  if (seq_ptr->start_handle() > seq_ptr->data()->start_handle() && i != begin()) {
    if (MB_SUCCESS != check_merge_prev(i)) {
      sequenceSet.erase(i);
      return MB_FAILURE;
    }
  }

  // Merge with next sequence ?
  if ((*i)->end_handle() < (*i)->data()->end_handle()) {
    if (MB_SUCCESS != check_merge_next(i)) {
      sequenceSet.erase(i);
      return MB_FAILURE;
    }
  }

  // We merged adjacent sequences sharing a SequenceData, so
  // we can safely assume that unless this EntitySequence is
  // using the entire SequenceData, there are unused portions.
  if (!seq_ptr->using_entire_data())
    availableList.insert(seq_ptr->data());

  // lastReferenced is only allowed to be NULL if there are
  // no sequences (avoids unnecessary if's in fast path).
  if (!lastReferenced)
    lastReferenced = seq_ptr;

  // Each SequenceData has a pointer to the first EntitySequence
  // referencing it. Update that pointer if the new sequence is
  // the first one.
  if ((*i)->start_handle() == (*i)->data()->start_handle() ||
      lower_bound((*i)->data()->start_handle()) == i)
    (*i)->data()->seqManData.firstSequence = i;

  assert(check_valid_data(seq_ptr));
  return MB_SUCCESS;
}

ErrorCode TypeSequenceManager::replace_subsequence(EntitySequence* seq_ptr,
                                                   const int* tag_sizes,
                                                   int num_tag_sizes)
{
  // Find the sequence of interest
  iterator i = lower_bound(seq_ptr->start_handle());
  if (i == end() || (*i)->data() == seq_ptr->data())
    return MB_FAILURE;
  // New sequence must be a subset of an existing one
  if (seq_ptr->start_handle() < (*i)->start_handle() ||
      seq_ptr->end_handle() > (*i)->end_handle())
    return MB_FAILURE;
  // New sequence's data must be new also, and cannot intersect
  // any existing sequence (just require that the data range
  // matches the sequence range for now)
  if (!seq_ptr->using_entire_data())
    return MB_FAILURE;
  // Copy tag data (move ownership of var-len data)
  SequenceData* const dead_data = (*i)->data();
  dead_data->move_tag_data(seq_ptr->data(), tag_sizes, num_tag_sizes);

  // Split sequences sharing old data into two groups:
  // p->i : first sequence to i
  // i->n : i to one past last sequence
  iterator p, n = i;
  p = (*i)->data()->seqManData.firstSequence;
  for (++n; n != end() && (*n)->data() == (*i)->data(); ++n);

  // First subdivide EntitySequence as necessary
  // Move i to be the first sequence past the insertion point
  // such that the new order will be:
  // [p,i-1] seq_ptr [i,n]
  // where p == i if no previous sequence

  // Four possible cases:
  // 0. All entities in sequence are in new sequence
  // 1. Old entities in sequence before and after new sequence,
  //    requiring sequence to be split.
  // 2. Old entities after new sequence
  // 3. Old entities before new sequence
  const bool some_before = ((*i)->start_handle() < seq_ptr->start_handle());
  const bool some_after  = ((*i)->  end_handle() > seq_ptr->  end_handle());
  // Case 0
  if (!(some_before || some_after)) {
    // Remove dead sequence from internal lists
    EntitySequence* seq = *i;
    iterator dead = i; ++i;
    if (p == dead)
      p = i;
    sequenceSet.erase(dead);

    // Delete old sequence
    delete seq;
    // Make sure lastReferenced isn't stale
    if (lastReferenced == seq)
      lastReferenced = seq_ptr;
  }
  // Case 1
  else if (some_before && some_after) {
    i = split_sequence(i, seq_ptr->start_handle());
    (*i)->pop_front(seq_ptr->size());
  }
  // Case 2
  else if (some_after) {
    (*i)->pop_front(seq_ptr->size());
  }
  // Case 3
  else { // some_before
    (*i)->pop_back(seq_ptr->size());
    ++i;
  }

  // Now subdivide the underlying sequence data as necessary
  availableList.erase(dead_data);
  if (p != i) {
    iterator last = i; --last;
    SequenceData* new_data = (*p)->create_data_subset((*p)->start_handle(), (*last)->end_handle());
    new_data->seqManData.firstSequence = p;

    for (; p != i; ++p)
      (*p)->data(new_data);
    // Copy tag data (move ownership of var-len data)
    dead_data->move_tag_data(new_data, tag_sizes, num_tag_sizes);
    if (!(*new_data->seqManData.firstSequence)->using_entire_data())
      availableList.insert(new_data);
  }
  if (i != n) {
    iterator last = n; --last;
    SequenceData* new_data = (*i)->create_data_subset((*i)->start_handle(), (*last)->end_handle());
    new_data->seqManData.firstSequence = i;
    for (; i != n; ++i)
      (*i)->data(new_data);
    // Copy tag data (move ownership of var-len data)
    dead_data->move_tag_data(new_data, tag_sizes, num_tag_sizes);
    if (!(*new_data->seqManData.firstSequence)->using_entire_data())
      availableList.insert(new_data);
  }
  delete dead_data;

  // Put new sequence in lists
  return insert_sequence(seq_ptr);
}

TypeSequenceManager::iterator TypeSequenceManager::erase(iterator i)
{
  EntitySequence* seq = *i;
  SequenceData* data = seq->data();
  iterator j;

  // Check if we need to delete the referenced SequenceData also
  bool delete_data;
  if (seq->using_entire_data()) // Only sequence
    delete_data = true;
  else if (data->seqManData.firstSequence != i) { // Earlier sequence?
    delete_data = false;
    availableList.insert(data);
  }
  else { // Later sequence ?
    j = i; ++j;
    delete_data = (j == end() || (*j)->data() != data);
    if (delete_data)
      availableList.erase(data);
    else {
      availableList.insert(data);
      data->seqManData.firstSequence = j;
    }
  }

  // Remove sequence, updating i to be next sequence
  j = i++;
  sequenceSet.erase(j);

  // Make sure lastReferenced isn't stale. It can only be NULL if
  // no sequences.
  if (lastReferenced == seq)
    lastReferenced = sequenceSet.empty() ? 0 : *sequenceSet.begin();

  // Always delete sequence before the SequenceData it references.
  assert(0 == find(seq->start_handle()));
  delete seq;
  if (delete_data)
    delete data;
  else {
    assert(check_valid_data(*data->seqManData.firstSequence));
    assert(lastReferenced != seq);
  }
  return i;
}

ErrorCode TypeSequenceManager::remove_sequence(const EntitySequence* seq_ptr,
                                               bool& unreferenced_data)
{
  // Remove sequence from set
  iterator i = lower_bound(seq_ptr->start_handle());
  if (i == end() || *i != seq_ptr)
    return MB_ENTITY_NOT_FOUND;
  sequenceSet.erase(i);

  // Check if this is the only sequence referencing its data
  if (seq_ptr->using_entire_data())
    unreferenced_data = true;
  else {
    i = lower_bound(seq_ptr->data()->start_handle());
    unreferenced_data = i == end() || (*i)->data() != seq_ptr->data();
    if (unreferenced_data)
      availableList.erase(seq_ptr->data());
    else
      seq_ptr->data()->seqManData.firstSequence = i; // Might be 'i' already
  }

  if (lastReferenced == seq_ptr)
    lastReferenced = sequenceSet.empty() ? 0 : *sequenceSet.begin();

  return MB_SUCCESS;
}

TypeSequenceManager::iterator
TypeSequenceManager::find_free_handle(EntityHandle min_start_handle,
                                      EntityHandle max_end_handle,
                                      bool& append_out,
                                      int values_per_ent)
{
  for (data_iterator i = availableList.begin(); i != availableList.end(); ++i) {
    if ((*(*i)->seqManData.firstSequence)->values_per_entity() != values_per_ent)
      continue;

    if ((*i)->start_handle() > max_end_handle || (*i)->end_handle() < min_start_handle)
      continue;

    for (iterator j = (*i)->seqManData.firstSequence;
         j != end() && (*j)->start_handle() <= (max_end_handle + 1) && (*j)->data() == *i;
         ++j) {
      if ((*j)->end_handle() + 1 < min_start_handle)
        continue;
      if ((*j)->start_handle() > (*i)->start_handle() &&
          (*j)->start_handle() > min_start_handle) {
        append_out = false;
        return j;
      }
      if ((*j)->end_handle() < (*i)->end_handle() &&
          (*j)->end_handle() < max_end_handle) {
        append_out = true;
        return j;
      }
    }
  }

  return end();
}

bool TypeSequenceManager::is_free_sequence(EntityHandle start,
                                           EntityID num_entities,
                                           SequenceData*& data_out,
                                           int values_per_ent)
{
  data_out = 0;
  if (empty())
    return true;

  const_iterator i = lower_bound(start);
  if (i == end()) {
    --i; // Safe because already tested empty()
    // If we don't overlap the last data object...
    if ((*i)->data()->end_handle() < start)
      return true;
    data_out = (*i)->data();
    if ((*i)->values_per_entity() != values_per_ent)
      return false;
    // If we overlap a data object, we must be entirely inside of it
    return start + num_entities - 1 <= (*i)->data()->end_handle();
  }

#ifndef NDEBUG
  if (i != begin()) {
    const_iterator j = i;
    --j;
    assert((*j)->end_handle() < start);
  }
#endif

  // Check if we fit in the block of free handles
  if (start + num_entities > (*i)->start_handle()) // start + num + 1 >= i->start
    return false;

  // Check if we overlap the data for the next sequence
  if (start + num_entities > (*i)->data()->start_handle()) {
    data_out = (*i)->data();
    if ((*i)->values_per_entity() != values_per_ent)
      return false;
    // If overlap, must be entirely contained
    return start >= data_out->start_handle() &&
           start + num_entities - 1 <= data_out->end_handle();
  }

  // Check if we overlap the data for the previous sequence
  if (i != begin()) {
    --i;
    if ((*i)->data()->end_handle() >= start) {
      data_out = (*i)->data();
      if ((*i)->values_per_entity() != values_per_ent)
        return false;
      return start + num_entities - 1 <= (*i)->data()->end_handle();
    }
  }

  // Unused handle block that overlaps no SequenceData
  return true;
}

EntityHandle TypeSequenceManager::find_free_block(EntityID num_entities,
                                                  EntityHandle min_start_handle,
                                                  EntityHandle max_end_handle)
{
  const_iterator i = lower_bound(min_start_handle);
  if (i == end())
    return min_start_handle;

  if ((*i)->start_handle() < min_start_handle + num_entities)
    return min_start_handle;

  EntityHandle prev_end = (*i)->end_handle(); ++i;
  for (; i != end(); prev_end = (*i)->end_handle(), ++i) {
    EntityID len = (*i)->start_handle() - prev_end - 1;
    if (len >= num_entities)
      break;
  }

  if (prev_end + num_entities > max_end_handle)
    return 0;
  else
    return prev_end + 1;
}

struct range_data {
  EntityID num_entities;
  EntityHandle min_start_handle, max_end_handle;
  EntityHandle first, last;
};

static bool check_range(const range_data& d,
                        bool prefer_end,
                        EntityHandle& result)
{
  EntityHandle first = std::max(d.min_start_handle, d.first);
  EntityHandle  last = std::min(d.max_end_handle, d.last);
  if (last < first + d.num_entities - 1) {
    result = 0;
    return false;
  }

  result = prefer_end ? last + 1 - d.num_entities : first;
  return true;
}

EntityHandle TypeSequenceManager::find_free_sequence(EntityID num_entities,
                                                     EntityHandle min_start_handle,
                                                     EntityHandle max_end_handle,
                                                     SequenceData*& data_out,
                                                     EntityID &data_size,
                                                     int num_verts)
{
  if (max_end_handle < min_start_handle + num_entities - 1)
    return 0;

  EntityHandle result;
  iterator p, i = lower_bound(min_start_handle);
  range_data d = {num_entities, min_start_handle, max_end_handle, 0, 0};

  if (i == end()) {
    data_out = 0;
    return min_start_handle;
  }
  else if (i == begin()) {
    if ((*i)->values_per_entity() == num_verts) {
      d.first = (*i)->data()->start_handle();
      d.last  = (*i)->start_handle() - 1;
      if (check_range(d, true, result)) {
        data_out = (*i)->data();
        return result;
      }
    }
    d.first = min_start_handle;
    d.last = (*i)->data()->start_handle() - 1;
    if (check_range(d, true, result)) {
      data_out = 0;
      // This will back up against the end of the seq data, so
      // size the data that way
      data_size = num_entities;
      return result;
    }
    p = i++;
  }
  else {
    p = i;
    --p;
  }

  for (; i != end() && (*i)->start_handle() < max_end_handle; p = i++) {
    if ((*p)->data() == (*i)->data()) {
      if ((*p)->values_per_entity() == num_verts) {
        d.first = (*p)->end_handle() + 1;
        d.last = (*i)->start_handle() - 1;
        if (check_range(d, false, result)) {
          data_out = (*p)->data();
          return result;
        }
      }
    }
    else {
      if ((*p)->values_per_entity() == num_verts) {
        d.first = (*p)->end_handle() + 1;
        d.last = (*p)->data()->end_handle();
        if (check_range(d, false, result)) {
          data_out = (*p)->data();
          return result;
        }
      }
      if ((*i)->values_per_entity() == num_verts) {
        d.first = (*i)->data()->start_handle();
        d.last = (*i)->start_handle() - 1;
        if (check_range(d, true, result)) {
          data_out = (*i)->data();
          return result;
        }
      }
      d.first = (*p)->data()->end_handle() + 1;
      d.last  = (*i)->data()->start_handle() - 1;
      if (check_range(d, false, result)) {
        data_out = 0;
        data_size = d.last - d.first + 1;
        return result;
      }
    }
  }

  if ((*p)->values_per_entity() == num_verts) {
    d.first = (*p)->end_handle() + 1;
    d.last = (*p)->data()->end_handle();
    if (check_range(d, false, result)) {
      data_out = (*p)->data();
      return result;
    }
  }

  d.first = (*p)->data()->end_handle() + 1;
  d.last = max_end_handle;
  if (check_range(d, false, result)) {
    data_out = 0;
    return result;
  }

  data_out = 0;
  return 0;
}

EntityHandle TypeSequenceManager::last_free_handle(EntityHandle after_this) const
{
  int junk;
  const_iterator it = lower_bound(after_this);
  if (it == end())
    return CREATE_HANDLE(TYPE_FROM_HANDLE(after_this), MB_END_ID, junk);
  else if ((*it)->start_handle() > after_this) {
    // Need to check against the sequence data first
    EntityHandle rhandle = (*it)->data()->start_handle();
    return rhandle - 1;
  }
  else
    return 0;
}

ErrorCode TypeSequenceManager::check_valid_handles(Error* /* error_handler */,
                                                   EntityHandle first,
                                                   EntityHandle last) const
{
  const_iterator i = lower_bound(first);
  if (i == end() || (*i)->start_handle() > first) {
#if 0
    // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
    // MB_SET_ERR on it
    fprintf(
      stderr,
      "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)first
      );
#endif
    return MB_ENTITY_NOT_FOUND;
  }

  while ((*i)->end_handle() < last) {
    EntityHandle prev_end = (*i)->end_handle();
    ++i;
    if (i == end() || prev_end + 1 != (*i)->start_handle())
      return MB_ENTITY_NOT_FOUND;
  }

  return MB_SUCCESS;
}

ErrorCode TypeSequenceManager::erase(Error* /* error_handler */, EntityHandle h)
{
  EntitySequence* seq = find(h);
  if (!seq) {
#if 0
    // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
    // MB_SET_ERR on it
    fprintf(
      stderr,
      "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)h
      );
#endif
    return MB_ENTITY_NOT_FOUND;
  }

  if (seq->start_handle() == h) {
    if (seq->end_handle() != h) {
      if (seq->using_entire_data())
        availableList.insert(seq->data());
      seq->pop_front(1);
      return MB_SUCCESS;
    }
    SequenceData* data = seq->data();
    bool delete_data;
    ErrorCode rval = remove_sequence(seq, delete_data);
    if (MB_SUCCESS != rval)
      return rval;
    delete seq;
    if (delete_data)
      delete data;
  }
  else if (seq->end_handle() == h) {
    if (seq->using_entire_data())
      availableList.insert(seq->data());
    seq->pop_back(1);
  }
  else {
    iterator i = lower_bound(h);
    if ((*i)->using_entire_data())
      availableList.insert((*i)->data());
    i = split_sequence(i, h);
    seq = *i;
    assert(seq->start_handle() == h);
    seq->pop_front(1);
  }

  return MB_SUCCESS;
}

ErrorCode TypeSequenceManager::erase(Error* /* error */, EntityHandle first, EntityHandle last)
{
  // First check that all entities in range are valid

  ErrorCode rval = check_valid_handles(NULL, first, last);
  if (MB_SUCCESS != rval)
    return rval;

  // Now remove entities

  // Get first sequence intersecting range
  iterator i = lower_bound(first);
  if (i == end()) // Shouldn't be possible given check_valid_handles call above.
    return MB_ENTITY_NOT_FOUND;

  // If range is entirely in interior of sequence, need to split sequence.
  if ((*i)->start_handle() < first && (*i)->end_handle() > last) {
    if ((*i)->using_entire_data())
      availableList.insert((*i)->data());
    i = split_sequence(i, first);
    (*i)->pop_front(last - first + 1);
    assert(check_valid_data(*i));
    return MB_SUCCESS;
  }

  // If range doesn't entirely contain first sequence, remove some
  // handles from the end of the sequence and advance to the next
  // sequence.
  if ((*i)->start_handle() < first) {
    if ((*i)->using_entire_data())
      availableList.insert((*i)->data());
    (*i)->pop_back((*i)->end_handle() - first + 1);
    ++i;
  }

  // Destroy all sequences contained entirely within the range
  while (i != end() && (*i)->end_handle() <= last)
    i = erase(i);

  // If necessary, remove entities from the beginning of the
  // last sequence.
  if (i != end() && (*i)->start_handle() <= last) {
    if ((*i)->using_entire_data())
      availableList.insert((*i)->data());
    (*i)->pop_front(last - (*i)->start_handle() + 1);
    assert(check_valid_data(*i));
  }

  return MB_SUCCESS;
}

TypeSequenceManager::iterator TypeSequenceManager::split_sequence(iterator i, EntityHandle h)
{
  EntitySequence* seq = (*i)->split(h);
  if (!seq)
    return end();

  i = sequenceSet.insert(i, seq);
  assert(check_valid_data(*i));

  return i;
}

ErrorCode TypeSequenceManager::is_free_handle(EntityHandle handle,
                                              iterator& seq_iter_out,
                                              SequenceData*& data_ptr_out,
                                              EntityHandle& block_start,
                                              EntityHandle& block_end,
                                              int values_per_ent)
{
  int junk;
  block_start = CREATE_HANDLE(TYPE_FROM_HANDLE(handle), MB_START_ID, junk);
  block_end   = CREATE_HANDLE(TYPE_FROM_HANDLE(handle), MB_END_ID,   junk);

  iterator i = lower_bound(handle);
  if (i != end()) {
    block_end = (*i)->start_handle() - 1;

    // If sequence contains handle, then already allocated
    if ((*i)->start_handle() <= handle)
      return MB_ALREADY_ALLOCATED;

    // Handle is not within an existing sequence, but is
    // within an existing SequenceData...
    if ((*i)->data()->start_handle() <= handle) {
      // If values_per_entity don't match, can't put new entity
      // in existing SequenceData
      if ((*i)->values_per_entity() != values_per_ent)
        return MB_ALREADY_ALLOCATED;

      data_ptr_out = (*i)->data();
      if (block_end == handle) {
        // Prepend to existing sequence
        seq_iter_out = i;
        block_start = handle;
      }
      else {
        // Add new sequence to existing SequenceData
        seq_iter_out = end();
        if (i == begin() || (*--i)->data() != data_ptr_out)
          block_start = data_ptr_out->start_handle();
        else
          block_start = (*i)->end_handle() + 1;
      }
      return MB_SUCCESS;
    }
  }

  if (i != begin()) {
    --i;
    block_start = (*i)->end_handle() + 1;

    // Handle is within previous sequence data...
    if ((*i)->data()->end_handle() >= handle) {
      // If values_per_entity don't match, can't put new entity
      // in existing SequenceData
      if ((*i)->values_per_entity() != values_per_ent)
        return MB_ALREADY_ALLOCATED;

      data_ptr_out = (*i)->data();
      if (block_start == handle) {
        // Append to existing sequence
        seq_iter_out = i;
        block_end = handle;
      }
      else {
        // Add new sequence to existing SequenceData
        seq_iter_out = end();
        if (++i == end() || (*i)->data() != data_ptr_out)
          block_end = data_ptr_out->end_handle();
        else
          block_end = (*i)->start_handle() - 1;
      }
      return MB_SUCCESS;
    }
  }

  seq_iter_out = end();
  data_ptr_out = 0;

  return MB_SUCCESS;
}

ErrorCode TypeSequenceManager::notify_appended(iterator seq)
{
  ErrorCode rval = check_merge_next(seq);
  if ((*seq)->using_entire_data())
    availableList.erase((*seq)->data());

  return rval;
}

ErrorCode TypeSequenceManager::notify_prepended(iterator seq)
{
  ErrorCode rval = check_merge_prev(seq);
  if ((*seq)->using_entire_data())
    availableList.erase((*seq)->data());

  return rval;
}

void TypeSequenceManager::get_memory_use(unsigned long long& entity_storage,
                                         unsigned long long& total_storage) const
{
  entity_storage = total_storage = 0;
  if (empty())
    return;

  EntityType mytype = TYPE_FROM_HANDLE(lastReferenced->start_handle());
  int junk;
  get_memory_use(CREATE_HANDLE(mytype, MB_START_ID, junk),
                 CREATE_HANDLE(mytype, MB_END_ID,   junk),
                 entity_storage,
                 total_storage);
}

void TypeSequenceManager::append_memory_use(EntityHandle first,
                                            EntityHandle last,
                                            const SequenceData* data,
                                            unsigned long long& entity_storage,
                                            unsigned long long& total_storage) const
{
  const unsigned long allocated_count = data->size();

  unsigned long bytes_per_ent, seq_size;
  const_iterator i = data->seqManData.firstSequence;
  (*i)->get_const_memory_use(bytes_per_ent, seq_size);

  unsigned long other_ent_mem = 0;
  unsigned long occupied_count = 0, entity_count = 0, sequence_count = 0;
  for (; i != end() && (*i)->data() == data; ++i) {
    occupied_count += (*i)->size();
    ++sequence_count;

    EntityHandle start = std::max(first, (*i)->start_handle());
    EntityHandle  stop = std::min(last, (*i)->end_handle());
    if (stop < start)
      continue;

    entity_count += stop - start + 1;
    other_ent_mem += (*i)->get_per_entity_memory_use(start, stop);
  }

  unsigned long sum = sequence_count * seq_size +
                      allocated_count * bytes_per_ent;

  // Watch for overflow
  assert(entity_count > 0 && occupied_count > 0 && allocated_count > 0);
  if (std::numeric_limits<unsigned long>::max() / entity_count <= sum) {
    total_storage  += sum * (entity_count /  occupied_count) + other_ent_mem;
    entity_storage += sum * (entity_count / allocated_count) + other_ent_mem;
  }
  else {
    total_storage  += sum * entity_count /  occupied_count + other_ent_mem;
    entity_storage += sum * entity_count / allocated_count + other_ent_mem;
  }
}

void TypeSequenceManager::get_memory_use(EntityHandle first,
                                         EntityHandle last,
                                         unsigned long long& entity_storage,
                                         unsigned long long& total_storage) const
{
  entity_storage = total_storage = 0;

  while (first <= last) {
    const_iterator i = lower_bound(first);
    if (i == end())
      return;

    SequenceData* data = (*i)->data();
    if (first < data->end_handle()) {
      append_memory_use(first, last, data, entity_storage, total_storage);
    }
    first  = data->end_handle() + 1;
  }
}

EntityID TypeSequenceManager::get_occupied_size(const SequenceData* data) const
{
  EntityID result = 0;
  for (const_iterator i = data->seqManData.firstSequence; i != end() && (*i)->data() == data; ++i)
    result += (*i)->size();

  return result;
}

#ifndef NDEBUG
bool TypeSequenceManager::check_valid_data(const EntitySequence* seq) const
{
  // Caller passed a sequence that should be contained, so cannot be empty
  if (empty())
    return false;

  // Make sure lastReferenced points to something
  if (!lastReferenced)
    return false;

  const_iterator seqi = sequenceSet.lower_bound(lastReferenced);
  if (seqi == sequenceSet.end() || *seqi != lastReferenced)
    return false;

  // Make sure passed sequence is in list
  const EntitySequence* seq2 = find(seq->start_handle());
  if (seq2 != seq)
    return false;

  // Check all sequences referencing the same SequenceData
  const SequenceData* data = seq->data();
  const_iterator i = lower_bound(data->start_handle());
  if (i != data->seqManData.firstSequence)
    return false;

  if (i != begin()) {
    const_iterator j = i;
    --j;
    if ((*j)->end_handle() >= data->start_handle())
      return false;
    if ((*j)->data()->end_handle() >= data->start_handle())
      return false;
  }

  for (;;) {
    seq2 = *i;
    ++i;
    if (i == end())
      return true;
    if ((*i)->data() != data)
      break;

    if (seq2->end_handle() >= (*i)->start_handle())
      return false;
  }

  if ((*i)->start_handle() <= data->end_handle())
    return false;
  if ((*i)->data()->start_handle() <= data->end_handle())
    return false;

  return true;
}

#endif

} // namespace moab