summaryrefslogtreecommitdiff
path: root/src/include/xblnklstord.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/include/xblnklstord.h')
-rwxr-xr-xsrc/include/xblnklstord.h367
1 files changed, 367 insertions, 0 deletions
diff --git a/src/include/xblnklstord.h b/src/include/xblnklstord.h
new file mode 100755
index 0000000..d319c31
--- /dev/null
+++ b/src/include/xblnklstord.h
@@ -0,0 +1,367 @@
+/* xblnklstord.h
+
+XBase64 Software Library
+
+Copyright (c) 1997,2003,2014,2019,2022 Gary A Kunkel
+
+The xb64 software library is covered under the terms of the GPL Version 3, 2007 license.
+
+Email Contact:
+
+ XDB-devel@lists.sourceforge.net
+ XDB-users@lists.sourceforge.net
+
+*/
+
+
+// Ordered link list
+
+
+
+#ifndef __XB_XBLNKLSTORD_H__
+#define __XB_XBLNKLSTORD_H__
+
+#ifdef XB_LINKLIST_SUPPORT
+
+
+namespace xb{
+
+
+template<class xbNodeType>
+class XBDLLEXPORT xbLinkListOrd {
+ public:
+ xbLinkListOrd();
+ ~xbLinkListOrd();
+
+ void Clear();
+ xbLinkListNode<xbNodeType> *GetHeadNode() const;
+ xbLinkListNode<xbNodeType> *GetEndNode() const;
+ xbLinkListNode<xbNodeType> *GetNodeForKey( const xbString &sKey ) const;
+
+ xbInt16 GetDataForKey ( const xbNodeType &ntKey, xbString &sData );
+
+ xbBool GetDupKeys ();
+
+ xbUInt32 GetNodeCnt () const;
+ xbUInt32 GetNodeCnt ( const xbString &sNodeKey ) const;
+ xbInt16 InsertKey ( const xbNodeType &ntKey );
+ xbInt16 InsertKey ( const xbNodeType &ntKey, const xbString &sData );
+ xbInt16 InsertKey ( const xbNodeType &ntKey, xbUInt32 ulData );
+
+ xbBool KeyExists ( const xbNodeType &ntKey ) const;
+ xbInt16 RemoveKey ( const xbNodeType &ntKey );
+ xbInt16 RemoveFromEnd ( xbNodeType &ntKey );
+ xbInt16 RemoveFromFront( xbNodeType &ntKey );
+ xbInt16 RemoveFromFront();
+ void SetDupKeys ( xbBool bAllowDupKeys );
+ xbInt16 UpdateForKey ( const xbNodeType &ntKey, const xbString &sData );
+
+
+ private:
+ xbUInt32 ulNodeCnt;
+ xbBool bAllowDupKeys;
+ xbLinkListNode<xbNodeType> *llStartPtr;
+ xbLinkListNode<xbNodeType> *llEndPtr;
+
+};
+
+
+template<class xbNodeType>
+xbLinkListOrd<xbNodeType>::xbLinkListOrd(){
+ bAllowDupKeys = xbTrue; // default setting - allow duplicate keys
+ ulNodeCnt = 0;
+ llStartPtr = NULL;
+ llEndPtr = NULL;
+}
+
+template<class xbNodeType>
+xbLinkListOrd<xbNodeType>::~xbLinkListOrd(){
+ Clear();
+}
+
+template<class xbNodeType>
+void xbLinkListOrd<xbNodeType>::Clear(){
+ xbLinkListNode<xbNodeType> *cPtr = llStartPtr, *tPtr;
+ for( xbUInt32 i = 0; i < ulNodeCnt; i++ ){
+ tPtr = cPtr;
+ cPtr = cPtr->GetNextNode();
+
+ // next line might cause seg faults
+ // delete tPtr->GetData();
+
+ delete tPtr;
+ }
+ ulNodeCnt = 0;
+ llStartPtr = NULL;
+ llEndPtr = NULL;
+}
+
+template<class xbNodeType>
+xbLinkListNode<xbNodeType> * xbLinkListOrd<xbNodeType>::GetHeadNode() const{
+ return llStartPtr;
+}
+
+template<class xbNodeType>
+xbLinkListNode<xbNodeType> * xbLinkListOrd<xbNodeType>::GetEndNode() const{
+ return llEndPtr;
+}
+
+template<class xbNodeType>
+xbUInt32 xbLinkListOrd<xbNodeType>::GetNodeCnt() const{
+ return ulNodeCnt;
+}
+
+template<class xbNodeType>
+xbUInt32 xbLinkListOrd<xbNodeType>::GetNodeCnt( const xbString &sNodeKey ) const{
+
+ // won't work if nodekey is not a string
+ xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
+ // skip to sNodeKey
+ while( currPtr && ( sNodeKey > currPtr->GetKey())) {
+ currPtr = currPtr->GetNextNode();
+ }
+ // count entries for sNodeKey
+ xbInt16 iKeyCnt = 0;
+ while( currPtr && ( sNodeKey == currPtr->GetKey())) {
+ iKeyCnt++;
+ currPtr = currPtr->GetNextNode();
+ }
+ return iKeyCnt;
+}
+
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::InsertKey( const xbNodeType &ntKey ){
+ xbString s;
+ return InsertKey( ntKey, s );
+}
+
+
+
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::InsertKey( const xbNodeType &ntKey, xbUInt32 ul ){
+
+ xbString s;
+ s.Sprintf( "%ld", ul );
+ return InsertKey( ntKey, s );
+}
+
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::InsertKey( const xbNodeType &ntKey, const xbString &sData ){
+
+ xbLinkListNode<xbNodeType> *p = new xbLinkListNode<xbNodeType>( ntKey, sData );
+ if( p == 0 )
+ return XB_NO_MEMORY;
+
+ if( ulNodeCnt > 0 ){
+ xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
+ xbLinkListNode<xbNodeType> *prevPtr = NULL;
+
+ // find location in the chain
+ while( currPtr && ntKey > currPtr->GetKey() ){
+ prevPtr = currPtr;
+ currPtr = currPtr->GetNextNode();
+ }
+ if( currPtr && ntKey == currPtr->GetKey() && bAllowDupKeys == 0 ){
+ delete p;
+ return XB_KEY_NOT_UNIQUE;
+ }
+
+ if( currPtr == NULL ){
+ // std::cout << "at the end of the chain\n";
+ llEndPtr = p;
+ prevPtr->SetNextNode( p );
+ p->SetPrevNode( prevPtr );
+
+ } else if( currPtr->GetPrevNode() == NULL ){
+ // std::cout << "at the beginning of the chain\n";
+ p->SetNextNode( llStartPtr );
+ llStartPtr->SetPrevNode( p );
+ llStartPtr = p;
+
+ } else {
+ // std::cout << "in the middle of the chain\n";
+ p->SetNextNode( currPtr );
+ p->SetPrevNode( currPtr->GetPrevNode());
+ currPtr->SetPrevNode( p );
+ prevPtr->SetNextNode( p );
+ }
+ } else {
+ // std::cout << "first addition to the chain\n";
+ llStartPtr = p;
+ llEndPtr = p;
+ }
+ ulNodeCnt++;
+ return XB_NO_ERROR;
+}
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::RemoveKey( const xbNodeType &ntKey ){
+ // Remove the first instance of ntKey from the node chain
+ xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
+ xbLinkListNode<xbNodeType> *prevPtr = NULL;
+
+ while( currPtr && ntKey > currPtr->GetKey() ){
+ prevPtr = currPtr;
+ currPtr = currPtr->GetNextNode();
+ }
+
+ if( currPtr && ntKey == currPtr->GetKey()){
+// ntKey = currPtr->GetKey();
+ if( prevPtr == NULL ){ // this is the first node
+ llStartPtr = currPtr->GetNextNode();
+ // next line fails
+ if( llStartPtr ){
+ llStartPtr->SetPrevNode( NULL );
+ }
+ delete currPtr;
+ ulNodeCnt--;
+ return XB_NO_ERROR;
+ } else if( currPtr->GetNextNode() == NULL ){ // this is the last node
+ llEndPtr = prevPtr;
+ prevPtr->SetNextNode( NULL );
+ delete currPtr;
+ ulNodeCnt--;
+ return XB_NO_ERROR;
+ } else {
+
+ prevPtr->SetNextNode( currPtr->GetNextNode());
+ currPtr->GetNextNode()->SetPrevNode( prevPtr );
+ delete currPtr;
+ ulNodeCnt--;
+ return XB_NO_ERROR;
+ }
+ } else {
+ return XB_NOT_FOUND;
+ }
+}
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::RemoveFromFront( xbNodeType &ntKey ){
+
+ if( ulNodeCnt <= 0 )
+ return XB_INVALID_NODELINK;
+ xbLinkListNode<xbNodeType> *p = llStartPtr;
+ llStartPtr = p->GetNextNode();
+ if( llStartPtr )
+ llStartPtr->SetPrevNode( NULL );
+ ntKey = p->GetKey();
+ delete p;
+ ulNodeCnt--;
+ return XB_NO_ERROR;
+}
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::RemoveFromFront(){
+
+ if( ulNodeCnt <= 0 )
+ return XB_INVALID_NODELINK;
+ xbLinkListNode<xbNodeType> *p = llStartPtr;
+ llStartPtr = p->GetNextNode();
+ if( llStartPtr )
+ llStartPtr->SetPrevNode( NULL );
+
+ if( p->GetKey())
+ delete p->GetKey();
+
+ delete p;
+ ulNodeCnt--;
+
+ return XB_NO_ERROR;
+}
+
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::RemoveFromEnd( xbNodeType &ntKey ){
+
+ if( ulNodeCnt <= 0 )
+ return XB_INVALID_NODELINK;
+ xbLinkListNode<xbNodeType> *p = llEndPtr;
+ llEndPtr = p->GetPrevNode();
+ llEndPtr->SetNextNode( NULL );
+ ntKey = p->GetKey();
+ delete p;
+ ulNodeCnt--;
+ return XB_NO_ERROR;
+}
+
+template<class xbNodeType>
+xbBool xbLinkListOrd<xbNodeType>::GetDupKeys(){
+ return bAllowDupKeys;
+}
+
+template<class xbNodeType>
+void xbLinkListOrd<xbNodeType>::SetDupKeys( xbBool bAllowDupKeys ){
+ this->bAllowDupKeys = bAllowDupKeys;
+}
+
+
+template<class xbNodeType>
+xbBool xbLinkListOrd<xbNodeType>::KeyExists( const xbNodeType &ntKey ) const {
+
+ xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
+ while( currPtr && ntKey > currPtr->GetKey() ){
+ currPtr = currPtr->GetNextNode();
+ }
+ if( currPtr && ntKey == currPtr->GetKey()){
+ return xbTrue;
+ } else {
+ return xbFalse;
+ }
+}
+
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::GetDataForKey( const xbNodeType &ntKey, xbString &sData ){
+
+ xbLinkListNode<xbNodeType> *currPtr = llStartPtr;
+ while( currPtr && ntKey > currPtr->GetKey() ){
+ currPtr = currPtr->GetNextNode();
+ }
+
+ if( currPtr && ntKey == currPtr->GetKey()){
+ sData = currPtr->GetData();
+ return XB_NO_ERROR;
+ } else {
+ return XB_NOT_FOUND;
+ }
+}
+
+
+template<class xbNodeType>
+xbInt16 xbLinkListOrd<xbNodeType>::UpdateForKey( const xbNodeType &ntKey, const xbString &sData ){
+
+ if( ulNodeCnt == 0 )
+ return InsertKey( ntKey, sData );
+ xbLinkListNode<xbNodeType> * currPtr = llStartPtr;
+ xbLinkListNode<xbNodeType> * prevPtr = NULL;
+ while( currPtr && ntKey > currPtr->GetKey() ) {
+ prevPtr = currPtr;
+ currPtr = currPtr->GetNextNode();
+ }
+
+ if( currPtr && ntKey == currPtr->GetKey() ) {
+ xbLinkListNode<xbNodeType> *p = new xbLinkListNode<xbNodeType>( ntKey, sData );
+ if( prevPtr )
+ prevPtr->SetNextNode( p );
+ else
+ llStartPtr = p;
+ p->SetNextNode( currPtr->GetNextNode() );
+ p->SetPrevNode( currPtr->GetPrevNode() );
+ delete currPtr;
+ return XB_NO_ERROR;
+ }
+
+ return InsertKey( ntKey, sData );
+
+// return 0;
+}
+
+} // namespace
+
+#endif // XB_LINKLIST_SUPPORT
+#endif // XB_XBLNKLSTORD_H__
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-13 10:12:30 +0000