BAAAZINGA BAAAZINGA - 4 months ago 12
Java Question

Check sorted array for duplicates

I do have a sorted array that I want to check for duplicate entrys. Problem is I need to know where the duplicate was as its a multidiensional array and I need to remove the 2nd entry too. Also in the end I must have an array filled with values so just overwriting the duplicates with some dummy won't work. I have read about

Array.utils
doing the trick but I'D rather not import any other libaries and
Array.utils
isn't recognized so I would've to import that.

I also tried to write a little function myself

Integer iIndex = 1;
while (keepRunning2){
if(phoneNameNumber[iIndex][0].equals(phoneNameNumber[iIndex-1][0])){
keepRunning = true;
tmp = new String[phoneNameNumber.length-1][2];
int k = 0;
int t=0;
while(keepRunning){
Log.wtf("running",String.valueOf(iIndex) + ":" + String.valueOf(k));
tmp[t][0] = phoneNameNumber[k][0];
tmp[t][1] = phoneNameNumber[k][1];
if(k!=i-1){
k++;
t++;
}else{
k=k+2;
t++;
}
if(t==tmp.length-1)
keepRunning=false;

}
phoneNameNumber = null;
phoneNameNumber = new String[tmp.length][2];
phoneNameNumber = tmp;
}
if(!(iIndex < phoneNameNumber.length-1)){
keepRunning2 = false;
}
iIndex++;
}


Buuuut... first it takes like 10 years to complete this and as this is for a UI of an app you can see that it should be alittle faster + for some reason after processing all of this it jumps back to while like keeppRunning2 'd never be set to false.

So does somebody know a solution?

and if sb wanna know where the data comes from: heres the activity

import android.app.ActionBar;
import android.app.Activity;
import android.app.DialogFragment;
import android.content.ContentResolver;
import android.content.Intent;
import android.database.Cursor;
import android.os.AsyncTask;
import android.os.Bundle;
import android.provider.ContactsContract;
import android.support.v7.app.AppCompatActivity;
import android.util.Log;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.widget.AdapterView;
import android.widget.ArrayAdapter;
import android.widget.Button;
import android.widget.CheckBox;
import android.widget.CheckedTextView;
import android.widget.EditText;
import android.widget.LinearLayout;
import android.widget.RadioGroup;
import android.widget.Spinner;
import android.widget.TextView;
import android.widget.Toast;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.ExecutionException;

/**
* Created by **** on 19.07.2016.
*/
public class newChatActivity extends Activity implements View.OnClickListener,AdapterView.OnItemSelectedListener{

Button bCreateChat;
Button bCancelChat;
EditText tchat_name;
//EditText tmembers;
CheckBox cBoxPrivateChat;
Spinner memberSpinner;
String members = "";
String lastContactName = "";
List<String> nameList,number;
String[][]phoneNameNumber,tmp;
String[] sortedNames;
Integer i = 0;
Integer memberCount = 0;
Boolean keepRunning = true;
Boolean keepRunning2 = true;

private static final String[] PROJECTION = new String[] {
ContactsContract.CommonDataKinds.Phone.CONTACT_ID,
ContactsContract.Contacts.DISPLAY_NAME,
ContactsContract.CommonDataKinds.Phone.NUMBER
};



@Override
public void onCreate(Bundle savedInstanceState){
super.onCreate(savedInstanceState);
setContentView(R.layout.new_chat);
setTitle("Add New Chat");

bCreateChat = (Button) findViewById(R.id.bCreateChat);
bCancelChat = (Button) findViewById(R.id.bChatCance);
tchat_name = (EditText) findViewById(R.id.tchat_name);
cBoxPrivateChat = (CheckBox) findViewById(R.id.cBoxprivChat);
memberSpinner = (Spinner) findViewById(R.id.memberSpinner);


bCreateChat.setOnClickListener(this);
bCancelChat.setOnClickListener(this);

loadAllContacts();
sortedNames = new String[phoneNameNumber.length];
Integer iIndex = 1;
while (keepRunning2){
if(phoneNameNumber[iIndex][0].equals(phoneNameNumber[iIndex-1][0])){
keepRunning = true;
tmp = new String[phoneNameNumber.length-1][2];
int k = 0;
int t=0;
while(keepRunning){
Log.wtf("running",String.valueOf(iIndex) + ":" + String.valueOf(k));
tmp[t][0] = phoneNameNumber[k][0];
tmp[t][1] = phoneNameNumber[k][1];
if(k!=i-1){
k++;
t++;
}else{
k=k+2;
t++;
}
if(t==tmp.length-1)
keepRunning=false;


}
phoneNameNumber = null;
phoneNameNumber = new String[tmp.length][2];
phoneNameNumber = tmp;
}
if(!(iIndex < phoneNameNumber.length-1)){
keepRunning2 = false;
}
iIndex++;
}

for(int i = 0;i<phoneNameNumber.length;i++){
sortedNames[i] = phoneNameNumber[i][0];
}
ArrayAdapter<String> spinnerAdapter = new ArrayAdapter<String>(this,android.R.layout.simple_spinner_item,sortedNames);
spinnerAdapter.setDropDownViewResource(android.R.layout.simple_spinner_dropdown_item);
memberSpinner.setAdapter(spinnerAdapter);
memberSpinner.setOnItemSelectedListener(this);



}


@Override
public void onClick(View v) {
switch (v.getId()){
case R.id.bCreateChat:
if (!tchat_name.getText().toString().isEmpty()&&!members.isEmpty()) {
if(cBoxPrivateChat.isChecked()){
createChat("name=" + tchat_name.getText().toString() + "&members=" + members + ScrollingActivity.Identifier + "#");
}
} else{
Toast.makeText(this,"Keine Daten Eingegeben",Toast.LENGTH_SHORT).show();
}
break;
case R.id.bChatCance:
this.finish();
break;
default:
if(v.getId() > 2000000 ){
members = members.replace("#" + number.get(v.getId() - 2000000) + "#","");
TextView delText = (TextView) findViewById(v.getId());
delText.setVisibility(View.GONE);
memberCount = memberCount - 1;
if(memberCount <= 1){
cBoxPrivateChat.setEnabled(true);
}
}
}
}

public void createChat(String Data){
try {
Boolean b = new createNewCHat().executeOnExecutor(AsyncTask.THREAD_POOL_EXECUTOR,ScrollingActivity.ServerLocation + "/alterChat.php", Data).get();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
Intent intent = new Intent(getApplicationContext(), ScrollingActivity.class);
intent.setFlags(Intent.FLAG_ACTIVITY_CLEAR_TOP);
intent.putExtra("EXIT", true);
startActivity(intent);
}

@Override
public void onItemSelected(AdapterView<?> parent, View view, int position, long id) {
if(position != 0 && !cBoxPrivateChat.isChecked()) {
members = members + "#" + number.get(position) + "#";
TextView MemberText = new TextView(this);
MemberText.setId(2000000 + position);
MemberText.setText(phoneNameNumber[position][0] + " " + phoneNameNumber[position][1]);
LinearLayout memberLayout = (LinearLayout) findViewById(R.id.membersLayout);
RadioGroup.LayoutParams params = new RadioGroup.LayoutParams(RadioGroup.LayoutParams.MATCH_PARENT, 100);
memberLayout.addView(MemberText, params);
MemberText.setOnClickListener(this);
memberCount++;
if(memberCount > 1){
cBoxPrivateChat.setEnabled(false);
cBoxPrivateChat.setChecked(false);
}
} else if(position != 0 && cBoxPrivateChat.isChecked() && members.equals("")){
members = members + "#" + number.get(position) + "#";
TextView MemberText = new TextView(this);
MemberText.setId(2000000 + position);
MemberText.setText(phoneNameNumber[position][0] + " " + phoneNameNumber[position][1]);
LinearLayout memberLayout = (LinearLayout) findViewById(R.id.membersLayout);
RadioGroup.LayoutParams params = new RadioGroup.LayoutParams(RadioGroup.LayoutParams.MATCH_PARENT, 100);
memberLayout.addView(MemberText, params);
MemberText.setOnClickListener(this);
memberCount++;
}
}

@Override
public void onNothingSelected(AdapterView<?> parent) {

}


public void loadAllContacts(){
nameList = new ArrayList<String>();
number = new ArrayList<String>();
ContentResolver cr = getContentResolver();
Cursor cursor = cr.query(ContactsContract.CommonDataKinds.Phone.CONTENT_URI, PROJECTION, null, null, null);
if (cursor != null) {
try {
final int nameIndex = cursor.getColumnIndex(ContactsContract.Contacts.DISPLAY_NAME);
final int numberIndex = cursor.getColumnIndex(ContactsContract.CommonDataKinds.Phone.NUMBER);


nameList.add(0,"Select chat members");
number.add(0,"");

while (cursor.moveToNext()) {
if(!cursor.getString(nameIndex).equals(lastContactName)){
nameList.add(cursor.getString(nameIndex));
number.add(cursor.getString(numberIndex));
lastContactName = cursor.getString(nameIndex);
}
}
} finally {
cursor.close();

}
phoneNameNumber = new String[nameList.size()][2];

for(int i = 0; i<nameList.size();i++){
phoneNameNumber[i][0] = nameList.get(i);
phoneNameNumber[i][1] = number.get(i);
}

Arrays.sort(phoneNameNumber, new Comparator<String[]>() {
@Override
public int compare(final String[] entry1, final String[] entry2) {
final String time1 = entry1[0];
final String time2 = entry2[0];
return time1.compareTo(time2);
}
});

}

}
}


oh and btw does somebody know why there are duplicates in the array? because if i simply use the list names on the spinner i dont have any duplicates

Answer

so you probably wanted some function like this:

(but I didn't understand your "I need to know where duplicate was" ... why? And also your code doesn't use the other dimension in any way, only [0] is compared... so I mimick that in my code too, but maybe it is not what you wanted?)

import java.util.Arrays;  // Maybe all of your problem is that you had typo in import?
// This is language standard stuff, available everywhere IMHO

