//<HEADER> 
/*
Data & Model Server (DMS), a server for DSS applications. 
Version: see RtcInterface.h
Copyright (C) 1998-2002  YUSE GSO Object Vision BV. 
http://www.objectvision.nl/DMS/

This library is free software; you can use, redistribute, and/or
modify it under the terms of the GNU General Public Licence version 2 
(the Licence) as published by the Free Software Foundation.

See LICENSE.TXT for terms of distribution or look at our web site:
http://www.objectvision.nl/DMS/Liense.txt
or alternatively at: http://www.gnu.org/copyleft/gpl.html

You can use, redistribute and/or modify this library source code file
provided that this entire header notice is preserved.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public Licence for more details. However, specific warranties might be
granted by an additional written contract for support, assistance and/or development

Additional to the terms of the license, we request you to apply the following
guidelines (these additional requests are not limiting your rights under the terms of the license):
- We would like to be notified if you make any modification and receive your 
  source code at email://mhilferink@ObjectVision.nl
- In case of bug-fixes and small additions, we might or might not use your
  improvements in a possible future version of the DMS without notification of
  your modification (ie you will not be displayed as the author), nevertheless,
  when you distribute the DMS source code with your modifications, you should
  give a prominent notification as described in article 2a of the Licence.
- In case of larger additions, you will remain the author of these additions
  and this will be displayed if your addition is distributed by us. 
- When you have made a product that uses the DMS, you can distribute it under
  the same GPL Licence conditions. We would like to receive a copy of your product
  including source code. You will remain the author of this product.

Documentation on using the Data & Model Server library can be found at:
http://www.ObjectVision.nl/DMS/

This software is developed by YUSE GSO Object Vision BV.
YUSE GSO Object Vision BV has specialized in developing software for 
policy oriented data analysis applications.

YUSE GSO Object Vision BV
http://www.ObjectVision.Nl/
email://m.hilferink@yusegso.nl
Zijlweg 148-a
2015 BJ Haarlem
the Netherlands
tel +31-23-5319161
fax +31-23-5420252
*/
//</HEADER>
#pragma once

/***************************************************************************
 *
 * File:      sequence_array.h
 * Module:    RunTimeComponent
 * Author:    Maarten Hilferink
 *
 ***************************************************************************

sequence_array<T> is (nearly) compatible with std::vector<std::vector<T> >
but has a faster memory management strategy.

Rationale:

I often worked with vectors of sequences, two examples:

1. typedef std::pair<double, double> dpoint;
   typedef std::vector<dpoint> dpolygon;   // point sequence
   typedef std::vector<dpolygon> dpolygon_array; // point sequence array

2. typedef std::basic_string<char> String; // char sequence
   typedef std::vector<String> StringArray; // char sequence array

When working with vector-based sequence arrays (as above),
the memory management strategy is not efficient
due to the many allocations/deallocations of the individual sequences.
Especially the destruction of such vector based sequence arrays
often takes unneccesary and annoying amount of time.

The memory allocation of sequences by sequence_array<T> 
offers two advantages above using a vector of vectors:
1. A sequence_array specific memory pool for the sequences from which 
   sequences are allocated to avoid individual heap (de)allocations
	for each sequence
2. Not providing synchronization on such memory allocation
   (note that common implementations of vector also don't provide
	thread safety anyway

sequence_array<T> uses an internal
    DataVectorType m_Data;
for sequential storage of sequences of T (the memory pool)
and an additional
    std::vector<std::pair<DataVectorType::iterator, DataVectorType::iterator> > m_Seqs;
for identifying allocated sequences.

DataVectorType is defined as std::vector<T> for elementary types T and simple structures thereof,
and can be defined as sequece_array<U> when T is a collection of U in order to support
arrays of arrays of sequcences of U (three dimensional) and higher dimensional equivalents.

sequence_array offers:
	typedef iterator, 
	typedef const_iterator, 
	typedef reference,
	typedef const_reference
with interfaces nearly compatibe with
	std::vector<T>*, 
	const std::vector<T>*, 
	vector<T>&, resp. 
	const vector<T>&.
(the sequences however don't have a reserve() member function,
only a resize() resulting in reallocation in m_Data if they grow
AND [are not the last sequence in m_Data
or insufficent reserved space after m_Data.end() is available] )

The storage m_Data grows with the familiar doubling strategy
as sequences are inserted or re-allocated due to calls to their resize() mf.
m_Seqs is adjusted when m_Data has grown by re-allocation.

Destruction of a sequence_array only requires two calls to delete[].
(assuming that T::~T() doesn't do additional things).

sequence_array minimizes the pollution of the heap with varying sized
arrays.

Users benefit most when the total size and number of the sequences is known in advance, 
and provided to a sequence_array by the member-functions reserve() and data_reserve().

At this point, my implementation is not ready for inclusion in boost for the following reasons:
- it is dependent on other headers in my pre-boost facilities library
- it is not yet in boost style
- lack of required peer review in order to get sufficient quality and general purpose usability.
(however, it does work fine after having solved some problems in the DMS, our product).
- open design issues

I specifically would like to hear from you on the following design issues:
- I am considering to change the definition of the above mentioned m_Seqs to:
    std::vector<std::pair<size_t, size_t> > m_Seqs;
where m_Seqs[i].first and second are offsets of the start and end of sequence i relative to m_Data.begin().
This avoids adjustment when m_Data grows, for a small const access-time penalty.
- At this point, the destruction of abandoned elements in m_Data
 (= elements not being part anymore of a reallocated sequence),
 is deferrred to the destruction or re-allocation of m_Data.
- the last sequence in m_Data now gets special treatment when it is resized and sufficient reserved
space is available after m_Data.end(). This special treatment saves an order of complexity
when the last sequence often grows, but adds a constant cost to the re-allocation administration.
- generalization to sequece_array arrays (3 levels deep) or higher dimensions.

*/

