0

I'm having some trouble writing a substring() method for a class I'm building called LString. This class creates a linked list object called LString that builds strings. It mimics the String and StringBuilder objects in Java.

substring(int start, int end) creates a new LString out of the given this LString, from the index provided by start to end. It returns type LString.

Here is the error message without any edits to make end inclusive:

Running substring tests (63 tests)
Starting tests: ......E........................................................
Time: 0.031

There was 1 failure:
1) test43cSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.AssertionError: Substring of One Character LString is not equals LString expected: LString<a> but was: LString<a>
        at org.junit.Assert.fail(Assert.java:88)
        at org.junit.Assert.failNotEquals(Assert.java:743)
        at org.junit.Assert.assertEquals(Assert.java:118)
        at LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(LStringTest.java:401)
        ... 10 more

Test Failed! (1 of 63 tests failed.)

Test failures: abandoning other phases.

This produces a simpler error message, with only 1 failure.

Here is the code corresponding to that error message:

import java.io.*;
import java.util.*;

public class LString    {

     node   front;
     int size;

     //Creating a node class
     private    class   node {
          char data;
          node next;

          public    node (){
          }

          public    node    (char   newData){
                this.data = newData;
          }

          public    node    (char   newData,    node newNext){
                this.data = newData;
                this.next = newNext;
          }


     }
     //Constructors
     public LString(){
          this.size =   0;
          this.front =  null;
     }
     public LString(String original)    {
          this.size = original.length();
          if (original.length() > 0){

              this.front =  new node(original.charAt(0));
              node curr = this.front;

              for   (int i =1; i <  original.length(); i++) {
                    curr.next = new node(original.charAt(i));
                    curr = curr.next;
              }
          }



     }

    //  Length method,  returns the length of LString
     public int length()    {
        return this.size;
    }

    //  compareTo method,   compares    this LString to anotherLString, returns 0   if  equal,
    //  -1  if  lexicogrpahically   less,   and 1   if  lexicographically   greater
    public int compareTo(LString anotherLString)    {
        int len1    = length();
        int len2    = anotherLString.length();
        int lim = Math.min(len1, len2);

        node cn1    = front;
        node cn2    = anotherLString.front;

        int k   = 0;
        while   (k  < lim) {
            char c1 = cn1.data;
            char c2 = cn2.data;
            if  (c1 != c2) {
                return c1-c2;
            }
            k++;
            cn1 =   cn1.next;
            cn2 =   cn2.next;
        }
        return len1 - len2;

    }

    //  a boolean equals method that returns true   if  LString and other   are the same, false if not
    public boolean  equals(Object other)    {
        if  (this   ==  other) {
            return true;
        }
        if  (other instanceof   LString)    {
            LString otherLString    = (LString)other;
            int n   = length();
            if  (n  ==  otherLString.length()) {
                node n1 = front;
                node n2 = otherLString.front;
                while   (n1 != null) {
                    if  (n1.data    !=  n2.data)    {
                        return false;
                    }
                    n1  = n1.next;
                    n2  = n2.next;
                }
                return true;
            }
        }

        return false;
    }


    //  charAt returns  the character of LString at the argument index
    public char charAt(int index)   {

        if  ((index < 0) || (index >= this.length()))   {
            throw   new IndexOutOfBoundsException();
        }
        node curNode =  front;
        for (int    i = 0; i    < this.length(); i++, curNode   = curNode.next) {
            if  (i  ==  index) {
                return curNode.data;
            }
        }
        throw   new IllegalStateException();
    }

    //
    public void setCharAt(int index,    char ch)    {
      if (index < 0 || index >= this.length()) {
         throw new IndexOutOfBoundsException();
      }
      else {
         node currNode = front;
         for (int i = 0; i <this.length(); i++, currNode = currNode.next) {
            if (i == index) {
            currNode.data = ch;
            }
         }
      }
   }

    public LString  substring(int start,    int end)    {
      if (start < 0 || end > this.length() || start > end) {
         throw new IndexOutOfBoundsException();
      }
      LString substring = new LString();
      if (start == end) {
         return substring;
      }
      node node = this.front;
      for (int i = 0; i < start; i++) {
         node = node.next;
      }
      node copy = new node(node.data);
      substring.front = copy;
      for (int i = start+1; i < end; i++) {
         node = node.next;
         copy = copy.next = new node(node.data);
      }
      return substring;      
    }
    public LString  replace(int start, int end, LString lStr)   {
        return null;
    }

