Java. Linear search. Developing a generic class that contains tools for implementing linear search

Linear search. Developing a generic class that contains tools for implementing linear search

- Task
- Instructions

Related topics

Search other websites:

Task

Develop a generic LSearch<T> class that contains facilities for implementing linear search in a one-dimensional array. Demonstrate how the class works in the main() function.

Instructions

1. The structure of console application. Classes LSearch<T> and TestLSearch

First of all, you need to create a new class that contains the main() function. In our case, the class name is TestLSearch. A file named TestLSearch.java is created with two classes:

generic class LSearch<T>, which needs to be developed in accordance with the condition of the problem;
the TestLSearch class containing the main() function. The main() function will test the LSearch<T> class.

The general structure of the classes is as follows:

// A generalized class that implements linear search.
// Class works with type T
class LSearch<T> {

}

// The class containing the main() function in which the work of the LSearch<T> class is tested
public class TestLSearch {

  public static void main(String[] args) {

  }

}

In the next steps, the LSearch<T> class will add the internal variables and methods to perform the task. The body of the main() function will contain the code for testing class methods.

⇑

2. Developing the LSearch<T> class

2.1. Input the internal class variables

Since the linear search algorithm is used for one-dimensional arrays, a private one-dimensional internal array A is introduced into the LSearch<T> class.

class LSearch<T> {
  // Internal variable of class
  private T[] A; // array of generic type T
}

⇑

2.2. Class constructors

For convenient initialization of the internal array A, the class includes three public constructors:

constructor without parameters. Initializes array A to null;
constructor with a parameter of type array T[]. This constructor initializes the inner array A with the values of the outer array. The clone() method makes a complete copy (with memory allocation) of the input array;
constructor with parameter of type LSearch<T>. This is the case when you need to initialize an instance of a class with the data of another instance without using additional transforming methods.

After entering the constructors, the class text is as follows

class LSearch<T> {

  // Internal variables of class
  private T[] A; // array of generic type T

  // ------------ Class constructors --------------
  // Constructor without parameters
  public LSearch() {
    A = null;
  }

  // Constructor with 1 parameter.
  // Parameter: _A - an external array of elements that the external array
  //                 is initialized to
  public LSearch(T[] _A) {
    A = _A.clone(); // Make a copy in a different memory location
  }

  // Constructor that initializes with an instance of another class of type LSearch <T>
  public LSearch(LSearch<T> L) {
    this.A = L.A.clone();
  }
}

⇑

2.3. Methods for accessing internal data in a class

To access the internal class variables, the Get() and Set() methods are used, which have the following implementation

// Method that returns a reference to the internal data array
public T[] Get() {
  return this.A;
}

// Method that sets up a new array of data
public void Set(T[] _A) {
  this.A = _A.clone();
}

⇑

2.4. Methods of implementation of linear search

In order to provide a convenient linear search for a given element (key) in an array, the class implements 5 overloaded methods (see below).

2.4.1. The overloaded IsItem() method. Determining if a given element is in an array

The IsItem() method has two implementations: private and public.

In the first (hidden) implementation, the method receives as an input parameter an array of type T[] and a key of type T. The method returns true if the key element is in the input array. This method is located in the private section.

In the second implementation, the method receives the key. The search is performed in the internal array A of the given class.

// Hidden method that determines if the key element is in the _A array
private boolean IsItem(T[] _A, T key) {
  for (int i=0; i<_A.length; i++)
    if (key==_A[i])
      return true;
  return false;
}

// A public method that determines if the key element is in the internal array A
public boolean IsItem(T key) {
  return IsItem(A, key); // call a hidden method
}

⇑

2.4.2. Overloaded method GetFirstPos(). Determining the position of the first occurrence of an element in an array

The GetFirstPos() method implements a linear search from the beginning of the array. The method scans the array sequentially until the first match. As soon as the value of the key matches an element in the array, the method exits and the position (numbered from 0) of this element is returned.

The method has two implementations: private and public.

// A hidden method that determines the position of the first occurrence of key in the _A array.
// If there is no element in the array, then the method returns -1
private int GetFirstPos(T[] _A, T key) {
  for (int i=0; i<_A.length; i++)
    if (key == _A[i])
      return i;
  return -1;
}

// The overloaded GetFirstPos() method processes the internal array A of the class
public int GetFirstPos(T key) {
  return GetFirstPos(A, key); // invoke the hidden method
}

⇑

2.4.3. Overloaded method GetLastPos(). Determining the position of the last occurrence of an element in an array

The GetLastPos() method returns the position of the last occurrence of an element in an array. The search for the required key is carried out from the end of the array.

// Method that determines the position of the last occurrence of an element in the _A array
private int GetLastPos(T[] _A, T key) {
  for (int i=_A.length-1; i>=0; i--)
    if (key == _A[i])
      return i;
  return -1;
}

// Overloaded version of GetLastPos () - processes array A of class
public int GetLastPos(T key) {
  return GetLastPos(A, key);
}

⇑

2.4.4. Overloaded method GetNOccurences(). Determining the number of occurrences of an element in an array

// Method that determines the number of occurrences of an element in the array _A
private int GetNOccurences(T[] _A, T key) {
  int n = 0;
  for (int i=0; i<_A.length; i++)
    if (key==_A[i])
      n++;
  return n;
}

// Overloaded version of GetNOccurences() method - works with the internal array A
public int GetNOccurences(T key) {
  return GetNOccurences(A, key);
}

⇑

2.4.5. Overloaded method GetPositions(). Get an array of positions of occurrence of an element in an array

A useful method for use is the GetPositions() method, which allows you to get an array in which the positions of occurrence of the given key in the array A are written.

// A method that returns an array of occurrences of key in array _A
private int[] GetPositions(T[] _A, T key) {
  // Calculate the number of occurrences
  int nPos = GetNOccurences(key);

  // Declaring the array
  int[] AP = new int[nPos];

  // Add item numbers in the array AP
  int t=0;

  for (int i=0; i<_A.length; i++)
    if (key==_A[i])
      AP[t++] = i;

  // Return the array
  return AP;
}

// Overloaded method GetPositions()
public int[] GetPositions(T key) {
  // Call the hidden method of the same name
  return GetPositions(A, key);
}

⇑

2.5. Inner array output method

Additionally, the class implements the Print() method, which displays the elements of the array. The method receives as a parameter the comment string text. The method can be used to control and test the work of a class.

// Method that outputs the internal array
public void Print(String text) {
  System.out.println(text);
  for (int i=0; i<A.length; i++) {
    System.out.print(A[i]+" ");
  }
  System.out.println("");
}

⇑

3. Development of the TestLSearch class. Function main()

To test the work of the LSearch<T> class, a class is created that contains the main() function – the entry point into the program. The main() function demonstrates the creation of instances of the LSearch<T> class for different types. The use of constructors, accessors, and linear search is also demonstrated.

The text of the TestLSearch class is as follows.

// The class that contains the main() function, in which the work of the LSearch class is tested
public class TestLSearch {
  public static void main(String[] args) {
    // ----------------- Constructors testing -----------------
    // An array of integers
    Integer[] AI = { 2, 3, 5, -77 };

    // Declare an instance A1
    LSearch<Integer> A1 = new LSearch<Integer>(AI); // constructor LSearch(T[]) is called
    A1.Print("A1:");

    // Declare an instance A2
    LSearch<Integer> A2 = A1; // constructor LSearch(LSearch<T>) is called
    A2.Print("A2");

    // --------------- Testing of access methods -------------------
    // Declare array of real numbers AD
    Double[] AD = { 2.8, 3.5, -7.7, -9.99 };

    // Declare the A3 instance of real numbers
    LSearch<Double> A3 = new LSearch<Double>(); // the constructor with no parameters is called

    // Set a new array in A3 instance and print it
    A3.Set(AD);
    A3.Print("A3");

    // Get a reference to an internal array in an A3 instance
    Double[] AD2 = A3.Get();
    AD2[1] = 100.33; // Change element of internal array A3 via reference
    A3.Print("A3:");

    System.out.print("AD2: ");
    for (int i=0; i<AD2.length; i++)
      System.out.print(AD2[i] + " ");
    System.out.println();

    // ------------- Testing linear search methods ----------------
    // Method IsItem() - determining if an element is in an array
    if (A1.IsItem(5))
      System.out.println("Element 5 is present in array A1");
    else
      System.out.println("Element 5 is absent in the array A1");

    // Method GetFirstPos()
    int pos = A2.GetFirstPos(5);
    System.out.println();
    System.out.print("Array A2: ");
    A2.Print("");
    System.out.println("position of 5 is: " + pos);

    // Method GetNOccurences()
    Integer[] AI2 = { 5, 8, -3, 2, 5, 0, 0, 1, 3, 5, 8 }; // declare the array
    LSearch<Integer> A4 = new LSearch<Integer>(AI2); // declare an instance of class LSearch<>
    int n;

    n = A4.GetNOccurences(5); // the number of occurrences of the number 5 in the array A4
    System.out.println("n = " + n);

    // Method GetPositions() - get an array of positions
    int[] AP; // AP - the resulting array of positions
    AP = A4.GetPositions(5);

    System.out.print("Array of positions AP: ");
    for (int i=0; i<AP.length; i++)
      System.out.print(AP[i]+" ");
    System.out.println();
  }
}

⇑

4. The text of the entire module. Abridged version

After going through all the stages of this topic, you can get the program code of the TestLSearch.java module. Below is an abbreviated version of the LSearch<T> and TestLSearch classes.

// A generalized class that implements linear search.
// Class works with generic type T
class LSearch<T> {

  // Internal variables of the class
  private T[] A; // array of generic type T

  // ------------ Class constructors --------------
  // Constructor without parameters
  public LSearch() {
    ...
  }

  // Constructor with 1 parameter.
  // Parameter: _A - outer array of elements, which is initialized to the inner array
  public LSearch(T[] _A) {
    ...
  }

  // Constructor that initializes with an instance of another class of type LSearch<T>
  public LSearch(LSearch<T> L) {
    ...
  }

  // -------------- Methods for accessing internal data in a class --------------
  // Method that returns a reference to the internal data array
  public T[] Get() {
    ...
  }

  // Method that sets up a new array of data
  public void Set(T[] _A) {
    ...
  }

  // -------------- Methods of linear search ---------------------
  // Hidden method that determines if the key element is in the _A array
  private boolean IsItem(T[] _A, T key) {
    ...
  }

  // A public method that determines if the key element is in the internal array A
  public boolean IsItem(T key) {
    ...
  }

  // A hidden method that determines the position of the first occurrence of key in the _A array.
  // If the element is not in the array, the method returns -1
  private int GetFirstPos(T[] _A, T key) {
    ...
  }

  // The overloaded GetFirstPos() method processes the internal array A of the class
  public int GetFirstPos(T key) {
    ...
  }

  // Method that determines the position of the last occurrence of an element in the array _A
  private int GetLastPos(T[] _A, T key) {
    ...
  }

  // Overloaded GetLastPos() method - processes an array of A class
  public int GetLastPos(T key) {
    ...
  }

  // Method that determines the number of occurrences of an element in the _A array
  private int GetNOccurences(T[] _A, T key) {
    ...
  }

  // Overloaded GetNOccurences() method - works with the internal array A
  public int GetNOccurences(T key) {
    ...
  }

  // A method that returns an array of occurrences of key in array _A
  private int[] GetPositions(T[] _A, T key) {
    ...
  }

  // An overloaded variant of GetPositions()
  public int[] GetPositions(T key) {
    ...
  }

  // Method that prints an internal array
  public void Print(String text) {
    ...
  }
}

// The class that contains the main () function, in which the work of the LSearch class is tested
public class TestLSearch {
  public static void main(String[] args) {
    ...
  }
}

BestProg