#if !defined(__SEQUENCE_ARRAY_H)
#define __SEQUENCE_ARRAY_H

//=======================================
// Wrapping of myown facilities library
//=======================================

#include <vector>
#include "dbg/Check.h"
#include "geo/BaseBounds.h"

#if !defined(STD)
#define STD std::
#endif
#if !defined(__BASEBOUNDS_H)
struct Undefined { Undefined() {} };
#endif // !defined(__BASEBOUNDS_H)
#if !defined(MGD_CHECK)
#define MGD_CHECK(x) assert(x)
#endif
//=======================================
// sequence_traits
//=======================================

template <typename T> struct sequence_traits  { typedef STD vector<T> sequence_type; };
//template <typename T> struct sequence_traits<STD vector<T> > { typedef sequence_array<T> sequence_type; };

//=======================================
// sequence_array
//=======================================

template <typename T>
struct sequence_array
{
private:
	typedef sequence_array<T> ThisSequeceArrayType;

   // DataVectorType is usally std::vector<T>.
	// It is sequence_array<U> if T == std::vector<U> in order to support n dimensional structures where n>2
	// sequence_traits<T> is defined elsewhere. 
	// You can define it as STD vector<T> when T is an elementary type or composed thereof.
	typedef sequence_traits<T>::sequence_type   DataVectorType; 

	typedef DataVectorType::const_iterator  const_data_iterator; // compatible with const T*
	typedef DataVectorType::iterator        data_iterator;       // compatible with T*
	typedef DataVectorType::const_reference const_data_reference;// compatible with const T&
	typedef DataVectorType::reference       data_reference;      // compatible with T&
	typedef DataVectorType::size_type       data_size_type; 
	typedef DataVectorType::difference_type data_difference_type;

	//=======================================
	// Sequence<T*> is used as value_type for m_Seqs
	// it identifies a sequence of T's by a beginning (first) and ending (second) iterator
	// It can only be used to access (const) and modify (non-const) elements.
	// For resizing a Sequence, one needs to get and use a sequence_array<T>Reference
	//=======================================

	struct Sequence : STD pair<data_iterator, data_iterator>
	{
		typedef const T              value_type;
		typedef data_size_type       size_type;

		typedef const_data_iterator  const_iterator;
		typedef const_data_reference const_reference;

		// default ctor creates an empty sequence (0 elements as in an empty string)
		Sequence():             STD pair<data_iterator, data_iterator>(data_iterator(), data_iterator()) {}
		// specific ctor to identify a sequence by its b(eginning) and e(nding)
		Sequence(data_iterator b, data_iterator e): STD pair<data_iterator, data_iterator>(b, e) {}

		// special ctor to identify an Undefined sequence (as a NULL string value in SQL)
		Sequence(Undefined):    STD pair<data_iterator, data_iterator>(0, 0) { --first; --second; }

		bool      IsDefined() const { return first+1 != data_iterator(); }
		size_type size()      const { return second - first; }

