home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / GCC / GERLIB_DEV08B.LHA / gerlib / libg++ / etc / trie-gen / compact.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-12  |  3.2 KB  |  79 lines
  1. /* This may look like C code, but it is really -*- C++ -*- */
  2.  
  3. /* Compact a sparse 2-D matrix.  Uses the Tarjan and Yao algorithm
  4.    taken from the article ``Storing a Sparse Table'' in CACM, 1979.
  5.  
  6.    Copyright (C) 1989 Free Software Foundation, Inc.
  7.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  8.    
  9.    This file is part of GNU TRIE-GEN.
  10.    
  11.    GNU TRIE-GEN is free software; you can redistribute it and/or modify
  12.    it under the terms of the GNU General Public License as published by
  13.    the Free Software Foundation; either version 1, or (at your option)
  14.    any later version.
  15.    
  16.    GNU TRIE-GEN is distributed in the hope that it will be useful,
  17.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19.    GNU General Public License for more details.
  20.    
  21.    You should have received a copy of the GNU General Public License
  22.    along with GNU trie-gen; see the file COPYING.  If not, write to
  23.    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  24.  
  25. /* This really should go in the class scope, but alas g++ doesn't like that... */
  26. typedef int ITEM_TYPE;
  27.  
  28. class Compact_Matrix
  29. {
  30. public:
  31.               Compact_Matrix (ITEM_TYPE *mat, int rows, int cols);
  32.               Compact_Matrix (int default_rows = 0);
  33.   ITEM_TYPE   operator () (int i, int j);
  34.   void        operator () (int i, int j, ITEM_TYPE value);
  35.   void        output (void);
  36.  
  37. private:
  38.  
  39.   void init(int rows);
  40.  
  41.   struct Column_Node
  42.     {
  43.       int            index; /* Actual column index in the current row. */
  44.       ITEM_TYPE      value; /* Value at this index location. */
  45.       Column_Node   *next;  /* Pointer to next column in the row. */
  46.  
  47.       Column_Node (Column_Node *p, int i, ITEM_TYPE v)
  48.       : index (i), value (v), next (p) { }
  49.     };
  50.  
  51.   struct Row_Node
  52.     {
  53.       Column_Node   *col_list; // List of column index values for this row.
  54.       int            count;    // Count of total number of columns in the list.
  55.       Row_Node() { col_list = 0; count = 0; }
  56.     };
  57.  
  58.   int           max_col_count;   /* Total number of columns in largest row. */
  59.   int           total_cols;      /* Total number of columns in the matrix (if applicable). */
  60.   int           total_entries;   /* Total number of non-null entries in the matrix. */
  61.   int           compressed_len;  /* Size of the compacted matrix buffer. */
  62.   int          *row_offsets;     /* Dynamic buffer used for double-offset indexing. */
  63.   int          *checks;          /* Dynamic buffer used for double-offset indexing. */
  64.   int           current_rows;    /* Current items in ROW_VEC, at this point. */
  65.   int           max_rows;        /* Maximum size of ROW_VEC, at this point. */
  66.   Row_Node     *row_vec;         /* Dynamic buffer indexed by row number. */
  67.   Column_Node **bucket_vec;      /* Dynamic buffer used to sort by column count. */
  68.   ITEM_TYPE    *values;          /* Dynamic buffer containing non-null matrix values. */
  69.   ITEM_TYPE    *matrix;          /* Pointer to 2-D matrix (if appropriate). */
  70.   
  71.   void          resize (int new_size);
  72.   void          first_fit_decreasing (void);
  73.   void          bucket_sort (void);
  74.   void          output_lookup (void);
  75.   void          output_arrays (void);
  76.   void          dump_entries (void);
  77.   void          dump_bucket (void);
  78. };
  79.