<?php
 /**
 * This file is part of phpMorphy library
 *
 * Copyright c 2007-2008 Kamaev Vladimir <heromantor@users.sourceforge.net>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

require_once(PHPMORPHY_DIR . '/gramtab.php');
require_once(PHPMORPHY_DIR . '/unicode.php');

// ----------------------------
// Morphier interface
// ----------------------------
interface phpMorphy_Morphier_Interface {
    public function getAnnot($word);
    public function getBaseForm($word);
    public function getAllForms($word);
    public function getPseudoRoot($word);
    public function getPartOfSpeech($word);
    public function getWordDescriptor($word);
    public function getAllFormsWithAncodes($word);
    public function getAncode($word);
    public function getGrammarInfoMergeForms($word);
    public function getGrammarInfo($word);
}

class phpMorphy_Morphier_Empty implements phpMorphy_Morphier_Interface {
    public function getAnnot($word) { return false; }
    public function getBaseForm($word) { return false; }
    public function getAllForms($word) { return false; }
    public function getAllFormsWithGramInfo($word) { return false; }
    public function getPseudoRoot($word) { return false; }
    public function getPartOfSpeech($word) { return false; }
    public function getWordDescriptor($word) { return false; }
    public function getAllFormsWithAncodes($word) { return false; }
    public function getAncode($word) { return false; }
    public function getGrammarInfoMergeForms($word) { return false; }
    public function getGrammarInfo($word) { return false; }
    public function castFormByGramInfo($word, $partOfSpeech, $grammems, $returnWords = false, $callback = null) { return false; }
}

// ----------------------------
// Annot decoder
// ----------------------------
interface phpMorphy_AnnotDecoder_Interface {
    public function decode($annotsRaw, $withBase);
};

abstract class phpMorphy_AnnotDecoder_Base implements phpMorphy_AnnotDecoder_Interface {
    const INVALID_ANCODE_ID = 0xFFFF;
    protected
        $ends,
        $unpack_str,
        $block_size;

    public function __construct($ends) {
        $this->ends = $ends;

        $this->unpack_str = $this->getUnpackString();
        $this->block_size = $this->getUnpackBlockSize();
    }

    abstract protected function getUnpackString();
    abstract protected function getUnpackBlockSize();

    public function decode($annotRaw, $withBase) {
        if(empty($annotRaw)) {
            throw new phpMorphy_Exception("Empty annot given");
        }

        $unpack_str = $this->unpack_str;
        $unpack_size = $this->block_size;

        $result = unpack("Vcount/$unpack_str", $annotRaw);

        if(false === $result) {
            throw new phpMorphy_Exception("Invalid annot string '$annotRaw'");
        }

        if($result['common_ancode'] == self::INVALID_ANCODE_ID) {
            $result['common_ancode'] = null;
        }

        $count = $result['count'];

        $result = array($result);

        if($count > 1) {
            for($i = 0; $i < $count - 1; $i++) {
                $res = unpack($unpack_str, $GLOBALS['__phpmorphy_substr']($annotRaw, 4 + ($i + 1) * $unpack_size, $unpack_size));

                if($res['common_ancode'] == self::INVALID_ANCODE_ID) {
                    $res['common_ancode'] = null;
                }

                $result[] = $res;
            }
        }

        if($withBase) {
            $items = explode($this->ends, $GLOBALS['__phpmorphy_substr']($annotRaw, 4 + $count * $unpack_size));
            for($i = 0; $i < $count; $i++) {
                $result[$i]['base_prefix'] = $items[$i * 2];
                $result[$i]['base_suffix'] = $items[$i * 2 + 1];
            }
        }

        return $result;
    }
}

class phpMorphy_AnnotDecoder_Common extends phpMorphy_AnnotDecoder_Base {
    protected function getUnpackString() {
        return 'Voffset/vcplen/vplen/vflen/vcommon_ancode/vforms_count/vpacked_forms_count/vaffixes_size/vform_no/vpos_id';
//      return 'Voffset/vcplen/vplen/vflen/vcommon_ancode/vforms_count/vpacked_forms_count/vaffixes_size/vpos_id';
    }

    protected function getUnpackBlockSize() {
        return 22;
    }
}

class phpMorphy_AnnotDecoder_Predict extends phpMorphy_AnnotDecoder_Common {
    protected function getUnpackString() {
//      return 'Voffset/vcplen/vplen/vflen/vcommon_ancode/vforms_count/vpacked_forms_count/vaffixes_size/vform_no/vpos_id/vfreq';
        return parent::getUnpackString() . '/vfreq';
    }

    protected function getUnpackBlockSize() {
        return parent::getUnpackBlockSize() + 2;
    }
}

class phpMorphy_AnnotDecoder_Factory {
    protected static $instances = array();

    protected
        $cache_common,
        $cache_predict,
        $eos;

    protected function __construct($eos) {
        $this->eos = $eos;
    }

    static function create($eos) {
        if(!isset(self::$instances[$eos])) {
            self::$instances[$eos] = new phpMorphy_AnnotDecoder_Factory($eos);
        }

        return self::$instances[$eos];
    }

    public function getCommonDecoder() {
        if(!isset($this->cache_common)) {
            $this->cache_common = $this->instantinate('common');
        }

        return $this->cache_common;
    }

    public function getPredictDecoder() {
        if(!isset($this->cache_predict)) {
            $this->cache_predict = $this->instantinate('predict');
        }

        return $this->cache_predict;
    }

    protected function instantinate($type) {
        $clazz = 'phpMorphy_AnnotDecoder_' . ucfirst($GLOBALS['__phpmorphy_strtolower']($type));

        return new $clazz($this->eos);
    }
}

interface phpMorphy_AncodesResolver_Interface {
    public function resolve($ancodeId);
    public function unresolve($ancode);
}

class phpMorphy_AncodesResolver_Proxy implements phpMorphy_AncodesResolver_Interface {
    protected
        $args, $class,
        $__obj;


    public function __construct($class, $ctorArgs) {
        $this->class = $class;
        $this->args = $ctorArgs;
    }

    public function unresolve($ancode) {
        return $this->getObj()->unresolve($ancode);
    }

    public function resolve($ancodeId) {
        return $this->getObj()->resolve($ancodeId);
    }

    static function instantinate($class, $args) {
        $ref = new ReflectionClass($class);
        return $ref->newInstanceArgs($args);
    }

    public function getObj() {
        if ($this->__obj !== null) {
            return $this->__obj;
        }
        $this->__obj = $this->instantinate($this->class, $this->args);

        unset($this->args);
        unset($this->class);

        return $this->__obj;
    }
}

class phpMorphy_AncodesResolver_ToText implements phpMorphy_AncodesResolver_Interface {
    protected $gramtab;

    public function __construct(phpMorphy_GramTab_Interface $gramtab) {
        $this->gramtab = $gramtab;
    }

    public function resolve($ancodeId) {
        if(!isset($ancodeId)) {
            return null;
        }

        return $this->gramtab->ancodeToString($ancodeId);
    }

    public function unresolve($ancode) {
        return $this->gramtab->stringToAncode($ancode);
        //throw new phpMorphy_Exception("Can`t convert grammar info in text into ancode id");
    }
}

class phpMorphy_AncodesResolver_ToDialingAncodes implements phpMorphy_AncodesResolver_Interface {
    protected
        $ancodes_map,
        $reverse_map;

    public function __construct(phpMorphy_Storage $ancodesMap) {
        if(false === ($this->ancodes_map = unserialize($ancodesMap->read(0, $ancodesMap->getFileSize())))) {
            throw new phpMorphy_Exception("Can`t open phpMorphy => Dialing ancodes map");
        }

        $this->reverse_map = array_flip($this->ancodes_map);
    }

    public function unresolve($ancode) {
        if(!isset($ancode)) {
            return null;
        }

        if(!isset($this->reverse_map[$ancode])) {
            throw new phpMorphy_Exception("Unknwon ancode found '$ancode'");
        }

        return $this->reverse_map[$ancode];
    }

    public function resolve($ancodeId) {
        if(!isset($ancodeId)) {
            return null;
        }

        if(!isset($this->ancodes_map[$ancodeId])) {
            throw new phpMorphy_Exception("Unknwon ancode id found '$ancodeId'");
        }

        return $this->ancodes_map[$ancodeId];
    }
}

class phpMorphy_AncodesResolver_AsIs implements phpMorphy_AncodesResolver_Interface {
    // This ctor for ReflectionClass::newInstanceArgs($args) with $args = array()
    public function __construct() {
    }

    public function resolve($ancodeId) {
        return $ancodeId;
    }

    public function unresolve($ancode) {
        return $ancode;
    }
}

// ----------------------------
// Helper
// ----------------------------
class phpMorphy_Morphier_Helper {
    protected
        $graminfo,
        $annot_decoder,
        $char_size,
        $ends,
        $gramtab,
        $ancodes_resolver,
        $gramtab_consts_included = false,
        $resolve_pos;

    public function __construct(
        phpMorphy_GramInfo_Interace $graminfo,
        phpMorphy_GramTab_Interface $gramtab,
        phpMorphy_AncodesResolver_Interface $ancodesResolver,
        $resolvePartOfSpeech
    ) {
        $this->graminfo = $graminfo;
        $this->gramtab = $gramtab;
        $this->resolve_pos = (bool)$resolvePartOfSpeech;
        $this->ancodes_resolver = $ancodesResolver;

        $this->char_size = $graminfo->getCharSize();

        $this->ends = $graminfo->getEnds();
    }

    public function setAnnotDecoder(phpMorphy_AnnotDecoder_Interface $annotDecoder) {
        $this->annot_decoder = $annotDecoder;
    }

    // getters
    public function getEndOfString() {
        return $this->ends;
    }

    public function getCharSize() {
        return $this->char_size;
    }

    public function hasAnnotDecoder() {
        return isset($this->annot_decoder);
    }

    public function getAnnotDecoder() {
        return $this->annot_decoder;
    }

    public function getAncodesResolver() {
        return $this->ancodes_resolver;
    }

    public function getGramInfo() {
        return $this->graminfo;
    }

    public function getGramTab() {
        return $this->gramtab;
    }

    public function isResolvePartOfSpeech() {
        return $this->resolve_pos;
    }

    // other
    public function resolvePartOfSpeech($posId) {
        return $this->gramtab->resolvePartOfSpeechId($posId);
    }

    public function getGrammems($ancodeId) {
        return $this->gramtab->getGrammems($ancodeId);
    }

    public function getGrammemsAndPartOfSpeech($ancodeId) {
        return array(
            $this->gramtab->getPartOfSpeech($ancodeId),
            $this->gramtab->getGrammems($ancodeId)
        );
    }

    public function extractPartOfSpeech($annot) {
        if($this->resolve_pos) {
            return $this->resolvePartOfSpeech($annot['pos_id']);
        } else {
            return $annot['pos_id'];
        }
    }

    protected function includeGramTabConsts() {
        if($this->isResolvePartOfSpeech()) {
            $this->gramtab->includeConsts();
        }

        $this->gramtab_consts_included = true;
    }

    // getters
    public function getWordDescriptor($word, $annots) {
        if(!$this->gramtab_consts_included) {
            $this->includeGramTabConsts();
        }

        return new phpMorphy_WordDescriptor_Collection($word, $annots, $this);
    }

    protected function getBaseAndPrefix($word, $cplen, $plen, $flen) {
        if($flen) {
            $base = $GLOBALS['__phpmorphy_substr']($word, $cplen + $plen, -$flen);
        } else {
            if($cplen || $plen) {
                $base = $GLOBALS['__phpmorphy_substr']($word, $cplen + $plen);
            } else {
                $base = $word;
            }
        }

        $prefix = $cplen ? $GLOBALS['__phpmorphy_substr']($word, 0, $cplen) : '';

        return array($base, $prefix);
    }

    public function getPartOfSpeech($word, $annots) {
        if(false === $annots) {
            return false;
        }

        $result = array();

        foreach($this->decodeAnnot($annots, false) as $annot) {
            $result[$this->extractPartOfSpeech($annot)] = 1;
        }

        return array_keys($result);
    }

    public function getBaseForm($word, $annots) {
        if(false === $annots) {
            return false;
        }

        $annots = $this->decodeAnnot($annots, true);

        return $this->composeBaseForms($word, $annots);
    }

    public function getPseudoRoot($word, $annots) {
        if(false === $annots) {
            return false;
        }

        $annots = $this->decodeAnnot($annots, false);

        $result = array();

        foreach($annots as $annot) {
            list($base) = $this->getBaseAndPrefix(
                $word,
                $annot['cplen'],
                $annot['plen'],
                $annot['flen']
            );

            $result[$base] = 1;
        }

        return array_keys($result);
    }

    public function getAllForms($word, $annots) {
        if(false === $annots) {
            return false;
        }

        $annots = $this->decodeAnnot($annots, false);

        return $this->composeForms($word, $annots);
    }

    public function castFormByGramInfo($word, $annots, $partOfSpeech, $grammems, $returnWords = false, $callback = null) {
        if(false === $annots) {
            return false;
        }

        if(isset($callback) && !is_callable($callback)) {
            throw new phpMorphy_Exception("Invalid callback given");
        }

        $result = array();
        $grammems = (array)$grammems;
        $partOfSpeech = isset($partOfSpeech) ? (string)$partOfSpeech : null;

        foreach($this->decodeAnnot($annots, false) as $annot) {
            $all_ancodes = $this->graminfo->readAncodes($annot);
            $flexias = $this->graminfo->readFlexiaData($annot);
            $common_ancode = $annot['common_ancode'];
            $common_grammems = isset($common_ancode) ? $this->gramtab->getGrammems($common_ancode) : array();

            list($base, $prefix) = $this->getBaseAndPrefix(
                $word,
                $annot['cplen'],
                $annot['plen'],
                $annot['flen']
            );

            // i use strange $form_no handling for perfomance issue (no function call overhead)
            $i = 0;
            $form_no = 0;
            foreach($all_ancodes as $form_ancodes) {
                foreach($form_ancodes as $ancode) {
                    $form_pos = $this->gramtab->getPartOfSpeech($ancode);
                    $form_grammems = array_merge($this->gramtab->getGrammems($ancode), $common_grammems);
                    $form = $prefix . $flexias[$i] . $base . $flexias[$i + 1];

                    if(isset($callback)) {
                        if(!call_user_func($callback, $form, $form_pos, $form_grammems, $form_no)) {
                            $form_no++;
                            continue;
                        }
                    } else {
                        if(isset($partOfSpeech) && $form_pos !== $partOfSpeech) {
                            $form_no++;
                            continue;
                        }

                        if(count(array_diff($grammems, $form_grammems)) > 0) {
                            $form_no++;
                            continue;
                        }
                    }

                    if($returnWords) {
                        $result[$form] = 1;
                    } else {
                        $result[] = array(
                            'form' => $form,
                            'form_no' => $form_no,
                            'pos' => $form_pos,
                            'grammems' => $form_grammems
                        );
                    }

                    $form_no++;
                }

                $i += 2;
            }
        }

        return $returnWords ? array_keys($result) : $result;
    }

    public function getAncode($annots) {
        if(false === $annots) {
            return false;
        }

        $result = array();

        foreach($this->decodeAnnot($annots, false) as $annot) {
            $all_ancodes = $this->graminfo->readAncodes($annot);

            $result[] = array(
                'common' => $this->ancodes_resolver->resolve($annot['common_ancode']),
                'all' => array_map(
                    array($this->ancodes_resolver, 'resolve'),
                    $all_ancodes[$annot['form_no']]
                )
            );
        }

        return $this->array_unique($result);
    }

    protected static function array_unique($array) {
        static $need_own;

        if(!isset($need_own)) {
            $need_own = -1 === version_compare(PHP_VERSION, '5.2.9');
        }

        if($need_own) {
            $result = array();

            foreach(array_keys(array_unique(array_map('serialize', $array))) as $key) {
                $result[$key] = $array[$key];
            }

            return $result;
        } else {
            return array_unique($array, SORT_REGULAR);
        }
    }


    public function getGrammarInfoMergeForms($annots) {
        if(false === $annots) {
            return false;
        }

        $result = array();

        foreach($this->decodeAnnot($annots, false) as $annot) {
            $all_ancodes = $this->graminfo->readAncodes($annot);
            $common_ancode = $annot['common_ancode'];
            $grammems = isset($common_ancode) ? $this->gramtab->getGrammems($common_ancode) : array();

            $forms_count = 0;
            $form_no = $annot['form_no'];

            foreach($all_ancodes[$form_no] as $ancode) {
                $grammems = array_merge($grammems, $this->gramtab->getGrammems($ancode));
                $forms_count++;
            }

            $grammems = array_unique($grammems);
            sort($grammems);

            $result[] = array(
                // part of speech identical across all joined forms
                'pos' => $this->gramtab->getPartOfSpeech($ancode),
                'grammems' => $grammems,
                'forms_count' => $forms_count,
                'form_no_low' => $form_no,
                'form_no_high' => $form_no + $forms_count,
            );
        }

        return $this->array_unique($result);
    }

    public function getGrammarInfo($annots) {
        if(false === $annots) {
            return false;
        }

        $result = array();

        foreach($this->decodeAnnot($annots, false) as $annot) {
            $all_ancodes = $this->graminfo->readAncodes($annot);
            $common_ancode = $annot['common_ancode'];
            $common_grammems = isset($common_ancode) ? $this->gramtab->getGrammems($common_ancode) : array();

            $info = array();

            $form_no = $annot['form_no'];
            foreach($all_ancodes[$form_no] as $ancode) {
                $grammems = //array_unique(
                    array_merge($common_grammems, $this->gramtab->getGrammems($ancode));
                //);

                sort($grammems);

                $info_item = array(
                    'pos' => $this->gramtab->getPartOfSpeech($ancode),
                    'grammems' => $grammems,
                    'form_no' => $form_no,
                );


                $info[] = $info_item;
            }

            $unique_info = $this->array_unique($info);
            sort($unique_info);
            $result[] = $unique_info;
        }

        return $this->array_unique($result);
    }

    public function getAllFormsWithResolvedAncodes($word, $annots, $resolveType = 'no_resolve') {
        if(false === $annots) {
            return false;
        }

        $annots = $this->decodeAnnot($annots, false);

        return $this->composeFormsWithResolvedAncodes($word, $annots);
    }

    public function getAllFormsWithAncodes($word, $annots, &$foundFormNo = array()) {
        if(false === $annots) {
            return false;
        }

        $annots = $this->decodeAnnot($annots, false);

        return $this->composeFormsWithAncodes($word, $annots, $foundFormNo);
    }

    public function getAllAncodes($word, $annots) {
        if(false === $annots) {
            return false;
        }

        $result = array();

        foreach($annots as $annot) {
            $result[] = $this->graminfo->readAncodes($annot);
        }

        return $result;
    }

    protected function composeBaseForms($word, $annots) {
        $result = array();

        foreach($annots as $annot) {

            if($annot['form_no'] > 0) {
                list($base, $prefix) = $this->getBaseAndPrefix(
                    $word,
                    $annot['cplen'],
                    $annot['plen'],
                    $annot['flen']
                );

                $result[$prefix . $annot['base_prefix'] . $base . $annot['base_suffix']] = 1;
            } else {
                $result[$word] = 1;
            }
        }

        return array_keys($result);
    }

    protected function composeForms($word, $annots) {
        $result = array();

        foreach($annots as $annot) {
            list($base, $prefix) = $this->getBaseAndPrefix(
                $word,
                $annot['cplen'],
                $annot['plen'],
                $annot['flen']
            );

            // read flexia
            $flexias = $this->graminfo->readFlexiaData($annot);

            for($i = 0, $c = count($flexias); $i < $c; $i += 2) {
                $result[$prefix . $flexias[$i] . $base . $flexias[$i + 1]] = 1;
            }
        }

        return array_keys($result);
    }

    protected function composeFormsWithResolvedAncodes($word, $annots) {
        $result = array();

        foreach($annots as $annotIdx => $annot) {
            list($base, $prefix) = $this->getBaseAndPrefix(
                $word,
                $annot['cplen'],
                $annot['plen'],
                $annot['flen']
            );

            $words = array();
            $ancodes = array();
            $common_ancode = $annot['common_ancode'];

            // read flexia
            $flexias = $this->graminfo->readFlexiaData($annot);
            $all_ancodes = $this->graminfo->readAncodes($annot);

            for($i = 0, $c = count($flexias); $i < $c; $i += 2) {
                $form = $prefix . $flexias[$i] . $base . $flexias[$i + 1];

                $current_ancodes = $all_ancodes[$i / 2];
                foreach($current_ancodes as $ancode) {
                    $words[] = $form;
                    $ancodes[] = $this->ancodes_resolver->resolve($ancode);
                }
            }

            $result[] = array(
                'forms' => $words,
                'common' => $this->ancodes_resolver->resolve($common_ancode),
                'all' => $ancodes,
            );
        }

        return $result;
    }

    protected function composeFormsWithAncodes($word, $annots, &$foundFormNo) {
        $result = array();

        foreach($annots as $annotIdx => $annot) {
            list($base, $prefix) = $this->getBaseAndPrefix(
                $word,
                $annot['cplen'],
                $annot['plen'],
                $annot['flen']
            );

            // read flexia
            $flexias = $this->graminfo->readFlexiaData($annot);
            $ancodes = $this->graminfo->readAncodes($annot);

            $found_form_no = $annot['form_no'];

            $foundFormNo = !is_array($foundFormNo) ? array() : $foundFormNo;

            for($i = 0, $c = count($flexias); $i < $c; $i += 2) {
                $form_no = $i / 2;
                $word = $prefix . $flexias[$i] . $base . $flexias[$i + 1];

                if($found_form_no == $form_no) {
                    $count = count($result);
                    $foundFormNo[$annotIdx]['low'] = $count;
                    $foundFormNo[$annotIdx]['high'] = $count + count($ancodes[$form_no]) - 1;
                }

                foreach($ancodes[$form_no] as $ancode) {
                    $result[] = array($word, $ancode);
                }
            }
        }

        return $result;
    }

    public function decodeAnnot($annotsRaw, $withBase) {
        if(is_array($annotsRaw)) {
            return $annotsRaw;
        } else {
            return $this->annot_decoder->decode($annotsRaw, $withBase);
        }
    }
}

// ----------------------------
// WordDescriptor
// ----------------------------
// TODO: extend ArrayObject?
class phpMorphy_WordDescriptor_Collection implements Countable, IteratorAggregate, ArrayAccess {
    protected
        $word,
        $descriptors = array(),
        $helper;

    public function __construct($word, $annots, phpMorphy_Morphier_Helper $helper) {
        $this->word = (string)$word;
        $this->annots = false === $annots ? false : $helper->decodeAnnot($annots, true);

        $this->helper = $helper;

        if(false !== $this->annots) {
            foreach($this->annots as $annot) {
                $this->descriptors[] = $this->createDescriptor($word, $annot, $helper);
            }
        }
    }

    protected function createDescriptor($word, $annot, phpMorphy_Morphier_Helper $helper) {
        return new phpMorphy_WordDescriptor($word, $annot, $helper);
    }

    public function getDescriptor($index) {
        if(!$this->offsetExists($index)) {
            throw new phpMorphy_Exception("Invalid index '$index' specified");
        }

        return $this->descriptors[$index];
    }

    public function getByPartOfSpeech($poses) {
        $result = array();
        settype($poses, 'array');

        foreach($this as $desc) {
            if($desc->hasPartOfSpeech($poses)) {
                $result[] = $desc;
            }
        }

//        return count($result) ? $result : false;
        return $result;
    }

    public function offsetExists($off): bool {
        return isset($this->descriptors[$off]);
    }

    public function offsetUnset($off): void {
        throw new phpMorphy_Exception(__CLASS__ . " is not mutable");
    }

    public function offsetSet($off, $value): void {
        throw new phpMorphy_Exception(__CLASS__ . " is not mutable");
    }

    public function offsetGet($off): mixed {
        return $this->getDescriptor($off);
    }

    public function count(): int {
        return count($this->descriptors);
    }

    public function getIterator(): \Traversable {
        return new ArrayIterator($this->descriptors);
    }
}

class phpMorphy_WordForm {
    protected
        $word,
        $form_no,
        $pos_id,
        $grammems
        ;

    public function __construct($word, $form_no, $pos_id, $grammems) {
        $this->word = (string)$word;
        $this->form_no = (int)$form_no;
        $this->pos_id = $pos_id;

        sort($grammems);
        $this->grammems = $grammems;
    }

    public function getPartOfSpeech() {
        return $this->pos_id;
    }

    public function getGrammems() {
        return $this->grammems;
    }

    public function hasGrammems($grammems) {
        $grammems = (array)$grammems;

        $grammes_count = count($grammems);
        return $grammes_count && count(array_intersect($grammems, $this->grammems)) == $grammes_count;
    }

    static function compareGrammems($a, $b) {
        return count($a) == count($b) && count(array_diff($a, $b)) == 0;
    }

    public function getWord() {
        return $this->word;
    }

    public function getFormNo() {
        return $this->form_no;
    }
}

class phpMorphy_WordDescriptor implements Countable, ArrayAccess, IteratorAggregate {
    protected
        $word,
        $annot,
        $helper,
        $cached_forms,
        $cached_base,
        $cached_pseudo_root,
        $all_forms,
        $found_form_no,
        $common_ancode_grammems;

    public function __construct($word, $annot, phpMorphy_Morphier_Helper $helper) {
        $this->word = (string)$word;
        $this->annot = array($annot);

        $this->helper = $helper;
    }

    public function getPseudoRoot() {
        if(!isset($this->cached_pseudo_root)) {
            list($this->cached_pseudo_root) = $this->helper->getPseudoRoot($this->word, $this->annot);
        }

        return $this->cached_pseudo_root;
    }

    public function getBaseForm() {
        if(!isset($this->cached_base)) {
            list($this->cached_base) = $this->helper->getBaseForm($this->word, $this->annot);
        }

        return $this->cached_base;
    }

    public function getAllForms() {
        if(!isset($this->cached_forms)) {
            $this->cached_forms = $this->helper->getAllForms($this->word, $this->annot);
        }

        return $this->cached_forms;
    }

    public function getWordForm($index) {
        $this->readAllForms();

        if(!$this->offsetExists($index)) {
            throw new phpMorphy_Exception("Invalid index '$index' given");
        }

        return $this->all_forms[$index];
    }

    protected function createWordForm($word, $form_no, $ancode) {
        if(!isset($this->common_ancode_grammems)) {
            $common_ancode = $this->annot[0]['common_ancode'];

            $this->common_ancode_grammems = isset($common_ancode) ?
                $this->helper->getGrammems($common_ancode) :
                array();
        }

        list($pos_id, $all_grammems) = $this->helper->getGrammemsAndPartOfSpeech($ancode);

        return new phpMorphy_WordForm($word, $form_no, $pos_id, array_merge($this->common_ancode_grammems, $all_grammems));
    }

    protected function readAllForms() {
        if(!isset($this->all_forms)) {
            $result = array();

            $form_no = 0;

            $found_form_no = array();
            foreach($this->helper->getAllFormsWithAncodes($this->word, $this->annot, $found_form_no) as $form) {
                $word = $form[0];

                $result[] = $this->createWordForm($word, $form_no, $form[1]);

                $form_no++;
            }

            $this->found_form_no = $found_form_no[0];
            $this->all_forms = $result;
        }

        return $this->all_forms;
    }

    protected function getFoundFormNoLow() {
        $this->readAllForms();

        return $this->found_form_no['low'];
    }

    protected function getFoundFormNoHigh() {
        $this->readAllForms();

        return $this->found_form_no['high'];
    }

    public function getFoundWordForm() {
        $result = array();
        for($i = $this->getFoundFormNoLow(), $c = $this->getFoundFormNoHigh() + 1; $i < $c; $i++) {
            $result[] = $this->getWordForm($i);
        }

        return $result;
    }

    public function hasGrammems($grammems) {
        settype($grammems, 'array');

        foreach($this as $wf) {
            if($wf->hasGrammems($grammems)) {
                return true;
            }
        }

        return false;
    }

    public function getWordFormsByGrammems($grammems) {
        settype($grammems, 'array');
        $result = array();

        foreach($this as $wf) {
            if($wf->hasGrammems($grammems)) {
                $result[] = $wf;
            }
        }

        return $result;
//        return count($result) ? $result : false;
    }

    public function hasPartOfSpeech($poses) {
        settype($poses, 'array');

        foreach($this as $wf) {
            if(in_array($wf->getPartOfSpeech(), $poses, true)) {
                return true;
            }
        }

        return false;
    }

    public function getWordFormsByPartOfSpeech($poses) {
        settype($poses, 'array');
        $result = array();

        foreach($this as $wf) {
            if(in_array($wf->getPartOfSpeech(), $poses, true)) {
                $result[] = $wf;
            }
        }

        return $result;
//        return count($result) ? $result : false;
    }

    public function count(): int {
        return count($this->readAllForms());
    }

    public function offsetExists($off): bool {
        $this->readAllForms();

        return isset($this->all_forms[$off]);
    }

    public function offsetSet($off, $value): void {
        throw new phpMorphy_Exception(__CLASS__ . " is not mutable");
    }

    public function offsetUnset($off): void {
        throw new phpMorphy_Exception(__CLASS__ . " is not mutable");
    }

    public function offsetGet($off): mixed {
        return $this->getWordForm($off);
    }

    public function getIterator(): \Traversable {
        $this->readAllForms();

        return new ArrayIterator($this->all_forms);
    }
}

// ----------------------------
// Finders
// ----------------------------
interface phpMorphy_Morphier_Finder_Interface {
    public function findWord($word);
    public function decodeAnnot($raw, $withBase);
    public function getAnnotDecoder();
}

abstract class phpMorphy_Morphier_Finder_Base implements phpMorphy_Morphier_Finder_Interface {
    protected
        $annot_decoder,
        $prev_word,
        $prev_result = false;

    public function __construct(phpMorphy_AnnotDecoder_Interface $annotDecoder) {
        $this->annot_decoder = $annotDecoder;
    }

    public function findWord($word) {
        if($this->prev_word === $word) {
            return $this->prev_result;
        }

        $result = $this->doFindWord($word);

        $this->prev_word = $word;
        $this->prev_result = $result;

        return $result;
    }

    public function getAnnotDecoder() {
        return $this->annot_decoder;
    }

    public function decodeAnnot($raw, $withBase) {
        return $this->annot_decoder->decode($raw, $withBase);
    }

    abstract protected function doFindWord($word);
}

class phpMorphy_Morphier_Finder_Common extends phpMorphy_Morphier_Finder_Base {
    protected
        $fsa,
        $root;

    public function __construct(phpMorphy_Fsa_Interface $fsa, phpMorphy_AnnotDecoder_Interface $annotDecoder) {
        parent::__construct($annotDecoder);

        $this->fsa = $fsa;
        $this->root = $this->fsa->getRootTrans();
    }

    public function getFsa() {
        return $this->fsa;
    }

    protected function doFindWord($word) {
        $result = $this->fsa->walk($this->root, $word);

        if(!$result['result'] || null === $result['annot']) {
            return false;
        }

        return $result['annot'];
    }
}

class phpMorphy_Morphier_Finder_Predict_Suffix extends phpMorphy_Morphier_Finder_Common {
    protected
        $min_suf_len,
        $unicode;

    public function __construct(phpMorphy_Fsa_Interface $fsa, phpMorphy_AnnotDecoder_Interface $annotDecoder, $encoding, $minimalSuffixLength = 4) {
        parent::__construct($fsa, $annotDecoder);

        $this->min_suf_len = (int)$minimalSuffixLength;
        $this->unicode = phpMorphy_UnicodeHelper::create($encoding);
    }

    protected function doFindWord($word) {
        $word_len = $this->unicode->strlen($word);

        if(!$word_len) {
            return false;
        }

        for($i = 1, $c = $word_len - $this->min_suf_len; $i < $c; $i++) {
            $word = $GLOBALS['__phpmorphy_substr']($word, $this->unicode->firstCharSize($word));

            if(false !== ($result = parent::doFindWord($word))) {
                break;
            }
        }

        if($i < $c) {
            //$known_len = $word_len - $i;
            $unknown_len = $i;

            return $result;
            /*
            return $this->fixAnnots(
                $this->decodeAnnot($result, true),
                $unknown_len
            );
            */
        } else {
            return false;
        }
    }

    protected function fixAnnots($annots, $len) {
        for($i = 0, $c = count($annots); $i < $c; $i++) {
            $annots[$i]['cplen'] = $len;
        }

        return $annots;
    }
}

class phpMorphy_Morphier_PredictCollector extends phpMorphy_Fsa_WordsCollector {
    protected
        $used_poses = array(),
        $annot_decoder,
        $collected = 0;

    public function __construct($limit, phpMorphy_AnnotDecoder_Interface $annotDecoder) {
        parent::__construct($limit);

        $this->annot_decoder = $annotDecoder;
    }

    public function collect($path, $annotRaw) {
        if($this->collected > $this->limit) {
            return false;
        }

        $used_poses =& $this->used_poses;
        $annots = $this->decodeAnnot($annotRaw);

        for($i = 0, $c = count($annots); $i < $c; $i++) {
            $annot = $annots[$i];
            $annot['cplen'] = $annot['plen'] = 0;

            $pos_id = $annot['pos_id'];

            if(isset($used_poses[$pos_id])) {
                $result_idx = $used_poses[$pos_id];

                if($annot['freq'] > $this->items[$result_idx]['freq']) {
                    $this->items[$result_idx] = $annot;
                }
            } else {
                $used_poses[$pos_id] = count($this->items);
                $this->items[] = $annot;
            }
        }

        $this->collected++;
        return true;
    }

    public function clear() {
        parent::clear();
        $this->collected = 0;
        $this->used_poses = array();
    }

    public function decodeAnnot($annotRaw) {
        return $this->annot_decoder->decode($annotRaw, true);
    }
}

