Bernard Kintzing,
A Javascript Implementation of Lexicographic Ordering
What is Lexicographic Ordering?
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set. There are several variants and generalizations of the lexicographical ordering. One variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements.Another variant, widely used in combinatorics, orders subsets of a given finite set by assigning a total order to the finite set, and converting subsets into increasing sequences, to which the lexicographical order is applied. A generalization defines an order on a Cartesian product of partially ordered sets; this order is a total order if and only if all factors of the Cartesian product are totally ordered.
Util Functions
const MIN = "0000";
const MAX = "zzzz";
const BASE = 36;
function updateIndexForKey(array: Array, value: T, newIndex: any, key: string): Array {
let index = undefined;
array.forEach((a, i) => {
if (a[key as keyof T] === value[key as keyof T]) index = i;
});
if (newIndex = 0) array.splice(index, 1);
array.splice(newIndex, 0, value);
return array;
}
const stringToNumber = (s: string): number => {
return parseInt(s, BASE);
};
const numberToString = (n: number): string => {
return n.toString(BASE);
};
export const generateLexoRank = (prev?: string, next?: string): [string, boolean] => {
if (prev === "" || !prev) prev = MIN;
if (next === "" || !next) next = MAX;
// same value provided, need to resort
if (prev === next) return ["", true];
// make sure ranks are the same length
while (prev.length !== next.length) {
if (prev.length > next.length) next += "a";
else prev += "a";
}
const prevNumeric = stringToNumber(prev);
const nextNumeric = stringToNumber(next);
// count of characters between prev and next
const diff = nextNumeric - prevNumeric;
// next is greater than prev, error with inputs
if (diff > 1;
const midRank = array[mid][key as keyof T];
if (typeof midRank !== "string") return array;
switch (midRank.localeCompare(rank)) {
case -1:
// midRank less than rank
start = mid + 1;
break;
case 0:
// midRank equal to rank
start = mid;
end = -1;
break;
case 1:
// midRank greater than rank
end = mid;
break;
}
}
return updateIndexForKey(array, value, start, "id");
}
export function removeLexo(array: Array, value: T, key: string): Array {
const v = value[key as keyof T];
array.forEach((e, i) => {
if (e[key as keyof T] === v) return array.splice(i, 1);
});
return array;
}Implementation
The above utils are designed to work with an ordered array of objects, where each object holds an order key.
Getting Started
When working with lexicographic ordering it is important that the initial array you receive is ordered by the key. When working with large document sets, I prefer to store the data in a context.
Attach Firebase listener to collection
By reading updates on change from the database we can validate that the local data is not stale.
/**
* Attach a listener to the studies arm collection
*
* @param callback - The callback function to be triggered when a doc updates
* @returns a promise with the unsubscribe function for the created listener
*/
export type Listener = (studyId: string, callback: ListenerCallback) => Unsubscribe;
/**
* The callback function triggered by an arm doc change
*
* @param changeType - The type of document change provided by the database
* @param doc - The updated doc
* @param newIndex - The index of the changed document in the result set
* immediately after this DocumentChange (assuming that all prior DocumentChange
* objects and the current DocumentChange object have been applied). Returns -1
* for 'removed' events.
*/
export type ListenerCallback = (changeType: DocumentChangeType, doc: Document, newIndex: number) => void;
const listener: Listener = (callback) => {
return onSnapshot(query(collection(firestore, ), orderBy("order")), (snapshot) => {
snapshot.docChanges().forEach((change) => {
callback(change.type, change.doc.data(), change.newIndex);
});
});
};Subscribe to changes, and notify context
When working with database listeners, remember to detach the listener when it is no longer needed. In this is instance the listener is detached when the component unmounts.
useEffect(() => {
const unsubscribe = listener((changeType, doc) => {
if (changeType === "removed") dispatch(removeDoc(doc));
else dispatch(setDoc(doc));
})
return unsubscribe()
}, []) Updating Context
The context reducers rely on the util classes to retain order when updating/removing.
export const reducers = (state: State, action: Actions): State => {
switch (action.type) {
case "set-doc": {
return {
...state,
map: {
...state.map,
[action.doc.id]: action.doc,
},
ordered: updateLexo(state.ordered, action.doc, "order"),
};
}
case "order-doc": {
return {
...state,
ordered: updateIndexForKey(state.ordered, action.doc, action.newIndex, "id"),
};
}
case "remove-doc": {
const docs = state.map;
delete docs[action.doc.id];
const updated = removeLexo(state.ordered, action.doc, "id");
return {
...state,
map: docs,
ordered: updated,
};
}
}
}; Drag and Drop Reordering
The Drag and Drop is accomplished by using Atlassian's NPM Package.
const OrderableList: React.FC = () => {
const { state, dispatch } = useContext(AppContext);
const getItemStyle = (isDragging: boolean, draggableStyle: DraggingStyle | NotDraggingStyle | undefined): React.CSSProperties => {
return {
...draggableStyle,
userSelect: "none",
pointerEvents: isDragging ? "none" : "inherit",
boxShadow: isDragging ? "2px 2px 2px 1px rgba(0, 0, 0, 0.2);" : "inherit",
};
};
const getListStyle = (isDraggingOver: boolean): React.CSSProperties => {
return {
display: "flex",
background: isDraggingOver ? "#bababa" : "inherit",
borderRadius: "5px",
};
};
const handleDragEnd = (draggableId: string, compare: DNDCompare) => {
const prev = getLexo(state.ordered, "order", compare.prev);
const next = getLexo(state.ordered, "order", compare.next);
const [rank, reorder] = generateLexoRank(prev, next);
// If true we need to rebalance/reorder
if (!reorder) {
const doc = state.map[draggableId];
if (!doc) return;
// update doc in context
dispatch(orderDoc(doc, compare.destination));
// update doc in Firebase server
updateDoc(doc.id, "order", rank);
}
};
const onDragEnd = (result: DropResult) => {
if (!result.destination) return;
const start = result.source.index;
const end = result.destination.index;
if (start === end) return;
if (start < end) {
// moved up in list
handleDragEnd(result.draggableId, {
destination: end,
prev: end,
next: end + 1,
});
} else {
// moved down in list
handleDragEnd(result.draggableId, {
destination: end,
prev: end - 1,
next: end,
});
}
};
return (
<DragDropContext onDragEnd={onDragEnd}>
<Droppable droppableId="ordered-list" direction="horizontal">
{(provided, snapshot) => (
<div {...provided.droppableProps} ref={provided.innerRef} style={getListStyle(snapshot.isDraggingOver)}>
{state.ordered.map((doc, index) => (
<Draggable draggableId={doc.id} index={index}>
{(provided, snapshot) => (
<div
ref={provided.innerRef}
{...provided.draggableProps}
{...provided.dragHandleProps}
style={getItemStyle(snapshot.isDragging, provided.draggableProps.style)}
>
<p>{doc.name}</p>
</div>
)}
</Draggable>
))}
{provided.placeholder}
</div>
)}
</Droppable>
</DragDropContext>
);
};