// EventIdList.cxx

#include "dataset_id/EventIdList.h"
#include <algorithm>
#include <iostream>
#include "dataset_util/memsize.h"
#include "dataset_util/XmlElement.h"
#include "dataset_util/DtdRegistry.h"

using std::string;
using std::pair;
using std::equal_range;
using std::ostream;
using std::endl;
using std::insert_iterator;
using std::includes;
using std::set_intersection;

typedef EventId::RunNumber RunNumber;
typedef EventId::EventNumber EventNumber;

typedef EventIdRange Range;
typedef EventIdList::RangeList RangeList;
typedef EventIdList::value_type value_type;
typedef EventIdList::size_type size_type;
typedef EventIdList::const_iterator const_iterator;
typedef EventIdList::InsertStatus InsertStatus;

//**********************************************************************
// Local definitions.
//**********************************************************************

namespace {

// Register the DTD.
DtdRegistry::Status ISTAT =
  DtdRegistry::register_dtd<EventIdList>("dataset");

// Invalid value.
value_type INVALID_VALUE;

// Maximum # of event ID ranges to display.
int MAX_EVENT_RANGES = 20;

}  // end unnamed namespace

//**********************************************************************
// EventIdList::const_iterator member functions.
//**********************************************************************

// Default constructor.

const_iterator::ConstIterator() : _plist(0) {
}

//**********************************************************************

// Full constructor.

const_iterator::
ConstIterator(const EventIdList* plist,
              RangeList::const_iterator& irng,
              EventId::EventNumber evt)
: _plist(plist), _irng(irng), _evt(evt) {
}

//**********************************************************************

// Constructor for the end of a list.

const_iterator::ConstIterator(const EventIdList* plist)
: _plist(plist) {
  if ( plist != 0 ) {
    _irng = plist->ranges().end();
  }
}

//**********************************************************************

// Equality.

bool const_iterator::operator==(const const_iterator& rhs) const {
  if ( _plist != rhs._plist ) return false;
  if ( _plist == 0 ) return true;
  if ( _irng != rhs._irng ) return false;
  if ( _irng == _plist->ranges().end() ) return true;
  return _evt == rhs._evt;
}

//**********************************************************************

// Inequality.

bool const_iterator::operator!=(const const_iterator& rhs) const {
  return ! operator==(rhs);
}

//**********************************************************************

// Dereference.

EventId const_iterator::operator*() const {
  assert( _plist != 0 );
  if ( _plist == 0 ) {
    return EventId();
  }
  if ( _irng == _plist->ranges().end() ) {
    return EventId();
  }
  EventId::RunNumber run = _irng->run();
  assert( _evt >= _irng->first_event() );
  assert( _evt <= _irng->last_event() );
  return EventId(run, _evt);
}

//**********************************************************************

// Increment.

const_iterator& const_iterator::operator++() {
  assert( _plist != 0 );
  if ( _plist == 0 ) {
    return *this;
  }
  if ( _irng == _plist->ranges().end() ) {
    return *this;
  }
  if ( _evt < _irng->last_event() ) {
    ++_evt;
    return *this;
  }
  ++_irng;
  if ( _irng == _plist->ranges().end() ) {
    _evt = 0;
  } else {
    _evt = _irng->first_event();
  }
  return *this;
}

//**********************************************************************

// Post increment.

const_iterator const_iterator::operator++(int) {
  const_iterator save = *this;
  operator++();
  return save;
}

//**********************************************************************

// Deccrement.

const_iterator& const_iterator::operator--() {
  assert( _plist != 0 );
  if ( _plist == 0 ) {
    return *this;
  }
  if ( *this == _plist->begin() ) {
    return *this;
  }
  if ( _evt > _irng->first_event() ) {
    --_evt;
    return *this;
  }
  assert( _irng != _plist->ranges().begin() );
  --_irng;
  _evt = _irng->last_event();
  return *this;
}

//**********************************************************************

// Post decrement.

const_iterator const_iterator::operator--(int) {
  const_iterator save = *this;
  operator--();
  return save;
}

//**********************************************************************
// EventId static member functions.
//**********************************************************************

// DTD.

const Text& EventIdList::dtd() {
  static Text txt;
  if ( txt.size() == 0 ) {
    txt.append("<!ELEMENT EventIdList (EventId | EventIdRange)*>");
  }
  return txt;
}

//**********************************************************************
// EventIdList member functions.
//**********************************************************************

// Constructor.

EventIdList::EventIdList() : m_size(0), m_update_from_xml(false) {
  assert( ! m_ele.is_valid() );
}

//**********************************************************************

// Range constructor.

EventIdList::EventIdList(const EventIdRange& rng)
: m_size(0), m_update_from_xml(false) {
  assert( ! m_ele.is_valid() );
  insert(rng);
}

//**********************************************************************

// XML constructor.

EventIdList::EventIdList(const XmlElement& ele, bool try_children)
: m_size(0), m_update_from_xml(true) {
  assert( ! m_ele.is_valid() );
  const XmlElement* pele = 0;
  if ( ele.name() == xml_name() ) {
    pele = &ele;
  } else if ( try_children ) {
    const XmlElement::ElementList& children = ele.children(xml_name());
    if ( children.size() == 1 ) {
      pele = children.front();
    }
  }
  if ( pele != 0 ) {  
    m_ele = *pele;
  }
}

//**********************************************************************

// Return the list of ranges.

const RangeList& EventIdList::ranges() const {
  xml_update();
  return m_ranges;
}

//**********************************************************************

// Begin iterator.

const_iterator EventIdList::begin() const {
  xml_update();
  RangeList::const_iterator irng = m_ranges.begin();
  EventId::EventNumber evt = 0;
  if ( irng != m_ranges.end() ) {
    evt = irng->first_event();
  }
  return const_iterator(this, irng, evt);
}

//**********************************************************************

// End iterator.

const_iterator EventIdList::end() const {
  xml_update();
  return const_iterator(this);
}

//**********************************************************************

// Return the size.

size_type EventIdList::size() const {
  xml_update();
  return m_size;
}

//**********************************************************************

// Front.

value_type EventIdList::front() const {
  xml_update();
  if ( size() == 0 ) return INVALID_VALUE;
  const EventIdRange& rng = *m_ranges.begin();
  return EventId(rng.run(), rng.first_event());
}

//**********************************************************************

// Back.

value_type EventIdList::back() const {
  xml_update();
  if ( size() == 0 ) return INVALID_VALUE;
  const EventIdRange& rng = *m_ranges.rbegin();
  return EventId(rng.run(), rng.last_event());
}

//**********************************************************************

// Return the max size.
// This is a minimum extimate.
// The actual capacity will be larger if the ID's are contiguous.

size_type EventIdList::max_size() const {
  return m_ranges.max_size() + size() - m_ranges.size();
}

//**********************************************************************

// Find.

const_iterator EventIdList::find(const EventId& eid) const {
  xml_update();
  Range rng(eid);
  pair<RangeList::const_iterator, RangeList::const_iterator> lims =
    equal_range(m_ranges.begin(), m_ranges.end(), rng);
  for ( RangeList::const_iterator irng=lims.first;
        irng!=lims.second; ++irng) {
    if ( eid.event() >= irng->first_event()  &&
         eid.event() <= irng->last_event() ) {
      return const_iterator(this, irng, eid.event());
    }
  }
  return end();
}

//**********************************************************************

// Is an event ID included in this list?

bool EventIdList::contains(const EventId& eid) const {
  xml_update();
  const_iterator ieid = find(eid);
  return ieid != end();
}

//**********************************************************************

// Is an event ID range included in this list?

bool EventIdList::contains(const EventIdRange& rng) const {
  xml_update();
  if ( rng.size() == 0 ) return true;
  pair<RangeList::const_iterator, RangeList::const_iterator> lims =
    equal_range(m_ranges.begin(), m_ranges.end(), rng);
  if ( (lims.second - lims.first) != 1 ) {
    return false;
  }
  return ( lims.first->contains(rng) );
}

//**********************************************************************

// Is an event ID list included in this list?

bool EventIdList::contains(const EventIdList& eids) const {
  xml_update();
  if ( eids.size() == 0 ) return true;
  return includes(begin(), end(), eids.begin(), eids.end());
}

//**********************************************************************

// Write xml.

size_t EventIdList::memsize() const {
  size_t mem = 0;
  mem += sizeof(m_size);
  mem += memsize_vector(m_ranges);
  mem += sizeof(m_update_from_xml);
  mem += m_ele.memsize();
  return mem;
}

//**********************************************************************

// Write XML.

