/*
 * mkstorage.h --
 *
 *	This file contains the definition of the Metakit driver for
 *	e4Graph. This file defines the class e4_MetakitStorageImpl which
 *	is derived from e4_StorageImpl.
 *
 * Copyright (c) 2000-2003, JYL Software Inc.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE, EVEN IF
 * JYL SOFTWARE INC. IS MADE AWARE OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * Get the definitions from MetaKit. MetaKit is being used as a dependent
 * DLL, so define q4_KITDLL.
 */

#include "mk4.h"
#include "mk4str.h"

/*
 * These constants define the version number of the MK storage driver:
 *
 * The current format version is 1.4:
 */

#define E4_MKSTORAGE_MAJORVER		1
#define E4_MKSTORAGE_MINORVER		4

/*
 * These layout strings describe the format of storage used by e4Graph. The
 * e4Graph format uses several top-level views:
 *
 * e4GraphMarkers	- contains all markers in this storage.
 *			  (removed as of 1.4)
 * e4GraphNodes		- contains all nodes in this storage.
 * e4GraphVertices	- contains all vertices in this storage.
 * e4GraphNames		- contains all marker and vertex names in this storage.
 * e4GraphDoubles	- contains all 64-bit floating point data.
 * e4GraphStrings	- contains all string data in this storage.
 * e4GraphBinary	- contains all binary data in this storage.
 * e4GraphUnused	- contains indices of "unused slot" lists for
 *			  all other views in this storage, as well as
 *			  some metadata and bookkeeping information.
 * e4GraphParents	- contains indices of all parent nodes.
 *
 * Integer data is represented directly in the vertex, in the "row" column.
 */

/*
 * Five versions supported, 1.0, 1.1, 1.2, 1.3 and 1.4:
 */

#define	MK4_GRAPHMARKERS1_0 \
	"e4GraphMarkers[nameID:I,next:I,root:I,used:I,userData:I]"
#define	MK4_GRAPHNODES1_0 \
	"e4GraphNodes[firstVertex:I,lastVertex:I,vertexCount:I,parentID:I," \
		      "used:I,next:I,refCount:I,nodeMarkers:I,userData:I]"
#define MK4_GRAPHVERTICES1_0 \
	"e4GraphVertices[nameID:I,nodeID:I,vertexType:I,row:I,next:I," \
			 "prev:I,used:I,userData:I]"
#define MK4_GRAPHDOUBLES1_0	"e4GraphDoubles[d:D,next:I,used:I]"
#define MK4_GRAPHSTRINGS1_0	"e4GraphStrings[s:S,next:I,used:I]"
#define MK4_GRAPHNAMES1_0	"e4GraphNames[n:S,next:I,used:I]"
#define MK4_GRAPHBINARY1_0	"e4GraphBinary[b:B,next:I,used:I]"
#define MK4_GRAPHUNUSED1_0	"e4GraphUnused[first:I]"
#define MK4_GRAPHPARENTS1_0 \
	"e4GraphParents[nodeID:I,count:I,next:I,used:I]"

#define	MK4_GRAPHMARKERS1_1 \
	"e4GraphMarkers[nameID:I,next:I,root:I,flags:I,userData:I]"
#define	MK4_GRAPHNODES1_1 \
	"e4GraphNodes[firstVertex:I,lastVertex:I,vertexCount:I,parentID:I," \
		      "flags:I,next:I,refCount:I,nodeMarkers:I,userData:I]"
#define MK4_GRAPHVERTICES1_1 \
	"e4GraphVertices[nameID:I,nodeID:I,vertexType:I,row:I,next:I," \
			 "prev:I,flags:I,userData:I]"
#define MK4_GRAPHDOUBLES1_1	"e4GraphDoubles[d:D,next:I,flags:I]"
#define MK4_GRAPHSTRINGS1_1	"e4GraphStrings[s:S,next:I,flags:I]"
#define MK4_GRAPHNAMES1_1	"e4GraphNames[n:S,next:I,flags:I]"
#define MK4_GRAPHBINARY1_1	"e4GraphBinary[b:B,next:I,flags:I]"
#define MK4_GRAPHUNUSED1_1	"e4GraphUnused[first:I]"
#define MK4_GRAPHPARENTS1_1 \
	"e4GraphParents[nodeID:I,count:I,next:I,flags:I]"

#define	MK4_GRAPHMARKERS1_2 \
	"e4GraphMarkers[nameID:I,next:I,root:I,flags:I,userData:I]"
#define	MK4_GRAPHNODES1_2 \
	"e4GraphNodes[firstVertex:I,lastVertex:I,vertexCount:I,parentID:I," \
		      "flags:I,next:I,refCount:I,nodeMarkers:I,userData:I]"
#define MK4_GRAPHVERTICES1_2 \
	"e4GraphVertices[nameID:I,nodeID:I,vertexType:I,row:I,next:I," \
			 "prev:I,nextinparent:I,flags:I,userData:I]"
#define MK4_GRAPHDOUBLES1_2	"e4GraphDoubles[d:D,next:I,flags:I]"
#define MK4_GRAPHSTRINGS1_2	"e4GraphStrings[s:S,next:I,flags:I]"
#define MK4_GRAPHNAMES1_2	"e4GraphNames[n:S,next:I,flags:I]"
#define MK4_GRAPHBINARY1_2	"e4GraphBinary[b:B,next:I,flags:I]"
#define MK4_GRAPHUNUSED1_2	"e4GraphUnused[first:I]"
#define MK4_GRAPHPARENTS1_2 \
	"e4GraphParents[nodeID:I,count:I,next:I,flags:I,vertexchain:I]"

#define	MK4_GRAPHMARKERS1_3 \
	"e4GraphMarkers[nameID:I,next:I,root:I,flags:I,userData:I]"
#define	MK4_GRAPHNODES1_3 \
	"e4GraphNodes[firstVertex:I,lastVertex:I,vertexCount:I,parentID:I," \
		      "flags:I,next:I,refCount:I,nodeMarkers:I,userData:I," \
		      "detachedvertices:I]"
#define MK4_GRAPHVERTICES1_3 \
	"e4GraphVertices[nameID:I,nodeID:I,vertexType:I,row:I,next:I," \
			 "prev:I,nextinparent:I,flags:I,userData:I]"
#define MK4_GRAPHDOUBLES1_3	"e4GraphDoubles[d:D,next:I,flags:I]"
#define MK4_GRAPHSTRINGS1_3	"e4GraphStrings[s:S,next:I,flags:I]"
#define MK4_GRAPHNAMES1_3	"e4GraphNames[n:S,next:I,flags:I]"
#define MK4_GRAPHBINARY1_3	"e4GraphBinary[b:B,next:I,flags:I]"
#define MK4_GRAPHUNUSED1_3	"e4GraphUnused[first:I]"
#define MK4_GRAPHPARENTS1_3 \
	"e4GraphParents[nodeID:I,count:I,next:I,flags:I,vertexchain:I]"

/*
 * As of version 1.4 there is no e4GraphMarkers view:
 */

#define	MK4_GRAPHNODES1_4 \
	"e4GraphNodes[firstVertex:I,lastVertex:I,vertexCount:I,parentID:I," \
		      "flags:I,next:I,refCount:I,userData:I," \
		      "detachedvertices:I]"
#define MK4_GRAPHVERTICES1_4 \
	"e4GraphVertices[nameID:I,nodeID:I,vertexType:I,row:I,next:I," \
			 "prev:I,nextinparent:I,flags:I,userData:I]"
#define MK4_GRAPHDOUBLES1_4	"e4GraphDoubles[d:D,next:I,flags:I]"
#define MK4_GRAPHSTRINGS1_4	"e4GraphStrings[s:S,next:I,flags:I]"
#define MK4_GRAPHNAMES1_4	"e4GraphNames[n:S,next:I,flags:I]"
#define MK4_GRAPHBINARY1_4	"e4GraphBinary[b:B,next:I,flags:I]"
#define MK4_GRAPHUNUSED1_4	"e4GraphUnused[first:I]"
#define MK4_GRAPHPARENTS1_4 \
	"e4GraphParents[nodeID:I,count:I,next:I,flags:I,vertexchain:I]"

/*
 * Version 1.5 is identical to version 1.4 but the size of the e4GraphUnused
 * view changed and the size is used to distinguish whether important data
 * is present, so this necessitates a new version.
 */

