CODEWITHSUNDEEP
javaperformancecollectionsiterator
ApollonDigital
ApollonDigital

Reputation: 973

Java Iterator start from specific element of sorted set

I have a sorted set in Java (eg a TreeSet). I want to have an iterator starting from a specific element of the tree and be able to go to the next or previous element (in the order of sorting).

Is there any idea of how to do this without implementing my own data structure??

Thanks

EDIT:

I forgot to mention that I want to do it with a naive way (if there is any) since I care about perfomance. If I had access to the implementation of the tree it would take O(1) time to do that. I want something similar.

Also feel free to suggest other (3rd party) implementations of Sorted Trees in java that supports this.

Upvotes: 6

Views: 4185

Answers (5)

Raedwald
Raedwald

Reputation: 48682

To go forward from element x of SortedSet s, use s.tailSet(x).iterator().

To go backwards from element x of NavigableSet s use s.descendingSet().tailSet(x).iterator().

tailSet() and descendingSet() create views of the original set, s. Their implementation therefore can not create copies of the original set (otherwise the copy would become out of date if the viewed set were changed), and so will have O(1) performance.

A TreeSet is a NavigableSet and thus a SortedSet.

Upvotes: 4

Hoopje
Hoopje

Reputation: 12932

The iterator returned by a TreeSet does not support going forwards and backwards. So if going forwards and backwards is a hard requirement, you will have to create a list first and obtain a list iterator from it:

List<T> list = new ArrayList<>(treeSet);
int index = list.indexOf(object);
ListIterator<T> iterator = list.listIterator(index);

If you want to use the iterator to modify the set, this is not an option because, obviously, you would modify the list rather than the set.

If going backwards is not a hard requirement, you can create a subset of your TreeSet and obtain an iterator from that:

Navigable<T> subset = treeSet.tailSet(object);
Iterator<T> iterator = subset.iterator();

This is quite fast, because tailSet returns a view of the given subset, so it doesn't require making a copy of part of the set.

Upvotes: 1

Eldius
Eldius

Reputation: 320

You can try something like this:

List<Long> list = Arrays.asList(1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 0L);
TreeSet<Long> tree = new TreeSet<>(list);
tree.tailSet(4L).iterator()

Upvotes: 0

MK.
MK.

Reputation: 34587

  TreeSet<Integer> set = new TreeSet<>(IntStream.range(0, 10).boxed().collect(Collectors.toList()));
  for (int n : set.stream().skip(5).collect(Collectors.toList())) {
     System.out.println(n);
  }

Upvotes: 0

GregH
GregH

Reputation: 5459

You can keep calling continue to skip that iteration until you reach the Object you are looking for. Hard to give much more information without more context

ArrayList list = new ArrayList();
Iterator itr = list.iterator();
boolean skipElement = true;
while(itr.hasNext()) {
    Object element = itr.next();
    if(element.equals(myTargetElement)){ //target element is what you're comparing against to see where you want to start iterating (you didn't supply that info so not sure how you want to handle this)
        skipElement=false;
    }
    if(skipElement){
        continue;
    }
     System.out.print(element);
  }

this will print out the element that you want to start iterating at first.

Upvotes: 1

Related Questions