Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Source file indexTrie.ml
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169(**************************************************************************)(* *)(* Copyright 2013 OCamlPro *)(* *)(* All rights reserved. This file is distributed under the terms of *)(* the Lesser GNU Public License version 3.0. *)(* *)(* This software 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 *)(* Lesser GNU General Public License for more details. *)(* *)(**************************************************************************)let(!!)=Lazy.forcetype('a,'b)t={value:'blist;children:('a*('a,'b)t)listLazy.t;}letcreate ?(children =lazy[])?value()=letvalue=match valuewithSomev->[v]|None ->[]in{children;value;}letempty=create()letreclist_map_filterf=function|[]->[]|h::tl->matchfhwith|Someh->h::list_map_filterftl|None->list_map_filterftlletmapftree=letrecauxrev_pathtree={value =(match tree.valuewith|[]->[]|v->List.map(f(List.revrev_path))v);children =lazy (List.map(fun(key,value)->(key,aux(key::rev_path)value))!!(tree.children))}inaux[]treeletiterftree=let recauxrev_pathtree=List.iter(f(List.revrev_path))tree.value;List.iter(fun(k,v)->aux(k::rev_path)v)!!(tree.children)inaux[]treeletfold0ftree acc=letrecauxacctrev_path =letacc=List.fold_right(fun(key,n)acc ->auxaccn(key::rev_path))!!(t.children)accinmatcht.valuewith|[]->acc|values->facc(List.revrev_path)valuesinauxacctree[]letfoldf=fold0(funaccpathvalues->List.fold_left(funaccv->faccpath v)accvalues)letsubtreepath=letrecauxtree=function|[]->tree|h::tl->aux(List.assoch!!(tree.children))tlintry auxtreepathwithNot_found->emptyletfind_alltreepath=letrecauxtree=function|h::tl ->aux(List.assoch!!(tree.children))tl|[]->tree.valueintryauxtreepathwithNot_found->[]let findtreepath=matchfind_alltreepathwith|v::_->v|[]->raiseNot_foundletmemtreepath=letrecauxtree=function|h::tl ->aux(List.assoch!!(tree.children))tl|[]->tree.value<>[]intryauxtreepathwithNot_found->false(* maps f on the element of assoc list children with key [key], appending a
new empty child if necessary *)letlist_map_assocfchildrenkeyempty=letrecauxacc=function|[]->List.rev_appendacc[key,fempty]|(k,v)as child::children->ifk=keythenList.rev_appendacc((key,fv)::children)elseaux(child::acc)childreninaux[]childrenletrecmap_subtree tree pathf=matchpathwith|[]->ftree|h::tl->let children=lazy(list_map_assoc (funn->map_subtreentlf)!!(tree.children)hempty)in{treewithchildren}letsettreepathvalue =map_subtreetreepath(funt->{twithvalue=[value]})letset_lazytreepathlazy_value=map_subtree treepath (funt->{twithvalue=[!!lazy_value]})letaddtreepathvalue=map_subtreetreepath(funt->{twithvalue=value::t.value})letadd_lazytreepathlazy_value=map_subtree treepath (funt->{twithvalue=!!lazy_value::t.value})letunsettreepath=map_subtreetreepath(funt->{twithvalue=[]})letrecfilter_keysftree={treewithchildren =lazy (list_map_filter(fun(key,n)->iffkeythenSome(key,filter_keysfn)elseNone)!!(tree.children))}letgrafttreepathnode=map_subtree tree path (funt->{twithchildren=node.children})letgraft_lazytreepathlazy_node=map_subtreetreepath(funt->{twithchildren=lazy!!(!!lazy_node.children)})letrecmerge ?(values=funv1v2->v2@v1)t1 t2=letrecaux l1l2=matchl1,l2with|((k1,v1)ash1::tl1),((k2,v2)ash2::tl2)->ifk1 <k2thenh1::auxtl1l2elseifk2<k1thenh2::auxl1tl2else(k1,merge~valuesv1v2):: auxtl1tl2|[],l|l,[]->linletvalue=valuest1.valuet2.valueinletcompare_keys(k1,_)(k2,_)=comparek1k2inletchildren=lazy(letc1=List.sortcompare_keys(Lazy.forcet1.children)inletc2=List.sortcompare_keys(Lazy.forcet2.children)inauxc1c2)in{value;children}letappendtree(path,node)=map_subtree tree path (funt->mergetnode)