#define	MK4_GRAPHNODES1_5 \
	"e4GraphNodes[firstVertex:I,lastVertex:I,vertexCount:I,parentID:I," \
		      "flags:I,next:I,refCount:I,userData:I," \
		      "detachedvertices:I]"
#define MK4_GRAPHVERTICES1_5 \
	"e4GraphVertices[nameID:I,nodeID:I,vertexType:I,row:I,next:I," \
			 "prev:I,nextinparent:I,flags:I,userData:I]"
#define MK4_GRAPHDOUBLES1_5	"e4GraphDoubles[d:D,next:I,flags:I]"
#define MK4_GRAPHSTRINGS1_5	"e4GraphStrings[s:S,next:I,flags:I]"
#define MK4_GRAPHNAMES1_5	"e4GraphNames[n:S,next:I,flags:I]"
#define MK4_GRAPHBINARY1_5	"e4GraphBinary[b:B,next:I,flags:I]"
#define MK4_GRAPHUNUSED1_5	"e4GraphUnused[first:I]"
#define MK4_GRAPHPARENTS1_5 \
	"e4GraphParents[nodeID:I,count:I,next:I,flags:I,vertexchain:I]"

/*
 * These constants define indices into the e4GraphUnused view, used for storing
 * the unused-list indices for each kind of unused slot list and various
 * other globally accessible entities such as the root node in a storage.
 */

#define MK4_GRAPHSTORAGEMAJORVER	0
#define MK4_GRAPHSTORAGEMINORVER	1
#define	MK4_GRAPHFIRSTUNUSEDMARKER	2
#define MK4_GRAPHFIRSTUNUSEDNODE	3
#define MK4_GRAPHFIRSTUNUSEDVERTEX	4
#define MK4_GRAPHFIRSTUNUSEDDOUBLE	5
#define MK4_GRAPHFIRSTUNUSEDSTRING	6
#define MK4_GRAPHFIRSTUNUSEDBINARY	7
#define MK4_GRAPHFIRSTUNUSEDNAME	8
#define MK4_GRAPHFIRSTUNUSEDPARENT	9
#define MK4_GRAPHHASHCODE		10
#define MK4_GRAPHUNREACHABLENODES	11
/*
 * Slot 12 is unused. We cannot reuse it or we'd introduce an incompatibility
 * between future storage formats and the layout used in format 1.4.
 */
#define MK4_GRAPHUNUSEDSLOT0		12
#define MK4_GRAPHROOTNODE		13
/*
 * New sots introduced in format 1.5.
 */
#define MK4_GRAPHE4GRAPHMAJORVERSION	14
#define MK4_GRAPHE4GRAPHMINORVERSION	15
#define MK4_GRAPHE4GRAPHRELSTATUS	16
#define MK4_GRAPHE4GRAPHRELITER		17

/*
 * This constant defines the size of the e4GraphUnused view.
 */

#define MK4_GRAPHUNUSEDSIZE_1_4		20
#define MK4_GRAPHUNUSEDSIZE_1_5		25

/*
 * Increment size for general views:
 */

#define MK4_GRAPHINCREMENT	128

/*
 * Increment size for the vertices view:
 */

#define MK4_VERTICESINCREMENT	128

/*
 * The e4_MetakitStorageImpl class:
 */

class e4_MetakitStorageImpl: public e4_StorageImpl 
{
    /*
     *=========================================================================
     *
     * Methods declared below this header are part of the implementation,
     * not part of the storage driver interface:
     *
     *=========================================================================
     */

public:

    /*
     * The default constructor is public. It throws an exception to prevent
     * direct construction of instances.
     */

    e4_MetakitStorageImpl();

    /*
     * The destructor:
     */

    virtual ~e4_MetakitStorageImpl();
    
    /*
     * This method is called to create a new instance of
     * e4_MetakitStorageImpl.
     */

    static e4_StorageImpl *GetStorage(const char *fname,
				      int state,
				      int pps);

    /*
     * This method is called to get version info about the
     * version of e4Graph that wrote this storage.
     */

