Stack.d - d-phoenix - Project Hosting on Google Code

‹r100

r124

Source path: svn/ trunk/ source/ system/ collections/ Stack.d

/**
 * 该模块实现了一个泛型Stack
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */
module system.collections.Stack;

import system.Array;
import system.Exception;
import system.collections.ICollection;
import system.collections.IEnumerable;
import system.collections.IEnumerator;


/**
 * 表示泛型版后进先出 (LIFO) 集合。
 */
public class Stack(T) : ICollection!(T), IEnumerable!(T)
{
    private T[] theArray;
    private int topOfStack;
    private int theVersion;

    private const int defaultCapacity = 16;

    /**
     * 初始化 Stack(T) 类的新实例，该实例为空并且具有默认初始容量。
     *
     * Comments: Stack(T)的容量是 Stack(T) 可以容纳的元素数。
     *           当向 Stack(T) 中添加元素时，将通过重新分配内部数组来根据需要自动增大容量。
     *           如果可以估计集合的大小，那么当指定初始容量后，将无需在向 Stack(T) 中添加元素时执行大量的大小调整操作。
     *           可通过调用 trimExcess 来减少容量。
     *           此构造函数的运算复杂度是 O(1)。
     *           默认初始容量是16。
     */
    public this()
    {
        this(defaultCapacity);
    }

    /**
     * 初始化 Stack(T) 类的新实例，该实例为空并且具有指定的初始容量。
     * Params: initialCapacity = Stack(T) 可包含的初始元素数。
     * Comments: ditto。
     */
    public this(int initialCapacity)
    in
    {
        assert(initialCapacity >= 0);
    }
    body
    {
        theArray = new T[initialCapacity];
        topOfStack = -1;
    }

    /**
     * 初始化 Stack(T) 类的新实例，该实例包含从指定的集合中复制的元素并且其容量足以容纳所复制的元素数。
     */
    public this(IEnumerable!(T) collection)
    in
    {
        assert( collection !is null, "Parameter collection can not be null." );
    }
    body
    {
        ICollection!(T) col = cast(ICollection!(T))collection;
        if(col !is null)
        {
            auto size = col.count;
            topOfStack = size-1;
            theArray = new T[size];
            col.toArray( theArray );
        }
        else
        {
            topOfStack = -1;
            theArray = new T[defaultCapacity];
            foreach(i; collection)
            {
                this.push(i);
            }
        }
    }

    /* ************************************************************
     * 实现ICollection(T)接口
     * ************************************************************/

    /**
     * 查看 Stack(T) 是否为空。
     */
    public final bool isEmpty()
    {
        return topOfStack == -1;
    }

    /**
     * 返回 Stack(T) 的元素数。
     */
    public final int count()
    {
        return topOfStack+1;
    }

    /**
     * 查看该集合是否只读。
     */
    public final bool isReadOnly()
    {
        return false;
    }

    /**
     * Throws: NotSupportedException.
     */
    public final bool add(T item)
    {
        throw new NotSupportedException();
    }

    /**
     * Throws: NotSupportedException.
     */
    public final bool remove(T item)
    {
        throw new NotSupportedException();
    }

    /**
     * 从 Stack(T) 中移除所有对象。
     * Comments: count 被设置为零，并且集合中的元素对其他对象的引用也被释放。
     *           容量保持不变。若要重置 Stack(T) 的容量，请调用 trimExcess。
     *           此方法的运算复杂度是 O(n)，其中 n 是 count。
     */
    public final void clear()
    {
        if( theArray !is null )
            Array.clear!(T)(theArray);
        topOfStack = -1;
        theVersion++;
    }

    /**
     * 确定某元素是否在 Stack(T) 中。
     * Params: item = 要在 Stack(T) 中定位的对象。对于引用类型，该值可以为 null。
     * Returns: 如果在 Stack(T) 中找到 item，则为 true；否则为 false。
     * Comments: 此方法使用用于 T（列表中的值的类型）的默认相等比较器 DefaultEqualityComparer(T).getInstance() 来确定相等性。
     *           此方法执行线性搜索；因此，此方法的运算复杂度是 O(n)，其中 n 为 count。

     */
    public final bool contains(T item)
    {
        return theArray !is null && Array.indexOf!(T)(theArray, item) != -1;
    }
    /**
     * 将 Stack(T) 复制到现有一维 Array 中。
     * Comments: 按后进先出的顺序将元素复制到数组，类似于连续调用 Pop 所返回的元素的顺序。
     *           此方法的运算复杂度是 O(n)，其中 n 是 count。
     */
    public final void toArray(T[] array)
    in
    {
        assert( array !is null );
    }
    body
    {
        if( theArray !is null )
        {
            Array.copy!(T)(theArray, array, this.count());
            array.reverse;
        }
    }

