list.h

Go to the documentation of this file.

// Evo C++ Library
/* Copyright 2019 Justin Crowell
Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
*/

#pragma once
#ifndef INCL_evo_list_h
#define INCL_evo_list_h

#include "impl/container.h"
#include "impl/iter.h"

// Disable certain MSVC warnings for this file
#if defined(_MSC_VER)
    #pragma warning(push)
    #pragma warning(disable:4458)
#endif

namespace evo {


template<class T,class TSize=SizeT>
class List : public ListBase<T,TSize> {
protected:
    using ListBase<T,TSize>::data_; // Slice data pointer, NULL if null, EVO_PEMPTY if empty (null/empty: buffer unused, no reference)
    using ListBase<T,TSize>::size_; // Slice size, 0 if empty

public:
    EVO_CONTAINER_TYPE;
    typedef TSize               Size;               
    typedef Size                Key;                
    typedef T                   Value;              
    typedef T                   Item;               
    typedef typename DataCopy<T>::PassType ItemVal; 

    typedef List<T,Size>        ThisType;           
    typedef List<T,Size>        ListType;           
    typedef ListBase<T,Size>    ListBaseType;       

    // Iterator support types
    typedef Key IterKey;
    typedef T   IterItem;
    typedef typename IteratorRa<ThisType>::Const Iter;      
    typedef IteratorRa<ThisType>                 IterM;     

    struct Edit {
        T*    ptr;      
        Size  size;     
        void* header;   

        Edit() : ptr(NULL), size(0), header(NULL)
            { }

        ~Edit() {
            if (header != NULL)
                ::free(header);
        }

        void clear() {
            if (header != NULL) {
                ::free(header);
                header = NULL;
            }
            ptr  = NULL;
            size = 0;
        }

        Size write(const ListBaseType& src, Size start=0, Size count=ALL) {
            if (start < src.size_ && count > 0) {
                const Size maxcount = src.size_ - start;
                if (count > maxcount)
                    count = maxcount;
                DataInit<Item>::init(ptr + size, src.data_, count);
                size += count;
            } else
                count = 0;
            return count;
        }

        Size write(const Item* data, Size count) {
            if (count > 0) {
                assert( data != NULL );
                DataInit<Item>::init(ptr + size, data, count);
                size += count;
            }
            return count;
        }
    };

    List() {
        data_ = NULL;
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
    }

    explicit List(const ValEmpty& val) {
        EVO_PARAM_UNUSED(val);
        data_ = EVO_PEMPTY;
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
    }

    List(const ListType& data) {
        data_ = NULL;
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        ref(data);
    }

    List(const ListType& data, Key index, Key size=ALL) {
        data_ = NULL;
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        ref(data, index, size);
    }

    List(const ListBaseType& data, Key index=0, Key size=ALL) {
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        if (data.data_ == NULL) {
            data_ = NULL;
        } else if (index < data.size_) {
            const Size max_size = data.size_ - index;
            if (size > max_size)
                size = max_size;
            if (size > 0)
                copy(data.data_+index, size);
            else
                data_ = EVO_PEMPTY;
        } else
            data_ = EVO_PEMPTY;
    }

    List(const ListBaseType* data, Key index=0, Key size=ALL) {
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        if (data == NULL || data->data_ == NULL) {
            data_ = NULL;
        } else if (index < data->size_) {
            const Size max_size = data->size_ - index;
            if (size > max_size)
                size = max_size;
            if (size > 0)
                copy(data->data_+index, size);
            else
                data_ = EVO_PEMPTY;
        } else
            data_ = EVO_PEMPTY;
    }

    List(const Item* data, Size size) {
        data_ = NULL;
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        if (data != NULL)
            ref(data, size);
    }

    List(const PtrBase<Item>& data, Size size) {
        data_ = NULL;
        size_ = 0;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        if (data.ptr_ != NULL)
            copy(data.ptr_, size);
    }

#if defined(EVO_CPP11)

    List(std::initializer_list<T> init) : List() {
        assert( init.size() < IntegerT<Size>::MAX );
        modAppend(NULL, (Size)init.size());
        T* item = data_;
        for (auto& val : init)
            new(item++) T(val);
    }

    List(ListType&& src) {
        ::memcpy(this, &src, sizeof(ListType));
        ::memset(&src, 0, sizeof(ListType));
    }

    ListType& operator=(ListType&& src) {
        clear();
        capacity(0);
        ::memcpy(this, &src, sizeof(ListType));
        ::memset(&src, 0, sizeof(ListType));
        return *this;
    }
#endif

    const ListType& asconst() const {
        return *this;
    }

    // SET

    ListType& operator=(const ListType& data)
        { return set(data); }

    ListType& operator=(const ListBaseType& data) {
        if (data.data_ == NULL)
            set();
        else if (data.size_ > 0)
            copy(data.data_, data.size_);
        else
            setempty();
        return *this;
    }

    ListType& operator=(const ValNull&)
        { return set(); }

    ListType& operator=(const ValEmpty&)
        { clear(); data_ = EVO_PEMPTY; return *this; }

    ListType& clear() {
        if (data_ > EVO_PEMPTY) {
            if (buf_.ptr != NULL) {
                assert( buf_.header != NULL );
                if (buf_.header->refs > 1) {
                    // Detach from shared
                    --buf_.header->refs;
                    buf_.header = NULL;
                    buf_.ptr    = NULL;
                    data_       = EVO_PEMPTY;
                } else if (buf_.header->used > 0) {
                    // Clear buffer, leave buffer for later use
                    assert( buf_.header->refs == 1 );
                    DataInit<T>::uninit(buf_.ptr, buf_.header->used);
                    buf_.header->used = 0;
                    data_             = buf_.ptr;
                }
            } else {
                data_ = EVO_PEMPTY;
                #if !EVO_LIST_OPT_LAZYBUF
                    // Lazy buffer disabled
                    assert( buf_.header == NULL );
                #endif
            }
            size_ = 0;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        #if !EVO_LIST_OPT_LAZYBUF
            // Lazy buffer disabled
            assert( (buf_.header != NULL) == (buf_.ptr != NULL) );
        #endif
        return *this;
    }

    ListType& set()
        { clear(); data_ = NULL; return *this; }

    ListType& set(const Item* data, Size size)
        { ref(data, size); return *this; }

    ListType& set(const PtrBase<Item>& data, Size size) {
        if (data.ptr_ == NULL)
            set();
        else
            copy(data.ptr_, size);
        return *this;
    }

    ListType& set(const ListType& data)
        { ref(data); return *this; }

    ListType& set(const ListType& data, Key index, Key size=ALL)
        { ref(data, index, size); return *this; }

    ListType& set(const ListBaseType& data, Key index=0, Key size=ALL) {
        if (data.data_ == NULL)
            set();
        else if (index < data.size_) {
            const Size max_size = data.size_ - index;
            if (size > max_size)
                size = max_size;
            if (size > 0)
                copy(data.data_+index, size);
            else
                setempty();
        } else
            setempty();
        return *this;
    }

    ListType& set2(const ListType& data, Key index1, Key index2)
        { ref(data, index1, (index1<index2?index2-index1:0)); return *this; }

    ListType& set2(const ListBaseType& data, Key index1, Key index2) {
        if (data.data_ == NULL) {
            set();
        } else {
            if (index2 > data.size_)
                index2 = data.size_;
            if (index1 < data.size_ && index2 > index1)
                copy(data.data_+index1, (index2-index1));
            else
                setempty();
        }
        return *this;
    }

    ListType& setempty()
        { clear(); data_ = EVO_PEMPTY; return *this; }

    // INFO

    bool null() const
        { return (data_ == NULL); }

    bool empty() const
        { return (size_ == 0); }

    Size size() const
        { return size_; }

    bool shared() const
        { return (buf_.ptr == NULL ? (size_ > 0) : (buf_.header->refs > 1)); }

    Size capacity() const
        { return (buf_.header == NULL ? 0 : buf_.header->size); }

    const Item* data() const
        { return data_; }

    const Item& operator[](Key index) const
        { assert( index < size_ ); return data_[index]; }

    const Item& item(Key index) const
        { assert( index < size_ ); return data_[index]; }

    const Item* first() const
        { return (size_ > 0 ? data_ : NULL); }

    const Item* last() const
        { return (size_ > 0 ? data_+size_-1 : NULL); }

    Key iend(Size offset=0) const
        { return (offset < size_ ? size_-1-offset : END); }

    ulong hash(ulong seed=0) const
        { return DataHash<T>::hash(data_, size_, seed); }

    // COMPARE

    int compare(const ListBaseType& data) const {
        int result;
        if (data_ == NULL)
            result = (data.data_ == NULL ? 0 : -1);
        else if (data.data_ == NULL)
            result = 1;
        else
            result = DataCompare<T>::compare(data_, size_, data.data_, data.size_);
        return result;
    }

    bool operator==(const ListBaseType& data) const {
        bool result;
        if (data_ == NULL)
            result = (data.data_ == NULL);
        else if (data.data_ == NULL || size_ != data.size_)
            result = false;
        else if (size_ == 0 || data_ == data.data_) {
            result = true;
        } else
            result = DataEqual<T>::equal(data_, data.data_, data.size_);
        return result;
    }
    
    bool operator!=(const ListBaseType& data) const {
        bool result;
        if (data_ == NULL)
            result = (data.data_ != NULL);
        else if (data.data_ == NULL || size_ != data.size_)
            result = true;
        else if (size_ == 0 || data_ == data.data_) {
            result = false;
        } else
            result = !DataEqual<T>::equal(data_, data.data_, data.size_);
        return result;
    }

    bool starts(ItemVal item) const
        { return (size_ > 0 && data_[0] == item); }

    bool starts(const Item* items, Size size) const
        { return (size > 0 && size_ >= size && DataEqual<T>::equal(data_, items, size)); }

    bool starts(const ListBaseType& items) const
        { return (items.size_ > 0 && size_ >= items.size_ && DataEqual<T>::equal(data_, items.data_, items.size_)); }

    bool ends(ItemVal item) const
        { return (size_ > 0 && data_[size_-1] == item); }

    bool ends(const Item* items, Size size) const
        { return (size > 0 && size_ >= size && DataEqual<T>::equal(data_+(size_-size), items, size)); }

    bool ends(const ListBaseType& items) const
        { return (items.size_ > 0 && size_ >= items.size_ && DataEqual<T>::equal(data_+(size_-items.size_), items.data_, items.size_)); }

    // FIND

    Iter cbegin() const
        { return Iter(*this); }

    Iter cend() const
        { return Iter(); }

    IterM begin()
        { return IterM(*this); }

    Iter begin() const
        { return Iter(*this); }

    IterM end()
        { return IterM(); }

    Iter end() const
        { return Iter(); }

    Key find(ItemVal item, Key start=0, Key end=END) const {
        if (end > size_)
            end = size_;
        for (; start < end; ++start)
            if (data_[start] == item)
                return start;
        return NONE;
    }

    Key findr(ItemVal item, Key start=0, Key end=END) const {
        if (end > size_)
            end = size_;
        while (end > start)
            if (data_[--end] == item)
                return end;
        return NONE;
    }

    Key findany(const Item* items, Size count, Key start=0, Key end=END) const {
        Size j;
        if (end > size_)
            end = size_;
        for (; start < end; ++start)
            for (j=0; j<count; ++j)
                if (data_[start] == items[j])
                    return start;
        return NONE;
    }

    Key findanyr(const Item* items, Size count, Key start=0, Key end=END) const {
        Size j;
        if (end > size_)
            end = size_;
        while (end>start) {
            --end;
            for (j=0; j < count; ++j)
                if (data_[end] == items[j])
                    return end;
        }
        return NONE;
    }

    bool contains(ItemVal item) const {
        bool result = false;
        for (Key i=0; i < size_; ++i)
            if (data_[i] == item)
                { result = true; break; }
        return result;
    }

    bool contains(const Item* data, Size size) const {
        bool result = false;
        if (size > 0 && size_ >= size) {
            const Size end = size_ - size;
            for (Key i=0; i <= end; ++i)
                if (DataEqual<T>::equal(data_+i, data, size))
                    { result = true; break; }
        }
        return result;
    }

    bool contains(const ListBaseType& data) const {
        bool result = false;
        if (data.size_ > 0 && size_ >= data.size_) {
            const Size end = size_ - data.size_;
            for (Key i=0; i <= end; ++i)
                if (DataEqual<T>::equal(data_+i, data.data_, data.size_))
                    { result = true; break; }
        }
        return result;
    }

    // SPLIT

    template<class T1,class T2>
    bool splitat(Key index, T1& left, T2& right) const {
        bool result;
        if (index >= size_) {
            left.set(*this);
            right.set();
            result = false;
        } else {
            left.set(*this, 0, index);
            right.set(*this, index+1, ALL);
            result = true;
        }
        return result;
    }

    template<class T1>
    bool splitat(Key index, T1& left) const {
        bool result;
        if (index >= size_) {
            left.set(*this);
            result = false;
        } else {
            left.set(*this, 0, index);
            result = true;
        }
        return result;
    }

    template<class T2>
    bool splitat(Key index, ValNull left, T2& right) const {
        EVO_PARAM_UNUSED(left);
        bool result;
        if (index >= size_) {
            right.set();
            result = false;
        } else {
            right.set(*this, index+1, ALL);
            result = true;
        }
        return result;
    }

    // SPLIT_SET

    bool splitat_setl(Key index) {
        bool result;
        if (index >= size_) {
            result = false;
        } else {
            slice(0, index);
            result = true;
        }
        return result;
    }

    template<class T2>
    bool splitat_setl(Key index, T2& right) {
        bool result;
        if (index >= size_) {
            right.set();
            result = false;
        } else {
            right.set(*this, index+1, ALL);
            slice(0, index);
            result = true;
        }
        return result;
    }

    bool splitat_setr(Key index) {
        bool result;
        if (index >= size_) {
            set();
            result = false;
        } else {
            slice(index+1, ALL);
            result = true;
        }
        return result;
    }

    template<class T1>
    bool splitat_setr(Key index, T1& left) {
        bool result;
        if (index >= size_) {
            left.set(*this);
            set();
            result = false;
        } else {
            left.set(*this, 0, index);
            slice(index+1, ALL);
            result = true;
        }
        return result;
    }

    // TRIM

    ListType& triml(Size size) {
        if (size > size_)
            size = size_;
        if (size > 0) {
            size_ -= size;
            data_ += size;
        }
        return *this;
    }

    ListType& trimr(Size size) {
        if (size > 0) {
            if (size < size_)
                size_ -= size;
            else
                size_ = 0;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    ListType& truncate(Size size=0) {
        if (size < size_) {
            size_       = size;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    // SLICE

    ListType& slice(Key index) {
        if (index > 0) {
            if (index >= size_) {
                // Empty end slice
                data_ = data_ + size_;
                size_ = 0;
            } else {
                // Normal slice
                data_  = data_ + index;
                size_ -= index;
            }
        }
        return *this;
    }

    ListType& slice(Key index, Size size) {
        if (index > 0) {
            if (index >= size_) {
                // Empty end slice
                size_ = 0;
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = false;
                #endif
            } else {
                // Normal slice
                data_ = data_ + index;
                size_ -= index;
                if (size < size_) {
                    size_       = size;
                    #if EVO_LIST_OPT_REFTERM
                        terminated_ = false;
                    #endif
                }
            }
        } else if (size < size_) {
            size_       = size;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    ListType& slice2(Key index1, Key index2)
        { return slice(index1, (index1 < index2 ? index2-index1 : 0)); }

    ListType& unslice() {
        if (buf_.ptr != NULL && buf_.header->used > size_) {
            if (buf_.header->refs > 1) {
                // New buffer, was shared
                --buf_.header->refs;
                if (size_ > 0) {
                    assert( data_ != NULL );
                    buf_.ptr = (Item*)buf_.memalloc(Capacity::init(size_+1), size_, buf_.header);
                    DataInit<Item>::init(buf_.ptr, data_, size_);
                       data_ = buf_.ptr;
                } else {
                    buf_.header = NULL;
                    buf_.ptr    = NULL;
                    data_       = EVO_PEMPTY;
                }
            } else {
                // Existing buffer, unslice
                assert( buf_.header->refs == 1 );
                assert( buf_.header->used > 0 );
                unsliceBuffer(size_);
            }
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    // INFO_SET

    T* dataM()
        { unshare(); return data_; }

    T& operator()(Key index)
        { assert( index < size_ ); unshare(); return data_[index]; }

    T& itemM(Key index)
        { assert( index < size_ ); unshare(); return data_[index]; }

    Item* firstM()
        { unshare(); return (size_ > 0 ? data_ : NULL); }

    Item* lastM()
        { unshare(); return (size_ > 0 ? data_+size_-1 : NULL); }

    ListType& capacity(Size size) {
        #if !EVO_LIST_OPT_LAZYBUF
            // Lazy buffer disabled
            assert( (buf_.header != NULL) == (buf_.ptr != NULL) );
        #endif
        if (buf_.header != NULL) {
            #if EVO_LIST_OPT_LAZYBUF
                if (buf_.ptr == NULL) {
                    // Existing buffer, unused
                    assert( buf_.header->used == 0 );
                    assert( buf_.header->refs == 1 );
                    if (buf_.header->size != size) {
                        if (size_ > size) {
                            size_ = size;
                            #if EVO_LIST_OPT_REFTERM
                                terminated_ = false;
                            #endif
                        }
                        buf_.memfree();
                        if (size > 0)
                            buf_.memalloc(size, 0, buf_.header);
                        else {
                            buf_.header = NULL;
                            if (data_ != NULL)
                                data_ = EVO_PEMPTY;
                        }
                    }
                } else
            #else
                // Lazy buffer disabled
                assert( buf_.ptr != NULL );
            #endif
            if (buf_.header->refs == 1) {
                // Existing buffer
                if (buf_.header->size != size) {
                    if (size > 0) {
                        if (buf_.header->used > 0) {
                            unsliceBuffer(size_);
                            if (size < size_) {
                                // Shrinking capacity, removing items
                                DataInit<T>::uninit(buf_.ptr+size, buf_.header->used-size);
                                buf_.ptr          = buf_.memrealloc(size);
                                buf_.header->used = size;
                                size_             = size;
                                #if EVO_LIST_OPT_REFTERM
                                    terminated_ = false;
                                #endif
                            } else
                                // Resizing without affecting items
                                buf_.ptr = buf_.memrealloc(size);
                            data_ = buf_.ptr;
                        } else {
                            // Empty, resizing buffer
                            buf_.ptr = buf_.memrealloc(size);
                            if (data_ != NULL)
                                data_ = buf_.ptr;
                        }
                    } else {
                        buf_.free();
                        buf_.clear();
                        if (data_ != NULL)
                            data_ = EVO_PEMPTY;
                        size_ = 0;
                        #if EVO_LIST_OPT_REFTERM
                            terminated_ = false;
                        #endif
                    }
                }
            } else {
                // Shared buffer
                assert( buf_.header->refs > 1);
                --buf_.header->refs;
                if (size > 0) {
                    if (size_ > size)
                        size_ = size;
                    buf_.ptr = buf_.memalloc(size, size_, buf_.header);
                    if (size_ > 0)
                        DataInit<T>::init(buf_.ptr, data_, size_);
                    data_ = buf_.ptr;
                } else {
                    assert( data_ != NULL );
                    buf_.clear();
                    data_ = EVO_PEMPTY;
                    size_ = 0;
                }
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = false;
                #endif
            }
        } else {
            // New buffer, leave unused
            assert( buf_.ptr == NULL );
            if (size_ > size) {
                size_       = size;
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = false;
                #endif
            }
            if (size > 0) {
                #if EVO_LIST_OPT_LAZYBUF
                    buf_.memalloc(size, 0, buf_.header);
                #else
                    // Lazy buffer disabled so use buffer
                    buf_.ptr = buf_.memalloc(size, size_, buf_.header);
                    if (size_ > 0) {
                        DataInit<T>::init(buf_.ptr, data_, size_);
                        data_ = buf_.ptr;
                    } else if (data_ != NULL)
                        data_ = buf_.ptr;
                    #if EVO_LIST_OPT_REFTERM
                        terminated_ = false;
                    #endif
                #endif
            } else if (data_ != NULL)
                data_ = EVO_PEMPTY;
        }
        assert( size_ <= size );
        assert( size > 0 || data_ == NULL || data_ == EVO_PEMPTY );
        #if !EVO_LIST_OPT_LAZYBUF
            // Lazy buffer disabled
            assert( (buf_.header != NULL) == (buf_.ptr != NULL) );
        #endif
        return *this;
    }

    ListType& capacitymin(Size min) {
        if (buf_.header == NULL)
            capacity(size_ > min ? size_ : min);
        else if (min > buf_.header->size)
            capacity(min);
        return *this;
    }

    ListType& capacitymax(Size max) {
        if (buf_.header != NULL && buf_.header->size > max)
            capacity(max);
        else if (size_ > max) {
            size_ = max;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    ListType& compact() {
        if (buf_.header != NULL && buf_.header->refs == 1) {
            const Size min = size_ + CONSERVE;
            if (buf_.header->size > min)
                capacity(min);
        }
        return *this;
    }

    ListType& reserve(Size size, bool prefer_realloc=false) {
        const Size minsize = size_ + size;
        if (buf_.header != NULL) {
            #if EVO_LIST_OPT_LAZYBUF
                if (buf_.ptr == NULL) {
                    if (buf_.header->size >= minsize) {
                        // Use previous buffer
                        assert( buf_.header->refs == 1 );
                        assert( buf_.header->used == 0 );
                        buf_.ptr = (Item*)(buf_.header + 1);
                        if (size_ > 0)
                            DataInit<Item>::init(buf_.ptr, data_, size_);
                        buf_.header->used = size_;
                        data_ = buf_.ptr;
                        #if EVO_LIST_OPT_REFTERM
                            terminated_ = false;
                        #endif
                        return *this;
                    } else {
                        // Previous buffer not big enough, free it
                        buf_.memfree();
                        buf_.header = NULL;
                    }
                } else
            #else
                // Lazy buffer disabled
                assert( buf_.ptr != NULL );
            #endif
            if (buf_.header->refs > 1) {
                // New buffer, was shared
                assert( buf_.ptr != NULL );
                --buf_.header->refs;
            } else {
                // Already unique, ensure buffer is ready, unslice if sliced
                assert( buf_.header->refs == 1 );
                assert( buf_.ptr != NULL );
                if (minsize > buf_.header->size) {
                    if (data_ < buf_.ptr) {
                        // Realloc previous buffer
                        data_ = buf_.ptr = buf_.memrealloc(minsize);
                    } else if (prefer_realloc || data_ == buf_.ptr) {
                        // Either not sliced or prefer realloc
                        assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                        const Size offset = (Size)(data_ - buf_.ptr);
                        buf_.ptr = buf_.memrealloc(minsize);
                        data_ = buf_.ptr + offset;
                    } else
                        goto newbuf;    // unslice and move to new buffer (below)
                } else if (data_ <= EVO_PEMPTY)
                    data_ = buf_.ptr;
                return *this;
            }
        }

        // New buffer
        if (minsize > 0) {
        newbuf:
            if (size_ > 0) {
                buf_.ptr = buf_.memalloc(Capacity::init(minsize+1), size_, buf_.header);
                DataInit<T>::init(buf_.ptr, data_, size_);
                data_ = buf_.ptr;
            } else
                data_ = buf_.ptr = buf_.memalloc(Capacity::init(minsize+1), 0, buf_.header);
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        } else {
            assert( buf_.header == NULL && buf_.ptr == NULL );
        }
        return *this;
    }

    ListType& unshare() {
        if (buf_.header != NULL) {
            #if EVO_LIST_OPT_LAZYBUF
                if (buf_.ptr == NULL) {
                    if (buf_.header->size >= size_) {
                        // Use previous buffer
                        assert( buf_.header->refs == 1 );
                        assert( buf_.header->used == 0 );
                        buf_.ptr = (T*)(buf_.header + 1);
                        if (size_ > 0)
                            DataInit<T>::init(buf_.ptr, data_, size_);
                        buf_.header->used = size_;
                        data_ = buf_.ptr;
                        #if EVO_LIST_OPT_REFTERM
                            terminated_ = false;
                        #endif
                        return *this;
                    } else {
                        // Previous buffer not big enough, free it
                        buf_.memfree();
                        buf_.header = NULL;
                    }
                } else
            #else
                // Lazy buffer disabled
                assert( buf_.ptr != NULL );
            #endif
            if (buf_.header->refs > 1) {
                // New buffer, was shared
                assert( buf_.ptr != NULL );
                --buf_.header->refs;
            } else {
                // Already unique
                assert( buf_.header->refs == 1 );
                assert( buf_.ptr != NULL );
                if (data_ <= EVO_PEMPTY)
                    data_ = buf_.ptr;
                return *this;
            }
        }

        // New buffer
        if (size_ > 0) {
            assert( data_ != NULL );
            buf_.ptr = (T*)buf_.memalloc(Capacity::init(size_+1), size_, buf_.header);
            DataInit<T>::init(buf_.ptr, data_, size_);
               data_ = buf_.ptr;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        } else {
            assert( buf_.header == NULL && buf_.ptr == NULL );
        }
        return *this;
    }

    // RESIZE

    ListType& resize(Size size) {
        if (size == 0) {
            clear();
            capacity(0);
        } else {
            if (buf_.header != NULL) {
                #if EVO_LIST_OPT_LAZYBUF
                    if (buf_.ptr == NULL) {
                        // Use previous buffer
                        assert( buf_.header->used == 0 );
                        assert( buf_.header->refs == 1 );
                        buf_.ptr = (T*)(buf_.header+1);
                        if (size > buf_.header->size)
                            // Grow previous buffer
                            buf_.memrealloc(size);
                        if (size <= size_) {
                            DataInit<T>::init(buf_.ptr, data_, size);
                        } else {
                            if (size_ > 0)
                                DataInit<T>::init(buf_.ptr, data_, size_);
                            DataInit<T>::init_tail_safe(buf_.ptr, size_, size);
                        }
                        data_ = buf_.ptr;
                        buf_.header->used = size_ = size;
                        return *this;
                    } else
                #else
                    // Lazy buffer disabled
                    assert( buf_.ptr != NULL );
                #endif
                if (buf_.header->refs == 1) {
                    // Existing buffer
                    if (buf_.header->used > 0)
                        unsliceBuffer(size < size_ ? size : size_);
                    if (size > buf_.header->size)
                        // Grow buffer
                        buf_.ptr = buf_.memrealloc(size);
                    if (buf_.header->used < size) {
                        // Add items
                        DataInit<T>::init_tail_safe(buf_.ptr, buf_.header->used, size);
                        buf_.header->used = size;
                    }
                    data_ = buf_.ptr;
                    size_ = size;
                    return *this;
                } else {
                    // New buffer, was shared
                    assert( buf_.header->refs > 1 );
                    --buf_.header->refs;
                }
            }

            // New buffer
            if (size_ > 0) {
                assert( data_ != NULL );
                buf_.ptr = (T*)buf_.memalloc(Capacity::init(size+1), size, buf_.header);
                DataInit<T>::init_safe(buf_.ptr, size, data_, size_);
                data_ = buf_.ptr;
            } else {
                data_ = buf_.ptr = (T*)buf_.memalloc(Capacity::init(size+1), size, buf_.header);
                DataInit<T>::init_safe(data_, size);
            }
            size_ = size;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    // COPY

    ListType& copy(const Item* data, Size size) {
        if (buf_.header != NULL) {
            if (buf_.header->refs > 1) {
                // New buffer, was shared
                --buf_.header->refs;
            } else {
                // Existing buffer
                assert( buf_.header->refs == 1 );
                buf_.ptr = (T*)(buf_.header + 1);
                if (buf_.header->used > 0) {
                    DataInit<T>::uninit(buf_.ptr, buf_.header->used);
                    buf_.header->used = 0;
                }
                if (size > buf_.header->size)
                    // Grow buffer
                    buf_.memrealloc(size);
                if (size > 0) {
                    DataInit<T>::init(buf_.ptr, data, size);
                    buf_.header->used = size;
                    data_ = buf_.ptr;
                } else
                    data_ = EVO_PEMPTY;
                size_ = size;
                return *this;
            }
        }

        // New buffer
        if (size > 0) {
            assert( data != NULL );
            data_ = buf_.ptr = (T*)buf_.memalloc(Capacity::init(size+1), size, buf_.header);
            DataInit<T>::init(buf_.ptr, data, size);
        } else {
            buf_.header = NULL;
            buf_.ptr    = NULL;
            data_       = EVO_PEMPTY;
        }
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
        size_ = size;
        return *this;
    }

    ListType& copy(const ListBaseType& data) {
        if (data.data_ == NULL)
            set();
        else
            copy(data.data_, data.size_);
        return *this;
    }

    // ADD

    ListType& addnew(Size size=1)
        { modAppend(EVO_PDEFAULT, size); return *this; }

    ListType& addmin(Size minsize) {
        if (minsize > size_)
            modAppend(EVO_PDEFAULT, minsize - size_);
        return *this;
    }

    ListType& add(const Item* data, Size size)
        { modAppend(data, size); return *this; }

    ListType& add(const ListBaseType& data)
        { modAppend(data.data_, data.size_); return *this; }

    ListType& add(const Item& data)
        { modAppend(&data, 1); return *this; }

    ListType& operator<<(const Item& data)
        { return add(data); }

    ListType& operator<<(const ListBaseType& data)
        { return add(data); }

    ListType& operator<<(const ValNull& val) {
        EVO_PARAM_UNUSED(val);
        clear(); data_ = NULL; return *this;
    }

    ListType& operator<<(const ValEmpty& val) {
        EVO_PARAM_UNUSED(val);
        clear(); data_ = EVO_PDEFAULT; return *this;
    }

    // PREPEND

    ListType& prependnew(Size size=1)
        { modPrepend(EVO_PDEFAULT, size); return *this; }

    ListType& prepend(const Item* data, Size size)
        { modPrepend(data, size); return *this; }

    ListType& prepend(const ListBaseType& data)
        { modPrepend(data.data_, data.size_); return *this; }

    ListType& prepend(const Item& data)
        { modPrepend(&data, 1); return *this; }

    // INSERT

    Size insertnew(Key index, Size size=1)
        { return modInsert(index, EVO_PDEFAULT, size); }

    Size insert(Key index, const Item* data, Size size)
        { return modInsert(index, data, size); }

    Size insert(Key index, const ListBaseType& data)
        { return modInsert(index, data.data_, data.size_); }

    Size insert(Key index, const Item& data)
        { return modInsert(index, &data, 1); }

    // REMOVE

    Size remove(Key index, Size size=1)
        { return modRemove(index, size); }

    // POP

    bool pop(T& item, Key index) {
        bool result;
        if (index < size_) {
            DataInit<T>::copy(&item, data_+index, 1);
            modRemove(index, 1);
            result = true;
        } else 
            result = false;
        return result;
    }

    bool pop(T& item) {
        bool result;
        if (size_ > 0) {
            const Size index = size_ - 1;
            DataInit<T>::copy(&item, data_+index, 1);
            modRemove(index, 1);
            result = true;
        } else 
            result = false;
        return result;
    }

    const Item* pop() {
        const Item* result;
        if (size_ > 0)
            result = data_ + --size_;
        else
            result = NULL;
        return result;
    }

    bool popq(T& item) {
        bool result;
        if (size_ > 0) {
            DataInit<T>::copy(&item, data_, 1);
            modRemove(0, 1);
            result = true;
        } else
            result = false;
        return result;
    }

    const Item* popq() {
        const Item* result;
        if (size_ > 0) {
            result = data_;
            data_  = data_ + 1;
            --size_;
        } else 
            result = NULL;
        return result;
    }

    // FILL

    ListType& fill(const Item& item, Key index=0, Size size=ALL) {
        if (index == END)
            index = size_;
        if (size == ALL)
            size = (index < size_ ? size_ - index : 0);
        if (size > 0) {
            const Size newsize = index + size;
            if (newsize > size_)
                advResize(newsize);
            else
                unshare();
            DataFill<T>::fill(data_+index, size, item);
        }
        return *this;
    }

    // REPLACE

    ListType& replace(Key index, Size rsize, const Item* data, Size size) {
        if (rsize == 0)
            modInsert(index, data, size);
        else if (size == 0)
            modRemove(index, rsize);
        else if (index >= size_)
            modAppend(data, size);
        else
            modReplace(index, rsize, data, size);
        return *this;
    }

    // MOVE / SWAP

    void move(Key dest, Key index) {
        if (index < size_) {
            if (dest >= size_)
                dest = size_ - 1;
            if (index != dest) {
                unshare();
                char buf[sizeof(T)];
                memcpy(buf, data_+index, sizeof(T));
                if (index > dest)
                    // Moving left, shift items right
                    memmove(data_+dest+1, data_+dest, (index-dest)*sizeof(T));
                else
                    // Moving right, shift items left
                    memmove(data_+index, data_+index+1, (dest-index)*sizeof(T));
                memcpy(data_+dest, buf, sizeof(T));
            }
        }
    }

    Size move(Key dest, ListType& src, Key srcindex=0, Size size=ALL) {
        const Size maxsize = (srcindex < src.size_ ? src.size_-srcindex : 0);
        if (size > maxsize)
            size = maxsize;
        if (size > 0) {
            if (dest > size_)
                dest = size_;
            const Size newused = size_ + size;
            if (buf_.header != NULL) {
                #if EVO_LIST_OPT_LAZYBUF
                    if (buf_.ptr == NULL) {
                        if (buf_.header->size >= newused) {
                            // Use previous buffer, there's room
                            assert( size_ > 0 );
                            buf_.ptr = (T*)(buf_.header + 1);
                            if (dest > 0)
                                DataInit<T>::init(buf_.ptr, data_, dest);
                            const Size nextindex = dest + size;
                            if (nextindex < newused)
                                DataInit<T>::init(buf_.ptr+nextindex, data_+dest, newused-nextindex);
                            buf_.header->used = newused;
                            data_             = buf_.ptr;
                            size_             = newused;
                            #if EVO_LIST_OPT_REFTERM
                                terminated_ = false;
                            #endif
                            goto movedata;
                        }
                    } else
                #else
                    // Lazy buffer disabled
                    assert( buf_.ptr != NULL );
                #endif
                if (buf_.header->refs == 1) {
                    // Existing buffer -- mostly copied from modInsertMid()
                    Size offset;
                    if (buf_.header->used > 0) {
                        assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                        offset = (Size)(data_ - buf_.ptr);

                        const Size tailsize = buf_.header->used - size_ - offset;
                        if (tailsize > 0) {
                            DataInit<T>::uninit(data_+size_, tailsize);
                            buf_.header->used -= tailsize;
                        }
                    } else {
                        offset = 0;
                        data_  = buf_.ptr;
                    }
                    if (newused > buf_.header->size) {
                        // Move to new bigger buffer
                        Size newbufsize = Capacity::grow(buf_.header->size);
                        if (newbufsize <= newused)
                            newbufsize = newused + 1; // Leave extra space
                        Header* newheader;
                        T* newbuf = buf_.memalloc(newbufsize, newused, newheader);
                        if (dest > 0)
                            memcpy(newbuf, data_, sizeof(T)*dest);
                        const Size tailsize = size_ - dest;
                        if (tailsize > 0)
                            memcpy(newbuf+dest+size, data_+dest, sizeof(T)*tailsize);
                        if (offset > 0)
                            DataInit<T>::uninit(buf_.ptr, offset);
                        buf_.memfree();
                        buf_.header = newheader;
                        buf_.ptr    = newbuf;
                        data_       = newbuf;
                    } else  {
                        if (size > offset) {
                            // Shift beginning and end to make room
                            if (offset > 0) {
                                DataInit<T>::uninit(buf_.ptr, offset);
                                if (dest > 0)
                                    memmove(buf_.ptr, data_, sizeof(T)*dest);
                                data_ = buf_.ptr;
                            }
                            const Size tailsize = size_ - dest;
                            if (tailsize > 0)
                                memmove(data_+dest+size, data_+dest+offset, sizeof(T)*tailsize);
                            buf_.header->used = newused;
                        } else {
                            // Shift beginning to make room
                            const Size newoffset = offset - size;
                            data_ = buf_.ptr + newoffset;
                            DataInit<T>::uninit(buf_.ptr, offset-newoffset);
                            if (dest > 0)
                                memmove(data_, buf_.ptr+offset, sizeof(T)*dest);
                        }
                    }
                    size_ = newused;
                    goto movedata;
                }
            }

            // New buffer
            Header* newheader;
            T* newbuf = buf_.memalloc(newused, newheader);
            if (size_ > 0) {
                if (dest > 0)
                    DataInit<T>::init(newbuf, data_, dest);
                const Size nextindex = dest + size;
                if (nextindex < newheader->used)
                    DataInit<T>::init(newbuf+nextindex, data_+dest, newheader->used-nextindex);
            }
            data_ = buf_.replace(newbuf, newheader);
            size_ = buf_.header->used;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
            goto movedata;
        }
        return 0;

    movedata:
        if (src.buf_.ptr != NULL && src.buf_.header->refs == 1) {
            // Move from src buffer, is unique
            memcpy(data_+dest, src.data_+srcindex, sizeof(T)*size);
            src.modRemove(srcindex, size, false);
        } else {
            // Copy and remove from src
            meminit(data_+dest, src.data_+srcindex, size);
            src.modRemove(srcindex, size, true);
        }
        return size;
    }

    void swap(Key index1, Key index2) {
        if (index1 != index2 && index1 < size_ && index2 < size_) {
            unshare();
            advSwap(index1, index2);
        }
    }

    void swap(ListType& list)
        { EVO_IMPL_CONTAINER_SWAP(this, &list, ThisType); }

    // ALGS

    ListType& reverse() {
        if (size_ > 0) {
            unshare();
            char temp[sizeof(T)];
            T* left = data_;
            T* right = data_ + (size_ - 1);
            while (left < right) {
                memcpy(temp, left, sizeof(T));
                memcpy(left, right, sizeof(T));
                memcpy(right, temp, sizeof(T));
                ++left;
                --right;
            }
        }
        return *this;
    }

    // ADVANCED

    ListType& advResize(Size size) {
        // Copied from resize(), only difference is init() and init_tail_fast()
        if (size == 0) {
            clear();
            capacity(0);
        } else {
            if (buf_.header != NULL) {
                #if EVO_LIST_OPT_LAZYBUF
                    if (buf_.ptr == NULL) {
                        // Use previous buffer
                        assert( buf_.header->used == 0 );
                        assert( buf_.header->refs == 1 );
                        buf_.ptr = (T*)(buf_.header+1);
                        if (size > buf_.header->size)
                            // Grow previous buffer
                            buf_.memrealloc(size);
                        if (size <= size_) {
                            DataInit<T>::init(buf_.ptr, data_, size);
                        } else {
                            if (size_ > 0)
                                DataInit<T>::init(buf_.ptr, data_, size_);
                            DataInit<T>::init_tail_fast(buf_.ptr, size_, size);
                        }
                        data_ = buf_.ptr;
                        buf_.header->used = size_ = size;
                        return *this;
                    } else
                #else
                    // Lazy buffer disabled
                    assert( buf_.ptr != NULL );
                #endif
                if (buf_.header->refs == 1) {
                    // Existing buffer
                    if (buf_.header->used > 0)
                        unsliceBuffer(size < size_ ? size : size_);
                    if (size > buf_.header->size)
                        // Grow buffer
                        buf_.ptr = buf_.memrealloc(size);
                    if (buf_.header->used < size) {
                        // Add items
                        DataInit<T>::init_tail_fast(buf_.ptr, buf_.header->used, size);
                        buf_.header->used = size;
                    }
                    data_ = buf_.ptr;
                    size_ = size;
                    return *this;
                } else {
                    // New buffer, was shared
                    assert( buf_.header->refs > 1 );
                    --buf_.header->refs;
                }
            }

            // New buffer
            if (size_ > 0) {
                assert( data_ != NULL );
                buf_.ptr = (T*)buf_.memalloc(Capacity::init(size+1), size, buf_.header);
                DataInit<T>::init(buf_.ptr, size, data_, size_);
                data_ = buf_.ptr;
            } else {
                data_ = buf_.ptr = (T*)buf_.memalloc(Capacity::init(size+1), size, buf_.header);
                DataInit<T>::init(data_, size);
            }
            size_ = size;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        }
        return *this;
    }

    bool advEdit(Edit& edit, Size minsize, bool inplace=true) {
        assert( minsize > 0 );
        edit.clear();
        if (buf_.header != NULL) {
            #if EVO_LIST_OPT_LAZYBUF
                if (buf_.ptr == NULL) {
                    if (buf_.header->size < minsize) {
                        // Previous buffer not big enough, free it
                        buf_.memfree();
                        buf_.header = NULL;
                        goto newbuf;
                    } else {
                        // Previous buffer is big enough, detach and use as new buffer
                        assert( buf_.header->used == 0 );
                        assert( buf_.header->refs == 1 );
                        edit.ptr    = (T*)(buf_.header+1);
                        edit.header = (void*)buf_.header;
                        edit.size   = 0;
                        buf_.ptr    = NULL;
                        buf_.header = NULL;
                        return false;
                    }
                }
            #else
                // Lazy buffer disabled
                assert( buf_.ptr != NULL );
            #endif

            // If unique buffer is big enough and beginning isn't sliced, stop here to edit in-place
            if (inplace && buf_.header->refs == 1 && buf_.header->size >= minsize && data_ == buf_.ptr) {
                edit.ptr  = buf_.ptr;
                edit.size = size_;
                return true;
            }
        }

    newbuf:
        // Create new edit buffer
        edit.ptr  = (T*)buf_.memalloc(Capacity::init(minsize+1), minsize, (Header*&)edit.header);
        edit.size = 0;
        return false;
    }

    void advEditDone(Edit& edit) {
        assert( edit.ptr != NULL );
        if (edit.header == NULL) {
            // Update size after in-place editing
            assert( buf_.header != NULL );
            size_ = buf_.header->used = edit.size;
        } else {
            // Switch to new buffer
            if (buf_.header != NULL && --buf_.header->refs == 0)
                buf_.memfree();
            buf_.header = (Header*)edit.header;
            buf_.ptr    = edit.ptr;
            data_       = buf_.ptr;
            size_       = buf_.header->used = edit.size;
            assert( buf_.header->refs == 1 );
            edit.header = NULL;
        }
        edit.ptr  = NULL;
        edit.size = 0;
    }

    T* advBuffer(Size size) {
        advResize(size);
        return buf_.ptr;
    }

    T* advBuffer()
        { return buf_.ptr; }

    void advSize(Size size) {
        assert( buf_.header != NULL );
        size_ = buf_.header->used = size;
    }

    T* advWrite(Size addsize) {
        assert( addsize > 0 );
        unslice();
        reserve(addsize);
        return buf_.ptr + buf_.header->used;
    }

    void advWriteDone(Size addsize) {
        assert( buf_.header != NULL );
        size_ = buf_.header->used += addsize;
    }

    T& advItem(Key index) {
        assert( index < size_ );
        return data_[index];
    }

    T* advFirst()
        { return (size_ > 0 ? data_ : NULL); }

    T* advLast()
        { return (size_ > 0 ? data_+size_-1 : NULL); }

    void advAdd(Size size)
        { modAppend(NULL, size); }

    void advPrepend(Size size)
        { modPrepend(NULL, size); }

    Key advInsert(Key index, Size size)
        { return modInsert(index, NULL, size); }

    void advRemove(Key index, Size size)
        { modRemove(index, size, false); }

    void advSwap(Key index1, Key index2) {
        assert( index1 < size_ && index2 < size_ );
        char buf[sizeof(T)];
        memcpy(buf, data_+index1, sizeof(T));
        memcpy(data_+index1, data_+index2, sizeof(T));
        memcpy(data_+index2, buf, sizeof(T));
    }

    // INTERNAL

    // Internal methods
    Size used() const
        { return (buf_.ptr == NULL ? size_ : buf_.header->used); }
    // Testing methods
    #if EVO_UNIT_TEST_MODE
    bool utTerminated() const {
        #if EVO_LIST_OPT_REFTERM
            return terminated_;
        #else
            return false;
        #endif
    }
    Size utRefs() const
        { return (buf_.ptr == NULL ? 0 : buf_.header->refs); }
    const Item* utBuffer() const
        { return buf_.ptr; }
    void utSetEmptyBuffer(bool setempty, size_t size=1) {
        assert( size < IntegerT<Size>::MAX );
        resize((Size)size);
        DataInit<T>::uninit(buf_.ptr, (Size)size);
        buf_.header->used = 0;
        size_ = 0;
        if (setempty)
            data_ = EVO_PEMPTY;
    }
    void utSetUnusedBuffer(bool setempty, size_t size=1) {
        assert( size < IntegerT<Size>::MAX );
        resize((Size)size);
        DataInit<T>::uninit(buf_.ptr, (Size)size);
        buf_.header->used = 0;
        buf_.ptr = NULL;
        size_    = 0;
        if (setempty)
            data_ = EVO_PEMPTY;
    }
    void utSetBufPtr() {
        if (buf_.header != NULL)
            buf_.ptr = (T*)(buf_.header + 1);
    }
    #endif

    // Iterator support methods
    void iterInitMutable()
        { unshare(); }
    const IterItem* iterFirst(IterKey& key) const {
        const IterItem* result;
        if (size_ > 0) {
            key    = 0;
            result = data_;
        } else {
            key    = END;
            result = NULL;
        }
        return result;
    }
    const IterItem* iterNext(IterKey& key) const {
        const IterItem* result = NULL;
        if (key != END) {
            if (++key < size_)
                result = data_ + key;
            else
                key = END;
        }
        return result;
    }
    const IterItem* iterNext(Size count, IterKey& key) const {
        const Item* result = NULL;
        if (key != END) {
            if ( (key+=count) < size_ )
                result = data_ + key;
            else
                key = END;
        }
        return result;
    }
    const IterItem* iterLast(IterKey& key) const {
        const IterItem* result;
        if (size_ > 0) {
            key    = size_ - 1;
            result = data_ + key;
        } else {
            key    = END;
            result = NULL;
        }
        return result;
    }
    const IterItem* iterPrev(IterKey& key) const {
        const IterItem* result = NULL;
        if (key != END) {
            if (key > 0)
                result = data_ + --key;
            else
                key = END;
        }
        return result;
    }
    const IterItem* iterPrev(Size count, IterKey& key) const {
        const IterItem* result = NULL;
        if (key != END) {
            if (key > 0 && count <= key)
                result = data_ + (key-=count);
            else
                key = END;
        }
        return result;
    }
    Size iterCount() const
        { return size_; }
    const IterItem* iterSet(IterKey key) const {
        const IterItem* result = NULL;
        if (key < size_)
            result = data_ + key;
        return result;
    }
protected:
    struct Header {
        Size used;                  
        Size size;                  
        Size refs;                  
    };

    struct Buf {
        Header* header;             
        T*      ptr;                
        #if EVO_ALLOCATORS
            Allocator*  allocator;  
        #endif

        Buf() {
            header = NULL;
            ptr    = NULL;
        }

        ~Buf()
            { free(); }

        void clear() {
            header = NULL;
            ptr    = NULL;
        }

        T* memalloc(Size size, Size used, Header*& header) {
            assert( size > 0 );
            const Size bytes = sizeof(Header) + (size*sizeof(T));
            #if EVO_ALLOCATORS
                if (allocator == NULL)
                    header = (Header*)::malloc(bytes);
                else
                    header = (Header*)allocator->alloc(bytes);
            #else
                header = (Header*)::malloc(bytes);
            #endif
            assert( header != NULL );
            header->refs = 1;
            header->used = used;
            header->size = size;
            return (T*)(header + 1);
        }

        T* memalloc(Size size, Header*& header)
            { return memalloc(Capacity::init(size), size, header); }

        T* memrealloc(Size size) {
            assert( (size_t)this->header > sizeof(Header) );
            assert( this->ptr != NULL );
            assert( size > 0 );
            const Size bytes = sizeof(Header) + (size*sizeof(T));
            #if EVO_ALLOCATORS
                if (allocator == NULL)
                    this->header = (Header*)::realloc(this->header, bytes);
                else
                    this->header = (Header*)allocator->realloc(this->header, bytes);
            #else
                this->header = (Header*)::realloc(this->header, bytes);
            #endif
            assert( this->header != NULL );
            this->ptr = (T*)(this->header+1);
            this->header->size = size;
            return this->ptr;
        }

        void memfree() {
            assert( (size_t)header > sizeof(Header) );
            #if EVO_ALLOCATORS
                if (this->allocator == NULL)
                    ::free(header);
                else
                    this->allocator->free(header);
            #else
                ::free(header);
            #endif
        }

        void free() {
            if (header != NULL && --header->refs == 0) {
                if (header->used > 0)
                    DataInit<T>::uninit((T*)(header+1), header->used);
                memfree();
            }
        }

        T* replace(T* newptr, Header* newheader) {
            assert( newptr != NULL );
            assert( newheader != NULL );
            assert( newptr != ptr );
            free();
            header = newheader;
            ptr    = newptr;
            return ptr;
        }
    };

    Buf   buf_;                 
    #if EVO_LIST_OPT_REFTERM
    bool  terminated_;          
    #endif

    void ref(const ListType& data) {
        if (data.data_ == NULL) {
            set();
        } else if (data.size_ == 0) {
            setempty();
        #if EVO_ALLOCATORS
        } else if (buf_.allocator != NULL && data.buf_.ptr != NULL) {
            copy(data);
        #endif
        } else if (data.buf_.ptr == NULL) {
            // External reference
            if (buf_.ptr != NULL) {
                assert( buf_.header != NULL );
                if (buf_.header->refs > 1) {
                    // Detach from shared buffer
                    --buf_.header->refs;
                    buf_.header = NULL;
                    buf_.ptr    = NULL;
                } else {
                    // Leave buffer for later use
                    assert( buf_.header->refs == 1 );
                    if (buf_.header->used > 0)
                        DataInit<T>::uninit(buf_.ptr, buf_.header->used);
                    #if EVO_LIST_OPT_LAZYBUF
                        buf_.header->used = 0;
                    #else
                        // Lazy buffer disabled -- can't leave for later use
                        buf_.memfree();
                        buf_.header = NULL;
                    #endif
                    buf_.ptr = NULL;
                }
            }
            data_ = data.data_;
            size_ = data.size_;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = data.terminated_;
            #endif
        } else {
            // Shared
            assert( data.buf_.header != NULL );
            assert( data.buf_.ptr != NULL );
            buf_.free();
            buf_.header = data.buf_.header;
            buf_.ptr    = data.buf_.ptr;
            ++buf_.header->refs;
            data_ = data.data_;
            size_ = data.size_;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = data.terminated_;
            #endif
        }
    }

    void ref(const ListType& data, Size index, Size size) {
        if (data.data_ == NULL)
            set();
        else if (index >= data.size_)
            setempty();
        else {
            const Size max_size = (data.size_ - index);
            if (size > max_size)
                size = max_size;
            if (size == 0) {
                setempty();
            #if EVO_ALLOCATORS
            } else if (buf_.allocator != NULL && data.buf_.header != NULL) {
                copy(data.data_+index, size);
            #endif
            } else if (data.buf_.ptr == NULL) {
                // External reference
                if (buf_.ptr != NULL) {
                    assert( buf_.header != NULL );
                    if (buf_.header->refs > 1) {
                        // Detach from shared buffer
                        --buf_.header->refs;
                        buf_.header = NULL;
                        buf_.ptr    = NULL;
                    } else {
                        // Leave buffer for later use
                        assert( buf_.header->refs == 1 );
                        if (buf_.header->used > 0)
                            DataInit<T>::uninit(buf_.ptr, buf_.header->used);
                        #if EVO_LIST_OPT_LAZYBUF
                            buf_.header->used = 0;
                        #else
                            // Lazy buffer disabled -- can't leave for later use
                            buf_.memfree();
                            buf_.header = NULL;
                        #endif
                        buf_.ptr = NULL;
                    }
                }
                data_ = data.data_ + index;
                size_ = size;
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = (data.terminated_ && size == max_size);
                #endif
            } else {
                // Shared
                assert( data.buf_.header != NULL );
                buf_.free();
                buf_.header = data.buf_.header;
                buf_.ptr    = data.buf_.ptr;
                data_       = data.data_ + index;
                size_       = size;
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = data.terminated_;
                #endif
                ++buf_.header->refs;
            }
        }
    }

    void ref(const Item* data, Size size, bool term=false) {
        if (data == NULL)
            set();
        else if (size == 0)
            setempty();
        else {
            // External reference
            if (buf_.ptr != NULL) {
                assert( buf_.header != NULL );
                if (buf_.header->refs > 1) {
                    // Detach from shared buffer
                    --buf_.header->refs;
                    buf_.header = NULL;
                    buf_.ptr    = NULL;
                } else {
                    // Leave buffer for later use
                    assert( buf_.header->refs == 1 );
                    if (buf_.header->used > 0)
                        DataInit<T>::uninit(buf_.ptr, buf_.header->used);
                    #if EVO_LIST_OPT_LAZYBUF
                        buf_.header->used = 0;
                    #else
                        // Lazy buffer disabled -- can't leave for later use
                        buf_.memfree();
                        buf_.header = NULL;
                    #endif
                    buf_.ptr = NULL;
                }
            }
            data_ = (T*)data;
            size_ = size;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = term;
            #else
                EVO_PARAM_UNUSED(term);
            #endif
        }
    }

private:
    static const Size CONSERVE = (sizeof(T) == 1 ? 1 : 0);

    void unsliceBuffer(Size size) {
        assert( buf_.header != NULL && buf_.ptr >= (T*)(buf_.header+1) );
        assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
        const Size offset = (Size)(data_ - buf_.ptr);

        const Size tailsize = buf_.header->used - size - offset;
        if (tailsize > 0) {
            DataInit<T>::uninit(data_+size, tailsize);
            buf_.header->used -= tailsize;
        }

        if (offset > 0) {
            DataInit<T>::uninit(buf_.ptr, offset);
            if (size > 0)
                memmove((void*)buf_.ptr, (void*)(buf_.ptr+offset), size*sizeof(T));
            data_ = buf_.ptr;
            buf_.header->used -= offset;
        }
    }

    void modAppend(const Item* data, Size size) {
        if (size > 0) {
            const Size newused = size_ + size;
            if (buf_.header != NULL) {
                #if EVO_LIST_OPT_LAZYBUF
                    if (buf_.ptr == NULL) {
                        assert( buf_.header->refs == 1 );
                        if (buf_.header->size >= newused) {
                            // Use previous buffer
                            buf_.ptr = (T*)(buf_.header + 1);
                            if (size_ > 0)
                                DataInit<T>::init(buf_.ptr, data_, size_);
                            meminit(buf_.ptr+size_, data, size);
                            buf_.header->used = newused;
                            data_       = buf_.ptr;
                            size_       = newused;
                            #if EVO_LIST_OPT_REFTERM
                                terminated_ = false;
                            #endif
                            return;
                        }
                    } else
                #else
                    // Lazy buffer disabled
                    assert( buf_.ptr != NULL );
                #endif
                if (buf_.header->refs == 1) {
                    // Existing buffer
                    Size offset;
                    if (buf_.header->used > 0) {
                        assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                        offset = (Size)(data_ - buf_.ptr);

                        const Size tailsize = buf_.header->used - size_ - offset;
                        if (tailsize > 0) {
                            DataInit<T>::uninit(data_+size_, tailsize);
                            buf_.header->used -= tailsize;
                        }
                    } else
                        offset = 0;
                    if (newused > buf_.header->size) {
                        // Move to new bigger buffer
                        Size newbufsize = Capacity::grow(buf_.header->size);
                        if (newbufsize <= newused)
                            newbufsize = newused + 1; // Leave extra space
                        Header* newheader;
                        T* newbuf = buf_.memalloc(newbufsize, newused, newheader);
                        if (size_ > 0)
                            memcpy((void*)newbuf, (void*)data_, sizeof(T)*size_);
                        if (offset > 0)
                            DataInit<T>::uninit(buf_.ptr, offset);

                        // Write new items
                        meminit(newbuf+size_, data, size);
                        size_ = newused;

                        // Free old items, update state
                        buf_.memfree();
                        buf_.header = newheader;
                        buf_.ptr    = newbuf;
                        data_       = newbuf;
                    } else if (offset > 0 && size > buf_.header->size-buf_.header->used) {
                        // Shift to make room at end
                        DataInit<T>::uninit(buf_.ptr, offset);
                        memmove((void*)buf_.ptr, (void*)data_, sizeof(T)*size_);
                        if (data >= data_ && data < data_ + size_)
                            data -= (data_ - buf_.ptr); // Copy from self
                        buf_.header->used = newused;
                        data_             = buf_.ptr;

                        // Write new items
                        meminit(data_+size_, data, size);
                        size_ = newused;
                    } else {
                        // Enough room at end
                        if (data_ < buf_.ptr) {
                            assert( offset == 0 );
                            data_ = buf_.ptr;
                        }
                        buf_.header->used += size;

                        // Write new items
                        meminit(data_+size_, data, size);
                        size_ = newused;
                    }
                    return;
                }
            }

            // New buffer
            Header* newheader;
            T* newbuf = buf_.memalloc(Capacity::init(newused+1), newused, newheader);
            if (size_ > 0)
                DataInit<T>::init(newbuf, data_, size_);
            meminit(newbuf+size_, data, size);
            newheader->used = newused;
            data_ = buf_.replace(newbuf, newheader);
            size_ = newused;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        } else if (data_ == NULL)
            data_ = EVO_PEMPTY;
    }

    void modPrepend(const Item* data, Size size) {
        if (size > 0) {
            const Size newused = size_ + size;
            if (buf_.header != NULL) {
                #if EVO_LIST_OPT_LAZYBUF
                    if (buf_.ptr == NULL) {
                        if (buf_.header->size >= newused) {
                            // Use previous buffer
                            buf_.ptr = (T*)(buf_.header + 1);
                            if (size_ > 0)
                                DataInit<T>::init(buf_.ptr+size, data_, size_);
                            meminit(buf_.ptr, data, size);
                            buf_.header->used = newused;
                            data_ = buf_.ptr;
                            size_ = newused;
                            #if EVO_LIST_OPT_REFTERM
                                terminated_ = false;
                            #endif
                            return;
                        }
                    } else
                #else
                    // Lazy buffer disabled
                    assert( buf_.ptr != NULL );
                #endif
                if (buf_.header->refs == 1) {
                    // Existing buffer
                    Size offset;
                    if (buf_.header->used > 0) {
                        assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                        offset = (ulong)(data_ - buf_.ptr);

                        const Size tailsize = buf_.header->used - size_ - offset;
                        if (tailsize > 0) {
                            DataInit<T>::uninit(data_+size_, tailsize);
                            buf_.header->used -= tailsize;
                        }
                    } else
                        offset = 0;
                    if (newused > buf_.header->size) {
                        // Move to new bigger buffer
                        Size newbufsize = Capacity::grow(buf_.header->size);
                        if (newbufsize <= newused)
                            newbufsize = newused + 1; // Leave extra space
                        Header* newheader;
                        T* newbuf = buf_.memalloc(newbufsize, newused, newheader);
                        if (size_ > 0)
                            memcpy((void*)(newbuf+size), (void*)data_, sizeof(T)*size_);
                        if (offset > 0)
                            DataInit<T>::uninit(buf_.ptr, offset);

                        // Write new items
                        meminit(newbuf, data, size);

                        // Free old items, update state
                        buf_.memfree();
                        buf_.header = newheader;
                        buf_.ptr    = newbuf;
                        data_       = newbuf;
                    } else if (size > offset) {
                        // Shift to make room at beginning
                        if (offset > 0)
                            DataInit<T>::uninit(buf_.ptr, offset);
                        memmove((void*)(buf_.ptr+size), (void*)data_, sizeof(T)*size_);
                        if (data >= data_ && data < data_ + size_)
                            data += (buf_.ptr + size - data_); // Copy from self
                        buf_.header->used = newused;
                        data_             = buf_.ptr;

                        // Write new items
                        meminit(data_, data, size);
                    } else {
                        // Enough room at beginning
                        data_ = buf_.ptr + (offset - size);
                        DataInit<T>::uninit(data_, size);

                        // Write new items
                        meminit(data_, data, size);
                    }
                    size_ = newused;
                    return;
                }
            }

            // New buffer
            Header* newheader;
            T* newbuf = buf_.memalloc(newused, newheader);
            if (size_ > 0) {
                assert( data_ != NULL );
                DataInit<T>::init(newbuf+size, data_, size_);
            }
            meminit(newbuf, data, size);
            data_ = buf_.replace(newbuf, newheader);
            size_ = buf_.header->used;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
        } else if (data_ == NULL)
            data_ = EVO_PEMPTY;
    }

    Size modInsert(Size index, const Item* data, Size size) {
        if (index >= size_) {
            index = size_;
            modAppend(data, size);
        } else if (index == 0)
            modPrepend(data, size);
        else
            index = modInsertMid(index, data, size);
        return index;
    }

    Size modInsertMid(Size index, const Item* data, Size size) {
        assert( index > 0 && index < size_ );
        assert( size_ > 0 );
        if (size > 0) {
            if (buf_.header != NULL) {
                const Size newused = size_ + size;
                #if EVO_LIST_OPT_LAZYBUF
                    if (buf_.ptr == NULL) {
                        if (buf_.header->size >= newused) {
                            // Use previous buffer
                            buf_.ptr = (T*)(buf_.header + 1);
                            DataInit<T>::init(buf_.ptr, data_, index);
                            {
                                const Size nextindex = index + size;
                                assert( nextindex < newused );
                                DataInit<T>::init(buf_.ptr+nextindex, data_+index, newused-nextindex);
                            }
                            meminit(buf_.ptr+index, data, size);
                            buf_.header->used = newused;
                            data_ = buf_.ptr;
                            size_ = newused;
                            #if EVO_LIST_OPT_REFTERM
                                terminated_ = false;
                            #endif
                            return index;
                        }
                    } else
                #else
                    // Lazy buffer disabled
                    assert( buf_.ptr != NULL );
                #endif
                if (buf_.header->refs == 1) {
                    // Existing buffer -- not empty
                    assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                    Size offset = (Size)(data_ - buf_.ptr);
                    {
                        const Size tailsize = buf_.header->used - size_ - offset;
                        if (tailsize > 0) {
                            DataInit<T>::uninit(data_+size_, tailsize);
                            buf_.header->used -= tailsize;
                        }
                    }
                    if (newused > buf_.header->size) {
                        // Move to new bigger buffer
                        Size newbufsize = Capacity::grow(buf_.header->size);
                        if (newbufsize <= newused)
                            newbufsize = newused + 1; // Leave extra space
                        Header* newheader;
                        T* newbuf = buf_.memalloc(newbufsize, newused, newheader);
                        memcpy((void*)newbuf, (void*)data_, sizeof(T)*index);
                        memcpy((void*)(newbuf+index+size), (void*)(data_+index), sizeof(T)*(size_-index));
                        if (offset > 0)
                            DataInit<T>::uninit(buf_.ptr, offset);

                        // Write new items
                        meminit(newbuf+index, data, size);

                        // Free old items, update state
                        buf_.memfree();
                        buf_.header = newheader;
                        buf_.ptr    = newbuf;
                        data_       = newbuf;
                    } else if (size > offset) {
                        // Shift beginning and end to make room
                        if (offset > 0) {
                            DataInit<T>::uninit(buf_.ptr, offset);
                            memmove((void*)buf_.ptr, (void*)data_, sizeof(T)*index);
                            if (data >= data_ && data < data_ + index)
                                data -= offset; // Copy from self, adjust for shift
                            data_ = buf_.ptr;
                        }
                        T* ptr = data_ + index;
                        memmove((void*)(ptr+size), (void*)(ptr+offset), sizeof(T)*(size_-index));
                        buf_.header->used = newused;

                        // Write new items
                        if (data >= data_ && data < ptr) {
                            // Copy from self before insert point
                            Size sz = (Size)(ptr - data);
                            if (sz > size)
                                sz = size;
                            meminit(ptr, data, sz);
                            if (size > sz)
                                meminit(ptr+sz, ptr+size, size-sz);
                        } else {
                            if (data < (data_ + size_) && data >= data_)
                                data += (size - offset); // Copy from self after insert point, adjust for shift
                            meminit(data_+index, data, size);
                        }
                    } else {
                        // Shift beginning to make room
                        const Size newoffset = offset - size;
                        DataInit<T>::uninit(buf_.ptr, offset-newoffset);
                        if (data >= data_ && data < data_ + index) {
                            // Copy from self, which is splitting to make room
                            data_ = buf_.ptr + newoffset;
                            memmove((void*)data_, (void*)(buf_.ptr+offset), sizeof(T)*index);
                            data -= (offset - newoffset); // source moved, adjust pointer

                            // Write new items
                            if (size >= index) {
                                // Insert splits source, copy from both sides of split -- data after insert hasn't moved
                                T* ptr = data_ + index;
                                const Size sz = (Size)(ptr - data);
                                meminit(ptr, data, sz);
                                meminit(ptr+sz, ptr+size, size-sz);
                            } else
                                meminit(data_+index, data, size);
                        } else {
                            data_ = buf_.ptr + newoffset;
                            memmove((void*)data_, (void*)(buf_.ptr+offset), sizeof(T)*index);

                            // Write new items
                            meminit(data_+index, data, size);
                        }
                    }
                    size_ = newused;
                    return index;
                }
            }

            // New buffer
            Header* newheader;
            T* newbuf = buf_.memalloc(size_+size, newheader);
            {
                DataInit<T>::init(newbuf, data_, index);
                const Size nextindex = index + size;
                assert( nextindex < newheader->used );
                DataInit<T>::init(newbuf+nextindex, data_+index, newheader->used-nextindex);
            }
            meminit(newbuf+index, data, size);
            data_  = buf_.replace(newbuf, newheader);
            size_  = buf_.header->used;
            #if EVO_LIST_OPT_REFTERM
                terminated_ = false;
            #endif
            return index;
        }
        return NONE;
    }

    Size modRemove(Size index, Size size, bool uninit=true) {
        if (index < size_) {
            {
                const Size maxsize = size_ - index;
                if (size > maxsize)
                    size = maxsize;
            }
            if (size >= size_) {
                // Remove all -- mostly copied from clear()
                assert( size == size_ );
                assert( data_ > EVO_PEMPTY );
                if (buf_.ptr != NULL) {
                    assert( buf_.header != NULL );
                    if (buf_.header->refs > 1) {
                        // Detach from shared
                        --buf_.header->refs;
                        buf_.header = NULL;
                        buf_.ptr    = NULL;
                        data_       = EVO_PEMPTY;
                    } else if (buf_.header->used > 0) {
                        // Clear buffer, leave buffer for later use
                        assert( buf_.header->refs == 1 );
                        if (uninit) {
                            DataInit<T>::uninit(buf_.ptr, buf_.header->used);
                        } else {
                            // Uninitialize only previously removed items
                            assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                            const Size offset = (Size)(data_ - buf_.ptr);
                            if (offset > 0)
                                DataInit<T>::uninit(buf_.ptr, offset);

                            const Size tailsize = buf_.header->used - size_ - offset;
                            if (tailsize > 0) {
                                DataInit<T>::uninit(data_+size_, tailsize);
                                buf_.header->used -= tailsize;
                            }
                        }
                        buf_.header->used = 0;
                        data_             = buf_.ptr;
                    }
                } else {
                    data_ = EVO_PEMPTY;
                    #if !EVO_LIST_OPT_LAZYBUF
                        // Lazy buffer disabled
                        assert( buf_.header == NULL );
                    #endif
                }
                size_ = 0;
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = false;
                #endif
            } else if (size > 0) {
                // Remove some
                if (buf_.header != NULL) {
                    const Size newsize = size_ - size;
                    #if EVO_LIST_OPT_LAZYBUF
                        if (buf_.ptr == NULL) {
                            if (buf_.header->size >= newsize) {
                                // Use previous buffer
                                assert( buf_.header->used == 0 );
                                buf_.ptr = (T*)(buf_.header + 1);
                                if (index > 0)
                                    DataInit<T>::init(buf_.ptr, data_, index);
                                const Size nextindex = index + size;
                                if (nextindex < size_)
                                    DataInit<T>::init(buf_.ptr+index, data_+nextindex, size_-nextindex);
                                buf_.header->used = newsize;
                                data_  = buf_.ptr;
                                size_  = newsize;
                                #if EVO_LIST_OPT_REFTERM
                                    terminated_ = false;
                                #endif
                                return size;
                            }
                        } else
                    #else
                        // Lazy buffer disabled
                        assert( buf_.ptr != NULL );
                    #endif
                    if (buf_.header->refs == 1) {
                        // Existing buffer
                        assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                        const Size offset = (Size)(data_ - buf_.ptr);
                        {
                            const Size tailsize = buf_.header->used - size_ - offset;
                            if (tailsize > 0) {
                                DataInit<T>::uninit(data_+size_, tailsize);
                                buf_.header->used -= tailsize;
                            }
                        }

                        // Remove items
                        if (uninit)
                            DataInit<T>::uninit(data_+index, size);
                        const Size nextindex = index + size;
                        if (nextindex < size_)
                            memmove((void*)(data_+index), (void*)(data_+nextindex), sizeof(T)*(size_-nextindex));
                        buf_.header->used -= size;
                        size_              = newsize;
                        return size;
                    }
                }

                // New buffer
                assert( data_ != NULL );
                Header* newheader;
                const Size newused = size_ - size;
                T* newbuf = buf_.memalloc(newused+1, newused, newheader); // Leave extra space
                {
                    if (index > 0)
                        DataInit<T>::init(newbuf, data_, index);
                    const Size nextindex = index + size;
                    if (nextindex < size_)
                        DataInit<T>::init(newbuf+index, data_+nextindex, size_-nextindex);
                }
                data_ = buf_.replace(newbuf, newheader);
                size_ = buf_.header->used;
                #if EVO_LIST_OPT_REFTERM
                    terminated_ = false;
                #endif
            }
        } else
            size = 0;
        #if !EVO_LIST_OPT_LAZYBUF
            // Lazy buffer disabled
            assert( (buf_.header != NULL) == (buf_.ptr != NULL) );
        #endif
        return size;
    }

    void modReplace(Size index, Size size, const Item* data, Size newsize) {
        assert( size > 0 && newsize > 0 );
        assert( index < size_ );
        assert( data != NULL );
        const Size maxsize = size_ - index;
        if (size > maxsize)
            size = maxsize;
        if (buf_.header != NULL) {
            const Size newdatasize = size_ - size + newsize;
            #if EVO_LIST_OPT_LAZYBUF
                if (buf_.ptr == NULL) {
                    if (buf_.header->size >= newdatasize) {
                        // Use previous buffer
                        assert( buf_.header->used == 0 );
                        buf_.ptr = (T*)(buf_.header + 1);
                        if (index > 0)
                            DataInit<T>::init(buf_.ptr, data_, index);
                        DataInit<T>::init(buf_.ptr+index, data, newsize);

                        const Size nextindex = index + size;
                        if (nextindex < size_)
                            DataInit<T>::init(buf_.ptr+index+newsize, data_+nextindex, size_-nextindex);
                        buf_.header->used = newdatasize;
                        data_ = buf_.ptr;
                        size_ = newdatasize;
                        #if EVO_LIST_OPT_REFTERM
                            terminated_ = false;
                        #endif
                        return;
                    }
                } else
            #else
                // Lazy buffer disabled
                assert( buf_.ptr != NULL );
            #endif
            if (buf_.header->refs == 1) {
                // Existing buffer
                assert( data_ >= buf_.ptr && data_ <= buf_.ptr+buf_.header->used );
                {
                    // Replace existing items
                    const Size copysize = (size < newsize ? size : newsize);
                    assert( data < data_+index || data >= data_+index+copysize ); // Replacement source can't overlap with target to replace
                    DataInit<T>::copy(data_+index, data, copysize);
                    index     += copysize;
                    data      += copysize;
                    size      -= copysize;
                    newsize   -= copysize;
                }
                if (size > 0) {
                    // Remove extra items
                    T* dataptr = data_ + index;
                    DataInit<T>::uninit(dataptr, size);
                    const Size nextindex = index + size;
                    if (nextindex < size_)
                        memmove(dataptr, data_+nextindex, sizeof(T)*(size_-nextindex));
                    buf_.header->used -= size;
                    size_             -= size;
                } else if (newsize > 0) {
                    size = newsize;
                    const Size newused = size_ + size;

                    // Copied as-is from modInsertMid()
                    Size offset = (Size)(data_ - buf_.ptr);
                    {
                        const Size tailsize = buf_.header->used - size_ - offset;
                        if (tailsize > 0) {
                            DataInit<T>::uninit(data_+size_, tailsize);
                            buf_.header->used -= tailsize;
                        }
                    }
                    if (newused > buf_.header->size) {
                        // Move to new bigger buffer
                        Size newbufsize = Capacity::grow(buf_.header->size);
                        if (newbufsize <= newused)
                            newbufsize = newused + 1; // Leave extra space
                        Header* newheader;
                        T* newbuf = buf_.memalloc(newbufsize, newused, newheader);
                        memcpy((void*)newbuf, (void*)data_, sizeof(T)*index);
                        memcpy((void*)(newbuf+index+size), (void*)(data_+index), sizeof(T)*(size_-index));
                        if (offset > 0)
                            DataInit<T>::uninit(buf_.ptr, offset);

                        // Write new items
                        meminit(newbuf+index, data, size);

                        // Free old items, update state
                        buf_.memfree();
                        buf_.header = newheader;
                        buf_.ptr    = newbuf;
                        data_       = newbuf;
                    } else if (size > offset) {
                        // Shift beginning and end to make room
                        if (offset > 0) {
                            DataInit<T>::uninit(buf_.ptr, offset);
                            memmove((void*)buf_.ptr, (void*)data_, sizeof(T)*index);
                            if (data >= data_ && data < data_ + index)
                                data -= offset; // Copy from self, adjust for shift
                            data_ = buf_.ptr;
                        }
                        T* ptr = data_ + index;
                        memmove((void*)(ptr+size), (void*)(ptr+offset), sizeof(T)*(size_-index));
                        buf_.header->used = newused;

                        // Write new items
                        if (data >= data_ && data < ptr) {
                            // Copy from self before insert point
                            Size sz = (Size)(ptr - data);
                            if (sz > size)
                                sz = size;
                            meminit(ptr, data, sz);
                            if (size > sz)
                                meminit(ptr+sz, ptr+size, size-sz);
                        } else {
                            if (data < (data_ + size_) && data >= data_)
                                data += (size - offset); // Copy from self after insert point, adjust for shift
                            meminit(data_+index, data, size);
                        }
                    } else {
                        // Shift beginning to make room
                        const Size newoffset = (Size)(offset - size);
                        DataInit<T>::uninit(buf_.ptr, offset-newoffset);
                        if (data >= data_ && data < data_ + index) {
                            // Copy from self, which is splitting to make room
                            data_ = buf_.ptr + newoffset;
                            memmove((void*)data_, (void*)(buf_.ptr+offset), sizeof(T)*index);
                            data -= (offset - newoffset); // source moved, adjust pointer

                            // Write new items
                            if (size >= index) {
                                // Insert splits source, copy from both sides of split -- data after insert hasn't moved
                                T* ptr = data_ + index;
                                const Size sz = (Size)(ptr - data);
                                meminit(ptr, data, sz);
                                meminit(ptr+sz, ptr+size, size-sz);
                            } else
                                meminit(data_+index, data, size);
                        } else {
                            data_ = buf_.ptr + newoffset;
                            memmove((void*)data_, (void*)(buf_.ptr+offset), sizeof(T)*index);

                            // Write new items
                            meminit(data_+index, data, size);
                        }
                    }
                    size_ = newused;
                }
                return;
            }
        }
        
        // New buffer
        Header* newheader;
        T* newbuf = buf_.memalloc(size_-size+newsize, newheader);
        {
            if (index > 0)
                DataInit<T>::init(newbuf, data_, index);
            DataInit<T>::init(newbuf+index, data, newsize);
            const Size fromindex = index + size;
            if (fromindex < size_)
                DataInit<T>::init(newbuf+index+newsize, data_+fromindex, size_-fromindex);
        }
        data_ = buf_.replace(newbuf, newheader);
        size_ = buf_.header->used;
        #if EVO_LIST_OPT_REFTERM
            terminated_ = false;
        #endif
    }

    static void meminit(T* ptr, const Item* data, Size size) {
        if (data == EVO_PDEFAULT)
            DataInit<T>::init(ptr, size);
        else if (data != NULL)
            DataInit<T>::init(ptr, data, size);
    }
};


}
#if defined(_MSC_VER)
    #pragma warning(pop)
#endif
#endif