    /**
     * Removes duplicates and nulls from sorted array, first item (sortedArray[i][0]) is considered
     * for duplicates search, rest of values sortedArray[i][1..n] is not considered at all.
     * 
     * @param sortedArray
     *            sorted 2D String array, can have any 1 <= length in second dimension.
     * @return items with duplicate in [i][0] or null will be removed from result array.
     */
    public static String[][] removeDuplicateOrNullItems(final String[][] sortedArray) {
        // validate input
        if (null == sortedArray || sortedArray.length <= 1) {
            return sortedArray; // garbage in, garbage out
        }
        // search for first duplicate (if any)
        int i = 0;
        while (++i < sortedArray.length) {
            if (null == sortedArray[i][0] || sortedArray[i][0].equals(sortedArray[i - 1][0])) {
                break;
            }
        }
        if (i == sortedArray.length) {
            return sortedArray; // no duplicate found, return input
        }
        // First duplicate is at index i, now compact the rest of array content (overwriting dupes)
        int newi = i; // will serve both as count of unique values, and compact-writing index
        while (++i < sortedArray.length) {
            if (null == sortedArray[i][0] || sortedArray[i][0].equals(sortedArray[i - 1][0])) {
                continue; // another duplicate, skip this one
            }
            sortedArray[newi++] = sortedArray[i]; // valid value, compact it
        }
        return Arrays.copyOf(sortedArray, newi); // return the compacted result
    }

// demo how to call it:

        String[][] in = {{"A1", "A2"}, {"A1", "dupA"}, {null, null}, {"B1", "B2"}, {"B1", "dupB1"}, {"B1", "dupB2"}, {"C1", "C2"}};
//      String[][] in = {{"A1", "A2", "A3"}, {"B1", "B2", "B3"}};
//      String[][] in = null;

        String[][] out = removeDuplicateOrNullItems(in);

I tried to comment it a bit to give you idea what it is doing... although using debugger and stepping it line by line few times may help a lot more.


If you really want to avoid java.util.Arrays, then the last return Arrays.copyOf... should be replaced with this:

    final String[][] result = new String[newi][sortedArray[0].length];
    for (i = 0; i < newi; ++i) result[i] = sortedArray[i];
    return result;