I agree with Kerm: that's very exciting to see one figure out stuff like that. I've been working on programming language design since 2004 (arguably), and have figured out a lot of such stuff! ... If you look at the Antidisassemblage compiler, it's ... SLOW! Using a LUT is DEFINITELY the way to go for things like Tokens (I use something like that for mine). As for searching, if you are searching through predefined values (e.g. searching a table), I highly recommend using a binary search (which requires things to be stored in "order"). I will let you figure out what/how, but it's a must for speed if it's applicable. Smile
shkaboinka wrote:
As for searching, if you are searching through predefined values (e.g. searching a table), I highly recommend using a binary search (which requires things to be stored in "order").


That depends on the type of search Wink There are some things for which I prefer I radix tree.
elfprince13 wrote:
shkaboinka wrote:
As for searching, if you are searching through predefined values (e.g. searching a table), I highly recommend using a binary search (which requires things to be stored in "order").


That depends on the type of search Wink There are some things for which I prefer I radix tree.
Absolutely; I only wish radix and binary trees in particular were a little less clunky to use and modify in z80 ASM. Smile
KermMartian wrote:
Absolutely; I only wish radix and binary trees in particular were a little less clunky to use and modify in z80 ASM. Smile
If the order does not have to be perfectly strict, a heap would be more suitable where dynamic memory management is not a simple task (since it can all be managed in a static array). This is the structure often used for priority queues and allocation "heaps" (e.g. in C++).
In this case, I am just searching for labels and label names in a file. Otherwise, I already have two algorithms that sound like the above mentioned. Otherwise, I am not familiar with the terms here :/
Xeda112358 wrote:
In this case, I am just searching for labels and label names in a file. Otherwise, I already have two algorithms that sound like the above mentioned. Otherwise, I am not familiar with the terms here :/
The simplest form of a tree is what you might intuitively imagine. The tree has a root where all inserts, deletes, and searches start. It then branches into N branches (N=2 for a binary tree), then branches again at the end of each of those branches, etc until it reaches leaves. If every path in the tree is the same length, and you have L total leaves, that means you need only pass through log base N of L decisions (branch points) to get to any of the leaves, an efficiency of what we call O(log(L)) is computer sciency terms. By comparison, if you have a list of those L items that you have to search through, you have an efficiency of O(L), which is much worse. To put that in more solid numerical terms, if L=100, log base 2 of 100 is 6.64, meaning that the binary tree approach could be up to 100/6.64 = fifteen times faster than the linear search, or perhaps more like seven to eight times if you assume that on average you need to traverse 50% of the list to find the item you need.
Hmm, well at first I saw graph theory terms, but by the end of it, I still could not figure out how to code such a tree. Would this mean that I need to store the data in a non-linear design?
There are two ways to do this: The OO way and the non-OO way. Since OO is a bit hard to code in asm, I'll explain the non-OO way. The way this works is to encode the tree into an array. For example, if I have the following tree,

Code:

     4
   /   \
  2     6
 / \   / \
1   3 5   7


It would be encoded as:
[4,2,6,1,3,5,7]
So the first node in the tree is in 0, it's left child in 1, right in 2, and so on.
Can I see it applied? I am still not seeing it, sorry Sad
seana11 wrote:
There are two ways to do this: The OO way and the non-OO way. Since OO is a bit hard to code in asm, I'll explain the non-OO way. The way this works is to encode the tree into an array. For example, if I have the following tree,

Code:

     4
   /   \
  2     6
 / \   / \
1   3 5   7


It would be encoded as:
[4,2,6,1,3,5,7]
So the first node in the tree is in 0, it's left child in 1, right in 2, and so on.


Why as a flattened array? There *IS* a magic thing called structures and pointers Wink While initializing structures in assembly may sound like a pain, it's really as simple as just just declaring the arrays as static data at the end of the program (probably in a way, easier than C in some instances). First, I'll show a (what I find personally) better version, in C, which could be represented in assembly as well:


Code:
typedef enum{ no_match = 0, Apple, Accident, Java, Jiggle } radix_token;
// in case you don't know what an enum is, it allows the compiler to consider the names no_match to be equal to 0, Apple = 1, Accident = 2, etc.

typedef struct {
   char*entry; // the string it holds
   int nodes; // the number of nodes
   int token; // the result token value it will refer to
   radix_node*children[]; // an array of pointers to all children nodes
} radix_node;
typedef radix_node radix_head;


Then, you could then initialize the tree, so that there is a head node, and let's say two children with two children each. This can hold 4 possible outcomes in the tree, which we can use in this example as {"Java", "Jiggle", "Apple", "Accident"}. As you can imagine, they first split off as 'a' and 'j', and later compare the rest of the string contents:


Code:
radix_head head = {"\0", 2, no_match, { // the first array of two children
  {"A", 2, no_match, { // node for 'A' matches
    {"pple", 0 , Apple, NULL},  // Apple (notice the NULL array is because this is a bottom member of the tree
    {"ccident", 0, Accident , NULL} // Accident
  }},
  {"J", 2, { // node for 'J' matches
    {"ava", 0 , Java, NULL}, // Java
    {"iggle", 0 , Jiggle, NULL} // Jiggle
  }}
}};


The tree is now initialized; here would be a generic function that would take string input, and return a token value if found and matched, 0 otherwise:


Code:
radix_token find_match(char*entry, radix_head tree) {
   radix_node*cur_node = &tree; //cur_node points to the tree's head node
   int entry_string_offset = 0; // increases as we search into the string and match by chunks
   while(true) {
      _Bool advanced = false;
      for(int i = 0; i < cur_node->nodes; i++) { // loop through all sub-nodes
         if(memcmp(cur_node->entry, entry+entry_string_offset, strlen(cur_node->entry)) == 0) {
            // if the string content between the given value string's substring and the current node's value string are equal
            if(cur_node->children == NULL) { // if the matching node was a bottom of the tree
               return cur_node->token; // return the curren node's token
            } else {
               entry_string_offset += strlen(cur_node->entry); // advance the string's offset by the length of the string compared
               cur_node = cur_node->children[i]; //then make the node pointer point to the node with the correct answer
               advanced = true;
            }
         }
      }
      if(!advanced) {
         return no_match;
      }
   }
}


Then, calling it like this:


Code:
find_match("Apple", head);


Would ideally return a value of apple, also known as 1. Hope this application of it in a generally low-level approach helps! Smile
I am still not understanding it, but it will come to me eventually. I did, however, finally figure out how to get very nice 3-level grayscale to work on the calculator, so I made a program to display grayscale tilemaps. However, to make it better, I decided instead to add the last two sprite options (for Pt-On(, only)-- mask and gray. Since the tilemap routine hooks into the tile displaying routine, this means tilemaps get the same feature. WabbitEmu cannot get what it looks like on an actual calc, but here is a pretty close rendition (less flicker on a real calc) :
Oh wow, that looks really really cool! Surprised
Thanks Smile And that happens to be the map of an RPG I am working on (well, on and off). The next thing I am trying to get working is linking. I want to see if I can get two people to play normally, but have them show up on the other screen (if they are in the viewing window). Unfortunately, I cannot seem to make a working routine :[
Okay, here is an update (nothing with linking for a while). I have added a bunch of stuff since that last post including:

Switched the sine and cosine routine to using an LUT
conj( has been fixed to now handle notes.
Added support for 32-bit text output
Added the little E ([2nd][,]) for binary input
' for displaying a char by number with Text(
° for displaying ASCII with Text(
ln( for jumping to a line (relative)
Str support for storing to OS strings
Xtra var support (adding numbers to the end of Str, Pic,GDB)
Token hook and menu change
° for writing words when using [
[[ for writing all values as words
[( for writing hex, directly
/ (with a space after it) for doing signed division

A lot of this is pretty technical and would be best understood by versed Grammer coders. To draw attention to conj(, I finally figured out how to map the right frequencies to certain notes, so users now input a Note, Octave, and Duration to be played Smile I even have a working player that will parse files to play music. The syntax for the music player is pretty similar to Omnicalc's play( function, but the data is stored in programs.

So a link: Grammer 2
And I don't really have screenies for these kinds of updates :/ However, I do have a screenie of a few programs I made Smile
Inspired by a program from yeong:

Just a random thing I made:

The music player:
What Ashbad presented (the "flat array") is a heap. [b]Something simple[b] you could do is just keep a sorted list for your labels (or other things). Then, to find something, you store the first index and the last index in variables, and repeat this loop: take the "middle" index ((first+last)/2), and if the item at that index is it, then you found it. Otherwise, if the item is "less" than the middle item, then store the "middle" index to the variable holding the "last" index, and repeat; otherwise its greater than the middle index (because it's not less or equal), so store the middle index as the start index and try again. This allows you to find items VERY fast. This is much more efficient than a "check everything" algorithm (as long as you can make the list beforehand .... if you have to add or remove things from the list, then all the copying or values will make it no better). A heap stores it all the same way, but in such a way that you do not have to move very many items around to insert or remove things ... but you'd have to research that a bit, which is why I just suggested the "sorted list" idea.

By the way, those screenshots are AWESOME! Visual examples will definitely promote your language as people see what can be done with it Smile
Thanks! And I was thinking that since I would only have to "tokenise" then compiling programs it doesn't matter too much how fast it is. So I might just go with a similar method to yours Smile Plus, i can store the tokens all in alphabetical order, so that will really speed things up...
Xeda112358 wrote:
Thanks Smile And that happens to be the map of an RPG I am working on (well, on and off). The next thing I am trying to get working is linking. I want to see if I can get two people to play normally, but have them show up on the other screen (if they are in the viewing window). Unfortunately, I cannot seem to make a working routine :[
You know that I'm going to suggest CALCnet here. Wink
Hmm, is there some way I can integrate that into Grammer? If there is a rather easy way to use it, I would be all for it. For later versions of Grammer (Grammer 3 and 4) I would prefer to use my own routines if possible, but for now, I am okay with using CALCnet Smile
Xeda112358 wrote:
Hmm, is there some way I can integrate that into Grammer? If there is a rather easy way to use it, I would be all for it. For later versions of Grammer (Grammer 3 and 4) I would prefer to use my own routines if possible, but for now, I am okay with using CALCnet Smile
Currently, I suggest having the programs hook into Doors CS somehow (they already compile to ASM programs that can run under Doors CS, right?).
Sorry, I am confused... what does "they" refer to in your parentheses?
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 2 of 4
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement