decal.pas

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

		procedure RBLeftRotate(node : DTreeNode);
		procedure RBRightRotate(node : DTreeNode);
		procedure RBinsert(insertToLeft : Boolean; x,y,z : DTreeNode);
		function RBErase(z : DTreeNode) : DTreeNode;

		function RBInternalInsert(x,y : DTreeNode; const pair : DPair) : Boolean;
		procedure RBInitializeRoot;
		procedure RBInitializeHeader;
		procedure RBInitialize;
		function RBCopyTree(oldNode, parent : DTreeNode) : DTreeNode;
		procedure RBCopy(tree : DRedBlackTree);
		procedure RBEraseTree(node : DTreeNode; direct : Boolean);
		// function key(node : DTreeNode) : DObject;
		// function value(node : DTreeNode) : DObject;

		function StartNode : DTreeNode;
		function EndNode : DTreeNode;

	public

		constructor Create(insideOf : DContainer; always : Boolean; compare : DComparator);
		destructor Destroy; override;

		function start : DIterator;
		function finish : DIterator;

		function empty : Boolean;
		function size : Integer;
		function maxSize : Integer;

		procedure swap(another : DRedBlackTree);

		function insert(const pair : DPair) : Boolean;
		function insertAt(pos : DIterator; const pair : DPair) : Boolean;
		function insertIn(_start, _finish : DIterator) : Boolean;

		procedure erase(direct : Boolean);
		procedure eraseAt(pos : DIterator);
		function eraseKeyN(const obj : DObject; count : Integer) : Integer;
		function eraseKey(const obj : DObject) : Integer;
		function eraseIn(_start, _finish : DIterator) : Integer;

		function find(const obj : DObject) : DIterator;
		function count(const obj : DObject) : Integer;
		function lower_bound(const obj : DObject) : DIterator;
		function upper_bound(const obj : DObject) : DIterator;
		function equal_range(const obj : DObject) : DRange;

	end;

	////////////////////////////////////////////////////////////////////
	//
	// Associative Structures
	//
	////////////////////////////////////////////////////////////////////

	DAssociative = class(DContainer)
	public

		//
		// The following methods need to be overridden by subclasses of
		// DAssociative.
		//
		{** Determine if this map permits duplicates. }
		function allowsDuplicates : Boolean; virtual; abstract;

		{** Return the number of pairs with keys equal to the specified key. }
		// function _count(const key : DObject) : Integer; virtual; abstract;

		{** Return the number of pairs with values equal to the specified value. }
		function _countValues(const value : DObject) : Integer; virtual; abstract;

		{** Retrieve the value for a specified key.  The key must exist in the map. }
		function _getAt(const key : DObject) : DObject; virtual; abstract;

		{** Returns an iterator positioned at the pair with the specified key.
		If the key is not found, the iterator is positioned at the end. }
		function _locate(const key : DObject) : DIterator; virtual; abstract;

		{** Add the specified key, value pair to the map. Copies are made of
		the objects. }
		procedure _putAt(const key, value : DObject); virtual; abstract;

		{** Removes the first count pairs with the specified key. }
		procedure _removeN(const key : DObject; count : Integer); virtual; abstract;

		{** Removes the first pair with the specified value. }
		procedure _removeValueN(const value : DObject; count : Integer); virtual; abstract;

		{** Removes the pair the iterator is pointing to. }
		procedure removeAt(iterator : DIterator); virtual; abstract;

		{** Removes all pairs from start to finish. }
		procedure removeIn(_start, _finish : DIterator); virtual; abstract;

		{** Returns a key oriented iterator positioned at the first pair. }
		function startKey : DIterator; virtual; abstract;


		//
		// These methods are implemented here and subclasses inherit them.
		//
		{** Return the number of pairs with the specified key. Pass only one key. }
		// function count(key : array of const) : Integer; virtual;

		{** Return the number of pairs with values equal to the specified value. }
		function countValues(value : array of const) : Integer; virtual;

		{** Retrieve the value for a specified key.  The key must exist in the map. }
		function getAt(key : array of const) : DObject; virtual;

		{** Returns an iterator positioned at the pair with the specified key.
		If the key is not found, the iterator is positioned at the end. }
		function locate(key : array of const) : DIterator; virtual;

		{** Add an open array of keys and values to the map.  There must be
		the same number of elements in each array.  The first element in the
		key array is matched with the first in the value array; the second with
		the second, and so on. }
		procedure putAt(key, value : array of const); virtual;

		{** Add a key, value pair.  You must pass exactly two items in the const
		array. }
		procedure putPair(pair : array of const); virtual;

		{** Removes the first pair with the specified value. }
		procedure removeValueN(value : array of const; count : Integer); virtual;

		{** Removes all pairs with the specified value. }
		procedure removeValue(value : array of const); virtual;

	end;

	DAssociativeClass = class of DAssociative;

	{** Internal class.  Do not use. }
	DInternalMap = class(DAssociative)

	protected

		tree : DRedBlackTree;

		//
		// 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;
		function igetAt(const iterator : DIterator; offset : Integer) : PDObject; override;
		procedure iputAt(const iterator : DIterator; offset : Integer; const obj : DObject); override;

		procedure MorphIterator(var iterator : DIterator); virtual;

		constructor ProtectedCreate(always_insert : Boolean; compare : DComparator);
		constructor ProtectedDuplicate(another : DInternalMap);

		{** Clears all objects from this map. }
		procedure _clear(direct : Boolean); override;

	public

		//
		// DContainer
		//

		{** Adds an object to this map. }
		procedure _add(const obj : DObject); override;

    {** Clones this map to another one. }
		procedure cloneTo(newContainer : DContainer); override;

    {** Returns an iterator positioned after the last item. }
		function finish : DIterator; override;
    {** Returns the absolute maximum number of items this map can hold. }
		function maxSize : Integer; override;
		{** Returns an iterator positioned at the first pair in the map. }
		function start : DIterator; override;

    {** Returns the number of pairs in this map. }
		function size : Integer; override;

		//
		// Map stuff
		//

    {** Determine if this map permits duplicates. }
		function allowsDuplicates : Boolean; override;

    {** Return the number of pairs with keys equal to the specified key. }
		function _count(const key : DObject) : Integer; override;

    {** Return the number of pairs with values equal to the specified value. }
		function _countValues(const value : DObject) : Integer; override;

    {** Retrieve the value for a specified key.  The key must exist in the map. }
		function _getAt(const key : DObject) : DObject; override;

    {** Returns an iterator positioned at the pair with the specified key.
    If the key is not found, the iterator is positioned at the end. }
    function _locate(const key : DObject) : DIterator; override;

    {** Position an iterator on the first pair that matches or is greater
		than the supplied key. Bound functions are only available on ordered
    map structures. }
		function _lower_bound(const key : DObject) : DIterator;

    {** Position an iterator on the first pair that matches or is greater
		than the supplied key. Bound functions are only available on ordered
    map structures. }
		function lower_bound(obj : array of const) : DIterator;

    {** Position an iterator after the last pair that matches or is less
    than the supplied key. Bound functions are only available on ordered
		map structures. }
		function _upper_bound(const key : DObject) : DIterator;

    {** Position an iterator after the last pair that matches or is less
		than the supplied key. Bound functions are only available on ordered
    map structures. }
    function upper_bound(obj : array of const) : DIterator;

    {** Add the specified key, value pair to the map. Copies are made of
    the objects. }
		procedure _putAt(const key, value : DObject); override;

    {** Removes the all pairs with the specified key. }
		procedure _remove(const key : DObject); override;

    {** Removes the first count pairs with the specified key. }
		procedure _removeN(const key : DObject; count : Integer); override;

    {** Removes the first pair with the specified value. }
		procedure _removeValueN(const value : DObject; count : Integer); override;

		{** Removes the pair the iterator is pointing to. }
		procedure removeAt(iterator : DIterator); override;

    {** Removes all pairs from start to finish. }
		procedure removeIn(_start, _finish : DIterator); override;

		{** Returns a key oriented iterator positioned at the first pair. }
		function startKey : DIterator; override;

		destructor Destroy; override;

	end;

	{** Maps associate a key with a value.  If no comparator is supplied during construction, the hashComparator is
	used...making a hash map. }
	DMap = class(DInternalMap)
	public
		function usesPairs : Boolean; override;
		constructor Create; override;
		constructor CreateWith(compare : DComparator); override;
		constructor CreateFrom(another : DMap);

		// function clone : DContainer; override;
	end;

	{** Multi maps permit a key to appear more than once. }
	DMultiMap = class(DInternalMap)
	public
		function usesPairs : Boolean; override;
		constructor Create; override;
		constructor CreateWith(compare : DComparator); override;
		constructor CreateFrom(another : DMultiMap);

		// function clone : DContainer; override;

	end;

	////////////////////////////////////////////////////////////////////
	//
	// Sets
	//
	////////////////////////////////////////////////////////////////////

	// Sets are implemented in terms of maps.  Sets us the same structure
	// as maps, but the second half of the pair is always empty.
	DSet = class(DInternalMap)

	protected
		procedure MorphIterator(var iterator : DIterator); override;

	public
		constructor Create; override;
		constructor CreateWith(compare : DComparator); override;
		constructor CreateFrom(another : DSet);

		// function clone : DContainer; override;

		procedure _add(const obj : DObject); override;
		procedure _putAt(const key, value : DObject); override;


		{** Returns true if the specified object is in the set.}
		function _includes(const obj : DObject) : Boolean; virtual;
		{** Returns true if ALL the specified objects are in the set. }
		function includes(obj : array of const) : Boolean; virtual;

	end;

	DMultiSet = class(DSet)
		constructor Create; override;
		constructor CreateWith(compare : DComparator); override;
		constructor CreateFrom(another : DMultiSet);

		// function clone : DContainer; override;
	end;

	////////////////////////////////////////////////////////////////////
	//
	// Hash maps
	//
	////////////////////////////////////////////////////////////////////

	DHash = function(const buffer; byteCount : Integer) : Integer of object;
	DHashProc = function(ptr : Pointer; const buffer; byteCount : Integer) : Integer;

	DInternalHash = class(DAssociative)
	protected
		FHash : DHash;
		FStorageClass : DSequenceClass;
		FAllowDups : Boolean;  		// Do we allow duplicates, or do we replace?
		FBuckets : DArray;
		FBuck