1. ADTs in Euphoria
Hi I'm a newbie evaluating euphoria.
Could someone briefly illustrate (or give a reference to some
info on) how one would implement a doubly-linked list or
binary search tree in Euphoria?
Thanks in advance.
--sns
2. Re: ADTs in Euphoria
sns,
Not sure if this is what you mean, but in the RDS archives,
http://www.rapideuphoria.com/contrib.htm
Jiri Babor has "Associative Lists", Routines for manipulating lists of
key/value pairs.
Can download directly from:
http://www.rapideuphoria.com/list.zip
Dan Moyer
----- Original Message -----
From: "S Ns" <sw at PARADISE.NET.NZ>
To: <EUPHORIA at LISTSERV.MUOHIO.EDU>
Sent: Wednesday, December 20, 2000 5:44 AM
Subject: ADTs in Euphoria
> Hi I'm a newbie evaluating euphoria.
>
> Could someone briefly illustrate (or give a reference to some
> info on) how one would implement a doubly-linked list or
> binary search tree in Euphoria?
>
> Thanks in advance.
>
> --sns
3. Re: ADTs in Euphoria
On Thu, 21 Dec 2000, S Ns wrote:
> Hi I'm a newbie evaluating euphoria.
>
> Could someone briefly illustrate (or give a reference to some
> info on) how one would implement a doubly-linked list or
> binary search tree in Euphoria?
>
> Thanks in advance.
>
> --sns
>
Both of these are a little more difficult, and less effective implemented
in Euphoria than implemented in C since Euphoria does not support
pointers, and it already has a dynamic array - the sequence.
Doubly linked lists can be completely replaced by a simple sequence, since
sequences are dynamic arrays. Instead of dealing with pointers etc. you
can just use append, prepend, & and subscripts to get the same
functionality.
Binary search trees can also be implemented in multi-dimensional
sequences, though all the subscripting would probably make them rather
ineffective.
Of course, you could use allocate, peek, poke, and free to do a C-like
implementation of the above. However, these are all rather expensive
functions and it is much faster to use sequences and other built-in
Euphoria data types.
Jeff Fielding
4. Re: ADTs in Euphoria
In reply to my query:
>Hi I'm a newbie evaluating euphoria.
>
>Could someone briefly illustrate (or give a reference to some
>info on) how one would implement a doubly-linked list or
>binary search tree in Euphoria?
>
>Thanks in advance.
>
>--sns
Dan Moyer kindly replied:
-------------------------
Not sure if this is what you mean, but in the RDS archives,
http://www.rapideuphoria.com/contrib.htm
Jiri Babor has "Associative Lists", Routines for manipulating lists of
key/value pairs.
Can download directly from:
http://www.rapideuphoria.com/list.zip
and Jeff Fielding expanded:
---------------------------
Both of these are a little more difficult, and less effective implemented
in Euphoria than implemented in C since Euphoria does not support
pointers, and it already has a dynamic array - the sequence.
Doubly linked lists can be completely replaced by a simple sequence, since
sequences are dynamic arrays. Instead of dealing with pointers etc. you
can just use append, prepend, & and subscripts to get the same
functionality.
Binary search trees can also be implemented in multi-dimensional
sequences, though all the subscripting would probably make them rather
ineffective.
Of course, you could use allocate, peek, poke, and free to do a C-like
implementation of the above. However, these are all rather expensive
functions and it is much faster to use sequences and other built-in
Euphoria data types.
---------------------------------------------------------------------
I'd like to be able to use Euphoria for more than
just little scripts.
>From the version 2.2 reference manual:
-------------------------------------
<quote>
2.3 Euphoria versus Conventional Languages
==========================================
By basing Euphoria on this one, simple, general, recursive
data structure, a tremendous amount of the complexity
normally found in programming languages has been avoided.
The arrays, structures, unions, arrays of records,
multidimensional arrays, etc. of other languages can all
be easily represented in Euphoria with sequences. **So can
higher-level structures such as lists, stacks, queues, trees etc.**
</quote>
The last line talks about a capability that is important to
me. I think it can be done 'fairly' efficiently after all
RDS mention porting apps from C to Eu and advertise this
service on their website.
I don't know if this is possible, but I'll just sketch
it anyway as indication. Look at a binary tree:
The node is a 3-element sequence where element:
1. is the data (this could be a record - represented as a
sequence of course)
2. is the left child which is a node sequence like the
parent (recursive)
3. is the right child like 2.
I don't know if 2 and 3 are possible in this fashion.
I don't think that this is the same as Jeff's
mutlidimensional sequence.
If this is possible in Eu then we have to implement some
operations: e.g. assume our tree is tree1:
our interface operations could be:
tree_new(tree1)
tree_add(tree1, some_data)
tree_find(tree1, some_data)
tree_copy(tree2, tree1)
Clearly, we need a function to traverse the tree.
So,
if we can represent the node and a traversal function
we are most of the way there.
Thoughts?
Thanks in advance.
-- sns
5. Re: ADTs in Euphoria
Hi sns,
Without going into details .... cause I'm just a bit busy now ...
you might like to look in Euphoria\demo directory.
There is a demo prograsm called tree.ex - that counts words by adding
them to a binary tree.
There is also animal.ex which states that it uses a "tree like" structure
for a very simple Expert system that guesses animals.
Hope this hepls.
Ray Smith
On Thu, 21 Dec 2000 12:39:23 +1300, S Ns <sw at PARADISE.NET.NZ> wrote:
>In reply to my query:
>
>>Hi I'm a newbie evaluating euphoria.
>>
>>Could someone briefly illustrate (or give a reference to some
>>info on) how one would implement a doubly-linked list or
>>binary search tree in Euphoria?
>>
>>Thanks in advance.
>>
>>--sns
>
>Dan Moyer kindly replied:
>-------------------------
>Not sure if this is what you mean, but in the RDS archives,
>http://www.rapideuphoria.com/contrib.htm
>Jiri Babor has "Associative Lists", Routines for manipulating lists of
>key/value pairs.
>
>Can download directly from:
>http://www.rapideuphoria.com/list.zip
>
>and Jeff Fielding expanded:
>---------------------------
>Both of these are a little more difficult, and less effective implemented
>in Euphoria than implemented in C since Euphoria does not support
>pointers, and it already has a dynamic array - the sequence.
>
>Doubly linked lists can be completely replaced by a simple sequence, since
>sequences are dynamic arrays. Instead of dealing with pointers etc. you
>can just use append, prepend, & and subscripts to get the same
>functionality.
>
>Binary search trees can also be implemented in multi-dimensional
>sequences, though all the subscripting would probably make them rather
>ineffective.
>
>Of course, you could use allocate, peek, poke, and free to do a C-like
>implementation of the above. However, these are all rather expensive
>functions and it is much faster to use sequences and other built-in
>Euphoria data types.
>---------------------------------------------------------------------
>
>I'd like to be able to use Euphoria for more than
>just little scripts.
>
>From the version 2.2 reference manual:
>-------------------------------------
><quote>
>
> 2.3 Euphoria versus Conventional Languages
> ==========================================
>
> By basing Euphoria on this one, simple, general, recursive
> data structure, a tremendous amount of the complexity
> normally found in programming languages has been avoided.
> The arrays, structures, unions, arrays of records,
> multidimensional arrays, etc. of other languages can all
> be easily represented in Euphoria with sequences. **So can
> higher-level structures such as lists, stacks, queues, trees etc.**
>
></quote>
>
>The last line talks about a capability that is important to
>me. I think it can be done 'fairly' efficiently after all
>RDS mention porting apps from C to Eu and advertise this
>service on their website.
>
>I don't know if this is possible, but I'll just sketch
>it anyway as indication. Look at a binary tree:
>
>The node is a 3-element sequence where element:
>1. is the data (this could be a record - represented as a
> sequence of course)
>2. is the left child which is a node sequence like the
> parent (recursive)
>3. is the right child like 2.
>
>I don't know if 2 and 3 are possible in this fashion.
>
>I don't think that this is the same as Jeff's
>mutlidimensional sequence.
>
>If this is possible in Eu then we have to implement some
>operations: e.g. assume our tree is tree1:
>
>our interface operations could be:
>
> tree_new(tree1)
> tree_add(tree1, some_data)
> tree_find(tree1, some_data)
> tree_copy(tree2, tree1)
>
>Clearly, we need a function to traverse the tree.
>
>So,
>if we can represent the node and a traversal function
>we are most of the way there.
>
>Thoughts?
>
>Thanks in advance.
>
>-- sns
6. Re: ADTs in Euphoria
> From: S Ns
I think you can do what you're looking for fairly easily in Eu.
> I don't know if this is possible, but I'll just sketch
> it anyway as indication. Look at a binary tree:
>
> The node is a 3-element sequence where element:
> 1. is the data (this could be a record - represented as a
> sequence of course)
> 2. is the left child which is a node sequence like the
> parent (recursive)
> 3. is the right child like 2.
So:
sequence tree
tree = { "root",
{ "node1", { "node11", {}, {}}, { "node12", {} {} }},
{ "node2", { "node21", {}, {}}, { "node22", {}, {}}}}
> I don't know if 2 and 3 are possible in this fashion.
Technically, the complexity of a sequence is only limited by available
memory.
> I don't think that this is the same as Jeff's
> mutlidimensional sequence.
Actually, it probably is.
> If this is possible in Eu then we have to implement some
> operations: e.g. assume our tree is tree1:
>
> our interface operations could be:
>
> tree_new(tree1)
> tree_add(tree1, some_data)
> tree_find(tree1, some_data)
> tree_copy(tree2, tree1)
For this I think we need to know a little more about the structure of the
data in the tree, and what exactly you want these functions to do. But it
should be pretty simple once you know what you want to do.
Matt Lewis
http://www14.brinkster.com/matthewlewis
7. Re: ADTs in Euphoria
At 18:44 20/12/00 -0500, Ray Smith kindly replied:
>Hi sns,
>
>Without going into details .... cause I'm just a bit busy now ...
>you might like to look in Euphoria\demo directory.
>
>There is a demo prograsm called tree.ex - that counts words by adding
>them to a binary tree.
>
>There is also animal.ex which states that it uses a "tree like" structure
>for a very simple Expert system that guesses animals.
>
>Hope this hepls.
>
>Ray Smith
>
>
>
>On Thu, 21 Dec 2000 12:39:23 +1300, S Ns <sw at PARADISE.NET.NZ> wrote:
>
>>In reply to my query:
>>
>>>Hi I'm a newbie evaluating euphoria.
>>>
>>>Could someone briefly illustrate (or give a reference to some
>>>info on) how one would implement a doubly-linked list or
>>>binary search tree in Euphoria?
>>>
>>>Thanks in advance.
>>>
>>>--sns
>>
>>Dan Moyer kindly replied:
>>-------------------------
>>Not sure if this is what you mean, but in the RDS archives,
>>http://www.rapideuphoria.com/contrib.htm
>>Jiri Babor has "Associative Lists", Routines for manipulating lists of
>>key/value pairs.
>>
>>Can download directly from:
>>http://www.rapideuphoria.com/list.zip
>>
>>and Jeff Fielding expanded:
>>---------------------------
>>Both of these are a little more difficult, and less effective implemented
>>in Euphoria than implemented in C since Euphoria does not support
>>pointers, and it already has a dynamic array - the sequence.
>>
>>Doubly linked lists can be completely replaced by a simple sequence, since
>>sequences are dynamic arrays. Instead of dealing with pointers etc. you
>>can just use append, prepend, & and subscripts to get the same
>>functionality.
>>
>>Binary search trees can also be implemented in multi-dimensional
>>sequences, though all the subscripting would probably make them rather
>>ineffective.
>>
>>Of course, you could use allocate, peek, poke, and free to do a C-like
>>implementation of the above. However, these are all rather expensive
>>functions and it is much faster to use sequences and other built-in
>>Euphoria data types.
>>---------------------------------------------------------------------
>>
>>I'd like to be able to use Euphoria for more than
>>just little scripts.
>>
>>From the version 2.2 reference manual:
>>-------------------------------------
>><quote>
>>
>> 2.3 Euphoria versus Conventional Languages
>> ==========================================
>>
>> By basing Euphoria on this one, simple, general, recursive
>> data structure, a tremendous amount of the complexity
>> normally found in programming languages has been avoided.
>> The arrays, structures, unions, arrays of records,
>> multidimensional arrays, etc. of other languages can all
>> be easily represented in Euphoria with sequences. **So can
>> higher-level structures such as lists, stacks, queues, trees etc.**
>>
>></quote>
>>
>>The last line talks about a capability that is important to
>>me. I think it can be done 'fairly' efficiently after all
>>RDS mention porting apps from C to Eu and advertise this
>>service on their website.
>>
>>I don't know if this is possible, but I'll just sketch
>>it anyway as indication. Look at a binary tree:
>>
>>The node is a 3-element sequence where element:
>>1. is the data (this could be a record - represented as a
>> sequence of course)
>>2. is the left child which is a node sequence like the
>> parent (recursive)
>>3. is the right child like 2.
>>
>>I don't know if 2 and 3 are possible in this fashion.
>>
>>I don't think that this is the same as Jeff's
>>mutlidimensional sequence.
>>
>>If this is possible in Eu then we have to implement some
>>operations: e.g. assume our tree is tree1:
>>
>>our interface operations could be:
>>
>> tree_new(tree1)
>> tree_add(tree1, some_data)
>> tree_find(tree1, some_data)
>> tree_copy(tree2, tree1)
>>
>>Clearly, we need a function to traverse the tree.
>>
>>So,
>>if we can represent the node and a traversal function
>>we are most of the way there.
>>
>>Thoughts?
>>
>>Thanks in advance.
>>
>>-- sns
---------------------------------------------------------
Yep, that's what I was looking for. Thank you Ray.
--sns
8. Re: ADTs in Euphoria
Hi SNs,
>if we can represent the node and a traversal function
we are most of the way there.
>Thoughts?
I think you are most of the way there. I use ADTs all the time, love them
li'l thangs. I haven't had the need to implement binary trees in Euphoria
yet, but when I do, I expect to go about it in the way you suggest.
You can indeed represent a node as { data, leftChild, rightChild }, where
leftChild and rightChild are also nodes, or empty sequences. (You could
define an empty sequence as a node, but I don't think it's a good idea.)
For that matter, you can also create a "type treeNode":
-- begin *untested* code
-- I assume True and False have been defined as 1 and 0, respectively.
constant
TNdata = 1,
TNleftChild = 2,
TNrightChild = 3
type emptySequence(sequence candidate)
-- short form:
return sequence(candidate) and length(sequence) = 0
end type
type treeNode(sequence candidate)
integer isTreeNode
if sequence(candidate)
if length(candidate) = 3 then
-- In this example, candidate[TNdata] can be anything....
if (emptySequence(candidate[TNleftChild]
or treeNode(candidate[TNleftChild]))
and (emptySequence(candidate[TNrightChild]
or treeNode(candidate[TNrightChild])) then
isTreeNode = True
else
isTreeNode = False
end if
else
isTreeNode = False
end if
return isTreeNode
end type
-- end *untested* code
I hope that example gets you started, or moves you along a bit. I say
"example" 'coz obviously there is more than one way to do this.
George Henry
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com
9. ADTs in Euphoria
Binary trees can be implemented in Euphoria, but this imposes unnecessary
overhead (multiple subscripts) versus a simple sorted sequence. Here are
some routines.
type sorted_sequence(sequence s) -- slow, use this only when essential
integer len
len=length(s)
if len<2 then return 1 end if
for i=1 to len-1 do
if compare(s[1],s[2])>0 then return 0 end if -- out of order
end for
return 1 -- order is OK
end type
function find_sorted(object x,sequence s) -- find x in s
-- returns position if found, negative of position it would go in if not
found
integer min,max,mid,test
min=1
max=length(s)
while min<=max do
mid=floor((min+max)/2)
test=compare(x,s[mid])
if test=1 then -- in top half of sequence
min=mid+1
elseif test=-1 -- in bottom half of sequence
max=mid-1
else -- equal
return mid
end while
return -min
end function
function insert_sorted(object x,sequence s) -- insert x into s, unless
duplicated
integer index
index=find_sorted(x)
if index<0 then
return s[1..-index-1]&{x}&s[-index..length(s)] --return new
sequence
else
--error handling code could be added
return s
end if
end function
function remove_sorted(object x,sequence s) -- removes x from s, if present
integer index
index=find_sorted(x,s)
if index>0 then
return s[1..index-1]&s[index+1..length(s)] -- return new sequence
else
-- error handling code could be added
return s
end if
end function
-- Mike