    public String toString(){
        StringBuilder result    = new   StringBuilder();

        node curr = front;
        while   (curr   !=  null){

            result.append(curr.data);
            curr = curr.next;
        }
        return result.toString();
    }
}

A few notes: I did write a toString() method, and in this code is also a replace() method, which I'll write after this.

Here is the error and code for making end inclusive:

Error:

Running substring tests (63 tests)
Starting tests: E....EEE....E.EEEEEE.....E.EEEEEEE....E.EEEEEEE....E.EEEEEEE...
Time: 0.028

There were 35 failures:
1) test41aSubStringEmpty(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test41aSubStringEmpty(LStringTest.java:368)
        ... 10 more
2) test43bSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43bSubStringOneChar(LStringTest.java:395)
        ... 10 more
3) test43cSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(LStringTest.java:401)
        ... 10 more
4) test43dSubStringOneCharIsNew(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43dSubStringOneCharIsNew(LStringTest.java:407)
        ... 10 more
5) test51bEmptySubstringAtEnd[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
6) test51dSubstringAtStart[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
7) test51eSubstringAtEnd[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
8) test51fSubstringInMiddle[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<[]> but was:<[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
9) test51gSubstringAll[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
10) test51hSubstringAtStartIsNew[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
11) test51jSubstringAtEndIsNew[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
12) test51bEmptySubstringAtEnd[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
13) test51dSubstringAtStart[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
14) test51eSubstringAtEnd[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
15) test51fSubstringInMiddle[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<b[]> but was:<b[c]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
16) test51gSubstringAll[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
17) test51hSubstringAtStartIsNew[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
18) test51jSubstringAtEndIsNew[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
19) test51kSubstringInMiddleIsNew[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<b[]> but was:<b[c]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more
20) test51bEmptySubstringAtEnd[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
21) test51dSubstringAtStart[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<A long []> but was:<A long [s]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
22) test51eSubstringAtEnd[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
23) test51fSubstringInMiddle[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<ng str[]> but was:<ng str[i]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
24) test51gSubstringAll[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
25) test51hSubstringAtStartIsNew[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<A long []> but was:<A long [s]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
26) test51jSubstringAtEndIsNew[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
27) test51kSubstringInMiddleIsNew[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<ng str[]> but was:<ng str[i]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more
28) test51bEmptySubstringAtEnd[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
29) test51dSubstringAtStart[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<This is an even[]> but was:<This is an even[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
30) test51eSubstringAtEnd[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
31) test51fSubstringInMiddle[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<an even longer[]> but was:<an even longer[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
32) test51gSubstringAll[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
33) test51hSubstringAtStartIsNew[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<This is an even[]> but was:<This is an even[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
34) test51jSubstringAtEndIsNew[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
35) test51kSubstringInMiddleIsNew[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<an even longer[]> but was:<an even longer[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more

Test Failed! (35 of 63 tests failed.)

Test failures: abandoning other phases.

Here is the relevant differences in code, only substring() is different:

public LString  substring(int start,    int end)    {
  if (start < 0 || end >= this.length() || start > end) {
     throw new IndexOutOfBoundsException();
  }
  LString substring = new LString();
  /*if (start == end) {
     return substring;
  }*/
  node node = this.front;
  for (int i = 0; i < start; i++) {
     node = node.next;
  }
  node copy = new node(node.data);
  substring.front = copy;
  for (int i = start; i < end; i++) {
     node = node.next;
     copy = copy.next = new node(node.data);
  }
  return substring;      
}

Section from LStringTest regarding the error:

   @Test public void test43aSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not Empty",
               nullLString, testLString.substring(0, 0));
      }

      @Test public void test43bSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not Empty",
               nullLString, testLString.substring(1, 1));
      }

      @Test public void test43cSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not equals LString",
               testLString, testLString.substring(0, 1));
      }
Improve this question
5
  • The tests are definitely expecting exclusive end. I need to see the code for the method LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(). Please include that code in your question. Commented Mar 5, 2015 at 2:31
  • I added the code for all SubStringOneChar() methods Commented Mar 5, 2015 at 2:41
  • The bug is in your equals method. See if you can figure out why equals is returning the wrong answer for string length 1. Commented Mar 5, 2015 at 2:46
  • Alright I think I know the problem. Add the line substring.size = end - start; just before the return statement at the end of the substring method. I updated my answer to show this. Commented Mar 5, 2015 at 3:24
  • ah yes! I forgot about changing size. Thanks for your help. I'll move on to the replace method now Commented Mar 5, 2015 at 4:02

