Python Forum

Python Forum > Python Coding > General Coding Help > a dictionary of ranges
Full Version: a dictionary of ranges
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2

Skaperen

Nov-29-2017, 01:53 AM
looking up numbers in a very sparse unordered collection is easy with a dictionary.  but what about a sparse collection of ranges?  this would be a set of numbers that are either present or absent where a range is a span of values than might number in excess of existing memory but the number of ranges boundaries do not.  an example of this can be indexing a collection by floating point ranges.  let's say you add the range 4.5 to 5.25 to such a collection.  now is 4.500000000001 in the range? clearly you will not be putting trillions of individual numbers in the object.  what if the range is a range of ints from 4500000000000000 to 6000000000000000?

so what i am looking for is an object class that can allow the insertion of ranges into each instance where the supported type for range indexing is anything that support < or > comparison.  it needs to support overlapping replacement insertions, as well as deletions.  each insert will also have a value to get back out if th requested index is inside that ramge.

Windspar

Nov-29-2017, 01:45 PM
example
# width is how many floating point
# step must be an integer not a float
def float_range(width, start, end=None, step=1):
    float_width = 10 ** width
    if end is None:
        end = start * float_width
        start = 0.1 * float_width
    else:
        start = start * float_width
        end = end * float_width

    # return range(start, end, step)
    while start < end:
        yield start / float_width
        start += step


if __name__ == '__main__':
    for i in float_range(2, 4.5, 5.0):
        print(i)
        if i == 4.7: break
example class form
class FloatRange:
    # width is how many floating point
    # step must be in integer
    def __init__(self, width, start, end=None, step=1):
        self.width = 10 ** width
        if end is None:
            self.start = int(0.1 * self.width)
            self.end = int(start * self.width)
        else:
            self.start = int(start * self.width)
            self.end = int(end * self.width)

        self.book = self.start, self.end, step
        self.step = step

    def __iter__(self):
        while self.start < self.end:
            yield self.start / self.width
            self.start += self.step

    def __lt__(self, value):
        return value * self.width < self.book[0]

    def __gt__(self, value):
        return value * self.width > self.book[1]

    # special check to see if variabel inside range
    def __eq__(self, value):
        return self.book[1] > int(value * self.width) >= self.book[0]

if __name__ == '__main__':
    rangef = FloatRange(2, 4.5, 4.7)
    print(rangef == 4.61)
    for i in rangef:
        print(i)

buran

Nov-29-2017, 02:47 PM
@Windspar:
you should implement special method __contains__ to check membership, not __eq__
https://docs.python.org/3/reference/data...iner-types

Windspar

Nov-29-2017, 04:13 PM
@buran Thanks
small improvement
def __contains__(self, value):
        return int(value * self.width) in range(*self.book)

Windspar

Nov-29-2017, 09:23 PM
Working with floats are annoying. So I change to Fraction.
from fractions import Fraction

def fract10(value, width):
    return Fraction(value, 10 ** width)

class FloatRange:
    def __init__(self, width, start, start_width, end=None, end_width=None, step=1):
        self.width = Fraction(10 ** width, 1)
        if end is None:
            self.start_width(10 ** self.width, 1)
            self.end_width = Fraction(10 ** start_width, 1)
            self.end = Fraction(start, 10 ** start_width)
            self.start = Fraction(1, self.width)
        else:
            self.start_width = Fraction(10 ** start_width, 1)
            self.end_width = Fraction(10 ** end_width, 1)
            self.start = Fraction(start, 10 ** start_width)
            self.end = Fraction(end, 10 ** end_width)

        self.step = Fraction(step, 10 ** width)
        self.start_range = self.start, self.end, self.step

    def __iter__(self):
        while self.start < self.end:
            yield float(self.start / self.width * self.start_width)
            self.start += self.step

    def __lt__(self, value, width):
        return Fraction(value, 10 ** width) <= self.start_range[0]

    def __gt__(self, value, width):
        return Fraction(value, 10 ** width) > self.start_range[1]

    def __contains__(self, value_tup):
        value, width = value_tup
        v = int(Fraction(value, 10 ** width) * self.width)
        s = int(self.start_range[0] * self.start_width)
        e = int(self.start_range[1] * self.end_width)
        step = int(self.step * self.width)
        return v in range(s, e, step) # or
        #return e > v >= s


if __name__ == "__main__":
    frange = FloatRange(3, 450, 2, 470 , 2)
    print((452, 2) in frange)
    print((452, 3) in frange)

    #for i in frange:
    #    print(i)

Skaperen

Nov-30-2017, 02:17 AM
in English, the plural form of range is ranges.  i'm looking for a class that supports more than one range.  an instance of such a class should start empty and have a default value (can be specified or be None if not specified).  i then add range 2,3.5 to have a value of 'foo'.  i then add range 4.5,6 to have a value of 'bar'.  i then lookup 4.75 and get 'bar'.  i then delete range 3,5.  i repeat lookup 4.75 and now i get the default value.  so delete is just a case of adding a range of the default value.  this is a "flat" range container.

a "stack" range container would return a list of values based on the inserts being stacked over and the lookup seeing the stack.  so in the above i would get [None, 'bar', None].  a special smash function would mash down everything in the range specified so that if range 3,5 is smashed (a true delete) then looking up 4.75 returns [None].

there would also be network address variants of those that can be optimized and support high speed route tables.

maybe these have already been done?

buran

Nov-30-2017, 04:52 AM
Then start coding whatever you want.

Windspar

Nov-30-2017, 05:56 PM
@Skaperen Thank to you. I learn how to work with floats as Fraction. Learn how to convert them.
Example my float range
from fractions import Fraction

class FloatRange:
    # width = how many float points
    def __init__(self, width, start, end, step=1):
        self.width_size = width
        self.width = Fraction(10 ** width, 1)
        if end is None:
            self.end = self.num_to_fraction(start)
            self.start = Fraction(1, 10 ** width)
        else:
            self.start = self.num_to_fraction(start)
            self.end = self.num_to_fraction(end)

        self.step = Fraction(step, 10 ** width)
        self.float_range = self.start, self.end, self.step

    def num_to_fraction(self, pynum):
        if type(pynum) is float:
            f = str(pynum)
            i = f.find('.') + 1
            return Fraction(int(f.replace('.', '')), 10 ** (len(f) - i))
        return Fraction(pynum, 1)

    def convert(self, value):
        str_value = str(value)
        index = str_value.find('.') + 1
        width = len(str_value) - index
        if width < self.width_size:
            return int(str_value.replace('.','')) * (10 ** (self.width_size - width))
        elif index == 0:
            return int(str_value.replace('.','')) * (10 ** self.width_size)
        return int(str_value.replace('.',''))

    def __iter__(self):
        while self.start < self.end:
            yield float(self.start)
            self.start += self.step

    def __lt__(self, value):
        return self.num_to_fraction(value) > self.float_range[1]

    def __gt__(self, value):
        return self.num_to_fraction(value) < self.float_range[0]

    def __contains__(self, value):
        v = self.convert(value)
        s = int(self.float_range[0] * self.width)
        e = int(self.float_range[1] * self.width)
        st = int(self.float_range[2] * self.width)
        return v in range(s, e, st) # or
        #return s <= v < e

if __name__ == "__main__":
    for i in range(1,4):
        frange = FloatRange(i, 4.5, 4.7)
        print("\n ** FloatRange contains float point", i, "**")
        print(452 in frange)
        print(45.2 in frange)
        print(4.52 in frange)
        print(4.521 in frange)

    print("\n ** Less than and Greater than test **")
    frange = FloatRange(2, 4.5, 4.7)
    print(4.4 < frange)
    print(4.6 < frange)
    print(4.6 > frange)
    print(4.8 > frange)

    print("\n ** Output test **")
    for i in frange:
        print(i)
Are you looking for something like this ?
from fractions import Fraction

