如何在android中使用autocompleteTextView执行Trie搜索

Question

我需要实现一个AutocompleteTextView与Trie搜索。我使用一个顶点类和一个Trie类的Trie树数据结构和一个适配器自定义autocompleteTextView的下拉框的视图。

下面是我使用的所有类:

顶点类:

public class Vertex {
private HashMap<Character, Vertex> vertexSons;
private List<Integer> wordsIndexList;
private List<Integer> prefixesIndexList;
private int wordsNumber;
private int prefixesNumber;
public Vertex() {
    vertexSons = new HashMap<Character, Vertex>();
    wordsIndexList = new ArrayList<Integer>();
    prefixesIndexList = new ArrayList<Integer>();
    wordsNumber = 0;
    prefixesNumber = 0;
}
public boolean hasWords() {
    if (wordsNumber > 0) {
        return true;
    }
    return false;
}
public boolean hasPrefixes() {
    if (prefixesNumber > 0) {
        return true;
    }
    return false;
}
public void addVertexSon(Character character) {
    vertexSons.put(character, new Vertex());
}
public void addIndexToWordsIndexList(int index) {
    wordsIndexList.add(index);
}
public void addIndexToPrefixesIndexList(int index) {
    prefixesIndexList.add(index);
}
public HashMap<Character, Vertex> getVertexSons() {
    return vertexSons;
}
public List<Integer> getWordsIndexList() {
    return wordsIndexList;
}
public List<Integer> getPrefixesIndexList() {
    return prefixesIndexList;
}
public int getWordsNumber() {
    return wordsNumber;
}
public int getPrefixesNumber() {
    return prefixesNumber;
}
public void increaseWordsNumber() {
    wordsNumber++;
}
public void increasePrefixesNumber() {
    prefixesNumber++;
}
}

tree类:

public class Trie {
private Vertex rootVertex;
public Trie(List<Trieable> objectList, Locale locale) {
    rootVertex = new Vertex();
    for (int i = 0; i<objectList.size(); i++) {
        String word = objectList.get(i).toString().toLowerCase(locale);
        addWord(rootVertex, word, i);
    }
}
public Vertex getRootVertex() {
    return rootVertex;
}
public void addWord(Vertex vertex, String word, int index) {
    if (word.isEmpty()) { 
        vertex.addIndexToWordsIndexList(index);
        vertex.increaseWordsNumber();
    }
    else {
        vertex.addIndexToPrefixesIndexList(index);
        vertex.increasePrefixesNumber();
        Character fChar = word.charAt(0);
        HashMap<Character, Vertex> vertexSons = vertex.getVertexSons();
        if (!vertexSons.containsKey(fChar)) {
            vertex.addVertexSon(fChar);
        }
        word = (word.length() == 1) ? "" : word.substring(1);
        addWord(vertexSons.get(fChar), word, index);
    }
}
public List<Integer> getWordsIndexes(Vertex vertex, String word) {
    if (word.isEmpty()) {
        return vertex.getWordsIndexList();
    }
    else {
        Character fChar = word.charAt(0);
        if (!(vertex.getVertexSons().containsKey(fChar))) {
            return null;
        }
        else {
            word = (word.length() == 1) ? "" : word.substring(1);
            return getWordsIndexes(vertex.getVertexSons().get(fChar), word);
        }
    }
}
public List<Integer> getPrefixesIndexes(Vertex vertex, String prefix) {
    if (prefix.isEmpty()) {
        return vertex.getWordsIndexList();
    }
    else {
        Character fChar = prefix.charAt(0);
        if (!(vertex.getVertexSons().containsKey(fChar))) {
            return null;
        }
        else {
            prefix = (prefix.length() == 1) ? "" : prefix.substring(1);
            return getWordsIndexes(vertex.getVertexSons().get(fChar), prefix);
        }
    }
}
}

适配器类:

public class MunicipalitySearchAdapter extends ArrayAdapter<Municipality> {
private ArrayList<Municipality> municipalities;
private ArrayList<Municipality> allMunicipalities;
private ArrayList<Municipality> suggestedMunicipalities;
private List<Trieable> triableList;
private Trie municipalityTrie;
private int viewResourceId;
@SuppressWarnings("unchecked")
public MunicipalitySearchAdapter(Context context, int viewResourceId, ArrayList<Municipality> municipalities) {
    super(context, viewResourceId, municipalities);
    this.municipalities = municipalities;
    this.allMunicipalities = (ArrayList<Municipality>) this.municipalities.clone();
    this.suggestedMunicipalities = new ArrayList<Municipality>();
    this.viewResourceId = viewResourceId;
    this.triableList = new ArrayList<Trieable>();
    for (Municipality mun : allMunicipalities) {
        triableList.add(mun);
    }
    municipalityTrie = new Trie(triableList, Locale.ITALY);
}
@Override
public View getView(int position, View convertView, ViewGroup parent) {
    View v = convertView;
    if (v == null) {
        LayoutInflater inflater = (LayoutInflater) getContext().getSystemService(Context.LAYOUT_INFLATER_SERVICE);
        v = inflater.inflate(this.viewResourceId, null);
    }
    Municipality municipality = municipalities.get(position);
    if (municipality != null) {
        TextView munNameTxtView = (TextView) v.findViewById(R.id.name);
        TextView proSignTxtView = (TextView) v.findViewById(R.id.sign);
        TextView regNameTxtView = (TextView) v.findViewById(R.id.regionName);
        if (munNameTxtView != null) {
            munNameTxtView.setText(municipality.getName());
        }
        if (proSignTxtView != null) {
            proSignTxtView.setText(municipality.getProvinceSign());
        }
        if (regNameTxtView != null) {
            regNameTxtView.setText(municipality.getRegionName());
        }
    }
    return v;
}
@Override 
public Filter getFilter() {
    return municipalityFilter;
}
Filter municipalityFilter = new Filter() {

    @Override
    public String convertResultToString(Object resultValue) {
        String str = ((Municipality) (resultValue)).getName();
        return str;
    }
    @Override
    protected FilterResults performFiltering(CharSequence constraint) {
        if (constraint != null) {
            String constraintString = constraint.toString().trim();
            suggestedMunicipalities.clear();

            List<Integer> wordsIndexesList = municipalityTrie.getWordsIndexes(municipalityTrie.getRootVertex(), constraintString);
            for (int index : wordsIndexesList) {
                suggestedMunicipalities.add(allMunicipalities.get(index));
            }
            List<Integer> prefixesIndexesList = municipalityTrie.getPrefixesIndexes(municipalityTrie.getRootVertex(), constraintString);
            for (int index : prefixesIndexesList) {
                suggestedMunicipalities.add(allMunicipalities.get(index));
            }
            FilterResults filterRes = new FilterResults();
            filterRes.values = suggestedMunicipalities;
            filterRes.count = suggestedMunicipalities.size();
            return filterRes;
        }
        else {
            return new FilterResults();
        }
    }
    @Override
    protected void publishResults(CharSequence constraint, FilterResults results) {
        if (results != null && results.count > 0) {
            @SuppressWarnings("unchecked")
            ArrayList<Municipality> filteredMunicipalities = (ArrayList<Municipality>) results.values;
            ArrayList<Municipality> supportMunicipalitiesList = new ArrayList<Municipality>();
            clear();
            for (Municipality mun : filteredMunicipalities) {
                supportMunicipalitiesList.add(mun);
            }
            Iterator<Municipality> municipalityIterator = supportMunicipalitiesList.iterator();
            while (municipalityIterator.hasNext()) {
                Municipality municipality = municipalityIterator.next();
                add(municipality);
            }
            notifyDataSetChanged();
        }           
    }
};
}

我在这一行得到一个空指针(在适配器内部的Filter performfilters()方法实现中):

for (int index : wordsIndexesList) {
                suggestedMunicipalities.add(allMunicipalities.get(index));
            }

对于这个问题，你有什么可能的解决办法吗?我解决不了。我遗漏或弄错了什么?

编辑:我发现了问题，我需要设置约束toLowerCase()。现在它起作用了。然而。为什么只有当我输入完整的单词时才会看到自动补全建议?(在我的例子中是一个城市的名字)。

似乎我的Trie没有返回我可以用来填充建议列表的PrefixIndexes。但是我找不到问题所在。任何想法?

再次感谢!

Answer 1

为了解决作者提到的全字输入问题，在Trie类的getPrefixesIndexes()方法中将getWordsIndexes替换为getPrefixesIndexes，将getWordsIndexList -替换为getPrefixesIndexList:

public List<Integer> getPrefixesIndexes(Vertex vertex, String prefix)
{
    if (prefix.isEmpty())
    {
        return vertex.getPrefixesIndexList();
    }
    else
    {
        Character fChar = prefix.charAt(0);
        if (!(vertex.getVertexSons().containsKey(fChar)))
        {
            return null;
        }
        else
        {
            prefix = (prefix.length() == 1) ? "" : prefix.substring(1);
            return getPrefixesIndexes(vertex.getVertexSons().get(fChar), prefix);
        }
    }
}