THESE/codes/graphe/GCmex1.9/LinkedBlockList.h

   1 /* Singly Linked List of Blocks */\r
   2 // This data structure should be used only for the GCoptimization class implementation\r
   3 // because it lucks some important general functions for general list, like remove_item()\r
   4 // The head block may be not full \r
   5 // For regular 2D grids, it's better to set GCLL_BLOCK_SIZE to 2\r
   6 // For other graphs, it should be set to the average expected number of neighbors\r
   7 // Data in linked list for the neighborhood system is allocated in blocks of size GCLL_BLOCK_SIZE \r
   8 \r
   9 #ifndef __LINKEDBLOCKLIST_H__\r
  10 #define __LINKEDBLOCKLIST_H__\r
  11 \r
  12 #define GCLL_BLOCK_SIZE 4  \r
  13 // GCLL_BLOCKSIZE should "fit" into the type BlockType. That is \r
  14 // if GCLL_BLOCKSIZE is larger than 255 but smaller than largest short integer\r
  15 // then  BlockType should be set to short\r
  16 typedef char BlockType;\r
  17 \r
  18 //The type of data stored in the linked list\r
  19 typedef void * ListType;\r
  20 \r
  21 class LinkedBlockList{\r
  22 \r
  23 public: \r
  24         void addFront(ListType item);\r
  25         inline bool isEmpty(){if (m_head == 0) return(true); else return(false);};\r
  26         inline LinkedBlockList(){m_head = 0; m_head_block_size = GCLL_BLOCK_SIZE;}; \r
  27         ~LinkedBlockList();\r
  28 \r
  29         // Next three functins are for the linked list traversal\r
  30         inline void setCursorFront(){m_cursor = m_head; m_cursor_ind = 0;};\r
  31         ListType next();\r
  32         bool hasNext();\r
  33 \r
  34 private:\r
  35         typedef struct LLBlockStruct{\r
  36                 ListType m_item[GCLL_BLOCK_SIZE];\r
  37                 struct LLBlockStruct *m_next;\r
  38         } LLBlock;\r
  39 \r
  40         LLBlock *m_head;\r
  41         // Remembers the number of elements in the head block, since it may not be full\r
  42         BlockType m_head_block_size;\r
  43         // For block traversal, points to current element in the current block\r
  44         BlockType m_cursor_ind;\r
  45         // For block traversal, points to current block in the linked list\r
  46         LLBlock *m_cursor;\r
  47 };\r
  48 \r
  49 #endif\r
  50 \r