ItemContainerGenerator.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / wpf / src / Framework / System / Windows / Controls / ItemContainerGenerator.cs / 1 / ItemContainerGenerator.cs

                            //---------------------------------------------------------------------------- 
//
// 
//    Copyright (C) Microsoft Corporation.  All rights reserved.
//  
//
// Description: ItemContainerGenerator object 
// 
// Specs:       http://avalon/connecteddata/M5%20General%20Docs/Data%20Styling.mht
// 
//---------------------------------------------------------------------------

using System;
using System.Collections; 
using System.Collections.Generic;
using System.Collections.Specialized; 
using System.ComponentModel; 
using System.Globalization;     // for CultureInfo.InvariantCulture (event tracing)
 
using System.Windows.Media;
using System.Windows.Controls.Primitives;   // IItemContainerGenerator
using System.Windows.Data;
using System.Windows.Markup; 
using System.Diagnostics;
using MS.Internal; 
using MS.Internal.Controls; 
using MS.Internal.KnownBoxes;
using MS.Internal.Utility; 
using MS.Utility;


namespace System.Windows.Controls 
{
    ///  
    /// An ItemContainerGenerator is responsible for generating the UI on behalf of 
    /// its host (e.g. ItemsControl).  It maintains the association between the items in
    /// the control's data view and the corresponding 
    /// UIElements.  The control's item-host can ask the ItemContainerGenerator for
    /// a Generator, which does the actual generation of UI.
    /// 
    public sealed class ItemContainerGenerator : IRecyclingItemContainerGenerator, IWeakEventListener 
    {
        //----------------------------------------------------- 
        // 
        //  Constructors
        // 
        //-----------------------------------------------------

        ///  Constructor 
        ///  the control that owns the items  
        internal ItemContainerGenerator(IGeneratorHost host)
            : this(null, host, host as DependencyObject, 0) 
        { 
            // The top-level generator always listens to changes from ItemsCollection.
            // It needs to get these events before anyone else, so that other listeners 
            // can call the generator's mapping functions with correct results.
            CollectionChangedEventManager.AddListener(host.View, this);
        }
 
        private ItemContainerGenerator(ItemContainerGenerator parent, GroupItem groupItem)
            : this(parent, parent.Host, groupItem, parent.Level + 1) 
        { 
        }
 
        private ItemContainerGenerator(ItemContainerGenerator parent, IGeneratorHost host, DependencyObject peer, int level)
        {
            _parent = parent;
            _host = host; 
            _peer = peer;
            _level = level; 
            OnRefresh(); 
        }
 
        //------------------------------------------------------
        //
        //  Public Properties
        // 
        //-----------------------------------------------------
 
        ///  The status of the generator  
        public GeneratorStatus Status
        { 
            get { return _status; }
        }

        //[CodeAnalysis("AptcaMethodsShouldOnlyCallAptcaMethods")] //Tracking Bug: 29647 
        private void SetStatus(GeneratorStatus value)
        { 
            if (value != _status) 
            {
                _status = value; 

                switch (_status)
                {
                    case GeneratorStatus.GeneratingContainers: 
                        if (EventTrace.IsEnabled(EventTrace.Flags.performance, EventTrace.Level.normal))
                        { 
                            EventTrace.EventProvider.TraceEvent(EventTrace.GuidFromId(EventTraceGuidId.GENERICSTRINGGUID), MS.Utility.EventType.StartEvent, "ItemsControl.Generator"); 
                            _itemsGenerated = 0;
                        } 
                        else
                            _itemsGenerated = Int32.MinValue;
#if GENERATOR_TRACE
                        _creationTimer.Reset(); 
                        _timer.Begin();
#endif 
                        break; 

                    case GeneratorStatus.ContainersGenerated: 
                        string label = null;
                        if (_itemsGenerated >= 0)   // this implies that tracing is enabled
                        {
                            DependencyObject d = Host as DependencyObject; 
                            if (d != null)
                                label = (string)d.GetValue(FrameworkElement.NameProperty); 
                            if (label == null || label.Length == 0) 
                                label = Host.GetHashCode().ToString(CultureInfo.InvariantCulture);
                            EventTrace.EventProvider.TraceEvent(EventTrace.GuidFromId(EventTraceGuidId.GENERICSTRINGGUID), 
                                                                 MS.Utility.EventType.EndEvent,
                                                                 String.Format(CultureInfo.InvariantCulture, "ItemContainerGenerator for {0} {1} - {2} items", Host.GetType().Name, label, _itemsGenerated));
                        }
#if GENERATOR_TRACE 
                        _timer.End();
                        if (_itemsGenerated > 0) 
                        { 
                            Console.WriteLine("Generator for {0} {1}  did {2} items in {3:f2} msec - {4:f2} msec/item",
                                Host.GetType().Name, label, _itemsGenerated, _timer.TimeOfLastPeriod, _timer.TimeOfLastPeriod/_itemsGenerated); 
                            Console.WriteLine("  this excludes time for element creation: {0:f2} msec - {1:f2} msec/item",
                                _creationTimer.OverallTimeInMilliseconds, _creationTimer.OverallTimeInMilliseconds/_itemsGenerated);
                        }
#endif 
                        break;
                } 
 
                if (StatusChanged != null)
                    StatusChanged(this, EventArgs.Empty); 
            }
        }

 
        //------------------------------------------------------
        // 
        //  Public Methods 
        //
        //------------------------------------------------------ 

        #region IItemContainerGenerator

        ///  
        /// Return the ItemContainerGenerator appropriate for use by the given panel
        ///  
        ItemContainerGenerator IItemContainerGenerator.GetItemContainerGeneratorForPanel(Panel panel) 
        {
            if (!panel.IsItemsHost) 
                throw new ArgumentException(SR.Get(SRID.PanelIsNotItemsHost), "panel");

            // if panel came from an ItemsPresenter, use its generator
            ItemsPresenter ip = ItemsPresenter.FromPanel(panel); 
            if (ip != null)
                return ip.Generator; 
 
            // if panel came from a style, use the main generator
            if (panel.TemplatedParent != null) 
                return this;

            // otherwise the panel doesn't have a generator
            return null; 
        }
 
        ///  Begin generating at the given position and direction  
        /// 
        /// This method must be called before calling GenerateNext.  It returns an 
        /// IDisposable object that tracks the lifetime of the generation loop.
        /// This method sets the generator's status to GeneratingContent;  when
        /// the IDisposable is disposed, the status changes to ContentReady or
        /// Error, as appropriate. 
        /// 
        IDisposable IItemContainerGenerator.StartAt(GeneratorPosition position, GeneratorDirection direction) 
        { 
            return ((IItemContainerGenerator)this).StartAt(position, direction, false);
        } 

        ///  Begin generating at the given position and direction 
        /// 
        /// This method must be called before calling GenerateNext.  It returns an 
        /// IDisposable object that tracks the lifetime of the generation loop.
        /// This method sets the generator's status to GeneratingContent;  when 
        /// the IDisposable is disposed, the status changes to ContentReady or 
        /// Error, as appropriate.
        ///  
        IDisposable IItemContainerGenerator.StartAt(GeneratorPosition position, GeneratorDirection direction, bool allowStartAtRealizedItem)
        {
            if (_generator != null)
                throw new InvalidOperationException(SR.Get(SRID.GenerationInProgress)); 

            _generator = new Generator(this, position, direction, allowStartAtRealizedItem); 
            return _generator; 
        }
 
        DependencyObject IItemContainerGenerator.GenerateNext()
        {
            bool isNewlyRealized;
            if (_generator == null) 
                throw new InvalidOperationException(SR.Get(SRID.GenerationNotInProgress));
 
            return _generator.GenerateNext(true, out isNewlyRealized); 
        }
 
        DependencyObject IItemContainerGenerator.GenerateNext(out bool isNewlyRealized)
        {
            if (_generator == null)
                throw new InvalidOperationException(SR.Get(SRID.GenerationNotInProgress)); 

            return _generator.GenerateNext(false, out isNewlyRealized); 
        } 

        ///  
        /// Prepare the given element to act as the container for the
        /// corresponding item.  This includes applying the container style,
        /// forwarding information from the host control (ItemTemplate, etc.),
        /// and other small adjustments. 
        /// 
        ///  
        /// This method must be called after the element has been added to the 
        /// visual tree, so that resource references and inherited properties
        /// work correctly. 
        /// 
        ///  The container to prepare.
        /// Normally this is the result of the previous call to GenerateNext.
        ///  
        void IItemContainerGenerator.PrepareItemContainer(DependencyObject container)
        { 
            object item = container.ReadLocalValue(ItemForItemContainerProperty); 
            Host.PrepareItemContainer(container, item);
        } 

        /// 
        /// Remove generated elements.
        ///  
        void IItemContainerGenerator.Remove(GeneratorPosition position, int count)
        { 
            Remove(position, count, /*isRecycling = */ false); 
        }
 
        /// 
        /// Remove generated elements.
        /// 
        private void Remove(GeneratorPosition position, int count, bool isRecycling) 
        {
            if (position.Offset != 0) 
                throw new ArgumentException(SR.Get(SRID.RemoveRequiresOffsetZero, position.Index, position.Offset), "position"); 
            if (count <= 0)
                throw new ArgumentException(SR.Get(SRID.RemoveRequiresPositiveCount, count), "count"); 

            int index = position.Index;
            ItemBlock block;
 
            // find the leftmost item to remove
            int offsetL = index; 
            for (block = _itemMap.Next;  block != _itemMap;  block = block.Next) 
            {
                if (offsetL < block.ContainerCount) 
                    break;

                offsetL -= block.ContainerCount;
            } 
            RealizedItemBlock blockL = block as RealizedItemBlock;
 
            // find the rightmost item to remove 
            int offsetR = offsetL + count - 1;
            for (; block != _itemMap;  block = block.Next) 
            {
                if (!(block is RealizedItemBlock))
                    throw new InvalidOperationException(SR.Get(SRID.CannotRemoveUnrealizedItems, index, count));
 
                if (offsetR < block.ContainerCount)
                    break; 
 
                offsetR -= block.ContainerCount;
            } 
            RealizedItemBlock blockR = block as RealizedItemBlock;

            // de-initialize the containers that are being removed
            RealizedItemBlock rblock = blockL; 
            int offset = offsetL;
            while (rblock != blockR || offset <= offsetR) 
            { 
                DependencyObject container = rblock.ContainerAt(offset);
 
                UnlinkContainerFromItem(container, rblock.ItemAt(offset), isRecycling);

                if (isRecycling)
                { 
                    Debug.Assert(!_recyclableContainers.Contains(container), "trying to add a container to the collection twice");
 
                    if (_containerType == null) 
                    {
                        _containerType = container.GetType(); 
                    }
                    else if (_containerType != container.GetType())
                    {
                        throw new InvalidOperationException(SR.Get(SRID.CannotRecyleHeterogeneousTypes)); 
                    }
 
                    _recyclableContainers.Enqueue(container); 
                }
 
                if (++offset >= rblock.ContainerCount && rblock != blockR)
                {
                    rblock = rblock.Next as RealizedItemBlock;
                    offset = 0; 
                }
            } 
 
            // see whether the range hits the edge of a block on either side,
            // and whether the a`butting block is an unrealized gap 
            bool edgeL = (offsetL == 0);
            bool edgeR = (offsetR == blockR.ItemCount-1);
            bool abutL = edgeL && (blockL.Prev is UnrealizedItemBlock);
            bool abutR = edgeR && (blockR.Next is UnrealizedItemBlock); 

            // determine the target (unrealized) block, 
            // the offset within the target at which to insert items, 
            // and the intial change in cumulative item count
            UnrealizedItemBlock blockT; 
            ItemBlock predecessor = null;
            int offsetT;
            int deltaCount;
 
            if (abutL)
            { 
                blockT = (UnrealizedItemBlock)blockL.Prev; 
                offsetT = blockT.ItemCount;
                deltaCount = -blockT.ItemCount; 
            }
            else if (abutR)
            {
                blockT = (UnrealizedItemBlock)blockR.Next; 
                offsetT = 0;
                deltaCount = offsetL; 
            } 
            else
            { 
                blockT = new UnrealizedItemBlock();
                offsetT = 0;
                deltaCount = offsetL;
 
                // remember where the new block goes, so we can insert it later
                predecessor = (edgeL) ? blockL.Prev : blockL; 
            } 

            // move items within the range to the target block 
            for (block = blockL;  block != blockR;  block = block.Next)
            {
                int itemCount = block.ItemCount;
                MoveItems(block, offsetL, itemCount-offsetL, 
                            blockT, offsetT, deltaCount);
                offsetT += itemCount-offsetL; 
                offsetL = 0; 
                deltaCount -= itemCount;
                if (block.ItemCount == 0) 
                    block.Remove();
            }

            // the last block in the range is a little special... 
            // Move the last unrealized piece.
            int remaining = block.ItemCount - 1 - offsetR; 
            MoveItems(block, offsetL, offsetR - offsetL + 1, 
                        blockT, offsetT, deltaCount);
 
            // Move the remaining realized items
            RealizedItemBlock blockX = blockR;
            if (!edgeR)
            { 
                if (blockL == blockR && !edgeL)
                { 
                    blockX = new RealizedItemBlock(); 
                }
 
                MoveItems(block, offsetR+1, remaining,
                            blockX, 0, offsetR+1);
            }
 
            // if we created any new blocks, insert them in the list
            if (predecessor != null) 
                blockT.InsertAfter(predecessor); 
            if (blockX != blockR)
                blockX.InsertAfter(blockT); 

            RemoveAndCoalesceBlocksIfNeeded(block);

        } 

        ///  
        /// Remove all generated elements. 
        /// 
        void IItemContainerGenerator.RemoveAll() 
        {
            // Take _itemMap offline, to protect against reentrancy (bug 1285179)
            ItemBlock itemMap = _itemMap;
            _itemMap = null; 

            try 
            { 
                // de-initialize the containers that are being removed
                if (itemMap != null) 
                {
                    for (ItemBlock block = itemMap.Next;  block != itemMap;  block = block.Next)
                    {
                        RealizedItemBlock rib = block as RealizedItemBlock; 
                        if (rib != null)
                        { 
                            for (int offset = 0; offset < rib.ContainerCount; ++offset) 
                            {
                                UnlinkContainerFromItem(rib.ContainerAt(offset), rib.ItemAt(offset)); 
                            }
                        }
                    }
                } 
            }
            finally 
            { 
                PrepareGrouping();
 
                // re-initialize the data structure
                _itemMap = new ItemBlock();
                _itemMap.Prev = _itemMap.Next = _itemMap;
 
                UnrealizedItemBlock uib = new UnrealizedItemBlock();
                uib.InsertAfter(_itemMap); 
                uib.ItemCount = Items.Count; 

                _recyclableContainers = new Queue(); 

                SetAlternationCount();

                // tell generators what happened 
                if (MapChanged != null)
                { 
                    MapChanged(null, -1, 0, uib, 0, 0); 
                }
            } 

        }

        void IRecyclingItemContainerGenerator.Recycle(GeneratorPosition position, int count) 
        {
            Remove(position, count, /*isRecyling = */ true); 
        } 

        ///  
        /// Map an index into the items collection to a GeneratorPosition.
        /// 
        GeneratorPosition IItemContainerGenerator.GeneratorPositionFromIndex(int itemIndex)
        { 
            GeneratorPosition position;
            ItemBlock itemBlock; 
            int offsetFromBlockStart; 

            GetBlockAndPosition(itemIndex, out position, out itemBlock, out offsetFromBlockStart); 

            if (itemBlock == _itemMap && position.Index == -1)
                ++position.Offset;
 
            return position;
        } 
 
        /// 
        /// Map a GeneratorPosition to an index into the items collection. 
        /// 
        int IItemContainerGenerator.IndexFromGeneratorPosition(GeneratorPosition position)
        {
            int index = position.Index; 

            if (index == -1) 
            { 
                // offset is relative to the fictitious boundary item
                if (position.Offset >= 0) 
                {
                    return position.Offset - 1;
                }
                else 
                {
                    return Items.Count + position.Offset; 
                } 
            }
 
            if (_itemMap != null)
            {
                int itemIndex = 0;      // number of items we've skipped over
 
                // locate container at the given index
                for (ItemBlock block = _itemMap.Next;  block != _itemMap;  block = block.Next) 
                { 
                    if (index < block.ContainerCount)
                    { 
                        // container is within this block.  return the answer
                        return itemIndex + index + position.Offset;
                    }
                    else 
                    {
                        // skip over this block 
                        itemIndex += block.ItemCount; 
                        index -= block.ContainerCount;
                    } 
                }
            }

            return -1; 
        }
 
        #endregion IItemContainerGenerator 

        ///  
        /// Return the item corresponding to the given UI element.
        /// If the element was not generated as a container for this generator's
        /// host, the method returns DependencyProperty.UnsetValue.
        ///  
        public object ItemFromContainer(DependencyObject container)
        { 
            if (container == null) 
                throw new ArgumentNullException("container");
 
            object item = container.ReadLocalValue(ItemForItemContainerProperty);

            if (item != DependencyProperty.UnsetValue)
            { 
                // verify that the element really belongs to the host
                if (!Host.IsHostForItemContainer(container)) 
                    item = DependencyProperty.UnsetValue; 
            }
 
            return item;
        }

        ///  
        /// Return the UI element corresponding to the given item.
        /// Returns null if the item does not belong to the item collection, 
        /// or if no UI has been generated for it. 
        /// 
        public DependencyObject ContainerFromItem(object item) 
        {
            DependencyObject container = null;
            int index;
            DoLinearSearch(ref container, ref item, out index); 

            return container; 
        } 

        ///  
        /// Given a generated UI element, return the index of the corresponding item
        /// within the ItemCollection.
        /// 
        public int IndexFromContainer(DependencyObject container) 
        {
            if (container == null) 
            { 
                throw new ArgumentNullException("container");
            } 

            object item = null;
            int index;
            DoLinearSearch(ref container, ref item, out index); 

            return index; 
        } 

