bsearch.py

该软件根据网络数据生成NetFlow记录。NetFlow可用于网络规划、负载均衡、安全监控等

#! /usr/bin/env python
###############################################################################
#                                                                             #
#   Copyright 2005 University of Cambridge Computer Laboratory.               #
#                                                                             #
#   This file is part of Nprobe.                                              #
#                                                                             #
#   Nprobe is free software; you can redistribute it and/or modify            #
#   it under the terms of the GNU General Public License as published by      #
#   the Free Software Foundation; either version 2 of the License, or         #
#   (at your option) any later version.                                       #
#                                                                             #
#   Nprobe is distributed in the hope that it will be useful,                 #
#   but WITHOUT ANY WARRANTY; without even the implied warranty of            #
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             #
#   GNU General Public License for more details.                              #
#                                                                             #
#   You should have received a copy of the GNU General Public License         #
#   along with Nprobe; if not, write to the Free Software                     #
#   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA #
#                                                                             #
###############################################################################


##############################################################################
## 
##
## 
## 
##
## 

############################################################################ 
############################################################################

import string
from sys import argv
import getopt 
import sys

############################################################################ 
############################################################################

def get_data(file):
    print 'foo'
    f = open(file, 'r')
    data = []
    n = 0
    while 1:
	s = f.readline()
	if not len(s):
	    break
	if s[0] == '#' or s[0] == ' ' or s[0] =='\n':
	    #print 'comment'
	    continue
	vs = string.split(s)
	data.append(string.atof(vs[1]))
	n = n + 1

    print 'read %d data points' % (n)

    return (data, n)
 
############################################################################

class NotInRange:
    pass
 
############################################################################

def find_point_after(val, data, i1, i2):

    l = i1
    r = i2

    print data

    if i1 == i2:
	# single point
	if val != data[i1]:
	    raise NotInRange
	else:
	    return i1

    while r > l:
	p = (l+r)/2
	#print 'l=%d r=%d p=%d' % (l, r, p)
	x = data[p]
	if val < x:
	    r = p
	else:
	    l = p
	if r - l == 1:
	    if data[r] < val or val < data[l]:
		raise NotInRange
	    if data[l] <= val <= data[r]:
		if data[l] <= val < data[r]:
		    return r
		else:
		    return min([i2, r+1])
		
############################################################################

def find_point_before(val, data, i1, i2):

    l = i1
    r = i2

    print data
    #raw_input('...')

    if i1 == i2:
	# single point
	if val != data[i1]:
	    raise NotInRange
	else:
	    return i1

    while r > l:
	p = (l+r)/2
	#print 'l=%d r=%d p=%d' % (l, r, p)
	x = data[p]
	if val < x:
	    r = p
	else:
	    l = p
	if r - l == 1:
	    if data[r] < val or val < data[l]:
		raise NotInRange
	    if data[l] <= val <= data[r]:
		if data[l] < val <= data[r]:
		    return l
		else:
		    return max([l-1, i1])
	#raw_input('...')
		
############################################################################

def main():
    print main
    try:
	optlist, args = getopt.getopt(sys.argv[1:], '')

    except getopt.error, s:
	print 'bsearch: ' + s
	usage()
	sys.exit(1)

    data, n = get_data(args[0])
    data.sort()
    val = string.atof(args[1])

    try:
	indx = find_point_after(val, data, 0, n-1)
	print indx
	print 'point following %.3f = %.3f indx=%d)' % (val, 
					data[indx], indx)
    except NotInRange:
	print 'Value %.3f not in range' % (val)

    try:
	indx = find_point_before(val, data, 0, n-1)
	print indx
	print 'point before %.3f = %.3f indx=%d)' % (val, 
					data[indx], indx)
    except NotInRange:
	print 'Value %.3f not in range' % (val)
		
############################################################################


# Call main when run as script
if __name__ == '__main__':
        main()