    static bool GetVersionInfo(const char *fname,
			       int &maj,
			       int &min,
			       e4_ReleaseStatus &rs,
			       int &ri);

private:
    c4_Storage *storage;		/* The actual MetaKit storage. */
    c4_View parents;			/* Cached view of the parents
					 * of all nodes in this storage. */
    c4_View markers;			/* Cached view of the markers
                                         * in this storage.
					 *
					 * NOTE: We keep this view because
					 * we may need to convert storages
					 * from an older format to 1.4 or
					 * later. */    
    c4_View nodes;			/* Cached view of the nodes
                                         * in this storage. */
    c4_View vertices;			/* Cached view of the vertices
                                         * in this storage. */
    c4_View doubles;			/* This view contains the
                                         * values for all double-valued
                                         * vertices in this storage. */
    c4_View strings;			/* This view contains the
                                         * values of all string
                                         * vertices in this storage. */
    c4_View names;			/* This view contains all
                                         * the strings used as
                                         * vertex names in this storage. */
    c4_View binary;			/* This view contains the
                                         * values of all binary
                                         * vertices in this storage. */
    c4_View unused;			/* This view contains the values of
                                         * all unused-list indices for
                                         * this storage. */

    int statistics[(int) E4_SPLAST][(int) E4_SSLAST];
					/* Space for collecting statistics. */

    /*
     * Storage used for deletion mechanism:
     */

    e4_IntStack *idStack1, *idStack2;

    /*
     * Is GC needed?
     */

    bool needsGC;

    e4_MetakitStorageImpl(const e4_MetakitStorageImpl &);
					/* Copy constructor cannot be
					 * called either. */
    void operator= (const e4_MetakitStorageImpl *);
					/* Nor assignment. */


    /*
     * GC mechanism:
     */

    void InitGC();
    void SpanReachableNodes();
    void SeedReachableNodesFromReferencedNodes();
    void SeedReachableNodesFromReferencedVertices();
    void SpanSeededNodes();

    void CollectUnreachableEntities();
    void RecycleUnreachableVertexValues();
    void CollectUnreachableNodes();
    void CollectUnreachableVertices();

    /*
     * Fire detach events for newly detached entites, after a GC.
     */

    void FireEventsForNewlyDetached();
    void FireEventsForNewlyDetachedNodes();
    void FireEventsForNewlyDetachedVertices();

    /*
     * Increase the size of various resources:
     */

    void MakeParentSpace();
    void MakeNodeSpace();
    void MakeVertexSpace();
    void MakeDoubleSpace();
    void MakeStringSpace();
    void MakeBinarySpace();
    void MakeNameSpace();

    /*
     * Recycle storage for a parent.
     */

    void UnusedParent(int i);

    /*
     * These operations free up a previously used item given the unique
     * identifier for the item. The operations return true if the item
     * was successfully freed.
     */

    bool FreeDouble(int index);
    bool FreeString(int index);
    bool FreeBinary(int index);

    /*
     * These methods are helpers that implement different methods to visit
     * vertices in a storage:
     */

    e4_VertexImpl *FindNextVertexStorage(int vertexID, int vf, int nameID,
					 e4_VertexType ft) const;
    e4_VertexImpl *FindNextVertexNode(int VertexID, int vf, int nameID,
				      e4_VertexType ft, int nodeID) const;
    e4_VertexImpl *FindNextVertexNodeRandom(int vertexID, int vf, int nameID,
					    e4_VertexType ft, int nodeID)
	const;
    e4_VertexImpl *FindNextVertexParent(int vertexID, int nameID, int nodeID,
					int parentID, e4_DetachChoice dc)
	const;

    e4_VertexImpl *FindNextVertexStorageNone(int vertexID) const;
    e4_VertexImpl *FindNextVertexStorageName(int vertexID, int nameID) const;
    e4_VertexImpl *FindNextVertexStorageType(int vertexID, e4_VertexType ft) 
	const;
    e4_VertexImpl *FindNextVertexStorageBoth(int vertexID, int nameID,
					     e4_VertexType ft) const;

    e4_VertexImpl *FindNextVertexNodeNone(int vertexID, int nodeID) const;
    e4_VertexImpl *FindNextVertexNodeName(int vertexID, int nameID,
					  int nodeID) const;
    e4_VertexImpl *FindNextVertexNodeType(int vertexID, e4_VertexType ft,
					  int nodeID) const;
    e4_VertexImpl *FindNextVertexNodeBoth(int vertexID, int nameID,
					  e4_VertexType ft, int nodeID) const;