class phpMorphy_Morphier_Finder_Predict_Databse extends phpMorphy_Morphier_Finder_Common {
    protected
        $collector,
        $unicode,
        $graminfo,
        $min_postfix_match;

    public function __construct(
        phpMorphy_Fsa_Interface $fsa,
        phpMorphy_AnnotDecoder_Interface $annotDecoder,
        $encoding,
        phpMorphy_GramInfo_Interace $graminfo,
        $minPostfixMatch = 2,
        $collectLimit = 32
    ) {
        parent::__construct($fsa, $annotDecoder);

        $this->graminfo = $graminfo;
        $this->min_postfix_match = $minPostfixMatch;
        $this->collector = $this->createCollector($collectLimit, $this->getAnnotDecoder());

        $this->unicode = phpMorphy_UnicodeHelper::create($encoding);
    }

    protected function createAnnotDecoder() {
        return phpmorphy_annot_decoder_new('predict');
    }

    protected function doFindWord($word) {
        $rev_word = $this->unicode->strrev($word);
        $result = $this->fsa->walk($this->root, $rev_word);

        if($result['result'] && null !== $result['annot']) {
            $annots = $result['annot'];
        } else {
            $match_len = $this->unicode->strlen($this->unicode->fixTrailing($GLOBALS['__phpmorphy_substr']($rev_word, 0, $result['walked'])));

            if(null === ($annots = $this->determineAnnots($result['last_trans'], $match_len))) {
                return false;
            }
        }

        if(!is_array($annots)) {
            $annots = $this->collector->decodeAnnot($annots);
        }

        return $this->fixAnnots($word, $annots);
    }

    protected function determineAnnots($trans, $matchLen) {
        $annots = $this->fsa->getAnnot($trans);

        if(null == $annots && $matchLen >= $this->min_postfix_match) {
            $this->collector->clear();

            $this->fsa->collect(
                $trans,
                $this->collector->getCallback()
            );

            $annots = $this->collector->getItems();
        }

        return $annots;
    }

    protected function fixAnnots($word, $annots) {
        $result = array();

        // remove all prefixes?
        for($i = 0, $c = count($annots); $i < $c; $i++) {
            $annot = $annots[$i];

            $annot['cplen'] = $annot['plen'] = 0;

            $flexias = $this->graminfo->readFlexiaData($annot, false);

            $prefix = $flexias[$annot['form_no'] * 2];
            $suffix = $flexias[$annot['form_no'] * 2 + 1];

            $plen = $GLOBALS['__phpmorphy_strlen']($prefix);
            $slen = $GLOBALS['__phpmorphy_strlen']($suffix);
            if(
                (!$plen || $GLOBALS['__phpmorphy_substr']($word, 0, $GLOBALS['__phpmorphy_strlen']($prefix)) === $prefix) &&
                (!$slen || $GLOBALS['__phpmorphy_substr']($word, -$GLOBALS['__phpmorphy_strlen']($suffix)) === $suffix)
            ) {
                $result[] = $annot;
            }
        }

        return count($result) ? $result : false;
    }

    protected function createCollector($limit) {
        return new phpMorphy_Morphier_PredictCollector($limit, $this->getAnnotDecoder());
    }
}

// ----------------------------
// Morphiers
// ----------------------------
abstract class phpMorphy_Morphier_Base implements phpMorphy_Morphier_Interface {
    protected
        /**
         * @var phpMorphy_Morphier_Finder_Interface
         */
        $finder,
        /**
         * @var phpMorphy_Morphier_Helper
         */
        $helper;

    public function __construct(phpMorphy_Morphier_Finder_Interface $finder, phpMorphy_Morphier_Helper $helper) {
        $this->finder = $finder;

        $this->helper = clone $helper;
        $this->helper->setAnnotDecoder($finder->getAnnotDecoder());
    }

    /**
     * @return phpMorphy_Morphier_Finder_Interface
     */
    public function getFinder() {
        return $this->finder;
    }

    /**
     * @return phpMorphy_Morphier_Helper
     */
    public function getHelper() {
        return $this->helper;
    }

    public function getAnnot($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->decodeAnnot($annots, true);
    }

    public function getWordDescriptor($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getWordDescriptor($word, $annots);
    }

    public function getAllFormsWithAncodes($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getAllFormsWithResolvedAncodes($word, $annots);
    }

    public function getPartOfSpeech($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getPartOfSpeech($word, $annots);
    }

