00001 /***************************************************************************** 00002 * Copyright (C) 2000 Jim Kent. This source code may be freely used * 00003 * for personal, academic, and non-profit purposes. Commercial use * 00004 * permitted only by explicit agreement with Jim Kent (jim_kent@pacbell.net) * 00005 *****************************************************************************/ 00006 /* spaceSaver - routines that help layout 1-D objects into a 00007 * minimum number of tracks so that no two objects overlap 00008 * within a single track. */ 00009 #ifndef SPACESAVER_H 00010 #define SPACESAVER_H 00011 00012 struct spaceSaver 00013 /* Help layout 1-D objects onto multiple tracks so that 00014 * no two objects overlap on a single track. */ 00015 { 00016 struct spaceSaver *next; /* Next in list. */ 00017 struct spaceNode *nodeList; /* List of things put in space saver. */ 00018 struct spaceRowTracker *rowList; /* List of rows. */ 00019 int rowCount; /* Number of rows. */ 00020 int winStart,winEnd; /* Start and end of area we're modeling. */ 00021 int cellsInRow; /* Number of cells per row. */ 00022 double scale; /* What to scale by to get to cell coordinates. */ 00023 int maxRows; /* Maximum number of rows. */ 00024 boolean isFull; /* Set to true if can't fit data into maxRows. */ 00025 }; 00026 00027 struct spaceNode 00028 /* Which row is this one on? */ 00029 { 00030 struct spaceNode *next; /* Next in list. */ 00031 int row; /* Which row, starting at zero. */ 00032 void *val; 00033 }; 00034 00035 struct spaceRowTracker 00036 /* Keeps track of how much of row is used. */ 00037 { 00038 struct spaceRowTracker *next; /* Next in list. */ 00039 bool *used; /* A flag for each spot used. */ 00040 }; 00041 00042 struct spaceSaver *spaceSaverMaxCellsNew(int winStart, int winEnd, int maxRows, int maxCells); 00043 /* Create a new space saver around the given window. */ 00044 00045 struct spaceSaver *spaceSaverNew(int winStart, int winEnd, int maxRows); 00046 /* Create a new space saver around the given window. */ 00047 00048 void spaceSaverFree(struct spaceSaver **pSs); 00049 /* Free up a space saver. */ 00050 00051 struct spaceNode *spaceSaverAdd(struct spaceSaver *ss, int start, int end, void *val); 00052 /* Add a new node to space saver. */ 00053 00054 00055 struct spaceNode *spaceSaverAddOverflow(struct spaceSaver *ss, int start, int end, 00056 void *val, boolean allowOverflow); 00057 /* Add a new node to space saver. Returns NULL if can't fit item in 00058 * and allowOverflow == FALSE. If allowOverflow == TRUE then put items 00059 * that won't fit in first row (ends up being last row after 00060 * spaceSaverFinish()). */ 00061 00062 void spaceSaverFinish(struct spaceSaver *ss); 00063 /* Tell spaceSaver done adding nodes. */ 00064 #endif /* SPACESAVER_H */ 00065
1.5.2