DLL: PB 4/8 ok
Class: PB 5/9
free: use at your own risk

String/String, Key/Value, AVL Tree
google "AVL tree"

Keys must be unique

Fast - about half the speed of a hash
find 100,000 strings 0.55 seconds (netbook)

Keys always in alphabetical order (UCase)
handle millions of items (memory)
Values stored in buffers - NULL ok
no null in Key - mess up compare


Code:
 
 
 
'PBCC 5, PBWin 9
    'STRING/STRING : Key/Value : AVL Balanced Binary Tree Class
    '   google "avl tree"
    '   Keys must be unique
    '   used for storing Key/Value pairs
    '   (in C++ STL called "map")
    'Pro:
    '    Extremely fast
    '       find 100,000 strings 0.55 seconds (netbook)
    '    Can handle millions of Key/Value pairs
    '    Tree always in order (and balanced)
    '    Fast inserts and deletes anywhere in tree
    '    Unlike Hash - can traverse in order
    '    Unlike Hash - doesn’t have to rebuild when Key count goes over/under productive range
    'Con:
    '    Uses more resources than an array
    '    Not quite as fast as a Hash
    '    If you don’t need to maintain order - Hash is faster
    'Implementation:
    '    Tree = upside-down tree (root on top)
    '    Tree may be stored/restored to/from string
    '
    'use:
    'put "SSTreeC_DLL-1.inc" in same folder as source code
    '#Include Once "SSTreeC_DLL-1.inc"
    '
    'put "SSTreeC_DLL-1.DLL" in same folder as source code
    '
    'LOCAL tree as SSTreeI
    'tree = NewCom ClsId $SSTreeC_GUID Lib "SSTreeC_DLL-1.DLL"
    '   start using
 
$SSTreeC_GUID = Guid$("{331DF364-EDCB-4F06-951A-B590F9503595}")
$SSTreeI_GUID = Guid$("{04471B50-3087-4D12-A29F-2AA70B439AEA}")
 
Interface SSTreeI $SSTreeI_GUID
    Inherit IUnknown
    'Add() or Set()
    '   use Set() to always set Value
    '       Key added if not in tree
    '   use Add() to avoid overwriting existing Value
    '       Add() will fail if Key already in tree
    '
    'you can move back and forth in tree using cursor function; Go...()
    '   the cursor functions use a Node Handle
    '       you can get Key, get/set Value while using cursor
    'NOTE: once you hit END or BEGINNING of tree;
    '   you have to GoFirst() or GoLast() to get a valid Node Handle
    '
    '   you can't Delete(key) of node you're sitting on while using cursor functions
    '       save Key and move right or left before deleting Key
    '           (Node Handle would become invalid)
 
    Method Clear()
        'delete all data
        '   call Clear() before obj = NOTHING
        '   internal resources will immediately be freed
        '       instead of waiting till obj destroyed
 
    Method Count() As Long
        'get Key/Value count
 
    Method Add(In ByRef key As String, In ByRef value As String) As Long
        'add Key/Value to tree
        '   fail if Key exist
        '   return node handle if succeed
        '       return False if fail
 
    Method Set(In ByRef key As String, In ByRef value As String) As Long
        'set Key's Value
        '   add Key/Value if Key not in tree
        '   return non-zeor if succeed (node handle)
        '   return FALSE if fail
 
    Method Get(In ByRef key As String) As String
        'get Value associated with Key
 
    Method Contains(In ByRef key As String) As Long
        'see if Key in tree
        '   return Node handle if found (non-zero)
        '   FALSE if not found
 
    Method Delete(In ByRef key As String)
        'remove Key/Value from tree
 
    Method Replace(In ByRef oldKey As String, In ByRef newKey As String)
        'replace Old Key with New Key
        '   new Key must not exist
        '   slightly expensive operation
 
    Method GoFirst() As Long
        'got lowest Key in tree - Beginning - Far Left
        '   return Node Handle
        '       NULL if fail
 
    Method GoLast() As Long
        'go to highest Key in tree - End - Far Right
        '   return Node Handle
        '       NULL if fail
 
    Method GoNext(ByVal hNode As Long) As Long
        'go to next node in tree - right
        '   return Node Handle
        '       NULL if past end of tree
 
    Method GoPrev(ByVal hNode As Long) As Long
        'go left - previous node
        '   return Node Handle
        '       NULL if past beginning of tree
 
    Method GoGetKey(ByVal hNode As Long) As String
        'get Key at current node position
 
    Method GoSetValue(ByVal hNode As Long, In ByRef value As String)
        'change Value at current node position
 
    Method GoGetValue(ByVal hNode As Long) As String
        'get Value at current node position
 
    Method Store() As String
        'get whole tree as string (persist)
 
    Method Restore(In ByRef storedTree As String)
        'build tree from storage string
        '   current contents cleared
 
    Method StoreValidate(In ByRef storedTree As String) As Long
        'True/False if string is valid
        '   storage strings protected with two unique DWord validation hashes - front/back
 
End Interface
Attached Files