        ///  
        ///     Performs a linear search.
        /// 
        /// 
        ///     There's no avoiding a linear search, which leads to O(n^2) performance 
        ///     if someone calls ContainerFromItem or IndexFromContainer for every item.
        ///     To mitigate this, we start each search at _startIndexForUIFromItem, and 
        ///     heuristically set this in various places to where we expect the next 
        ///     call to occur.
        /// 
        ///     For example, after a successul search, we set it to the resulting
        ///     index, hoping that the next call will query either the same item or
        ///     the one after it.  And after inserting a new item, we expect a query
        ///     about the new item.  Etc. 
        ///
        ///     Saving this as an index instead of a (block, offset) pair, makes it 
        ///     more robust during insertions/deletions.  If the index ends up being 
        ///     wrong, the worst that happens is a full search (as opposed to following
        ///     a reference to a block that's no longer in use). 
        ///
        ///     To re-use the search code for two methods, please read the description
        ///     of the parameters.
        ///  
        /// 
        ///     If non-null, then searches for the container. 
        ///     Otherwise, updated with container for the item. 
        /// 
        ///  
        ///     If non-null, then searches for the item.
        ///     Otherwise, updated with the item that the container represents.
        /// 
        ///  
        ///     If a container or item is found, then updated with its index.
        ///     Otherwise, set to -1. 
        ///  
        /// 
        ///     true if found, false otherwise. 
        /// 
        private bool DoLinearSearch(ref DependencyObject container, ref object item, out int itemIndex)
        {
            itemIndex = 0; 

            if (_itemMap == null) 
            { 
                // _itemMap can be null if we re-enter the generator.  Scenario:  user calls RemoveAll(), we Unlink every container, fire
                // ClearContainerForItem for each, and someone overriding ClearContainerForItem decides to look up the container. 
                return false;
            }

            // Move to the starting point of the search 
            ItemBlock startBlock = _itemMap.Next;
            int index = 0;      // index of first item in current block 
            RealizedItemBlock rib; 
            int startOffset;
 
            while (index <= _startIndexForUIFromItem && startBlock != _itemMap)
            {
                index += startBlock.ItemCount;
                startBlock = startBlock.Next; 
            }
            startBlock = startBlock.Prev; 
            index -= startBlock.ItemCount; 
            rib = startBlock as RealizedItemBlock;
 
            if (rib != null)
            {
                startOffset = _startIndexForUIFromItem - index;
                if (startOffset >= rib.ItemCount) 
                {
                    // we can get here if items get removed since the last 
                    // time we saved _startIndexForUIFromItem - so the 
                    // saved offset is no longer meaningful.  To make the
                    // search work, we need to make sure the first loop 
                    // does at least one iteration.  Setting startOffset to 0
                    // does exactly that.
                    startOffset = 0;
                } 
            }
            else 
            { 
                startOffset = 0;
            } 

            // search for the desired item, wrapping around the end
            ItemBlock block = startBlock;
            int offset = startOffset; 
            int endOffset = startBlock.ItemCount;
            while (true) 
            { 
                // search the current block (only need to search realized blocks)
                if (rib != null) 
                {
                    for (; offset < endOffset; ++offset)
                    {
                        CollectionViewGroup group; 
                        bool found = false;
                        if (container != null) 
                        { 
                            if (rib.ContainerAt(offset) == container)
                            { 
                                found = true;
                                item = rib.ItemAt(offset);
                            }
                        } 
                        else
                        { 
                            if (Object.Equals(item, rib.ItemAt(offset))) 
                            {
                                found = true; 
                                container = rib.ContainerAt(offset);
                            }
                        }
 
                        if (IsGrouping && !found && ((group = rib.ItemAt(offset) as CollectionViewGroup) != null))
                        { 
                            // found a group;  see if the group contains the item 
                            GroupItem groupItem = (GroupItem)rib.ContainerAt(offset);
                            found = groupItem.Generator.DoLinearSearch(ref container, ref item, out itemIndex); 
                        }

                        if (found)
                        { 
                            // found the item;  update state and return
                            _startIndexForUIFromItem = index + offset; 
                            itemIndex += GetRealizedItemBlockCount(rib, offset) + GetCount(block); 
                            return true;
                        } 
                    }

                    // check for termination
                    if (block == startBlock && offset == startOffset) 
                    {
                        itemIndex = -1; 
                        return false; 
                    }
                } 

                // advance to next block
                index += block.ItemCount;
                offset = 0; 
                block = block.Next;
 
                // if we've reached the end, wrap around 
                if (block == _itemMap)
                { 
                    block = block.Next;
                    index = 0;
                }
 
                // prepare to search the block
                endOffset = block.ItemCount; 
                rib = block as RealizedItemBlock; 

                // check for termination 
                if (block == startBlock)
                {
                    if (rib != null)
                    { 
                        endOffset = startOffset;    // search first part of block
                    } 
                    else 
                    {
                        itemIndex = -1; 
                        return false;
                    }
                }
            } 
        }
 
        private int GetCount() 
        {
            return GetCount(_itemMap); 
        }

        private int GetCount(ItemBlock stop)
        { 
            int count = 0;
            ItemBlock start = _itemMap; 
            ItemBlock block = start.Next; 

            while (block != stop) 
            {
                RealizedItemBlock rib = block as RealizedItemBlock;
                if (rib != null)
                { 
                    // Search for groups within realized blocks
                    count += GetRealizedItemBlockCount(rib, rib.ItemCount); 
                } 
                else
                { 
                    count += block.ItemCount;
                }

                block = block.Next; 
            }
 
            return count; 
        }
 
        private int GetRealizedItemBlockCount(RealizedItemBlock rib, int end)
        {
            if (!IsGrouping)
            { 
                // when the UI is not grouping, each item counts as 1, even
                // groups (bug 1761421) 
                return end; 
            }
 
            int count = 0;

            for (int offset = 0; offset < end; ++offset)
            { 
                CollectionViewGroup group;
                if ((group = rib.ItemAt(offset) as CollectionViewGroup) != null) 
                { 
                    // found a group, count the group
                    GroupItem groupItem = (GroupItem)rib.ContainerAt(offset); 
                    count += groupItem.Generator.GetCount();
                }
                else
                { 
                    count++;
                } 
            } 

            return count; 
        }

        /// 
        /// Return the UI element corresponding to the item at the given index 
        /// within the ItemCollection.
        ///  
        public DependencyObject ContainerFromIndex(int index) 
        {
#if DEBUG 
            object target = (Parent == null) && (0 <= index  &&  index < Host.View.Count) ? Host.View[index] : null;
#endif
            int subIndex = 0;
 
            // if we're grouping, determine the appropriate child
            if (IsGrouping) 
            { 
                int n;
                subIndex = index; 
                for (index=0, n=Items.Count;  index < n;  ++index)
                {
                    CollectionViewGroup group = Items[index] as CollectionViewGroup;
                    int size = (group == null) ? 1 : group.ItemCount; 

                    if (subIndex < size) 
                        break; 
                    else
                        subIndex -= size; 
                }
            }

            // search the table for the item 

            for (ItemBlock block = _itemMap.Next; block != _itemMap; block = block.Next) 
            { 
                if (index < block.ItemCount)
                { 
                    DependencyObject container = block.ContainerAt(index);
                    GroupItem groupItem = container as GroupItem;

                    if (groupItem != null) 
                    {
                        container = groupItem.Generator.ContainerFromIndex(subIndex); 
                    } 
#if DEBUG
                    object item = (Parent == null) && (container != null) ? 
                                container.ReadLocalValue(ItemForItemContainerProperty) : null;
                    Debug.Assert(item == null || Object.Equals(item, target),
                        "Generator's data structure is corrupt - ContainerFromIndex found wrong item");
#endif 
                    return container;
                } 
 
                index -= block.ItemCount;
            } 

            return null;  // *not* throw new IndexOutOfRangeException(); - bug 890195
        }
 

        //----------------------------------------------------- 
        // 
        //  Public Events
        // 
        //------------------------------------------------------

        /// 
        /// The ItemsChanged event is raised by a ItemContainerGenerator to inform 
        /// layouts that the items collection has changed.
        ///  
        public event ItemsChangedEventHandler ItemsChanged; 

        ///  
        /// The StatusChanged event is raised by a ItemContainerGenerator to inform
        /// controls that its status has changed.
        /// 
        public event EventHandler StatusChanged; 

 
        //----------------------------------------------------- 
        //
        //  Internal methods 
        //
        //-----------------------------------------------------

        // regenerate everything 
        internal void Refresh()
        { 
            OnRefresh(); 
        }
 
        // called when this generator is no longer needed
        internal void Release()
        {
            ((IItemContainerGenerator)this).RemoveAll(); 
        }
 
        // called when the host's AlternationCount changes 
        internal void ChangeAlternationCount()
        { 
            // update my AlternationCount and adjust my containers
            SetAlternationCount();

            // propagate to subgroups, if necessary 
            if (IsGrouping && GroupStyle != null)
            { 
                ItemBlock block = _itemMap.Next; 
                while (block != _itemMap)
                { 
                    for (int offset = 0;  offset < block.ContainerCount;  ++offset)
                    {
                        GroupItem gi = ((RealizedItemBlock)block).ContainerAt(offset) as GroupItem;
                        if (gi != null) 
                        {
                            gi.Generator.ChangeAlternationCount(); 
                        } 
                    }
 
                    block = block.Next;
                }
            }
        } 

        // update AlternationIndex on each container to reflect the new AlternationCount 
        void ChangeAlternationCount(int newAlternationCount) 
        {
            if (_alternationCount == newAlternationCount) 
                return;

            // find the first realized container (need this regardless of what happens)
            ItemBlock block = _itemMap.Next; 
            int offset = 0;
            while (offset == block.ContainerCount) 
            { 
                block = block.Next;
            } 

            // if there are no realized containers, there's nothing to do
            if (block != _itemMap)
            { 
                // if user is requesting alternation, reset each container's AlternationIndex
                if (newAlternationCount > 0) 
                { 
                    _alternationCount = newAlternationCount;
                    SetAlternationIndex((RealizedItemBlock)block, offset, GeneratorDirection.Forward); 
                }
                // otherwise, clear each container's AlternationIndex
                else if (_alternationCount > 0)
                { 
                    while (block != _itemMap)
                    { 
                        for (offset = 0;  offset < block.ContainerCount;  ++offset) 
                        {
                            ItemsControl.ClearAlternationIndex(((RealizedItemBlock)block).ContainerAt(offset)); 
                        }

                        block = block.Next;
                    } 
                }
            } 
 
            _alternationCount = newAlternationCount;
        } 

        //-----------------------------------------------------
        //
        //  Internal properties 
        //
        //------------------------------------------------------ 
 
        internal ItemContainerGenerator Parent
        { 
            get { return _parent;}
        }

        internal int Level 
        {
            get { return _level;} 
        } 

        // The group style that governs the generation of UI for the items. 
        internal GroupStyle GroupStyle
        {
            get { return _groupStyle; }
            set 
            {
                if (_groupStyle != value) 
                { 
                    if (_groupStyle is INotifyPropertyChanged)
                    { 
                        PropertyChangedEventManager.RemoveListener(_groupStyle, this, String.Empty);
                    }

                    _groupStyle = value; 

                    if (_groupStyle is INotifyPropertyChanged) 
                    { 
                        PropertyChangedEventManager.AddListener(_groupStyle, this, String.Empty);
                    } 
                }
            }
        }
 
        // The collection of items, as IList
        internal IList Items 
        { 
            get { return _items; }
            set 
            {
                if (_items != value)
                {
                    INotifyCollectionChanged incc = _items as INotifyCollectionChanged; 
                    if (_items != Host.View && incc != null)
                    { 
                        CollectionChangedEventManager.RemoveListener(incc, this); 
                    }
 
                    _items = value;

                    incc = _items as INotifyCollectionChanged;
                    if (_items != Host.View && incc != null) 
                    {
                        CollectionChangedEventManager.AddListener(incc, this); 
                    } 
                }
            } 
        }

        /// 
        ///     ItemForItemContainer DependencyProperty 
        /// 
        // This is an attached property that the generator sets on each container 
        // (generated or direct) to point back to the item. 
        internal static readonly DependencyProperty ItemForItemContainerProperty =
                DependencyProperty.RegisterAttached("ItemForItemContainer", typeof(object), typeof(ItemContainerGenerator), 
                                            new FrameworkPropertyMetadata((object)null));

        //-----------------------------------------------------
        // 
        //  Internal events
        // 
        //------------------------------------------------------ 

        internal event EventHandler PanelChanged; 

        internal void OnPanelChanged()
        {
            if (PanelChanged != null) 
                PanelChanged(this, EventArgs.Empty);
        } 
 
        //------------------------------------------------------
        // 
        //  Private Nested Class -  ItemContainerGenerator.Generator
        //
        //-----------------------------------------------------
 

        ///  
        ///     Generator is the object that generates UI on behalf of an ItemsControl, 
        ///     working under the supervision of an ItemContainerGenerator.
        ///  
        private class Generator : IDisposable
        {
            //------------------------------------------------------
            // 
            //  Constructors
            // 
            //----------------------------------------------------- 

            internal Generator(ItemContainerGenerator factory, GeneratorPosition position, GeneratorDirection direction, bool allowStartAtRealizedItem) 
            {
                _factory = factory;
                _direction = direction;
 
                _factory.MapChanged += new MapChangedHandler(OnMapChanged);
 
                _factory.MoveToPosition(position, direction, allowStartAtRealizedItem, ref _cachedState); 
                _done = (_factory.Items.Count == 0);
 
                _factory.SetStatus(GeneratorStatus.GeneratingContainers);
            }

            //----------------------------------------------------- 
            //
            //  Public Properties 
            // 
            //-----------------------------------------------------
 
/* This method was requested for virtualization.  It's not being used right now
(bug 1079525) but it probably will be when UI virtualization comes back.
            /// 
            /// returns false if a call to GenerateNext is known to return null (indicating 
            /// that the generator is done).  Does not generate anything or change the
            /// generator's state;  cheaper than GenerateNext.  Returning true does not 
            /// necessarily mean GenerateNext will produce anything. 
            /// 
            public bool IsActive 
            {
                get { return !_done; }
            }
*/ 

            //------------------------------------------------------ 
            // 
            //  Public Methods
            // 
            //-----------------------------------------------------

            ///  Generate UI for the next item or group
            public DependencyObject GenerateNext(bool stopAtRealized, out bool isNewlyRealized) 
            {
                DependencyObject container = null; 
                isNewlyRealized = false; 

                while (container == null) 
                {
                    UnrealizedItemBlock uBlock = _cachedState.Block as UnrealizedItemBlock;
                    IList items = _factory.Items;
                    int itemIndex = _cachedState.ItemIndex; 
                    int incr = (_direction == GeneratorDirection.Forward) ? +1 : -1;
 
                    if (_cachedState.Block == _factory._itemMap) 
                        _done = true;            // we've reached the end of the list
 
                    if (uBlock == null && stopAtRealized)
                        _done = true;

                    if (!(0 <= itemIndex && itemIndex < items.Count)) 
                        _done = true;
 
                    if (_done) 
                    {
                        isNewlyRealized = false; 
                        return null;
                    }

                    object item = items[itemIndex]; 

                    if (uBlock != null) 
                    { 
                        // We don't have a realized container for this item.  Try to use a recycled container
                        // if possible, otherwise generate a new container. 

                        isNewlyRealized = true;

                        CollectionViewGroup group = item as CollectionViewGroup; 
                        if (group == null || !_factory.IsGrouping)
                        { 
 
                            if (_factory._recyclableContainers.Count > 0 && !_factory.Host.IsItemItsOwnContainer(item))
                            { 
                                container = _factory._recyclableContainers.Dequeue();
                                isNewlyRealized = false;
                            }
                            else 
                            {
                                // generate container for an item 
                                container = _factory.Host.GetContainerForItem(item); 
                            }
 
                            ItemContainerGenerator.LinkContainerToItem(container, item, /* isRecycled = */ !isNewlyRealized);
                        }
                        else
                        { 
                            // generate container for a group
                            container = _factory.ContainerForGroup(group); 
                        } 

                        // add the (item, container) to the current block 
                        if (container != null)
                        {
                            _factory.Realize(uBlock, _cachedState.Offset, item, container);
 
                            // set AlternationIndex on the container (and possibly others)
                            _factory.SetAlternationIndex(_cachedState.Block, _cachedState.Offset, _direction); 
                        } 
                    }
                    else 
                    {
                        // return existing realized container
                        isNewlyRealized = false;
                        RealizedItemBlock rib = (RealizedItemBlock)_cachedState.Block; 
                        container = rib.ContainerAt(_cachedState.Offset);
                    } 
 
                    // advance to the next item
                    _cachedState.ItemIndex = itemIndex; 
                    if (_direction == GeneratorDirection.Forward)
                    {
                        _cachedState.Block.MoveForward(ref _cachedState, true);
                    } 
                    else
                    { 
                        _cachedState.Block.MoveBackward(ref _cachedState, true); 
                    }
                } 

                return container;
            }
 
            //------------------------------------------------------
            // 
            //  Interfaces - IDisposable 
            //
            //------------------------------------------------------ 

            ///  Dispose this generator. 
            void IDisposable.Dispose()
            { 
                if (_factory != null)
                { 
                    _factory.MapChanged -= new MapChangedHandler(OnMapChanged); 
                    _done = true;
                    _factory.SetStatus(GeneratorStatus.ContainersGenerated); 
                    _factory._generator = null;
                    _factory = null;
                }
            } 

            //----------------------------------------------------- 
            // 
            //  Private methods
            // 
            //------------------------------------------------------

            // The map data structure has changed, so the state must change accordingly.
            // This is called in various different ways. 
            //  A. Items were moved within the data structure, typically because
            //  items were realized or un-realized.  In this case, the args are: 
            //      block - the block from where the items were moved 
            //      offset - the offset within the block of the first item moved
            //      count - how many items moved 
            //      newBlock - the block to which the items were moved
            //      newOffset - the offset within the new block of the first item moved
            //      deltaCount - the difference between the cumululative item counts
            //                  of newBlock and block 
            //  B. An item was added or removed from the data structure.  In this
            //  case the args are: 
            //      block - null  (to distinguish case B from case A) 
            //      offset - the index of the changed item, w.r.t. the entire item list
            //      count - +1 for insertion, -1 for deletion 
            //      others - unused
            //  C. Refresh: all items are returned to a single unrealized block.
            //  In this case, the args are:
            //      block - null 
            //      offset - -1 (to distinguish case C from case B)
            //      newBlock = the single unrealized block 
            //      others - unused 
            void OnMapChanged(ItemBlock block, int offset, int count,
                            ItemBlock newBlock, int newOffset, int deltaCount) 
            {
                // Case A.  Items were moved within the map data structure
                if (block != null)
                { 
                    // if the move affects this generator, update the cached state
                    if (block == _cachedState.Block && offset <= _cachedState.Offset && 
                        _cachedState.Offset < offset + count) 
                    {
                        _cachedState.Block = newBlock; 
                        _cachedState.Offset += newOffset - offset;
                        _cachedState.Count += deltaCount;
                    }
                } 
                // Case B.  An item was inserted or deleted
                else if (offset >= 0) 
                { 
                    // if the item occurs before my block, update my item count
                    if (offset < _cachedState.Count) 
                    {
                        _cachedState.Count += count;
                        _cachedState.ItemIndex += count;
                    } 
                    // if the item occurs within my block before my item, update my offset
                    else if (offset < _cachedState.Count + _cachedState.Offset) 
                    { 
                        _cachedState.Offset += count;
                        _cachedState.ItemIndex += count; 
                    }
                    // if an insert occurs at my position, update my offset
                    else if (offset == _cachedState.Count + _cachedState.Offset &&
                        count > 0) 
                    {
                        _cachedState.Offset += count; 
                        _cachedState.ItemIndex += count; 
                    }
                } 
                // Case C.  Refresh
                else
                {
                    _cachedState.Block = newBlock; 
                    _cachedState.Offset += _cachedState.Count;
                    _cachedState.Count = 0; 
                } 
            }
 
            //-----------------------------------------------------
            //
            //  Private Fields
            // 
            //-----------------------------------------------------
 
            ItemContainerGenerator     _factory; 
            GeneratorDirection  _direction;
            bool                _done; 
            GeneratorState      _cachedState;
        }

 
        //-----------------------------------------------------
        // 
        //  Private Properties 
        //
        //------------------------------------------------------ 

        IGeneratorHost Host { get { return _host; } }

        // The DO for which this generator was created.  For normal generators, 
        // this is the ItemsControl.  For subgroup generators, this is
        // the GroupItem. 
        DependencyObject Peer 
        {
            get { return _peer; } 
        }

        bool IsGrouping
        { 
            get { return (Items != Host.View); }
        } 
 

        //----------------------------------------------------- 
        //
        //  Private Methods
        //
        //------------------------------------------------------ 

        void MoveToPosition(GeneratorPosition position, GeneratorDirection direction, bool allowStartAtRealizedItem, ref GeneratorState state) 
        { 
            ItemBlock block = _itemMap;
            int itemIndex = 0; 

            // first move to the indexed (realized) item
            if (position.Index != -1)
            { 
                // find the right block
                int itemCount = 0; 
                int index = position.Index; 
                block = block.Next;
                while (index >= block.ContainerCount) 
                {
                    itemCount += block.ItemCount;
                    index -= block.ContainerCount;
                    itemIndex += block.ItemCount; 
                    block = block.Next;
                } 
 
                // set the position
                state.Block = block; 
                state.Offset = index;
                state.Count = itemCount;
                state.ItemIndex = itemIndex + index;
            } 
            else
            { 
                state.Block = block; 
                state.Offset = 0;
                state.Count = 0; 
                state.ItemIndex = itemIndex - 1;
            }

            // adjust the offset - we always set the state so it points to the next 
            // item to be generated.
            int offset = position.Offset; 
            if (offset == 0 && (!allowStartAtRealizedItem || state.Block == _itemMap)) 
            {
                offset = (direction == GeneratorDirection.Forward) ? 1 : -1; 
            }

            // advance the state according to the offset
            if (offset > 0) 
            {
                state.Block.MoveForward(ref state, true); 
                while (--offset > 0) 
                {
                    state.Block.MoveForward(ref state, allowStartAtRealizedItem); 
                }
            }
            else if (offset < 0)
            { 
                if (state.Block == _itemMap)
                { 
                    state.ItemIndex = state.Count = Items.Count; 
                }
                state.Block.MoveBackward(ref state, true); 
                while (++offset < 0)
                {
                    state.Block.MoveBackward(ref state, allowStartAtRealizedItem);
                } 
            }
        } 
 
        // "Realize" the item in a block at the given offset, to be
        // the given item with corresponding container.  This means updating 
        // the item map data structure so that the item belongs to a Realized block.
        // It also requires updating the state of every generator to track the
        // changes we make here.
        void Realize(UnrealizedItemBlock block, int offset, object item, DependencyObject container) 
        {
            RealizedItemBlock prevR, nextR; 
 
            RealizedItemBlock newBlock; // new location of the target item
            int newOffset;              // its offset within the new block 
            int deltaCount;             // diff between cumulative item count of block and newBlock

            // if we're realizing the leftmost item and there's room in the
            // previous block, move it there 
            if (offset == 0 &&
                (prevR = block.Prev as RealizedItemBlock) != null && 
                prevR.ItemCount < ItemBlock.BlockSize) 
            {
                newBlock = prevR; 
                newOffset = prevR.ItemCount;
                MoveItems(block, offset, 1, newBlock, newOffset, -prevR.ItemCount);
                MoveItems(block, 1, block.ItemCount, block, 0, +1);
            } 

            // if we're realizing the rightmost item and there's room in the 
            // next block, move it there 
            else if (offset == block.ItemCount - 1 &&
                (nextR = block.Next as RealizedItemBlock) != null && 
                nextR.ItemCount < ItemBlock.BlockSize)
            {
                newBlock = nextR;
                newOffset = 0; 
                MoveItems(newBlock, 0, newBlock.ItemCount, newBlock, 1, -1);
                MoveItems(block, offset, 1, newBlock, newOffset, offset); 
            } 

            // otherwise we need a new block for the target item 
            else
            {
                newBlock = new RealizedItemBlock();
                newOffset = 0; 
                deltaCount = offset;
 
                // if target is leftmost item, insert it before remaining items 
                if (offset == 0)
                { 
                    newBlock.InsertBefore(block);
                    MoveItems(block, offset, 1, newBlock, newOffset, 0);
                    MoveItems(block, 1, block.ItemCount, block, 0, +1);
                } 

                // if target is rightmost item, insert it after remaining items 
                else if (offset == block.ItemCount - 1) 
                {
                    newBlock.InsertAfter(block); 
                    MoveItems(block, offset, 1, newBlock, newOffset, offset);
                }

                // otherwise split the block into two, with the target in the middle 
                else
                { 
                    UnrealizedItemBlock newUBlock = new UnrealizedItemBlock(); 
                    newUBlock.InsertAfter(block);
                    newBlock.InsertAfter(block); 
                    MoveItems(block, offset+1, block.ItemCount-offset-1, newUBlock, 0, offset+1);
                    MoveItems(block, offset, 1, newBlock, 0, offset);
                }
            } 

            RemoveAndCoalesceBlocksIfNeeded(block); 
 
            // add the new target to the map
            newBlock.RealizeItem(newOffset, item, container); 
        }

        void RemoveAndCoalesceBlocksIfNeeded(ItemBlock block)
        { 
            if (block != null && block != _itemMap && block.ItemCount == 0)
            { 
                block.Remove(); 

                // coalesce adjacent unrealized blocks 
                if (block.Prev is UnrealizedItemBlock && block.Next is UnrealizedItemBlock)
                {
                    MoveItems(block.Next, 0, block.Next.ItemCount, block.Prev, block.Prev.ItemCount, -block.Prev.ItemCount-1);
                    block.Next.Remove(); 
                }
            } 
        } 

        // Move 'count' items starting at position 'offset' in block 'block' 
        // to position 'newOffset' in block 'newBlock'.  The difference between
        // the cumulative item counts of newBlock and block is given by 'deltaCount'.
        void MoveItems(ItemBlock block, int offset, int count,
                        ItemBlock newBlock, int newOffset, int deltaCount) 
        {
            RealizedItemBlock ribSrc = block as RealizedItemBlock; 
            RealizedItemBlock ribDst = newBlock as RealizedItemBlock; 

            // when both blocks are Realized, entries must be physically copied 
            if (ribSrc != null && ribDst != null)
            {
                ribDst.CopyEntries(ribSrc, offset, count, newOffset);
            } 
            // when the source block is Realized, clear the vacated entries -
            // to avoid leaks.  (No need if it's now empty - the block will get GC'd). 
            else if (ribSrc != null && ribSrc.ItemCount > count) 
            {
                ribSrc.ClearEntries(offset, count); 
            }

            // update block information
            block.ItemCount -= count; 
            newBlock.ItemCount += count;
 
            // tell generators what happened 
            if (MapChanged != null)
                MapChanged(block, offset, count, newBlock, newOffset, deltaCount); 
        }

        // Set the AlternationIndex on a newly-realized container.  Also, reset
        // the AlternationIndex on other containers to maintain the adjacency 
        // criterion.
        void SetAlternationIndex(ItemBlock block, int offset, GeneratorDirection direction) 
        { 
            // If user doesn't request alternation, don't do anything
            if (_alternationCount <= 0) 
                return;

            int index;
            RealizedItemBlock rib; 

            // Proceed in the direction of generation.  This tends to reach the 
            // end sooner (often in one step). 
            if (direction != GeneratorDirection.Backward)
            { 
                // Forward.  Back up one container to determine the starting index
                -- offset;
                while (offset < 0 || block is UnrealizedItemBlock)
                { 
                    block = block.Prev;
                    offset = block.ContainerCount - 1; 
                } 

                rib = block as RealizedItemBlock; 
                index = (block == _itemMap) ? -1 : ItemsControl.GetAlternationIndex(rib.ContainerAt(offset));

                // loop through the remaining containers, resetting each AlternationIndex
                for (;;) 
                {
                    // advance to next realized container 
                    ++offset; 
                    while (offset == block.ContainerCount)
                    { 
                        block = block.Next;
                        offset = 0;
                    }
 
                    // exit if we've reached the end
                    if (block == _itemMap) 
                        break; 

                    // advance the AlternationIndex 
                    index = (index + 1) % _alternationCount;

                    // assign it to the container
                    rib = block as RealizedItemBlock; 
                    ItemsControl.SetAlternationIndex(rib.ContainerAt(offset), index);
                } 
            } 
            else
            { 
                // Backward.  Advance one container to determine the starting index
                ++ offset;
                while (offset >= block.ContainerCount || block is UnrealizedItemBlock)
                { 
                    block = block.Next;
                    offset = 0; 
                } 

                rib = block as RealizedItemBlock; 
                index = (block == _itemMap) ? _alternationCount : ItemsControl.GetAlternationIndex(rib.ContainerAt(offset));

                // loop through the remaining containers, resetting each AlternationIndex
                for (;;) 
                {
                    // retreat to next realized container 
                    --offset; 
                    while (offset == 0)
                    { 
                        block = block.Prev;
                        offset = block.ContainerCount;
                    }
 
                    // exit if we've reached the end
                    if (block == _itemMap) 
                        break; 

                    // retreat the AlternationIndex 
                    index = (index - 1) % _alternationCount;

                    // assign it to the container
                    rib = block as RealizedItemBlock; 
                    ItemsControl.SetAlternationIndex(rib.ContainerAt(offset), index);
                } 
            } 
        }
 
        // create a group item for the given group
        DependencyObject ContainerForGroup(CollectionViewGroup group)
        {
            if (!ShouldHide(group)) 
            {
                // normal group - link a new GroupItem 
                GroupItem groupItem = new GroupItem(); 

                LinkContainerToItem(groupItem, group); 

                // create the generator
                groupItem.Generator = new ItemContainerGenerator(this, groupItem);
 
                return groupItem;
            } 
            else 
            {
                // hidden empty group - link a new EmptyGroupItem 
                AddEmptyGroupItem(group);

                // but don't return it to layout
                return null; 
            }
        } 
 
        // prepare the grouping information.  Called from RemoveAll.
        void PrepareGrouping() 
        {
            GroupStyle groupStyle;
            IList items;
 
            if (Level == 0)
            { 
                groupStyle = Host.GetGroupStyle(null, 0); 

                if (groupStyle == null) 
                {
                    items = Host.View;
                }
                else 
                {
                    CollectionView cv = Host.View.CollectionView; 
                    items = (cv == null) ? null : cv.Groups; 
                    if (items == null)
                    { 
                        items = Host.View;
                    }
                }
            } 
            else
            { 
                GroupItem groupItem = (GroupItem)Peer; 
                CollectionViewGroup group = groupItem.ReadLocalValue(ItemForItemContainerProperty) as CollectionViewGroup;
 
                if (group != null)
                {
                    if (group.IsBottomLevel)
                    { 
                        groupStyle = null;
                    } 
                    else 
                    {
                        groupStyle = Host.GetGroupStyle(group, Level); 
                    }

                    items = group.Items;
                } 
                else
                { 
                    groupStyle = null; 
                    items = Host.View;
                } 
            }

            GroupStyle = groupStyle;
            Items = items; 

            if ((Level == 0) && (Host != null)) 
            { 
                // Notify the host of a change in IsGrouping
                Host.SetIsGrouping(IsGrouping); 
            }
        }

        void SetAlternationCount() 
        {
            int alternationCount; 
 
            if (IsGrouping && GroupStyle != null)
            { 
                if (GroupStyle.IsAlternationCountSet)
                {
                    alternationCount = GroupStyle.AlternationCount;
                } 
                else if (_parent != null)
                { 
                    alternationCount = _parent._alternationCount; 
                }
                else 
                {
                    alternationCount = Host.AlternationCount;
                }
            } 
            else
            { 
                alternationCount = Host.AlternationCount; 
            }
 
            ChangeAlternationCount(alternationCount);
        }

        // should the given group be hidden? 
        bool ShouldHide(CollectionViewGroup group)
        { 
            return  GroupStyle.HidesIfEmpty &&      // user asked to hide 
                    group.ItemCount == 0;           // group is empty
        } 

        // create an empty-group placeholder item
        void AddEmptyGroupItem(CollectionViewGroup group)
        { 
            EmptyGroupItem emptyGroupItem = new EmptyGroupItem();
 
            LinkContainerToItem(emptyGroupItem, group); 

            emptyGroupItem.SetGenerator(new ItemContainerGenerator(this, emptyGroupItem)); 

            // add it to the list of placeholder items (this keeps it from being GC'd)
            if (_emptyGroupItems == null)
                _emptyGroupItems = new ArrayList(); 
            _emptyGroupItems.Add(emptyGroupItem);
        } 
 
        // notification that a subgroup has become non-empty
        void OnSubgroupBecameNonEmpty(EmptyGroupItem groupItem, CollectionViewGroup group) 
        {
            // Discard placeholder container.
            UnlinkContainerFromItem(groupItem, group);
            if (_emptyGroupItems != null) 
                _emptyGroupItems.Remove(groupItem);
 
            // inform layout as if the group just got added 
            if (ItemsChanged != null)
            { 
                GeneratorPosition position = PositionFromIndex(Items.IndexOf(group));
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Add, position, 1, 0));
            }
        } 

        // notification that a subgroup has become empty 
        void OnSubgroupBecameEmpty(CollectionViewGroup group) 
        {
            if (ShouldHide(group)) 
            {
                GeneratorPosition position = PositionFromIndex(Items.IndexOf(group));

                // if the group is realized, un-realize it and notify layout 
                if (position.Offset == 0 && position.Index >= 0)
                { 
                    // un-realize 
                    ((IItemContainerGenerator)this).Remove(position, 1);
 
                    // inform layout as if the group just got removed
                    if (ItemsChanged != null)
                    {
                        ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Remove, position, 1, 1)); 
                    }
 
                    // create the placeholder 
                    AddEmptyGroupItem(group);
                } 
            }
        }

        // convert an index (into Items) into a GeneratorPosition 
        GeneratorPosition PositionFromIndex(int itemIndex)
        { 
            GeneratorPosition position; 
            ItemBlock itemBlock;
            int offsetFromBlockStart; 

            GetBlockAndPosition(itemIndex, out position, out itemBlock, out offsetFromBlockStart);

            return position; 
        }
 
 
        void GetBlockAndPosition(object item, int itemIndex, bool deletedFromItems, out GeneratorPosition position, out ItemBlock block, out int offsetFromBlockStart, out int correctIndex)
        { 
            if (itemIndex >= 0)
            {
                GetBlockAndPosition(itemIndex, out position, out block, out offsetFromBlockStart);
                correctIndex = itemIndex; 
            }
            else 
            { 
                GetBlockAndPosition(item, deletedFromItems, out position, out block, out offsetFromBlockStart, out correctIndex);
            } 
        }


        void GetBlockAndPosition(int itemIndex, out GeneratorPosition position, out ItemBlock block, out int offsetFromBlockStart) 
        {
            position = new GeneratorPosition(-1, 0); 
            block = null; 
            offsetFromBlockStart = itemIndex;
 
            if (_itemMap == null || itemIndex < 0)
                return;

            int containerIndex = 0; 

            for (block = _itemMap.Next;  block != _itemMap;  block = block.Next) 
            { 
                if (offsetFromBlockStart >= block.ItemCount)
                { 
                    // item belongs to a later block, increment the containerIndex
                    containerIndex += block.ContainerCount;
                    offsetFromBlockStart -= block.ItemCount;
                } 
                else
                { 
                    // item belongs to this block.  Determine the container index and offset 
                    if (block.ContainerCount > 0)
                    { 
                        // block has realized items
                        position = new GeneratorPosition(containerIndex + offsetFromBlockStart, 0);
                    }
                    else 
                    {
                        // block has unrealized items 
                        position = new GeneratorPosition(containerIndex-1, offsetFromBlockStart+1); 
                    }
 
                    break;
                }
            }
        } 

        void GetBlockAndPosition(object item, bool deletedFromItems, out GeneratorPosition position, out ItemBlock block, out int offsetFromBlockStart, out int correctIndex) 
        { 
            correctIndex = 0;
            int containerIndex = 0; 
            offsetFromBlockStart = 0;
            int deletionOffset = deletedFromItems ? 1 : 0;
            position = new GeneratorPosition(-1, 0);
 
            for (block = _itemMap.Next;  block != _itemMap;  block = block.Next)
            { 
                UnrealizedItemBlock uib; 
                RealizedItemBlock rib = block as RealizedItemBlock;
 
                if (rib != null)
                {
                    // compare realized items with item for which we are searching
                    offsetFromBlockStart = rib.OffsetOfItem(item); 
                    if (offsetFromBlockStart >= 0)
                    { 
                        position = new GeneratorPosition(containerIndex + offsetFromBlockStart, 0); 
                        correctIndex += offsetFromBlockStart;
                        break; 
                    }
                }
                else if ((uib = block as UnrealizedItemBlock) != null)
                { 
                    // if the item isn't realized, we can't find it
                    // directly.  Instead, look for indirect evidence that it 
                    // belongs to this block by checking the indices of 
                    // nearby realized items.
 
#if DEBUG
                    // Sanity check - make sure data structure is OK so far.
                    rib = block.Prev as RealizedItemBlock;
                    if (rib != null && rib.ContainerCount > 0) 
                    {
                        Debug.Assert(Object.Equals(rib.ItemAt(rib.ContainerCount - 1), 
                                                    Items[correctIndex - 1]), 
                                    "Generator data structure is corrupt");
                    } 
#endif

                    bool itemIsInCurrentBlock = false;
                    rib = block.Next as RealizedItemBlock; 
                    if (rib != null && rib.ContainerCount > 0)
                    { 
                        // if the index of the next realized item is off by one, 
                        // the deleted item likely comes from the current
                        // unrealized block. 
                        itemIsInCurrentBlock =
                                Object.Equals(rib.ItemAt(0),
                                    Items[correctIndex + block.ItemCount - deletionOffset]);
                    } 
                    else if (block.Next == _itemMap)
                    { 
                        // similarly if we're at the end of the list and the 
                        // overall count is off by one, or if the current block
                        // is the only block, the deleted item likely 
                        // comes from the current (last) unrealized block
                        itemIsInCurrentBlock = block.Prev == _itemMap ||
                            (Items.Count == correctIndex + block.ItemCount - deletionOffset);
                    } 

                    if (itemIsInCurrentBlock) 
                    { 
                        // we don't know where it is in this block, so assume
                        // it's the very first item. 
                        offsetFromBlockStart = 0;
                        position = new GeneratorPosition(containerIndex-1, 1);
                        break;
                    } 
                }
 
                correctIndex += block.ItemCount; 
                containerIndex += block.ContainerCount;
            } 

            if (block == _itemMap)
            {
                // There's no way of knowing which unrealized block it belonged to, so 
                // the data structure can't be updated correctly.  Sound the alarm.
                throw new InvalidOperationException(SR.Get(SRID.CannotFindRemovedItem)); 
            } 
        }
 

        private void LinkContainerToItem(DependencyObject container, object item)
        {
            LinkContainerToItem(container, item, false); 
        }
 
        // establish the link from the container to the corresponding item 
        static void LinkContainerToItem(DependencyObject container, object item, bool isRecycled)
        { 
            // always set the ItemForItemContainer property
            container.ClearValue(ItemForItemContainerProperty);
            container.SetValue(ItemForItemContainerProperty, item);
 
            // for non-direct items, set the DataContext property
            if (container != item) 
            { 
                if (!isRecycled)
                { 
                    // We already cleared recycled containers in UnlinkContainerFromItem
                    container.ClearValue(FrameworkElement.DataContextProperty);
                }
                container.SetValue(FrameworkElement.DataContextProperty, item); 
            }
        } 
 
        private void UnlinkContainerFromItem(DependencyObject container, object item)
        { 
            UnlinkContainerFromItem(container, item, false);
        }

        // unlink the container from the corresponding item 
        private void UnlinkContainerFromItem(DependencyObject container, object item, bool isRecycled)
        { 
            container.ClearValue(ItemForItemContainerProperty); 

            // There are two ways to view the properties set by PrepareItemContainer: 
            //
            //  a) these properties are added by the generator/host so that
            //      the container can function correctly in the generated tree.
            // 
            //  b) these properties are part of the container's initial state,
            //      independent of whether the container belongs to the tree. 
            // 
            // If you take the first point of view, then the generator should remove
            // these properties when the container is removed from the tree.  If 
            // you take the second point of view, then the generator should not do this.
            //
            // In response to bug 1445288 and independent discussions, we take the
            // second point of view.  This saves the cost of clearing all those 
            // properties, which can add up to quite a lot.  As long as no one expects
            // to use a container after it has been removed, there should be no harm. 
            // 
            // We make a small exception for the ItemForItemContainer property, since
            // that is an internal property that only makes sense for an active container. 
            //
            // When we're in Recycling mode, the above doesn't apply; we need to clear off
            // the DataContext property on the container since it will get re-used.  The
            // issue here is that if we don't clear it off we can alias DataContexts;  we 
            // could get a container on the recycled list with the same DataContext as a
            // live container -- that causes all sorts of subtle issues. 
            // 

            if (isRecycled && container != item) 
            {
                // ClearValue has a perf problem because the DataContext will be inherited by the recycled container's
                // parent.  That will cause us to resolve a binding that we really don't care about.  This can be insanely expensive
                // depending on the structure of the data. 
                //
                // In the rare case that the DataContext property has an expression on it we have to do ClearValue to get rid of it 
                // so that the SetValue later in LinkContainerToItem will work. 

                DependencyProperty dp = FrameworkElement.DataContextProperty; 
                EntryIndex entryIndex = container.LookupEntry(dp.GlobalIndex);

                if (container.HasExpression(entryIndex, dp))
                { 
                    container.ClearValue(dp);
                } 
                else 
                {
                    container.SetValue(dp, null); 
                }
            }

            _host.ClearContainerForItem(container, item); 
        }
 
        ///  
        /// Handle events from the centralized event table
        ///  
        bool IWeakEventListener.ReceiveWeakEvent(Type managerType, object sender, EventArgs e)
        {
            if (managerType == typeof(PropertyChangedEventManager))
            { 
                PropertyChangedEventArgs pce = (PropertyChangedEventArgs)e;
                if (sender == GroupStyle) 
                { 
                    if (pce.PropertyName == "Panel")
                    { 
                        OnPanelChanged();
                    }
                    else
                    { 
                        OnRefresh();
                    } 
                } 
            }
            else if (managerType == typeof(CollectionChangedEventManager)) 
            {
                OnCollectionChanged(sender, (NotifyCollectionChangedEventArgs)e);
            }
            else 
            {
                return false;       // unrecognized event 
            } 

            return true; 
        }

        void ValidateAndCorrectIndex(object item, ref int index)
        { 
            if (index >= 0)
            { 
                // this check is expensive - Items[index] potentially iterates through 
                // the collection.  So trust the sender to tell us the truth in retail bits.
                Debug.Assert(Object.Equals(item, Items[index]), "Event contains the wrong index"); 
            }
            else
            {
                index = Items.IndexOf(item); 
                if (index < 0)
                    throw new InvalidOperationException(SR.Get(SRID.CollectionAddEventMissingItem, item)); 
            } 
        }
 
        /// 
        /// Forward a CollectionChanged event
        /// 
        // Called  when items collection changes. 
        void OnCollectionChanged(object sender, NotifyCollectionChangedEventArgs args)
        { 
            // get the affected item 
            object item;
            int startingIndex = -1; 
            switch (args.Action)
            {
                case NotifyCollectionChangedAction.Add:
                case NotifyCollectionChangedAction.Remove: 
                    if (sender != Items)
                        return;     // ignore events from ItemsCollection when we're listening to group's items. 
 

                    if (args.Action == NotifyCollectionChangedAction.Add) 
                    {
                        if (args.NewItems.Count != 1)
                            throw new NotSupportedException(SR.Get(SRID.RangeActionsNotSupported));
                        item = args.NewItems[0]; 
                        startingIndex = args.NewStartingIndex;
                    } 
                    else 
                    {
                        if (args.OldItems.Count != 1) 
                            throw new NotSupportedException(SR.Get(SRID.RangeActionsNotSupported));
                        item = args.OldItems[0];
                        startingIndex = args.OldStartingIndex;
                    } 
                    break;
 
                case NotifyCollectionChangedAction.Replace: 
                case NotifyCollectionChangedAction.Move:
                case NotifyCollectionChangedAction.Reset: 
                    item = null;
                    break;

                default: 
                    throw new NotSupportedException(SR.Get(SRID.UnexpectedCollectionChangeAction, args.Action));
            } 
 
            if (_traceLog != null)
                _traceLog.Add("Received collection change from {0}  action = {1}  item={2}", 
                            TraceLog.IdFor(sender), args.Action, item);

            switch (args.Action)
            { 
                case NotifyCollectionChangedAction.Add:
                    OnItemAdded(item, startingIndex); 
                    break; 

                case NotifyCollectionChangedAction.Remove: 
                    OnItemRemoved(item, startingIndex);
                    break;

                case NotifyCollectionChangedAction.Replace: 
                    OnItemReplaced(args.OldItems[0], args.NewItems[0], args.NewStartingIndex);
                    break; 
                case NotifyCollectionChangedAction.Move: 
                    OnItemMoved(args.OldItems[0], args.OldStartingIndex, args.NewStartingIndex);
                    break; 


                case NotifyCollectionChangedAction.Reset:
                    OnRefresh(); 
                    break;
            } 
        } 

        // Called when an item is added to the items collection 
        void OnItemAdded(object item, int index)
        {
            ValidateAndCorrectIndex(item, ref index);
 
            GeneratorPosition position = new GeneratorPosition(-1,0);
 
            // find the block containing the new item 
            ItemBlock block = _itemMap.Next;
            int offset = index; 
            while (block != _itemMap && offset >= block.ItemCount)
            {
                offset -= block.ItemCount;
                position.Index += block.ContainerCount; 
                block = block.Next;
            } 
 
            position.Offset = offset + 1;
 
            // if it's an unrealized block, add the item by bumping the count
            UnrealizedItemBlock uib = block as UnrealizedItemBlock;
            if (uib != null)
            { 
                MoveItems(uib, offset, 1, uib, offset+1, 0);
                ++ uib.ItemCount; 
            } 

            // if the item can be added to a previous unrealized block, do so 
            else if ((offset == 0 || block == _itemMap) &&
                    ((uib = block.Prev as UnrealizedItemBlock) != null))
            {
                ++ uib.ItemCount; 
            }
 
            // otherwise, create a new unrealized block 
            else
            { 
                uib = new UnrealizedItemBlock();
                uib.ItemCount = 1;

                // split the current realized block, if necessary 
                RealizedItemBlock rib;
                if (offset > 0 && (rib = block as RealizedItemBlock) != null) 
                { 
                    RealizedItemBlock newBlock = new RealizedItemBlock();
                    MoveItems(rib, offset, rib.ItemCount - offset, newBlock, 0, offset); 
                    newBlock.InsertAfter(rib);
                    position.Index += block.ContainerCount;
                    position.Offset = 1;
                    block = newBlock; 
                }
 
                uib.InsertBefore(block); 
            }
 
            if (_traceLog != null)
                _traceLog.Add("OnItemAdded {0} index = {1}", TraceLog.IdFor(item), index);

            // tell generators what happened 
            if (MapChanged != null)
            { 
                MapChanged(null, index, +1, null, 0, 0); 
            }
 
            // tell layout what happened
            if (ItemsChanged != null)
            {
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Add, position, 1, 0)); 
            }
        } 
 

        // Called when an item is removed from the items collection 
        void OnItemRemoved(object item, int itemIndex)
        {

            DependencyObject container = null;    // the corresponding container 
            int containerCount = 0;
 
            // search for the deleted item 
            GeneratorPosition position;
            ItemBlock block; 
            int offsetFromBlockStart;
            int correctIndex;
            GetBlockAndPosition(item, itemIndex, true, out position, out block, out offsetFromBlockStart, out correctIndex);
 
            RealizedItemBlock rib = block as RealizedItemBlock;
            if (rib != null) 
            { 
                containerCount = 1;
                container = rib.ContainerAt(offsetFromBlockStart); 
            }

            // remove the item, and remove the block if it's now empty
            MoveItems(block, offsetFromBlockStart + 1, block.ItemCount - offsetFromBlockStart - 1, block, offsetFromBlockStart, 0); 
            --block.ItemCount;
            if (rib != null) 
            { 
                // fix up the alternation index before removing an empty block, while
                // we still have a valid block and offset 
                SetAlternationIndex(block, offsetFromBlockStart, GeneratorDirection.Forward);
            }
            RemoveAndCoalesceBlocksIfNeeded(block);
 
            if (_traceLog != null)
                _traceLog.Add("OnItemRemoved {0} index = {1}", TraceLog.IdFor(item), itemIndex); 
 
            // tell generators what happened
            if (MapChanged != null) 
            {
                MapChanged(null, itemIndex, -1, null, 0, 0);
            }
 
            // tell layout what happened
            if (ItemsChanged != null) 
            { 
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Remove, position, 1, containerCount));
            } 

            // unhook the container.  Do this after layout has (presumably) removed it from
            // the UI, so that it doesn't inherit DataContext falsely.
            if (container != null) 
            {
                UnlinkContainerFromItem(container, item); 
            } 

            // detect empty groups, so they can be hidden if necessary 
            if (Level > 0 && Items.Count == 0)
            {
                GroupItem groupItem = (GroupItem)Peer;
                CollectionViewGroup group = groupItem.ReadLocalValue(ItemForItemContainerProperty) as CollectionViewGroup; 

                // the group could be null if the parent generator has already 
                // unhooked its container 
                if (group != null)
                { 
                    Parent.OnSubgroupBecameEmpty(group);
                }
            }
        } 

        void OnItemReplaced(object oldItem, object newItem, int index) 
        { 
            // search for the replaced item
            GeneratorPosition position; 
            ItemBlock block;
            int offsetFromBlockStart;
            int correctIndex;
            GetBlockAndPosition(oldItem, index, false, out position, out block, out offsetFromBlockStart, out correctIndex); 

            // If the item is in an UnrealizedItemBlock, then this change need not 
            // be made to the _itemsMap as we are replacing an unrealized item with another unrealized 
            // item in the same place.
            RealizedItemBlock rib = block as RealizedItemBlock; 
            if (rib != null)
            {
                DependencyObject container = rib.ContainerAt(offsetFromBlockStart);
 
                // replace the old item with the new one
                rib.RealizeItem(offsetFromBlockStart, newItem, container); 
 
                // hook up the container to the new item
                LinkContainerToItem(container, newItem); 
                _host.PrepareItemContainer(container, newItem);
            }

            if (_traceLog != null) 
                _traceLog.Add("OnItemReplaced {0} index = {1}", TraceLog.IdFor(oldItem), index);
        } 
 
        void OnItemMoved(object item, int oldIndex, int newIndex)
        { 
            DependencyObject container = null;    // the corresponding container
            int containerCount = 0;
            UnrealizedItemBlock uib;
 
            // search for the moved item
            GeneratorPosition position; 
            ItemBlock block; 
            int offsetFromBlockStart;
            int correctIndex; 
            GetBlockAndPosition(item, oldIndex, true, out position, out block, out offsetFromBlockStart, out correctIndex);

            GeneratorPosition oldPosition = position;
 
            RealizedItemBlock rib = block as RealizedItemBlock;
            if (rib != null) 
            { 
                containerCount = 1;
                container = rib.ContainerAt(offsetFromBlockStart); 
            }

            // remove the item, and remove the block if it's now empty
            MoveItems(block, offsetFromBlockStart + 1, block.ItemCount - offsetFromBlockStart - 1, block, offsetFromBlockStart, 0); 
            --block.ItemCount;
            RemoveAndCoalesceBlocksIfNeeded(block); 
 
            //
            // now insert into the new spot. 
            //

            position = new GeneratorPosition(-1,0);
            block = _itemMap.Next; 
            offsetFromBlockStart = newIndex;
            while (block != _itemMap && offsetFromBlockStart >= block.ItemCount) 
            { 
                offsetFromBlockStart -= block.ItemCount;
                if (block.ContainerCount > 0) 
                {
                    position.Index += block.ContainerCount;
                    position.Offset = 0;
                } 
                else
                { 
                    position.Offset += block.ItemCount; 
                }
                block = block.Next; 
            }

            position.Offset += offsetFromBlockStart + 1;
 
            // if it's an unrealized block, add the item by bumping the count
            uib = block as UnrealizedItemBlock; 
            if (uib != null) 
            {
                MoveItems(uib, offsetFromBlockStart, 1, uib, offsetFromBlockStart+1, 0); 
                ++ uib.ItemCount;
            }

            // if the item can be added to a previous unrealized block, do so 
            else if ((offsetFromBlockStart == 0 || block == _itemMap) &&
                    ((uib = block.Prev as UnrealizedItemBlock) != null)) 
            { 
                ++ uib.ItemCount;
            } 

            // otherwise, create a new unrealized block
            else
            { 
                uib = new UnrealizedItemBlock();
                uib.ItemCount = 1; 
 
                // split the current realized block, if necessary
                if (offsetFromBlockStart > 0 && (rib = block as RealizedItemBlock) != null) 
                {
                    RealizedItemBlock newBlock = new RealizedItemBlock();
                    MoveItems(rib, offsetFromBlockStart, rib.ItemCount - offsetFromBlockStart, newBlock, 0, offsetFromBlockStart);
                    newBlock.InsertAfter(rib); 
                    position.Index += block.ContainerCount;
                    position.Offset = 1; 
                    offsetFromBlockStart = 0; 
                    block = newBlock;
                } 

                uib.InsertBefore(block);
            }
 
            if (_traceLog != null)
                _traceLog.Add("OnItemMoved {0} oldIndex = {1}", TraceLog.IdFor(item), oldIndex); 
 
            DependencyObject parent = VisualTreeHelper.GetParentInternal(container);
 
            // tell layout what happened
            if (ItemsChanged != null)
            {
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Move, position, oldPosition, 1, containerCount)); 
            }
 
            // unhook the container.  Do this after layout has (presumably) removed it from 
            // the UI, so that it doesn't inherit DataContext falsely.
            if (container != null) 
            {
                if (parent == null || VisualTreeHelper.GetParentInternal(container) != parent)
                {
                    UnlinkContainerFromItem(container, item); 
                }
                else 
                { 
                    // If the container has the same visual parent as before then that means that
                    // the container was just repositioned within the parent's VisualCollection. 
                    // we don't need to unlink the container, but we do need to re-realize the block.
                    Realize(uib, offsetFromBlockStart, item, container);
                }
            } 

            // fix up the AlternationIndex on containers affected by the move 
            if (_alternationCount > 0) 
            {
                // start with the smaller of the two positions, and proceed forward. 
                // This tends to preserve the AlternatonIndex on containers at the
                // front of the list, as users expect
                int index = Math.Min(oldIndex, newIndex);
                GetBlockAndPosition(index, out position, out block, out offsetFromBlockStart); 
                SetAlternationIndex(block, offsetFromBlockStart, GeneratorDirection.Forward);
            } 
        } 

        // Called when the items collection is refreshed 
        void OnRefresh()
        {
            ((IItemContainerGenerator)this).RemoveAll();
 
            if (_traceLog != null)
                _traceLog.Add("OnRefresh count = {0}", Items.Count); 
 
            // tell layout what happened
            if (ItemsChanged != null) 
            {
                GeneratorPosition position = new GeneratorPosition(0, 0);
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Reset, position, 0, 0));
            } 
        }
 
        // this method is here just to avoid the compiler error 
        // error CS0649: Warning as Error: Field '..._traceLog' is never assigned to, and will always have its default value null
        void InitializeTraceLog() 
        {
            _traceLog = new TraceLog(20);
        }
 
        //------------------------------------------------------
        // 
        //  Private Fields 
        //
        //----------------------------------------------------- 

        private TraceLog        _traceLog;
        private Generator       _generator;
        private IGeneratorHost  _host; 
        private ItemBlock       _itemMap;
        private GeneratorStatus _status; 
        private int             _itemsGenerated; 
        private int             _startIndexForUIFromItem;
        private DependencyObject _peer; 
        private int             _level;
        private IList           _items;
        private GroupStyle      _groupStyle;
        private ItemContainerGenerator _parent; 
        private ArrayList       _emptyGroupItems;
        private int             _alternationCount; 
 
        private Type            _containerType;     // type of containers on the recycle queue
        private Queue _recyclableContainers = new Queue(); 

        event MapChangedHandler MapChanged;

        delegate void MapChangedHandler(ItemBlock block, int offset, int count, 
                    ItemBlock newBlock, int newOffset, int deltaCount);
 
#if GENERATOR_TRACE 
        MS.Internal.Utility.HFTimer _timer = new MS.Internal.Utility.HFTimer();
        MS.Internal.Utility.HFTimer _creationTimer = new MS.Internal.Utility.HFTimer(); 
#endif

        //------------------------------------------------------
        // 
        //  Private Nested Classes
        // 
        //----------------------------------------------------- 

        // The ItemContainerGenerator uses the following data structure to maintain 
        // the correspondence between items and their containers.  It's a doubly-linked
        // list of ItemBlocks, with a sentinel node serving as the header.
        // Each node maintains two counts:  the number of items it holds, and
        // the number of containers. 
        //
        // There are two kinds of blocks - one holding only "realized" items (i.e. 
        // items that have been generated into containers) and one holding only 
        // unrealized items.  The container count of a realized block is the same
        // as its item count (one container per item);  the container count of an 
        // unrealized block is zero.
        //
        // Unrealized blocks can hold any number of items.  We only need to know
        // the count.  Realized blocks have a fixed-sized array (BlockSize) so 
        // they hold up to that many items and their corresponding containers.  When
        // a realized block fills up, it inserts a new (empty) realized block into 
        // the list and carries on. 
        //
        // This data structure was chosen with virtualization in mind.  The typical 
        // state is a long block of unrealized items (the ones that have scrolled
        // off the top), followed by a moderate number (<50?) of realized items
        // (the ones in view), followed by another long block of unrealized items
        // (the ones that have not yet scrolled into view).  So the list will contain 
        // an unrealized block, followed by 3 or 4 realized blocks, followed by
        // another unrealized block.  Fewer than 10 blocks altogether, so linear 
        // searching won't cost that much.  Thus we don't need a more sophisticated 
        // data structure.  (If profiling reveals that we do, we can always replace
        // this one.  It's totally private to the ItemContainerGenerator and its 
        // Generators.)

        // represents a block of items
        private class ItemBlock 
        {
            public const int BlockSize = 16; 
 
            public int ItemCount { get { return _count; } set { _count = value; } }
            public ItemBlock Prev { get { return _prev; } set { _prev = value; } } 
            public ItemBlock Next { get { return _next; } set { _next = value; } }

            public virtual int ContainerCount { get { return Int32.MaxValue; } }
            public virtual DependencyObject ContainerAt(int index) { return null; } 
            public virtual object ItemAt(int index) { return null; }
 
            public void InsertAfter(ItemBlock prev) 
            {
                Next = prev.Next; 
                Prev = prev;

                Prev.Next = this;
                Next.Prev = this; 
            }
 
            public void InsertBefore(ItemBlock next) 
            {
                InsertAfter(next.Prev); 
            }

            public void Remove()
            { 
                Prev.Next = Next;
                Next.Prev = Prev; 
            } 

            public void MoveForward(ref GeneratorState state, bool allowMovePastRealizedItem) 
            {
                if (IsMoveAllowed(allowMovePastRealizedItem))
                {
                    state.ItemIndex += 1; 
                    if (++state.Offset >= ItemCount)
                    { 
                        state.Block = Next; 
                        state.Offset = 0;
                        state.Count += ItemCount; 
                    }
                }
            }
 
            public void MoveBackward(ref GeneratorState state, bool allowMovePastRealizedItem)
            { 
                if (IsMoveAllowed(allowMovePastRealizedItem)) 
                {
                    if (--state.Offset < 0) 
                    {
                        state.Block = Prev;
                        state.Offset = state.Block.ItemCount - 1;
                        state.Count -= state.Block.ItemCount; 
                    }
                    state.ItemIndex -= 1; 
                } 
            }
 
            protected virtual bool IsMoveAllowed(bool allowMovePastRealizedItem)
            {
                return allowMovePastRealizedItem;
            } 

            int _count; 
            ItemBlock _prev, _next; 
        }
 
        // represents a block of unrealized (ungenerated) items
        private class UnrealizedItemBlock : ItemBlock
        {
            public override int ContainerCount { get { return 0; } } 

            protected override bool IsMoveAllowed(bool allowMovePastRealizedItem) 
            { 
                return true;
            } 
        }

        // represents a block of realized (generated) items
        private class RealizedItemBlock : ItemBlock 
        {
            public override int ContainerCount { get { return ItemCount; } } 
 
            public override DependencyObject ContainerAt(int index)
            { 
                return _entry[index].Container;
            }

            public override object ItemAt(int index) 
            {
                return _entry[index].Item; 
            } 

            public void CopyEntries(RealizedItemBlock src, int offset, int count, int newOffset) 
            {
                int k;
                // choose which direction to copy so as not to clobber existing
                // entries (in case the source and destination blocks are the same) 
                if (offset < newOffset)
                { 
                    // copy right-to-left 
                    for (k = count - 1;  k >= 0;  --k)
                    { 
                        _entry[newOffset + k] = src._entry[offset + k];
                    }

                    // clear vacated entries, to avoid leak 
                    if (src != this)
                    { 
                        src.ClearEntries(offset, count); 
                    }
                    else 
                    {
                        src.ClearEntries(offset, newOffset - offset);
                    }
                } 
                else
                { 
                    // copy left-to-right 
                    for (k = 0;  k < count;  ++k)
                    { 
                        _entry[newOffset + k] = src._entry[offset + k];
                    }

                    // clear vacated entries, to avoid leak 
                    if (src != this)
                    { 
                        src.ClearEntries(offset, count); 
                    }
                    else 
                    {
                        src.ClearEntries(newOffset + count, offset - newOffset);
                    }
                } 
            }
 
            public void ClearEntries(int offset, int count) 
            {
                for (int i=0; i 0) 
                { 
                    ItemContainerGenerator generator = Generator;
                    generator.ItemsChanged -= new ItemsChangedEventHandler(OnItemsChanged); 
                    generator.Parent.OnSubgroupBecameNonEmpty(this, group);
                }
            }
        } 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
//---------------------------------------------------------------------------- 
//
// 
//    Copyright (C) Microsoft Corporation.  All rights reserved.
//  
//
// Description: ItemContainerGenerator object 
// 
// Specs:       http://avalon/connecteddata/M5%20General%20Docs/Data%20Styling.mht
// 
//---------------------------------------------------------------------------

using System;
using System.Collections; 
using System.Collections.Generic;
using System.Collections.Specialized; 
using System.ComponentModel; 
using System.Globalization;     // for CultureInfo.InvariantCulture (event tracing)
 
using System.Windows.Media;
using System.Windows.Controls.Primitives;   // IItemContainerGenerator
using System.Windows.Data;
using System.Windows.Markup; 
using System.Diagnostics;
using MS.Internal; 
using MS.Internal.Controls; 
using MS.Internal.KnownBoxes;
using MS.Internal.Utility; 
using MS.Utility;


namespace System.Windows.Controls 
{
    ///  
    /// An ItemContainerGenerator is responsible for generating the UI on behalf of 
    /// its host (e.g. ItemsControl).  It maintains the association between the items in
    /// the control's data view and the corresponding 
    /// UIElements.  The control's item-host can ask the ItemContainerGenerator for
    /// a Generator, which does the actual generation of UI.
    /// 
    public sealed class ItemContainerGenerator : IRecyclingItemContainerGenerator, IWeakEventListener 
    {
        //----------------------------------------------------- 
        // 
        //  Constructors
        // 
        //-----------------------------------------------------

        ///  Constructor 
        ///  the control that owns the items  
        internal ItemContainerGenerator(IGeneratorHost host)
            : this(null, host, host as DependencyObject, 0) 
        { 
            // The top-level generator always listens to changes from ItemsCollection.
            // It needs to get these events before anyone else, so that other listeners 
            // can call the generator's mapping functions with correct results.
            CollectionChangedEventManager.AddListener(host.View, this);
        }
 
        private ItemContainerGenerator(ItemContainerGenerator parent, GroupItem groupItem)
            : this(parent, parent.Host, groupItem, parent.Level + 1) 
        { 
        }
 
        private ItemContainerGenerator(ItemContainerGenerator parent, IGeneratorHost host, DependencyObject peer, int level)
        {
            _parent = parent;
            _host = host; 
            _peer = peer;
            _level = level; 
            OnRefresh(); 
        }
 
        //------------------------------------------------------
        //
        //  Public Properties
        // 
        //-----------------------------------------------------
 
        ///  The status of the generator  
        public GeneratorStatus Status
        { 
            get { return _status; }
        }

        //[CodeAnalysis("AptcaMethodsShouldOnlyCallAptcaMethods")] //Tracking Bug: 29647 
        private void SetStatus(GeneratorStatus value)
        { 
            if (value != _status) 
            {
                _status = value; 

                switch (_status)
                {
                    case GeneratorStatus.GeneratingContainers: 
                        if (EventTrace.IsEnabled(EventTrace.Flags.performance, EventTrace.Level.normal))
                        { 
                            EventTrace.EventProvider.TraceEvent(EventTrace.GuidFromId(EventTraceGuidId.GENERICSTRINGGUID), MS.Utility.EventType.StartEvent, "ItemsControl.Generator"); 
                            _itemsGenerated = 0;
                        } 
                        else
                            _itemsGenerated = Int32.MinValue;
#if GENERATOR_TRACE
                        _creationTimer.Reset(); 
                        _timer.Begin();
#endif 
                        break; 

                    case GeneratorStatus.ContainersGenerated: 
                        string label = null;
                        if (_itemsGenerated >= 0)   // this implies that tracing is enabled
                        {
                            DependencyObject d = Host as DependencyObject; 
                            if (d != null)
                                label = (string)d.GetValue(FrameworkElement.NameProperty); 
                            if (label == null || label.Length == 0) 
                                label = Host.GetHashCode().ToString(CultureInfo.InvariantCulture);
                            EventTrace.EventProvider.TraceEvent(EventTrace.GuidFromId(EventTraceGuidId.GENERICSTRINGGUID), 
                                                                 MS.Utility.EventType.EndEvent,
                                                                 String.Format(CultureInfo.InvariantCulture, "ItemContainerGenerator for {0} {1} - {2} items", Host.GetType().Name, label, _itemsGenerated));
                        }
#if GENERATOR_TRACE 
                        _timer.End();
                        if (_itemsGenerated > 0) 
                        { 
                            Console.WriteLine("Generator for {0} {1}  did {2} items in {3:f2} msec - {4:f2} msec/item",
                                Host.GetType().Name, label, _itemsGenerated, _timer.TimeOfLastPeriod, _timer.TimeOfLastPeriod/_itemsGenerated); 
                            Console.WriteLine("  this excludes time for element creation: {0:f2} msec - {1:f2} msec/item",
                                _creationTimer.OverallTimeInMilliseconds, _creationTimer.OverallTimeInMilliseconds/_itemsGenerated);
                        }
#endif 
                        break;
                } 
 
                if (StatusChanged != null)
                    StatusChanged(this, EventArgs.Empty); 
            }
        }

 
        //------------------------------------------------------
        // 
        //  Public Methods 
        //
        //------------------------------------------------------ 

        #region IItemContainerGenerator

        ///  
        /// Return the ItemContainerGenerator appropriate for use by the given panel
        ///  
        ItemContainerGenerator IItemContainerGenerator.GetItemContainerGeneratorForPanel(Panel panel) 
        {
            if (!panel.IsItemsHost) 
                throw new ArgumentException(SR.Get(SRID.PanelIsNotItemsHost), "panel");

            // if panel came from an ItemsPresenter, use its generator
            ItemsPresenter ip = ItemsPresenter.FromPanel(panel); 
            if (ip != null)
                return ip.Generator; 
 
            // if panel came from a style, use the main generator
            if (panel.TemplatedParent != null) 
                return this;

            // otherwise the panel doesn't have a generator
            return null; 
        }
 
        ///  Begin generating at the given position and direction  
        /// 
        /// This method must be called before calling GenerateNext.  It returns an 
        /// IDisposable object that tracks the lifetime of the generation loop.
        /// This method sets the generator's status to GeneratingContent;  when
        /// the IDisposable is disposed, the status changes to ContentReady or
        /// Error, as appropriate. 
        /// 
        IDisposable IItemContainerGenerator.StartAt(GeneratorPosition position, GeneratorDirection direction) 
        { 
            return ((IItemContainerGenerator)this).StartAt(position, direction, false);
        } 

        ///  Begin generating at the given position and direction 
        /// 
        /// This method must be called before calling GenerateNext.  It returns an 
        /// IDisposable object that tracks the lifetime of the generation loop.
        /// This method sets the generator's status to GeneratingContent;  when 
        /// the IDisposable is disposed, the status changes to ContentReady or 
        /// Error, as appropriate.
        ///  
        IDisposable IItemContainerGenerator.StartAt(GeneratorPosition position, GeneratorDirection direction, bool allowStartAtRealizedItem)
        {
            if (_generator != null)
                throw new InvalidOperationException(SR.Get(SRID.GenerationInProgress)); 

            _generator = new Generator(this, position, direction, allowStartAtRealizedItem); 
            return _generator; 
        }
 
        DependencyObject IItemContainerGenerator.GenerateNext()
        {
            bool isNewlyRealized;
            if (_generator == null) 
                throw new InvalidOperationException(SR.Get(SRID.GenerationNotInProgress));
 
            return _generator.GenerateNext(true, out isNewlyRealized); 
        }
 
        DependencyObject IItemContainerGenerator.GenerateNext(out bool isNewlyRealized)
        {
            if (_generator == null)
                throw new InvalidOperationException(SR.Get(SRID.GenerationNotInProgress)); 

            return _generator.GenerateNext(false, out isNewlyRealized); 
        } 

        ///  
        /// Prepare the given element to act as the container for the
        /// corresponding item.  This includes applying the container style,
        /// forwarding information from the host control (ItemTemplate, etc.),
        /// and other small adjustments. 
        /// 
        ///  
        /// This method must be called after the element has been added to the 
        /// visual tree, so that resource references and inherited properties
        /// work correctly. 
        /// 
        ///  The container to prepare.
        /// Normally this is the result of the previous call to GenerateNext.
        ///  
        void IItemContainerGenerator.PrepareItemContainer(DependencyObject container)
        { 
            object item = container.ReadLocalValue(ItemForItemContainerProperty); 
            Host.PrepareItemContainer(container, item);
        } 

        /// 
        /// Remove generated elements.
        ///  
        void IItemContainerGenerator.Remove(GeneratorPosition position, int count)
        { 
            Remove(position, count, /*isRecycling = */ false); 
        }
 
        /// 
        /// Remove generated elements.
        /// 
        private void Remove(GeneratorPosition position, int count, bool isRecycling) 
        {
            if (position.Offset != 0) 
                throw new ArgumentException(SR.Get(SRID.RemoveRequiresOffsetZero, position.Index, position.Offset), "position"); 
            if (count <= 0)
                throw new ArgumentException(SR.Get(SRID.RemoveRequiresPositiveCount, count), "count"); 

            int index = position.Index;
            ItemBlock block;
 
            // find the leftmost item to remove
            int offsetL = index; 
            for (block = _itemMap.Next;  block != _itemMap;  block = block.Next) 
            {
                if (offsetL < block.ContainerCount) 
                    break;

                offsetL -= block.ContainerCount;
            } 
            RealizedItemBlock blockL = block as RealizedItemBlock;
 
            // find the rightmost item to remove 
            int offsetR = offsetL + count - 1;
            for (; block != _itemMap;  block = block.Next) 
            {
                if (!(block is RealizedItemBlock))
                    throw new InvalidOperationException(SR.Get(SRID.CannotRemoveUnrealizedItems, index, count));
 
                if (offsetR < block.ContainerCount)
                    break; 
 
                offsetR -= block.ContainerCount;
            } 
            RealizedItemBlock blockR = block as RealizedItemBlock;

            // de-initialize the containers that are being removed
            RealizedItemBlock rblock = blockL; 
            int offset = offsetL;
            while (rblock != blockR || offset <= offsetR) 
            { 
                DependencyObject container = rblock.ContainerAt(offset);
 
                UnlinkContainerFromItem(container, rblock.ItemAt(offset), isRecycling);

                if (isRecycling)
                { 
                    Debug.Assert(!_recyclableContainers.Contains(container), "trying to add a container to the collection twice");
 
                    if (_containerType == null) 
                    {
                        _containerType = container.GetType(); 
                    }
                    else if (_containerType != container.GetType())
                    {
                        throw new InvalidOperationException(SR.Get(SRID.CannotRecyleHeterogeneousTypes)); 
                    }
 
                    _recyclableContainers.Enqueue(container); 
                }
 
                if (++offset >= rblock.ContainerCount && rblock != blockR)
                {
                    rblock = rblock.Next as RealizedItemBlock;
                    offset = 0; 
                }
            } 
 
            // see whether the range hits the edge of a block on either side,
            // and whether the a`butting block is an unrealized gap 
            bool edgeL = (offsetL == 0);
            bool edgeR = (offsetR == blockR.ItemCount-1);
            bool abutL = edgeL && (blockL.Prev is UnrealizedItemBlock);
            bool abutR = edgeR && (blockR.Next is UnrealizedItemBlock); 

            // determine the target (unrealized) block, 
            // the offset within the target at which to insert items, 
            // and the intial change in cumulative item count
            UnrealizedItemBlock blockT; 
            ItemBlock predecessor = null;
            int offsetT;
            int deltaCount;
 
            if (abutL)
            { 
                blockT = (UnrealizedItemBlock)blockL.Prev; 
                offsetT = blockT.ItemCount;
                deltaCount = -blockT.ItemCount; 
            }
            else if (abutR)
            {
                blockT = (UnrealizedItemBlock)blockR.Next; 
                offsetT = 0;
                deltaCount = offsetL; 
            } 
            else
            { 
                blockT = new UnrealizedItemBlock();
                offsetT = 0;
                deltaCount = offsetL;
 
                // remember where the new block goes, so we can insert it later
                predecessor = (edgeL) ? blockL.Prev : blockL; 
            } 

            // move items within the range to the target block 
            for (block = blockL;  block != blockR;  block = block.Next)
            {
                int itemCount = block.ItemCount;
                MoveItems(block, offsetL, itemCount-offsetL, 
                            blockT, offsetT, deltaCount);
                offsetT += itemCount-offsetL; 
                offsetL = 0; 
                deltaCount -= itemCount;
                if (block.ItemCount == 0) 
                    block.Remove();
            }

            // the last block in the range is a little special... 
            // Move the last unrealized piece.
            int remaining = block.ItemCount - 1 - offsetR; 
            MoveItems(block, offsetL, offsetR - offsetL + 1, 
                        blockT, offsetT, deltaCount);
 
            // Move the remaining realized items
            RealizedItemBlock blockX = blockR;
            if (!edgeR)
            { 
                if (blockL == blockR && !edgeL)
                { 
                    blockX = new RealizedItemBlock(); 
                }
 
                MoveItems(block, offsetR+1, remaining,
                            blockX, 0, offsetR+1);
            }
 
            // if we created any new blocks, insert them in the list
            if (predecessor != null) 
                blockT.InsertAfter(predecessor); 
            if (blockX != blockR)
                blockX.InsertAfter(blockT); 

            RemoveAndCoalesceBlocksIfNeeded(block);

        } 

        ///  
        /// Remove all generated elements. 
        /// 
        void IItemContainerGenerator.RemoveAll() 
        {
            // Take _itemMap offline, to protect against reentrancy (bug 1285179)
            ItemBlock itemMap = _itemMap;
            _itemMap = null; 

            try 
            { 
                // de-initialize the containers that are being removed
                if (itemMap != null) 
                {
                    for (ItemBlock block = itemMap.Next;  block != itemMap;  block = block.Next)
                    {
                        RealizedItemBlock rib = block as RealizedItemBlock; 
                        if (rib != null)
                        { 
                            for (int offset = 0; offset < rib.ContainerCount; ++offset) 
                            {
                                UnlinkContainerFromItem(rib.ContainerAt(offset), rib.ItemAt(offset)); 
                            }
                        }
                    }
                } 
            }
            finally 
            { 
                PrepareGrouping();
 
                // re-initialize the data structure
                _itemMap = new ItemBlock();
                _itemMap.Prev = _itemMap.Next = _itemMap;
 
                UnrealizedItemBlock uib = new UnrealizedItemBlock();
                uib.InsertAfter(_itemMap); 
                uib.ItemCount = Items.Count; 

                _recyclableContainers = new Queue(); 

                SetAlternationCount();

                // tell generators what happened 
                if (MapChanged != null)
                { 
                    MapChanged(null, -1, 0, uib, 0, 0); 
                }
            } 

        }

        void IRecyclingItemContainerGenerator.Recycle(GeneratorPosition position, int count) 
        {
            Remove(position, count, /*isRecyling = */ true); 
        } 

        ///  
        /// Map an index into the items collection to a GeneratorPosition.
        /// 
        GeneratorPosition IItemContainerGenerator.GeneratorPositionFromIndex(int itemIndex)
        { 
            GeneratorPosition position;
            ItemBlock itemBlock; 
            int offsetFromBlockStart; 

            GetBlockAndPosition(itemIndex, out position, out itemBlock, out offsetFromBlockStart); 

            if (itemBlock == _itemMap && position.Index == -1)
                ++position.Offset;
 
            return position;
        } 
 
        /// 
        /// Map a GeneratorPosition to an index into the items collection. 
        /// 
        int IItemContainerGenerator.IndexFromGeneratorPosition(GeneratorPosition position)
        {
            int index = position.Index; 

            if (index == -1) 
            { 
                // offset is relative to the fictitious boundary item
                if (position.Offset >= 0) 
                {
                    return position.Offset - 1;
                }
                else 
                {
                    return Items.Count + position.Offset; 
                } 
            }
 
            if (_itemMap != null)
            {
                int itemIndex = 0;      // number of items we've skipped over
 
                // locate container at the given index
                for (ItemBlock block = _itemMap.Next;  block != _itemMap;  block = block.Next) 
                { 
                    if (index < block.ContainerCount)
                    { 
                        // container is within this block.  return the answer
                        return itemIndex + index + position.Offset;
                    }
                    else 
                    {
                        // skip over this block 
                        itemIndex += block.ItemCount; 
                        index -= block.ContainerCount;
                    } 
                }
            }

            return -1; 
        }
 
        #endregion IItemContainerGenerator 

        ///  
        /// Return the item corresponding to the given UI element.
        /// If the element was not generated as a container for this generator's
        /// host, the method returns DependencyProperty.UnsetValue.
        ///  
        public object ItemFromContainer(DependencyObject container)
        { 
            if (container == null) 
                throw new ArgumentNullException("container");
 
            object item = container.ReadLocalValue(ItemForItemContainerProperty);

            if (item != DependencyProperty.UnsetValue)
            { 
                // verify that the element really belongs to the host
                if (!Host.IsHostForItemContainer(container)) 
                    item = DependencyProperty.UnsetValue; 
            }
 
            return item;
        }

        ///  
        /// Return the UI element corresponding to the given item.
        /// Returns null if the item does not belong to the item collection, 
        /// or if no UI has been generated for it. 
        /// 
        public DependencyObject ContainerFromItem(object item) 
        {
            DependencyObject container = null;
            int index;
            DoLinearSearch(ref container, ref item, out index); 

            return container; 
        } 

        ///  
        /// Given a generated UI element, return the index of the corresponding item
        /// within the ItemCollection.
        /// 
        public int IndexFromContainer(DependencyObject container) 
        {
            if (container == null) 
            { 
                throw new ArgumentNullException("container");
            } 

            object item = null;
            int index;
            DoLinearSearch(ref container, ref item, out index); 

            return index; 
        } 

        ///  
        ///     Performs a linear search.
        /// 
        /// 
        ///     There's no avoiding a linear search, which leads to O(n^2) performance 
        ///     if someone calls ContainerFromItem or IndexFromContainer for every item.
        ///     To mitigate this, we start each search at _startIndexForUIFromItem, and 
        ///     heuristically set this in various places to where we expect the next 
        ///     call to occur.
        /// 
        ///     For example, after a successul search, we set it to the resulting
        ///     index, hoping that the next call will query either the same item or
        ///     the one after it.  And after inserting a new item, we expect a query
        ///     about the new item.  Etc. 
        ///
        ///     Saving this as an index instead of a (block, offset) pair, makes it 
        ///     more robust during insertions/deletions.  If the index ends up being 
        ///     wrong, the worst that happens is a full search (as opposed to following
        ///     a reference to a block that's no longer in use). 
        ///
        ///     To re-use the search code for two methods, please read the description
        ///     of the parameters.
        ///  
        /// 
        ///     If non-null, then searches for the container. 
        ///     Otherwise, updated with container for the item. 
        /// 
        ///  
        ///     If non-null, then searches for the item.
        ///     Otherwise, updated with the item that the container represents.
        /// 
        ///  
        ///     If a container or item is found, then updated with its index.
        ///     Otherwise, set to -1. 
        ///  
        /// 
        ///     true if found, false otherwise. 
        /// 
        private bool DoLinearSearch(ref DependencyObject container, ref object item, out int itemIndex)
        {
            itemIndex = 0; 

            if (_itemMap == null) 
            { 
                // _itemMap can be null if we re-enter the generator.  Scenario:  user calls RemoveAll(), we Unlink every container, fire
                // ClearContainerForItem for each, and someone overriding ClearContainerForItem decides to look up the container. 
                return false;
            }

            // Move to the starting point of the search 
            ItemBlock startBlock = _itemMap.Next;
            int index = 0;      // index of first item in current block 
            RealizedItemBlock rib; 
            int startOffset;
 
            while (index <= _startIndexForUIFromItem && startBlock != _itemMap)
            {
                index += startBlock.ItemCount;
                startBlock = startBlock.Next; 
            }
            startBlock = startBlock.Prev; 
            index -= startBlock.ItemCount; 
            rib = startBlock as RealizedItemBlock;
 
            if (rib != null)
            {
                startOffset = _startIndexForUIFromItem - index;
                if (startOffset >= rib.ItemCount) 
                {
                    // we can get here if items get removed since the last 
                    // time we saved _startIndexForUIFromItem - so the 
                    // saved offset is no longer meaningful.  To make the
                    // search work, we need to make sure the first loop 
                    // does at least one iteration.  Setting startOffset to 0
                    // does exactly that.
                    startOffset = 0;
                } 
            }
            else 
            { 
                startOffset = 0;
            } 

            // search for the desired item, wrapping around the end
            ItemBlock block = startBlock;
            int offset = startOffset; 
            int endOffset = startBlock.ItemCount;
            while (true) 
            { 
                // search the current block (only need to search realized blocks)
                if (rib != null) 
                {
                    for (; offset < endOffset; ++offset)
                    {
                        CollectionViewGroup group; 
                        bool found = false;
                        if (container != null) 
                        { 
                            if (rib.ContainerAt(offset) == container)
                            { 
                                found = true;
                                item = rib.ItemAt(offset);
                            }
                        } 
                        else
                        { 
                            if (Object.Equals(item, rib.ItemAt(offset))) 
                            {
                                found = true; 
                                container = rib.ContainerAt(offset);
                            }
                        }
 
                        if (IsGrouping && !found && ((group = rib.ItemAt(offset) as CollectionViewGroup) != null))
                        { 
                            // found a group;  see if the group contains the item 
                            GroupItem groupItem = (GroupItem)rib.ContainerAt(offset);
                            found = groupItem.Generator.DoLinearSearch(ref container, ref item, out itemIndex); 
                        }

                        if (found)
                        { 
                            // found the item;  update state and return
                            _startIndexForUIFromItem = index + offset; 
                            itemIndex += GetRealizedItemBlockCount(rib, offset) + GetCount(block); 
                            return true;
                        } 
                    }

                    // check for termination
                    if (block == startBlock && offset == startOffset) 
                    {
                        itemIndex = -1; 
                        return false; 
                    }
                } 

                // advance to next block
                index += block.ItemCount;
                offset = 0; 
                block = block.Next;
 
                // if we've reached the end, wrap around 
                if (block == _itemMap)
                { 
                    block = block.Next;
                    index = 0;
                }
 
                // prepare to search the block
                endOffset = block.ItemCount; 
                rib = block as RealizedItemBlock; 

                // check for termination 
                if (block == startBlock)
                {
                    if (rib != null)
                    { 
                        endOffset = startOffset;    // search first part of block
                    } 
                    else 
                    {
                        itemIndex = -1; 
                        return false;
                    }
                }
            } 
        }
 
        private int GetCount() 
        {
            return GetCount(_itemMap); 
        }

        private int GetCount(ItemBlock stop)
        { 
            int count = 0;
            ItemBlock start = _itemMap; 
            ItemBlock block = start.Next; 

            while (block != stop) 
            {
                RealizedItemBlock rib = block as RealizedItemBlock;
                if (rib != null)
                { 
                    // Search for groups within realized blocks
                    count += GetRealizedItemBlockCount(rib, rib.ItemCount); 
                } 
                else
                { 
                    count += block.ItemCount;
                }

                block = block.Next; 
            }
 
            return count; 
        }
 
        private int GetRealizedItemBlockCount(RealizedItemBlock rib, int end)
        {
            if (!IsGrouping)
            { 
                // when the UI is not grouping, each item counts as 1, even
                // groups (bug 1761421) 
                return end; 
            }
 
            int count = 0;

            for (int offset = 0; offset < end; ++offset)
            { 
                CollectionViewGroup group;
                if ((group = rib.ItemAt(offset) as CollectionViewGroup) != null) 
                { 
                    // found a group, count the group
                    GroupItem groupItem = (GroupItem)rib.ContainerAt(offset); 
                    count += groupItem.Generator.GetCount();
                }
                else
                { 
                    count++;
                } 
            } 

            return count; 
        }

        /// 
        /// Return the UI element corresponding to the item at the given index 
        /// within the ItemCollection.
        ///  
        public DependencyObject ContainerFromIndex(int index) 
        {
#if DEBUG 
            object target = (Parent == null) && (0 <= index  &&  index < Host.View.Count) ? Host.View[index] : null;
#endif
            int subIndex = 0;
 
            // if we're grouping, determine the appropriate child
            if (IsGrouping) 
            { 
                int n;
                subIndex = index; 
                for (index=0, n=Items.Count;  index < n;  ++index)
                {
                    CollectionViewGroup group = Items[index] as CollectionViewGroup;
                    int size = (group == null) ? 1 : group.ItemCount; 

                    if (subIndex < size) 
                        break; 
                    else
                        subIndex -= size; 
                }
            }

            // search the table for the item 

            for (ItemBlock block = _itemMap.Next; block != _itemMap; block = block.Next) 
            { 
                if (index < block.ItemCount)
                { 
                    DependencyObject container = block.ContainerAt(index);
                    GroupItem groupItem = container as GroupItem;

                    if (groupItem != null) 
                    {
                        container = groupItem.Generator.ContainerFromIndex(subIndex); 
                    } 
#if DEBUG
                    object item = (Parent == null) && (container != null) ? 
                                container.ReadLocalValue(ItemForItemContainerProperty) : null;
                    Debug.Assert(item == null || Object.Equals(item, target),
                        "Generator's data structure is corrupt - ContainerFromIndex found wrong item");
#endif 
                    return container;
                } 
 
                index -= block.ItemCount;
            } 

            return null;  // *not* throw new IndexOutOfRangeException(); - bug 890195
        }
 

        //----------------------------------------------------- 
        // 
        //  Public Events
        // 
        //------------------------------------------------------

        /// 
        /// The ItemsChanged event is raised by a ItemContainerGenerator to inform 
        /// layouts that the items collection has changed.
        ///  
        public event ItemsChangedEventHandler ItemsChanged; 

        ///  
        /// The StatusChanged event is raised by a ItemContainerGenerator to inform
        /// controls that its status has changed.
        /// 
        public event EventHandler StatusChanged; 

 
        //----------------------------------------------------- 
        //
        //  Internal methods 
        //
        //-----------------------------------------------------

        // regenerate everything 
        internal void Refresh()
        { 
            OnRefresh(); 
        }
 
        // called when this generator is no longer needed
        internal void Release()
        {
            ((IItemContainerGenerator)this).RemoveAll(); 
        }
 
        // called when the host's AlternationCount changes 
        internal void ChangeAlternationCount()
        { 
            // update my AlternationCount and adjust my containers
            SetAlternationCount();

            // propagate to subgroups, if necessary 
            if (IsGrouping && GroupStyle != null)
            { 
                ItemBlock block = _itemMap.Next; 
                while (block != _itemMap)
                { 
                    for (int offset = 0;  offset < block.ContainerCount;  ++offset)
                    {
                        GroupItem gi = ((RealizedItemBlock)block).ContainerAt(offset) as GroupItem;
                        if (gi != null) 
                        {
                            gi.Generator.ChangeAlternationCount(); 
                        } 
                    }
 
                    block = block.Next;
                }
            }
        } 

        // update AlternationIndex on each container to reflect the new AlternationCount 
        void ChangeAlternationCount(int newAlternationCount) 
        {
            if (_alternationCount == newAlternationCount) 
                return;

            // find the first realized container (need this regardless of what happens)
            ItemBlock block = _itemMap.Next; 
            int offset = 0;
            while (offset == block.ContainerCount) 
            { 
                block = block.Next;
            } 

            // if there are no realized containers, there's nothing to do
            if (block != _itemMap)
            { 
                // if user is requesting alternation, reset each container's AlternationIndex
                if (newAlternationCount > 0) 
                { 
                    _alternationCount = newAlternationCount;
                    SetAlternationIndex((RealizedItemBlock)block, offset, GeneratorDirection.Forward); 
                }
                // otherwise, clear each container's AlternationIndex
                else if (_alternationCount > 0)
                { 
                    while (block != _itemMap)
                    { 
                        for (offset = 0;  offset < block.ContainerCount;  ++offset) 
                        {
                            ItemsControl.ClearAlternationIndex(((RealizedItemBlock)block).ContainerAt(offset)); 
                        }

                        block = block.Next;
                    } 
                }
            } 
 
            _alternationCount = newAlternationCount;
        } 

        //-----------------------------------------------------
        //
        //  Internal properties 
        //
        //------------------------------------------------------ 
 
        internal ItemContainerGenerator Parent
        { 
            get { return _parent;}
        }

        internal int Level 
        {
            get { return _level;} 
        } 

        // The group style that governs the generation of UI for the items. 
        internal GroupStyle GroupStyle
        {
            get { return _groupStyle; }
            set 
            {
                if (_groupStyle != value) 
                { 
                    if (_groupStyle is INotifyPropertyChanged)
                    { 
                        PropertyChangedEventManager.RemoveListener(_groupStyle, this, String.Empty);
                    }

                    _groupStyle = value; 

                    if (_groupStyle is INotifyPropertyChanged) 
                    { 
                        PropertyChangedEventManager.AddListener(_groupStyle, this, String.Empty);
                    } 
                }
            }
        }
 
        // The collection of items, as IList
        internal IList Items 
        { 
            get { return _items; }
            set 
            {
                if (_items != value)
                {
                    INotifyCollectionChanged incc = _items as INotifyCollectionChanged; 
                    if (_items != Host.View && incc != null)
                    { 
                        CollectionChangedEventManager.RemoveListener(incc, this); 
                    }
 
                    _items = value;

                    incc = _items as INotifyCollectionChanged;
                    if (_items != Host.View && incc != null) 
                    {
                        CollectionChangedEventManager.AddListener(incc, this); 
                    } 
                }
            } 
        }

        /// 
        ///     ItemForItemContainer DependencyProperty 
        /// 
        // This is an attached property that the generator sets on each container 
        // (generated or direct) to point back to the item. 
        internal static readonly DependencyProperty ItemForItemContainerProperty =
                DependencyProperty.RegisterAttached("ItemForItemContainer", typeof(object), typeof(ItemContainerGenerator), 
                                            new FrameworkPropertyMetadata((object)null));

        //-----------------------------------------------------
        // 
        //  Internal events
        // 
        //------------------------------------------------------ 

        internal event EventHandler PanelChanged; 

        internal void OnPanelChanged()
        {
            if (PanelChanged != null) 
                PanelChanged(this, EventArgs.Empty);
        } 
 
        //------------------------------------------------------
        // 
        //  Private Nested Class -  ItemContainerGenerator.Generator
        //
        //-----------------------------------------------------
 

        ///  
        ///     Generator is the object that generates UI on behalf of an ItemsControl, 
        ///     working under the supervision of an ItemContainerGenerator.
        ///  
        private class Generator : IDisposable
        {
            //------------------------------------------------------
            // 
            //  Constructors
            // 
            //----------------------------------------------------- 

            internal Generator(ItemContainerGenerator factory, GeneratorPosition position, GeneratorDirection direction, bool allowStartAtRealizedItem) 
            {
                _factory = factory;
                _direction = direction;
 
                _factory.MapChanged += new MapChangedHandler(OnMapChanged);
 
                _factory.MoveToPosition(position, direction, allowStartAtRealizedItem, ref _cachedState); 
                _done = (_factory.Items.Count == 0);
 
                _factory.SetStatus(GeneratorStatus.GeneratingContainers);
            }

            //----------------------------------------------------- 
            //
            //  Public Properties 
            // 
            //-----------------------------------------------------
 
/* This method was requested for virtualization.  It's not being used right now
(bug 1079525) but it probably will be when UI virtualization comes back.
            /// 
            /// returns false if a call to GenerateNext is known to return null (indicating 
            /// that the generator is done).  Does not generate anything or change the
            /// generator's state;  cheaper than GenerateNext.  Returning true does not 
            /// necessarily mean GenerateNext will produce anything. 
            /// 
            public bool IsActive 
            {
                get { return !_done; }
            }
*/ 

            //------------------------------------------------------ 
            // 
            //  Public Methods
            // 
            //-----------------------------------------------------

            ///  Generate UI for the next item or group
            public DependencyObject GenerateNext(bool stopAtRealized, out bool isNewlyRealized) 
            {
                DependencyObject container = null; 
                isNewlyRealized = false; 

                while (container == null) 
                {
                    UnrealizedItemBlock uBlock = _cachedState.Block as UnrealizedItemBlock;
                    IList items = _factory.Items;
                    int itemIndex = _cachedState.ItemIndex; 
                    int incr = (_direction == GeneratorDirection.Forward) ? +1 : -1;
 
                    if (_cachedState.Block == _factory._itemMap) 
                        _done = true;            // we've reached the end of the list
 
                    if (uBlock == null && stopAtRealized)
                        _done = true;

                    if (!(0 <= itemIndex && itemIndex < items.Count)) 
                        _done = true;
 
                    if (_done) 
                    {
                        isNewlyRealized = false; 
                        return null;
                    }

                    object item = items[itemIndex]; 

                    if (uBlock != null) 
                    { 
                        // We don't have a realized container for this item.  Try to use a recycled container
                        // if possible, otherwise generate a new container. 

                        isNewlyRealized = true;

                        CollectionViewGroup group = item as CollectionViewGroup; 
                        if (group == null || !_factory.IsGrouping)
                        { 
 
                            if (_factory._recyclableContainers.Count > 0 && !_factory.Host.IsItemItsOwnContainer(item))
                            { 
                                container = _factory._recyclableContainers.Dequeue();
                                isNewlyRealized = false;
                            }
                            else 
                            {
                                // generate container for an item 
                                container = _factory.Host.GetContainerForItem(item); 
                            }
 
                            ItemContainerGenerator.LinkContainerToItem(container, item, /* isRecycled = */ !isNewlyRealized);
                        }
                        else
                        { 
                            // generate container for a group
                            container = _factory.ContainerForGroup(group); 
                        } 

                        // add the (item, container) to the current block 
                        if (container != null)
                        {
                            _factory.Realize(uBlock, _cachedState.Offset, item, container);
 
                            // set AlternationIndex on the container (and possibly others)
                            _factory.SetAlternationIndex(_cachedState.Block, _cachedState.Offset, _direction); 
                        } 
                    }
                    else 
                    {
                        // return existing realized container
                        isNewlyRealized = false;
                        RealizedItemBlock rib = (RealizedItemBlock)_cachedState.Block; 
                        container = rib.ContainerAt(_cachedState.Offset);
                    } 
 
                    // advance to the next item
                    _cachedState.ItemIndex = itemIndex; 
                    if (_direction == GeneratorDirection.Forward)
                    {
                        _cachedState.Block.MoveForward(ref _cachedState, true);
                    } 
                    else
                    { 
                        _cachedState.Block.MoveBackward(ref _cachedState, true); 
                    }
                } 

                return container;
            }
 
            //------------------------------------------------------
            // 
            //  Interfaces - IDisposable 
            //
            //------------------------------------------------------ 

            ///  Dispose this generator. 
            void IDisposable.Dispose()
            { 
                if (_factory != null)
                { 
                    _factory.MapChanged -= new MapChangedHandler(OnMapChanged); 
                    _done = true;
                    _factory.SetStatus(GeneratorStatus.ContainersGenerated); 
                    _factory._generator = null;
                    _factory = null;
                }
            } 

            //----------------------------------------------------- 
            // 
            //  Private methods
            // 
            //------------------------------------------------------

            // The map data structure has changed, so the state must change accordingly.
            // This is called in various different ways. 
            //  A. Items were moved within the data structure, typically because
            //  items were realized or un-realized.  In this case, the args are: 
            //      block - the block from where the items were moved 
            //      offset - the offset within the block of the first item moved
            //      count - how many items moved 
            //      newBlock - the block to which the items were moved
            //      newOffset - the offset within the new block of the first item moved
            //      deltaCount - the difference between the cumululative item counts
            //                  of newBlock and block 
            //  B. An item was added or removed from the data structure.  In this
            //  case the args are: 
            //      block - null  (to distinguish case B from case A) 
            //      offset - the index of the changed item, w.r.t. the entire item list
            //      count - +1 for insertion, -1 for deletion 
            //      others - unused
            //  C. Refresh: all items are returned to a single unrealized block.
            //  In this case, the args are:
            //      block - null 
            //      offset - -1 (to distinguish case C from case B)
            //      newBlock = the single unrealized block 
            //      others - unused 
            void OnMapChanged(ItemBlock block, int offset, int count,
                            ItemBlock newBlock, int newOffset, int deltaCount) 
            {
                // Case A.  Items were moved within the map data structure
                if (block != null)
                { 
                    // if the move affects this generator, update the cached state
                    if (block == _cachedState.Block && offset <= _cachedState.Offset && 
                        _cachedState.Offset < offset + count) 
                    {
                        _cachedState.Block = newBlock; 
                        _cachedState.Offset += newOffset - offset;
                        _cachedState.Count += deltaCount;
                    }
                } 
                // Case B.  An item was inserted or deleted
                else if (offset >= 0) 
                { 
                    // if the item occurs before my block, update my item count
                    if (offset < _cachedState.Count) 
                    {
                        _cachedState.Count += count;
                        _cachedState.ItemIndex += count;
                    } 
                    // if the item occurs within my block before my item, update my offset
                    else if (offset < _cachedState.Count + _cachedState.Offset) 
                    { 
                        _cachedState.Offset += count;
                        _cachedState.ItemIndex += count; 
                    }
                    // if an insert occurs at my position, update my offset
                    else if (offset == _cachedState.Count + _cachedState.Offset &&
                        count > 0) 
                    {
                        _cachedState.Offset += count; 
                        _cachedState.ItemIndex += count; 
                    }
                } 
                // Case C.  Refresh
                else
                {
                    _cachedState.Block = newBlock; 
                    _cachedState.Offset += _cachedState.Count;
                    _cachedState.Count = 0; 
                } 
            }
 
            //-----------------------------------------------------
            //
            //  Private Fields
            // 
            //-----------------------------------------------------
 
            ItemContainerGenerator     _factory; 
            GeneratorDirection  _direction;
            bool                _done; 
            GeneratorState      _cachedState;
        }

 
        //-----------------------------------------------------
        // 
        //  Private Properties 
        //
        //------------------------------------------------------ 

        IGeneratorHost Host { get { return _host; } }

        // The DO for which this generator was created.  For normal generators, 
        // this is the ItemsControl.  For subgroup generators, this is
        // the GroupItem. 
        DependencyObject Peer 
        {
            get { return _peer; } 
        }

        bool IsGrouping
        { 
            get { return (Items != Host.View); }
        } 
 

        //----------------------------------------------------- 
        //
        //  Private Methods
        //
        //------------------------------------------------------ 

        void MoveToPosition(GeneratorPosition position, GeneratorDirection direction, bool allowStartAtRealizedItem, ref GeneratorState state) 
        { 
            ItemBlock block = _itemMap;
            int itemIndex = 0; 

            // first move to the indexed (realized) item
            if (position.Index != -1)
            { 
                // find the right block
                int itemCount = 0; 
                int index = position.Index; 
                block = block.Next;
                while (index >= block.ContainerCount) 
                {
                    itemCount += block.ItemCount;
                    index -= block.ContainerCount;
                    itemIndex += block.ItemCount; 
                    block = block.Next;
                } 
 
                // set the position
                state.Block = block; 
                state.Offset = index;
                state.Count = itemCount;
                state.ItemIndex = itemIndex + index;
            } 
            else
            { 
                state.Block = block; 
                state.Offset = 0;
                state.Count = 0; 
                state.ItemIndex = itemIndex - 1;
            }

            // adjust the offset - we always set the state so it points to the next 
            // item to be generated.
            int offset = position.Offset; 
            if (offset == 0 && (!allowStartAtRealizedItem || state.Block == _itemMap)) 
            {
                offset = (direction == GeneratorDirection.Forward) ? 1 : -1; 
            }

            // advance the state according to the offset
            if (offset > 0) 
            {
                state.Block.MoveForward(ref state, true); 
                while (--offset > 0) 
                {
                    state.Block.MoveForward(ref state, allowStartAtRealizedItem); 
                }
            }
            else if (offset < 0)
            { 
                if (state.Block == _itemMap)
                { 
                    state.ItemIndex = state.Count = Items.Count; 
                }
                state.Block.MoveBackward(ref state, true); 
                while (++offset < 0)
                {
                    state.Block.MoveBackward(ref state, allowStartAtRealizedItem);
                } 
            }
        } 
 
        // "Realize" the item in a block at the given offset, to be
        // the given item with corresponding container.  This means updating 
        // the item map data structure so that the item belongs to a Realized block.
        // It also requires updating the state of every generator to track the
        // changes we make here.
        void Realize(UnrealizedItemBlock block, int offset, object item, DependencyObject container) 
        {
            RealizedItemBlock prevR, nextR; 
 
            RealizedItemBlock newBlock; // new location of the target item
            int newOffset;              // its offset within the new block 
            int deltaCount;             // diff between cumulative item count of block and newBlock

            // if we're realizing the leftmost item and there's room in the
            // previous block, move it there 
            if (offset == 0 &&
                (prevR = block.Prev as RealizedItemBlock) != null && 
                prevR.ItemCount < ItemBlock.BlockSize) 
            {
                newBlock = prevR; 
                newOffset = prevR.ItemCount;
                MoveItems(block, offset, 1, newBlock, newOffset, -prevR.ItemCount);
                MoveItems(block, 1, block.ItemCount, block, 0, +1);
            } 

            // if we're realizing the rightmost item and there's room in the 
            // next block, move it there 
            else if (offset == block.ItemCount - 1 &&
                (nextR = block.Next as RealizedItemBlock) != null && 
                nextR.ItemCount < ItemBlock.BlockSize)
            {
                newBlock = nextR;
                newOffset = 0; 
                MoveItems(newBlock, 0, newBlock.ItemCount, newBlock, 1, -1);
                MoveItems(block, offset, 1, newBlock, newOffset, offset); 
            } 

            // otherwise we need a new block for the target item 
            else
            {
                newBlock = new RealizedItemBlock();
                newOffset = 0; 
                deltaCount = offset;
 
                // if target is leftmost item, insert it before remaining items 
                if (offset == 0)
                { 
                    newBlock.InsertBefore(block);
                    MoveItems(block, offset, 1, newBlock, newOffset, 0);
                    MoveItems(block, 1, block.ItemCount, block, 0, +1);
                } 

                // if target is rightmost item, insert it after remaining items 
                else if (offset == block.ItemCount - 1) 
                {
                    newBlock.InsertAfter(block); 
                    MoveItems(block, offset, 1, newBlock, newOffset, offset);
                }

                // otherwise split the block into two, with the target in the middle 
                else
                { 
                    UnrealizedItemBlock newUBlock = new UnrealizedItemBlock(); 
                    newUBlock.InsertAfter(block);
                    newBlock.InsertAfter(block); 
                    MoveItems(block, offset+1, block.ItemCount-offset-1, newUBlock, 0, offset+1);
                    MoveItems(block, offset, 1, newBlock, 0, offset);
                }
            } 

            RemoveAndCoalesceBlocksIfNeeded(block); 
 
            // add the new target to the map
            newBlock.RealizeItem(newOffset, item, container); 
        }

        void RemoveAndCoalesceBlocksIfNeeded(ItemBlock block)
        { 
            if (block != null && block != _itemMap && block.ItemCount == 0)
            { 
                block.Remove(); 

                // coalesce adjacent unrealized blocks 
                if (block.Prev is UnrealizedItemBlock && block.Next is UnrealizedItemBlock)
                {
                    MoveItems(block.Next, 0, block.Next.ItemCount, block.Prev, block.Prev.ItemCount, -block.Prev.ItemCount-1);
                    block.Next.Remove(); 
                }
            } 
        } 

        // Move 'count' items starting at position 'offset' in block 'block' 
        // to position 'newOffset' in block 'newBlock'.  The difference between
        // the cumulative item counts of newBlock and block is given by 'deltaCount'.
        void MoveItems(ItemBlock block, int offset, int count,
                        ItemBlock newBlock, int newOffset, int deltaCount) 
        {
            RealizedItemBlock ribSrc = block as RealizedItemBlock; 
            RealizedItemBlock ribDst = newBlock as RealizedItemBlock; 

            // when both blocks are Realized, entries must be physically copied 
            if (ribSrc != null && ribDst != null)
            {
                ribDst.CopyEntries(ribSrc, offset, count, newOffset);
            } 
            // when the source block is Realized, clear the vacated entries -
            // to avoid leaks.  (No need if it's now empty - the block will get GC'd). 
            else if (ribSrc != null && ribSrc.ItemCount > count) 
            {
                ribSrc.ClearEntries(offset, count); 
            }

            // update block information
            block.ItemCount -= count; 
            newBlock.ItemCount += count;
 
            // tell generators what happened 
            if (MapChanged != null)
                MapChanged(block, offset, count, newBlock, newOffset, deltaCount); 
        }

        // Set the AlternationIndex on a newly-realized container.  Also, reset
        // the AlternationIndex on other containers to maintain the adjacency 
        // criterion.
        void SetAlternationIndex(ItemBlock block, int offset, GeneratorDirection direction) 
        { 
            // If user doesn't request alternation, don't do anything
            if (_alternationCount <= 0) 
                return;

            int index;
            RealizedItemBlock rib; 

            // Proceed in the direction of generation.  This tends to reach the 
            // end sooner (often in one step). 
            if (direction != GeneratorDirection.Backward)
            { 
                // Forward.  Back up one container to determine the starting index
                -- offset;
                while (offset < 0 || block is UnrealizedItemBlock)
                { 
                    block = block.Prev;
                    offset = block.ContainerCount - 1; 
                } 

                rib = block as RealizedItemBlock; 
                index = (block == _itemMap) ? -1 : ItemsControl.GetAlternationIndex(rib.ContainerAt(offset));

                // loop through the remaining containers, resetting each AlternationIndex
                for (;;) 
                {
                    // advance to next realized container 
                    ++offset; 
                    while (offset == block.ContainerCount)
                    { 
                        block = block.Next;
                        offset = 0;
                    }
 
                    // exit if we've reached the end
                    if (block == _itemMap) 
                        break; 

                    // advance the AlternationIndex 
                    index = (index + 1) % _alternationCount;

                    // assign it to the container
                    rib = block as RealizedItemBlock; 
                    ItemsControl.SetAlternationIndex(rib.ContainerAt(offset), index);
                } 
            } 
            else
            { 
                // Backward.  Advance one container to determine the starting index
                ++ offset;
                while (offset >= block.ContainerCount || block is UnrealizedItemBlock)
                { 
                    block = block.Next;
                    offset = 0; 
                } 

                rib = block as RealizedItemBlock; 
                index = (block == _itemMap) ? _alternationCount : ItemsControl.GetAlternationIndex(rib.ContainerAt(offset));

                // loop through the remaining containers, resetting each AlternationIndex
                for (;;) 
                {
                    // retreat to next realized container 
                    --offset; 
                    while (offset == 0)
                    { 
                        block = block.Prev;
                        offset = block.ContainerCount;
                    }
 
                    // exit if we've reached the end
                    if (block == _itemMap) 
                        break; 

                    // retreat the AlternationIndex 
                    index = (index - 1) % _alternationCount;

                    // assign it to the container
                    rib = block as RealizedItemBlock; 
                    ItemsControl.SetAlternationIndex(rib.ContainerAt(offset), index);
                } 
            } 
        }
 
        // create a group item for the given group
        DependencyObject ContainerForGroup(CollectionViewGroup group)
        {
            if (!ShouldHide(group)) 
            {
                // normal group - link a new GroupItem 
                GroupItem groupItem = new GroupItem(); 

                LinkContainerToItem(groupItem, group); 

                // create the generator
                groupItem.Generator = new ItemContainerGenerator(this, groupItem);
 
                return groupItem;
            } 
            else 
            {
                // hidden empty group - link a new EmptyGroupItem 
                AddEmptyGroupItem(group);

                // but don't return it to layout
                return null; 
            }
        } 
 
        // prepare the grouping information.  Called from RemoveAll.
        void PrepareGrouping() 
        {
            GroupStyle groupStyle;
            IList items;
 
            if (Level == 0)
            { 
                groupStyle = Host.GetGroupStyle(null, 0); 

                if (groupStyle == null) 
                {
                    items = Host.View;
                }
                else 
                {
                    CollectionView cv = Host.View.CollectionView; 
                    items = (cv == null) ? null : cv.Groups; 
                    if (items == null)
                    { 
                        items = Host.View;
                    }
                }
            } 
            else
            { 
                GroupItem groupItem = (GroupItem)Peer; 
                CollectionViewGroup group = groupItem.ReadLocalValue(ItemForItemContainerProperty) as CollectionViewGroup;
 
                if (group != null)
                {
                    if (group.IsBottomLevel)
                    { 
                        groupStyle = null;
                    } 
                    else 
                    {
                        groupStyle = Host.GetGroupStyle(group, Level); 
                    }

                    items = group.Items;
                } 
                else
                { 
                    groupStyle = null; 
                    items = Host.View;
                } 
            }

            GroupStyle = groupStyle;
            Items = items; 

            if ((Level == 0) && (Host != null)) 
            { 
                // Notify the host of a change in IsGrouping
                Host.SetIsGrouping(IsGrouping); 
            }
        }

        void SetAlternationCount() 
        {
            int alternationCount; 
 
            if (IsGrouping && GroupStyle != null)
            { 
                if (GroupStyle.IsAlternationCountSet)
                {
                    alternationCount = GroupStyle.AlternationCount;
                } 
                else if (_parent != null)
                { 
                    alternationCount = _parent._alternationCount; 
                }
                else 
                {
                    alternationCount = Host.AlternationCount;
                }
            } 
            else
            { 
                alternationCount = Host.AlternationCount; 
            }
 
            ChangeAlternationCount(alternationCount);
        }

        // should the given group be hidden? 
        bool ShouldHide(CollectionViewGroup group)
        { 
            return  GroupStyle.HidesIfEmpty &&      // user asked to hide 
                    group.ItemCount == 0;           // group is empty
        } 

        // create an empty-group placeholder item
        void AddEmptyGroupItem(CollectionViewGroup group)
        { 
            EmptyGroupItem emptyGroupItem = new EmptyGroupItem();
 
            LinkContainerToItem(emptyGroupItem, group); 

            emptyGroupItem.SetGenerator(new ItemContainerGenerator(this, emptyGroupItem)); 

            // add it to the list of placeholder items (this keeps it from being GC'd)
            if (_emptyGroupItems == null)
                _emptyGroupItems = new ArrayList(); 
            _emptyGroupItems.Add(emptyGroupItem);
        } 
 