		// called from AdjustPtrs to accomodate a relocation of m_Data 
		// (f.e. after reloading from persistent storage when the old m_Data.begin() was stored and read back)
		void MovePtrs(data_iterator oldBegin, data_iterator newBegin) 
		{
			if (!IsDefined() || first == data_iterator()) return;
			MGD_CHECK(second != data_iterator() && second+1 != data_iterator());
			first = newBegin + (first - oldBegin);
			second  = newBegin + (second  - oldBegin);
		}
	}; // end of struct Sequence;

	typedef STD vector<Sequence>            SeqsVectorType;
	typedef SeqsVectorType::iterator        seqs_iterator;
	typedef SeqsVectorType::const_iterator  const_seqs_iterator;
	typedef SeqsVectorType::size_type       seqs_size_type; 
	typedef SeqsVectorType::difference_type seqs_difference_type;

	//=======================================
	// const_reference
	//=======================================
	// const_reference refers to a const sequence of T elements.
	// it has (most of) the interface of std::vector<T>
	// we don't need the pointer to the containing sequence_array as we don't reallocate const sequences

	struct ConstReference
	{
		typedef const T              value_type;
		typedef data_size_type       size_type;

		typedef const_data_iterator  const_iterator;
		typedef const_data_reference const_reference;

		// ctor usally called from const_reference sequence_array<T>::operator [](size_type) const;
		ConstReference(const Sequence* ptrPair): m_PtrPair(ptrPair) {}

		// special ctor to identify an Undefined sequence (as a NULL string value in SQL)
		ConstReference(Undefined) : m_PtrPair(0) {}

		// Element ro access
		const_iterator begin() const { MGD_CHECK(m_PtrPair); return m_PtrPair->first; }
		const_iterator end  () const { MGD_CHECK(m_PtrPair); return m_PtrPair->second; }
		size_type      size () const { MGD_CHECK(m_PtrPair); return m_PtrPair->size(); }
		bool           empty() const { return size() == 0; }
		bool           IsDefined() const { return m_PtrPair && m_PtrPair->IsDefined(); }

		const_reference operator[](size_type i) const { MGD_CHECK(m_PtrPair); return *(m_PtrPair->first + i); }

		// compare contents
		bool operator ==(const ConstReference& rhs) const
		{ 
			size_type s = size();
			return s
				? (size() == rhs.size() && STD equal(m_PtrPair->first, m_PtrPair->second, rhs.m_PtrPair->first))
				: IsDefined() ? (rhs.IsDefined() && rhs.size() == 0) : !rhs.IsDefined();
		}
		bool operator < (const ConstReference& rhs) const
		{ 
			return IsDefined()
				? STD lexicographical_compare(begin(), end(), rhs.begin(), rhs.end())
				: rhs.IsDefined(); }

	protected:
		const Sequence* m_PtrPair;

	private:
		// Forbidden
		ConstReference() : m_PtrPair(0) {} 
		void operator =(const ConstReference& rhs){}

		friend struct Reference;
		friend struct ThisSequeceArrayType;
	};

	//=======================================
	// reference
	//=======================================
	// we do need the pointer to the containing sequence_array here to support reallocating the sequence
	// as a result of resize() or insert();

	struct Reference
	{
		typedef T              value_type;
		typedef data_size_type size_type;

		typedef data_iterator  iterator;
		typedef data_reference reference;
		typedef const_data_iterator  const_iterator;
		typedef const_data_reference const_reference;

		operator ConstReference() const { return m_PtrPair; }

		// sequence properties
		size_type size () const { MGD_CHECK(m_PtrPair); return m_PtrPair->size(); }
		bool      empty() const { return size() == 0; }
		bool      IsDefined() const { MGD_CHECK(m_PtrPair); return m_PtrPair->IsDefined(); }

		// Element rw access
		iterator  begin() { MGD_CHECK(m_PtrPair); return m_PtrPair->first; }
		iterator  end()   { MGD_CHECK(m_PtrPair); return m_PtrPair->second; }
		reference operator[](size_type i) { MGD_CHECK(m_PtrPair); return *(m_PtrPair->first + i); }

		// Element ro access
		const_iterator  begin() const { MGD_CHECK(m_PtrPair); return m_PtrPair->first; }
		const_iterator  end()   const { MGD_CHECK(m_PtrPair); return m_PtrPair->second; }
		const_reference operator[](size_type i) const { MGD_CHECK(m_PtrPair); return *(m_PtrPair->first + i); }

		// compare contents
		bool operator ==(const Reference& rhs) const
		{ 
	//		return size() == rhs.size() && STD equal(begin(), end(), rhs.end()); 
			size_type s = size();
			return s
				? (size() == rhs.size() && STD equal(m_PtrPair->first, m_PtrPair->second, rhs.m_PtrPair->first))
				: IsDefined() ? (rhs.IsDefined() && rhs.size() == 0) : !rhs.IsDefined();

		}
		bool operator < (const Reference& rhs) const
		{ 
			return IsDefined()
				? STD lexicographical_compare(m_PtrPair->first, m_PtrPair->second, rhs.begin(), rhs.end())
				: rhs.IsDefined();
		}
		// sequence assignment
		void assign(const T* first, const T* last) 
		{
			MGD_CHECK(m_Container);
			m_Container->allocateSequence(m_PtrPair, first, last);
			MGD_CHECK(m_PtrPair->size() == last - first);
		}
		void assign(Undefined) 
		{
			MGD_CHECK(m_Container);
			m_Container->m_ActualDataSize -= m_PtrPair->size();
			*m_PtrPair = Sequence(Undefined());
		}

		void erase(T* first, T* last)
		{
			MGD_CHECK(m_Container);
			m_Container->allocateSequence(m_PtrPair, STD copy(last, end(), first) - begin());
		}
		void resize(size_type seqSize, const value_type& zero = value_type())
		{
			MGD_CHECK(m_Container);
			if (seqSize == UNDEFINED_VALUE(size_type))
				assign(Undefined());
			else
				if (seqSize > size() || (seqSize == 0 && !IsDefined()))
					m_Container->allocateSequence(m_PtrPair, seqSize, zero);
		}

		void push_back(const value_type& zero = value_type())
		{
			MGD_CHECK(m_PtrPair);
			MGD_CHECK(m_PtrPair->size() == 0 || m_PtrPair->second == m_Container->m_Data.end());
			m_Container->allocateSequence(m_PtrPair, m_PtrPair->size()+1, zero);
		}

		void operator =(ConstReference rhs) 
		{ 
			if (rhs.IsDefined()) 
				assign(rhs.begin(), rhs.end()); 
			else 
				assign(Undefined()); 
		}
		void operator =(Reference rhs) 
		{ 
			MGD_CHECK(m_Container);
			if (m_Container == rhs.m_Container)
			{
				m_Container->m_ActualDataSize -= size();
				*m_PtrPair = *rhs.m_PtrPair;
				m_Container->m_ActualDataSize += size();
			}
			else if (rhs.IsDefined())
				assign(rhs.begin(), rhs.end()); 
			else assign(Undefined());
		}
	protected:
		Sequence*       m_PtrPair;
		ThisSequeceArrayType* m_Container;


		Reference(ThisSequeceArrayType* container, Sequence* ptrPair)
			: m_Container(container), m_PtrPair(ptrPair) {};
		Reference() : m_Container(0), m_PtrPair(0) {}

	private:
		friend struct sequence_array<T>;
	};

	//=======================================
	// const_iterator
	//=======================================

	struct ConstIterator:
		private ConstReference, 
		public STD iterator<STD random_access_iterator_tag, ConstReference >
	{
		typedef ConstIterator                     ThisType;

		ConstIterator() {}
		ConstIterator(const Sequence* ptrPair)
			: ConstReference(ptrPair) {};

		ConstReference operator *() const // const dereference
		{
			MGD_CHECK(m_PtrPair);
			return *this;
		}

		const ConstReference* operator ->() const // const dereference
		{
			MGD_CHECK(m_PtrPair);
			return this;
		}

		ThisType operator +(seqs_difference_type displacement) const
		{
			MGD_CHECK(m_PtrPair);
			ThisType tmp = *this;
			tmp.m_PtrPair += displacement;
			return tmp;
		}

		ThisType operator -(seqs_difference_type displacement) const { return *this + - displacement; }
		seqs_difference_type operator -(ThisType rhs) const { return m_PtrPair - rhs.m_PtrPair; }

		ConstReference operator[](size_type i) const 
		{ 
			MGD_CHECK(m_PtrPair); 
			return *(*this + i);
		}

		void operator += (seqs_difference_type displacement) { MGD_CHECK(m_PtrPair); m_PtrPair += displacement; }
		void operator -= (seqs_difference_type displacement) { MGD_CHECK(m_PtrPair); m_PtrPair -= displacement; }

		ThisType& operator ++() // prefix; return new value
		{
			++m_PtrPair;
			return *this;
		}

		ThisType operator ++(int) // postfix; return old value
		{
			MGD_CHECK(m_PtrPair);
			ThisType tmp = *this;
			++m_PtrPair;
			return tmp;
		}

		ThisType& operator --() // prefix; return new value
		{
			MGD_CHECK(m_PtrPair);
			--m_PtrPair;
			return *this;
		}

		ThisType operator --(int) // postfix; return old value
		{
			MGD_CHECK(m_PtrPair);
			ThisType tmp = *this;
			--m_PtrPair;
			return tmp;
		}

		void operator =(const ThisType& rhs)
		{
			m_PtrPair = rhs.m_PtrPair;
		}

		bool operator ==(ThisType rhs) const { return m_PtrPair == rhs.m_PtrPair; }
		bool operator !=(ThisType rhs) const { return m_PtrPair != rhs.m_PtrPair; }
		bool operator < (ThisType rhs) const { return m_PtrPair < rhs.m_PtrPair; }
		bool operator <=(ThisType rhs) const { return !(rhs < *this); }
	};
	//=======================================
	// iterator
	//=======================================

	struct Iterator:
		private Reference, 
		public STD iterator<STD random_access_iterator_tag, Reference >
	{
		typedef Iterator        ThisType;

		Iterator() {}
		Iterator(ThisSequeceArrayType* container, Sequence* ptrPair)
			: Reference(container, ptrPair) {};

		Reference& operator *() const // dereference
		{
			MGD_CHECK(m_PtrPair);
			return const_cast<ThisType&>(*this);
		}

		Reference* operator ->() const // dereference
		{
			MGD_CHECK(m_PtrPair);
			return const_cast<ThisType*>(this);
		}

		Reference operator[](size_type i) const
		{ 
			MGD_CHECK(m_PtrPair && m_Container && (m_PtrPair + i) < m_Container.size() ); 
			return *(*this + i); 
		}
		operator ConstIterator() const // to const
		{
			return ConstIterator(m_PtrPair);
		}

		ThisType operator +(seqs_difference_type displacement) const
		{
			MGD_CHECK(m_PtrPair);
			ThisType tmp = *this;
			tmp.m_PtrPair += displacement;
			return tmp;
		}

		ThisType operator -(seqs_difference_type displacement) const { return *this + - displacement; }
		seqs_difference_type operator -(ThisType rhs) const { MGD_CHECK(m_Container == rhs.m_Container); return m_PtrPair - rhs.m_PtrPair; }

		void operator += (seqs_difference_type displacement) { MGD_CHECK(m_PtrPair); m_PtrPair += displacement; }
		void operator -= (seqs_difference_type displacement) { MGD_CHECK(m_PtrPair); m_PtrPair -= displacement; }

		ThisType& operator ++() // prefix; return new value
		{
			MGD_CHECK(m_PtrPair);
			++m_PtrPair;
			return *this;
		}

		ThisType operator ++(int) // postfix; return old value
		{
			MGD_CHECK(m_PtrPair);
			ThisType tmp = *this;
			++m_PtrPair;
			return tmp;
		}

		ThisType& operator --() // prefix; return new value
		{
			MGD_CHECK(m_PtrPair);
			--m_PtrPair;
			return *this;
		}

		ThisType operator --(int) // postfix; return old value
		{
			MGD_CHECK(m_PtrPair);
			ThisType tmp = *this;
			--m_PtrPair;
			return tmp;
		}

		void operator =(const ThisType& rhs)
		{
			m_Container = rhs.m_Container;
			m_PtrPair = rhs.m_PtrPair;
		}

		bool operator ==(const ThisType& rhs) const
		{ 
			MGD_CHECK(m_Container == rhs.m_Container || m_PtrPair != rhs.m_PtrPair);
			return m_PtrPair == rhs.m_PtrPair;
		}
		bool operator !=(const ThisType& rhs) const
		{ 
			MGD_CHECK(m_Container == rhs.m_Container || m_PtrPair != rhs.m_PtrPair);
			return m_PtrPair != rhs.m_PtrPair;
		}
		bool operator <(const ThisType& rhs) const
		{ 
			MGD_CHECK(m_Container == rhs.m_Container || m_PtrPair != rhs.m_PtrPair);
			return m_PtrPair < rhs.m_PtrPair;
		}
		bool operator <=(const ThisType& rhs) const { return !(rhs < *this); }
	};

public:
	typedef seqs_size_type       size_type;
	typedef seqs_difference_type difference_type;

	typedef struct ConstReference const_reference;
	typedef struct Reference      reference;
	typedef struct ConstIterator  const_iterator;
	typedef struct Iterator       iterator;
	typedef struct ConstReference value_type;

	//=======================================
	// sequence_array constructors
	//=======================================


	sequence_array() : m_ActualDataSize(0) {}
	sequence_array(size_type n)  { Reset(0, n); }
	sequence_array(const_iterator first, const_iterator last)
	{
		Reset(CalcActualDataSize(first, last) , last-first);
		SeqcContainer::iterator seqs = m_Seqs.begin();
		while (first != last)
		{
			allocateSequence(seqs++, first->begin(), first->end());
			++first;
		}
	}
	sequence_array(const ThisSequeceArrayType& src, data_size_type expectedGrowth = 0)
		: m_ActualDataSize(src.m_ActualDataSize)
	{
		data_reserve(src.ActualDataSize() + expectedGrowth);
		resize(src.size(), Undefined());

		SeqsVectorType::const_iterator
			i = src.m_Seqs.begin(),
			e = src.m_Seqs.end();
		SeqsVectorType::iterator
			ri = m_Seqs.begin();
		MGD_CHECK(ri+(e-i) == m_Seqs.end());

		DataVectorType::iterator dataEnd = m_Data.end();
		while (i!=e) 
		{
			if (i->IsDefined())
			{
				DataVectorType::size_type size = i->size();
				m_Data.insert(dataEnd, i->first, i->second);
				ri->first = dataEnd;
				dataEnd += size;
				MGD_CHECK(dataEnd == m_Data.end());
				ri->second = dataEnd;
			}
			++i; ++ri;
		}
		MGD_CHECK(ActualDataSize(m_Seqs.begin(), m_Seqs.end()) == m_ActualDataSize);
		MGD_CHECK(!IsDirty());
	}

	void swap(ThisSequeceArrayType& rhs)
	{
		m_Data.swap(rhs.m_Data);
		m_Seqs.swap(rhs.m_Seqs);
		STD swap(m_ActualDataSize, rhs.m_ActualDataSize);
	}

	//=======================================
	// sequence_array collection modification
	//=======================================

	void erase(const iterator& first, const iterator& last)
	{
		MGD_CHECK(first == last || (first.m_Container == this && last.m_Container == this));

		UInt32 dataSize = CalcActualDataSize(first, last);
		MGD_CHECK(dataSize <= m_ActualDataSize);
		m_ActualDataSize -= dataSize;
		m_Seqs.erase(first.m_PtrPair, last.m_PtrPair);
	}

	void reserve(size_type n) { m_Seqs.reserve(n); }
	void push_back(Undefined)
	{
		m_Seqs.push_back(Sequence(Undefined())); 
	}

	void push_back(const T* first, const T* last)
	{
		m_Seqs.push_back(Sequence()); 
		allocateSequence(m_Seqs.end()-1, first, last);
	}
	
	//=======================================
	// sequence_array statistice
	//=======================================

	size_type size() const           { return m_Seqs.size(); }
	size_type capacity() const       { return m_Seqs.capacity(); }
	size_type ActualDataSize() const { return m_ActualDataSize; }

	//=======================================
	// sequence_array data access
	//=======================================

	const_reference operator [](size_type i) const
	{
		MGD_CHECK(i<size());
		return const_reference(m_Seqs.begin() + i);
	}
	reference operator [](size_type i)
	{ 
		MGD_CHECK(i<size());
		return reference(this, m_Seqs.begin() + i); 
	}
	const_iterator begin() const { return const_iterator(m_Seqs.begin()); }
	const_iterator end()   const { return const_iterator(m_Seqs.end());   }
	iterator       begin()       { return iterator(this, m_Seqs.begin()); }
	iterator       end()         { return iterator(this, m_Seqs.end()); ; }

	//=======================================
	// sequence_array memory allocation control
	//=======================================

	void Reset(DataVectorType::size_type expectedDataSize, size_type nrSeqs)
	{
		vector_clear(m_Data);
		data_reserve(expectedDataSize);
		vector_fill_n(m_Seqs, nrSeqs, Undefined());
		m_ActualDataSize = 0;
	}

	void data_reserve(DataVectorType::size_type expectedDataSize)
	{
		m_Data.reserve(expectedDataSize);
	}

	void ReAllocate(DataVectorType::size_type expectedGrowth = 0)
	{
		// NYI: doe alleen m_Data en laat m_Seqs ongemoeid
		if (!IsDirty() && (expectedGrowth+m_Data.size() <= m_Data.capacity()))
			return;

		DataVectorType oldData;
		ReAllocate(oldData, expectedGrowth);
	}