2 Answers 2

Reset to default
1

The code in that other answer doesn't compile, and even if it did, doesn't function correctly.

Assuming you're using standard (for Java) zero-based indexing, and that the end index is exclusive, this code compiles and is tested.

public LString substring(int start, int end) {
    if (start < 0 || end > length() || start > end) {
        throw new IndexOutOfBoundsException();
    }
    LString result = new LString();
    if (start == end) {
        return result;
    }
    node node = this.front;
    for (int i = 0; i < start; i++) {
        node = node.next;
    }
    node copy = new node(node.data);
    result.front = copy;
    for (int i = start + 1; i < end; i++) {
        node = node.next;
        copy = copy.next = new node(node.data);
    }
    result.size = end - start;
    return result;
}

If you wanted end to be inclusive, though this would be against Java convention, you would change three things:

  1. the guard clause at the start of the method would have to say end >= length() instead of end > length(),
  2. the second guard clause if (start == end) { return substring; } would need to be removed entirely, and
  3. the last for loop would initialize int i = start instead of int i = start + 1.

By the way, it's much easier to see what's happening with your LString instances if you have a toString() method in the class.

@Override
public String toString() {
    if (this.front == null) return "";
    StringBuilder sb = new StringBuilder(length());
    node node = this.front;
    do sb.append(node.data);
    while ((node = node.next) != null);
    return sb.toString();
}
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thanks for your reply, what would I do if end was inclusive?
You're welcome. Regarding end inclusive - it's not conventional for Java. And you could never get an empty substring because, for instance, substring(3, 3) would return the fourth character but substring(3, 2) would be invalid. But to make it work inclusive, you would have to change two things: 1) the guard clause at the start of the method would have to say end >= length() instead of end > length(), and 2) the last for loop would initialize int i = start instead of int i = start + 1.
Correction, you would have to change three things for end inclusive: 3) remove the second guard clause if (start == end) { return substring; }. See also my updated answer.
Thanks again. If you don't mind continuing, you're helping me a lot. I made the edits, including the third one, but am receiving more errors than my original error. It seems to be adding more than it needs to.
Make an edit to your question, include your new code in a separate section, and I'll take a look at it.
|
1

I didn't review all the code but just put the logic for the substring() method. Since you can mutate an LString by setting some char at a given position, I took the hypothesis that you really want a copy of the linked-list for the substring: you don't want a behaviour where you take a substring, modify the parent string and have the substring modified.

You can implement a "clever" implementation that won't actually copy the nodes until it is necessary. For instance, you can have the substring observe the parent string for any modification that would impact the nodes of the substring. And when there is one, the copy will occur. See the Observer/Observable pattern to implement this. In your case, if you keep only one class, LString it will implement both Observer and Observable.

Anyway, here is the simple copy implementation

public LString  substring(int start,    int end)    {
    if (start < 0 || end > this.length() || start > end) {
        throw new IndexOutOfBoundsException();
    }
    if (start == end) {
        return new LString(); // return an "empty" LString
    }

    // Find starting node
    Node currentNode = front;
    for (int i = 0; i < start; i++) {
        currentNode = currentNode.next;
    }

    // create new LString and copy each node from start to end
    LString ls = new LString();
    ls.front = new node(currentNode.data)
    node newCur = ls.front;
    for (int i = start+1; i<end; i++) {
        currentNode = currentNode.next;
        node newNext = new node(currentNode.data);
        newCur.next = newNext;
        newCur = newNext;
    }
    ls.size = end-start;
    return ls;
}
Improve this answer

2 Comments

Thanks, that's a lot of help. For now I'm going to stick with just copying it into a new LString. I have other methods I need to write. Quick question, with this implementation I receive an error for an LString substring of one character, in this case 'a', where the error message is "AssertionError" , any ideas why that is? I can't see anything at the moment.
Sorry, I actually wrote this without compiling and there was a few details to correct (like the size and the declaration of int in the for)... Well, the other solution has obviously debugged mine ;)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.