    e4_VertexImpl *FindNextVertexNRNone(int vertexID, int nodeID) const;
    e4_VertexImpl *FindNextVertexNRName(int vertexID, int nameID,
					int nodeID) const;
    e4_VertexImpl *FindNextVertexNRType(int vertexID, e4_VertexType ft,
					int nodeID) const;
    e4_VertexImpl *FindNextVertexNRBoth(int vertexID, int nameID,
					e4_VertexType ft, int nodeID) const;

    e4_VertexImpl *FindNextVertexParentDetached(int vertexID, int nameID,
						int nodeID) const;
    e4_VertexImpl *FindNextVertexParentBoth(int vertexID, int nameID,
					    int nodeID) const;
    e4_VertexImpl *FindNextVertexParentSpecific(int vertexID, int nameID,
						int nodeID, int parentID)
      const;
    e4_VertexImpl *FindNextVertexParentAttached(int vertexID, int nameID,
						int nodeID) const;

    int FindNextVertexIndexInNode(int vertexID, int nodeID) const;
    
    /*
     * Populate the name hash table with the known names.
     */

    void PopulateNameHash();
    
    /*
     * Private constructor used by GetStorage.
     */

    e4_MetakitStorageImpl(const char *fname,
			  int state,
			  int pps);
    
    /*
     * Helper functions for moving vertices around.
     */

    void SpliceOut(int vertexID, int newParentID);
    void SpliceIn(int vertexID, int newParent, int vertexAfterID);

#ifdef	NOTDEF
    void SpliceIn(int vertexID, int newParent, int oldParent, int rank);
    int SpliceOut(int vertexID, bool updateChild);
#endif

    /*
     * Compute the total number of slots in a specific space in the storage.
     */

    void UpdateAvailable(e4_Space sp);

    /*
     * Compute the number of slots used in a specific space in the storage.
     */

    void UpdateUsed(e4_Space sp);

    /*
     * Initialize the storage.
     */

    bool Initialize(int state, bool caninit, bool canupdate);

    /*
     * Free the value of a vertex.
     */

    void FreeVertexValue(int vertexID);

    /*
     * Add the node identified by "parentID" to the list of nodes that
     * contain the node identified by "childID".
     */

    void AddParent(int childID, int parentID, int vertexID);

    /*
     * Remove a parent from a node.
     */

    void RemoveParent(int childID, int parentID, int vertexID);
    void RemoveParent(int childID, 
		      int parentID,
		      int vertexID,
		      bool GCOrDetach);

    /*
     * Update the format from 1.0 to 1.1:
     */

    void UpdateFormat1_0to1_1();

    /*
     * Update the format from 1.1 to 1.2:
     */

    void UpdateFormat1_1to1_2();

    /*
     * Update the format from 1.2 to 1.3:
     */

    void UpdateFormat1_2to1_3();

    /*
     * Update the format from 1.3 to 1.4:
     */

    void UpdateFormat1_3to1_4();

    /*
     * Update the format from 1.4 to 1.5:
     */

    void UpdateFormat1_4to1_5();

    /*
     * Clean up any remaining detached entities after the last commit.
     */

    void CleanupDetached();

    /*
     * Add items to each specific free list.
     */

    void UnusedNode(int i);
    void UnusedVertex(int i);
    void UnusedInt(int i);
    void UnusedDouble(int i);
    void UnusedString(int i);
    void UnusedName(int i);
    void UnusedBinary(int i);

    /*
     * Remove the association between a vertex and its node value. Used by
     * the new GC to clean up a vertex thats unreachable when its value is
     * a node that's not known to be unreachable.
     */

    void RemoveNodeVertexAssoc(int nid, int vid);

    /*
     *=========================================================================
     *
     * Methods below this header are part of the storage driver interface.
     * All of them have names starting with 'DRV_':
     *
     *=========================================================================
     */

public:
    
    virtual bool DRV_Commit();
    virtual bool DRV_IsValid() const;
    virtual bool DRV_SetRootNodeID(int nodeID);
    virtual int  DRV_GetRootNodeID();
    virtual bool DRV_IsRootNodeID(int nodeID);

    /*
     * Get a value for a statistic being collected for this storage.
     */

    virtual bool DRV_GetStatistic(e4_Space sp, e4_SpaceStat st, int &v);

    /*
     * Return the hash code for this storage.
     */

    virtual int DRV_HashCode() const;

    /*
     * Do a GC.
     */

    virtual void DRV_DoGC(int reqstate);

    /*
     * Is a GC needed?
     */

    virtual bool DRV_NeedsGC() const;

    /*
     * Set the flag indicating whether GC is needed.
     */

    void DRV_SetNeedsGC(bool needs);

protected:

    /*
     * APIs for support of the new GC:
     */

    virtual void DRV_FreeNode(int i);
    virtual void DRV_FreeVertex(int i);

    /*
     * Mark a node or vertex as having had the detach notify callback
     * delivered.
     */

    virtual void DRV_MarkDetachNotifiedNodeID(int id);
    virtual void DRV_MarkDetachNotifiedVertexID(int id);

    /*
     * Has a detach callback been delivered already for this node or
     * vertex? If not, return true.
     */

    virtual bool DRV_IsNewlyDetachedNodeID(int id);
    virtual bool DRV_IsNewlyDetachedVertexID(int it);

    /*
     * Is the node or vertex identified by the given ID detached?
     */

    virtual bool DRV_IsDetachedNodeID(int id) const;
    virtual bool DRV_IsDetachedVertexID(int id) const;

    /*
     * Count how many vertices there are in a node, given the nodeID.
     */

    virtual int DRV_VertexCountFromNodeID(int nodeID) const;

    /*
     * Count how many vertices in a node with this nodeID have the given
     * name, type or value. If vertexID == E4_VERTEXNOTFOUND then count
     * the total number of vertices with that name, type, or value.
     * Otherwise count up to and including the given vertexID.
     */

    virtual int DRV_VertexCountWithNameIDFromNodeID(int nodeID, 
						    int vertexID,
						    int nameID)
	const;
    virtual int DRV_VertexCountWithTypeFromNodeID(int nodeID,
						  int vertexID,
						  e4_VertexType tp)
	const;
    virtual int DRV_VertexCountWithValueFromNodeID(int nodeID,
						   int vertexID,
						   const e4_Value &v)
	const;

    /*
     * Return true if parentID is the id of a node that is a parent of
     * the node identified by childID.
     */

    virtual bool DRV_IsParentID(int parentID, int childID) const;

    /*
     * Find the rank of a child node in the vertex list of a node.
     */

    virtual int DRV_GetRankOfChildNode(int parentID, int childID, int ith)
	const;
    
    /*
     * Set a vertex whose vertex ID is given.
     */
    
    virtual bool DRV_SetVertex(int vertexID,
			       int nameID,
			       int vertexType,
			       int itemID);

    /*
     * Add a vertex according to the rank and io arguments to a node whose
     * node ID is given.
     */
    
    virtual int DRV_AddVertex(int nodeID, e4_InsertOrder io, int &rank);
    
    /*
     * Find the rank of a vertex with a given index in a node whose node ID
     * is given.
     */

    virtual int DRV_RankFromVertexID(int nodeID, int vertexID) const;

    /*
     * Find the nth vertex with a given name in a list of vertices.
     */
    
    virtual int DRV_VertexIDFromNthVertex(int nodeID,
					  int nameID,
					  int nth,
					  int &rank)
	const;

    /*
     * Get the next vertex after one identified by vertexID in
     * the node containing this vertex.
     */

    virtual e4_VertexImpl *DRV_NextVertex(int num, int vertexID) const;

    /*
     * Get the previous vertex before one identified by vertexID in
     * the node containing this vertex.
     */

    virtual e4_VertexImpl *DRV_PrevVertex(int num, int vertexID) const;

    /*
     * Get the ID of the next vertex after the one identified by vertexID.
     */

    virtual int DRV_NextVertexID(int vertexID) const;

    /*
     * Get the ID of the previous vertex before the one identified by
     * the given vertexID.
     */

    virtual int DRV_PrevVertexID(int vertexID) const;

    /*
     * Given the rank of a vertex in this node, find the corresponding
     * vertex ID.
     */

    virtual int DRV_VertexIDFromRank(int nodeID, int rank) const;

    /*
     * Get the parent node of a node or the parent ID, given the child node ID.
     */

    virtual e4_NodeImpl *DRV_GetParentNode(int childID, int nth) const;
    virtual int DRV_GetParentNodeID(int childID, int nth) const;

    /*
     * Get the vertex ID for the vertex containing this node in its parent.
     */

    virtual int DRV_GetVertexIDInParent(int parentID,
					int nodeID,
					int ith)
	const;
    
    /*
     * Get vertex IDs for the first or last vertex in a node, given 
     * the node ID.
     */

    virtual int DRV_GetFirstVertexID(int nodeID) const;
    virtual int DRV_GetLastVertexID(int nodeID) const;

    /*
     * Get the e4_VertexImpl instance representing the vertex following a
     * vertex identified by ID in the node containing that vertex.
     */

    virtual e4_VertexImpl *DRV_FindNextVertex(int vertexID,
					      e4_VisitMethod vm,
					      int vf, 
					      int nameID,
					      int nodeID,
					      int parentID,
					      e4_VertexType typeID,
					      e4_DetachChoice dc)
	const;

    /*
     * Get the e4_NodeImpl instance representing the node following a
     * node identified by ID.
     */

    virtual e4_NodeImpl *DRV_FindNextNode(int nodeID) const;

    /*
     * Given a vertex ID, find the e4_NodeImpl instance representing the node
     * that contains that vertex.
     */

    virtual e4_NodeImpl *DRV_ContainingNodeFromVertexID(int vertexID) const;

    /*
     * Given a vertex ID, find the node ID for the node that contains this
     * vertex.
     */

    virtual int DRV_ContainingNodeIDFromVertexID(int vertexID) const;

    /*
     * Is the node identified by nodeID valid?
     */

    virtual bool DRV_IsLegalNodeID(int nodeID) const;

    /*
     * Check that a vertex ID is legal.
     */

    virtual bool DRV_IsLegalVertexID(int index) const;

    /*
     * Get the value of a vertex whose vertex ID is given.
     */

    virtual bool DRV_GetVertexByIndex(int index, e4_ValueImpl *&v) const;
    virtual bool DRV_GetVertexByIndex(int index, e4_NodeImpl *&n) const;
    virtual bool DRV_GetVertexByIndex(int index, int &v) const;
    virtual bool DRV_GetVertexByIndex(int index, double &f) const;
    virtual bool DRV_GetVertexByIndex(int index, const char *&s) const;
    virtual bool DRV_GetVertexByIndex(int index, 
				      const void *&bytes,
				      int &nbytes)
	const;

    /*
     * Set the value of a vertex whose vertex ID is given.
     */

    virtual bool DRV_SetVertexByIndex(int index, int v);
    virtual bool DRV_SetVertexByIndex(int index, double f);
    virtual bool DRV_SetVertexByIndex(int index, const char *s);
    virtual bool DRV_SetVertexByIndex(int index,
				      const void *bytes, 
				      int nbytes);
    virtual bool DRV_SetVertexByIndexToNode(int index, int childID);

    /*
     * Rename a vertex whose index is given.
     */

    virtual bool DRV_RenameVertexByVertexID(int vertexID, int newNameID);

    /*
     * Return the vertex type and name of the vertex whose ID is given.
     */

    virtual e4_VertexType DRV_VertexTypeFromVertexID(int vertexID) const;
    virtual int DRV_NodeIDFromVertexID(int vertexID) const;
    virtual const char *DRV_VertexNameFromVertexID(int vertexID) const;
    virtual int DRV_NameIDFromVertexID(int vertexID) const;

    /*
     * Set and get the user data associated with an entity.
     */

    virtual bool DRV_SetNodeUserData(int nodeID, int userData);
    virtual bool DRV_SetVertexUserData(int vertexID, int userData);
    virtual bool DRV_GetNodeUserData(int nodeID, int &userData) const;
    virtual bool DRV_GetVertexUserData(int vertexID, int &userData) const;

