00001 /* 00002 * Copyright (c) 2004 CSIRO ICT Centre 00003 * 00004 * $Id: ALStructure.h 587 2004-12-03 15:06:33Z nch $ 00005 */ 00006 00007 /* 00008 * ALStructure is the main class in the implementation of the 00009 * data structure used by IndexedActiveList. This data 00010 * structure is a collection of elements linked by two doubly 00011 * linked lists. One of these lists is sorted by right 00012 * ascension, while the other is sorted by declination. In 00013 * addition, a binary tree indexes the list on right ascension. 00014 * 00015 * This data structure assumes that objects are added in 00016 * ascending order of declination. If objects will not be added 00017 * in ascending order of declination, then do not use this data 00018 * structure: it won't work. 00019 */ 00020 00021 #ifndef ALSTRUCTURE_DEFINED 00022 #define ALSTRUCTURE_DEFINED 00023 00024 #include "ALElement.h" 00025 #include "ALNode.h" 00026 00027 00028 class ALStructure 00029 { 00030 public: 00031 ALStructure(); 00032 ~ALStructure(); 00033 00034 ALElement * getRaHead() { return raHead; }; 00035 ALElement * getDecHead() { return decHead; }; 00036 ALElement * getTail() { return tail; }; 00037 00038 void remove(ALElement * element); 00039 void add(ActiveObject * activeObject); 00040 00041 /* find the element whose content is smaller while still 00042 * being greater than or equal to a given value. Used 00043 * to find a starting object for walking the list. 00044 */ 00045 ALElement * findLeastGE(double ra); 00046 00047 /* find the element whose content is smaller while still 00048 * being greater than a given value. Used 00049 * to find a stopping object for walking the list. 00050 */ 00051 ALElement * findLeastG(double ra); 00052 00053 unsigned int getSize(); 00054 00055 private: 00056 unsigned int size; 00057 00058 ALElement sentinel; 00059 ALElement * raHead; 00060 ALElement * decHead; 00061 ALElement * tail; 00062 00063 ALNode * rootNode; 00064 00065 enum Child {left, right}; 00066 00067 ALStructure(ALStructure const &); 00068 ALStructure & operator=(ALStructure const &); 00069 00070 void findNode(ALElement * element, ALNode * root, ALNode ** parent, Child * child); 00071 ALNode * grabSuccessor(ALNode * node); 00072 void removeNode(ALElement * element); 00073 ALElement * insertNew(ActiveObject * object, ALElement * nextRa, ALElement * nextDec); 00074 ALElement * findLowerBound(double ra, bool allowEquality); 00075 00076 }; 00077 00078 #endif // ifndef ALSTRUCTURE_DEFINED