        // notification that a subgroup has become non-empty
        void OnSubgroupBecameNonEmpty(EmptyGroupItem groupItem, CollectionViewGroup group) 
        {
            // Discard placeholder container.
            UnlinkContainerFromItem(groupItem, group);
            if (_emptyGroupItems != null) 
                _emptyGroupItems.Remove(groupItem);
 
            // inform layout as if the group just got added 
            if (ItemsChanged != null)
            { 
                GeneratorPosition position = PositionFromIndex(Items.IndexOf(group));
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Add, position, 1, 0));
            }
        } 

        // notification that a subgroup has become empty 
        void OnSubgroupBecameEmpty(CollectionViewGroup group) 
        {
            if (ShouldHide(group)) 
            {
                GeneratorPosition position = PositionFromIndex(Items.IndexOf(group));

                // if the group is realized, un-realize it and notify layout 
                if (position.Offset == 0 && position.Index >= 0)
                { 
                    // un-realize 
                    ((IItemContainerGenerator)this).Remove(position, 1);
 
                    // inform layout as if the group just got removed
                    if (ItemsChanged != null)
                    {
                        ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Remove, position, 1, 1)); 
                    }
 
                    // create the placeholder 
                    AddEmptyGroupItem(group);
                } 
            }
        }

        // convert an index (into Items) into a GeneratorPosition 
        GeneratorPosition PositionFromIndex(int itemIndex)
        { 
            GeneratorPosition position; 
            ItemBlock itemBlock;
            int offsetFromBlockStart; 

            GetBlockAndPosition(itemIndex, out position, out itemBlock, out offsetFromBlockStart);

            return position; 
        }
 
 
        void GetBlockAndPosition(object item, int itemIndex, bool deletedFromItems, out GeneratorPosition position, out ItemBlock block, out int offsetFromBlockStart, out int correctIndex)
        { 
            if (itemIndex >= 0)
            {
                GetBlockAndPosition(itemIndex, out position, out block, out offsetFromBlockStart);
                correctIndex = itemIndex; 
            }
            else 
            { 
                GetBlockAndPosition(item, deletedFromItems, out position, out block, out offsetFromBlockStart, out correctIndex);
            } 
        }


        void GetBlockAndPosition(int itemIndex, out GeneratorPosition position, out ItemBlock block, out int offsetFromBlockStart) 
        {
            position = new GeneratorPosition(-1, 0); 
            block = null; 
            offsetFromBlockStart = itemIndex;
 
            if (_itemMap == null || itemIndex < 0)
                return;

            int containerIndex = 0; 

            for (block = _itemMap.Next;  block != _itemMap;  block = block.Next) 
            { 
                if (offsetFromBlockStart >= block.ItemCount)
                { 
                    // item belongs to a later block, increment the containerIndex
                    containerIndex += block.ContainerCount;
                    offsetFromBlockStart -= block.ItemCount;
                } 
                else
                { 
                    // item belongs to this block.  Determine the container index and offset 
                    if (block.ContainerCount > 0)
                    { 
                        // block has realized items
                        position = new GeneratorPosition(containerIndex + offsetFromBlockStart, 0);
                    }
                    else 
                    {
                        // block has unrealized items 
                        position = new GeneratorPosition(containerIndex-1, offsetFromBlockStart+1); 
                    }
 
                    break;
                }
            }
        } 

        void GetBlockAndPosition(object item, bool deletedFromItems, out GeneratorPosition position, out ItemBlock block, out int offsetFromBlockStart, out int correctIndex) 
        { 
            correctIndex = 0;
            int containerIndex = 0; 
            offsetFromBlockStart = 0;
            int deletionOffset = deletedFromItems ? 1 : 0;
            position = new GeneratorPosition(-1, 0);
 
            for (block = _itemMap.Next;  block != _itemMap;  block = block.Next)
            { 
                UnrealizedItemBlock uib; 
                RealizedItemBlock rib = block as RealizedItemBlock;
 
                if (rib != null)
                {
                    // compare realized items with item for which we are searching
                    offsetFromBlockStart = rib.OffsetOfItem(item); 
                    if (offsetFromBlockStart >= 0)
                    { 
                        position = new GeneratorPosition(containerIndex + offsetFromBlockStart, 0); 
                        correctIndex += offsetFromBlockStart;
                        break; 
                    }
                }
                else if ((uib = block as UnrealizedItemBlock) != null)
                { 
                    // if the item isn't realized, we can't find it
                    // directly.  Instead, look for indirect evidence that it 
                    // belongs to this block by checking the indices of 
                    // nearby realized items.
 
#if DEBUG
                    // Sanity check - make sure data structure is OK so far.
                    rib = block.Prev as RealizedItemBlock;
                    if (rib != null && rib.ContainerCount > 0) 
                    {
                        Debug.Assert(Object.Equals(rib.ItemAt(rib.ContainerCount - 1), 
                                                    Items[correctIndex - 1]), 
                                    "Generator data structure is corrupt");
                    } 
#endif

                    bool itemIsInCurrentBlock = false;
                    rib = block.Next as RealizedItemBlock; 
                    if (rib != null && rib.ContainerCount > 0)
                    { 
                        // if the index of the next realized item is off by one, 
                        // the deleted item likely comes from the current
                        // unrealized block. 
                        itemIsInCurrentBlock =
                                Object.Equals(rib.ItemAt(0),
                                    Items[correctIndex + block.ItemCount - deletionOffset]);
                    } 
                    else if (block.Next == _itemMap)
                    { 
                        // similarly if we're at the end of the list and the 
                        // overall count is off by one, or if the current block
                        // is the only block, the deleted item likely 
                        // comes from the current (last) unrealized block
                        itemIsInCurrentBlock = block.Prev == _itemMap ||
                            (Items.Count == correctIndex + block.ItemCount - deletionOffset);
                    } 

                    if (itemIsInCurrentBlock) 
                    { 
                        // we don't know where it is in this block, so assume
                        // it's the very first item. 
                        offsetFromBlockStart = 0;
                        position = new GeneratorPosition(containerIndex-1, 1);
                        break;
                    } 
                }
 
                correctIndex += block.ItemCount; 
                containerIndex += block.ContainerCount;
            } 

            if (block == _itemMap)
            {
                // There's no way of knowing which unrealized block it belonged to, so 
                // the data structure can't be updated correctly.  Sound the alarm.
                throw new InvalidOperationException(SR.Get(SRID.CannotFindRemovedItem)); 
            } 
        }
 

        private void LinkContainerToItem(DependencyObject container, object item)
        {
            LinkContainerToItem(container, item, false); 
        }
 
        // establish the link from the container to the corresponding item 
        static void LinkContainerToItem(DependencyObject container, object item, bool isRecycled)
        { 
            // always set the ItemForItemContainer property
            container.ClearValue(ItemForItemContainerProperty);
            container.SetValue(ItemForItemContainerProperty, item);
 
            // for non-direct items, set the DataContext property
            if (container != item) 
            { 
                if (!isRecycled)
                { 
                    // We already cleared recycled containers in UnlinkContainerFromItem
                    container.ClearValue(FrameworkElement.DataContextProperty);
                }
                container.SetValue(FrameworkElement.DataContextProperty, item); 
            }
        } 
 
        private void UnlinkContainerFromItem(DependencyObject container, object item)
        { 
            UnlinkContainerFromItem(container, item, false);
        }

        // unlink the container from the corresponding item 
        private void UnlinkContainerFromItem(DependencyObject container, object item, bool isRecycled)
        { 
            container.ClearValue(ItemForItemContainerProperty); 

            // There are two ways to view the properties set by PrepareItemContainer: 
            //
            //  a) these properties are added by the generator/host so that
            //      the container can function correctly in the generated tree.
            // 
            //  b) these properties are part of the container's initial state,
            //      independent of whether the container belongs to the tree. 
            // 
            // If you take the first point of view, then the generator should remove
            // these properties when the container is removed from the tree.  If 
            // you take the second point of view, then the generator should not do this.
            //
            // In response to bug 1445288 and independent discussions, we take the
            // second point of view.  This saves the cost of clearing all those 
            // properties, which can add up to quite a lot.  As long as no one expects
            // to use a container after it has been removed, there should be no harm. 
            // 
            // We make a small exception for the ItemForItemContainer property, since
            // that is an internal property that only makes sense for an active container. 
            //
            // When we're in Recycling mode, the above doesn't apply; we need to clear off
            // the DataContext property on the container since it will get re-used.  The
            // issue here is that if we don't clear it off we can alias DataContexts;  we 
            // could get a container on the recycled list with the same DataContext as a
            // live container -- that causes all sorts of subtle issues. 
            // 

            if (isRecycled && container != item) 
            {
                // ClearValue has a perf problem because the DataContext will be inherited by the recycled container's
                // parent.  That will cause us to resolve a binding that we really don't care about.  This can be insanely expensive
                // depending on the structure of the data. 
                //
                // In the rare case that the DataContext property has an expression on it we have to do ClearValue to get rid of it 
                // so that the SetValue later in LinkContainerToItem will work. 

                DependencyProperty dp = FrameworkElement.DataContextProperty; 
                EntryIndex entryIndex = container.LookupEntry(dp.GlobalIndex);

                if (container.HasExpression(entryIndex, dp))
                { 
                    container.ClearValue(dp);
                } 
                else 
                {
                    container.SetValue(dp, null); 
                }
            }

            _host.ClearContainerForItem(container, item); 
        }
 
        ///  
        /// Handle events from the centralized event table
        ///  
        bool IWeakEventListener.ReceiveWeakEvent(Type managerType, object sender, EventArgs e)
        {
            if (managerType == typeof(PropertyChangedEventManager))
            { 
                PropertyChangedEventArgs pce = (PropertyChangedEventArgs)e;
                if (sender == GroupStyle) 
                { 
                    if (pce.PropertyName == "Panel")
                    { 
                        OnPanelChanged();
                    }
                    else
                    { 
                        OnRefresh();
                    } 
                } 
            }
            else if (managerType == typeof(CollectionChangedEventManager)) 
            {
                OnCollectionChanged(sender, (NotifyCollectionChangedEventArgs)e);
            }
            else 
            {
                return false;       // unrecognized event 
            } 

            return true; 
        }

        void ValidateAndCorrectIndex(object item, ref int index)
        { 
            if (index >= 0)
            { 
                // this check is expensive - Items[index] potentially iterates through 
                // the collection.  So trust the sender to tell us the truth in retail bits.
                Debug.Assert(Object.Equals(item, Items[index]), "Event contains the wrong index"); 
            }
            else
            {
                index = Items.IndexOf(item); 
                if (index < 0)
                    throw new InvalidOperationException(SR.Get(SRID.CollectionAddEventMissingItem, item)); 
            } 
        }
 
        /// 
        /// Forward a CollectionChanged event
        /// 
        // Called  when items collection changes. 
        void OnCollectionChanged(object sender, NotifyCollectionChangedEventArgs args)
        { 
            // get the affected item 
            object item;
            int startingIndex = -1; 
            switch (args.Action)
            {
                case NotifyCollectionChangedAction.Add:
                case NotifyCollectionChangedAction.Remove: 
                    if (sender != Items)
                        return;     // ignore events from ItemsCollection when we're listening to group's items. 
 

                    if (args.Action == NotifyCollectionChangedAction.Add) 
                    {
                        if (args.NewItems.Count != 1)
                            throw new NotSupportedException(SR.Get(SRID.RangeActionsNotSupported));
                        item = args.NewItems[0]; 
                        startingIndex = args.NewStartingIndex;
                    } 
                    else 
                    {
                        if (args.OldItems.Count != 1) 
                            throw new NotSupportedException(SR.Get(SRID.RangeActionsNotSupported));
                        item = args.OldItems[0];
                        startingIndex = args.OldStartingIndex;
                    } 
                    break;
 
                case NotifyCollectionChangedAction.Replace: 
                case NotifyCollectionChangedAction.Move:
                case NotifyCollectionChangedAction.Reset: 
                    item = null;
                    break;

                default: 
                    throw new NotSupportedException(SR.Get(SRID.UnexpectedCollectionChangeAction, args.Action));
            } 
 
            if (_traceLog != null)
                _traceLog.Add("Received collection change from {0}  action = {1}  item={2}", 
                            TraceLog.IdFor(sender), args.Action, item);

            switch (args.Action)
            { 
                case NotifyCollectionChangedAction.Add:
                    OnItemAdded(item, startingIndex); 
                    break; 

                case NotifyCollectionChangedAction.Remove: 
                    OnItemRemoved(item, startingIndex);
                    break;

                case NotifyCollectionChangedAction.Replace: 
                    OnItemReplaced(args.OldItems[0], args.NewItems[0], args.NewStartingIndex);
                    break; 
                case NotifyCollectionChangedAction.Move: 
                    OnItemMoved(args.OldItems[0], args.OldStartingIndex, args.NewStartingIndex);
                    break; 


                case NotifyCollectionChangedAction.Reset:
                    OnRefresh(); 
                    break;
            } 
        } 

        // Called when an item is added to the items collection 
        void OnItemAdded(object item, int index)
        {
            ValidateAndCorrectIndex(item, ref index);
 
            GeneratorPosition position = new GeneratorPosition(-1,0);
 
            // find the block containing the new item 
            ItemBlock block = _itemMap.Next;
            int offset = index; 
            while (block != _itemMap && offset >= block.ItemCount)
            {
                offset -= block.ItemCount;
                position.Index += block.ContainerCount; 
                block = block.Next;
            } 
 
            position.Offset = offset + 1;
 
            // if it's an unrealized block, add the item by bumping the count
            UnrealizedItemBlock uib = block as UnrealizedItemBlock;
            if (uib != null)
            { 
                MoveItems(uib, offset, 1, uib, offset+1, 0);
                ++ uib.ItemCount; 
            } 

            // if the item can be added to a previous unrealized block, do so 
            else if ((offset == 0 || block == _itemMap) &&
                    ((uib = block.Prev as UnrealizedItemBlock) != null))
            {
                ++ uib.ItemCount; 
            }
 
            // otherwise, create a new unrealized block 
            else
            { 
                uib = new UnrealizedItemBlock();
                uib.ItemCount = 1;

                // split the current realized block, if necessary 
                RealizedItemBlock rib;
                if (offset > 0 && (rib = block as RealizedItemBlock) != null) 
                { 
                    RealizedItemBlock newBlock = new RealizedItemBlock();
                    MoveItems(rib, offset, rib.ItemCount - offset, newBlock, 0, offset); 
                    newBlock.InsertAfter(rib);
                    position.Index += block.ContainerCount;
                    position.Offset = 1;
                    block = newBlock; 
                }
 
                uib.InsertBefore(block); 
            }
 
            if (_traceLog != null)
                _traceLog.Add("OnItemAdded {0} index = {1}", TraceLog.IdFor(item), index);

            // tell generators what happened 
            if (MapChanged != null)
            { 
                MapChanged(null, index, +1, null, 0, 0); 
            }
 
            // tell layout what happened
            if (ItemsChanged != null)
            {
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Add, position, 1, 0)); 
            }
        } 
 

        // Called when an item is removed from the items collection 
        void OnItemRemoved(object item, int itemIndex)
        {

            DependencyObject container = null;    // the corresponding container 
            int containerCount = 0;
 
            // search for the deleted item 
            GeneratorPosition position;
            ItemBlock block; 
            int offsetFromBlockStart;
            int correctIndex;
            GetBlockAndPosition(item, itemIndex, true, out position, out block, out offsetFromBlockStart, out correctIndex);
 
            RealizedItemBlock rib = block as RealizedItemBlock;
            if (rib != null) 
            { 
                containerCount = 1;
                container = rib.ContainerAt(offsetFromBlockStart); 
            }

            // remove the item, and remove the block if it's now empty
            MoveItems(block, offsetFromBlockStart + 1, block.ItemCount - offsetFromBlockStart - 1, block, offsetFromBlockStart, 0); 
            --block.ItemCount;
            if (rib != null) 
            { 
                // fix up the alternation index before removing an empty block, while
                // we still have a valid block and offset 
                SetAlternationIndex(block, offsetFromBlockStart, GeneratorDirection.Forward);
            }
            RemoveAndCoalesceBlocksIfNeeded(block);
 
            if (_traceLog != null)
                _traceLog.Add("OnItemRemoved {0} index = {1}", TraceLog.IdFor(item), itemIndex); 
 
            // tell generators what happened
            if (MapChanged != null) 
            {
                MapChanged(null, itemIndex, -1, null, 0, 0);
            }
 
            // tell layout what happened
            if (ItemsChanged != null) 
            { 
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Remove, position, 1, containerCount));
            } 

            // unhook the container.  Do this after layout has (presumably) removed it from
            // the UI, so that it doesn't inherit DataContext falsely.
            if (container != null) 
            {
                UnlinkContainerFromItem(container, item); 
            } 

            // detect empty groups, so they can be hidden if necessary 
            if (Level > 0 && Items.Count == 0)
            {
                GroupItem groupItem = (GroupItem)Peer;
                CollectionViewGroup group = groupItem.ReadLocalValue(ItemForItemContainerProperty) as CollectionViewGroup; 

                // the group could be null if the parent generator has already 
                // unhooked its container 
                if (group != null)
                { 
                    Parent.OnSubgroupBecameEmpty(group);
                }
            }
        } 

        void OnItemReplaced(object oldItem, object newItem, int index) 
        { 
            // search for the replaced item
            GeneratorPosition position; 
            ItemBlock block;
            int offsetFromBlockStart;
            int correctIndex;
            GetBlockAndPosition(oldItem, index, false, out position, out block, out offsetFromBlockStart, out correctIndex); 

            // If the item is in an UnrealizedItemBlock, then this change need not 
            // be made to the _itemsMap as we are replacing an unrealized item with another unrealized 
            // item in the same place.
            RealizedItemBlock rib = block as RealizedItemBlock; 
            if (rib != null)
            {
                DependencyObject container = rib.ContainerAt(offsetFromBlockStart);
 
                // replace the old item with the new one
                rib.RealizeItem(offsetFromBlockStart, newItem, container); 
 
                // hook up the container to the new item
                LinkContainerToItem(container, newItem); 
                _host.PrepareItemContainer(container, newItem);
            }

            if (_traceLog != null) 
                _traceLog.Add("OnItemReplaced {0} index = {1}", TraceLog.IdFor(oldItem), index);
        } 
 
        void OnItemMoved(object item, int oldIndex, int newIndex)
        { 
            DependencyObject container = null;    // the corresponding container
            int containerCount = 0;
            UnrealizedItemBlock uib;
 
            // search for the moved item
            GeneratorPosition position; 
            ItemBlock block; 
            int offsetFromBlockStart;
            int correctIndex; 
            GetBlockAndPosition(item, oldIndex, true, out position, out block, out offsetFromBlockStart, out correctIndex);

            GeneratorPosition oldPosition = position;
 
            RealizedItemBlock rib = block as RealizedItemBlock;
            if (rib != null) 
            { 
                containerCount = 1;
                container = rib.ContainerAt(offsetFromBlockStart); 
            }

            // remove the item, and remove the block if it's now empty
            MoveItems(block, offsetFromBlockStart + 1, block.ItemCount - offsetFromBlockStart - 1, block, offsetFromBlockStart, 0); 
            --block.ItemCount;
            RemoveAndCoalesceBlocksIfNeeded(block); 
 
            //
            // now insert into the new spot. 
            //

            position = new GeneratorPosition(-1,0);
            block = _itemMap.Next; 
            offsetFromBlockStart = newIndex;
            while (block != _itemMap && offsetFromBlockStart >= block.ItemCount) 
            { 
                offsetFromBlockStart -= block.ItemCount;
                if (block.ContainerCount > 0) 
                {
                    position.Index += block.ContainerCount;
                    position.Offset = 0;
                } 
                else
                { 
                    position.Offset += block.ItemCount; 
                }
                block = block.Next; 
            }

            position.Offset += offsetFromBlockStart + 1;
 
            // if it's an unrealized block, add the item by bumping the count
            uib = block as UnrealizedItemBlock; 
            if (uib != null) 
            {
                MoveItems(uib, offsetFromBlockStart, 1, uib, offsetFromBlockStart+1, 0); 
                ++ uib.ItemCount;
            }

            // if the item can be added to a previous unrealized block, do so 
            else if ((offsetFromBlockStart == 0 || block == _itemMap) &&
                    ((uib = block.Prev as UnrealizedItemBlock) != null)) 
            { 
                ++ uib.ItemCount;
            } 

            // otherwise, create a new unrealized block
            else
            { 
                uib = new UnrealizedItemBlock();
                uib.ItemCount = 1; 
 
                // split the current realized block, if necessary
                if (offsetFromBlockStart > 0 && (rib = block as RealizedItemBlock) != null) 
                {
                    RealizedItemBlock newBlock = new RealizedItemBlock();
                    MoveItems(rib, offsetFromBlockStart, rib.ItemCount - offsetFromBlockStart, newBlock, 0, offsetFromBlockStart);
                    newBlock.InsertAfter(rib); 
                    position.Index += block.ContainerCount;
                    position.Offset = 1; 
                    offsetFromBlockStart = 0; 
                    block = newBlock;
                } 

                uib.InsertBefore(block);
            }
 
            if (_traceLog != null)
                _traceLog.Add("OnItemMoved {0} oldIndex = {1}", TraceLog.IdFor(item), oldIndex); 
 
            DependencyObject parent = VisualTreeHelper.GetParentInternal(container);
 
            // tell layout what happened
            if (ItemsChanged != null)
            {
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Move, position, oldPosition, 1, containerCount)); 
            }
 
            // unhook the container.  Do this after layout has (presumably) removed it from 
            // the UI, so that it doesn't inherit DataContext falsely.
            if (container != null) 
            {
                if (parent == null || VisualTreeHelper.GetParentInternal(container) != parent)
                {
                    UnlinkContainerFromItem(container, item); 
                }
                else 
                { 
                    // If the container has the same visual parent as before then that means that
                    // the container was just repositioned within the parent's VisualCollection. 
                    // we don't need to unlink the container, but we do need to re-realize the block.
                    Realize(uib, offsetFromBlockStart, item, container);
                }
            } 

            // fix up the AlternationIndex on containers affected by the move 
            if (_alternationCount > 0) 
            {
                // start with the smaller of the two positions, and proceed forward. 
                // This tends to preserve the AlternatonIndex on containers at the
                // front of the list, as users expect
                int index = Math.Min(oldIndex, newIndex);
                GetBlockAndPosition(index, out position, out block, out offsetFromBlockStart); 
                SetAlternationIndex(block, offsetFromBlockStart, GeneratorDirection.Forward);
            } 
        } 

        // Called when the items collection is refreshed 
        void OnRefresh()
        {
            ((IItemContainerGenerator)this).RemoveAll();
 
            if (_traceLog != null)
                _traceLog.Add("OnRefresh count = {0}", Items.Count); 
 
            // tell layout what happened
            if (ItemsChanged != null) 
            {
                GeneratorPosition position = new GeneratorPosition(0, 0);
                ItemsChanged(this, new ItemsChangedEventArgs(NotifyCollectionChangedAction.Reset, position, 0, 0));
            } 
        }
 
        // this method is here just to avoid the compiler error 
        // error CS0649: Warning as Error: Field '..._traceLog' is never assigned to, and will always have its default value null
        void InitializeTraceLog() 
        {
            _traceLog = new TraceLog(20);
        }
 
        //------------------------------------------------------
        // 
        //  Private Fields 
        //
        //----------------------------------------------------- 

        private TraceLog        _traceLog;
        private Generator       _generator;
        private IGeneratorHost  _host; 
        private ItemBlock       _itemMap;
        private GeneratorStatus _status; 
        private int             _itemsGenerated; 
        private int             _startIndexForUIFromItem;
        private DependencyObject _peer; 
        private int             _level;
        private IList           _items;
        private GroupStyle      _groupStyle;
        private ItemContainerGenerator _parent; 
        private ArrayList       _emptyGroupItems;
        private int             _alternationCount; 
 
        private Type            _containerType;     // type of containers on the recycle queue
        private Queue _recyclableContainers = new Queue(); 

        event MapChangedHandler MapChanged;

        delegate void MapChangedHandler(ItemBlock block, int offset, int count, 
                    ItemBlock newBlock, int newOffset, int deltaCount);
 
#if GENERATOR_TRACE 
        MS.Internal.Utility.HFTimer _timer = new MS.Internal.Utility.HFTimer();
        MS.Internal.Utility.HFTimer _creationTimer = new MS.Internal.Utility.HFTimer(); 
#endif

        //------------------------------------------------------
        // 
        //  Private Nested Classes
        // 
        //----------------------------------------------------- 

        // The ItemContainerGenerator uses the following data structure to maintain 
        // the correspondence between items and their containers.  It's a doubly-linked
        // list of ItemBlocks, with a sentinel node serving as the header.
        // Each node maintains two counts:  the number of items it holds, and
        // the number of containers. 
        //
        // There are two kinds of blocks - one holding only "realized" items (i.e. 
        // items that have been generated into containers) and one holding only 
        // unrealized items.  The container count of a realized block is the same
        // as its item count (one container per item);  the container count of an 
        // unrealized block is zero.
        //
        // Unrealized blocks can hold any number of items.  We only need to know
        // the count.  Realized blocks have a fixed-sized array (BlockSize) so 
        // they hold up to that many items and their corresponding containers.  When
        // a realized block fills up, it inserts a new (empty) realized block into 
        // the list and carries on. 
        //
        // This data structure was chosen with virtualization in mind.  The typical 
        // state is a long block of unrealized items (the ones that have scrolled
        // off the top), followed by a moderate number (<50?) of realized items
        // (the ones in view), followed by another long block of unrealized items
        // (the ones that have not yet scrolled into view).  So the list will contain 
        // an unrealized block, followed by 3 or 4 realized blocks, followed by
        // another unrealized block.  Fewer than 10 blocks altogether, so linear 
        // searching won't cost that much.  Thus we don't need a more sophisticated 
        // data structure.  (If profiling reveals that we do, we can always replace
        // this one.  It's totally private to the ItemContainerGenerator and its 
        // Generators.)

        // represents a block of items
        private class ItemBlock 
        {
            public const int BlockSize = 16; 
 
            public int ItemCount { get { return _count; } set { _count = value; } }
            public ItemBlock Prev { get { return _prev; } set { _prev = value; } } 
            public ItemBlock Next { get { return _next; } set { _next = value; } }

            public virtual int ContainerCount { get { return Int32.MaxValue; } }
            public virtual DependencyObject ContainerAt(int index) { return null; } 
            public virtual object ItemAt(int index) { return null; }
 
            public void InsertAfter(ItemBlock prev) 
            {
                Next = prev.Next; 
                Prev = prev;

                Prev.Next = this;
                Next.Prev = this; 
            }
 
            public void InsertBefore(ItemBlock next) 
            {
                InsertAfter(next.Prev); 
            }

            public void Remove()
            { 
                Prev.Next = Next;
                Next.Prev = Prev; 
            } 

            public void MoveForward(ref GeneratorState state, bool allowMovePastRealizedItem) 
            {
                if (IsMoveAllowed(allowMovePastRealizedItem))
                {
                    state.ItemIndex += 1; 
                    if (++state.Offset >= ItemCount)
                    { 
                        state.Block = Next; 
                        state.Offset = 0;
                        state.Count += ItemCount; 
                    }
                }
            }
 
            public void MoveBackward(ref GeneratorState state, bool allowMovePastRealizedItem)
            { 
                if (IsMoveAllowed(allowMovePastRealizedItem)) 
                {
                    if (--state.Offset < 0) 
                    {
                        state.Block = Prev;
                        state.Offset = state.Block.ItemCount - 1;
                        state.Count -= state.Block.ItemCount; 
                    }
                    state.ItemIndex -= 1; 
                } 
            }
 
            protected virtual bool IsMoveAllowed(bool allowMovePastRealizedItem)
            {
                return allowMovePastRealizedItem;
            } 

            int _count; 
            ItemBlock _prev, _next; 
        }
 
        // represents a block of unrealized (ungenerated) items
        private class UnrealizedItemBlock : ItemBlock
        {
            public override int ContainerCount { get { return 0; } } 

            protected override bool IsMoveAllowed(bool allowMovePastRealizedItem) 
            { 
                return true;
            } 
        }

        // represents a block of realized (generated) items
        private class RealizedItemBlock : ItemBlock 
        {
            public override int ContainerCount { get { return ItemCount; } } 
 
            public override DependencyObject ContainerAt(int index)
            { 
                return _entry[index].Container;
            }

            public override object ItemAt(int index) 
            {
                return _entry[index].Item; 
            } 

            public void CopyEntries(RealizedItemBlock src, int offset, int count, int newOffset) 
            {
                int k;
                // choose which direction to copy so as not to clobber existing
                // entries (in case the source and destination blocks are the same) 
                if (offset < newOffset)
                { 
                    // copy right-to-left 
                    for (k = count - 1;  k >= 0;  --k)
                    { 
                        _entry[newOffset + k] = src._entry[offset + k];
                    }

                    // clear vacated entries, to avoid leak 
                    if (src != this)
                    { 
                        src.ClearEntries(offset, count); 
                    }
                    else 
                    {
                        src.ClearEntries(offset, newOffset - offset);
                    }
                } 
                else
                { 
                    // copy left-to-right 
                    for (k = 0;  k < count;  ++k)
                    { 
                        _entry[newOffset + k] = src._entry[offset + k];
                    }

                    // clear vacated entries, to avoid leak 
                    if (src != this)
                    { 
                        src.ClearEntries(offset, count); 
                    }
                    else 
                    {
                        src.ClearEntries(newOffset + count, offset - newOffset);
                    }
                } 
            }
 
            public void ClearEntries(int offset, int count) 
            {
                for (int i=0; i 0) 
                { 
                    ItemContainerGenerator generator = Generator;
                    generator.ItemsChanged -= new ItemsChangedEventHandler(OnItemsChanged); 
                    generator.Parent.OnSubgroupBecameNonEmpty(this, group);
                }
            }
        } 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK