// ChangeSorter.cpp: implementation of the ChangeSorter class. // ////////////////////////////////////////////////////////////////////// #include "ChangeSorter.h" ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// ChangeSorter::ChangeSorter() { head = NULL; seek = NULL; tail = NULL; counter = 0; size = 0; } ChangeSorter::~ChangeSorter() { if (head != NULL) delete head; } void ChangeSorter::AddChange(StrBuf input) { if (head == NULL) //empty list? { head = new ChangeNode(input); seek = head; tail = head; counter = 1; size = 1; return; } if ((input == head->change) || (input == seek->change) || (input == tail->change)) return; //value is already in the list, so add nothing ChangeNode* newnode = new ChangeNode(input); bool fwd; int n = newnode->value; int h = head->value; int s = seek->value; int t = tail->value; if (n < h) // new node is before head { newnode->next = head; head->prev = newnode; head = newnode; counter++; size++; return; } else if (t < n) // new node is after tail { newnode->prev = tail; tail->next = newnode; tail = newnode; size++; return; } else if (n < s) //new node is between head and seek { if ( (n - h) > (s - n) ) //closer to seek { fwd = false; } else //closer to head { seek = head; counter = 1; fwd = true; } } else if (s < n) // new node is between seek and tail { if ( (n - s) > (t - n) ) //closer to tail { fwd = false; seek = tail; counter = size; } else //closer to seek { fwd = true; } } else exit(1); // ChangeSorter invariant violated! if (fwd) // new node goes somewhere after seek { while (seek) { if (seek->value == n) return; else if (n < seek->value) //insert before seek { newnode->prev = seek->prev; newnode->next = seek; newnode->prev->next = newnode; newnode->next->prev = newnode; counter++; size++; return; } else { seek = seek->next; counter++; } } } else // new node goes somewhere before seek { while (seek) { if (seek->value == n) return; else if (seek->value < n) //insert after seek { newnode->prev = seek; newnode->next = seek->next; newnode->prev->next = newnode; newnode->next->prev = newnode; size++; return; } else { seek = seek->prev; counter--; } } } } int ChangeSorter::GetPos(StrBuf input) { if ((head == NULL) || (seek == NULL) || (tail == NULL)) return 0; int n = atoi((const char*) input.Text()); int h = head->value; int s = seek->value; int t = tail->value; if (n == h) return 1; if (n == s) return counter; if (n == t) return size; if ((n < h) || (t < n)) return 0; bool fwd; if (n < s) //before seek { if ( (n - h) < (s - n) ) //closer to head { seek = head; counter = 1; fwd = true; } else //closer to seek { fwd = false; } } else //after seek { if ( (n - s) < (t - n) ) //closer to seek { fwd = true; } else //closer to tail { seek = tail; counter = size; fwd = false; } } if (fwd) //node being sought is somewhere after seek { while (seek) { if (seek->value == n) return counter; else if (n < seek->value) return 0; //not here else { seek = seek->next; counter++; } } } else //node being sought is before seek { while (seek) { if (seek->value == n) return counter; else if (seek->value < n) return 0; //not here else { seek = seek->prev; counter--; } } } return 0; //default case, shouldn't ever happen } StrBuf ChangeSorter::GetChange(int pos) { if ((head == NULL) || (seek == NULL) || (tail == NULL)) return StrBuf(); if ((pos < 1) || (pos > size)) return StrBuf(); if (pos == 1) return head->change; if (pos == size) return tail->change; if (pos == counter) return seek->change; bool fwd; if (pos < counter) //before seek { if ( (pos - 1) < (counter - pos) ) //closer to head { seek = head; counter = 1; fwd = true; } else //closer to seek { fwd = false; } } else //after seek { if ( (pos - counter) < (size - pos) ) //closer to seek { fwd = true; } else //closer to tail { seek = tail; counter = size; fwd = false; } } if (fwd) //node being sought is somewhere after seek { while (seek) { if (counter == pos) return seek->change; else if (pos < counter) return StrBuf(); //not here else { seek = seek->next; counter++; } } } else //node being sought is before seek { while (seek) { if (counter == pos) return seek->change; else if (counter < pos) return StrBuf(); //not here else { seek = seek->prev; counter--; } } } return StrBuf(); //default case, shouldn't ever happen }
# | Change | User | Description | Committed | |
---|---|---|---|---|---|
#6 | 1704 | Sam Stafford |
Change API includes to <*.h> rather than "*.h". No functional change. |
||
#5 | 1685 | Sam Stafford |
Changes to p4hltest that didn't get submitted properly... boggle? |
||
#4 | 1684 | Sam Stafford |
Imported new 02.1 p4api headers and libs. MAJOR code cleanup to make it fit without resorting to re-hacking of the API headers. The hacked headers were not L33T. They deserved D34TH. |
||
#3 | 1522 | Sam Stafford |
New methods for ChangeSorter - StrBuf GetChange(int pos), which tells you what change is at a given position, and int Size(), which tells you the size of the ChangeSorter. No impact on P4HL, so no need to integrate it over. Infrastructure change. |
||
#2 | 1419 | Sam Stafford | Tweaking and edits to make it compile on its own. | ||
#1 | 1417 | Sam Stafford |
Branching backend stuff off for rigorous testing. Grahr. |
||
//guest/sam_stafford/p4hl/src/dlls/ChangeSorter.cpp | |||||
#2 | 1349 | Sam Stafford |
Overhaul to ChangeSorter implementation. Member variables of ChangeSorter have been made private, since nothing was (or should be) accessing them directly, and methods, which remain public, should look the same from outside. The original ChangeSorter was quick and dirty because I wanted to see P4HL working quickly, but it was also about as inefficient as possible because it used single links and linear searches. The new and improved ChangeSorter is a doubly-linked list with intelligent searching that's geared toward sequential access of elements that are close to each other, which is indeed the nature of most of the queries that P4HL makes. Even in a worst-case scenario, this version should perform at least as well as the old one. No noticeable performance change or bugs as of yet, but in theory we'd see the difference with really large sets of data (ones larger than P4HL can show us). |
||
#1 | 937 | Sam Stafford |
Renaming my guest directory to the more conventional sam_stafford. |
||
//guest/samwise/p4hl/src/dlls/ChangeSorter.cpp | |||||
#1 | 936 | Sam Stafford |
Adding P4HL to the public depot. See relnotes.txt for installation instructions; all relevant files are under p4hl/dist. Source code is under p4hl/src in the form of a VC++ project. |