After the Greek Variant of EERTREE program, I decide to make the english version. M2000 has two vocabularies, Greek and English, Also using the editor and utilizing F5 and Shift F5 we can find and change words or part of words (using Shift).
About the new variant:
We have one class, the MakeTree class, which we make a new object each time we start a palindrome search, We provide one by one character through the call of GetOne, a public member of object of class MakeTree, Each time the internal state change. We can show the internal state, the Structure using the member ShowTheStructure (M2000 isn't case sensitive, except for string type of labels, which rare used). We have to provide a document object (it is like a string, but internal has a strucutre of paragraphs. Also the = not replace the document with new value but append the value. Also these objects have always the $ suffix, and return a string in an expression, not the object. So we use by reference, using & prefix, to put the object in the ShowTheStructure)
The Get_the_children() function walk on the strecture and make the strings putting in an temporary stack (which expand easy), and as return value the stack object converted to array object (moving fast internal stack values to a tuple - array of one dimension. Tuple have some #functions which used as toppings to convert them, and here we use the #Str() function to make a string from all tupke items.
We expect the export to clipboars (and on screen, of M2000 environment, which we have to press space or click nouse button, because Report command has a "more" function, and stop on every 3/4 of lines display of current display format).
First number (001) is 1 internal and is the key for Tree list for specific Node. Second number is the length, and third number is the suffix. Some node have items in the myedges list. In 001 we have three items. We see keys as characters and values as numbers (the value 2 correspond to 002, is a soft link to Node(2)). Lists in M2000 works using hash tables, very fast.
So our internal structure is a List of Nodes, and each Node have three members, one of which is a List of Edges (keys of signle characters and values actually keys of List of Nodes). The other two members of Node object are Length and Suffix, and used for the construction based on input only.
Although we use the display of structure at the end, we can use it in any step to follow the construction of the structure.
The idea of eertree palindrome search tree are of Mikhail Rubinchik, Arseny M. Shur, 2015.
1. "eertree"
"ee", "e", "r", "t", "rtr", "ertre", "eertree"
Structure:
001 -1 1 {e}:=2 {r}:=4 {t}:=5
000 0 1 {e}:=3
002 1 0
003 2 2
004 1 0
005 1 0 {r}:=6
006 3 4 {e}:=7
007 5 2 {e}:=8
008 7 3
2. "banana"
"b", "a", "n", "ana", "nan", "anana"
Structure:
001 -1 1 {b}:=2 {a}:=3 {n}:=4
000 0 1
002 1 0
003 1 0 {n}:=6
004 1 0 {a}:=5
005 3 3
006 3 4 {a}:=7
007 5 5
3. "0123214bb5a7aaaa"
"bb", "aa", "aaaa", "0", "1", "2", "3", "4", "b", "5", "a", "7", "a7a", "aaa", "232", "12321"
Structure:
001 -1 1 {0}:=2 {1}:=3 {2}:=4 {3}:=5 {4}:=8 {b}:=9 {5}:=11 {a}:=12 {7}:=13
000 0 1 {b}:=10 {a}:=15
002 1 0
003 1 0
004 1 0
005 1 0 {2}:=6
006 3 4 {1}:=7
007 5 3
008 1 0
009 1 0
010 2 9
011 1 0
012 1 0 {a}:=16
013 1 0 {a}:=14
014 3 12
015 2 12 {a}:=17
016 3 15
017 4 16
4. "aaaa7a5bb4123210"
"aa", "bb", "aaaa", "a", "7", "5", "b", "4", "1", "2", "3", "0", "232", "12321", "a7a", "aaa"
Structure:
001 -1 1 {a}:=2 {7}:=6 {5}:=8 {b}:=9 {4}:=11 {1}:=12 {2}:=13 {3}:=14 {0}:=17
000 0 1 {a}:=3 {b}:=10
002 1 0 {a}:=4
003 2 2 {a}:=5
004 3 3
005 4 4
006 1 0 {a}:=7
007 3 2
008 1 0
009 1 0
010 2 9
011 1 0
012 1 0
013 1 0
014 1 0 {2}:=15
015 3 13 {1}:=16
016 5 12
017 1 0
So this is the program:
\\ https://rosettacode.org/wiki/eertree
Class MakeTree {
Private:
Tree=List
a$, Suffix=1
Class Node {
Private:
myedges=List
Public:
Suffix=0
Property Length {Value}
Function edges(a$) {
=-1 : If Exist(.myedges, a$) Then =Eval(.myedges)
}
Function ListKey$(Here) {
=Eval$(.myedges, Here)
}
Function Where(Here) {
=.myedges(Here!)
}
Function EdgesNumber() {
=Len(.myedges)
}
Module Append_edge (a$, there) {
Append .myedges, a$:=there
}
Class:
Module Node (.[Length]) {
Read ? .Suffix
}
}
Public:
Module GetOne(x$) {
.a$+=x$
i=Len(.a$)
n=.Suffix
Do {
k=.Tree(n).Length
b=i-k-1
If b>0 Then If Mid$(.a$,b,1)=x$ Then Exit
n=.Tree(n).Suffix
} Always
e=.Tree(n).edges(x$)
If e>=0 Then .Suffix<=e :Continue
.Suffix<=Len(.Tree)
Append .Tree, .Suffix:=.Node(k+2)
.Tree(n).Append_edge x$, .Suffix
If .Tree(.Suffix).Length=1 Then .Tree(.Suffix).Suffix=0 : Continue
Do {
n=.Tree(n).Suffix
b=i-.Tree(n).Length-1
If b>1 Then If Mid$(.a$, b,1)=x$ Then Exit
} Always
e=.Tree(n).edges(x$)
If e>=0 Then .Tree(.Suffix).Suffix=e
}
Module ShowTheStructure (&here$){
For i=0 To Len(.Tree)-1
thatKey$=Eval$(.Tree, i)
For .Tree(i!) {
d$=Format$("{0}{1::-3}{2::-3}",Str$(thatKey$,"000 "),.Length,.Suffix)
If .EdgesNumber()>0 Then
For k=0 To .EdgesNumber()-1
d$+=" {"+.ListKey$(k)+"}:="+.Where(k)
Next
End If
here$=chr$(9)+d$+{
}
}
Next
}
Function Get_the_children() {
Data 0, "", 1, ""
ο=Stack
While Not Empty {
Read n, root$
For .Tree(n) {
Μ=.EdgesNumber()
If Μ=0 Then Continue
Μ--
For i=0 To Μ {
x$= .ListKey$(i)
nxt=.Where(i)
p$ = If$(n=1 -> x$, x$+root$+x$)
Stack ο {Data p$}
Push p$, nxt
}
}
}
= Array(ο)
}
Class:
Module MakeTree {
Append .Tree, 1:=.Node(-1,1),0:=.Node(0,1)
}
}
Palindromo=Lambda many (a$) ->{
Document doc$
Tree=MakeTree()
For i=1 To Len(a$)
Tree.GetOne Mid$(a$,i,1)
Next
many++
doc$= many+". "+Quote$(a$)+{
}
doc$ = Quote$(Tree.Get_the_children()#Str$(Quote$(", ")))+{
Structure:
}
Tree.ShowTheStructure &doc$
=doc$
}
Document Final$
Final$ = Palindromo("eertree")
Final$ = Palindromo("banana")
Final$ = Palindromo("0123214bb5a7aaaa")
Final$ = Palindromo(StrRev$("0123214bb5a7aaaa"))
Report Final$
Clipboard Final$
