get-routes.js

const fs = require('fs')
const http = require('http');

// https://ftp.arin.net/pub/stats/arin/delegated-arin-extended-latest
// https://ftp.apnic.net/stats/apnic/delegated-apnic-latest

/**
 * get content from URL
 * @param {String} url  URL
 * @returns {Promise<String>} the response body of input URL
 */
async function get(url) {
  return new Promise((resolve, reject) =>
    http.get(url, res => {
      if (res.statusCode === 200) {
        let data = '';
        res.on('data', chunk => data += chunk)
        res.on('end', () => resolve(data))
        res.on('error', e => reject(e))
      } else {
        reject(`Get ${url} status code: ${res.statusCode}.`)
      }
    })
  );
}

/**
 * get content from local file path
 * @param {String} path local file path
 * @returns {Promise<String>} the file content of input file path
 */
async function readFile(path) {
  return new Promise((resolve, reject) => {
    fs.readFile(path, (err, data) => {
      if (err) {
        reject(err)
      } else {
        resolve(data.toString())
      }
    })
  })
}

/**
 * The marks for {IPNode}s
 */
const Marks = {
  Empty: 0,
  CN: 1,
  US: 2,
};

class Route {
  ip = 0
  range = 0
  mark = Marks.CN

  constructor(ip = 0, range = 0, mark = Marks.CN) {
    this.ip = ip
    this.range = range
    this.mark = mark
  }
}

class Solution {
  count = 0x7fff
  childrenMarks = [0, 0]
}


/**
 * The IP Node
 */
class IPNode {

  /**
   * route mark
   * @type {Number}
   */
  mark = Marks.Empty;

  /**
   * two children of the current node
   * @type {IPNode[]}
   */
  children = [null, null]

  /**
   * the dp solutions
   * @type {Solution[]}
   */
  solutions = [new Solution(), new Solution(), new Solution()]

  constructor() {}
}

/**
 * add IP to the tree
 * @param {Number} ip ip of an integer 
 * @param {Number} depth the tree depth
 * @param {IPNode} node node of current IP
 * @param {Number} range the mask range
 * @param {Number} mark the mark of the current route
 */
function add(ip, depth, node, range, mark) {
  if (node.mark) {
    console.log('err', intToIPv4(ip), depth, range, mark, node.mark)
    process.exit(1)
    return
  }
  if (depth === range) {
    node.mark = mark
    return
  }
  const next = (ip & (1 << (31 - depth))) ? 1 : 0;
  if (!node.children[next]) {
    node.children[next] = new IPNode()
  }
  add(ip, depth + 1, node.children[next], range, mark);
}

/**
 * IP addr to ip integer
 * @param {String} ip ip addr string format
 * @returns {Number} the integer of the IP
 */
function ipv4ToInt(ip) {
  return ip.split('.')
    .map(v => parseInt(v, 10))
    .reduce((acc, v) => (acc << 8) | v, 0)
}

/**
 * 
 * @param {Number} ip 
 * @returns {String}
 */
function intToIPv4(ip) {
  const items = []
  for (let i = 0; i < 4; i++) {
    items.push(ip & 0xff)
    ip >>>= 8
  }
  return items.reverse().map(v => v.toString(10)).join('.')
}

/**
 * mark the tree by file content
 * @param {String} file path of the file
 * @param {Number} mark mark of the ip
 * @param {String} countryCode the code of the country
 * @param {IPNode} root 
 */
async function markByFile(file, mark, countryCode, root) {
  const content = await readFile(file)
  content.split('\n')
    .map(l => l.trim())
    .filter(l => !l.startsWith('#'))
    .map(l => l.split('|'))
    .map(([, country, type, addr, count]) => ({
      country, type, addr, count,
    }))
    .filter(({country, type}) => country === countryCode && type === 'ipv4')
    .forEach(({addr, count}) => {
      const range = Math.floor(32 - Math.log2(count))
      const ip = ipv4ToInt(addr)
      // console.log(countryCode, addr, ip, range)
      add(ip, 0, root, range, mark)
    })
}



/**
 * dynamic programming to the the most optimized tree
 * @param {IPNode} node
 * @returns {Solution[]}
 */
function dp(node) {
  if (!node) {
    const emptyMarkSolution = [new Solution(), new Solution(), new Solution()]
    emptyMarkSolution[0].count = 0
    return emptyMarkSolution
  }

  if (node.mark) {
    node.solutions[node.mark].count = 1
    return node.solutions
  }

  const leftChildSolutions = dp(node.children[0])
  const rightChildSolutions = dp(node.children[1])

  for (let currentMark = 1; currentMark < 3; currentMark++) {
    for (let leftChildMark = 0; leftChildMark < 3; leftChildMark++) {
      for (let rightChildMark = 0; rightChildMark < 3; rightChildMark++) {
        let count = leftChildSolutions[leftChildMark].count + rightChildSolutions[rightChildMark].count;
        if (leftChildMark === rightChildMark && currentMark === leftChildMark) {
          count --
        } else if (currentMark !== leftChildMark && currentMark !== rightChildMark) {
          count ++
        }
        if (count < node.solutions[currentMark].count) {
          node.solutions[currentMark].count = count
          node.solutions[currentMark].childrenMarks = [leftChildMark, rightChildMark]
        }
      }
    }
  }
  return node.solutions;
}

/**
 * get the final result form IP tree
 * @param {IPNode} node 
 * @param {Number} ip 
 * @param {Number} depth 
 * @param {Number} mark 
 * @param {Number} parentMark 
 * @param {Route[]} result 
 */
function getResult(node, ip, depth, mark, parentMark, result) {
  if (!node) {
    return
  }

  if (mark !== parentMark) {
    result.push(new Route(ip, depth, mark))
  }

  const {childrenMarks: [leftMark, rightMark], count} = node.solutions[mark]

  getResult(node.children[0], ip,                       depth + 1, leftMark,  mark, result)
  getResult(node.children[1], ip | (1 << (31 - depth)), depth + 1, rightMark, mark, result)
}

async function main() {
  const root = new IPNode()
  await markByFile('/Users/winguse/Downloads/delegated-apnic-latest.txt', Marks.CN, 'CN', root)
  await markByFile('/Users/winguse/Downloads/delegated-arin-extended-latest.txt', Marks.US, 'US', root) 
  dp(root)
  const mark = root.solutions[Marks.CN].count < root.solutions[Marks.US].count ? Marks.CN : Marks.US
  const solution = root.solutions[mark];
  const result = []
  result.push(new Route(0, 0, mark))
  getResult(root.children[0], 0 << 31, 1, solution.childrenMarks[0], mark, result)
  getResult(root.children[1], 1 << 31, 1, solution.childrenMarks[1], mark, result)

  result.sort(({range: a}, {range: b}) => b - a).forEach(({ip, mark, range}) => {
    console.log(`${intToIPv4(ip)}/${range} -> ${mark === Marks.CN ? 'CN' : 'US'}`)
  })

  console.log(root.solutions)
  console.log(result.length)
}

main()