    /*
     * Retrieve the value of an entry in one of the type-specific
     * views. The value is returned in an output parameter. If the
     * row contains an in-use value, true is returned and the output
     * parameter is set. Otherwise false is returned and the
     * output parameter is not modified.
     */

    virtual bool DRV_GetNode(int index, e4_NodeImpl *&value) const;
    virtual bool DRV_GetInt(int index, int &value) const;
    virtual bool DRV_GetDouble(int index, double &value) const;
    virtual bool DRV_GetString(int index, char *&value) const;
    virtual bool DRV_GetBinary(int index, void *&value, int &nbytes) const;
    virtual bool DRV_GetVertexName(int index, const char *&value) const;

    /*
     * Get the raw value of a specific vertex as an index. For use only
     * by GC.
     */

    virtual bool DRV_GetRawValue(int index, int &value) const;

    /*
     * Get the index of the node that is the value of the given vertex.
     */

    virtual bool DRV_GetNodeID(int index, int &value) const;

    /*
     * Specialized version of GetNode that also returns an indication
     * whether the node is newly created.
     */

    virtual bool DRV_GetNode(int index,
			     e4_NodeImpl *&value,
			     bool *isNew)
	const;

    /*
     * Detach the node or vertex identified by the given ID.
     */

    virtual bool DRV_DetachNodeByID(int id);
    virtual bool DRV_DetachVertexByID(int id);

    /*
     * Get the vertex ID of the first detached vertex whose value is
     * the given node ID. Similarly, get the vertex ID of the next
     * detached vertex after this one that has this node as its value.
     */

    virtual int DRV_GetFirstDetachedVertexIDWithNodeID(int id) const;
    virtual int DRV_GetNextDetachedVertexIDAfter(int id) const;

    /*
     * Add a new entry to one of the type-specific views. The operation
     * returns the index of the new row in the view.
     */

    virtual int DRV_ReserveNodeID();
    virtual int DRV_ReserveVertexID(int nameID);
    virtual int DRV_AddInt(int value);
    virtual int DRV_AddDouble(double value);
    virtual int DRV_AddString(const char *value);
    virtual int DRV_AddBinary(const void *value, int nbytes);
    virtual int DRV_AddName(const char *nm);

    /*
     * Move the vertex identified by vertexID into the node identified by
     * nodeID as the first vertex.
     */

    virtual bool DRV_MoveVertexToFirst(int vertexID, int nodeID);

    /*
     * Move the vertex identified by vertexID into the node identified by
     * nodeID as the last vertex.
     */

    virtual bool DRV_MoveVertexToLast(int vertexID, int nodeID);

    /*
     * Move the vertex identified by vertexID to immediately after
     * the vertex identified by afterVertexID.
     */

    virtual bool DRV_MoveVertexAfter(int vertexID,
				     int afterVertexID,
				     int rank);

    /*
     * Copy the e4Graph related data from this storage to another.
     */

    virtual bool DRV_CopyTo(e4_StorageImpl *impl);

    /*
     * Destroy the physical storage for this storage and make it invalid.
     */

    virtual void DRV_Destroy();

    /*
     * Retrieve the nth vertex in the parent node identified by parentID
     * whose value is the node identified by nodeID.
     */

    virtual e4_VertexImpl *DRV_GetVertexRefFromParent(int parentID,
						      int nodeID,
						      int nth)
	const;

    /*
     * Retrieve the nth vertex in the ith parent of the node identified by
     * nodeID whose value is the node identified by nodeID.
     */

    virtual e4_VertexImpl *DRV_GetVertexRefFromIthParent(int i,
							 int nodeID,
							 int nth)
	const;

    /*
     * How many parents does the given node have?
     */

    virtual int DRV_ParentCount(int nodeID) const;

    /*
     * How many times does the node with the given ID appear as the value
     * of a vertex in this storage?
     */

    virtual int DRV_OccurrenceCount(int nodeID) const;

    /*
     * How many times does the node with the given child ID appear as
     * the value of a vertex in the node with the given parent ID?
     */

    virtual int DRV_OccurrenceCount(int nodeID, int parentID) const;

    /*
     * What is the rank of the node with the given parent ID for the
     * node with the given child ID?
     */

    virtual int DRV_ParentRank(int nodeID, int parentID) const;
};