	void ReAllocate(DataVectorType& oldData, DataVectorType::size_type expectedGrowth = 0)
	{
		STD swap(m_Data, oldData);

		data_reserve(ActualDataSize() + expectedGrowth);

		SeqsVectorType::iterator
			i = m_Seqs.begin(),
			e = m_Seqs.end();

		DataVectorType::iterator dataEnd = m_Data.end();
		while (i!=e) 
		{
			if (i->IsDefined())
			{
				DataVectorType::size_type size = i->size();
				m_Data.insert(dataEnd, i->first, i->second);
				i->first = dataEnd;
				dataEnd += size;
				MGD_CHECK(dataEnd == m_Data.end());
				i->second = dataEnd;
			}
			++i;
		}
#if defined(MG_DEBUG)
		UInt32 as = CalcActualDataSize(m_Seqs.begin(), m_Seqs.end());
		MGD_CHECK(as == m_ActualDataSize);
		MGD_CHECK(!IsDirty());
#endif
	}

	void cut(size_type nrSeqs)
	{
		bool keepMoreThanHalf = (nrSeqs > size() / 2);
		if (keepMoreThanHalf)  m_ActualDataSize -= CalcActualDataSize(m_Seqs.begin() + nrSeqs, m_Seqs.end());
		vector_cut(m_Seqs, nrSeqs);
		if (!keepMoreThanHalf) m_ActualDataSize = CalcActualDataSize(m_Seqs.begin(), m_Seqs.end());
	}

	void resize(size_type nrSeqs)            { m_Seqs.resize(nrSeqs); }
	void resize(size_type nrSeqs, Undefined) { m_Seqs.resize(nrSeqs, Undefined()); }

	bool CanContain (const_iterator p) const
	{
		return !(p->begin() < m_Data.begin())
			&& !(m_Data.end()< p->end());
	}
	bool DoesContain(const_iterator p) const
	{
		return p < m_Seqs.end() && !(p < m_Seqs.begin());
	}

	bool IsDirty() const 
	{
		MGD_CHECK(m_ActualDataSize <= m_Data.size());
		return (m_ActualDataSize != m_Data.size());
	}

protected:
	void allocateSequence(Sequence* seqPtr, data_size_type newSize, const T& zero = T())
	{
		MGD_CHECK(seqPtr && m_ActualDataSize >= seqPtr->size());
		DataVectorType::size_type       oldSize = seqPtr->size();
		DataVectorType::difference_type delta   =  newSize - oldSize;
		bool atEnd = (seqPtr->second == m_Data.end());

		if (delta > 0)
		{
			if ((atEnd ? delta : newSize) <= m_Data.capacity() - m_Data.size())
			{
				if (!atEnd)
				{
					InsertData(seqPtr->first, seqPtr->second); // copy oldSize elemeents from original 
					Abandon(seqPtr->first, seqPtr->second);    // and abandon that area
				}
				InsertData(delta, zero);
				seqPtr->second = m_Data.end();
				seqPtr->first  = seqPtr->second - newSize;
			}
			else
			{
				DataVectorType oldData;
				DataVectorType::const_iterator
					oldFirst  = seqPtr->first,
					oldSecond = seqPtr->second;
				seqPtr->second = seqPtr->first;
				m_ActualDataSize -= oldSize;
				ReAllocate(oldData, Max(m_ActualDataSize+2*oldSize, newSize) );
				InsertData(oldFirst, oldSecond);
				InsertData(delta, zero);
				seqPtr->second = m_Data.end();
				seqPtr->first  = seqPtr->second - newSize;
				delta += oldSize; MGD_CHECK(delta == newSize);
				MGD_CHECK(m_ActualDataSize + delta == CalcActualDataSize(begin(), end()));
			}
		}
		else
		{
			if (atEnd)
				m_Data.erase(seqPtr->first + newSize, seqPtr->second); // if not: area is abandoned
			if (newSize)
				seqPtr->second = seqPtr->first + newSize;
			else
				seqPtr->first = seqPtr->second = 0;
		}
		m_ActualDataSize += delta;
		MGD_CHECK(newSize == seqPtr->size());
	}

