Base abstract class for defining a hierarchical data structure in GCGlib for ordered nodes. It indicates the minimum methods that all data structures with ordered elements must provide. Note that some data structures might provide other interfaces to handle their elements. This interface is different than gcgLISTSTRUCTURE where the elements can be positioned anywhere in the data structure. Some data maps will also need a compare() method which is responsible for comparing any two ordered nodes. More...

#include <gcg.h>

Inheritance diagram for gcgORDEREDSTRUCTURE:

Public Member Functions
virtual gcgORDEREDNODE *	insert (gcgORDEREDNODE *newnode)=0
	Inserts a new entry newnode in the data structure. In general ordered structures require unique keys. However, this requirement can be relaxed by combining ordered data structures with other data structures. In most cases, the data structure only works for unique nodes and they must be mutually different in respect to gcgORDEREDSTRUCTURE::compare() method. Note that this restriction can also be easily broken by adapting the gcgORDEREDSTRUCTURE::compare() method. More...

virtual gcgORDEREDNODE *	search (gcgORDEREDNODE *key)=0
	Retrieves the entry of the data structure that is similar to the key in respect to the gcgORDEREDSTRUCTURE::compare() method. One or multiple attributes of key can be used for data retrieval. The gcgORDEREDSTRUCTURE::compare() method returns zero only for similar nodes of the data structure. If multiple nodes in the data structure are similar to key, then the gcgORDEREDSTRUCTURE::search() will return the first node found. Some data structures require the nodes to be unique. More...

virtual gcgORDEREDNODE *	remove (gcgORDEREDNODE *key)=0
	Removes the entry of the data structure that is similar to the key in respect to the gcgORDEREDSTRUCTURE::compare() method. One or multiple attributes of key can be used for data retrieval and subsequent removal. The gcgORDEREDSTRUCTURE::compare() method returns zero only for similar nodes node in the data structure. If multiple nodes are similar to key, then the first found is removed. Some data structures require the nodes to be unique. More...

virtual int	compare (gcgORDEREDNODE refnode1, gcgORDEREDNODE refnode2)=0
	Method that must be furnished by a specialization of gcgORDEREDSTRUCTURE and is responsible for comparing two gcgORDEREDNODE nodes. This is generally necessary for all tree operations of insertion, retrieval and removal. It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, -1 if refnode1 is smaller or precedes refnode2, or 1 if refnode1 is grater or succeeds refnode2. This virtual method is in the data structure, instead in the ordered node, because this will save a vtable pointer per node in C++. More...

Public Member Functions inherited from gcgCLASS
void *	operator new (size_t size)
	Defines a new operator to be used by instatiations of GCGlib classes instead the global one. More...

void *	operator new (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by instantiations of GCGlib classes instead the global one. Returns a NULL pointer instead of throwing an exception if an error occurs. More...

void *	operator new[] (size_t size)
	Defines a new operator to be used by GCGlib array allocations instead the global one. More...

void *	operator new[] (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by vector allocations instead the global one. More...

void	operator delete (void *p)
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete[] (void *p)
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

void	operator delete[] (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

Detailed Description

Base abstract class for defining a hierarchical data structure in GCGlib for ordered nodes. It indicates the minimum methods that all data structures with ordered elements must provide. Note that some data structures might provide other interfaces to handle their elements. This interface is different than gcgLISTSTRUCTURE where the elements can be positioned anywhere in the data structure. Some data maps will also need a compare() method which is responsible for comparing any two ordered nodes.

Since: 0.04.179

Member Function Documentation

◆ compare()

virtual int gcgORDEREDSTRUCTURE::compare	(	gcgORDEREDNODE *	refnode1,
		gcgORDEREDNODE *	refnode2
	)

pure virtual

Method that must be furnished by a specialization of gcgORDEREDSTRUCTURE and is responsible for comparing two gcgORDEREDNODE nodes. This is generally necessary for all tree operations of insertion, retrieval and removal. It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, -1 if refnode1 is smaller or precedes refnode2, or 1 if refnode1 is grater or succeeds refnode2. This virtual method is in the data structure, instead in the ordered node, because this will save a vtable pointer per node in C++.

Parameters

[in]	refnode1	pointer to a specialized gcgORDEREDNODE object instance that must be compared with refnode2.
[in]	refnode2	pointer to a specialized gcgORDEREDNODE object instance that must be compared with refnode1.

Returns: It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, a negative integer if refnode1 is smaller or precedes refnode2, or a positive integer if refnode1 is grater or succeeds refnode2.

See also: insert(); remove(); search()

Implemented in gcgHASHTABLE.

◆ insert()

virtual gcgORDEREDNODE* gcgORDEREDSTRUCTURE::insert ( gcgORDEREDNODE * newnode )

pure virtual

Inserts a new entry newnode in the data structure. In general ordered structures require unique keys. However, this requirement can be relaxed by combining ordered data structures with other data structures. In most cases, the data structure only works for unique nodes and they must be mutually different in respect to gcgORDEREDSTRUCTURE::compare() method. Note that this restriction can also be easily broken by adapting the gcgORDEREDSTRUCTURE::compare() method.

Parameters

[in] newnode a pointer to a comparable node (gcgORDEREDNODE) to be inserted in the data structure. It is generally an object of a specialization of gcgORDEREDNODE that carries the node information. In data structures that require unique nodes, if a similar node is already in the data structure (the gcgORDEREDSTRUCTURE::compare() method returns zero for an existing node), it returns the pointer of the node in the data structure. The insertion operation might call the gcgORDEREDSTRUCTURE::compare() method several times to correctly position the new node.

Returns: if newnode is similar to an existing node of the data structure that require node unique (the gcgORDEREDSTRUCTURE::compare() method returns zero for an existing node), the method returns the pointer of that node. If newnode is correctly inserted, it returns the pointer newnode. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: compare(); remove(); search()

Implemented in gcgHASHTABLE.

◆ remove()

virtual gcgORDEREDNODE* gcgORDEREDSTRUCTURE::remove ( gcgORDEREDNODE * key )

pure virtual

Removes the entry of the data structure that is similar to the key in respect to the gcgORDEREDSTRUCTURE::compare() method. One or multiple attributes of key can be used for data retrieval and subsequent removal. The gcgORDEREDSTRUCTURE::compare() method returns zero only for similar nodes node in the data structure. If multiple nodes are similar to key, then the first found is removed. Some data structures require the nodes to be unique.

Parameters

[in] key a pointer to a comparable node (gcgORDEREDNODE) that carries the information to be found and removed from the data structure. It is generally an object of a specialization of gcgORDEREDNODE that carries the information to be removed. If a similar node is found in the data structure (the gcgORDEREDSTRUCTURE::compare() method returns zero for an existing node), that node is removed from the data structure and returned. The removed node is NOT deleted. The remove operation might call the gcgORDEREDSTRUCTURE::compare() method several times to find the node before its removal.

Returns: if newnode is similar to an existing node of the data strucuture (the gcgORDEREDSTRUCTURE::compare() method returns zero for an existing node), the method removes that node from the data structure and returns its pointer. The node is NOT deleted by the method. If multiple nodes are similar to key, then the first found is removed and returned. If a similar node was not found or an error occurred, it returns NULL. Check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insert(); search(); compare()

Implemented in gcgHASHTABLE.

◆ search()

virtual gcgORDEREDNODE* gcgORDEREDSTRUCTURE::search ( gcgORDEREDNODE * key )

pure virtual

Retrieves the entry of the data structure that is similar to the key in respect to the gcgORDEREDSTRUCTURE::compare() method. One or multiple attributes of key can be used for data retrieval. The gcgORDEREDSTRUCTURE::compare() method returns zero only for similar nodes of the data structure. If multiple nodes in the data structure are similar to key, then the gcgORDEREDSTRUCTURE::search() will return the first node found. Some data structures require the nodes to be unique.

Parameters

[in] key a pointer to a comparable node (gcgORDEREDNODE) that carries the information to be searched in the data structure. It is generally an object of a specialization of gcgORDEREDNODE that carries the requested information. If a similar node is in the data structure (the gcgORDEREDSTRUCTURE::compare() method returns zero for an existing node), it returns the pointer of that node. The search operation might call the gcgORDEREDSTRUCTURE::compare() method several times to retrieve the node.

Returns: if key is similar to an existing node of the data structure (the gcgORDEREDSTRUCTURE::compare() method returns zero for an existing node), the method returns the pointer of that node. If multiple nodes are similar to key, then the first node found is returned. If a similar node was not found or an error occurred, it returns NULL. Check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem, if any.

See also: insert(); remove(); compare()

Implemented in gcgHASHTABLE.

The documentation for this class was generated from the following file:

M:/Documentos/Projetos/Projetos/GCGlib/src/gcg.h

Public Member Functions

Detailed Description

Member Function Documentation

◆ compare()

◆ insert()

◆ remove()

◆ search()