|
JX Application Framework
|
#include <JConstHashCursor.h>
Public Member Functions | |
| JConstHashCursor (const JHashTable< V > *table) | |
| JConstHashCursor (const JHashTable< V > *table, const JHashValue hash) | |
| virtual | ~JConstHashCursor () |
| bool | Next () |
| bool | Next (bool(*NextRecordType)(const JHashRecord< V > &), const bool stopOnEmpty) |
| bool | NextFull () |
| bool | NextOpen () |
| bool | NextHash (const bool allowEmpty=false) |
| bool | NextHashOrOpen () |
| bool | NextKey (const bool allowEmpty=false) |
| bool | NextKeyOrOpen () |
| bool | NextMapInsertHash () |
| bool | NextMapInsertKey () |
| void | Reset (const bool clear=false) |
| void | ResetHash (const JHashValue hash) |
| void | ResetKey (const V &value) |
| JHashValue | GetCursorHashValue () const |
| const JHashRecord< V > & | GetRecord () const |
| JHashRecordT::State | GetState () const |
| bool | IsEmpty () const |
| bool | IsDeleted () const |
| bool | IsFull () const |
| JHashValue | GetHashValue () const |
| const V & | GetValue () const |
Protected Member Functions | |
| const JHashTable< V > * | GetTable () const |
| JSize | GetIndex () const |
| void | Step () |
Static Protected Member Functions | |
| static JDualHashValue | DualHash (const JHashValue hash) |
| JConstHashCursor< V >::JConstHashCursor | ( | const JHashTable< V > * | table | ) |
JConstHashCursor is the basic cursor for JHashTable, providing the ability
to step through the hash table appropriately and read entries. As the name
implies, it cannot modify the table; however, it can be used on a const
table. Its subclass JHashCursor can modify its table but may not be used
on a const table.
Usage
A JCore cursor behaves like a JCore iterator, except it isn't safe; if one
cursor modifies a table while another is examining it the second cursor may
well be left in an invalid state. In that regard it is more like a simple
array index. Cursor usage generally fits the following stereotype:
(1) Create a cursor attached to the desired table (or reset an existing one
already attached), (2) call one of its Next... functions in a while loop,
(3) examine each record found in the loop body for some property, and
possibly (4) modify a record and then exit the loop.
For example, to examine all records with a given hash value to find one
to delete:
JHashTable<V> table;
...
JHashCursor<V> cursor(&table, hash);
while ( cursor.NextHash() )
{
V value = cursor.GetValue();
if (value == theRightValue)
{
cursor.Remove();
break;
}
}
The break is important; after modifying the table the cursor might not
be in a valid state and must be reset before using again. This is true
whenever the table is modified for all cursors then attached to it.
Note that the hash value was passed in--presumably the client called the
hash function or already had it on hand. Used as shown, the table calls
neither the hash function nor the comparison function pointers at all and
is an example of purely manual use.
Topics to add:
Need example of use with hash and comparison functions
Allows passing in hash values even when key is also there for efficiency;
don't screw it up.
NextMapInsertHash, NextMapInsertKey backup is dangerous.
Warning about moving records from one table to another with a different
hash function.
Base code generated by Codemill v0.1.0
The version without a hash value or key parameter iterates through the entire table, obviously in no perceptible order. Those which take a hash value or key pointer iterate over all records containing the given hash value or key, and if a key pointer was specified the key to which it points must exist while the cursor is being used (though it need not exist when the cursor is destructed, because the destructor will not reference the pointer).
| JConstHashCursor< V >::JConstHashCursor | ( | const JHashTable< V > * | table, |
| const JHashValue | hash | ||
| ) |
|
virtual |
|
inlinestaticprotected |
The secondary hash function which allows double-hashing.
|
inline |
Returns the hash value that the cursor is currently using. This can be useful for avoiding extra calls to the hash function.
|
inline |
|
inlineprotected |
|
inline |
|
inline |
|
inlineprotected |
|
inline |
|
inline |
|
inline |
|
inline |
| bool JConstHashCursor< V >::Next | ( | ) |
The meaning of copying and assignment of cursors is straightforward; after the the same series of operations with either cursor will have exactly the same behavior and effects as with the other. However, it is easy to get into trouble using cursor copies, since neither cursor knows about the other and changes to and/or by one do not affect the other. For example, after the calls
cursor2 = cursor1; cursor1.NextFull();
cursor2 still points to the original record, not the new one that cursor1 stepped to. After a subsequent
cursor2.NextFull();
they would again point to the same record. More complex behavior occurs when the table is modified. If the above example continues
cursor1.NextFull(); cursor1.Remove(); cursor2.NextFull();
the cursors would not point to the same record because cursor2 will step over the formerly full record that was deleted by cursor1.
In spite of this hazardous complexity it is occasionally crucial to be able to copy cursors, for example to remember a position and then scan on (an example is in the code to do a Set() for a map or associative array). As always, hide your dangerous operations behind opaque interfaces! These functions are the cursor's reason for being. If an appropriate unvisited element remains, advances to the next one and returns true; otherwise, returns false. They only differ in what kinds of elements they seek and which they skip over. Calls to different Next... functions may be freely intermixed with each other without a Reset. The form with no arguments visits all records, regardless of state or hash value.
| bool JConstHashCursor< V >::Next | ( | bool(*)(const JHashRecord< V > &) | NextRecordType, |
| const bool | stopOnEmpty | ||
| ) |
| bool JConstHashCursor< V >::NextFull | ( | ) |
Only visits full records. Will step past kEmpty records, since it is intended for stepping through all records in the hash table.
| bool JConstHashCursor< V >::NextHash | ( | const bool | allowEmpty = false | ) |
Only visits records with the same hash value as was used to initialize the cursor (and so it better have been initialized with a key or hash value).
If the argument is false (the default) NextHash will return false as soon as it steps to an empty record, so the client code never sees the empty record. If true, it will return true for the last time when it steps to an empty record. In either case all subsequent calls will return false.
| bool JConstHashCursor< V >::NextHashOrOpen | ( | ) |
Visits records which are empty or deleted or that are full and have the same hash value as was used to initialize the cursor (and so it better have been initialized with a key or hash value). This strange behavior is needed to implement maps (associative arrays).
| bool JConstHashCursor< V >::NextKey | ( | const bool | allowEmpty = false | ) |
Only visits records with the same key as was used to initialize the cursor (and so it better have been initialized with a key). Naturally, the key whose address was passed in must still exist.
If the argument is false (the default) NextKey will return false as soon as it steps to an empty record, so the client code never sees the empty record. If true, it will return true for the last time when it steps to an empty record. In either case all subsequent calls will return false.
| bool JConstHashCursor< V >::NextKeyOrOpen | ( | ) |
Visits records which are empty or deleted or that are full and have the same key as was used to initialize the cursor (and so it better have been initialized with a key or hash value). This strange behavior is needed to implement maps (associative arrays).
| bool JConstHashCursor< V >::NextMapInsertHash | ( | ) |
FindMapInsertHash finds the next location for a map- or array-style insertion, and is mostly useful for implementing associative arrays, or maps. The resulting behavior is intuitive in action precisely because it is designed to mimic a simple array indexed by the key type, but implementing this behavior in a data structure which has no such intrinsic behavior is somewhat complex complex.
Starting from the current position, it returns true positioned at the first slot that has the hash value the cursor was initialized with (so you better have initialized it with a hash value or key). If it finds no such hash value before the scan terminates (at an empty slot or by wrapping over the entire table), it backs up to the first deleted slot it encountered. If there was no deleted slot, it returns true at the empty slot which stopped the scan; in this case the cursor is finished and will return false on all subsequent calls. If there is no empty slot (which means the table is full, so it shouldn't happen normally) it returns false (and of course is also finished).
A key- rather than hash-based search could be implemented by repeated calls to NextMapInsertHash, but NextMapInsertKey() does the job automatically (if you're using the built-in key comparison facilities, of course).
| bool JConstHashCursor< V >::NextMapInsertKey | ( | ) |
Like NextMapInsertHash(), but stops on key matches rather than hash value matches. Obviously, the table has to have a comparison function, and the cursor must have been initialized with a key.
| bool JConstHashCursor< V >::NextOpen | ( | ) |
Only visits open (empty or deleted) records.
After stopping on an empty record it will not step further on subsequent calls.
| void JConstHashCursor< V >::Reset | ( | const bool | clear = false | ) |
With a boolean argument, true makes the cursor ready for an iteration starting at index zero, stepping by one. If the argument is false (the default) makes ready for a new iteration using the previous parameters (either the same hash value or single-stepping with no hash value).
With a hash value, makes the cursor ready for an iteration starting from the index corresponding to the given hash value, stepping by the dual hash of that hash value.
With a key, the cursor is also ready to use the key-specific functions. However, since it only stores a key reference, the object refered to must exist throughout the entire time the cursor is in use.
The hash and key versions only have different names because C++ can't be trusted to disambiguate pointers and integers.
| void JConstHashCursor< V >::ResetHash | ( | const JHashValue | hash | ) |
| void JConstHashCursor< V >::ResetKey | ( | const V & | value | ) |
|
inlineprotected |
Advances the index by the increment, wrapping to the tablesize. No safety of any kind.
1.9.8