Java - Structure de données appropriée pour intervalle de recherche

Si vos intervalles sont mutuellement exclusives, une carte triée (java.util.treemap) à l'aide d'un comparateur sur le dernier membre de l'intervalle et à l'aide de PremièreKeKe sur une tarotte sur l'élément recherché doit fonctionner correctement.

Si les intervalles peuvent se chevaucher, vous avez besoin d'un arbre de segment (http://fr.wikipedia.org/wiki/segment_tree), dont il n'y a pas de mise en œuvre dans la bibliothèque standard.

Votre question n'est pas tout à fait claire, en particulier ce que vous entendez par les valeurs 1, 2, 3, 4. mais si vous souhaitez une structure de données qui contient les limites d'un intervalle et vérifie si un numéro est compris, puis faire un! Comme ceci: xxx

et utilisez-le: xxx

J'utiliserais cette approche:

import static org.hamcrest.core.Is.is;
import static org.junit.Assert.assertThat;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class IntervalsTest {


    @Test
    public void shouldReturn1() {
        Intervals intervals = new Intervals();

        intervals.add(1, 10, 100);
        intervals.add(2, 200, 500);

        int result = intervals.findInterval(15);

        assertThat(result, is(1));

    }

    @Test
    public void shouldReturn2() {
        Intervals intervals = new Intervals();

        intervals.add(1, 10, 100);
        intervals.add(2, 200, 500);

        int result = intervals.findInterval(201);

        assertThat(result, is(2));

    }
}

class Range {

    private final int value;

    private final int lowerBound;

    private final int upperBound;


    Range(int value, int lowerBound, int upperBound) {
        this.value = value;
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
    }

    boolean includes(int givenValue) {
        return givenValue >= lowerBound && givenValue <= upperBound;

    }

    public int getValue() {
        return value;
    }
}

class Intervals {

    public List<Range> ranges = new ArrayList<Range>();

    void add(int value, int lowerBound, int upperBound) {
        add(new Range(value, lowerBound, upperBound));
    }

    void add(Range range) {
        this.ranges.add(range);
    }

    int findInterval(int givenValue) {
        for (Range range : ranges) {
            if(range.includes(givenValue)){
                return range.getValue();
            }
        }

        return 0; // nothing found // or exception
    }
}

Utilisez HASHMAP (rapide, plus de mémoire) ou liste (plus lente, petite mémoire). Je vous fournis les deux solutions ci-dessous:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Interval {

    private int begin;
    private int end;
    // 1, 2, 3, 4
    private int value;

    public Interval(int begin, int end, int value) {
        this.begin = begin;
        this.end = end;
        this.value = value;
    }

    public int getBegin() {
        return begin;
    }

    public void setBegin(int begin) {
        this.begin = begin;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public boolean contains(int number) {
        return (number > begin - 1) && (number < end + 1);
    }
}

public class IntervalSearch {

    // more memory consuming struct, fastest
    Map<Integer, Interval> intervalMap = new HashMap<Integer, Interval>();

    // less memory consuming, little slower
    List<Interval> intervalList = new ArrayList<Interval>();

    private boolean fastMethod = true;

    public IntervalSearch(boolean useFastMethod) {
        this.fastMethod = useFastMethod;
    }

    public Integer search(int number) {
        return fastMethod ? searchFast(number) : searchSlow(number);
    }

    private Integer searchFast(int number) {
        return intervalMap.get(number).getValue();
    }

    private Integer searchSlow(int number) {
        for (Interval ivl : intervalList) {
            if (ivl.contains(number)) {
                return ivl.getValue();
            }
        }
        return null;
    }

    public void addInterval(Integer begin, Integer end, Integer value) {
        Interval newIvl = new Interval(begin, end, value);
        if (fastMethod) {
            addIntervalToMap(newIvl);
        } else {
            addIntervalToList(newIvl);
        }
    }

    private void addIntervalToList(Interval newIvl) {
        intervalList.add(newIvl);
    }

    private void addIntervalToMap(Interval newIvl) {
        for (int i = newIvl.getBegin(); i < newIvl.getEnd() + 1; i++) {
            intervalMap.put(i, newIvl);
        }
    }

    public boolean isFastMethod() {
        return fastMethod;
    }
}

Utilisez Treemap, qui est NavigaBablap (Java 6 ou supérieur).

Supposons que vous ayez des entrées clé-> valeur code> (10-> 1, 100-> 1, 200- > 2, 500-> 2, 1000-> 3, 5000-> 3) code> p>

plancher (15) code> retournera 10-> 1 p>

plailingientry (15) code> retournera 100-> 1 code> p>

avec ceci, vous pouvez déterminer le nombre d'intervalles de 15, qui est 1. Vous pouvez également déterminer si un numéro est compris entre intervalles. P>

EDIT: Exemple ajouté P>

    TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
    map.put(10, 1);
    map.put(100, 1);
    map.put(200, 2);
    map.put(500, 2);
    map.put(1000, 3);
    map.put(5000, 3);
    int lookingFor = 15;
    int groupBelow = map.floorEntry(lookingFor).getValue();
    int groupAbove = map.ceilingEntry(lookingFor).getValue();
    if (groupBelow == groupAbove) {
        System.out.println("Number " + lookingFor + " is in group " + groupBelow);
    } else {
        System.out.println("Number " + lookingFor + 
                " is between groups " + groupBelow + " and " + groupAbove);
    }