class Ranges:
    def __init__(self):
        self.range_list =

    def add(self, start, end):
        for index, item in enumerate(self.range_list):
            if item is None:
                self.range_list[index] = (start, end)
                return

        self.range_list.append((start, end))

    def num_to_fraction(self, pynum):
        if type(pynum) is float:
            f = str(pynum)
            i = f.find('.') + 1
            return Fraction(int(f.replace('.', '')), 10 ** (len(f) - i))

        return Fraction(pynum, 1)

    def fetch(self, value):
        for index, group in enumerate(self.range_list):
            if group is None:
                continue
            elif group[0] <= value < group[1]:
                return index, group

        return None, None

    def run(self, index, width):
        if self.range_list[index] is None:
            return

        step = Fraction(1, 10 ** width)
        width = Fraction(10 ** width, 1)
        start, end = map(self.num_to_fraction, self.range_list[index])
        while start < end:
            yield float(start)
            start += step

    def run_combine(self, index, width, combine):
        for i in self.run(index, width):
            yield combine + str(i)

    def run_ip4(self, index, width, index2, width2):
        for i in self.run(index, width):
            for j in self.run(index2, width2):
                yield str(i) + '.' + str(j)

    def smash(self, index):
        self.range_list[index] = None

    def __str__(self):
        line =  "Ranges ["
        for r in self.range_list:
            if r is None:
                line += "None, "
            else:
                line += "({0}, {1}), ".format(*r)

        return line[:-2] + ']'


if __name__ == '__main__':
    my_range = Ranges()
    my_range.add(17.21, 17.27)
    my_range.add(2, 3.5)
    my_range.add(4.5, 6)

    for i in my_range.run_combine(1, 1, "192.168."):
        print(i)

    print()
    for i in my_range.run_ip4(0, 2, 2, 1):
        print(i)

Skaperen

Dec-01-2017, 04:10 AM
(Nov-30-2017, 04:52 AM)buran Wrote: [ -> ]Then start coding whatever you want.

this is one of those things i perceive as being too big/complex for me to do.  so i will use what other people have made or i will have nothing to use.
@Windspar

how does that handle overlapping ranges?  can it handle ranges between strings like ('bar','foo')?
i would also want to compare two ranges objects to know if they represent the same set of ranges (with the same value for each range) regardless of how different overlappings produce these ranges.

and much like a dictionary can produce an iterable, i want to have that.  while dict.items() would return an iterable of (key,value), ranges.items() would return an iterable of (from,to,value).  either of these can be sorted.

and adding 2 ranges that are exactly adjacent with the same value should (as seen in .items()) become a combined range.
oh, instead of (from,to,value) it could be (range,value).  there would be a range class that should be a simple class and then the ranges class that manges many.
then i will get more demanding and want 2D and 3D ranges.  or maybe more elaborate shapes.  imagine a class where i can merge a cube of 'purple' and a sphere of 'red' and a thing of green defined by a shape class object.

Windspar

Dec-02-2017, 07:40 PM
Here a start.
float_range.py . Some small changes
from fractions import Fraction

class FloatRange:
    # width = how many float points
    def __init__(self, width, start, end, step=1):
        self.base = width, start, end, step
        self.width = Fraction(10 ** width, 1)
        if end is None:
            self.end = self.num_to_fraction(start)
            self.start = Fraction(1, 10 ** width)
        else:
            self.start = self.num_to_fraction(start)
            self.end = self.num_to_fraction(end)

        self.step = Fraction(step, 10 ** width)
        self.float_range = self.start, self.end, self.step

    def num_to_fraction(self, pynum):
        if type(pynum) is float:
            f = str(pynum)
            i = f.find('.') + 1
            return Fraction(int(f.replace('.', '')), 10 ** (len(f) - i))
        return Fraction(pynum, 1)

    def convert(self, value):
        str_value = str(value)
        index = str_value.find('.') + 1
        width = len(str_value) - index
        if width < self.base[0]:
            return int(str_value.replace('.','')) * (10 ** (self.base[0] - width))
        elif index == 0:
            return int(str_value.replace('.','')) * (10 ** self.base[0])
        return int(str_value.replace('.',''))

    def __iter__(self):
        self.start = self.float_range[0]
        while self.start < self.end:
            yield float(self.start)
            self.start += self.step

    def __lt__(self, value):
        return self.num_to_fraction(value) > self.float_range[1]

    def __gt__(self, value):
        return self.num_to_fraction(value) < self.float_range[0]

    def with_in(self, value):
        s, e, st = self.float_range
        if type(value) is FloatRange:
            s2, e2, st2 = value.float_range
            if self.with_in(s2) or self.with_in(e2) or value.with_in(s) or value.with_in(e):
                return True
            return False
        else:
            v = self.num_to_fraction(value)
            return  s <= v < e

    def __contains__(self, value):
        v = self.convert(value)
        s = int(self.float_range[0] * self.width)
        e = int(self.float_range[1] * self.width)
        st = int(self.float_range[2] * self.width)
        return v in range(s, e, st)

    def __repr__(self):
        line = "FloatRange: {0}Width: {1}, Start: {2}, End: {3}, Step: {4}{5}"
        return line.format('{', *self.base, '}')