	void allocateSequence(Sequence* seqPtr, const T* first, const T* last)
	{
		MGD_CHECK(seqPtr && m_ActualDataSize >= seqPtr->size());
		DataVectorType::size_type       newSize = last - first;
		DataVectorType::size_type       oldSize = seqPtr->size();
		DataVectorType::difference_type delta   =  newSize - oldSize;
		bool atEnd = (seqPtr->second == m_Data.end());

		if (delta > 0)
		{
			if ((atEnd ? newSize - oldSize : newSize) <= m_Data.capacity() - m_Data.size())
			{
				const T* copyArea = first+oldSize;
				if (!atEnd)
				{
					InsertData(first, copyArea);               // insert first part
					Abandon(seqPtr->first, seqPtr->second);    // and abandon that area
				}
				else
					STD copy(first, copyArea, seqPtr->first);

				InsertData(copyArea, last);                   // insert second part
				seqPtr->second = m_Data.end();
				seqPtr->first  = seqPtr->second - newSize;
			}
			else
			{
				DataVectorType oldData;
				DataVectorType::const_iterator
					oldFirst  = seqPtr->first,
					oldSecond = seqPtr->second;
				seqPtr->second = seqPtr->first;
				m_ActualDataSize -= oldSize;
				ReAllocate(oldData, Max(m_ActualDataSize+2*oldSize, newSize) );
				InsertData(first, last);
				seqPtr->second = m_Data.end();
				seqPtr->first  = seqPtr->second - newSize;
				delta += oldSize; MGD_CHECK(delta == newSize);
				MGD_CHECK(m_ActualDataSize + delta == CalcActualDataSize(begin(), end()));
			}
		}
		else
		{
			STD copy(first, last, seqPtr->first);
			if (seqPtr->second == m_Data.end())
				m_Data.erase(seqPtr->first + newSize, seqPtr->second);
			if (newSize)
				seqPtr->second = seqPtr->first + newSize;
			else
				seqPtr->first = seqPtr->second = 0;
		}
		m_ActualDataSize += delta;
		MGD_CHECK(newSize == seqPtr->size());
	}
private:
	void Abandon(data_iterator first, data_iterator last)
	{
		// NYI
	}

	void InsertData(size_type n, const T& v)
	{
		MGD_CHECK(m_Data.capacity() - m_Data.size() >= n);
		data_iterator oldBegin = m_Data.begin();
		m_Data.insert(m_Data.end(), n, v);
		MGD_CHECK(oldBegin == m_Data.begin());
	}
	void InsertData(const T* first, const T* last)
	{
		MGD_CHECK(m_Data.capacity() - m_Data.size() >= last - first);
		data_iterator oldBegin = m_Data.begin();
		m_Data.insert(m_Data.end(), first, last);
		MGD_CHECK(oldBegin == m_Data.begin());
	}

	void AdjustPtrs(data_iterator oldDataBegin, data_iterator newDataBegin)
	{
		if (oldDataBegin != newDataBegin)
		{
			seqs_iterator 
				i = m_Seqs.begin(),
				e = m_Seqs.end();
			while (i != e)
				(*i++).MovePtrs(&*oldDataBegin, &*newDataBegin);
		}
	}

	static data_size_type CalcActualDataSize(ConstIterator first, ConstIterator last)
	{
		data_size_type result = 0;
		while (first != last)
			result += (*first++).size();
		return result;
	}

	SeqsVectorType m_Seqs;    // for identifying allocated sequences
	DataVectorType m_Data;    // for sequential storage of sequences of T (the memory pool)
	data_size_type m_ActualDataSize; // no of elements in allocated sequences (not abandoned elements)

	friend struct Reference;
	friend struct BinaryOutStream& operator << (struct BinaryOutStream& ar, const sequence_array<T>& vec);
	friend struct BinaryInpStream& operator >> (struct BinaryInpStream& ar,       sequence_array<T>& vec);
};


//----------------------------------------------------------------------
// Section: Assign helper func for assignment of sequence to/from sequence, vector or String
//----------------------------------------------------------------------

template <typename T> inline void Assign(sequence_array<T>::reference& lhs, sequence_array<T>::const_reference rhs) { lhs = rhs; }
template <typename T> inline void Assign(sequence_array<T>::reference& lhs, sequence_array<T>::reference       rhs) { lhs = rhs; }

template <typename T> inline void Assign(sequence_array<T>::reference& lhs, const STD vector<T>& rhs) 
{ 
	if (IsDefined(rhs))
		lhs.assign(MAKE_PTR(rhs.begin()), MAKE_PTR(rhs.end())); 
	else
		lhs.assign(Undefined());
}

template <typename T> inline void Assign(STD vector<T>&  lhs, const sequence_array<T>::const_reference&   rhs) 
{ 
	lhs.assign(rhs.begin(), rhs.end()); 
}



#endif // !defined(__SEQUENCE_ARRAY_H)