Tasks:

• find examples of using algos + data structures in the context of chatroom features

  • chat history search
  • word stats
  • chat censoring
  • word autocomplete
  • list of users with their status
  • friends - show 1st degree, 2nd degree
  • group chat suggestion

• migrate to typescript

data structures:

• trees
• lists

TODO:

• implement a list data structure
• store messages in a list (in a variable)
• implement methods:
  • find
  • map
  • forEach
  • first
  • last
  • prepend
  • remove
  • print

try not to google

null

{data: 'bla', next: null}

{ data: 'bla', next: { data: 'blabla', next: null } }

{ data: 'bla', next: { data: 'blabla', next: { data: 'hello', next: null } } }

does not modify list, but creates a new list make it functional

TODO:

• set up testing

• reduce

• make map not mutate the initial value

• make list item generic (also complex types)

• listToString uses reduce

• pass callback to find, and not the item, and return list.data (not the list) https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/find

• remove should be not mutating!

• reduce returns only the data, not the whole list

• look at reduce refernce at MDN

• do it TDD

expected prototype const <T, Acc>reduce(List: a, (acc: Acc, currentValue: T) => Acc, initialValue: Acc) => Acc

• refine the data types type List = ListItem | null type ListItem = { data: T, next: List }

test examples

1. reduce([], sum, 0) => 0
2. summing the length of items accumulator doesn't have to be the same type as the list item! test it! like so: reduce(['abc', 'cbd'], (acc, elem) => acc + elem.length, 0) -> 6

trees make some operations more efficient and some operations less efficient

a node in a tree has an arbitrary amount of children a tree with maxinum of two children per node is a binary tree

TODO:

• finish test for create tree
• implement methods (TDD!)

  • add items (nearest available insertion spot)

  • print tree

    print like this: a

• e
• b
• • c
• d

• make a .toString function instead of print function
• use the .toString function to test other functionalities (hide implementation details!)
• implement a
• null
• b

Homework

• Implement AVL or red-black (!) balancing

The idea: Store messages in a simple array Store words in a tree with arrays containing refences to the positions of messages in the words array In case of two words, perform two searches and then make an intersection of results to find messages that satisfy both searches

TODO:

• change the way data is stored data.word data.positions not the key value thing

• make the search function generic, not only for the key value thing search<K, T>(key: K, tree: <Tree<K, T>>, compare: () => number)

• do the chat search implementation refer to the screenshot in root folder

improvement idea: get results for every word that starts with... then it's not word bound

// TODO:

• message position should be array
• pass messagePosition instead of message array to addMessage, return the added