const XmlElement* EventIdList::xml() const {
  xml_update();
  XmlElement* pele = new XmlElement(xml_name());
  // Loop over ranges.
  for ( EventIdList::RangeList::const_iterator irng=ranges().begin();
        irng!=ranges().end(); ++irng ) {
    const EventIdRange& rng = *irng;
    assert( rng.is_valid() );
    const XmlElement* pchild = 0;
    if ( rng.size() == 1 ) {
      pchild = EventId(rng.run(), rng.first_event()).xml();
    } else {
      pchild = rng.xml();
    }
    assert( pchild != 0 );
    pele->add_child(pchild);
  }
  return pele;
}

//**********************************************************************
// Mutating member functions.
//**********************************************************************

// Insert an EventId.

InsertStatus EventIdList::insert(const EventId& rhs) {
  xml_update();
  return insert(Range(rhs));
}

//**********************************************************************

// Insert an EventId at a position.

const_iterator
EventIdList::insert(const const_iterator& ipos, const EventId& rhs) {
  xml_update();
  assert( ipos._plist == this );
  InsertStatus stat = insert(Range(rhs));
  if ( stat.second ) {
    return stat.first;
  }
  return end();
}

//**********************************************************************

// Insert an EventId range.

InsertStatus EventIdList::insert(const Range& rhs) {
  xml_update();
  // Handle invalid range.
  if ( ! rhs.is_valid() ) {
    return InsertStatus(end(), false);
  }
  // Extract run number and event range from the argument.
  RunNumber run = rhs.run();
  EventNumber new1 = rhs.first_event();
  EventNumber new2 = rhs.last_event();
  // Find the range of ranges which overlap the input range.
  pair<RangeList::iterator, RangeList::iterator> lims =
    equal_range(m_ranges.begin(), m_ranges.end(), rhs);
  RangeList::iterator ifirst = lims.first;
  RangeList::iterator isecond = ifirst;
  ++isecond;
  RangeList::iterator iend = lims.second;
  // Bool indicating if the container is modified.
  bool modified = false;
  // If there are none, then insert the new range.
  if ( ifirst == iend ) {
    ifirst = m_ranges.insert(ifirst,rhs);
    m_size += rhs.size();
    modified = true;
  // Otherwise, merge the existing ranges and the new one.
  } else {
    RangeList::iterator ilast = iend;
    assert( iend != m_ranges.begin() );
    --ilast;
    EventNumber min1 = ifirst->first_event();
    EventNumber min2 = ifirst->last_event();
    EventNumber max2 = ilast->last_event();
    EventId::EventNumber evt1 = min1;
    EventId::EventNumber evt2 = min2;
    if ( new1 < evt1 ) evt1 = new1;
    if ( new2 > evt2 ) evt2 = new2;
    if ( max2 > evt2 ) evt2 = max2;
    // There is a change...
    if ( evt1<min1 || evt2>min2 ) {
      modified = true;
      // Loop over the old entries.
      RangeList::size_type equal_range_count = 0;
      size_type equal_event_count = 0;
      for ( RangeList::iterator irng=ifirst; irng!=iend; ++irng ) {
        ++equal_range_count;
        equal_event_count += irng->size();
      }
      *ifirst = Range(EventId(run,evt1), evt2-evt1+1);
      // Delete any other elements in the equal range.
      RangeList::size_type old_size = m_ranges.size();
      m_ranges.erase(isecond, iend);
      assert( m_ranges.size() == old_size - equal_range_count + 1 );
      m_size -= equal_event_count;
      m_size += ifirst->size();
    // There was no change.
    } else {
      assert( isecond == iend );
    }
  }
  // Build the iterator pointing to the event ID in
  // the new range.
  RangeList::const_iterator itmp = ifirst;
  const_iterator ieid(this, itmp, new1);
  return InsertStatus(ieid, modified);
}

//**********************************************************************

// Remove an ID by iterator.

void EventIdList::erase(const const_iterator& ieid) {
  xml_update();
  assert( ieid._plist == this );
  if ( ieid._plist != this ) return;
  if ( ieid == end() ) return;
  // dla jul03
  // Strict compiler complained so patched the following line
  RangeList::iterator irng = (RangeList::iterator&)(ieid._irng);
  assert( irng != m_ranges.end() );
  EventId::EventNumber evt = ieid._evt;
  EventId::EventNumber evt1 = irng->first_event();
  EventId::EventNumber evt2 = irng->last_event();
  EventId::RunNumber run = irng->run();
  assert( irng->is_valid() );
  if ( irng->size() == 1 ) {
    m_ranges.erase(irng);
  } else if ( irng->first_event() == evt ) {
    irng->pop_front();
  } else if ( irng->last_event() == evt ) {
    irng->pop_back();
  } else {
    m_ranges.erase(irng);
    insert(Range(run,evt1,evt-1));
    insert(Range(run,evt+1,evt2));
  }
  --m_size;
}

//**********************************************************************

// Remove an ID by value.

size_type EventIdList::erase(const EventId& eid) {
  xml_update();
  const_iterator ieid = find(eid);
  if ( ieid == end() ) return 0;
  erase(ieid);
  return 1;
}

//**********************************************************************

// Select ID's that are common with an input list.
// We assume that erasing an element does not invalidate the
// iterator that precedes that element.

size_type EventIdList::select(const EventIdList& eids) {
  xml_update();
  EventIdList save;
  insert_iterator<EventIdList> isav(save, save.begin());
  set_intersection(begin(), end(), eids.begin(), eids.end(), isav);
  *this = save;
  return size();
}

//**********************************************************************

// Check for overlap.
// It is possible to provide a much more efficient implementation.

bool EventIdList::overlaps(const EventIdList& eids) const {
  xml_update();
  if ( size() == 0 ) return false;
  if ( eids.size() == 0 ) return false;
  EventIdList save;
  insert_iterator<EventIdList> isav(save, save.begin());
  set_union(begin(), end(), eids.begin(), eids.end(), isav);
  size_type nshare = size() + eids.size() - save.size();
  return nshare > 0;
}

//**********************************************************************

// Merge.

size_type EventIdList::merge(const EventIdList& eids, bool noshare) {
  xml_update();
  EventIdList save;
  insert_iterator<EventIdList> isav(save, save.begin());
  set_union(begin(), end(), eids.begin(), eids.end(), isav);
  if ( noshare ) {
    size_type nshare = size() + eids.size() - save.size();
    if ( nshare > 0 ) return 0;
  }
  *this = save;
  return size();
}

//**********************************************************************

// Update using XML.

void EventIdList::xml_update() const {
  if ( ! m_update_from_xml ) return;
  if ( ! m_ele.is_valid() ) return;
  const_cast<bool&>(m_update_from_xml) = false;
  EventIdList& mthis = const_cast<EventIdList&>(*this);
  assert( m_ele.name() == xml_name() );
  for ( XmlElement::ElementList::const_iterator
        iele=m_ele.children().begin();
        iele!=m_ele.children().end(); ++iele ) {
    const XmlElement& child = **iele;
    if ( child.name() == EventId::xml_name() ) {
      EventId id(child);
      assert( id.is_valid() );
      if ( id.is_valid() ) {
        InsertStatus stat = mthis.insert(id);
        assert( stat.second );
      }
    } else if ( child.name() == EventIdRange::xml_name() ) {
      EventIdRange rng(child);
      assert( rng.is_valid() );
      if ( rng.is_valid() ) {
        InsertStatus stat = mthis.insert(rng);
        assert( stat.second );
      }
    } else {
      assert(false);
    }
  }
}

//**********************************************************************

// Output stream.

ostream& EventIdList::ostr(ostream& lhs, string indent) const {
  xml_update();
  if ( xml_only() ) {
    lhs << indent 
        << "Event ID list has not been extracted";
    return lhs;
  }
  const RangeList rngs = ranges();
  lhs << indent << "Event ID list has " << size() << " ID";
  if ( size() != 1 ) {
    lhs << "'s";
  }
  size_type nrng = rngs.size();
  lhs << " in " << nrng << " range";
  if ( nrng != 1 ) {
    lhs << "s";
  }
  lhs << ":";
  string indent2 = indent + "  ";
  if ( nrng < MAX_EVENT_RANGES ) {
    for ( RangeList::const_iterator irng=rngs.begin();
          irng!=rngs.end(); ++irng ) {
      lhs << "\n" << indent2 << *irng;
    }
  } else {
    lhs << "\n" << indent2 << "First event range: " << rngs.front();
    lhs << "\n" << indent2 << " Last event range: " << rngs.back();
    lhs.flush();
  }
  return lhs;
}

//**********************************************************************
// Free functions.
//**********************************************************************

// Equality.

bool operator==(const EventIdList& lhs, const EventIdList& rhs) {
  return ( lhs.ranges() == rhs.ranges() );
}

//**********************************************************************

// Inequality.

bool operator!=(const EventIdList& lhs, const EventIdList& rhs) {
  return ! ( lhs == rhs );
}

//**********************************************************************

// Output stream.

ostream& operator<<(ostream& lhs, const EventIdList& rhs) {
  return rhs.ostr(lhs, "");
}

//**********************************************************************