CODEWITHSUNDEEP
javaalgorithmdata-structures
chiru
chiru

Reputation: 832

How to store IP Address range vs location

I have a problem i have ip address range

IP                                    Location
10.1.100.200- 10.1.100.800              x
10.1.101.200- 10.1.101.800              Y
10.1.102.200- 10.1.102.800              Z etc etc

Now given an ip I want to find location like eg 10.1.101.270 should give Y I dont want the code I am trying to use best algorithm to store and search them? How to approach this

B+Tree?

Upvotes: 0

Views: 1519

Answers (3)

Justin
Justin

Reputation: 4216

What about a Interval Tree or a Segment Tree? Interval Tree should be better if your "set" of IP address ranges are dynamic; Segment Tree should be better if the ranges are static and it is said to be better with "stabbing queries" which it seems like you are performing.

Interval Tree:

In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries.

Query time of O(log n)

Segment Tree:

In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point.

Query a point in O(log n + k), k being the number of retrieved intervals or segments.

Implementations:

Segment tree implementation in Java.

Interval Tree implementation in Java.

Upvotes: 4

Sage
Sage

Reputation: 15418

use, TreeMap<K, V>: You can store the start range to map the location. TreeMap uses Red-Black tree data structure for ordering the entry. Where the key finding operations including inseritng and removing are O(log n). This map provides two useful function:

higherEntry(K key): Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

lowerEntry(K key): Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

While searching with an specific ip as key, You can try find this left and right entry containing the start ip-range as key and their corresponding location as value. Compare against these ip-range with the searching key to determine the value V(location).

Upvotes: 4

Changgeng
Changgeng

Reputation: 588

I would use a TreeMap as Sage suggested. Assume there will be no overlap.

public class IPSegment implements Comparable<IPSegement>{

    private long start;
    private long end;
    public IPSegement(String startIp, String endIp){
         //convert the ip address to a 32 bit integer. 

    }
    public int compareTo(IPSegement other){

         return this.start - other.start;  //assume no overlap
    }

    public int equals(IPSegement other){
      // check both start and end
    }

    public boolean contains(long ip){
      //check whether 'ip' is in this range
    }
}


public class IPSegmentMap{
     private TreeMap<IPSegement> map = new TreeMap<IPSegement>();
     public void add(String start, String end, String location){
          //...
     }

     public String find(String ipAddress){
         long ip = convertIPtoInt(ipAddress);
         IPSegement request = new IPSegement(ip,ip);
         IPSegement exist = map.floorKey(request);
         if(exist.contains(ip)){
             return map.get(exist);
         }

     }

}

Upvotes: 1

Related Questions