OpenEuphoria

Re: ADTs in Euphoria

• Posted by S Ns <sw at PARADISE.NET.NZ> Dec 21, 2000
• 525 views

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