B4J Library TreeMap (A Sorted Map)

This is a wrapper for the Java TreeMap class. A TreeMap is a Red-Black tree based map. By default it is sorted according to the natural ordering of its keys but this can be overridden by using a custom comparator sub (see example code). Because it is tree based it is very easy to return portions of the Map based on the key values as shown in the example code.

TreeMapB4J
Author:
KeirS
Version: 1.01
  • TreeMap
    Methods:
    • CeilingKey (Key As Object) As Object
      Returns the least key greater than or equal to the given key, or null if there is no such key.
    • Clear
      Removes all of the mappings from this map.
    • ComparatorMap (ComparatorSub As String) As B4JTreeMap
      Returns a TreeMap with the keys ordered by the comparator sub.
    • ContainsKey (Key As Object) As Boolean
      Tests whether there is an item with the given key.
    • FirstKey As Object
      Returns the first (lowest) key currently in this map.
    • FloorKey (Key As Object) As Object
      Returns the greatest key less than or equal to the given key, or null if there is no such key.
    • Get (Key As Object) As Object
      Returns the value of the item with the given key.
    • GetKeyAt (index As Int) As Object
      Returns the key of the item at the given index. GetKeyAt and GetValueAt should be used to iterate over all the items.
    • GetValueAt (index As Int) As Object
      Returns the value of the item at the given index. GetKeyAt and GetValueAt should be used to iterate over all the items.
    • HeadMap (Key As Object, Inclusive As Boolean) As B4JTreeMap
      Returns a view of the portion of this map whose keys are less than (or equal to if inclusive) the passed Key
    • HigherKey (Key As Object) As Object
      Returns the least key strictly greater than the given key, or null if there is no such key.
    • Initialize (ComparatorSub As String)
    • Initialize2 (map As Map, ComparatorSub As String)
      Initializes the object. And populates it with the passed Map. If you want a custom comparator then pass the name of the sub.
      For the default comparator pass an empty string.
    • Keys As IterableList
      Returns an object which can be used to iterate over all the keys with a For Each block.
    • LastKey As Object
      Returns the last (highest) key currently in this map.
    • LowerKey (Key As Object) As Object
      Returns the greatest key less than the given key, or null if there is no such key.
    • Put (Key As Object, Value As Object)
      Puts a key/value pair in the map, overwriting the previous item with this key (if such exists).
      the previous item with this key or null if there was no such item.
    • Remove (Key As Object) As Object
    • Size As Int
      Returns the number of items stored in the map.
    • SubMap (FromKey As Object, ToKey As Object, Inclusive As Boolean) As B4JTreeMap
      Returns a TreMmap of the portion of this map whose keys range from fromKey to toKey.
      The range is inclusive of the key values if inclusive is true
    • TailMap (fromKey As Object, Inclusive As Boolean) As B4JTreeMap
      Returns a TreeMap of the portion of this map whose keys are greater than (or equal to if inclusive) fromKey.
    • Values As IterableList
      Returns an object which can be used to iterate over all the values with a For Each block

Sample Code:

B4X:
Sub Process_Globals
    Private fx As JFX
    Private MainForm As Form
    Dim MainMap As TreeMap
    Dim DescendingMainMap As TreeMap
    Dim SubMap As TreeMap
    Dim HeadMap As TreeMap
    Dim TailMap As TreeMap

End Sub

