ALStructure.h

Go to the documentation of this file.
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
Generated on Mon Oct 4 10:39:55 2010 for Matching.kdevelop by  doxygen 1.6.3