Реализация функции быстрого разделения на поток символов в Java


Я пишу кусок кода (пользовательские EntityProcessor для Гумз, но это не слишком актуально) предназначен для прорыва линии ввода на основе разделитель строк (toMatch ниже).

Символы читаются из потока, а затем перешел к addChar.
Предполагается, что каждый персонаж поставляется в потоке и смотреть вперед, не допускается - прорыв должен произойти после последнего символа матч прошел в.

Я написал две реализации ниже addChar и addChar2.
Первый-простой, тупой, сохранить буфер и сравнить его каждой итерации, второй-простой конечный автомат, а вторые чуть быстрее.

import java.util.Iterator;
import java.util.LinkedList;

public class CharStreamMatcher {
    protected char[] toMatch = null;


    public MagicCharStreamMatcher(char[] match){
        toMatch = match;
        for(int i=0;i<match.length;i++) li.add((char)0);
    }

    public void clear(){
        correspondences.clear();
    }

    LinkedList<Character> li = new LinkedList<Character>();
    public boolean addChar2(char c){
        li.addLast(c);
        li.removeFirst();
        int i=0;
        for(Character ch : li){
            if(ch.charValue() != toMatch[i++])
                return false;
        }
        return true;
    }


    private class MutableInteger{
        public int i;
        public MutableInteger(int i){
            this.i = i;
        }
    }

    LinkedList<MutableInteger> correspondences = new LinkedList<MutableInteger>();
    public boolean addChar(char c){
        boolean result = false; 

        if(c == toMatch[0])
            correspondences.add(new MutableInteger(-1));

        Iterator<MutableInteger> it = correspondences.iterator();
        while(it.hasNext()){
            MutableInteger mi = it.next();
            mi.i++;

            // check the match
            if(c != toMatch[mi.i]){
                it.remove();
            }
            // are we done? 
            else if(mi.i == toMatch.length-1){
                result = true;
                it.remove();
            }
        }

        return result;
    }   
}


1463
8
задан 17 февраля 2011 в 06:02 Источник Поделиться
Комментарии