Sub AppStart (Form1 As Form, Args() As String)
    MainForm = Form1
    'MainForm.RootPane.LoadLayout("Layout1") 'Load the layout file.
    MainForm.Show
    'Create Main Map
    MainMap.Initialize("")
    MainMap.Put("D","D")
    MainMap.Put("A","A")
    MainMap.Put("C","C")
    MainMap.Put("E","E")
    MainMap.Put("G","G")
    MainMap.Put("B","B")
    MainMap.Put("F","F")
 
    Log("Keys In Ascending Order")
    MapToLog(MainMap)
 
    'Get Map in Descinging Key Order.
    DescendingMainMap = MainMap.ComparatorMap("DescendingOrder")
    Log("Keys In Descending Order")
    MapToLog(DescendingMainMap)
 
    'get Map with keys B To F inclusive
    SubMap = MainMap.SubMap("B","F",True)
    Log("Keys Between B And F Inclsuive")
    MapToLog(SubMap)
 
    'get Map with keys <= F
    HeadMap = MainMap.HeadMap("F",True)
    Log("Keys <= F")
    MapToLog(HeadMap)
 
    'get Map with keys >= G
    TailMap = MainMap.TailMap("F",True)
    Log("Keys >= F")
    MapToLog(TailMap)
 
    Dim s As String = MainMap.LowerKey("F")
    Log("First Key Lower Than F: " & s)
 
    s = MainMap.FloorKey("C")
    Log("First Key Lower Than or Equal To C: " & s)
 
    s = MainMap.HigherKey("F")
    Log("First Key Higher Than F: " & s)
 
    s = MainMap.CeilingKey(" ")
    Log("First Key Higher Than Space: " & s)
 
    s = MainMap.FirstKey
    Log("First Key In Map: " & s)
 
    s = MainMap.LastKey
    Log("Last Key In Map: " & s)
 
    Log("Map Contains G: " & MainMap.ContainsKey("G"))
    Log("Map Contains Z: " & MainMap.ContainsKey("Z"))
 
    Log("Key At Position 3 Should Be D: " & MainMap.GetKeyAt(3))
    Log("Value At Position 2 Should Be C: " & MainMap.GetValueAt(2))
 
 
    MainMap.Remove("C")
    Log("Key C removed:")
    MapToLog(MainMap)
 
    
'Initalize2 method as suggested by Erel. Creates a TreeMap from a B4J Map
    Log("Initalize from B4J Map")
    MapFromCreateMap.Initialize2(CreateMap("A": "A","B": "B","C": "C","D": "D","E": "E","F": "F","G": "G"),"")
    MapToLog(MapFromCreateMap)

End Sub

Sub MapToLog(TM As TreeMap)
    For Each k As String In TM.Keys
    Log(k)
Next
 

End Sub

'Descending order comparator sub.
'Rules for comapartor are
' If Obj1 is less than Obj2: Return a negative Int.
' If Oj1 is greater than Obj2:  Return a positive Int.
' If Obj1 is equal  Obj2: Return 0.

'cheat because I just want descending order...
Sub DescendingOrder(S1 As String,S2 As String)
    Dim i As  Int = S1.CompareTo(S2) * -1
 
    Return i 
End Sub

Log output:

B4X:
Keys In Ascending Order
A
B
C
D
E
F
G
Keys Between B And F Inclsuive
B
C
D
E
F
Keys <= F
A
B
C
D
E
F
Keys >= F
F
G
First Key Lower Than F: E
First Key Lower Than or Equal To C: C
First Key Higher Than F: G
First Key Higher Than Space: A
First Key In Map: A
Last Key In Map: G
Map Contains G: true
Map Contains Z: false
Key At Position 3 Should Be D: D
Value At Position 2 Should Be C: C
Key C removed:
A
B
D
E
F
G
Initalize from B4J Map
A
B
C
D
E
F
G

Added Initalize2 method. Which populates a TreeMap from a B4J map.
 

Attachments

  • B4JTreemap1.01.zip
    5.1 KB · Views: 391
Last edited:

keirS

Well-Known Member
Licensed User
Longtime User
New version of the library implementing Erel's suggestion above.
 

Cableguy

Expert
Licensed User
Longtime User
Since this is a tree map, can this be achieved?

Alphabet->A->a
Alphabet->B->b
.........................
Alphabet->Z->z
Numerical->1-one
Numerical->2-two
........................
Numerical->0->zero
 

keirS

Well-Known Member
Licensed User
Longtime User
If understand your question correctly then yes. You can use a custom comparator sub to achieve that ordering.
 

Cableguy

Expert
Licensed User
Longtime User
Can you provide an example on how to achieve a map with a primary key and a secondary key/value pair?
 

keirS

Well-Known Member
Licensed User
Longtime User
You would have to put a another map into the value of your TreeMap to do that. No reason it shouldn't work however.

B4X:
Dim MainMap As TreeMap
Dim SubMap As TreeMap

MainMap.Initialize()
SubMap.Initialize()

MainMap.Put("A",SubMap)

Then You could add keys "a","b","c" etc into to your SubMap
 

keirS

Well-Known Member
Licensed User
Longtime User
The TreeMap is just a self balancing binary search tree.

2000px-Red-black_tree_example.svg.png



You would have to come up with a sorting scheme that ensured that there was only the required nodes under the primary key nodes. It may be possible to come up with such a sorting scheme but I cant think of one off hand.
 
Top