    /* *****************************************************************
     * 堆栈特有操作
     * *****************************************************************/
    /**
     * 返回位于 Stack(T) 顶部的对象但不将其移除。
     * Throws: InvalidOperationException，当堆栈为空时。
     * Comments: 此方法类似于 Pop 方法，但 Peek 不修改 Stack(T)。
     *           如果类型 T 是引用类型，则可以在需要时将 null 作为占位符推入到 Stack(T) 中。
     *           此方法的运算复杂度是 O(1)。
     */
    public final T peek()
    {
        if( isEmpty() )
        {
            throw new InvalidOperationException("The stack is a empty.");
        }

        return theArray[topOfStack];
    }
    /**
     * 移除并返回位于 Stack(T) 顶部的对象。
     * Returns: 从 Stack(T) 的顶部移除的对象。
     * Throws: InvalidOperationException，当堆栈为空时。
     */
    public final T pop()
    {
        if( isEmpty() )
        {
            throw new InvalidOperationException("The stack is empty.");
        }


        theVersion++;
        T popped = theArray[topOfStack];
        theArray[topOfStack] = T.init;
        topOfStack--;
        return popped;
    }
    /**
     * 将对象插入 Stack(T) 的顶部。
     * Params: item = 要推入到 Stack(T) 中的对象。对于引用类型，该值可以为 null。
     * Comments: Stack(T) 作为数组来实现。
     *           如果 count 已经等于容量，则会通过自动重新分配内部数组使 Stack(T) 的容量增加，并且在添加新元素之前将现有元素复制到新数组中。
     *           如果类型 T 是引用类型，则可以在需要时将 null 作为占位符推入到 Stack(T) 中。它占用堆栈中的一个槽，并且被当作任意对象一样处理。
     *           如果 count 小于堆栈的容量，则 Push 的运算复杂度是 O(1)。如果需要增加容量以容纳新元素，则 Push 的运算复杂度成为 O(n)，其中 n 为 count。
     */
    public final void push(T item)
    {
        if( topOfStack + 1 == theArray.length)
        {
            int size = topOfStack == -1 ? defaultCapacity : 2 * theArray.length;

			assert(size <= int.max);
			assert(size > 0);

			theArray.length = size;
			
        }
        theVersion++;
        theArray[++topOfStack] = item;
    }
    /**
     * 如果元素数小于当前容量的 90%，将容量设置为 Stack(T) 中的实际元素数。
     * Comments: 如果不向集合中添加新元素，则此方法可用于最小化集合的内存开销。但是，重新分配和复制较大 Stack(T) 的开销可能
     *           很大，因此，如果该列表大于容量的 90%，则 trimExcess 方法将不执行任何操作。这样可以避免为获得相对较少的
     *           收益而产生大量重新分配开销。
     *           此方法的运算复杂度是 O(n)，其中 n 是 count。
     */
    public final void trimExcess()
    {
        if( theArray !is null && this.count() < theArray.length * 0.9 )
        {
            theArray.length = this.count();
        }
        theVersion++;
    }

    /* *****************************************************************
     * 实现IEnumerable(T)接口
     * *****************************************************************/

    public final int opApply(int delegate(ref T value) dg)
    {
        auto scope enumerator = new Enumerator(this);
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
    }

    public final Enumerator getEnumerator()
    {
        return new Enumerator(this);
    }

    /**
     * Throws:
     * 		InvalidOperationException，当在遍历对象时修改了集合。
     */
    public final class Enumerator : IEnumerator!(T)
    {
        private const int NotStarted = -2;
        //this MUST be -1, because we depend on it in move next.
        //we just decr the count, so, 0 - 1 == Finished
        private const int Finished = -1;

        private Stack!(T) parent;
        private int index;
        private int theVersion;

        package this(Stack!(T) stack)
        in
        {
            assert( stack !is null );
        }
        body
        {
            parent = stack;
            index = NotStarted;
            theVersion = stack.theVersion;
        }

         /* ****************************************************************
          * 实现IEnumerator(T)接口
          * ****************************************************************/

        public bool moveNext()
        {
            if( theVersion != parent.theVersion )
                throw new InvalidOperationException("Enumerate failed.");

            if( index == -2 )
                index = parent.count;

            return index != Finished && --index != Finished;
        }

        public T current()
        {
            if( index < 0 )
                throw new InvalidOperationException("This operation can not happen.");

            return parent.theArray[index];
        }

        public void reset()
        {
            if( theVersion != parent.theVersion )
                throw new InvalidOperationException();

            index = NotStarted;
        }
    }
}

unittest
{
    /* **************************************************
     * 测试Stack(T)构造函数
     * **************************************************/
    Stack!(int) stack;
    assert( stack is null );

    try
    {
        stack = new Stack!(int)(null);
    }
    catch(Error error)
    {
        assert(true);
    }

    try
    {
        stack = new Stack!(int)(-1);
    }
    catch(Error error)
    {
        assert(true);
    }

    stack = new Stack!(int)();
    assert( stack !is null );

    /* **************************************************
     * 测试Stack(T)其他函数
     * **************************************************/

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    auto stackII = new Stack!(int)(stack);

    assert( stackII !is null );

    assert( stack.count == 5 );
    assert( stack.contains(5) );

    assert( stackII.count == 5 );
    assert( stackII.contains(5) );

    for(auto i = 5; i>0; i--)
    {
        assert( stack.pop() == i );
    }

    assert( stack.count == 0 );
    assert( stack.isEmpty() );
    assert( stack.isReadOnly() == false );

    int[] array = new int[stackII.count];
    stackII.toArray(array);

    for(auto i = 0; i < stackII.count; i++)
    {
        assert( stackII.pop() == array[i] );
    }

    stackII.push(1);
    stackII.push(2);

    stackII.clear();
    assert( stackII.count == 0 );
    assert( stackII.isEmpty() );


    auto stackIII = new Stack!(int)();
    stackIII.trimExcess();
    assert( stackIII.count == 0 );

    auto stackIV = new Stack!(Object)();
    stackIV.push(null);
    assert( stackIV.contains(null) );
}

Show details Hide details

Change log

r109 by lucifer1...@yeah.net on Nov 24, 2008 Diff

修正 Params 在 D 文档生成时没有参数信息的 Bug 。

Go to:

Project members, sign in to write a code review

Older revisions

r100 by lucifer1...@yeah.net on Nov 19, 2008 Diff

[No log message]

r99 by lucifer1...@yeah.net on Nov 19, 2008 Diff

[No log message]

r96 by lucifer1...@yeah.net on Nov 12, 2008 Diff

[No log message]

All revisions of this file

File info

Size: 12493 bytes, 414 lines

View raw file