decal.pas

C++中的STL真的让人爱不释手,如果你使用DELPHI,现在你也有了类似于STL的标准库,还不赶快下载啊!

		// bidirectional
		procedure iretreat(var iterator : DIterator); override;
		procedure iretreatBy(var iterator : DIterator; count : Integer); override;
		function igetAt(const iterator : DIterator; offset : Integer) : PDObject; override;
		procedure iputAt(const iterator : DIterator; offset : Integer; const obj : DObject); override;

		// random
		function iindex(const iterator : DIterator) : Integer; override;
		function iless(const iter1, iter2 : DIterator) : Boolean; override;

		function _at(pos : Integer) : PDObject; override;
		procedure _clear(direct : Boolean); override;

	public
		constructor create; override;
		constructor createWith(compare : Dcomparator); override;
		constructor createSize(size : Integer);
		destructor destroy; override;

		{** Add an object to the array.

			@param	obj				The object to add.

		}
		procedure _add(const obj : DObject); override;

		{** Return an iterator positioned after the last item in the array. }
		function finish : DIterator; override;

		{** Return the maximum number of items that may be placed in the
		array.  This is a theoretical limit. }
		function maxSize : Integer; override;

		{** Return the current number of items in the array. }
		function size : Integer; override;

		{** Return an iterator positioned on the first item in the array.  If
		there are no items in the array, the iterator is positioned atEnd. }
		function start : DIterator; override;

		//
		// DSequence overrides;
		//
    {** Return the item at the specified position.
    @param pos Position of the item to retrieve. }
		function at(pos : Integer) : DObject; override;

    {** Returns a reference to the last item in the array. }
		function backRef : PDObject; override;

    {** Returns a reference to the first item in the array. }
		function frontRef : PDObject; override;

    {** Removes and returns the last item in the array. }
		function popBack : DObject; override;

    {** Removes and returns the first item in the array.  }
		function popFront : DObject; override;

		procedure _pushBack(const obj : DObject); override;
		procedure _pushFront(const obj : DObject); override;

    {** Removes the number of items specified in count, starting with the
    given iterator. }
    function removeAtIter(iter : DIterator; count : Integer) : DIterator; override;

    {** Put an object at a specific place.

     @param 	index 		Position to place the object.  What happens when we have a
     										really long comment?  What does it decide to do?  We are curious
                        about the result of a long description.
     @param		obj				The object to put there. }
		procedure _putAt(index : Integer; const obj : DObject); override;

		//
		// DArray specific
		//
    {** Copy the contents of another array into this one. }
		procedure copy(another : DArray);

		{** Copy the contents of this array into another one. }
		procedure copyTo(another : DArray);

    {** Returns the current blocking factor.  When growing the array, the current array capacity is divided by
    the block factor to determine how many new entries to add.  Block factor
    defaults to 4, so that capacity / 4 entries will be added each time the
		array must be grown. }
    function blockFactor : Integer;

    {** Sets the current blocking factor.  The current capacity will be divided
    by this factor to determine the number of entries to add to the array, when
    expansion is necessary. Block factor must be greater than zero. }
    procedure setBlockFactor(factor : Integer);

		//
		// DVector overrides
		//
		{** Return the number of items the array is capable of holding without
		expanding. }
		function capacity : Integer; override;

		{** Ensure that a certain number of items can be held without expanding
		storage (which can be expensive). It's a good idea to set this when
		you're going to add a large number of items to a container. }
		procedure ensureCapacity(amount : Integer); override;

		{** Inserts  count copies of obj before the object iterator is positioned at. }
		procedure _insertAtIter(iterator : DIterator; const obj : DObject); override;

		{** Inserts an object before the object at position index.
		If the iterator is atEnd, the object will be added at the end. }
		procedure _insertAt(index : Integer; const obj : DObject); override;

		{** Inserts  count copies of obj before the object iterator is positioned at. }
		procedure _insertMultipleAtIter(iterator : DIterator; count : Integer; const obj : DObject); override;

		{** Inserts count copies of obj before the object at position index. }
		procedure _insertMultipleAt(index : Integer; count : Integer; const obj : DObject); override;


		{** Inserts copies of the objects in a given range before the object the
		iterator is over. }
		procedure insertRangeAtIter(iterator : DIterator; _start, _finish : DIterator); override;

		{** Inserts copies of the objects in a given range before the object at position
		index. }
		procedure insertRangeAt(index : Integer; _start, _finish : DIterator); override;

		procedure _remove(const obj : DObject); override;
		procedure removeAt(index : Integer); override;
		procedure removeBetween(_begin, _end : Integer); override;
		procedure _removeWithin(_begin, _end : Integer; const obj : DObject); override;

		procedure setCapacity(amount : Integer); override;

		{** Directly set the number of items being held by this array.  If the
		size is smaller than the current size, the extra items will be cleared
		and eliminated.  If the size is larger, the newly created items will be
		filled with an empty value. }
		procedure setSize(newSize : Integer); virtual;

		{** Minimize the storage required by this container.  The storage used
		will shrink to the smallest possible amount. }
		procedure trimToSize; override;

	end;

  {** Node element for DList class. }
	DListNode = class(DBaseClass)
		next, previous : DListNode;
		obj : DObject;

		constructor Create(const anObj : DObject);
    destructor Destroy; override;
    destructor Kill; virtual;

	end;

  {** Double linked list. The classic data structure -- fast insertion,
  fast deletion, slow searching. }
	DList = class(DSequence)
	protected
		head, tail : DListNode;
    length : Integer;

		procedure _clear(direct : Boolean); override;

	public

  	{** Construct a new DList. }
		constructor Create; override;

    {** Construct a new DList, that uses the specified comparator for operations
    that require comparators. }
		constructor CreateWith(compare : DComparator); override;
		destructor Destroy; override;

    {** Override of DContainer's _add; usually called internally.  Adds the
    specified DObject to the list.  Copies the DObject. }
		procedure _add(const obj : DObject); override;

		procedure _remove(const obj : DObject); override;

    {** Creates a new DList that is a clone of this one, including copies of
    all the items in this list.  If the items are objects, only the pointer
    is copied, not the object itself (shallow copy). }
		// function clone : DContainer; override;

    {** Returns an iterator positioned at the end of this list.  Inserting
    at the iterator will add to the list. }
		function finish : DIterator; override;

    {** Returns the maximum number of elements that can be placed in the list. }
		function maxSize : Integer; override;

    {** Returns the number of items in this list. }
		function Size : Integer; override;

    {** Returns an iterator positioned at the beginning of this list, on the first
		item.  If the iterator has no items in it, it returns an iterator with
    atEnd being true. }
		function start : DIterator; override;

		//
		// DSequence overrides;
		//
    {** Returns a pointer to the last object in the list.  Does not copy the
    object.  The pointer can be derefences to examine its value. }
		function backRef : PDObject; override;

    {** Returns a pointer to the first object in the list.  Does not copy the
    object.  The pointer can be derefences to examine its value. }
		function frontRef : PDObject; override;

    {** Returns the last object in this list, and removes it from the list.
    Note that this is returning a DObject, and as such, the value returned
    must be cleared with ClearDObject if it is not stored in an appropriate
    place. }
		function popBack : DObject; override;

    {** Returns the first object in this list, and removes it from the list.
    Note that this is returning a DObject, and as such, the value returned
    must be cleared with ClearDObject if it is not stored in an appropriate
    place. }
		function popFront : DObject; override;

    {** Adds an object to the end of the list.  Copies the object given. }
		procedure _pushBack(const obj : DObject); override;

    {** Adds an object to the front of the list.  Copies the object given. }
		procedure _pushFront(const obj : DObject); override;

    {** Removes all objects in the list between the two integer positions for
		that are equal to obj. }
		procedure _removeWithin(_begin, _end : Integer; const obj : DObject); override;

    {** Removes count objects beginning at the given iterator. }
    function removeAtIter(iter : DIterator; count : Integer) : DIterator; override;

		//
		// DList specific
		//
    {** Removes all objects between two iterators.  Does not remove under the
    _finish iterator (removes all objects up to but NOT including the _finish
    object. }
		procedure cut(_start, _finish : DIterator); virtual;

    {** Insert an object at the given iterator.  The item the iterator is
    currently positioned at is pushed back.  If an atEnd iterator is passed
    as the location, the object is added to the end (back) of the list. }
		procedure _insertAtIter(iterator : DIterator; const obj : DObject); virtual;

    {** Insert objects at the given iterator.  The item the iterator is
    currently positioned at is pushed back.  If an atEnd iterator is passed
    as the location, the object is added to the end (back) of the list. }
		procedure insertAtIter(iterator : DIterator; objs : array of const); virtual;

    {** Sort this DList, very efficiently. }
    procedure mergeSort; virtual;

    {** Sort this DList, using the specified comparator. }
    procedure mergeSortWith(compare : DComparator); virtual;


	protected

		procedure removeRange(s,f : DListNode); virtual;
		procedure removeNode(node : DListNode); virtual;
    procedure _mergeSort(var s, f : DListNode; compare : DComparator); virtual;

		//
		// Iterator manipulation.
		//
		procedure iadvance(var iterator : DIterator); override;
		function iget(const iterator : DIterator) : PDObject; override;
		function iequals(const iter1, iter2 : DIterator) : Boolean; override;
		procedure iput(const iterator : DIterator; const obj : DObject); override;
    function iremove(const iterator : DIterator) : DIterator; override;

		// bidirectional
		procedure iretreat(var iterator : DIterator); override;

	end;

	////////////////////////////////////////////////////////////////////
	//
	// Internal Red-Black Tree
	//
	////////////////////////////////////////////////////////////////////

  {** Red black tree nodes get colored either red or black.  Surprised? }
	DTreeNodeColor = (tnfBlack, tnfRed);

  {** RBTrees are collections of nodes. }
	DTreeNode = class(DBaseClass)

  public

		pair : DPair;
		left, right, parent : DTreeNode;
		color : DTreeNodeColor;

		constructor Create;
		destructor Destroy; override;
		destructor Kill; virtual;
		constructor CreateWith(const _pair : DPair);
		constructor CreateUnder(const _pair : DPair; _parent : DTreeNode);
		constructor MakeWith(const _pair : DPair; _parent, _left, _right : DTreeNode);

{$IFDEF USEPOOLS}
    class function NewInstance : TObject; override;
    procedure FreeInstance; override;
{$ENDIF}

	end;

  {** Internal class.  Do not use. }
	DRedBlackTree = class(DBaseClass)

	protected

		FContainer : DContainer;
		FHeader : DTreeNode;
		FComparator : DComparator;
		FNodeCount : Integer;
		FInsertAlways : Boolean;

		//
		// Internal functions
		//
		procedure RBInitNil;
		procedure RBIncrement(var node : DTreeNode);
		procedure RBDecrement(var node : DTreeNode);
		function RBMinimum(node : DTreeNode) : DTreeNode;
		function RBMaximum(node : DTreeNode) : DTreeNode;