    public function getBaseForm($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getBaseForm($word, $annots);
    }

    public function getPseudoRoot($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getPseudoRoot($word, $annots);
    }

    public function getAllForms($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getAllForms($word, $annots);
    }

    public function getAncode($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getAncode($annots);
    }

    public function getGrammarInfo($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getGrammarInfo($annots);
    }

    public function getGrammarInfoMergeForms($word) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->getGrammarInfoMergeForms($annots);
    }

    public function castFormByGramInfo($word, $partOfSpeech, $grammems, $returnOnlyWord = false, $callback = null) {
        if(false === ($annots = $this->finder->findWord($word))) {
            return false;
        }

        return $this->helper->castFormByGramInfo($word, $annots);
    }

    public function castFormByPattern($word, $patternWord, $returnOnlyWord = false, $callback = null) {
        if(false === ($orig_annots = $this->finder->findWord($word))) {
            return false;
        }

        if(false === ($pattern_annots = $this->finder->findWord($patternWord))) {
            return false;
        }

        return $this->helper->castFormByPattern(
            $word, $orig_annots,
            $patternWord, $pattern_annots,
            $returnOnlyWord,
            $callback
        );
    }
};

class phpMorphy_Morphier_Common extends phpMorphy_Morphier_Base {
    public function __construct(phpMorphy_Fsa_Interface $fsa, phpMorphy_Morphier_Helper $helper) {
        parent::__construct(
            new phpMorphy_Morphier_Finder_Common(
                $fsa,
                $this->createAnnotDecoder($helper)
            ),
            $helper
        );
    }

    protected function createAnnotDecoder(phpMorphy_Morphier_Helper $helper) {
        return phpMorphy_AnnotDecoder_Factory::create($helper->getGramInfo()->getEnds())->getCommonDecoder();
    }
};

class phpMorphy_Morphier_Predict_Suffix extends phpMorphy_Morphier_Base {
    public function __construct(phpMorphy_Fsa_Interface $fsa, phpMorphy_Morphier_Helper $helper) {
        parent::__construct(
            new phpMorphy_Morphier_Finder_Predict_Suffix(
                $fsa,
                $this->createAnnotDecoder($helper),
                $helper->getGramInfo()->getEncoding(),
                4
            ),
            $helper
        );
    }

    protected function createAnnotDecoder(phpMorphy_Morphier_Helper $helper) {
        return phpMorphy_AnnotDecoder_Factory::create($helper->getGramInfo()->getEnds())->getCommonDecoder();
    }
}

class phpMorphy_Morphier_Predict_Database extends phpMorphy_Morphier_Base {
    public function __construct(phpMorphy_Fsa_Interface $fsa, phpMorphy_Morphier_Helper $helper) {
        parent::__construct(
            new phpMorphy_Morphier_Finder_Predict_Databse(
                $fsa,
                $this->createAnnotDecoder($helper),
                $helper->getGramInfo()->getEncoding(),
                $helper->getGramInfo(),
                2,
                32
            ),
            $helper
        );
    }

    protected function createAnnotDecoder(phpMorphy_Morphier_Helper $helper) {
        return phpMorphy_AnnotDecoder_Factory::create($helper->getGramInfo()->getEnds())->getPredictDecoder();
    }
}

class phpMorphy_Morphier_Bulk implements phpMorphy_Morphier_Interface {
    protected
        $fsa,
        $root_trans,
        $helper,
        $notfound = array(),
        $graminfo;

    public function __construct(phpMorphy_Fsa_Interface $fsa, phpMorphy_Morphier_Helper $helper) {
        $this->fsa = $fsa;
        $this->root_trans = $fsa->getRootTrans();

        $this->helper = clone $helper;
        $this->helper->setAnnotDecoder($this->createAnnotDecoder($helper));

        $this->graminfo = $helper->getGramInfo();
    }

    public function getFsa() {
        return $this->fsa;
    }

    public function getHelper() {
        return $this->helper;
    }

    public function getGraminfo() {
        return $this->graminfo;
    }

    public function getNotFoundWords() {
        return $this->notfound;
    }

    protected function createAnnotDecoder(phpMorphy_Morphier_Helper $helper) {
        return new phpMorphy_AnnotDecoder_Common($helper->getGramInfo()->getEnds());
    }

    public function getAnnot($word) {
        $result = array();

        foreach($this->findWord($word) as $annot => $words) {
            $annot = $this->helper->decodeAnnot($annot, true);

            foreach($words as $word) {
                $result[$word][] = $annot;
            }
        }

        return $result;
    }

    public function getBaseForm($words) {
        $annots = $this->findWord($words);

        return $this->composeForms($annots, true, false, false);
    }

    public function getAllForms($words) {
        $annots = $this->findWord($words);

        return $this->composeForms($annots, false, false, false);
    }

    public function getPseudoRoot($words) {
        $annots = $this->findWord($words);

        return $this->composeForms($annots, false, true, false);
    }

    public function getPartOfSpeech($words) {
        $annots = $this->findWord($words);

        return $this->composeForms($annots, false, false, true);
    }

    protected function processAnnotsWithHelper($words, $method, $callWithWord = false) {
        $result = array();

        foreach($this->findWord($words) as $annot_raw => $words) {
            if($GLOBALS['__phpmorphy_strlen']($annot_raw) == 0) continue;

            if($callWithWord) {
                foreach($words as $word) {
                    $result[$word] = $this->helper->$method($word, $annot_raw);
                }
            } else {
                $result_for_annot = $this->helper->$method($annot_raw);

                foreach($words as $word) {
                    $result[$word] = $result_for_annot;
                }
            }
        }

        return $result;
    }

    public function getAncode($words) {
        return $this->processAnnotsWithHelper($words, 'getAncode');
    }

    public function getGrammarInfoMergeForms($words) {
        return $this->processAnnotsWithHelper($words, 'getGrammarInfoMergeForms');
    }

    public function getGrammarInfo($words) {
        return $this->processAnnotsWithHelper($words, 'getGrammarInfo');
    }

    public function getAllFormsWithAncodes($words) {
        return $this->processAnnotsWithHelper($words, 'getAllFormsWithResolvedAncodes', true);
    }

    public function getWordDescriptor($word) {
        return $this->processAnnotsWithHelper($words, 'getWordDescriptor', true);
    }

    protected function findWord($words) {
        $unknown_words_annot = '';

        $this->notfound = array();

        list($labels, $finals, $dests) = $this->buildPatriciaTrie($words);

        $annots = array();
        $unknown_words_annot = '';
        $stack = array(0, '', $this->root_trans);
        $stack_idx = 0;

        $fsa = $this->fsa;

        // TODO: Improve this
        while($stack_idx >= 0) {
            $n = $stack[$stack_idx];
            $path = $stack[$stack_idx + 1] . $labels[$n];
            $trans = $stack[$stack_idx + 2];
            $stack_idx -= 3; // TODO: Remove items from stack? (performance!!!)

            $is_final = $finals[$n] > 0;

            $result = false;
            if(false !== $trans && $n > 0) {
                $label = $labels[$n];

                $result = $fsa->walk($trans, $label, $is_final);

                if($GLOBALS['__phpmorphy_strlen']($label) == $result['walked']) {
                    $trans = $result['word_trans'];
                } else {
                    $trans = false;
                }
            }

            if($is_final) {
                if(false !== $trans && isset($result['annot'])) {
                    $annots[$result['annot']][] = $path;
                } else {
                    //$annots[$unknown_words_annot][] = $path;
                    $this->notfound[] = $path;
                }
            }

            if(false !== $dests[$n]) {
                foreach($dests[$n] as $dest) {
                    $stack_idx += 3;
                    $stack[$stack_idx] = $dest;
                    $stack[$stack_idx + 1] = $path;
                    $stack[$stack_idx + 2] = $trans;
                }
            }
        }

        return $annots;
    }

    protected function composeForms($annotsRaw, $onlyBase, $pseudoRoot, $partOfSpeech) {
        $result = array();

        // process found annotations
        foreach($annotsRaw as $annot_raw => $words) {
            if($GLOBALS['__phpmorphy_strlen']($annot_raw) == 0) continue;

            foreach($this->helper->decodeAnnot($annot_raw, $onlyBase) as $annot) {
                if(!($onlyBase || $pseudoRoot)) {
                    $flexias = $this->graminfo->readFlexiaData($annot);
                }

                $cplen = $annot['cplen'];
                $plen = $annot['plen'];
                $flen = $annot['flen'];

                if($partOfSpeech) {
                    $pos_id = $this->helper->extractPartOfSpeech($annot);
                }

                foreach($words as $word) {
                    if($flen) {
                        $base = $GLOBALS['__phpmorphy_substr']($word, $cplen + $plen, -$flen);
                    } else {
                        if($cplen || $plen) {
                            $base = $GLOBALS['__phpmorphy_substr']($word, $cplen + $plen);
                        } else {
                            $base = $word;
                        }
                    }

                    $prefix = $cplen ? $GLOBALS['__phpmorphy_substr']($word, 0, $cplen) : '';

                    if($pseudoRoot) {
                        $result[$word][$base] = 1;
                    } else if($onlyBase) {
                        $form = $prefix . $annot['base_prefix'] . $base . $annot['base_suffix'];

                        $result[$word][$form] = 1;
                    } else if($partOfSpeech) {
                        $result[$word][$pos_id] = 1;
                    } else {
                        for($i = 0, $c = count($flexias); $i < $c; $i += 2) {
                            $form = $prefix . $flexias[$i] . $base . $flexias[$i + 1];
                            $result[$word][$form] = 1;
                        }
                    }
                }
            }
        }

        for($keys = array_keys($result), $i = 0, $c = count($result); $i < $c; $i++) {
            $key = $keys[$i];

            $result[$key] = array_keys($result[$key]);
        }

        return $result;
    }

    protected function buildPatriciaTrie($words) {
        if(!is_array($words)) {
            throw new phpMorphy_Exception("Words must be array");
        }

        sort($words);

        $stack = array();
        $prev_word = '';
        $prev_word_len = 0;
        $prev_lcp = 0;

        $state_labels = array();
        $state_finals = array();
        $state_dests = array();

        $state_labels[] = '';
        $state_finals = '0';
        $state_dests[] = array();

        $node = 0;

        foreach($words as $word) {
            if($word == $prev_word) {
                continue;
            }

            $word_len = $GLOBALS['__phpmorphy_strlen']($word);
            // find longest common prefix
            for($lcp = 0, $c = min($prev_word_len, $word_len); $lcp < $c && $word[$lcp] == $prev_word[$lcp]; $lcp++);

            if($lcp == 0) {
                $stack = array();

                $new_state_id = count($state_labels);

                $state_labels[] = $word;
                $state_finals .= '1';
                $state_dests[] = false;

                $state_dests[0][] = $new_state_id;

                $node = $new_state_id;
            } else {
                $need_split = true;
                $trim_size = 0; // for split

                if($lcp == $prev_lcp) {
                    $need_split = false;
                    $node = $stack[count($stack) - 1];
                } elseif($lcp > $prev_lcp) {
                    if($lcp == $prev_word_len) {
                        $need_split = false;
                    } else {
                        $need_split = true;
                        $trim_size = $lcp - $prev_lcp;
                    }

                    $stack[] = $node;
                } else {
                    $trim_size = $GLOBALS['__phpmorphy_strlen']($prev_word) - $lcp;

                    for($stack_size = count($stack) - 1; ;--$stack_size) {
                        $trim_size -= $GLOBALS['__phpmorphy_strlen']($state_labels[$node]);

                        if($trim_size <= 0) {
                            break;
                        }

                        if(count($stack) < 1) {
                            throw new phpMorphy_Exception('Infinite loop posible');
                        }

                        $node = array_pop($stack);
                    }

                    $need_split = $trim_size < 0;
                    $trim_size = abs($trim_size);

                    if($need_split) {
                        $stack[] = $node;
                    } else {
                        $node = $stack[$stack_size];
                    }
                }

                if($need_split) {
                    $node_key = $state_labels[$node];

                    // split
                    $new_node_id_1 = count($state_labels);
                    $new_node_id_2 = $new_node_id_1 + 1;

                    // new_node_1
                    $state_labels[] = $GLOBALS['__phpmorphy_substr']($node_key, $trim_size);
                    $state_finals .= $state_finals[$node];
                    $state_dests[] = $state_dests[$node];

                    // adjust old node
                    $state_labels[$node] = $GLOBALS['__phpmorphy_substr']($node_key, 0, $trim_size);
                    $state_finals[$node] = '0';
                    $state_dests[$node] = array($new_node_id_1);

                    // append new node, new_node_2
                    $state_labels[] = $GLOBALS['__phpmorphy_substr']($word, $lcp);
                    $state_finals .= '1';
                    $state_dests[] = false;

                    $state_dests[$node][] = $new_node_id_2;

                    $node = $new_node_id_2;
                } else {
                    $new_node_id = count($state_labels);

                    $state_labels[] = $GLOBALS['__phpmorphy_substr']($word, $lcp);
                    $state_finals .= '1';
                    $state_dests[] = false;

                    if(false !== $state_dests[$node]) {
                        $state_dests[$node][] = $new_node_id;
                    } else {
                        $state_dests[$node] = array($new_node_id);
                    }

                    $node = $new_node_id;
                }
            }

            $prev_word = $word;
            $prev_word_len = $word_len;
            $prev_lcp = $lcp;
        }

        return array($state_labels, $state_finals, $state_dests);
    }
}
