~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2011-04-07 10:36:24 UTC
  • mfrom: (5764 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5766.
  • Revision ID: john@arbash-meinel.com-20110407103624-n76g6tjeqmznwdcd
Merge bzr.dev 5764 to resolve release-notes (aka NEWS) conflicts

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
18
18
"""B+Tree indices"""
19
19
 
20
20
import cStringIO
21
 
from bisect import bisect_right
 
21
 
 
22
from bzrlib.lazy_import import lazy_import
 
23
lazy_import(globals(), """
 
24
import bisect
22
25
import math
23
26
import tempfile
24
27
import zlib
 
28
""")
25
29
 
26
30
from bzrlib import (
27
31
    chunk_writer,
1047
1051
        # iter_steps = len(in_keys) + len(fixed_keys)
1048
1052
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1049
1053
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1050
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1054
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1051
1055
        # elif bisect_steps < iter_steps:
1052
1056
        #     offsets = {}
1053
1057
        #     for key in in_keys: