Back to index

texmacs  1.0.7.15
list_environment.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : list_environment.hpp
00004 * DESCRIPTION: linked lists of several environments
00005 * COPYRIGHT  : (C) 2006  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #include "list_environment.hpp"
00013 
00014 tree list_environment_rep::uninit (UNINIT);
00015 
00016 /******************************************************************************
00017 * Environment compression: when 'misses' becomes large, the environment
00018 * is automatically compressed so as to reduce subsequent access times
00019 ******************************************************************************/
00020 
00021 void
00022 list_environment_rep::compress () {
00023   while (!is_nil (next->next) &&
00024         env->size > next->env->size + next->next->env->size)
00025     next->compress ();
00026     
00027   int new_size= env->size+ next->env->size;
00028   int new_n=2;
00029   while (new_n < new_size) new_n= new_n<<1;
00030   basic_environment new_env (new_n);
00031   new_env->multiple_insert (next->env->a, next->env->n);
00032   new_env->multiple_write (env->a, env->n);
00033   misses= 0;
00034   env   = new_env;
00035   next  = next->next;
00036 }
00037 
00038 /******************************************************************************
00039 * A method for fast read access
00040 ******************************************************************************/
00041 
00042 tree*
00043 list_environment_rep::raw_read (int key) {
00044   tree* r= env->raw_read (key);
00045   if (r != NULL || is_nil (next)) return r;
00046   misses++;
00047   if (misses >= env->size + next->env->size) {
00048     compress ();
00049     return raw_read (key);
00050   }
00051   else return next->raw_read (key);
00052 }
00053 
00054 /******************************************************************************
00055 * Printing
00056 ******************************************************************************/
00057 
00058 void
00059 list_environment_rep::print (const string& prefix) {
00060   cout << prefix << "List environment" << LF;
00061   env->print (prefix * "|  ");
00062   list_environment it= next;
00063   while (!is_nil (it)) {
00064     it->env->print (prefix * "|  ");
00065     it= it->next;
00066   }
00067 }
00068 
00069 /******************************************************************************
00070 * Flattening the environment
00071 ******************************************************************************/
00072 
00073 int
00074 total_size (list_environment l) {
00075   if (is_nil (l)) return 0;
00076   return l->env->size + total_size (l->next);
00077 }
00078 
00079 static void
00080 flatten (basic_environment& env, list_environment l) {
00081   if (is_nil (l->next))
00082     env->multiple_insert (l->env->a, l->env->n);
00083   else {
00084     flatten (env, l->next);
00085     env->multiple_write (l->env->a, l->env->n);
00086   }
00087 }
00088 
00089 basic_environment
00090 flatten (list_environment l) {
00091   if (is_nil (l)) return basic_environment (2);
00092   if (is_nil (l->next)) return l->env;
00093   int size= total_size (l);
00094   int n=2;
00095   while (n < size) n= n<<1;
00096   basic_environment env (n);
00097   flatten (env, l);
00098   return env;
00099 }