if __name__ == "__main__":
    for i in range(1,4):
        frange = FloatRange(i, 4.5, 4.7)
        print("\n ** FloatRange contains float point", i, "**")
        print(452 in frange)
        print(45.2 in frange)
        print(4.52 in frange)
        print(4.521 in frange)

    print("\n ** Less than and Greater than test **")
    frange = FloatRange(2, 4.5, 4.7)
    print(4.4 < frange)
    print(4.6 < frange)
    print(4.6 > frange)
    print(4.8 > frange)

    print("\n ** Within test **")
    a = FloatRange(1, 4.6, 5.0)
    b = FloatRange(3, 4.6, 5.0)
    c = FloatRange(2, 4.0, 5.0)
    d = FloatRange(2, 4.9, 5.0)
    print(a.with_in(frange))
    print(b.with_in(frange))
    print(c.with_in(frange))
    print(d.with_in(frange))

    print("\n ** Output test **")
    for i in frange:
        print(i)
ranges.py
from float_range import FloatRange

class Ranges:
    def __init__(self):
        self.ranges = {}

    def items(self):
        return self.ranges.items()

    def keys(self):
        return self.ranges.keys()

    def values(self):
        return self.ranges.values()

    def __getitem__(self, key):
        return self.ranges[key]

    def __delitem__(self, key):
        del self.ranges[key]

    def add(self, key_name, width, start, end=None, step=1):
        if end is None:
            self.ranges[key_name] = FloatRange(width, start)
        else:
            self.ranges[key_name] = FloatRange(width, start, end, step)

    def fetch(self, value, value_end=None):
        return_keys = []
        if value_end is None:
            for key, f_range in self.items():
                if value in f_range:
                    return_keys.append(key)
        else:
            v_range = FloatRange(0, value, value_end)
            for key, f_range in self.items():
                if f_range.with_in(v_range):
                    return_keys.append(key)

        return return_keys

    def smash(self, start, end=None):
        del_keys = []
        if end is None:
            for key, f_range in self.items():
                if start in f_range: # or with_in
                    del_keys.append(key)
        else:
            v_range = FloatRange(0, start, end)
            for key, f_range in self.items():
                if v_range.with_in(f_range):
                    del_keys.append(key)

        for key in del_keys:
            del self.ranges[key]

    def merge(self, key1, key2):
        return FloatRange(
            max(self.ranges[key1].base[0], self.ranges[key2].base[0]),
            min(self.ranges[key1].base[1], self.ranges[key2].base[1]),
            max(self.ranges[key1].base[2], self.ranges[key2].base[2]),
            min(self.ranges[key1].base[3], self.ranges[key2].base[3]) )


if __name__ == '__main__':
    m_range = Ranges()
    m_range.add('foo', 1, 2, 3.5)
    m_range.add('bar', 1, 4.5, 6)
    m_range.add('foo2', 1, 7.5, 10)
    for i in m_range['foo']:
        print(i)

    print(m_range.keys())

    print("\n ** Merge Test **")
    print(m_range.merge('foo', 'bar'))

    print("\n ** Smash Test **")
    m_range.smash(3, 5)
    print(m_range.keys())

    print("\n ** Fetch Test **")
    m_range.add('foo', 1, 2, 3.5)
    m_range.add('bar', 1, 4.5, 6)
    print(m_range.fetch(3, 5))
Pages: 1 2
Python Forum > Python Coding > General Coding Help > a dictionary of ranges