constructed trie appears to violate invariants

[RossBoylan]

The code at the bottom constructs a trie and graphs the resulting trie. As also verified by inspection in the debugger, the resulting trie does not seem to satisfy the requirement that descendants of a node share a common prefix.

Consider 162.247.74.0 and descendants. That node is RLL from the root: go right, then left, then left. Its L descendant is 171.25.193.0. That's a bigger value, but it's on the left. It and the parent differ in bit 4, even though the parent's decision bit is 22.

The R child of 171.25.193.0 is 158.69.217.248, a lower value even though it is to the right. 158.69 differs from parent at bit 2, even though the parent decision bit is 23.

I assume the left and right branching is being dictated by the decision bit, though I haven't verified it. The problem is that the most significant difference is not at the decision bit.

The inorder traversal is correspondingly unsorted:

23.129.64.0 bit: 3
31.220.2.0 bit: 4
49.88.112.0 bit: 2
54.174.144.174 bit: 5
58.218.0.0 bit: 4
61.177.172.128 bit: 5
77.247.181.0 bit: 1
89.234.157.254 bit: 3
89.236.112.100 bit: 13
93.186.170.7 bit: 5
112.85.42.0 bit: 2
116.31.116.0 bit: 5
0.0.0.0 bit: -1
171.25.193.0 bit: 23
158.69.217.248 bit: 28
162.247.74.0 bit: 22
185.165.168.229 bit: 3
185.220.0.0 bit: 9
192.42.116.0 bit: 1
192.151.150.0 bit: 8
209.141.0.0 bit: 3
218.92.0.0 bit: 4
222.186.0.0 bit: 5

#! /usr/bin/python3

DOTFILE = "pt-test.gv"

from cidr_trie import PatriciaTrie, PatriciaNode
from ipaddress import ip_address
from graphviz import Digraph

master = PatriciaTrie()
TEST = [
    "23.129.64.215/24",
    "31.220.2.100/24",
    "49.88.112.0/24",
    "54.174.144.174",
    "77.247.181.0/24",
    "89.234.157.254",
    "89.236.112.100",
    "93.186.170.7",
    "58.218.0.0/16",
    "61.177.172.128/32",
    "112.85.42.0/24",
    "116.31.116.5/24",
    "158.69.217.248",
    "162.247.74.213/24",
    "171.25.193.0/24",
    "185.165.168.229",
    "185.220.100.0/16",
    "192.42.116.26/24",
    "192.151.150.0/24",
    "209.141.0.0/16",
    "218.92.0.0/16",
    "222.186.175.8/16",
    ]

for nm in TEST:
    master.insert(nm, None)

def nodename(pn : PatriciaNode) -> str :
    "return name of node"
    ipa = ip_address(pn.ip)
    return ipa.exploded
    
def nodetext(pn : PatriciaNode) -> str :
    "return text of node"
    ipa = ip_address(pn.ip)
    r = ipa.exploded
    msks = list(pn.masks.keys())
    for msk in msks:
        if msk == 32 and len(msks) == 1:
            break
        r += " /{}".format(msk)
    r = "{}\n{:032b}\nbit: {}".format(r, pn.ip, pn.bit)
    return r
    
def graph(pt : PatriciaTrie):
    "plot a Trie of CIDR values to reveal internal structure"
    g = Digraph("G", filename=DOTFILE)
    pn = pt.root
    dive(g, pn, None, True)
    g.view()

def dive(g, pn, parent, left):
    """add subtree from pn on down to graph g. parent is parent node name or None
    left is true if pn is left descendant of parent"""
    myname = nodename(pn)
    g.node(myname, nodetext(pn))
    if parent:
        if left:
            g.edge(parent, myname, label="L", color="red")
        else:
            g.edge(parent, myname, label="R", color="blue")
    if pn.left.bit > pn.bit:
        dive(g, pn.left, myname, True)
    if pn.right.bit > pn.bit:
        dive(g, pn.right, myname, False)
    

graph(master)

pt-test.gv.pdf