Results 1 to 15 of 15
  1. #1
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default SortedSet Interface

    *NOTE: All questions are from the page The SortedSet Interface (The Java™ Tutorials > Collections > Interfaces)

    There are couple of things that are blowing my mind away and couple of things that are confusing. Here is the confusing part:
    Quote Originally Posted by Oracle
    The range-view operations are somewhat analogous to those provided by the List interface, but there is one big difference. Range views of a sorted set remain valid even if the backing sorted set is modified directly. This is feasible because the endpoints of a range view of a sorted set are absolute points in the element space rather than specific elements in the backing collection, as is the case for lists. A range-view of a sorted set is really just a window onto whatever portion of the set lies in the designated part of the element space. Changes to the range-view write back to the backing sorted set and vice versa. Thus, it's okay to use range-views on sorted sets for long periods of time, unlike range-views on lists.
    "Range views of a sorted set remain valid even if the backing sorted set is modified directly."
    and
    "Changes to the range-view write back to the backing sorted set and vice versa."

    are contradicting in my opinion. So is changing the range view of a sorted set change the sorted set? Conffussed!

    Quote Originally Posted by Oracle
    Suppose you want to view a closed interval, which contains both of its endpoints, instead of an open interval. If the element type allows for the calculation of the successor of a given value in the element space, merely request the subSet from lowEndpoint to successor(highEndpoint). Although it isn't entirely obvious, the successor of a string s in String's natural ordering is s + "\0" — that is, s with a null character appended.

    Thus, the following one-liner tells you how many words between "doorbell" and "pickle", including doorbell and pickle, are contained in the dictionary.

    count = dictionary.subSet("doorbell", "pickle\0").size();
    :O Blowing my mind away. I did System.out.println("\0"); and all I get is a square. What is \0? is there an article on it or something?
    Thanks in advance.

    EDIT: Okay so after some tests, I've come to the conclusion that changing either the range view of the SortedSet changes both the range view and the SortedSet; however, I would still like to know what they mean by, "Range views of a sorted set remain valid even if the backing sorted set is modified directly."

    EDIT: Make sure you also read post #2
    Last edited by Lil_Aziz1; 07-30-2010 at 04:37 AM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  2. #2
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    I tried to test the difference between List's subList and SortedSet's subList and I stumbled upon an exception:
    Java Code:
    public class SlashZero {
    	
    	public static void main (String[] args) {
    		TreeSet<String> test = new TreeSet<String>();
    		ArrayList<String> listTest = new ArrayList<String>();
    		test.add("hi"); listTest.add("hi");
    		test.add("fat"); listTest.add("fat");
    		test.add("zaa"); listTest.add("zaa");
    		test.add("loser"); listTest.add("loser");
    		test.add("bad"); listTest.add("bad");
    		test.add("xavier"); listTest.add("xavier");
    		test.add("cat"); listTest.add("cat");
    		test.add("valedictorian"); listTest.add("valedictorian");
    		test.add("dog"); listTest.add("dog");
    		test.add("utopia"); listTest.add("utopia");
    		test.add("euphoria"); listTest.add("euphoria");
    		test.add("tiger"); listTest.add("tiger");
    		TreeSet<String> test1 = (TreeSet<String>) test.subSet("dog", "hi");
    		ArrayList<String> listTest1 = (ArrayList<String>) listTest.subList(3, 6); //Line 24
    		System.out.println(test1); 
    		System.out.println(test);
    		test1.remove("euphoria");
    		System.out.println(test);
    		System.out.println(test1);
    		System.out.println("=================");
    		System.out.println(listTest1); 
    		System.out.println(listTest);
    		listTest.remove("bad");
    		System.out.println(listTest);
    		System.out.println(listTest1);
    	}
    }
    After executing it, I get this:
    Java Code:
    Exception in thread "main" java.lang.ClassCastException: java.util.RandomAccessSubList cannot be cast to java.util.ArrayList
    	at SlashZero.main(SlashZero.java:24)
    I said, "okay fine." and did this:
    Java Code:
                    ....
    		TreeSet<String> test1 = (TreeSet<String>) test.subSet("dog", "hi");
    		List<String> listTest1 = listTest.subList(3, 6);
                    ....
    and got this after execution:
    Java Code:
    [dog, euphoria, fat]
    [bad, cat, dog, euphoria, fat, hi, loser, tiger, utopia, valedictorian, xavier, zaa]
    [bad, cat, dog, fat, hi, loser, tiger, utopia, valedictorian, xavier, zaa]
    [dog, fat]
    =================
    [loser, bad, xavier]
    [hi, fat, zaa, loser, bad, xavier, cat, valedictorian, dog, utopia, euphoria, tiger]
    [hi, fat, zaa, loser, xavier, cat, valedictorian, dog, utopia, euphoria, tiger]
    Exception in thread "main" java.util.ConcurrentModificationException
    	at java.util.SubList.checkForComodification(Unknown Source)
    	at java.util.SubList.listIterator(Unknown Source)
    	at java.util.AbstractList.listIterator(Unknown Source)
    	at java.util.SubList.iterator(Unknown Source)
    	at java.util.AbstractCollection.toString(Unknown Source)
    	at java.lang.String.valueOf(Unknown Source)
    	at java.io.PrintStream.println(Unknown Source)
    	at SlashZero.main(SlashZero.java:35)
    Why am I getting these exceptions?
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  3. #3
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    12,012
    Rep Power
    20

    Default

    It's throwing it on the println for the subarray (test1).
    The toString method used in this case comes from AbstractMethod, which (not surprisingly) uses an Iterator. However, you have changed the underlying List that this is a sub list of, meaning any Iterator is automatically invalid.

    This doesn't happen with the Set, as the documentation you quoted implies.

  4. #4
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Quote Originally Posted by Tolls View Post
    It's throwing it on the println for the subarray (test1).
    Huh?
    Quote Originally Posted by Tolls View Post
    The toString method used in this case comes from AbstractMethod, which (not surprisingly) uses an Iterator. However, you have changed the underlying List that this is a sub list of, meaning any Iterator is automatically invalid.

    This doesn't happen with the Set, as the documentation you quoted implies.
    So the range view doesn't create its own iterator? Why doesn't? Isn't it a separate List? I understand why changing one of Range view and the List would also change the other one because they reference the same object. But why would a List not have its own ListIterator?
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,525
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Lil_Aziz1 View Post
    I did System.out.println("\0"); and all I get is a square. What is \0?
    It's a String with a single character '\0'. That character has all its bits set to zero and it is considered the smallest character, i.e. for all other characters x, the relation x > '\0' is true.


    kind regards,

    Jos

  6. #6
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    So when one appends \0 to a String, doesn't the string change? If so, shouldn't this fail
    Java Code:
    dictionary.subSet("doorbell", "pickle\0").size();
    because there is no String that is equivalent to "pickle\0" in the dictionary, only "pickle." You know what I'm saying?

    EDIT: I did this:

    Java Code:
    char charTest = '\0';
    System.out.println((int) '\0');
    and I get zero as my result like you said I would. Then I did:
    Java Code:
    		char charTest = '\0';
    		System.out.println(Integer.toHexString((int) charTest));
    and according to the ANSI character table, I should get 80 ( http://www.handheld-basic.com/docume.../page_599.html ). Instead, I get zero again.
    Last edited by Lil_Aziz1; 07-30-2010 at 05:21 PM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  7. #7
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    12,012
    Rep Power
    20

    Default

    Quote Originally Posted by Lil_Aziz1 View Post
    Huh?


    So the range view doesn't create its own iterator? Why doesn't? Isn't it a separate List? I understand why changing one of Range view and the List would also change the other one because they reference the same object. But why would a List not have its own ListIterator?
    The base list you are referring to has changed. The sublist does have its own iterator, which is now invalid thanks to the deletion of an entry in the base list. Hence the exception.

  8. #8
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Ah okay and for SortedSet you don't get an exception when you modify the base list.

    Now back to the \0.

    when one appends \0 to a String, doesn't the string change? If so, shouldn't this fail
    Java Code:
    dictionary.subSet("doorbell", "pickle\0").size();
    because there is no String that is equivalent to "pickle\0" or "picklenull" in the dictionary, only "pickle." You know what I'm saying?
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  9. #9
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    12,012
    Rep Power
    20

    Default

    Quote Originally Posted by Lil_Aziz1 View Post
    Ah okay and for SortedSet you don't get an exception when you modify the base list.
    yep. It doesn't have the same SubList concept (SubList is the List type I think of the...sub list :)).

    Quote Originally Posted by Lil_Aziz1 View Post
    Now back to the \0.

    when one appends \0 to a String, doesn't the string change? If so, shouldn't this fail
    Java Code:
    dictionary.subSet("doorbell", "pickle\0").size();
    because there is no String that is equivalent to "pickle\0" or "picklenull" in the dictionary, only "pickle." You know what I'm saying?
    That subSet() isn't doing what you think it is.

    Taking your existing example with the TreeSet run this:
    Java Code:
            TreeSet<String> test = new TreeSet<String>();
            test.add("hi");
            test.add("fat");
            test.add("zaa");
            test.add("loser");
            test.add("bad");
            test.add("xavier");
            test.add("cat");
            test.add("valedictorian");
            test.add("dog");
            test.add("utopia");
            test.add("euphoria");
            test.add("tiger");
            TreeSet<String> test1 = (TreeSet<String>) test.subSet("dog", "hi\0");
            TreeSet<String> test2 = (TreeSet<String>) test.subSet("dog", "hi");
            System.out.println(test);
            System.out.println(test1);
            System.out.println(test2);
    "test1" is running from dog to hi\0...and test2 is running from dog to hi.
    Now the API says:
    Returns a view of the portion of this set whose elements range from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive.
    Note the "exclusive". So test1 allows for "hi" because "hi\0" is alphabetically after "hi". test2 doesn't.

  10. #10
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    right but "hi\0" is not in test1 or test2.


    EDIT: holy crap. I just realized that it doesn't matter if the right endpoint is in the list or not :O! I did this instead:
    Java Code:
    TreeSet<String> test1 = (TreeSet<String>) test.subSet("dog", "hi1");
    and I got the same result!
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  11. #11
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    One more thing: Why is this giving me an exception?
    Java Code:
    ArrayList<String> listTest1 = (ArrayList<String>) listTest.subList(3, 6); //Line 24
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  12. #12
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    12,012
    Rep Power
    20

    Default

    subSet() uses the comparator (or compare() method) I think, so it will use Strings one, which will go until it finds something greater than or equal to the second value you give.

    As for the exception...what exception?

  13. #13
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    In post #2, I'm getting this exception:

    Java Code:
    Exception in thread "main" java.lang.ClassCastException: java.util.RandomAccessSubList cannot be cast to java.util.ArrayList
    	at SlashZero.main(SlashZero.java:24)
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  14. #14
    Tolls is online now Moderator
    Join Date
    Apr 2009
    Posts
    12,012
    Rep Power
    20

    Default

    That's because a sublist is not an ArrayList.
    All you know about the sublist() method is that it returns a List...casting to ArrayList is simply a case of guessing what sort of List it is...

  15. #15
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    That would explain the "java.util.RandomAccessSubList."

    Thanks a bunch!
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

Similar Threads

  1. SortedSet and Collections.binarySearch
    By ninoid in forum New To Java
    Replies: 4
    Last Post: 03-22-2010, 03:28 PM
  2. Use different comparator for SortedSet
    By linus_k in forum New To Java
    Replies: 0
    Last Post: 11-21-2008, 02:46 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •