Hi! Could you please point me in a direction on how to accomplish iterative longestPre

longestPrefixMatch is a more specific case of <a href

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

Here is sample code, your example modified: <div class="highlight highlight-source

Question: longestPrefixMatch in a loop based on condition about ipaddress HOT 4 CLOSED

urbanchef commented on June 3, 2024

Question: longestPrefixMatch in a loop based on condition

from ipaddress.

Comments (4)

seancfoley commented on June 3, 2024 1

longestPrefixMatch is a more specific case of elementsContaining.

Given an input address i, the longest prefix match address m is the address in the trie with the longest prefix of all the addresses in the trie that contain i.

For example, if there are 3 addresses m1, m2, m3 that contain address i, then the longest prefix match is the one of those three with the longest prefix.
if
m1 is 1.2.0.0/16
m2 is 1.2.0.0/20
m3 is 1.2.0.0/24,
and i is 1.2.3.4,
then longestPrefixMatch returns the node for 1.2.0.0/24, while elementsContaining returns the entire list of 1.2.0.0/16, 1.2.0.0/20, and 1.2.0.0/24 as a linked list.

So, you can use elementsContaining, then you can go to the end of the returned list, and work back to each containing node until you have the one you want. Or, slightly more quickly, you can move down the list while retaining the most recent match until you reach the end of the list.

I can write some sample code for you, but not right now.

You can also look at the wiki example.

from ipaddress.

seancfoley commented on June 3, 2024 1

Is it true to say that existing implementation of longestPrefixMatch search works for logN time?

The trie look-up is a binary search using the bits of the address. A binary tree search is log n time where n is the number of nodes. It is based on the number of node comparisons you need to do to find the matching node. In the worst case, you would have a tree which is a straight line and you might have to compare to all n nodes. In the average case, you do log2(n) comparisons.

However, in an address trie, the number of nodes is bounded, since there are 2 to the power of 32 possible IPv4 addresses. So in a trie with all IPv4 addresses, your average search is log2(2 to the power of 32) which is 32. You will average 32 comparisons for every each search in a trie holding every single IPv4 address. In fact, every single search in that trie will do 32 comparisons, so the average is also the upper and lower bounds for that trie.

In fact, the number of comparisons is bounded by the number of bits in the address, since in the worst case you might compare each and every bit in the address to a different node. So that is another way of seeing there is at most 32 comparisons.

So, for that reason, you can make the argument that it is constant time O(1), bounded by the worst-case scenario of doing 32 address comparisons. It depends on how you look at it.

In any case, a binary search is an efficient search.

from ipaddress.

urbanchef commented on June 3, 2024

@seancfoley Thank you! Appreciate such a quick and informative reply!

from ipaddress.

seancfoley commented on June 3, 2024

Here is sample code, your example modified:

public class Test {

      static IPv4AddressAssociativeTrie<Info> trie = new IPv4AddressAssociativeTrie<>();
    
    static class Info {
        String str;
        boolean bool;

        Info(String str, boolean bool) {
            this.str = str;
            this.bool = bool;
        }

        public boolean getBool() {
            return bool;
        }

        @Override
        public String toString() {
            return str + ' ' + bool;
        }
    }

    static IPv4Address getAddr(String addrStr) {
        return new IPAddressString(addrStr).getAddress().toIPv4();
    }

    static void addToTrie(IPv4AddressAssociativeTrie<Info> trie, String entry) {
        int index = entry.indexOf(':');
        String back = entry.substring(index + 2);
        trie.put(getAddr(back),
                new Info(back, Boolean.parseBoolean(entry.substring(0, index))));
    }

    public static void main(String[] args) {
        String[] mappings = {
                "true: 1.0.0.0/8",

                "true: 1.1.0.0/16",
                "true: 1.2.0.0/16",
                "true: 1.3.0.0/16",

                "false: 1.1.1.0/24",
                "false: 1.1.2.0/24",
                "false: 1.1.3.0/24",
        };

        for(String entry : mappings) {
            addToTrie(trie, entry);
        }
        System.out.println("The trie is:");
        System.out.println(trie);

        System.out.println("result is: " + findIpInfo(new IPAddressString("1.1.3.1").getAddress(), 32));
        System.out.println("result is: " + findIPInfoNew1(new IPAddressString("1.1.3.1").getAddress().toIPv4()));
        System.out.println("result is: " + findIPInfoNew2(new IPAddressString("1.1.3.1").getAddress().toIPv4()));
    }

    static Info findIpInfo(IPAddress ipAddress, int prefixLen) {
        IPv4Address iPv4Address = ipAddress.toIPv4().setPrefixLength(prefixLen);
        IPv4AddressAssociativeTrie.IPv4AssociativeTrieNode<Info> iPv4AssociativeTrieNode = trie.longestPrefixMatchNode(iPv4Address);
        if (iPv4AssociativeTrieNode != null && iPv4AssociativeTrieNode.getValue().getBool()) {
            return iPv4AssociativeTrieNode.getValue();
        }
        return null;
    }
    
    static Info findIPInfoNew1(IPv4Address iPv4Address) {
        IPv4AddressAssociativeTrie.IPv4AssociativeTrieNode<Info> ipv4AssociativeTrieNode = trie.elementsContaining(iPv4Address);
        if (ipv4AssociativeTrieNode != null) {
            System.out.println("\nfound: " + ipv4AssociativeTrieNode.toTreeString(true, false));
            // ipv4AssociativeTrieNode is a linked list, go to the end
            while(true) {
            	IPv4AssociativeTrieNode<Info> nextNode = ipv4AssociativeTrieNode.getLowerSubNode();
                if(nextNode == null) {
                    nextNode = ipv4AssociativeTrieNode.getUpperSubNode();
                    if(nextNode == null) {
                        break;
                    }
                }
            	ipv4AssociativeTrieNode = nextNode;
            }
            // go back up until we've found the result
            do {
            	Info value = ipv4AssociativeTrieNode.getValue();
            	if(value != null && value.getBool()) { // non-added nodes (eg 1.1.2.0/23) will have no value
            		return value;
            	}
            	ipv4AssociativeTrieNode = ipv4AssociativeTrieNode.getParent();
            } while(ipv4AssociativeTrieNode != null);
        }
        return null;
    }
    
    static Info findIPInfoNew2(IPv4Address iPv4Address) {
        IPv4AddressAssociativeTrie.IPv4AssociativeTrieNode<Info> ipv4AssociativeTrieNode = trie.elementsContaining(iPv4Address);
        Info result = null;
        if (ipv4AssociativeTrieNode != null) {
             System.out.println("\nfound: " + ipv4AssociativeTrieNode.toTreeString(true, false));
             // ipv4AssociativeTrieNode is a linked list, grab valid values while going to the end
             while(true) {
                Info value = ipv4AssociativeTrieNode.getValue();
                if(value != null && value.getBool()) { // non-added nodes (eg 1.1.2.0/23) will have no value
                    result = value;
                }
                IPv4AssociativeTrieNode<Info> nextNode = ipv4AssociativeTrieNode.getLowerSubNode();
                if(nextNode == null) {
                    nextNode = ipv4AssociativeTrieNode.getUpperSubNode();
                    if(nextNode == null) {
                        break;
                    }
                }
                ipv4AssociativeTrieNode = nextNode;
            }
        }
        return result;
    }
}

from ipaddress.

Question: longestPrefixMatch in a loop based on condition about ipaddress HOT 4 CLOSED

Comments (4)

Related Issues (20)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent